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

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

Основная идея — построить классификатор в предположении того, что функция $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,\dots ,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$ необходимо задать только ${\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}\mathrm {I}$;
• использовать предположение о том, что матрицы ковариации для всех классов одинаковы (этот метод при использовании первого частного случая для байесовского правила минимальной цены называется линейным дискриминантом Фишера (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}}(x)=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{aligned}\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{aligned}}$

${\begin{aligned}{\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{aligned}}$

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

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

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

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

${\begin{aligned}\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{aligned}}$

${\begin{aligned}{\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{aligned}}$

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

${\begin{aligned}{\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{aligned}}$

${\begin{aligned}{\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{aligned}}$

Отсюда видно, что разделяющая поверхность имеет линейный вид относительно $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