ML: Вероятностные методы


Введение

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


Совместная и условная вероятности

Пусть произведено $N$ наблюдений над некоторыми событиями и при этом событие $\mathrm{A}$ наступило $N(\mathrm{A})$ раз.
Эмпирической вероятностью $P(\mathrm{A})$ события $\mathrm{A}$ называют отношение $N(\mathrm{A})/N$: $$ P(\mathrm{A}) = \frac{N(\mathrm{A})}{N},~~~~~~~~~~~~~~~~~~~~~~~P(\mathrm{A},\mathrm{B}) = \frac{N(\mathrm{A},\mathrm{B})}{N}. $$ Если в каждом наблюдении могут произойти два события $\mathrm{A}$, $\mathrm{B}$ и они происходят $N(\mathrm{A},\mathrm{B})$ раз в $N$ наблюдениях, то отношение $N(\mathrm{A},\mathrm{B})/N$ называют совместной вероятностью $P(\mathrm{A},\mathrm{B})$ наступления, и $\mathrm{A}$, и $\mathrm{B}$.

Пусть теперь нас интересует вероятность наступления события $\mathrm{A}$, если в этом жеД наблюдении стало известно, что произошло событие $\mathrm{B}$. Для этого необходимо подсчитать число $N(\mathrm{A}, \mathrm{B})$ случаев среди $N(\mathrm{B})$ наблюдений, когда произошло $\mathrm{B}$. Их отношение называется условной вероятностью и далее будет обозначаться двумя эквивалентными способами: $$ P(\mathrm{B}\Rightarrow \mathrm{A}) \equiv P(\mathrm{A}|\mathrm{B}) ~=~ \frac{N(\mathrm{A},\mathrm{B})}{N(\mathrm{B})} ~=~ \frac{P(\mathrm{A},\mathrm{B})}{P(\mathrm{B})}. $$ События считаются независимыми, если условная вероятность $\mathrm{A}$ не зависит от факта наступления события $\mathrm{B}$: $P(\mathrm{A}|\mathrm{B})=P(\mathrm{A})$. В этом случае $P(\mathrm{A},\mathrm{B})=P(\mathrm{A})\cdot P(\mathrm{B})$.


☝ Совместность не означает одновременности. Например, пусть на стол $N$ раз бросают два игральных кубика разного цвета и событие $\mathrm{A}$ означает выпадение 6-ки на одном кубике и 1-цы на втором. Вероятности $P(\mathrm{A})=P(\mathrm{B})=1/6$ и $P(\mathrm{A},\mathrm{B})=1/36$ не зависят от того, кидают кубики одновременно или по-очереди (считая при этом одним наблюдением нахождение на столе обоих кубиков после броска).

Как и для совместных вероятностей, условная вероятность не подразумевает, что событие $\mathrm{B}$ происходит раньше события $\mathrm{A}$. Так, в примере с кубиками событием $\mathrm{B}$ может быть выпадение 1-цы на втром бросаемом кубике, а событие $\mathrm{A}$ - выпадение 6-ки на первом кубике. В данном случае события независимы, поэтому $P(\mathrm{B} \Rightarrow \mathrm{A})=P(\mathrm{A})$.


☝ Слова "эмпирическая вероятность" означает, что отношение $N(\mathrm{A})/N$ является лишь оценкой "истинной" вероятности $P(\mathrm{A})$ события $\mathrm{A}$. Эта оценка тем лучше, чем больше $N$. Существует простое соотношение, позволяющее понять степень надёжности полученного значения эмпирической вероятности. Пусть "истинная" вероятность (по "бесконечному" числу наблюдений) равна $p_\text{A}$. Тогда дисперсия эмпирической вероятности равна $p_\text{A}\,(1-p_\text{A})/N$ и можно написать: $$ P(\mathrm{A}) ~=~ \frac{N(\mathrm{A})}{N} ~\pm~ \sqrt{\frac{p_\text{A}\,(1-p_\text{A})}{N}}. $$ Таким образом, ошибка в измерении вероятности убывает достаточно медленно (как $1/\sqrt{N}$) и максимальна для событий с $p_\text{A}\sim 0.5$. Ошибку условной вероятности можно оценить взяв дифференциал её определения.


Вероятности букв в тексте

В качестве примера вычисления вероятностей рассмотрим словарь $\mathcal{V}=\{w^{(1)},...,w^{(\text{V})}\}$, состоящий из $\text{V}=|\mathcal{V}|$ слов (или символов). Последовательность $\mathcal{T}= w_1\,w_2....\,w_N$, где $w_i\in \mathcal{V}$ образует текст длиной $N=\mathrm{len}(\mathcal{T})$. Далее, для простоты будем говорить о буквах.

Вероятность встретить в тексте конкретную букву зависит от её предыстории (предшествующих букв). Например, после '$\mathbf{э}$' вероятность появления '$\mathbf{т}$' в 14 раз выше, чем безусловная вероятность появления буквы '$\mathbf{т}$': $P(\mathbf{т})=0.051$. Наоборот, некоторые сочетания букв сложно произносимы. Так, после '$\mathbf{б}$' маловероятно появление '$\mathbf{п}$'.

Чтобы вычислить совместную вероятность $P(\mathbf{эт})$ встретить в тексте строку 'эт', необходимо подсчитать число таких строк $N(\mathbf{эт})$ и разделить на число всех подстрок длиной два: $N(\mathbf{**})$, где звёздочка означает любой символ.

Для вычисления условной вероятности $P(\mathbf{э} \Rightarrow \mathbf{т})$, равной вероятности появления буквы 'т' если перед ней в тексте стоит 'э', необходимо отобрать все подстроки, удовлетворяющие маске '$\mathbf{э*}$' ('$\mathbf{э}$', затем любой символ '$\mathbf{*}$'), и выяснить, сколько среди них 'эт':

$$ P(\mathbf{эт})= \frac{N(\mathbf{эт})}{N(\mathbf{**})} = 0.002,~~~~~~~~~~~~~~~~~~~~ P(\mathbf{э}\Rightarrow \mathbf{т}) = \frac{N(\mathbf{эт})}{N(\mathbf{э*})} = 0.83. $$

Заметим, что сама по себе строка 'эт' имеет малую вероятность 0.002, но если мы уже встретили букву 'э', то после неё с вероятностью 0.83 будет идти буква 'т'.

Количество, как совместных, так и условных вероятностей двух букв русского алфавита из $33$ букв (без 'ё', но включая пробел) равно $33^2=1089$. Для текста из $N$ символов $N(\mathbf{**})=N-1$, а $N(\mathbf{э*})\approx N(\mathbf{э})=P(\mathbf{э})\cdot N$, поэтому $$ P(\mathbf{эт}) = P(\mathbf{э})\cdot P(\mathbf{э}\Rightarrow \mathbf{т}). $$

Это же соотношение следует из определения условной вероятности $P(\mathbf{э}\Rightarrow \mathbf{т})= P(\mathbf{эт})/ P(\mathbf{э})$. Так как в языке терминальных букв нет (после которых нет других букв), то сумма $P(w_1\Rightarrow w_2)$ по всем $w_2$ из словаря должна равняться единице (после $w_1$ будет хоть какая-то буква). Это же справедливо и в общем случае. Если $P(w_1,...,w_{n-1})$ отлично от нуля, то сумма $P(w_1,...,w_{n-1}\Rightarrow w_n)$ по всем словам $w_n$ словаря $\mathcal{V}$ равно 1.

Марковские процессы

Аналогично предыдущему разделу, для последовательности $w_1,...,w_n$ имеем: $$ P(w_1,...,w_n) = P(w_1,...,w_{n-1})\,P(w_1,...,w_{n-1} \Rightarrow w_n). $$ Применяя это определение рекурсивно, несложно получить т.н. цепное правило (сhain rule) для вычисления совместной вероятности через условные: $$ P(w_1,...,w_n) ~=~ P(w_1)\cdot P(w_1\Rightarrow w_2)\cdot...\cdot P(w_1...w_{n-1} \Rightarrow w_n) ~=~ \prod^N_{k=1} P(w_1...w_{k-1} \Rightarrow w_k). $$ Таким образом, сначала с вероятностью $P(w_1)$ появляется буква $w_1$. Если это произошло, с вероятностью $P(w_1\Rightarrow w_2)$ появится $w_2$ и т.д.

В марковских случайных процессах длинная история "забывается" и $$ P(w_1,...,w_{n-1} \Rightarrow w_n) = P(w_{n-k},...,w_{n-1} \Rightarrow w_n). $$ Если учловные вероятности к тому же не зависят от $k$ (не меняются вдоль последовательности), то такой процесс называется стационарным.

А.А. Марков рассмотривал простейший случай $k=1$, когда совместную вероятность $P(w_1,...,w_n)$ можно выразить через вероятности $P(w_{k-1}\Rightarrow w_k)$. Приведём пример чуть более сложного случая с историей длины $2$: $$ P(w_1,...,w_n) = P(w_1)\cdot P(w_1\Rightarrow w_2) \cdot P(w_1 w_2\Rightarrow w_3) \cdot P(w_2w_3\Rightarrow w_4)\cdot...\cdot P(w_{n-1}w_{n-2}\Rightarrow w_n). $$

Естественно, что свойства "короткой памяти" и "стационарности" являются приближениями и их справедливость проверяется качеством работы моделей, которые используют эти приближения.


Энтропия

Пусть $P=\{p_1,...,p_n\}$ - набор $n$ ненулевых вероятностей. Это могут быть вероятности появления символов в тексте или вероятности несовместных классов в модели классификации: $$ p_\alpha > 0,~~~~~~~~~~~\sum^n_{\alpha=1} p_\alpha = 1. $$ Энтропия $H$ является мерой равномерности вероятностей (чем больше $H$, тем ближе друг к другу $p_\alpha$): $$ H(P) = - \sum^n_{\alpha=1} p_\alpha\,\log p_\alpha. $$

В качестве логарифма, обычно выбирают, или натуральный логарифм $\ln$, или логарифм по основанию два: $\log_2$. Энтропия всегда положительна. Если все вероятности равны: $p_\alpha=1/n$, то энтропия достигает своего максимального значения $H_\max = \log n$. Если одна вероятность стремиться к 1, а остальные к 0, то энтропия стремиться к нулю. Например, для трёх вероятностей (c $\log=\ln$ и $\log_2$):

                       ln    log2
H(0.33, 0.33, 0.33) = 1.10 | 1.58 |   
H(0.25, 0.25, 0.50) = 1.04 | 1.50 |     n:          2      3    10   100
H(0.10, 0.20, 0.70) = 0.80 | 1.16 |     ln   n:  0.69   1.10  2.30  4.61  <-  H_max ln
H(0.10, 0.10, 0.80) = 0.64 | 0.92 |     log2 n:  1.00   1.58  3.32  6.64  <-  H_max log2
H(0.01, 0.01, 0.98) = 0.11 | 0.16 |   
Напомним, что $\ln p = \log_2 p \cdot \ln 2$. Поэтому энтропия с натуральным логарифмом всегда равна $0.69$ от энтропии с двоичным логарифмом.

Энтропия также характеризует степень "непредсказуемости" событий, вероятности которых равны $p_\alpha$. Eсли $n$ не велико и все вероятности малы, кроме одной, то почти всегда происходит соответствующее ей событие. Эта ситуация вполне предсказуема (энтропия мала). При равномерном же распределении вероятностей может произойти "что угодно" (энтропия максимальна).


☝ Доказательство основного свойства энтропии проводится при помощи поиска экстремума со связями (метод множителей Лагранжа). Условие нормировки (сумма $p_\alpha$ равна 1) умножаем на параметр $\lambda$ и добавляем к энтропии. Затем ищем экстремум по $p_1,...,p_n,\lambda$: $$ H = -\sum p_\alpha\,\ln p_\alpha + \lambda\,\bigr(\sum p_\alpha- 1\bigr), ~~~~~~~\frac{\partial H}{\partial p_\alpha} = -\ln p_\alpha - 1 +\lambda = 0~~~~~=>~~~~~p_\alpha=\mathrm{const}. $$ Производная по $\lambda$ даёт условие нормировки и которого следует, что $p_\alpha=1/n$.


Код Хаффмана

Пусть есть строка символов, вероятности которых равны обратным степеням двойки. Закодируем каждый символ двоичным числом так, чтобы длина кода была тем больше, чем меньше вероятность символа. Тогда энтропия по логарифму с основанием $2$ равна средней длине в битах (на символ) кода строки символов.

Например, пусть вероятности символов $\{a,b,c,d,e\}$ равны $\{1/2,~1/4,~1/8,~1/16,~1/16\}$. Построим бинарное дерево листьями которого являются символы. Спускаясь вниз от корня (равновероятно выбирая левую или правую ветки), мы будем попадать в эти символы с заданными вероятностями (см. рисунок). Тогда оптимальный код символа будет кодом пути к нему по дереву ($0$ - на левую ветку, $1$ - на правую):

Если $p_b = 1/2^b$, то $b = -\log_2 p_b$ равно числу бит (шагов от корня к листу). Соответственно, средняя длина на символ $b\,p_b$ равна энтропии текста.

Такой код является префиксным кодом Хаффмана и не требует разделительного символа (бинарная последовательность однозначно декодируется). Когда вероятности не являются обратными степенями двойки, также можно построить бинарное дерево, следуя следующему алгоритму. Сначала из списка символов выбирают два символа с самыми малыми вероятностями и объединяют их в бинарную ветку (выше это были бы d,e). Затем эти символы из списка удаляют, а вместо них в список помещают корень их ветки (как фиктивный символ) с их суммарной вероятностью. Процедура повторяется, пока в списке не останется единственный узел (корень бинарного дерева).

Средняя длина кода Хаффмана на символ больше или равна энтропии $H$ распределения вероятностей символов и меньше, чем $H_{\max}=\log_2 n$. Длина кода каждого символа обычно (но не всегда) равна целой части $-\log_2 p_\alpha$.


Кросс-энтропия

Рассмотрим два набора вероятностей $P=\{p_1,...,p_n\}$ и $Q=\{q_1,...,q_n\}$. Степень различности этих распределений характеризует кросс-энтропия: $$ H(P,Q) = -\sum^n_{\alpha=1} p_\alpha\,\ln q_\alpha. $$

Она достигает минимума, когда распределения совпадают $p_\alpha=q_\alpha$ (это доказывается также, как и для энтропии). На Python кросс-энтропию легко вычислить при помощи библиотеки numpy:
import numpy as np

p = np.array([0.1, 0.2, 0.7])
q = np.array([0.7, 0.1, 0.2])

H = - p @ np.log(q)
Приведём примеры кросс-энтропии:
                                    Q              H(P,Q)
                           [0.33, 0.33, 0.33]      1.10
                           [0.25, 0.25, 0.50]      0.90
P = [0.10, 0.20, 0.70]     [0.10, 0.20, 0.70]      0.80
                           [0.10, 0.10, 0.80]      0.85
                           [0.70, 0.10, 0.20]      1.62
Заметим, что для любых $P,Q$ справедливо неравенство $H(P) \le H(P,Q)$.

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

В задаче классификации с непересекающимися классами объект с признаками $\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(c)\,P(\mathbf{x}|c)}{p(\mathbf{x})} = \frac{p(c)\,P(\mathbf{x}|c)}{\sum_\alpha p(\alpha)\,P(\mathbf{x}|\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)$.


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

Байесовскую формулу можно также использовать для присваивания каждому слову $w_i$ предложения части речи $t_i$: существительное (N), прилагательное (A), глагол (V) и т.д. (Part-of-Speech Tagging). Пусть $t_i$ - один из маркеров (N, A, V...). Тогда, если известна условная вероятность $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)$.

Перплексия

Вероятностная языковая модель для данного слова $w$, по его контексту $\{\mathcal{T} - w\}$ (текст $\mathcal{T}$ без слова $w$) или по предшествующим к $w$ словам предсказывает вероятность этого слова: $P(w|\mathcal{T} - w)$. Одной из метрик качества различных моделей является перплексия. Чем меньше перплексия, тем лучше модель.

Перплексией (perplexity) текста $\mathcal{T}$ длиной $N=\mathrm{len}(\mathcal{T})$ называют: $$ \mathcal{P} = \exp\Bigr( -\frac{1}{N}\,\sum^{N}_{i=1} \ln P(w_i|\mathcal{T}-w_i) \Bigr). $$

Если вероятности $P(w_i|\mathcal{T}-w_i)$ оцениваются по предшествующей слову $w_i$ истории $P(w_i|w_1...w_{i-1})$ то, по цепному правилу имеем (сумма логарифмов равна логарифму произведения): $\mathcal{P}=\exp(-\ln P(w_1...w_n)/N)$, или: $$ \mathcal{P} = P(w_1,...,w_N)^{-1/N} \equiv \sqrt[N]{\frac{1}{P(w_1,...,w_N)}}. $$ Чем выше совместная вероятность последовательности слов, тем меньше перплексия. Важно помнить, что языковая модель должна возвращать "честную", нормированную на единицу вероятность слова $P(w_i|\mathcal{T}-w_i)$.
Т.е. сумма таких вероятностей по всем словам словаря должна равняться единице. Если это не так, то перплексия может оказаться неоправданно заниженной (например, когда для любого слова словаря модель возвращает 1).

Простейшая языковая модель, независимо от контекста, предсказывает безусловную вероятность слова: $P(w|\mathcal{T} - w) = P(w)$. В этом случае в сумме будет $N^{(i)} = P(w^{(i)})\cdot N$ раз встречаться слово $w^{(i)}$ и перплексия равна экспоненте от энропии вероятностей слов словаря: $$ \mathcal{P}_{1} = \exp\Bigr( -\sum^{n}_{\alpha=1} P\bigr(w^{(\alpha)}\bigr)\,\ln P\bigr(w^{(\alpha)}\bigr) \Bigr) ~=~ e^{H(P)}, $$ где $\mathcal{V}=\{w^{(1)},...,w^{(n)}\}$ - словарь из $n$ слов. Когда в модели все вероятности равны $P(w)=1/n$, перплексия равна мощности словаря (количеству различных слов): $\mathcal{P}_0 = n$. Минимальное значение перплексии равно 1. Перплексия, в отличии от энтропии, не зависит от основания логарифма (можно заменить $\ln\mapsto \log_2$ и $e\mapsto 2$).

Перплексию иногда интерпретируют как степень ветвления текста (branching factor) (сколько возможно веток для очередного слова, взвешенных на вероятности этих веток).

Энтропия словаря зависит от его размера. Ниже приведены значения энтропии (натуральный логарифм), вероятности которой вычислены на одном и том-же английском тексте при различных размерах словаря n (не попавшие в словарь слова заменяются на токен UNK):

n:            100    1000   5000   10000    36500
H:          2.913   4.811  5.841   6.080    6.247
P = exp H:     18     123    344     437      516
Поэтому, указание перплексии языковой модели, вообще говоря, необходимо сопровождать размером словаря которым оперирует модель.

Обычно языковую модель строят на одном множестве документов, а перплексию измеряют на другом. Чтобы не было тематического или стилевого перекоса, каждый документ разбивается на тренировочную и тестовую части (hold-out perplexity). Если в качестве ошибки модели используют кросс-энтропию CE в расчёте на слово, то перплексия равна $\mathcal{P}=\exp\text{CE}$.

Существует 1B Word Benchmark data set длиной около 829'250'940 английских слов со словарём 793'471 слов (в архиве 11 GB). На этом датасете часто сравнивают различные языковые модели (см. тут и тут). Так 5-граммные модели с интерполяцией дают значение $\mathcal{P}=67$ (1.76B параметров), LSTM + CNN INPUTS (см. этот документ) $\mathcal{P}=30$ (1.04B параметров), а ансамбль моделей достигает значения $\mathcal{P}=23.7$ (2016).