ML: Байесовские методы


Введение

В задачах машинного обучения и алгоритмах искусственного интеллекта важную роль играет формула Байеса. Этот документ является продолжением введения в теорию вероятности и посвящён различным аспектам применения формулы Байеса.


Формула Байеса

Пусть есть $n$ не пересекающихся (несовместных) гипотез $\{H_1,...,H_n\}$, $H_i\,\&\,H_j=\emptyset$. При этом предполагается, что одна из них истинна: $$ \sum_i P(H_i) = 1 $$ В частном случае может быть $n=2$ и гипотезы от том, что некоторое утверждение $H$ либо истинно, либо ложно - $H_i:\,\{h,\bar{h}\}$. Например:

$H_1: $ "человек болен данной болезнью",    $H_2: $ "человек не болен этой болезнью".

Будем считать, что известны вероятности $P(H_i)$ всех гипотез. Их можно получить из данных статистики (выше - это доля больных в популяции - Objectivist interpretation) или это может быть степень "убеждённости" или "веры" в истинности гипотезы тем, кто принимает некоторое решение (например, интеллектуальным агентом - Subjectivist interpretation). Эти вероятности называют априорными ("до опытные", лат. "a priori").

Когда наступает некоторое событие $E$ (несущее новую информацию), оно может изменить вероятности гипотез на апостериорные вероятности $P(H_i|E)$ (полученные из опыта, лат. "a posteriori"). Эти вероятности можно вычислить при помощи формулы Байеса: $$ P(H_i|E) = \frac{P(H_i\,\&\,E)}{P(E)} = \frac{P(E|H_i)}{P(E)}\,P(H_i), $$ где сначала записано определение условной вероятности $P(H_i|E)$, а затем учтено определение условной вероятности $P(E|H_i)$. Вероятность события $P(E)$ для полных (покрывающих все случаи) и несовместных (не пересекающихся) гипотез вычисляется следующим образом (формула полной вероятности): $$ P(E) = \sum_j P(E|H_j)\,P(H_j) = \sum_j P(E\,\&\,H_j) $$ В результате такой нормировки сумма $P(H_i|E)$ по всем $H_i$ равна единице (истинна одна из гипотез).

По формуле Байеса апостериорная вероятность $P(H_i|E)$ пропорциональна априорной вероятность $P(H_i)$, умноженной на "функцию правдоподобия" (likelihood) $P(E|H_i)$ события $E$ для гипотезы $H_i$. В частности, если событие не зависит от гипотезы $P(E|H_i)=P(E)$, то $P(H_i|E)=P(H_i)$ (априорная вероятность не меняется).

Часто накопить статистику для вычисления вероятностей $P(E|H_i)$ проще, чем для $P(H_i|E)$. Например, в случае $H:$ "человек болен болезнью $H$", можно взять всех больных (их может быть не так и много) и вычислить по ним вероятность $P(E|H)$ для симптома $E$. В то-же время симптом $E$ может возникать по множеству самых разнообразных причин, не связанных с болезнью $H$.

К тому же вероятности $P(E|H)$ оказываются более стабильными, чем $P(H|E)$. Например, пусть стало известно, что началась эпидемия. В результате вероятность $P(H)$ вырастает, тогда как $P(E|H)$ остаётся неизменной. По формуле Байеса $P(H|E)$, конечно, также увеличивается.


Пример: Тестирование болезни

+ - Tot
б 9 1 10
з 90 9900 9990
Tot 99 9901 10000
Пусть у человека провели тестирование по выявлению некоторой болезни. Известно, что это тестирование в $90\%$ случаев даёт позитивный результат если человек действительно болен. Если же человек здоров, тест ошибочно выдаёт позитивный результат в 0.9% случаев. Пусть также известно, что на 10'000 человек этой болезнью болеет 10 человек. Обозначим через $H_1:\text{"б"}$ гипотезу от том, что человек болен, $H_2:\text{"з"}$ - человек здоров; событие $E_1:\text{"+"}$ - тест положителен, $E_2:\text{"-"}$ - тест отрицателен: $$ P(\text{+}|\text{б}) = 0.9,~~~~~~~P(\text{+}|\text{з}) = 0.009,~~~~~~P(\text{б}) = 0.001. $$ Справа в таблице приведена статистика (в людях) на основании которой получены оценки для этих вероятностей. Вероятности $P(E|H)$ вычисляются по строкам, а $P(H|E)$ - по столбцам. Так, $P(+|б)=9/10$, а $P(з|+)=90/99$,

Вероятность обнаружить позитивный тест (независимо от состояния человека) равна: $$ P(\text{+}) = P(\text{+}|б)\,P(\text{б}) ~+~ P(\text{+}|з)\,P(\text{з}) = 0.9*0.001 + 0.009*(1-0.001)= 0.0099 $$ Естественно это же значение можно получить и из таблицы (tot в первой колонке 99/10000).

По формуле Байеса апостериорная вероятность быть больным равна: $$ P(\text{б}|\text{+}) = \frac{P(\text{+}|\text{б})}{P(\text{+})}\,P(\text{б}) = \frac{0.9}{0.00989}\,0.001 = 0.091. $$ Из таблицы этот результат получается по первой колонке: 9/99.

Таким образом, хотя тест достаточно точно работает на здоровых людях (ошибается $9$ раз на $1000$ тестов), вероятность оказаться больным при однократном положительном тесте равна всего $9\%$. Этот, на первый взгляд, странный результат связан с тем что, хотя ошибок у теста мало, доля больных среди всей популяуции ещё меньше. Стоит внимательно проанализировать таблицу приведенную выше (если тест провести у всей популяции позитивный результат будет у 99 человек, хотя среди них только 9 больных).


Последовательность наблюдений

При принятии решений формулу Байеса применяют для пересчёта вероятностей по мере поступления новой информации. Пусть в примере выше проведено два независимых теста (последовательно или одновременно, но в различных лабораториях). Какими станут апостериорные вероятности в этом случае?

Пусть $E_1$, $E_2$ - два условно независимых события ("++" или "+-"). Вероятность истинности гипотезы $H_i$, после возникновения событий, по формуле Байеса равна (считаем $\{E_1,\,E_2\}$ одним событием): $$ P(H_i|E_1,E_2) = \frac{P(E_1,E_2 | H_i)}{P(E_1,E_2)}\,P(H_i) = \frac{P(E_1 | H_i)\,P(E_2 | H_i)}{P(E_1,E_2)}\,P(H_i). $$ Во втором равенстве учтено, что события $E_1$ и $E_2$ независимы. Вероятность в знаменателе, как и раньше, находится из условия нормировки $P(H_i|E_1,E_2)$: $$ P(E_1,E_2) ~=~ \sum_j P(E_1 | H_j)\,P(E_2 | H_j)\,P(H_j). $$

Формулу для апостериорной вероятности можно переписать следующим образом:: $$ P(H_i|E_1,E_2) = \frac{P(E_2 | H_i)}{P(E_2|E_1)}\,P(H_i|E_1),~~~~~~~~~~~~~~ P(H_i|E_1) = \frac{P(E_1 | H_i)}{P(E_1)}\,P(H_i). $$ Таким образом событие $E_1$ превращает априорную вероятность $P(H_1)$ в $P(H_1|E)$, после чего она (при помощи той-же формулы Байеса) превращается в ещё более уточнённую вероятность гипотезы $P(H_i|E_1,E_2)$ и т.д. При этом последовательность независимых событий не играет роли.

Обратим внимание, что, хотя события условно независимы, но при этом $P(E_1,E_2) \neq P(E_1)\,P(E_2)$, Почему так происходит?

Ответ Проще понять это на примере тестирования болезни. Соотношение $P(E_1,E_2) = P(E_1)\,P(E_2)$ было бы верным, если бы результаты тестов $E_1$, $E_2$ были бы получены у двух случайно выбранных людей. В нашем случае тест проводится с одним и тем же человеком который или болен или здоров. Мы не знаем какая гипотеза верна, но в любом случае выполняется одна из них. Поэтому $P(E_1,E_2) ~=~ P(E_1,E_2 | б)\,P(б)+P(E_1,E_2 | з)\,P(з)$.


Пример вычислений на numpy

Приведём пример вычислений с тестированием болезни на Python при помощи библиотеки NumPy:
import numpy as np
np.set_printoptions(precision=5, suppress=True)
Совместные вероятности будем начинать с префикса P_, а условные с C_.
Нумерация событий: E=[+,-] и гипотез: и H=[б,з]. Исходные данные имеют вид:

NH, NE = 2, 2                          # число гипотез и событий

P_H  = np.array([0.001, 1-0.001])      # [P(б), P(з)]

C_EH = np.array([[  0.9,   0.009],     # P(+|б) P(+|з)
                 [1-0.9, 1-0.009] ])   # P(-|б) P(-|з)
Результаты однократного теста:
C_HE = ( C_EH*P_H.reshape(1,NH) ).T    # [[P(б|+), P(б|-)],      [[0.09099 0.0001]
C_HE /= C_HE.sum(0)                    #  [P(з|+), P(з|-)]]   =   [0.90901 0.9999]]
Результаты двух тестов:
C_HEE = (C_EH.reshape(NE,1,NH)*C_EH.reshape(1,NE,NH)*P_H.reshape(1,1,NH)).transpose(2,0,1)
C_HEE /= C_HEE.sum(0)

# P(б|++)  P(б|+-)  [[[0.90917 0.01   ]
# P(б|-+)  P(б|--)    [0.01    0.00001]]
#
# P(з|++)  P(з|+-)   [[0.09083 0.99   ]
# P(з|-+)  P(з|--)    [0.99    0.99999]]]

Таким образом, вероятность оказаться больным при двух положительных тестах $P(\text{б|++})=0.909$ существенно выше, чем при одном: $P(\text{б|+})=0.091$


Задача классификации

В задаче классификации с непересекающимися классами объект с признаками $\mathbf{x}=\{x_1,...,x_n\}$ необходимо отнести к одному из $C$ классов. Пусть $P(c|\mathbf{x})$ - условная вероятность того, что объект с признаками $\mathbf{x}$ принадлежит $c$-тому классу: $c\in [0...C-1]$.

В этом случае формула Байеса имеет следующий вид: $$ P(c|\mathbf{x}) ~=~ \frac{p(c,\mathbf{x})}{p(\mathbf{x})} = \frac{p(\mathbf{x}|c)}{p(\mathbf{x})}\,P(c), ~~~~~~~~~~~~~ p(\mathbf{x}) ~=~ \sum_\alpha p(\mathbf{x}|\alpha)\,P(\alpha), $$ где $P(c)$ - вероятности принадлежности случайно выбранного объекта к классу $c$ (независимо от значений признаков), а $p(\mathbf{x}|c) = p(c,\mathbf{x})/P(c)$ - распределение плотности вероятностей значений признаков $\mathbf{x}$ для объектов из класса $c$. Нормировка в знаменателе $p(\mathbf{x})$ - это распределение объектов в пространстве признаков. Если всего объектов $N$, то $p(\mathbf{x})\cdot N$ - это плотность числа объектов единице объёма.

Таким образом, чтобы получить вероятность $P(c|\mathbf{x})$, необходимо знать вероятности классов $P(c)$ и распределения $p(\mathbf{x}|c)$. Если обучающая выборка не смещена (классы в ней представлены с такой же частотой, что и в тестовой), то $P(c)$ получить несложно. А вот значения $p(\mathbf{x}|c)$ в многомерном пространстве признаков часто найти непросто. Если объекты класса образуют компактные "кластеры", то $p(\mathbf{x}|c)$ можно аппроксимировать гладкими функциями (например, многомерными распределениями Гаусса). Параметры этих функций получают по множеству обучающих примеров. Другой подход - это поиск ближайших соседей к точке $\mathbf{x}$ в каждом классе и построение по ним аппроксимирующих поверхностей $p(\mathbf{x}|c)$.

Иногда неплохие результаты даёт наивный Байес, в котором предполагается условная независимость признаков: $$ p(\mathbf{x}|c) ~=~p(x_1|c)\cdot...\cdot p(x_n|c). $$ Вероятности $p(x_i|c)$ особенно легко вычисляются для категориальных или бинарных признаков. В этом случае такой классификатор может оказаться очень эффективным. Если признаки непрерывные, то для $p(x_i|c)$ по обучающим данным можно строить гистограммы или вычислять статистики (например, в предположении, что $p(x_i|c)$ имеет нормальное распределение).


Мир Вампуса

Рассмотрим неплохой пример принятия решения в модельном мире Вампуса. Этот мир состоит из клеток по которым перемещается интеллектуальный агент. Пусть в любой клетке, независимым образом, с вероятностью $P(h)=0.2$ может находиться яма (hole). В этом случае в каждой из четырёх соседних с ямой клетках обязательно будет чувствоваться ветерок (wind). Предположим, что агент исследовал три угловые клетки своего мира. В них нет ям, но в двух есть ветер (тильда на рисунке справа). Необходимо определить вероятности ям в клетках (серого цвета), прилегающих к исследованной области.

Обозначим известную информацию о ямах и ветре в виде двух множеств: $\mathbb{H}=\{\bar{h}_{11},\,\bar{h}_{12},\,\bar{h}_{21}\}$ (нет ям) и $\mathbb{W}=\{\bar{w}_{11},\,w_{12},\,w_{21}\}$ (в ячейке $[1,1]$ ветра нет, а в $[1,2]$ и $[2,1]$ - есть). Мы хотим вычислить, например, вероятность ямы в верхней ячейке $H_{3,1}=\{h_{3,1},\,\bar{h}_{3,1}\}$, где значение $h_{3,1}$ случайной величины $H_{3,1}$ означает, что яма есть, а значение $\bar{h}_{31}$ - что её нет: $$ P(H_{31}|\mathbb{H}, \mathbb{W}) ~\sim~ P(H_{31},\mathbb{H},\mathbb{W}) = \sum_{H_{22},H_{13}} P(H_{31}, H_{22},H_{13}, \mathbb{H},\mathbb{W}). $$ Выше знак "$\sim$" означает, что мы опускаем множитель не зависящий от искомой переменной $H_{1,3}$, равный, по определению условной вероятности, $P(\mathbb{H}, \mathbb{W})$. Затем мы расширяем совместную вероятность на соседние клетки. Сумма состоит из четырёх слагаемых для всех возможных значений $H_{2,2}=\{h_{2,2},\,\bar{h}_{2,2}\}$ и $H_{1,3}=\{h_{1,3},\,\bar{h}_{1,3}\}$. Воспользовавшись снова определением условной вероятности, имеем: $$ P(H_{31}|\mathbb{H}, \mathbb{W}) ~\sim~ \sum_{H_{22},H_{13}} P(\mathbb{W}|H_{31}, H_{22},H_{13}, \mathbb{H})\, P(H_{31})P(H_{22})P(H_{13}). $$ Совместная вероятность была расширена, так как вероятность наличия ветра (доступная агенту информация $\mathbb{W}$) зависит от факта наличия или отсутствия ям во всех ячейках, приведенных на рисунке. Теперь можно провести вычисления, расписав явно суммы: $$ \begin{array}{lcl} P( h_{31}|\mathbb{H}, \mathbb{W}) &\sim& P(\mathbb{W}|h_{31}, h_{22},h_{13}, \mathbb{H})\, P(h_{31})P(h_{22})P(h_{13})+P(\mathbb{W}|h_{31}, \bar{h}_{22},h_{13}, \mathbb{H})\, P(h_{31})P(\bar{h}_{22})P(h_{13})\\ & +& P(\mathbb{W}|h_{31}, h_{22},\bar{h}_{13}, \mathbb{H})\, P(h_{31})P(h_{22})P(\bar{h}_{13})+P(\mathbb{W}|h_{31}, \bar{h}_{22},\bar{h}_{13}, \mathbb{H})\, P(h_{31})P(\bar{h}_{22})P(\bar{h}_{13}), \\ P(\bar{h}_{31}|\mathbb{H}, \mathbb{W}) &\sim& P(\mathbb{W}|\bar{h}_{31}, h_{22},h_{13}, \mathbb{H})\, P(\bar{h}_{31})P(h_{22})P(h_{13})+P(\mathbb{W}|\bar{h}_{31}, \bar{h}_{22},h_{13}, \mathbb{H})\, P(\bar{h}_{31})P(\bar{h}_{22})P(h_{13})\\ & +& P(\mathbb{W}|\bar{h}_{31}, h_{22},\bar{h}_{13}, \mathbb{H})\, P(\bar{h}_{31})P(h_{22})P(\bar{h}_{13})+P(\mathbb{W}|\bar{h}_{31}, \bar{h}_{22},\bar{h}_{13}, \mathbb{H})\, P(\bar{h}_{31})P(\bar{h}_{22})P(\bar{h}_{13}). \\ \end{array} $$ Учтём что $P(h_{ij})=0.2$ и $P(\bar{h}_{ij})=0.8$. Вероятность $P(\mathbb{W}|h_{31}, h_{22},h_{13}, \mathbb{H})=1$ так как ямы есть везде, что гарантированно приводит к ветру, а $P(\mathbb{W}|h_{31}, \bar{h}_{22},\bar{h}_{13}, \mathbb{H})=0$ так как отсутствие ям в ячейках $[2,2]$ и $[1,3]$ не согласуется с наличием ветра в $[1,2]$. Аналогично в остальных случаях. В результате: $$ \begin{array}{lcl} P( h_{31}|\mathbb{H}, \mathbb{W}) &\sim& 0.2^3 + 0.2^2\,0.8 + 0.2^2\,0.8, \\ P(\bar{h}_{31}|\mathbb{H}, \mathbb{W}) &\sim& 0.2^2\,0.8 + 0.2\,0.8^2. \end{array} $$ Этот результат можно представит в виде вектора, с двумя компонентами: $$ P(H_{31}|\mathbb{H}, \mathbb{W})~\sim \bigr\{0.2^3 + 2\cdot 0.2^2\cdot 0.8,~~~ 0.2^2\cdot 0.8 + 0.2\cdot 0.8^2\bigr \} \sim \bigr\{0.2 + 2\cdot 0.8,~~~ 0.8 + 4\cdot 0.8\bigr \}. $$ Теперь его необходимо отнормировать на единицу (восстановив опущенные множители): $$ P(H_{31}|\mathbb{H}, \mathbb{W}) = \bigr\{1.8,~ 4\bigr \}/(1.8+4) = \bigr\{0.31,~ 0.69 \}. $$ Таким образом, вероятность обнаружить яму в ячейке $[3,1]$ равна $0.31$. Стоит аналогично проверить, что вероятность ямы в ячейке $[2,2]$ равна $0.86$. Следовательно, агенту стоит (при необходимости) двигаться, либо в ячейку $[3,1]$, либо в ячейку $[1,3]$.


Угадать задуманное

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

Предположим, человек задумал объект $x$. Система задаёт вопрос $Q$, на который получает ответ $Y$ (Yes=да) или $N$ (No=нет): "Ваш персонаж женщина?", "Ваш персонаж из реальной жизни?", "Ваш персонаж дружит с медведем?" и т.д. При построении подобной системы необходимо учитывать, что человек, отвечая может ошибаться. Поэтому в общем случае от нуля отличны обе условные вероятности: $P(Q,Y|x)$ и $P(Q,N|x)$ - получить на вопрос $Q$ ответ $Y$ или $N$, если задуман объект $x$.

Y=Yes $Q_1$ $Q_2$ ... $Q_m$ $P(x)$
$x_1$ 9 1 ... 2 0.001
$x_2$ 10 0 ... 25 0.008
... ... ... ... ... ...
$x_n$ 0 890 ... 100 0.02
Пусть есть фиксированный набор $n$ объектов и $m$ вопросов. В процессе работы система должна обучаться, запоминая ответы людей. В результате возникает таблица подобная приведенной справа (число ответов $Y$ на вопрос $Q$, когда задуман $x$) и аналогичная таблица для ответов $N$. На основании этих данных для пар $(x,Q)$ и ответов $A:\{Y,N\}$ можно получить вероятности $P(Q,A|x)$ - по строкам таблиц и $P(x|Q,A)$ - по столбцам таблиц. Кроме этого, таблицы дают вероятности $P(x)$ задумываемых людьми персонажей.

Обозначим чере $I_k$ последовательность $k$ вопросов-ответов, полученных системой: $I_k=\{Q_1,A_1,...,Q_k,A_k\}$.
На основании этой информации формируются условные вероятности $P(x|I_k)$ для каждого $x$.
При помощи формулы Байеса можно записать: $$ P(x|I_k) = \frac{P(I_k|x)}{P(I_k)}\,P(x) = \frac{P(Q_1,A_1|x)...P(Q_k,A_k|x)}{P(I_k)}\,P(x), $$ где во втором равенстве сделано предположение (сравнительно грубое) о "не влиянии" пар вопросов-ответов друг на друга. Нормировочная вероятность $P(I_k)$, как обычно, находится из условия нормировки (сумма по всем $x$), в предположении, что человек задумал известный системе объект. Так как задача состоит в поиске $x$ с максимальным значением $P(x|I_k)$, знаменатель можно опустить: $$ x= \text{arg}\max_x ~P(Q_1,A_1|x)...P(Q_k,A_k|x)\,P(x). $$

Выбор очередного вопроса $Q$ после серии вопросов-ответов $I_{k-1}$ производится аналогично алгоритму ID3 построения деревьев решений . Единственное отличие состоит в том, что "признак" $Q$ может иметь два значения $A:\,\{Y,N\}$. Оптимальным является вопрос, который делает распределение вероятностей $P=P(x|I_{k-1},\, Q,A)$ максимально неравномерным (повышает вероятности отдельных объектов). Энтропия $H[P]$ такого распределения должна быть минимальной (усредняем энтропии для "да" и "нет" ответов): $$ Q = \text{arg}\min_{Q}~ H[ P(x|I_{k-1},\, Q,Y)]\,P(Q,Y) + H[ P(x|I_{k-1},\, Q,N)]\,P(Q,N), $$ где вероятности $P(Q,A)$ находятся с учётом известной к этому моменту вероятности объекта $x$: $$ P(Q,A) = \sum_{x} P(Q,A|x)\,P(x|I_{k-1}). $$


Определение частей речи

Байесовскую формулу можно использовать для присваивания каждому слову $w_i$ предложения части речи $t_i$: существительное (N), прилагательное (A), глагол (V) и т.д. (Part-of-Speech Tagging). Пусть $t_i$ - один из маркеров (N, A, V...). Тогда, если для последовательности слов $w_1...w_n$ известна условная вероятность $P(w_1,...,w_n\Rightarrow t_1,...,t_n)$, то задача решается поиском макимума этой вероятности: $$ t_1,...,t_n = \arg\max_{t_1,...,t_n}\,P(w_1...w_n\Rightarrow t_1...t_n). $$ Для оценки вероятности снова можно использовать формулу Байеса: $$ P(w_1...w_n\Rightarrow t_1...t_n) ~=~ \frac{P(w_1...w_n,t_1...t_n)}{P(w_1...w_n)} ~=~ \frac{P( t_1...t_n \Rightarrow w_1...w_n)\, P(t_1...t_n)}{P(w_1...w_n)} $$ Для максимизции по $t_i$ достаточно найти только числитель. Вероятность $P(t_1...t_n)$ характеризует степень правдоподобности данной последовательности частей речи (например N V более вероятно, чем A V). В первом приближении для её оценки, можно использовать биграммы. Для этого в цепном правиле делается марковское упрощение: $P(t_1...t_{k-1}\Rightarrow t_k)=P(t_{k-1}\Rightarrow t_k)$: $$ P( t_1...t_n) = P(t_1)\cdot P(t_1\Rightarrow t_2)\cdot... \cdot P(t_{n-1}\Rightarrow t_n). $$ Вторая вероятность в простейшем случае оценивается при помощи таких биграмм: $$ P( t_1...t_n \Rightarrow w_1...w_n) = P(t_1\Rightarrow w_1)\cdot...\cdot P(t_n\Rightarrow w_n). $$ При этом делается предположение (достаточно грубое) о независимости слов в последовательности. Заметим, что по той же теореме Байеса $P(t\Rightarrow w)=P(w\Rightarrow t)\,P(w)/P(t)$.