Квадратичный дискриминантный анализ

Квадратичный дискриминантный анализ (Quadratic Discriminant Analysis, QDA [1]) — это метод генеративной классификации, который базируется на предположении о том, что признаки каждого класса распределены согласно многомерному нормальному закону:

$$p(\boldsymbol{x} | y=c) = \mathcal{N}(\boldsymbol{\mu}_c, \Sigma_c)$$

Каждый класс имеет свою собственную матрицу ковариации $\Sigma_c$, что означает, что форма и ориентация распределения объектов каждого класса могут существенно различаться.

Дискриминантная функция

Плотность многомерного нормального распределения в рамках класса имеет вид:

$$p(\boldsymbol{x} | y=c) = \frac{1}{(2\pi)^{D/2} |\Sigma_c|^{1/2}} \exp \left( -\frac{1}{2} (\boldsymbol{x} - \boldsymbol{\mu}_c)^T \Sigma_c^{-1} (\boldsymbol{x} - \boldsymbol{\mu}_c) \right)$$

Как было показано в предыдущей главе, в генеративном подходе прогноз строится через максимизацию рейтинга $g_c(\boldsymbol{x}) = \ln p(y=c) + \ln p(\boldsymbol{x}|y=c)$.

Выведем дискриминантную функцию, подставив плотность в логарифм и отбросив константу $-\frac{D}{2} \ln (2\pi)$, которая не влияет на результат сравнения:

$$g_c(\boldsymbol{x}) = \ln p(y=c) - \frac{1}{2} \ln |\Sigma_c| - \frac{1}{2} (\boldsymbol{x} - \boldsymbol{\mu}_c)^T \Sigma_c^{-1} (\boldsymbol{x} - \boldsymbol{\mu}_c)$$

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

$$g_c(\boldsymbol{x}) = \ln p(y=c) - \frac{1}{2} \ln |\Sigma_c| - \frac{1}{2} \left( \boldsymbol{x}^T \Sigma_c^{-1} \boldsymbol{x} - 2\boldsymbol{\mu}_c^T \Sigma_c^{-1} \boldsymbol{x} + \boldsymbol{\mu}_c^T \Sigma_c^{-1} \boldsymbol{\mu}_c \right)$$

Итоговое выражение для квадратичной дискриминантной функции:

$$g_c(\boldsymbol{x}) = -\frac{1}{2} \boldsymbol{x}^T \Sigma_c^{-1} \boldsymbol{x} + \boldsymbol{\mu}_c^T \Sigma_c^{-1} \boldsymbol{x} - \frac{1}{2} \boldsymbol{\mu}_c^T \Sigma_c^{-1} \boldsymbol{\mu}_c - \frac{1}{2} \ln |\Sigma_c| + \ln p(y=c)$$

Так как функция содержит слагаемое $\boldsymbol{x}^T \Sigma_c^{-1} \boldsymbol{x}$, граница между любыми двумя классами $i,j$ определяется множеством точек $\{\boldsymbol{x}: g_i(\boldsymbol{x}) = g_j(\boldsymbol{x})\}$ и представляет собой квадратичную поверхность.

Аналитическое решение

Преимуществом метода является существование аналитического решения при настройке параметров методом максимального правдоподобия, что делает настройку модели быстрой.

Сложность модели и число параметров

QDA является достаточно гибким методом, что обусловлено большим количеством настраиваемых параметров. Для каждого класса $c \in \{1, \dots, C\}$ необходимо оценить:

• априорную вероятность $\pi_c=p(y=c)$ ($1$ параметр);
• вектор средних $\boldsymbol{\mu}_c$ ($D$ параметров);
• симметричную матрицу ковариации $\Sigma_c$ ($D(D+1)/2$ уникальных параметров).

Суммарное число параметров модели составляет:

$$C \cdot \left( 1 + D + \frac{D(D+1)}{2} \right)$$

При большой размерности признаков $D$ количество параметров растёт квадратично, что может привести к быстрому переобучению (overfitting), особенно если данных в конкретном классе мало.

Также заметим, что необходимость обращения ковариационных матриц для каждого класса имеет вычислительную сложность $O(C \cdot D^3)$.

Регуляризация

При высокой размерности признаков $D$ или малом объёме обучающей выборки $N$ выборочные ковариационные матрицы $\Sigma_y$ становятся плохо обусловленными (ill-conditioned) или вовсе вырожденными. В таких случаях для обеспечения устойчивости модели применяется регуляризованный дискриминантный анализ (Regularized Discriminant Analysis, RDA [1]), основанный на методе сжатия (shrinkage) оценок ковариационных матриц.

Задача

Докажите, что в случае, если количество признаков больше числа объектов ($D > N$), матрица $\Sigma_y$ будет вырожденной, что делает невозможным вычисление обратной матрицы $\Sigma_y^{-1}$ в стандартном QDA.

Основная идея регуляризации заключается в линейном комбинировании (смешивании) исходной матрицы с более стабильными структурами. Для этого используют коэффициент регуляризации $\alpha \in [0, 1]$ для управления степенью этого смешивания.

Индивидуальные ковариационные матрицы классов $\Sigma_y$ смешиваются с общей ковариационной матрицей $\Sigma$ для всех данных:

$$\Sigma'_y(\alpha) = (1 - \alpha) \Sigma_y + \alpha \Sigma$$

При $\alpha = 1$ модель QDA полностью переходит в линейный классификатор LDA, описанный в следующей главе, что резко сокращает число оцениваемых параметров и снижает риск переобучения.

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

Увеличение $\alpha$ приводит к тому, что ориентации и формы эллипсоидов рассеяния разных классов становятся всё более одинаковыми для всех классов.

Для ещё большей устойчивости в формуле выше вместо матрицы $\Sigma$ подставлять её смесь с единичной матрицей, умноженной на общую дисперсию данных $\sigma^2 = \text{tr}(\Sigma)/D$:

$$\Sigma \to (1 - \beta) \Sigma + \beta \sigma^2 I,\quad \beta\in [0,1]$$

В общем случае $\sigma>0$, и такое преобразование гарантирует, что матрица станет положительно определённой и обратимой.

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

Увеличение $\beta$ приближает эллипсоидальные линии уровня распределений к сферической форме, подавляя информацию о корреляциях между признаками. Это повышает устойчивость расчётов, так как итоговая матрица избавляется от околонулевых собственных чисел.

Гиперпараметры $\alpha$ и $\beta$ следует подбирать по валидационной выборке.

Частные случаи

Для снижения сложности модели часто вводят дополнительные ограничения на вид матриц ковариации $\Sigma_c$:

Диагональные матрицы

Можно сделать модельное предположение, что признаки внутри класса линейно независимы. В этом случае $\Sigma_c = \text{diag}(\sigma_{c,1}^2, \dots, \sigma_{c,D}^2)$. В результате число параметров $\Sigma_c$ сокращается с $O(D^2)$ до $O(D)$.

QDA с диагональными ковариационными матрицами также называется гауссовским наивным байесовским классификатором (Gaussian Naive Bayes), поскольку нескоррелированность признаков в случае их совместного нормального распределения эквивалентна их независимости при условии класса [2].

Сферические матрицы

Предполагается, что все признаки не только независимы, но и обладают одинаковой дисперсией $\Sigma_c = \sigma_c^2 \boldsymbol{I}$. В этом случае вместо $O(D)$ параметров для каждой ковариационной матрицы нужно оценить всего один - $\sigma_c^2$.

Классификация в этом случае сводится к поиску ближайшего центра класса $\boldsymbol{\mu}_c$ с учётом разброса точек каждого класса и с поправкой на его частотность.

Одинаковые матрицы ковариации

Предполагается, что ковариационные матрицы всех классов совпадают с общей ковариацией всех данных $\Sigma$:

$$\Sigma_1=\Sigma_2=...=\Sigma_C=\Sigma$$

В этом случае метод называется линейным дискриминантным анализом (Linear Discriminant Analysis, LDA).

Число параметров для оценки ковариационных матриц снижается с $O(CD^2)$ до $O(D^2)$, а сама оценка ковариации становится более устойчивой к шуму и нехватке данных, чем индивидуальные оценки в QDA. Это преимущество становится особенно важным, когда количество объектов в отдельных классах невелико.

Детально этот важный и часто используемый частный случай описывается в следующей главе.

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

Литература

1. Hastie T., Tibshirani R., Friedman J. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. – Springer Science & Business Media, 2009.

2. Soch, Joram, et al. (2024). The Book of Statistical Proofs

3. GeeksForGeeks: Linear and Quadratic Discriminant Analysis using Sklearn.

4. Документация scikit-learn: Linear and Quadratic Discriminant Analysis.