Гауссовский классификатор [ ]
Основная идея — построить классификатор в предположении того, что функция
p
(
x
|
y
)
{\displaystyle p(x|y) }
(так называемая функция правдоподобия , т.е. распределение объектов при фиксированном ответе
y
{\displaystyle y}
) известна для каждого класса и равна плотности многомерного нормального (гауссовского) распределения:
p
(
x
|
y
)
=
N
(
μ
y
,
Σ
y
)
=
1
(
2
π
)
D
|
det
(
Σ
y
)
|
exp
(
−
1
2
(
x
−
μ
y
)
T
Σ
y
−
1
(
x
−
μ
y
)
)
,
{\displaystyle
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
∈
{
1
,
2
,
…
,
C
}
.
{\displaystyle
y \in \{1, 2, \dots, C\}.
}
Σ
y
{\displaystyle \Sigma_y}
— матрица ковариации.
μ
y
{\displaystyle \mu_y }
— вектор математических ожиданий.
N
{\displaystyle N}
— число объектов.
D
{\displaystyle D}
— размерность признакового пространства.
Таким образом, параметрами гауссовского классификатора являются априорные распределения
p
(
y
)
{\displaystyle p(y) }
, вектора математических ожиданий
μ
y
{\displaystyle \mu_y }
и матрицы ковариации
Σ
y
{\displaystyle \Sigma_y}
, заданные для каждого класса
y
∈
{
1
,
…
,
C
}
{\displaystyle y \in \{ 1, \dots, C \} }
.
Оценка параметров (по методу максимального правдоподобия) и их количество [ ]
Семинар Соколова, 9 – 10
μ
y
=
1
m
∑
i
=
1
m
x
i
{\displaystyle
\mu_y = \frac{1}{m}\sum_{i=1}^{m}{x_i}
}
Σ
y
=
1
m
∑
i
=
1
m
(
x
i
−
μ
y
)
(
x
i
−
μ
y
)
T
{\displaystyle
\Sigma_y = \frac{1}{m}\sum_{i=1}^{m}{(x_i - \mu_y)(x_i - \mu_y)^T}
}
m
{\displaystyle m}
— число объектов, относящихся к классу
y
{\displaystyle y}
C
⋅
D
{\displaystyle C \cdot D}
параметров для оценки
μ
y
,
y
∈
{
1
,
…
,
C
}
{\displaystyle \mu_y, y \in
\{1, \dots, C\}}
Note:
μ
y
{\displaystyle \mu_y }
— вектор длины
D
{\displaystyle D}
. Всего
C
{\displaystyle C}
классов
⇒
{\displaystyle \Rightarrow}
C
{\displaystyle C}
центров
⇒
{\displaystyle \Rightarrow}
C
⋅
D
{\displaystyle C \cdot D}
параметров.
C
⋅
D
⋅
(
D
+
1
)
2
{\displaystyle \frac{C \cdot D \cdot(D+1)}{2} }
параметров для оценки
Σ
y
{\displaystyle \Sigma_y}
Note:
Σ
y
{\displaystyle \Sigma_y}
— симметричная матрица
⇒
{\displaystyle \Rightarrow}
необходимо задать только
D
⋅
(
D
+
1
)
2
{\displaystyle \frac{D \cdot (D+1)}{2} }
параметров. Таких матриц всего
C
{\displaystyle C}
по количеству классов.
Еще
C
{\displaystyle C}
параметров потребуется для того, чтобы задать все априорные распределения
p
(
y
)
,
y
∈
{
1
,
…
,
C
}
{\displaystyle p(y), y \in \{1, \dots, C\}}
.
Итого:
C
⋅
D
⋅
(
D
+
3
)
2
+
C
{\displaystyle \frac{C \cdot D \cdot (D+3)}{2} + C}
параметров содержит модель гауссовского классификатора без упрощающих предположений.
Оценка апостериорной вероятности [ ]
Оценим логарифм апостериорной вероятности:
log
p
(
y
|
x
)
=
log
p
(
x
|
y
)
+
log
p
(
y
)
−
log
p
(
x
)
{\displaystyle \log{p(y|x)} = \log{p(x|y)} + \log{p(y)} - \log{p(x)} }
=
−
1
2
(
x
−
μ
y
)
T
Σ
y
−
1
(
x
−
μ
y
)
−
{\displaystyle = -\frac{1}{2}(x - \mu_y) ^ T \Sigma_y^{-1} (x - \mu_y) - }
1
2
log
|
Σ
y
|
−
D
2
log
2
π
+
{\displaystyle \frac{1}{2}\log{|\Sigma_y|} - \frac{D}{2}\log{2\pi} + }
log
p
(
y
)
−
log
p
(
x
)
{\displaystyle \log{p(y)} - \log{p(x)} }
Дискриминантная функция (получаемая из последнего выражения после отбрасывания членов, не зависящих от класса
y
{\displaystyle y}
) имеет вид:
g
y
(
x
)
=
log
p
(
y
)
−
1
2
log
|
Σ
y
|
−
1
2
(
x
−
μ
y
)
T
Σ
y
−
1
(
x
−
μ
y
)
{\displaystyle 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) }
Снижение числа параметров [ ]
Серьезной проблемой гауссовского классификатора является большое число параметров , которые необходимо каким-то образом подбирать.
Есть несколько способов снизить число параметров:
снизить размерность признакового пространства (например, по методу главных компонент );
использовать предположение "наивного Байеса" о независимости признаков при условии класса, т.е. о диагональности матриц
Σ
y
{\displaystyle \Sigma_y}
:
Σ
y
=
d
i
a
g
{
σ
1
y
,
…
,
σ
D
y
}
,
y
∈
{
1
,
…
,
C
}
{\displaystyle \Sigma_y = diag\{\sigma_{1y}, \dots, \sigma_{Dy}\}, y \in \{1, \dots, C\} }
;
использовать предположение о том, что матрицы ковариации для всех классов пропорциональны единичной:
Σ
y
=
α
y
I
{\displaystyle \Sigma_y = \alpha_y\Iota}
;
использовать предположение о том, что матрицы ковариации для всех классов одинаковы (этот метод при использовании первого частного случая для байесовского правила минимальной цены называется линейным дискриминантом Фишера (Linear Discriminant Analysis) ):
Σ
1
=
⋯
=
Σ
C
=
Σ
{\displaystyle \Sigma_1 = \dots = \Sigma_C = \Sigma }
;
использовать предположение о том, что матрицы ковариации для всех классов пропорциональны некоторой матрице
Σ
{\displaystyle \Sigma}
:
Σ
y
=
α
y
Σ
,
y
∈
{
1
,
…
,
C
}
{\displaystyle \Sigma_y = \alpha_y \Sigma, y \in \{1, \dots, C \} }
.
Квадратичный дискриминантный анализ (Quadratic Discriminant Analysis (QDA)) и линейный дискриминантный анализ (или линейный дискриминант Фишера) (Linear Discriminant Analysis (LDA)) [ ]
Получим явный вид разделяющих поверхностей в этих двух случаях.
Для этого приравняем дискриминантные функции двух классов и таким образом получим уравнение поверхности, разделяющей эти два класса.
Рассмотрим первый частный случай для байесовского правила минимальной цены :
y
^
(
x
)
=
a
r
g
m
a
x
f
{
λ
f
p
(
f
|
x
)
}
{\displaystyle \hat{y}(x) = arg\underset{f}{max}\{\lambda_f p(f|x)\} }
.
Тогда дискриминантная функция имеет вид:
g
y
(
x
)
=
log
(
λ
y
p
(
y
)
)
−
1
2
log
|
Σ
y
|
−
1
2
(
x
−
μ
y
)
T
Σ
y
−
1
(
x
−
μ
y
)
{\displaystyle 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) }
Квадратичный дискриминантный анализ [ ]
Запишем уравнение поверхности:
log
(
λ
y
1
p
(
y
1
)
)
−
1
2
log
|
Σ
y
1
|
−
1
2
(
x
−
μ
y
1
)
T
Σ
y
1
−
1
(
x
−
μ
y
1
)
=
log
(
λ
y
2
p
(
y
2
)
)
−
1
2
log
|
Σ
y
2
|
−
1
2
(
x
−
μ
y
2
)
T
Σ
y
2
−
1
(
x
−
μ
y
2
)
{\displaystyle \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}}
1
2
(
(
x
−
μ
y
2
)
T
Σ
y
2
−
1
(
x
−
μ
y
2
)
−
(
x
−
μ
y
1
)
T
Σ
y
1
−
1
(
x
−
μ
y
1
)
)
+
log
(
λ
y
1
p
(
y
1
)
λ
y
2
p
(
y
2
)
)
−
1
2
log
(
|
Σ
y
2
|
|
Σ
y
1
|
)
=
0
{\displaystyle \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
{\displaystyle x}
.
Линейный дискриминант Фишера [ ]
Продолжаем рассматривать первый частный случай для байесовского правила минимальной цены :
y
^
(
x
)
=
a
r
g
m
a
x
f
{
λ
f
p
(
f
|
x
)
}
{\displaystyle \hat{y}(x) = arg\underset{f}{max}\{\lambda_f p(f|x)\} }
.
Используем предположение о том, что матрицы ковариации для всех классов одинаковы:
Σ
1
=
⋯
=
Σ
C
=
Σ
{\displaystyle \Sigma_1 = \dots = \Sigma_C = \Sigma }
.
log
(
λ
y
1
p
(
y
1
)
)
−
1
2
log
|
Σ
|
−
1
2
(
x
−
μ
y
1
)
T
Σ
−
1
(
x
−
μ
y
1
)
=
log
(
λ
y
2
p
(
y
2
)
)
−
1
2
log
|
Σ
|
−
1
2
(
x
−
μ
y
2
)
T
Σ
−
1
(
x
−
μ
y
2
)
{\displaystyle \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}}
1
2
(
(
x
−
μ
y
2
)
T
Σ
−
1
(
x
−
μ
y
2
)
−
(
x
−
μ
y
1
)
T
Σ
−
1
(
x
−
μ
y
1
)
)
+
log
(
λ
y
1
p
(
y
1
)
λ
y
2
p
(
y
2
)
)
=
0
{\displaystyle \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
{\displaystyle x}
члены в этом случае сократятся, и получим:
1
2
(
x
T
Σ
−
1
(
−
μ
y
2
)
+
(
−
μ
y
2
)
T
Σ
−
1
x
+
(
−
μ
y
2
)
T
Σ
−
1
(
−
μ
y
2
)
−
x
T
Σ
−
1
(
−
μ
y
1
)
−
(
−
μ
y
1
)
T
Σ
−
1
x
−
(
−
μ
y
1
)
T
Σ
−
1
(
−
μ
y
1
)
)
+
log
(
λ
y
1
p
(
y
1
)
λ
y
2
p
(
y
2
)
)
=
0
{\displaystyle \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}}
1
2
(
x
T
Σ
−
1
(
μ
y
1
−
μ
y
2
)
+
(
μ
y
1
−
μ
y
2
)
T
Σ
−
1
x
+
(
μ
y
2
−
μ
y
1
)
T
Σ
−
1
(
μ
y
2
−
μ
y
1
)
)
+
log
(
λ
y
1
p
(
y
1
)
λ
y
2
p
(
y
2
)
)
=
0
{\displaystyle \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
{\displaystyle x}
.
Практическое применение [ ]
Ссылки [ ]
Quadratic discriminant analysis, слайды 2-16
Лекции Китова, слайды 14-21