Гауссов классификатор

Гауссовский классификатор

Основная идея — построить классификатор в предположении того, что функция $p(x|y)$ (так называемая функция правдоподобия, т.е. распределение объектов при фиксированном ответе $y$) известна для каждого класса и равна плотности многомерного нормального (гауссовского) распределения: $p(x|y) = N(\mu_y, \Sigma_y) = \frac{1}{\sqrt{(2 \pi) ^ {D} |\det(\Sigma_y)|}} \exp \left(-\frac{1}{2}(x - \mu_y) ^ T \Sigma_y^{-1} (x - \mu_y)\right),$

$y \in \{1, 2, \dots, C\}.$

$\Sigma_y$ — матрица ковариации.

$\mu_y$ — вектор математических ожиданий.

$N$ — число объектов.

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

Таким образом, параметрами гауссовского классификатора являются априорные распределения $p(y)$, вектора математических ожиданий $\mu_y$ и матрицы ковариации $\Sigma_y$, заданные для каждого класса $y \in \{ 1, \dots, C \}$.

Оценка параметров (по методу максимального правдоподобия) и их количество

Семинар Соколова, 9 – 10

$\mu_y = \frac{1}{m}\sum_{i=1}^{m}{x_i}$

$\Sigma_y = \frac{1}{m}\sum_{i=1}^{m}{(x_i - \mu_y)(x_i - \mu_y)^T}$

$m$ — число объектов, относящихся к классу $y$

$C \cdot D$ параметров для оценки $\mu _{y},y\in {1,...,C}$

Note: $\mu_y$ — вектор длины $D$. Всего $C$ классов $\Rightarrow$ $C$ центров $\Rightarrow$ $C \cdot D$ параметров.

$\frac{C \cdot D \cdot(D+1)}{2}$ параметров для оценки $\Sigma_y$

Note: $\Sigma_y$ — симметричная матрица $\Rightarrow$ необходимо задать только $CD^{2}$ параметров и $D$ значений на диагонали, а это потребует $\frac{D \cdot (D+1)}{2}$ параметров. Таких матриц всего $C$ по количеству классов.

Еще $C$ параметров потребуется для того, чтобы задать все априорные распределения $p(y), y \in \{1, \dots, C\}$.

Итого: $\frac{C \cdot D \cdot (D+3)}{2} + C$ параметров содержит модель гауссовского классификатора без упрощающих предположений.

Оценка апостериорной вероятности

Оценим логарифм апостериорной вероятности:

$\log{p(y|x)} = \log{p(x|y)} + \log{p(y)} - \log{p(x)}$$= -\frac{1}{2}(x - \mu_y) ^ T \Sigma_y^{-1} (x - \mu_y) -$ $\frac{1}{2}\log{|\Sigma_y|} - \frac{D}{2}\log{2\pi} +$$\log{p(y)} - \log{p(x)}$

Дискриминантная функция (получаемая из последнего выражения после отбрасывания членов, не зависящих от класса $y$) имеет вид:

$g_y(x) = \log{p(y)} - \frac{1}{2}\log{|\Sigma_y|} - \frac{1}{2}(x - \mu_y) ^ T \Sigma_y^{-1} (x - \mu_y)$

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

Серьезной проблемой гауссовского классификатора является большое число параметров, которые необходимо каким-то образом подбирать.

Есть несколько способов снизить число параметров:

• снизить размерность признакового пространства (например, по методу главных компонент);
• использовать предположение "наивного Байеса" о независимости признаков при условии класса, т.е. о диагональности матриц $\Sigma_y$: $\Sigma_y = diag\{\sigma_{1y}, \dots, \sigma_{Dy}\}, y \in \{1, \dots, C\}$;
• использовать предположение о том, что матрицы ковариации для всех классов пропорциональны единичной: $\Sigma_y = \alpha_y\Iota$;
• использовать предположение о том, что матрицы ковариации для всех классов одинаковы (этот метод называется линейным дискриминантом Фишера (Linear Discriminant Analysis)): $\Sigma_1 = \dots = \Sigma_C = \Sigma$;
• использовать предположение о том, что матрицы ковариации для всех классов пропорциональны некоторой матрице $\Sigma$: $\Sigma_y = \alpha_y \Sigma, y \in \{1, \dots, C \}$.

Квадратичный дискриминантный анализ (Quadratic Discriminant Analysis (QDA)) и линейный дискриминантный анализ (или линейный дискриминант Фишера) (Linear Discriminant Analysis (LDA))

Получим явный вид разделяющих поверхностей в этих двух случаях.

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

Рассмотрим первый частный случай для байесовского правила минимальной цены: ${\hat {y}}=arg{\underset {f}{max}}\{\lambda _{f}p(f|x)\}$.

Тогда дискриминантная функция имеет вид:

$g_y(x) = \log{(\lambda_y p(y)}) - \frac{1}{2}\log{|\Sigma_y|} - \frac{1}{2}(x - \mu_y) ^ T \Sigma_y^{-1} (x - \mu_y)$

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

Запишем уравнение поверхности:

$\begin{align}\log{(\lambda_{y_1}p(y_1))} - \frac{1}{2}\log{|\Sigma_{y_1}|} - \frac{1}{2}(x - \mu_{y_1}) ^ T \Sigma_{y_1}^{-1} (x - \mu_{y_1})\\ = \log{(\lambda_{y_2}p(y_2))} - \frac{1}{2}\log{|\Sigma_{y_2}|} - \frac{1}{2}(x - \mu_{y_2}) ^ T \Sigma_{y_2}^{-1} (x - \mu_{y_2}) \end{align}$

$\begin{align} \frac{1}{2}\left( (x - \mu_{y_2}) ^ T \Sigma_{y_2}^{-1} (x - \mu_{y_2}) - (x - \mu_{y_1}) ^ T \Sigma_{y_1}^{-1} (x - \mu_{y_1}) \right) + \log\left( \frac{\lambda_{y_1}p(y_1)}{\lambda_{y_2}p(y_2)} \right)\\ - \frac{1}{2}\log\left( \frac{|\Sigma_{y_2}|}{|\Sigma_{y_1}|} \right) = 0 \end{align}$

Отсюда видно, что разделяющая поверхность имеет квадратичный вид относительно $x$.

Линейный дискриминант Фишера:

Используем предположение о том, что матрицы ковариации для всех классов одинаковы: $\Sigma_1 = \dots = \Sigma_C = \Sigma$.

$\begin{align}\log{(\lambda_{y_1}p(y_1))} - \frac{1}{2}\log{|\Sigma|} - \frac{1}{2}(x - \mu_{y_1}) ^ T \Sigma^{-1} (x - \mu_{y_1})\\ = \log{(\lambda_{y_2}p(y_2))} - \frac{1}{2}\log{|\Sigma|} - \frac{1}{2}(x - \mu_{y_2}) ^ T \Sigma^{-1} (x - \mu_{y_2}) \end{align}$

$\begin{align} \frac{1}{2}\left( (x - \mu_{y_2}) ^ T \Sigma^{-1} (x - \mu_{y_2}) - (x - \mu_{y_1}) ^ T \Sigma^{-1} (x - \mu_{y_1}) \right) + \log\left( \frac{\lambda_{y_1}p(y_1)}{\lambda_{y_2}p(y_2)} \right) = 0 \end{align}$

Квадратично зависящие от $x$ члены в этом случае сократятся, и получим:

$\begin{align} \frac{1}{2}( x ^ T \Sigma^{-1} (-\mu_{y_2}) + (-\mu_{y_2}) ^ T \Sigma^{-1} x + (-\mu_{y_2}) ^ T \Sigma^{-1} (-\mu_{y_2}) - x ^ T \Sigma^{-1} (-\mu_{y_1})\\ - (-\mu_{y_1}) ^ T \Sigma^{-1} x - (-\mu_{y_1}) ^ T \Sigma^{-1} (-\mu_{y_1})) + \log\left( \frac{\lambda_{y_1}p(y_1)}{\lambda_{y_2}p(y_2)}\right) = 0 \end{align}$

$\begin{align} \frac{1}{2} (x^T \Sigma^{-1} (\mu_{y_1} - \mu_{y_2}) + (\mu_{y_1} - \mu_{y_2})^T \Sigma^{-1} x + (\mu_{y_2} - \mu_{y_1})^T \Sigma^{-1} (\mu_{y_2} - \mu_{y_1}))\\ + \log\left( \frac{\lambda_{y_1}p(y_1)}{\lambda_{y_2}p(y_2)}\right) = 0 \end{align}$

Отсюда видно, что разделяющая поверхность имеет линейный вид относительно $x$.

Практическое применение

• "Наивный Байес": $\Sigma_1, ..., \Sigma_C$ являются диагональными.
• Метод главных компонент (PCA).
• Пропорциональность матриц ковариаций: $\Sigma_1 = \alpha_1\Sigma, ..., \Sigma_C = \alpha_C\Sigma$.
• Линейный дискриминантный анализ Фишера: $\Sigma_1 = ... = \Sigma_C$.

Ссылки

Quadratic discriminant analysis, слайды 2-16

Лекции Китова, слайды 14-21