Классификация на основе байесовской теории решений

2.1. Байесовский подход

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

Задано $$M$$ классов $$\Omega_1,\Omega_2,\ldots,\Omega_M$$, а также $$P(\Omega_i|x), \; i=1,2,\ldots,M$$ – вероятность того, что неизвестный образ, представляемый вектором признаков $$x$$, принадлежит классу $$\Omega_i$$.

$$P(\Omega_i|x)$$ называется апостериорной вероятностью, поскольку задает распределение индекса класса после эксперимента ( a posteriori – т.е. после того, как значение вектора признаков $$x$$ было получено).

Рассмотрим случай двух классов $$\Omega_1$$ и $$\Omega_2$$. Естественно выбрать решающее правило таким образом: объект относим к тому классу, для которого апостериорная вероятность выше. Такое правило классификации по максимуму апостериорной вероятности называется Байесовским: если $$P(\Omega_1|x)>P(\Omega_2|x)$$, то $$x$$ классифицируется в $$\Omega_1$$, иначе в $$\Omega_2$$. Таким образом, для Байесовского решающего правила необходимо получить апостериорные вероятности $$P(\Omega_i|x),\; i=1,2$$. Это можно сделать с помощью формулы Байеса.

Формула Байеса, полученная Т. Байесом, позволяет вычислить апостериорные вероятности событий через априорные вероятности и функции правдоподобия (была опубликована в 1763 году, через два года после смерти автора).

Пусть $$A_1,A_2,\ldots,A_n$$ – полная группа несовместных событий. $$\bigcup_{i=1}^n A_i=\Omega$$. $$A_i\cap A_j=\oslash$$, при $$i\neq j$$. Тогда апостериорная вероятность имеет вид:$$P(A_i|B)=\frac{P(A_i)P(B|A_i)}{\sum_{i=1}^n P(A_i)P(B|A_i)} ,$$ где $$P(A_i)$$ – априорная вероятность события $$A_i, P(B|A_i)$$ – условная вероятность события $$B$$ при условии, что произошло событие $$A_i$$.

Рассмотрим получение апостериорной вероятности $$P(\Omega|x)$$, зная $$P(\Omega)$$ и $$P(x|\Omega)$$.$$\begin{gathered} P(AB)=P(A|B)P(B), \; P(AB)=P(B|A)P(A) \\ P(A|B)P(B)=P(B|A)P(A) \\ P(B|A)=\frac{P(A|B)P(B)}{P(A)} \end{gathered}$$

Если $$P(A)$$ и $$P(A|B)$$ описываются плотностями $$p(x)$$ и $$p(x|B)$$, то$$P(B|x)=\frac{p(x|B)P(B)}{p(x)}\Rightarrow P(\Omega_i|x)=\frac{p(x|\Omega_i)P(\Omega_i)}{p(x)}.$$

При проверке классификации сравнение $$P(\Omega_1|x)$$ и $$P(\Omega_2|x)$$ эквивалентно сравнению $$p(x|\Omega_1)P(\Omega_1)$$ и $$p(x|\Omega_2)P(\Omega_2)$$. В случае, когда $$P(\Omega_1|x)=P(\Omega_2|x)$$, считается, что мера множества $$x$$ равна нулю.

Таким образом, задача сравнения по апостериорной вероятности сводится к вычислению величин $$P(\Omega_1), P(\Omega_2), p(x|\Omega_1), p(x|\Omega_2)$$. Будем считать, что у нас достаточно данных для определения вероятности принадлежности объекта каждому из классов $$P(\Omega_i), \; i=1,2$$. Такие вероятности называются априорными вероятностями классов. А также будем считать, что известны функции распределения вектора признаков для каждого класса $$P(x|\Omega_1), i=1,2$$. Они называются функциями правдоподобия $$x$$ по отношению к $$\Omega_i$$. Если априорные вероятности и функции правдоподобия неизвестны, то их можно оценить методами математической статистики на множестве прецедентов. Например, $$P(\Omega_i)\approx\frac{N_i}{N}$$, где $$N_i$$ – число прецедентов из $$\Omega_i, \; i=1,2$$. $$N$$ – общее число прецедентов. $$P(x|\Omega_i)$$ может быть приближено гистограммой распределения вектора признаков для прецедентов из класса $$\Omega_i$$.

Итак, Байесовский подход к статистическим задачам основывается на предположении о существовании некоторого распределения вероятностей для каждого параметра. Недостатком этого метода является необходимость постулирования как существования априорного распределения для неизвестного параметра, так и знание его формы.

2.2. Ошибка классификации

Определение. Вероятность $$P_e=P(x\in R_2,\Omega_1)+P(x\in R_1,\Omega_2)$$ называется ошибкой классификации,$$R_1=\{x:P(\Omega_1)p(x|\Omega_1)>P(\Omega_2)p(x|\Omega_2)\}, \; R_2=\{x:P(\Omega_1)p(x|\Omega_1)<P(\Omega_2)p(x|\Omega_2)\}$$ – области решения $$(\Omega_1\cap\Omega_2=\oslash)$$.

Теорема. Байесовский классификатор является оптимальным по отношению к минимизации вероятности ошибки классификации.

Доказательство. Рассмотрим ошибку классификации:$$\begin{gathered} P_e=P(x\in R_2,\Omega_1)+P(x\in R_1,\Omega_2)= \\ = P(\Omega_1)\int_{R_2}p(x|\Omega_1)dx+P(\Omega_2)\int_{R_1}p(x|\Omega_2)dx = \\ = P(\Omega_1)\left( 1-\int_{R_1}p(x|\Omega_1)dx\right)+P(\Omega_2)\int_{R_1}p(x|\Omega_2)dx = \\ = P(\Omega_1)-P(\Omega_1)\int_{R_1}p(x|\Omega_1)dx+P(\Omega_2)\int_{R_1}p(x|\Omega_2)dx = \end{gathered}$$

Учитывая формулу Байеса:$$p(x|\Omega_i)=\frac{P(\Omega_i|x)p(x)}{P(\Omega_i)}, \; i=1,2,$$ получим:$$\begin{gathered} =P(\Omega_1)-P(\Omega_1)\int_{R_1}\frac{P(\Omega_1|x)p(x)}{P(\Omega_1)}dx+P(\Omega_2)\int_{R_1}\frac{P(\Omega_2|x)p(x)}{P(\Omega_2)}dx = \\ =P(\Omega_1)-\int_{R_1}P(\Omega_1|x)p(x)dx+\int_{R_1}P(\Omega_2|x)p(x)dx =\\ =P(\Omega_1)-\int_{R_1}p(x)(P(\Omega_1|x)-P(\Omega_2|x))dx \end{gathered}$$ Таким образом, минимум достигается, когда $$R_1=\{ x:P(\Omega_1|x)>P(\Omega_2|x)\}$$. $$R_2$$ выбирается из остальных точек.

Данная теорема была доказана для двух классов $$\Omega_1$$ и $$\Omega_2$$. Обобщим ее на $$M$$ классов.

Пусть вектор признаков $$x$$ относится к классу $$\Omega_i$$, если $$P(\Omega_i|x)>P(\Omega_j|x)$$, при $$i\neqj, \; i=1,2,\ldots,M, \; j=1,2,\ldots,M$$. Соответственно необходимо доказать, что данное правило минимизирует вероятность ошибки классификации. Для доказательства следует воспользоваться формулой правильной классификации $$P_r=1-P_e$$.

Доказательство. Воспользуемся формулой правильной классификации $$P_r=1-P_e$$.$$\begin{gathered} P_r=P(x\in R_1,\Omega_1)+P(x\in R_2,\Omega_2)+\ldots+P(x\in R_i,\Omega_i)= \\ =\sum_{i=1}^l P(x\in R_i|\Omega_i)P(\Omega_i)= \\ =\sum_{i=1}^l P(\Omega_i)\int\limits_{R_i}p(x|\Omega_i)dx= \\ =P(\Omega_1)\left(1-\sum_{i=2}^l\int\limits_{R_i}p(x|\Omega_1)dx \right)+\sum_{i=2}^l P(\Omega_i)\int\limits_{R_i}p(x|\Omega_i)dx= \\ =P(\Omega_1)-\sum_{i=2}^l\left[P(\Omega_1)\int\limits_{R_i}p(x|\Omega_1)dx-P(\Omega_i)\int\limits_{R_i}p(x|\Omega_i)dx\right]= \end{gathered}$$ Учитывая формулу Байеса: $$p(x|\Omega_i)=\frac{P(\Omega_i|x)p(x)}{P(\Omega_i)}, \; i=1,2,\ldots,l$$, получим:$$\begin{gathered} =P(\Omega_1)-\sum_{i=2}^l\left[P(\Omega_1)\int\limits_{R_i}\frac{P(\Omega_1|x)p(x)}{P(\Omega_1)}dx- P(\Omega_1)\int\limits_{R_i}\frac{P(\Omega_i|x)p(x)}{P(\Omega_i)}dx\right]=\\ =P(\Omega_1)-\sum_{i=2}^l\left[\int\limits_{R_i}P(\Omega_1|x)p(x)dx-\int\limits_{R_i}P(\Omega_1|x)p(x)dx\right]=\\ =P(\Omega_1)-\sum_{i=2}^l\int\limits_{R_i}p(x)\left[P(\Omega_1|x)-P(\Omega_i|x) \right]dx \end{gathered}$$ Таким образом, максимум достигается, когда $$P(\omega_1|x)<P(\omega_i|x)$$. Аналогично для всех $$j=1,2,\ldots,l$$ максимум достигается, когда $$R_i=\{x:P(\omega_j|x)<P(\omega_i|x)\}$$.

2.3. Минимизация среднего риска

Вероятность ошибки классификации – не всегда лучший критерий проверки классификатора. В том случае, когда цена ошибок различного типа существенно различается, лучше использовать другой критерий качества классификации – минимум среднего риска.

Рассмотрим задачу классификации по $$M$$ классам. $$R_j, \; j=1,2,\ldots,M$$ – области предпочтения классов $$\varpi$$. Предположим, что вектор $$x$$ из класса $$\Omega_k$$ лежит в $$R_i, \; i\neq k$$, т.е. классификация происходит с ошибкой. Свяжем с этой ошибкой штраф $$\lambda_{ki}$$ называемый потерями в результате того, что объект из класса $$\Omega_k$$ был принят за объект из класса $$\Omega_i$$. Обозначим через $$L=\|\lambda_{ki}\|$$ матрицу потерь.

Определение. Выражение $$r_k=\sum_{i=1}^M \lambda_{ki} P\{x\in R_i|\Omega_k\}=\sum_{i=1}^M\lambda_{ki}\int\limits_{R_i}p(x|\Omega_k)dx$$ называется риском при классификации объекта класса $$\Omega_k$$.

Определение. Выражение $$r=\sum_{i=1}^M r_i P(\Omega_i)$$ называется общим средним риском.

Теперь мы можем поставить задачу о выборе классификатора, минимизирующего этот риск. Преобразуем выражение общего среднего риска:$$\begin{gathered} r=\sum_{i=1}^M r_k P(\Omega_k)=\sum_{k=1}^M P(\Omega_k)\sum_{i=1}^M\lambda_{ki}\int\limits_{R_i}p(x|\Omega_k)dx= \\ =\sum_{i=1}^M\left( \sum_{k=1}^M P(\Omega_k)\lambda_{ki}\int\limits_{R_i}p(x|\Omega_k)dx\right)= \\ =\sum_{i=1}^M\int\limits_{R_i}\left(\sum_{k=1}^M\lambda_{ki}p(x|\Omega_k)P(\Omega_k)\right)dx \end{gathered}$$

Из этого выражения видно, что риск минимален, когда каждый из интегралов в данной сумме минимален, т.е. $$x\in R_i$$, если $$l_i<l_j$$, при $$i\neq j$$, где $$l_i=\sum_{k=1}^M\lambda_{ki}p(x|\Omega_k)P(\Omega_k), l_j=\sum_{k=1}^M\lambda_{kj}p(x|\Omega_k)P(\Omega_k)$$.

Пример. Рассмотрим ситуацию радиолокационной разведки. На экране радара отражаются не только цели, но и помехи. Такой помехой может служить стая птиц, которую можно принять за небольшой самолет. В данном случае это двухклассовая задача.

Рассмотрим матрицу штрафов: $$L=\|\lambda_{ki}\|,\;i=1,2,\;k=1,2$$. $$\lambda_{ki}$$ – это штраф за принятие объекта из класса $$k$$ за объект класса $$i$$. Тогда$$\begin{gathered} l_1=\lambda_{11}p(x|\Omega_1)P(\Omega_1)+\lambda_{21}p(x|\Omega_2)P(\Omega_2)\\ l_2=\lambda_{12}p(x|\Omega_1)P(\Omega_1)+\lambda_{22}p(x|\Omega_2)P(\Omega_2) \end{gathered}$$ Пусть $$x$$ относится у классу $$\Omega_1$$, если $$l_1<l_2$$, т.е.$$\begin{gathered} \lambda_{11}p(x|\Omega_1)P(\Omega_1)+\lambda_{21}p(x|\Omega_2)P(\Omega_2)< \lambda_{12}p(x|\Omega_1)P(\Omega_1)+\lambda_{22}p(x|\Omega_2)P(\Omega_2) \\ (\lambda_{21}-\lambda_{22})p(x|\Omega_2)P(\Omega_2)<(\lambda_{12}-\lambda_{11})p(x|\Omega_1)P(\Omega_1) \end{gathered}$$ Т.к. $$\lambda_{21}>\lambda_{22}$$ и $$\lambda_{12}>\lambda_{11}$$, то$$\frac{p(x|\Omega_1)}{p(x|\Omega_2)}>\frac{\lambda_{21}-\lambda_{22}}{\lambda_{12}-\lambda_{11}}\cdot\frac{P(\Omega_2)}{P(\Omega_1)}$$

Стоящее в левой части неравенства отношение $$l_{12}=\frac{p(x|\Omega_1)}{p(x|\Omega_2)}$$ называется отношением правдоподобия. Неравенство описывает условие предпочтения класса $$\Omega_1$$ классу $$\Omega_2$$.

Пример. Рассмотрим двухклассовую задачу, в которой для единственного признака $$x$$ известна плотность распределения:$$\begin{gathered} p(x|\Omega_1)=\frac{1}{\sqrt{\pi}}\exp\left(-x^2\right) \\ p(x|\Omega_2)=\frac{1}{\sqrt{\pi}}\exp\left(-(x-1)^2\right) \end{gathered}$$ Пусть, также, априорные вероятности $$P(\Omega_1)=P(\Omega_2)=\frac12$$.

Задача – вычислить пороги для

a) минимальной вероятности ошибки

b) минимального риска при матрице риска$$L=\begin{pmatrix}00.5\\10\end{pmatrix}.$$

Решение задачи a):$$\begin{gathered} p(x|\Omega_1)P(\Omega_1)=p(x|\Omega_2)P(\Omega_2) \\ \exp\left(-x^2\right)=\exp\left(-(x-1)^2\right) \\ -x^2=-(x-1)^2 \\ \widehat{x}=\frac12 \end{gathered}$$

Решение задачи b):$$\begin{gathered} \frac{p(x|\Omega_1)}{p(x|\Omega_2)}=\frac{\lambda_{21}-\lambda_{22}}{\lambda_{12}-\lambda_{11}}\cdot\frac{P(\Omega_2)}{P(\Omega_1)} \\ \frac{\exp\left(-x^2\right)}{\exp\left(-(x-1)^2\right)} \\ -x^2=\ln 2-(x-1)^2 \\ \widetilde{x}=frac12(1-\ln 2) \end{gathered}$$

Пример. Рассмотрим двухклассовую задачу с Гауссовскими плотностями распределения $$p(x|\Omega_1)\cong N(0,\sigma^2)$$ и $$p(x|\Omega_2)\cong N(1,\sigma^2)$$ и матрицей потерь $$L=\begin{pmatrix}0\lambda_{12}\\ \lambda_{21}0\end{pmatrix}$$.

Задача – вычислить порог для проверки отношения правдоподобия.

Решение. С учетом матрицы потерь отношение правдоподобия$$\frac{p(x|\Omega_1)}{p(x|\Omega_2)}=\frac{\lambda_{21}-\lambda_{22}}{\lambda_{12}-\lambda_{11}}\cdot\frac{P(\Omega_2)}{P(\Omega_1)}$$ запишется в виде$$\frac{p(x|\Omega_1)}{p(x|\Omega_2)}=\frac{\lambda_{21}}{\lambda_{12}}\cdot\frac{P(\Omega_2)}{P(\Omega_1)}$$

Запишем плотности распределения$$\begin{gathered} p(x|\Omega_1)=\frac{1}{\sqrt{2\pi\sigma}}\exp\left(-\frac{x^2}{2\sigma^2}\right); \; p(x|\Omega_2)=\frac{1}{\sqrt{2\pi\sigma}}\exp\left(-\frac{(x-1)^2}{2\sigma^2}\right) \\ \frac{p(x|\Omega_1)}{p(x|\Omega_2)}=\frac{\lambda_{21}}{\lambda_{12}}\cdot\frac{P(\Omega_2)}{P(\Omega_1)}= \exp\left(\frac{(x-1)^2}{2\sigma^2}-\frac{x^2}{2\sigma^2}\right) \\ x^2-(x-1)^2=-2\sigma^2 \ln\left(\frac{\lambda_{21}}{\lambda_{12}}\cdot\frac{P(\Omega_2)}{P(\Omega_1)}\right) \\ x=\frac12-\sigma^2\ln\left(\frac{\lambda_{21}}{\lambda_{12}}\cdot\frac{P(\Omega_2)}{P(\Omega_1)}\right) \end{gathered}$$

Пример. Рассмотрим двухклассовую задачу с матрицей потерь $$L=\|\lambda_{ki}\|, \; k=1,2 \, i=1,2$$. Пусть $$\varepsilon_1$$ – вероятность ошибки, соответствующая вектору из класса $$\Omega_1$$ и $$\varepsilon_2$$ – вероятность ошибки, соответствующая вектору из класса $$\Omega_2$$. Задача – найти средний риск.

Решение.$$\begin{gathered} r=\sum_{i=1}^M r_k P(\Omega_k)= \\ =\sum_{i=1}^M\left(\sum_{k=1}^M P(\Omega_k)\lambda_{ki}\int\limits_{R_i}p(x|\Omega_k)dx\right)= \\ =\lambda_{11}(1-\varepsilon_1)P(\Omega_1)+ \lambda_{12}\varepsilon_1 P(\Omega_1)+ \lambda_{21}\varepsilon_2 P(\Omega_2)+ \lambda_{22}(1-\varepsilon_2)P(\Omega_2)= \\ =\lambda_{11}P(\Omega_1)+(\lambda_{12}-\lambda_{11})\varepsilon_1 P(\Omega_1)+ (\lambda_{21}-\lambda_{22})\varepsilon_2 P(\Omega_2)+\lambda_{22}P(\Omega_2) \end{gathered}$$

Пример. Доказать, что в задаче классификации по $$M$$ классам, вероятность ошибки классификации ограничена: $$P_e=\frac{M-1}{M}$$.

Указание: показать, что $$\max_{i=1,\ldots,M} P(\varpi_i|x)\geq\frac1M$$.

2.4. Дискриминантные функции и поверхности решения

Минимизация риска и вероятности ошибки эквивалентны разделению пространства признаков на $$M$$ областей. Если области $$R_i$$ и $$R_j$$ смежные, то они разделены поверхностью решения в многомерном пространстве. Для случая минимизации вероятности ошибки поверхность решения задается уравнением:$$P(\Omega_i|x)-P(\Omega_j|x)=0$$ В данном уравнении приходится оперировать с вероятностями. Иногда вместо вероятностей удобнее работать с функцией от вероятности:$$g_i(x)=f(P(\Omega_i|x)),$$ где функция $$f$$ монотонно возрастает.

Определение. Функция $$g_i(x)=f(P(\Omega_i|x))$$ называется дискриминантной функцией.

Таким образом, поверхность решения будет задаваться уравнением:$$g_i(x)-g_j(x)=0, \; i=1,2,\ldots,M \, , \; i\neq j.$$

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

2.5. Байесовский классификатор для нормального распределения

Распределение Гаусса очень широко используется по причине вычислительного удобства и адекватности во многих случаях. Рассмотрим многомерную плотность нормального распределения $$N(\mu_i,\Sigma_i)$$:$$p(x|\Omega_i)=\frac{1}{(2\pi)^{1\!/2}|\Sigma_i|^{1\!/2}}\cdot \exp\left(-\frac12 \frac{(x-\mu_i)^T}{\Sigma_i(x-\mu_i)}\right),\; i=1,2,\ldots,M$$ где $$\mu_i=E[X]$$ – математическое ожидание случайной величины $$x$$ в классе $$\Omega_i$$, $$\Sigma_i$$ – матрица ковариации размерности $$l\times l$$ для класса $$\Omega_i, \; \Sigma_i=E\lfloor(x-\mu_i)(x-\mu_i)^T\rfloor$$, $$|\Sigma_i|$$ – определитель матрицы ковариации. Здесь $$x, \mu_i$$ – это вектора-столбцы, а $$x^T, \mu_i^T$$ - вектора-строки.

5.1. Квадратичная поверхность решения. На основе этих данных необходимо построить байесовский классификатор. Рассмотрим логарифмическую дискриминантную функцию:$$\begin{gathered} g_i(x) = \ln (P(\Omega_i|x))= \\ =\ln (p(x|\Omega_i)P(\Omega_i))= \\ =\ln p(x|\Omega_i)+\ln P(\Omega_i)= \\ =-\frac{1}{2} \frac{(x-\mu_i)}{\Sigma_i}(x-\mu_i)^T+\ln P(\Omega_i) +\ln \frac{1}{(2\pi)^{1\!/2}|\Sigma_i|^{1\!/2}}= \\ =-\frac{1}{2} \frac{(x-\mu_i)}{\Sigma_i}(x-\mu_i)^T+\ln P(\Omega_i) -\frac{l}{2} \ln(2\pi)-\frac12\ln |\Sigma_i| = \\ =-\frac{1}{2} \frac{(x-\mu_i)}{\Sigma_i}(x-\mu_i)^T+\ln P(\Omega_i) + C_i, \text{ где } C_i=-\frac{l}{2} \ln(2\pi)-\frac{1}{2} \ln |\Sigma_i| \end{gathered}$$

Эта функция представляет собой квадратичную форму. Следовательно, разделяющая поверхность $$g_i(x)-g_j(x)=0$$ является гиперповерхностью второго порядка. Поэтому Байесовский классификатор является квадратичным классификатором.

Пример. Пусть $$l=2,\; \Sigma_i= \begin{pmatrix} \sigma_i^2 0 \\ 0 \sigma_i^2 \end{pmatrix} $$. Тогда $$\frac{1}{\Sigma_i}= \begin{pmatrix} \frac{1}{\sigma_i^2} 0 \\ 0 \frac{1}{\sigma_i^2} \end{pmatrix} $$.$$g_i(x)=-\frac{1}{2\sigma_i^2}(x_1^2+x_2^2)+\frac{1}{\sigma_i^2}(\mu_{i1}x_1+\mu_{i2}x_2)- \frac{1}{\sigma_i^2}(\mu_{i1}^2+\mu_{i2}^2)+\ln(P(\Omega_i))+C_i$$ Разделяющей поверхностью является коническое сечение.

Пример. Пусть$$P(\Omega_1)=P(\Omega_2), \; \mu_1=(0,0), \; \mu_2=(1,0), \; \Sigma_1= \begin{pmatrix} 0.1 0 \\ 0 0.15 \end{pmatrix}, \Sigma_2= \begin{pmatrix} 0.2 0 \\ 0 0.25 \end{pmatrix}.$$ Тогда$$\frac{1}{\Sigma_1}= \begin{pmatrix} 10 0 \\ 0 20/3 \end{pmatrix} ,\; \frac{1}{\Sigma_2}= \begin{pmatrix} 5 0 \\ 0 4 \end{pmatrix}.$$ Найдем поверхность решения.$$\begin{gathered} g_1(x)=-\frac12(x_1,x_2) \begin{pmatrix} 10 0 \\ 0 20/3 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} +\ln P(\Omega_1)-\ln(2\pi)+\frac12\ln\frac{200}{3}= \\ =\left(10x_1^2+\frac{20}{3}x_2^2\right)+\ln P-\ln(2\pi)+\frac12\ln\frac{200}{3} \\ g_2(x)=-\frac12(x_1-1,x_2) \begin{pmatrix} 5 0 \\ 0 4 \end{pmatrix} \begin{pmatrix} x_1-1 \\ x_2 \end{pmatrix} +\ln P(\Omega_2)-\ln(2\pi)+\frac12\ln 20 = \\ =-\frac12(5(x_1-1)^2+4x_2^2)+\ln P(\Omega_2)-\ln(2\pi)+\frac12\ln 20 \\ g_1(x)-g_2(x)=-\frac12 \left(10x_1^2+\frac{20}{3}x_2^2-5(x_1-1)^2-4x_2^2\right) +\frac12\left(\ln\frac{200}{3}-\ln 20\right)= \\ =-\frac12\left(5(x_1+1)^2+\frac83 x_2^2\right)+5+\frac12\ln\frac{10}{3} \end{gathered}$$

Т.к. $$g_1(x)-g_2(x)=0$$, то $$-\frac12\left(5(x_1+1)^2+\frac83 x_2^2\right)+5+\frac12\ln\frac{10}{3}=0$$$$\begin{gathered} 5(x_1+1)^2+\frac83 x_2^2=10+\ln\frac{10}{3} \\ \frac{(x_1+1)^2}{8/3}+\frac{x_2^2}{5}=\frac{3}{40}\left(10+\ln\frac{10}{3}\right) \\ \frac{(x_1+1)^2}{\left(2\sqrt{2/3}\right)^2}+\frac{x_2^2}{\left(\sqrt{5}\right)^2}=\frac{3}{40}\left(10+\ln\frac{10}{3}\right) \end{gathered}$$ – эллипс центром в точке $$(-1,0)$$.

Пример. Пусть$$P(\Omega_1)=P(\Omega_2), \; \mu_1=(0,0), \; \mu_2=(1,0), \; \Sigma_1= \begin{pmatrix} 0.1 0 \\ 0 0.15 \end{pmatrix}, \Sigma_2= \begin{pmatrix} 0.15 0 \\ 0 0.1 \end{pmatrix}.$$ Тогда$$\frac{1}{\Sigma_1}= \begin{pmatrix} 10 0 \\ 0 20/3 \end{pmatrix} ,\; \frac{1}{\Sigma_2}= \begin{pmatrix} 20/3 0 \\ 0 10 \end{pmatrix}.$$ .Найдем поверхность решения.

Из предыдущего примера:$$\begin{gathered} g_1(x)=-\frac12\left(5(x_1-1)^2+4x_2^2\right)+\ln P(\Omega_2)-\ln(2\pi)+\frac12\ln 20 \\ g_2(x)=-\frac12(x_1-1,x_2) \begin{pmatrix} 10/3 0 \\ 0 10 \end{pmatrix} \begin{pmatrix} x_1-1 \\ x_2 \end{pmatrix} +\ln P(\Omega_2)+\frac12\ln\frac{200}{3} \\ g_1(x)-g_2(x)=-\frac12\left(10x_1^2+\frac{20}{3}x_2^2-\frac{20}{3}(x_1-1)^2-10x_2^2\right)=\\ =-\frac12\left(\frac{10}{3}x_1^2-\frac{10}{3}x_2^2+\frac{40}{3}x_1-\frac{20}{3}\right)=\\ =-\frac12\cdot\frac{10}{3}(x_1^2-x_2^2+4x_1-2)=-\frac53\left((x_1+2)^2-x_2^2-6\right) \end{gathered}$$ Т.к. $$g_1(x)-g_2(x)=0$$, то $$-\frac53\left((x_1+2)^2-x_2^2-6\right)=0$$ $$(x_1+2)^2-x_2^2$$ =6 – гипербола с центром в точке $$(-2,0)$$

5.2. Линейная поверхность решения. Условие остается тем же:$$p(x|\Omega_i)=\frac{1}{(2\pi)^{1\!/2}\cdot|\Sigma_i|}\cdot \exp\left(-\frac12\frac{x-\mu_i}{\Sigma}(x-\mu_i)^T\right),\; i=1,2,\ldots,M.$$

В предыдущем пункте мы получили квадратичную форму:$$\begin{gathered} h_i(x)=\ln\left(p(x|\Omega_i)P(\Omega_i)\right)=\\ =\ln p(p(x|\Omega_i)+\ln P(\Omega_i)=\\ =-\frac12\frac{x-\mu_i}{\Sigma_i}(x-\mu_i)^T+\ln P(\Omega_1)+C_i,\text{ где } C_i=\ln\frac{1}{(2\pi)^{1\!/2}|\Sigma_i|^{1\!/2}} \end{gathered}.$$

Пусть $$\Sigma_i=\Sigma_j$$, тогда$$\begin{gathered} h_i(x)=-\frac12\left[\frac{x}{\Sigma_i}x^T-\frac{\mu_i}{\Sigma_i}x^T-\frac{x}{\Sigma_i}\mu_i^T+\frac{\mu_i}{\Sigma_i}\mu_i^T\right]+\ln P(\Omega_i)+C_i= \\ =-\frac12\left[\frac{x}{\Sigma_i}x^T-2\frac{\mu_i}{\Sigma_i}x^T+\frac{\mu_i}{\Sigma_i}\mu_i^T\right]+\ln P(\Omega_i)+C_i=\\ =-\frac12\left[K_i(x)-2W_i x^T+W_i\mu_i^T\right]+\ln P(\Sigma_i)+C_i=\\ =-\frac12 K_i(x)+L_i(x)+C_i, \text{ где } L_i(x)=W_i x^T+W_{i0};\; W_i=\frac{\mu_i}{\Sigma_i};\\ W_{i0}=\ln P(\sigma_i\mu_i^T) \end{gathered}$$

При $$\Sigma_i=\Sigma_j$$ можно сравнивать только $$L_i(x)$$ и $$L_j(x)$$. Таким образом, при $$\Sigma_i=\Sigma_j$$ мы получили линейную поверхность решения.

5.2.1. Линейная поверхность решения с диагональной матрицей ковариации. Рассмотрим случай, когда матрица диагональная с одинаковыми элементами: $$\Sigma= \begin{pmatrix} \sigma^2 0 \\ 0 \sigma^2 \end{pmatrix} $$. Тогда $$L_i(x)$$ имеет вид: $$L_i(x)=\frac{1}{\sigma^2}\mu_i^T x+W_{i0}$$ ;$$L_{ij}(x)=L_i(x)-L_j(x)=W^T(x-x_0)=0,$$ где$$W=\mu_i-\mu_j,\;x_0=\frac12(\mu_i+\mu_j)-\sigma^2\frac{\mu_i-\mu_j}{\|\mu_i-\mu_j\|^2}\ln\frac{P(\Omega_i)}{P(\Omega_j)}$$ В данном случае под нормой понимается евклидова норма. Поверхностью решения является гиперплоскость, проходящая через точку $$x_0$$.

Если $$P(\Omega_i)=P(\Omega_j)$$, то $$x_0$$ – это середина вектора $$\overline{\mu_i\mu_j}$$.

Т.к. $$L_{ij}(x)=0$$, то $$W^T(x-x_o)=(\mu_i-\mu_j)^T(x-x_0)=0$$. Следовательно, поверхность решения ортогональна $$\overline{\mu_i,\mu_j}$$.

Пример. Рассмотрим пример разделяющей поверхности решения для двухклассовой задачи с нормальным распределением. Поверхность решения лежит ближе к $$\mu_i$$, если $$P(\Omega_i)<P(\Omega_j)$$. Соответственно, поверхность решения лежит ближе к $$\mu_j$$, если $$P(\Omega_i)>P(\Omega_j)$$. Также, если $$\sigma^2$$ мало по отношению к $$\|\mu_i-\mu_j\|$$, то положение поверхности решения не очень чувствительно к изменению $$P(\Omega_i)$$ и $$P(\Omega_j)$$. Последнее справедливо, т.к. вектора лежат в малых окрестностях $$\mu_i$$ и $$\mu_j$$, поэтому изменение гиперплоскости их затрагивает не сильно. В центре изображен случай малого, а справа случай большого $$\sigma^2$$.

5.2.2. Линейная поверхность решения с недиагональной матрицей ковариации. В этом случае уравнение:$$L_{ij}(x)=L_i(x)-L_j(x)=W^T(x-x_0)=0$$ будет иметь несколько иные параметры:$$W=\frac{\mu_i-\mu_j}{\Sigma}\text{ и }x_0=\frac12(\mu_i+\mu_j)-\frac{\mu_i-\mu_j}{\|\mu_i-\mu_j\|_{\Sigma^{-1}}^2}$$ В данном случае под нормой понимается так называемая $$\Sigma^{-1}$$ норма $$x$$, которая имеет вид: $$\|x\|_{\Sigma^{-1}}=(x^T\Sigma^{-1}x)^{1\!/2}$$. Для такой нормы поверхность решения не ортогональна вектору $$\overline{\mu_i\mu_j}$$, Но она ортогональна его образу при преобразовании $$\Signa^{-1}(\mu_i-\mu_j)$$.

2.6. Классификаторы по минимуму расстояния

Будем рассматривать равновероятные классы с одинаковой матрицей ковариации. Тогда $$\Sigma_1=\Sigma_2=\ldots=\sigma_n=\Sigma$$ и выражение$$L_i(x)=-\frac12(x-\mu_i)\Sigma_i^{-1}(x-\mu_i)^T+\ln P(\Omega_i)+C_i$$ примет вид$$L_i(x)=-\frac12(x-\mu_i)\Sigma^{-1}(x-\mu_i)^T$$ (т.к. логарифм и константа сократятся).

6.1. Классификатор по минимуму расстояния с диагональной матрицей ковариации. Рассмотрим случай, когда матрица $$\Sigma$$ диагональная с одинаковыми элементами: $$\Sigma= \begin{pmatrix} \sigma^2 0 \\ 0 \sigma^2 \end{pmatrix} $$. Тогда максимизация $$L_i(x)$$ влечет минимизацию евклидового расстояния, определяемое выражением $$d_E=\|x-\mu_i\|$$. В данном случае будет считаться, что объект относится к данному классу, если он близок в смысле евклидового расстояния.

6.2. Классификатор по минимуму расстояния с недиагональной матрицей ковариации. В этом случае максимизация $$L_i(x)$$ влечет минимизацию расстояния Махалонобиса, определяемого выражением $$d_M=\left((x-\mu_i)^T\Sigma^{-1}(x-\mu_i)\right)^{1\!/2}$$.

Т.к. матрица ковариации является симметрической, ее можно представить в виде:$$\Sigma=\Phi\cdot\Lambda\cdot\Phi^T,$$ где $$\Phi^T=\Phi^{-1}$$, а $$\Lambda$$ – диагональная матрица с собственными значениями матрицы $$\Sigma$$ на диагонали. Матрица $$\Phi$$ имеет столбцы, соответствующие собственным векторам матрицы $$\Sigma$$:$$\Phi=(\nu_1,\nu_2,\ldots,\nu_l)$$ Таким образом, получаем линию равноудаленных точек $$x$$:$$(x-\mu_i^T)\cdot\Phi\cdot\Lambda^{-1}\Phi^T(x-\mu_i)=C^2$$ Пусть $$x'=\Phi^T x$$. Тогда координатами $$x'$$ являются $$\nu_k^T x,\; k=1,2,\ldots,l$$, т.е. проекции $$x$$ на собственные вектора. Другими словами, мы получили координаты в новой системе, у которой оси определяются собственными векторами $$\nu_k x,\; k=1,2,\ldots,l$$. Тогда последнее уравнение преобразуется в уравнение эллипсоида в новой системе координат:$$\frac{\left(x'_1-\mu'_{i1}\right)^2}{\lambda_1}+ \frac{\left(x'_2-\mu'_{i2}\right)^2}{\lambda_2}+ \ldots+ \frac{\left(x'_l-\mu'_{il}\right)^2}{\lambda_l}=C^2$$

При $$l=2$$ центр эллипса находится в точке $$\mu_i=(\mu_{i1},\mu_{i2})$$, а главные оси лежат по собственным векторам и имеют длины $$2\sqrt{\lambda_1}C$$ и $$2\sqrt{\lambda_1}C$$ соответственно.

Пример. Рассмотрим двумерный двухклассовый случай классификации двух нормально распределенных векторов с ковариационной матрицей $$\Sigma= \begin{pmatrix}1.1 0.3 \\ 0.3 1.9 \end{pmatrix}$$ и средними значениями $$\mu_1=(0,0)^T$$ и $$\mu_2=(3,3)^T$$.

Найдем $$\Sigma^{-1}$$:$$\begin{gathered} |\Sigma|-1.1\cdot 1.9-0.3^2=2.09-0.09=2 \\ \Sigma^{-1}=\frac12 \begin{pmatrix} 1.9 -0.3 \\ -0.3 1.1 \end{pmatrix} = \begin{pmatrix} 0.95 -0.15 \\ -0.15 0.55 \end{pmatrix} \end{gathered}$$

Классифицируем вектор $$1.2,2.2$$. Для этого посчитаем расстояние Махалонобиса:$$\begin{gathered} d_m^2(\mu_1,x)=(x-\mu_1)^T\Sigma^{-1}(x-\mu_1)= \\ =(1,2.2) \begin{pmatrix} 0.95 -0.15 \\ -0.15 0.55 \end{pmatrix} \begin{pmatrix} 1 \\ 2.2 \end{pmatrix} =\\ =(0.95-0.33)+(-0.15+1.21)\cdot 2.2=\\ =0.57+1\cdot 0.6 \cdot 2.2=0.57+2.332=2.952\\ d_m^2(\mu_2,x)=(x-\mu_2)^T\Sigma^{-1}(x-\mu_2)= \\ =(-1,-0.8) \begin{pmatrix} 0.95 -0.15 \\ -0.15 0.55 \end{pmatrix} \begin{pmatrix} -2 \\ -0.8 \end{pmatrix} =\\ =(-1.9+0.12)-(0.3-0.44)\cdot 0.8=\\ =3.56+0.112=3.672 \end{gathered}$$ Таким образом, хотя сама точка $$(1.0,2.2)$$ по евклидову расстоянию ближе к точке $$(0,0)$$, чем к точке $$(3,3)$$, но по расстоянию Махалонобиса она ближе к $$(3,3)$$.

Теперь вычислим главные оси эллипса с центром в точке $$(0,0)$$. Для этого найдем собственные значения:$$\begin{gathered} \begin{vmatrix} 1.1-\lambda 0.3 \\ 0.3 1.9-\lambda \end{vmatrix} =2.09-3\lambda+\lambda^2-0.09=\lambda^2-3\lambda+2=0 \\ \lambda_1=1,\;\lambda_2=2. \end{gathered}$$

Тогда собственные вектора (и направление главных осей эллипса) будут иметь вид:$$V_1=\left(\frac{3}{\sqrt{10}},\frac{-1}{\sqrt{10}}\right)^T,\;V_2=\left(\frac{1}{\sqrt{10}},\frac{3}{\sqrt{10}}\right).$$