Перейти к основному содержимому

Линейный дискриминантный анализ

Предположения​

Линейный дискриминантный анализ (Linear Discriminant Analysis, LDA) — это упрощённая модель квадратичного дискриминантного анализа при предположении, что все классы распределены нормально с общей ковариационной матрицей Σ\Sigma:

p(x∣y)=1(2π)D/2∣Σ∣1/2exp⁡(−12(x−μy)TΣ−1(x−μy))p(\boldsymbol{x} | y) = \frac{1}{(2\pi)^{D/2} |\Sigma|^{1/2}} \exp \left( -\frac{1}{2} (\boldsymbol{x} - \boldsymbol{\mu}_y)^T \Sigma^{-1} (\boldsymbol{x} - \boldsymbol{\mu}_y) \right)

где DD — размерность пространства признаков.

Геометрический смысл

Общность ковариационной матрицы означает, что распределение точек всех классов имеют идентичную форму и ориентацию, а различаются распределения только положением своих центров μy\boldsymbol{\mu}_y.

Вывод дискриминантной функции​

В генеративных моделях дискриминантные функции имеют следующий вид:

gy(x)=ln⁡p(x∣y)+ln⁡p(y),y=1,2,...Cg_y(\boldsymbol{x}) = \ln p(\boldsymbol{x}|y) + \ln p(y),\quad y=1,2,...C

Найдём их аналитически, подставив выражение для p(x∣y)p(\boldsymbol{x}|y):

gy(x)=ln⁡(1(2π)D/2∣Σ∣1/2)−12(x−μy)TΣ−1(x−μy)+ln⁡p(y)=−D2ln⁡(2π)−12ln⁡∣Σ∣−12(x−μy)TΣ−1(x−μy)+ln⁡p(y)\begin{aligned} g_y(\boldsymbol{x}) &= \ln \left( \frac{1}{(2\pi)^{D/2} |\Sigma|^{1/2}} \right) - \frac{1}{2} (\boldsymbol{x} - \boldsymbol{\mu}_y)^T \Sigma^{-1} (\boldsymbol{x} - \boldsymbol{\mu}_y) + \ln p(y) \\ &= -\frac{D}{2}\ln(2\pi)-\frac{1}{2}\ln|\Sigma|-\frac{1}{2} (\boldsymbol{x} - \boldsymbol{\mu}_y)^T \Sigma^{-1} (\boldsymbol{x} - \boldsymbol{\mu}_y) + \ln p(y) \end{aligned}

Отбрасывая общее для всех gy(x)g_y(\boldsymbol{x}) слагаемое −D2ln⁡(2π)−12ln⁡∣Σ∣-\frac{D}{2}\ln(2\pi)-\frac{1}{2}\ln|\Sigma|, получаем окончательный вид дискриминантных функций:

gy(x)=−12(x−μy)TΣ−1(x−μy)+ln⁡p(y)g_y(\boldsymbol{x})=-\frac{1}{2} (\boldsymbol{x} - \boldsymbol{\mu}_y)^T \Sigma^{-1} (\boldsymbol{x} - \boldsymbol{\mu}_y) + \ln p(y)
Геометрический смысл прогнозов

Из вида дискриминантной функции видно, что построение прогнозов методом LDA можно интерпретировать как переход в новое декоррелированное пространство признаков x′=Σ−1/2x\boldsymbol{x}' = \Sigma^{-1/2}\boldsymbol{x}, где множество объектов становится сферическим, после чего объект в обновлённом пространстве относится к классу с ближайшим центроидом μy\boldsymbol{\mu}_y с поправкой на частотность каждого класса.

Действительно, представив обратную ковариационную матрицу как квадрат из её корня Σ−1=(Σ−1/2)TΣ−1/2\Sigma^{-1} = (\Sigma^{-1/2})^T \Sigma^{-1/2} получим:

(x−μy)TΣ−1(x−μy)=(x−μy)T(Σ−1/2)TΣ−1/2(x−μy)=[Σ−1/2(x−μy)]T[Σ−1/2(x−μy)]=(Σ−1/2x−Σ−1/2μy)T(Σ−1/2x−Σ−1/2μy)=(x′−μy′)T(x′−μy′),\begin{aligned} (\boldsymbol{x} - \boldsymbol{\mu}_y)^T \Sigma^{-1} (\boldsymbol{x} - \boldsymbol{\mu}_y) &= (\boldsymbol{x} - \boldsymbol{\mu}_y)^T (\Sigma^{-1/2})^T \Sigma^{-1/2} (\boldsymbol{x} - \boldsymbol{\mu}_y) \\ &= \left[ \Sigma^{-1/2} (\boldsymbol{x} - \boldsymbol{\mu}_y) \right]^T \left[ \Sigma^{-1/2} (\boldsymbol{x} - \boldsymbol{\mu}_y) \right] \\ &= (\Sigma^{-1/2}\boldsymbol{x} - \Sigma^{-1/2}\boldsymbol{\mu}_y)^T (\Sigma^{-1/2}\boldsymbol{x} - \Sigma^{-1/2}\boldsymbol{\mu}_y) \\ &= (\boldsymbol{x}'-\boldsymbol{\mu}_y')^T (\boldsymbol{x}'-\boldsymbol{\mu}_y'), \end{aligned}

где x′\boldsymbol{x}' и μy′\boldsymbol{\mu}_y' получены декореллирующим преобразованием:

x′=Σ−1/2xμy′=Σ−1/2μy\begin{aligned} \boldsymbol{x}' &= \Sigma^{-1/2}\boldsymbol{x} \\ \boldsymbol{\mu}_y' &= \Sigma^{-1/2}\boldsymbol{\mu}_y \end{aligned}

Раскроем квадратичную форму:

gy(x)=−12(xTΣ−1x−xTΣ−1μy−μyTΣ−1x+μyTΣ−1μy)+ln⁡p(y)=−12xTΣ−1x+xTΣ−1μy−12μyTΣ−1μy+ln⁡p(y)\begin{aligned} g_y(\boldsymbol{x}) &= -\frac{1}{2} (\boldsymbol{x}^T \Sigma^{-1} \boldsymbol{x} - \boldsymbol{x}^T \Sigma^{-1} \boldsymbol{\mu}_y - \boldsymbol{\mu}_y^T \Sigma^{-1} \boldsymbol{x} + \boldsymbol{\mu}_y^T \Sigma^{-1} \boldsymbol{\mu}_y) + \ln p(y) \\ &= -\frac{1}{2} \boldsymbol{x}^T \Sigma^{-1} \boldsymbol{x} + \boldsymbol{x}^T \Sigma^{-1} \boldsymbol{\mu}_y - \frac{1}{2} \boldsymbol{\mu}_y^T \Sigma^{-1} \boldsymbol{\mu}_y + \ln p(y) \end{aligned}

Заметим, что слагаемое −12xTΣ−1x-\frac{1}{2} \boldsymbol{x}^T \Sigma^{-1} \boldsymbol{x} одинаково для всех классов. Поэтому отбросив это общее слагаемое, получим итоговую дискриминантную функцию:

gy(x)=xTΣ−1μy−12μyTΣ−1μy+ln⁡p(y)g_y(\boldsymbol{x}) = \boldsymbol{x}^T \Sigma^{-1} \boldsymbol{\mu}_y - \frac{1}{2} \boldsymbol{\mu}_y^T \Sigma^{-1} \boldsymbol{\mu}_y + \ln p(y)

Данная функция линейна по x\boldsymbol{x}, поэтому метод LDA является линейным классификатором, разделяющим классы линейными гиперплоскостями.

Особенности метода​

В отличие от QDA, где количество параметров растёт как O(C⋅D2)O(C \cdot D^2), в LDA мы оцениваем только одну ковариационную матрицу, общую для всех классов, поэтому число параметров растёт как O(D2)O(D^2).

Это делает метод более простым и менее склонным к переобучению, по сравнению с QDA. Общая ковариационная матрица менее склонна к вырождению, чем матрицы отдельных классов в QDA, особенно, когда есть классы, содержащие мало наблюдений.

Тем не менее, для большого числа признаков и малого числа наблюдений либо в случае линейной зависимости признаков даже общая ковариационная матрица может вырождаться или быть плохо обусловленной.

В таких случаях применяют регуляризацию, смешивая ковариационную матрицу с единичной матрицей:

Σ^reg=(1−α)Σ^+ασ2I\hat{\Sigma}_{reg} = (1 - \alpha) \hat{\Sigma} + \alpha \sigma^2 I

где α\alpha — гиперпараметр регуляризации, а σ2=tr(Σ^)/D\sigma^2= \text{tr}(\hat{\Sigma})/D — средняя дисперсия всех признаков.

С примерами использования методов QDA и LDA в библиотеке scikit-learn можно ознакомиться в [3] и [4].

Литература​

  1. GeeksForGeeks: Linear and Quadratic Discriminant Analysis using Sklearn.
  2. Документация scikit-learn: Linear and Quadratic Discriminant Analysis.