ML: Стохастические процессы
Введение
В ряде задач рассматривается упорядоченная последовательность
случайных величин $\{X_1,X_2,...,X_n\}$.
Если это последовательность во времени, то говорят о случайном процессе $X_t$.
В этом случае последовательность
$\{x_1,x_2,...,x_n\}$ наблюдается в одном испытании (данная реализация значений случайных величин).
Этот документ продолжает серию материалов по теории вероятностей. Предварительно стоит ознакомится с введением в теорию, байсовскими методами и понятием энтропия.
Вероятности букв в тексте
Рассмотрим в качестве примера случайного процесса естественный язык. Пусть есть словарь $\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{э} \to \mathbf{т})$, равной вероятности появления буквы 'т' если перед ней в тексте стоит 'э', необходимо отобрать все подстроки, удовлетворяющие маске '$\mathbf{э*}$' ('$\mathbf{э}$', затем любой символ '$\mathbf{*}$'), и выяснить, сколько среди них 'эт': $$ P(\mathbf{эт})= \frac{N(\mathbf{эт})}{N(\mathbf{**})} = 0.002,~~~~~~~~~~~~~~~~~~~~ P(\mathbf{э}\to \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{э}\to \mathbf{т}). $$
Так как в языке терминальных букв нет (после которых нет других букв), то сумма $P(w_1\to w_2)$ по всем $w_2$ из словаря должна равняться единице (после $w_1$ будет хоть какая-то буква). Это же справедливо и в общем случае. Если $P(w_1,...,w_{n-1})$ отлично от нуля, то сумма $P(w_1,...,w_{n-1}\to 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} \to w_n). $$ Применяя это соотношение рекурсивно, несложно получить т.н. цепное правило (сhain rule) для вычисления совместной вероятности через условные: $$ P(w_1,...,w_n) ~=~ P(w_1)\cdot P(w_1\to w_2)\cdot...\cdot P(w_1...w_{n-1} \to w_n) ~=~ \prod^N_{k=1} P(w_1...w_{k-1} \to w_k). $$ Эта формула интерпретруется следующим образом: сначала с вероятностью $P(w_1)$ появляется буква $w_1$. Если это произошло, с вероятностью $P(w_1\to w_2)$ появится $w_2$ и т.д.
В марковских случайных процессах длинная история "забывается" и $$ P(w_1,...,w_{n-1} \to w_n) = P(w_{n-k},...,w_{n-1} \to w_n). $$ Если условные вероятности не меняются вдоль последовательности, то такой процесс называется стационарным.
А.А. Марков рассмотривал простейший случай $k=1$, когда совместную вероятность $P(w_1,...,w_n)$ можно выразить через вероятности $P(w_{k-1}\to w_k)$. Приведём пример чуть более сложного случая с историей длины $2$: $$ P(w_1,...,w_n) = P(w_1)\cdot P(w_1\to w_2) \cdot P(w_1 w_2\to w_3) \cdot P(w_2w_3\to w_4)\cdot...\cdot P(w_{n-1}w_{n-2}\to w_n). $$
Естественно, что свойства "короткой памяти" и "стационарности" являются приближениями и их справедливость проверяется качеством работы моделей, которые используют эти приближения.
