Байесовское программирование

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

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

Байесовское программирование также можно рассматривать как формальную алгебраическую систему для задания графовых моделей, таких как, например, байесовские сети, динамические байесовские сети^[en], фильтры Кальмана или скрытые марковские модели. Действительно, байесовское программирование обобщает байесовские сети и имеет выразительную мощность эквивалентную фактор-графам^[en].

Формальная системаПравить

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

Ниже представлены составляющие элементы байесовской программы:

$\text{Program}\{\begin{array}{l}\text{Description}\{\begin{array}{l}\text{Specification}(\mathrm{\pi <!--\; \pi \; -->})\{\begin{array}{l}\text{Variables}\\ \text{Decomposition}\\ \text{Forms}\end{array}\\ \text{Identification (based on }\mathrm{\delta <!--\; \delta \; -->})\end{array}\\ \text{Question}\end{array}$${\text{Program}}{\begin{cases}{\text{Description}}{\begin{cases}{\text{Specification}}(\pi ){\begin{cases}{\text{Variables}}\\{\text{Decomposition}}\\{\text{Forms}}\\\end{cases}}\\{\text{Identification (based on }}\delta )\end{cases}}\\{\text{Question}}\end{cases}}$ 

1. Программа строится из описания (англ. description) и вопроса (англ. question).
2. Описание строится с помощью какого-либо определения ($\mathrm{\pi <!--\; \pi \; -->}$$\pi$ , англ. specification), заданного программистом, и идентификации (англ. identification) или процесса обучения для параметров, не полностью описанных в определении, с применением набора данных ($\mathrm{\delta <!--\; \delta \; -->}$$\delta$ ).
3. Определение строится из набора значимых переменных (англ. variables), декомпозиции (англ. decomposition) и набора форм (англ. forms).
4. Формы являются или параметрическими формами, или вопросами к другим байесовским программам.
5. Вопрос задает распределение вероятности, которое необходимо вычислить.

ОписаниеПравить

Описание задает эффективный метод вычисления совместного распределения вероятности^[en] набора переменных $\left\{X_1,X_2,\cdots <!--\; \cdots \; -->,X_N\right\}$$\left\{X_{1},X_{2},\cdots ,X_{N}\right\}$  для заданного набора экспериментальных данных $\mathrm{\delta <!--\; \delta \; -->}$$\delta$  и некоторого определения $\mathrm{\pi <!--\; \pi \; -->}$$\pi$ . Это совместное распределение обозначается как $P\left(X_1\wedge <!--\; \wedge \; -->X_2\wedge <!--\; \wedge \; -->\cdots <!--\; \cdots \; -->\wedge <!--\; \wedge \; -->X_N\mid <!--\; \mid \; -->\mathrm{\delta <!--\; \delta \; -->}\wedge <!--\; \wedge \; -->\mathrm{\pi <!--\; \pi \; -->}\right)$$P\left(X_{1}\wedge X_{2}\wedge \cdots \wedge X_{N}\mid \delta \wedge \pi \right)$ .

Чтобы задать предварительное знание $\mathrm{\pi <!--\; \pi \; -->}$$\pi$ , программист должен выполнить следующее:

1. Определить набор значимых переменных $\left\{X_1,X_2,\cdots <!--\; \cdots \; -->,X_N\right\}$$\left\{X_{1},X_{2},\cdots ,X_{N}\right\}$ , на которых задано совместное распределение вероятности.
2. Разложить совместное распределение (разбить его на подходящие независимые или условные вероятности).
3. Определить формы каждого из этих распределений (например, для каждой переменной выбрать одно из перечня распределений вероятности^[en]).

ДекомпозицияПравить

Пусть множество $\left\{X_1,X_2,\dots <!--\; \dots \; -->,X_N\right\}$$\left\{X_{1},X_{2},\ldots ,X_{N}\right\}$  содержит $K$$K$  подмножеств, переменные $K$$K$  определены как $L_1,\cdots <!--\; \cdots \; -->,L_K$$L_{1},\cdots ,L_{K}$ , каждая из которых соответствует одному из этих подмножеств. Каждая переменная $L_k$$L_{k}$  получается как конъюнкция переменных $\left\{X_{k_1},X_{k_2},\cdots <!--\; \cdots \; -->\right\}$$\left\{X_{k_{1}},X_{k_{2}},\cdots \right\}$ , относящихся к $k$$k$ -тому подмножеству. Рекурсивное применение теоремы Байеса приводит к

${\begin{aligned}&P\left(X_{1}\wedge X_{2}\wedge \cdots \wedge X_{N}\mid \delta \wedge \pi \right)\\={}&P\left(L_{1}\wedge \cdots \wedge L_{K}\mid \delta \wedge \pi \right)\\={}&P\left(L_{1}\mid \delta \wedge \pi \right)\times P\left(L_{2}\mid L_{1}\wedge \delta \wedge \pi \right)\times \cdots \times P\left(L_{K}\mid L_{K-1}\wedge \cdots \wedge L_{1}\wedge \delta \wedge \pi \right)\end{aligned}}$ 

Применение гипотезы условной независимости позволяют проделать дальнейшие упрощения. Гипотеза условной независимости для переменной $L_k$$L_{k}$  определяется выбором некоторой переменной $X_n$$X_{{n}}$  среди переменных, присутствующих в конъюнкции $L_{k-<!--\; -\; -->1}\wedge <!--\; \wedge \; -->\cdots <!--\; \cdots \; -->\wedge <!--\; \wedge \; -->L_2\wedge <!--\; \wedge \; -->L_1$$L_{k-1}\wedge \cdots \wedge L_{2}\wedge L_{1}$ . Обозначая через $R_k$$R_{k}$  конъюнкцию выбранных переменных и принимая

$P\left(L_k\mid <!--\; \mid \; -->L_{k-<!--\; -\; -->1}\wedge <!--\; \wedge \; -->\cdots <!--\; \cdots \; -->\wedge <!--\; \wedge \; -->L_1\wedge <!--\; \wedge \; -->\mathrm{\delta <!--\; \delta \; -->}\wedge <!--\; \wedge \; -->\mathrm{\pi <!--\; \pi \; -->}\right)=P\left(L_k\mid <!--\; \mid \; -->R_k\wedge <!--\; \wedge \; -->\mathrm{\delta <!--\; \delta \; -->}\wedge <!--\; \wedge \; -->\mathrm{\pi <!--\; \pi \; -->}\right)$$P\left(L_{k}\mid L_{k-1}\wedge \cdots \wedge L_{1}\wedge \delta \wedge \pi \right)=P\left(L_{k}\mid R_{k}\wedge \delta \wedge \pi \right)$ 

Получаем

${\begin{aligned}&P\left(X_{1}\wedge X_{2}\wedge \cdots \wedge X_{N}\mid \delta \wedge \pi \right)\\={}&P\left(L_{1}\mid \delta \wedge \pi \right)\times P\left(L_{2}\mid R_{2}\wedge \delta \wedge \pi \right)\times \cdots \times P\left(L_{K}\mid R_{K}\wedge \delta \wedge \pi \right)\end{aligned}}$ 

Такое упрощение совместного распределения в виде произведения более простых распределений называется декомпозицией, выведенной с помощью цепного правила^[en].

Это обеспечивает, чтобы каждая переменная появлялась слева от черточки условности не менее одного раза, что является необходимым и достаточным условием написания математически верных выкладок.

ФормыПравить

Каждое распределение $P\left(L_k\mid <!--\; \mid \; -->R_k\wedge <!--\; \wedge \; -->\mathrm{\delta <!--\; \delta \; -->}\wedge <!--\; \wedge \; -->\mathrm{\pi <!--\; \pi \; -->}\right)$$P\left(L_{k}\mid R_{k}\wedge \delta \wedge \pi \right)$ , встречающееся в произведении, далее связывается или с параметрической формой (то есть функцией $f_{\mathrm{\mu <!--\; \mu \; -->}}\left(L_k\right)$$f_{\mu }\left(L_{k}\right)$ ), или с вопросом к другой байсовской программе $P\left(L_k\mid <!--\; \mid \; -->R_k\wedge <!--\; \wedge \; -->\mathrm{\delta <!--\; \delta \; -->}\wedge <!--\; \wedge \; -->\mathrm{\pi <!--\; \pi \; -->}\right)=P\left(L\mid <!--\; \mid \; -->R\wedge <!--\; \wedge \; -->\stackrel{^<!--\; ^\; -->}{\mathrm{\delta <!--\; \delta \; -->}}\wedge <!--\; \wedge \; -->\stackrel{^<!--\; ^\; -->}{\mathrm{\pi <!--\; \pi \; -->}}\right)$$P\left(L_{k}\mid R_{k}\wedge \delta \wedge \pi \right)=P\left(L\mid R\wedge {\widehat {\delta }}\wedge {\widehat {\pi }}\right)$ .

Когда это форма $f_{\mathrm{\mu <!--\; \mu \; -->}}\left(L_k\right)$$f_{\mu }\left(L_{k}\right)$ , в общем случае $\mathrm{\mu <!--\; \mu \; -->}$$\mu$  является вектором параметров, которые могут зависеть или от $R_k$$R_{k}$ , или $\mathrm{\delta <!--\; \delta \; -->}$$\delta$ , или от обоих. Когда некоторые из этих параметров вычисляются с применением набора данных $\mathrm{\delta <!--\; \delta \; -->}$$\delta$ , происходит обучение.

Важная особенность байесовского программирования — это способность использовать вопросы к другим байесовским программам как составляющую определения новой байесовской программы. $P\left(L_k\mid <!--\; \mid \; -->R_k\wedge <!--\; \wedge \; -->\mathrm{\delta <!--\; \delta \; -->}\wedge <!--\; \wedge \; -->\mathrm{\pi <!--\; \pi \; -->}\right)$$P\left(L_{k}\mid R_{k}\wedge \delta \wedge \pi \right)$  получается выводом, произведенным другой байесовской программой, заданной определением $\stackrel{^<!--\; ^\; -->}{\mathrm{\pi <!--\; \pi \; -->}}$${\widehat {\pi }}$  и данными $\stackrel{^<!--\; ^\; -->}{\mathrm{\delta <!--\; \delta \; -->}}$${\widehat {\delta }}$ . Это похоже на вызов подпрограммы в классическом программировании, и предоставляет простой способ построения иерархических моделей.

ВопросПравить

Пусть дано описание (то есть $P\left(X_1\wedge <!--\; \wedge \; -->X_2\wedge <!--\; \wedge \; -->\cdots <!--\; \cdots \; -->\wedge <!--\; \wedge \; -->X_N\mid <!--\; \mid \; -->\mathrm{\delta <!--\; \delta \; -->}\wedge <!--\; \wedge \; -->\mathrm{\pi <!--\; \pi \; -->}\right)$$P\left(X_{1}\wedge X_{2}\wedge \cdots \wedge X_{N}\mid \delta \wedge \pi \right)$ ), вопрос получается разбиением $\left\{X_1,X_2,\cdots <!--\; \cdots \; -->,X_N\right\}$$\left\{X_{1},X_{2},\cdots ,X_{N}\right\}$  на три множества: исследуемые (англ. searched) переменные, известные (англ. known) переменные и свободные (англ. free) переменные.

Три переменные $Searched$$Searched$ , $Known$$Known$  и $Free$$Free$  определяются как конъюнкция переменных, принадлежащих к этим множествам.

Вопрос определяется как набор распределений

$P\left(Searched\mid <!--\; \mid \; -->\text{Known}\wedge <!--\; \wedge \; -->\mathrm{\delta <!--\; \delta \; -->}\wedge <!--\; \wedge \; -->\mathrm{\pi <!--\; \pi \; -->}\right)$$P\left(Searched\mid {\text{Known}}\wedge \delta \wedge \pi \right)$ 

составленный из «конкретизированных вопросов» как кардинал $Known$$Known$ , где каждый конкретизированный вопрос является распределением

$P\left(\text{Searched}\mid <!--\; \mid \; -->\text{Known}\wedge <!--\; \wedge \; -->\mathrm{\delta <!--\; \delta \; -->}\wedge <!--\; \wedge \; -->\mathrm{\pi <!--\; \pi \; -->}\right)$$P\left({\text{Searched}}\mid {\text{Known}}\wedge \delta \wedge \pi \right)$ 

ВыводПравить

Для заданного совместного распределения $P\left(X_1\wedge <!--\; \wedge \; -->X_2\wedge <!--\; \wedge \; -->\cdots <!--\; \cdots \; -->\wedge <!--\; \wedge \; -->X_N\mid <!--\; \mid \; -->\mathrm{\delta <!--\; \delta \; -->}\wedge <!--\; \wedge \; -->\mathrm{\pi <!--\; \pi \; -->}\right)$$P\left(X_{1}\wedge X_{2}\wedge \cdots \wedge X_{N}\mid \delta \wedge \pi \right)$  всегда возможно вычислить любой вопрос, применяя следующий общий вывод:

${\begin{aligned}&P\left({\text{Searched}}\mid {\text{Known}}\wedge \delta \wedge \pi \right)\\={}&\sum _{\text{Free}}\left[P\left({\text{Searched}}\wedge {\text{Free}}\mid {\text{Known}}\wedge \delta \wedge \pi \right)\right]\\={}&{\frac {\displaystyle \sum _{\text{Free}}\left[P\left({\text{Searched}}\wedge {\text{Free}}\wedge {\text{Known}}\mid \delta \wedge \pi \right)\right]}{\displaystyle P\left({\text{Known}}\mid \delta \wedge \pi \right)}}\\={}&{\frac {\displaystyle \sum _{\text{Free}}\left[P\left({\text{Searched}}\wedge {\text{Free}}\wedge {\text{Known}}\mid \delta \wedge \pi \right)\right]}{\displaystyle \sum _{{\text{Free}}\wedge {\text{Searched}}}\left[P\left({\text{Searched}}\wedge {\text{Free}}\wedge {\text{Known}}\mid \delta \wedge \pi \right)\right]}}\\={}&{\frac {1}{Z}}\times \sum _{\text{Free}}\left[P\left({\text{Searched}}\wedge {\text{Free}}\wedge {\text{Known}}\mid \delta \wedge \pi \right)\right]\end{aligned}}$ 

где первое равенство следует из правила обособления (англ. marginalization rule), второе вытекает из теоремы Байеса, а третье соответствует второму применению обособления. Знаменатель оказывается нормирующим членом (англ. normalization term), и его можно заменить постоянной $Z$$Z$ .

Теоретически это позволяет решать любые задачи байесовского вывода. Однако на практике почти во всех случаях затраты на исчерпывающее и точное вычисление $P\left(\text{Searched}\mid <!--\; \mid \; -->\text{Known}\wedge <!--\; \wedge \; -->\mathrm{\delta <!--\; \delta \; -->}\wedge <!--\; \wedge \; -->\mathrm{\pi <!--\; \pi \; -->}\right)$$P\left({\text{Searched}}\mid {\text{Known}}\wedge \delta \wedge \pi \right)$  оказываются слишком большими.

Заменяя совместное распределение его декомпозицией, получаем

${\begin{aligned}&P\left({\text{Searched}}\mid {\text{Known}}\wedge \delta \wedge \pi \right)\\={}&{\frac {1}{Z}}\sum _{\text{Free}}\left[\prod _{k=1}^{K}\left[P\left(L_{i}\mid K_{i}\wedge \pi \right)\right]\right]\end{aligned}}$ 

которое обычно является выражением, значительно более простым для вычисления, поскольку размерность задачи значительно снижена разложением на произведение распределений меньшей размерности.

ПримерПравить

Байесовское обнаружение спамаПравить

Целью байесовской фильтрации спама является устранение мусорных электронных писем.

Формулировка этой задачи достаточно простая. Электронные письма должны классифицироваться по одной из двух категорий: не-спам и спам. Единственной доступной информацией для классификации электронных писем является их содержание: набор слов. Использование слов без принятия во внимания их порядка в предложении часто называют моделью мешка слов.

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

ПеременныеПравить

Следующие переменные необходимы для написания этой программы:

1. $Spam$$Spam$ : двоичная переменная, ложь, если электронное письмо не является спамом, и истина в противном случае.
2. $W_0,W_1,\dots <!--\; \dots \; -->,W_{N-<!--\; -\; -->1}$$W_{0},W_{1},\ldots ,W_{N-1}$ : $N$$N$  двоичных переменных. $W_n$$W_{n}$  является истиной, если $n$$n$ -ое слово словаря присутствует в тексте.

Эти $N+1$$N+1$  двоичных переменных суммируют всю информацию об электронной почте.

ДекомпозицияПравить

Начиная с определения совместного распределения и рекурсивно применяя теорему Байеса, получаем:

${\begin{aligned}&P({\text{Spam}}\wedge W_{0}\wedge \cdots \wedge W_{N-1})\\={}&P({\text{Spam}})\times P(W_{0}\mid {\text{Spam}})\times P(W_{1}\mid {\text{Spam}}\wedge W_{0})\\&\times \cdots \\&\times P\left(W_{N-1}\mid {\text{Spam}}\wedge W_{0}\wedge \cdots \wedge W_{N-2}\right)\end{aligned}}$ 

Это точное математическое выражение.

Оно может быть радикально упрощено, если предположить, что вероятность появления слова при известной категории текста (спам или нет) является независимой от появления других слов. Такое предположение является наивным байесовским, и поэтому этот фильтр спама является наивной байсовской моделью.

Например, программист может предположить, что

$P(W_1\mid <!--\; \mid \; -->\text{Spam}\wedge <!--\; \wedge \; -->W_0)=P(W_1\mid <!--\; \mid \; -->\text{Spam})$$P(W_{1}\mid {\text{Spam}}\land W_{0})=P(W_{1}\mid {\text{Spam}})$ 

и в итоге получить

$P(\text{Spam}\wedge <!--\; \wedge \; -->W_0\wedge <!--\; \wedge \; -->\dots <!--\; \dots \; -->\wedge <!--\; \wedge \; -->W_{N-<!--\; -\; -->1})=P(\text{Spam})\underset{n=0}{\overset{N-<!--\; -\; -->1}{\prod <!--\; \prod \; -->}}[P(W_n\mid <!--\; \mid \; -->\text{Spam})]$$P({\text{Spam}}\land W_{0}\land \ldots \land W_{N-1})=P({\text{Spam}})\prod _{n=0}^{N-1}[P(W_{n}\mid {\text{Spam}})]$ 

Это предположение известно как наивное байесовское предположение. Оно является «наивным» в том смысле, что независимость между словами, очевидно, не является истинной. Например, оно полностью пренебрегает тем, что появление пары слов может быть более значимым, чем изолированные появления. Однако программист может принять эту гипотезу, и может разрабатывать эту модель и связанный с ней вывод, чтобы проверить, насколько надежной и эффективной она является.

Параметрические формыПравить

Чтобы иметь возможность вычислить совместное распределение, программист теперь должен указать $N+1$$N+1$  распределений, присутствующих в разложении:

1. $P(\text{Spam})$$P({\text{Spam}})$  определено априорно, например, как $P([\text{Spam}=1])=0.75$$P([{\text{Spam}}=1])=0.75$ 
2. Каждая из $N$$N$  форм $P(W_n\mid <!--\; \mid \; -->\text{Spam})$$P(W_{n}\mid {\text{Spam}})$  может быть задана с помощью правила следования Лапласа^[en] (это методика сглаживания^[en] на базе псевдосчетчика^[en] для преодоления проблемы нулевой частоты до сих пор не встречавшихся слов):
   1. $P(W_n\mid <!--\; \mid \; -->[\text{Spam}=\text{false}])=\frac{1+a_f^n}{2+a_f}$$P(W_{n}\mid [{\text{Spam}}={\text{false}}])={\frac {1+a_{f}^{n}}{2+a_{f}}}$ 
   2. $P(W_n\mid <!--\; \mid \; -->[\text{Spam}=\text{true}])=\frac{1+a_t^n}{2+a_t}$$P(W_{n}\mid [{\text{Spam}}={\text{true}}])={\frac {1+a_{t}^{n}}{2+a_{t}}}$ 

где $a_f^n$$a_{f}^{n}$  — количество появлений $n$$n$ -го слова в неспамовых электронных письмах, а $a_f$$a_{f}$  — общее количество неспамовых электронных писем. Аналогично, $a_t^n$$a_{t}^{n}$  — количество появлений $n$$n$ -го слова в спамовых электронных письмах, а $a_t$$a_{t}$  — общее количество спамовых электронных писем.

ИдентификацияПравить

$N$$N$  форм $P(W_n\mid <!--\; \mid \; -->\text{Spam})$$P(W_{n}\mid {\text{Spam}})$  еще не определены полностью, поскольку $2N+2$$2N+2$  параметров $a_f^{n=0,\dots <!--\; \dots \; -->,N-<!--\; -\; -->1}$$a_{f}^{n=0,\ldots ,N-1}$ , $a_t^{n=0,\dots <!--\; \dots \; -->,N-<!--\; -\; -->1}$$a_{t}^{n=0,\ldots ,N-1}$ , $a_f$$a_{f}$  и $a_t$$a_{t}$  еще не имеют значений.

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

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

ВопросПравить

Вопрос, который задается программе: «какова вероятность того, что данный текст является спамом, если известно, какие слова в нем присутствуют, а какие — нет?» Его можно формализовать как

$P(\text{Spam}\mid <!--\; \mid \; -->w_0\wedge <!--\; \wedge \; -->\cdots <!--\; \cdots \; -->\wedge <!--\; \wedge \; -->w_{N-<!--\; -\; -->1})$$P({\text{Spam}}\mid w_{0}\wedge \cdots \wedge w_{N-1})$ 

что может быть вычислено следующим образом:

${\begin{aligned}&P({\text{Spam}}\mid w_{0}\wedge \cdots \wedge w_{N-1})\\={}&{\frac {\displaystyle P({\text{Spam}})\prod _{n=0}^{N-1}[P(w_{n}\mid {\text{Spam}})]}{\displaystyle \sum _{\text{Spam}}[P({\text{Spam}})\prod _{n=0}^{N-1}[P(w_{n}\mid {\text{Spam}})]]}}\end{aligned}}$ 

В этом выражении знаменатель оказывается нормализующей константой^[en]. Его не обязательно вычислять для того, чтобы выяснить, имеем ли мы дело со спамом. Например, простой прием для вычисления отношения:

${\begin{aligned}&{\frac {P([{\text{Spam}}={\text{true}}]\mid w_{0}\wedge \cdots \wedge w_{N-1})}{P([{\text{Spam}}={\text{false}}]\mid w_{0}\wedge \cdots \wedge w_{N-1})}}\\={}&{\frac {P([{\text{Spam}}={\text{true}}])}{P([{\text{Spam}}={\text{false}}])}}\times \prod _{n=0}^{N-1}\left[{\frac {P(w_{n}\mid [{\text{Spam}}={\text{true}}])}{P(w_{n}\mid [{\text{Spam}}={\text{false}}])}}\right]\end{aligned}}$ 

Такое вычисление является более быстрым и удобным, поскольку оно требует всего лишь $2N$$2N$  произведений.

Байесовская программаПравить

Программа байесовского фильтра спама полностью определяется как

$Pr\{\begin{array}{l}Ds\{\begin{array}{l}Sp(\mathrm{\pi <!--\; \pi \; -->})\{\begin{array}{l}Va:\text{Spam},W_0,W_1\dots <!--\; \dots \; -->W_{N-<!--\; -\; -->1}\\ Dc:\{\begin{array}{l}P(\text{Spam}\wedge <!--\; \wedge \; -->W_0\wedge <!--\; \wedge \; -->\dots <!--\; \dots \; -->\wedge <!--\; \wedge \; -->W_n\wedge <!--\; \wedge \; -->\dots <!--\; \dots \; -->\wedge <!--\; \wedge \; -->W_{N-<!--\; -\; -->1})\\ =P(\text{Spam})\underset{n=0}{\overset{N-<!--\; -\; -->1}{\prod <!--\; \prod \; -->}}P(W_n\mid <!--\; \mid \; -->\text{Spam})\end{array}\\ Fo:\{\begin{array}{l}P(\text{Spam}):\{\begin{array}{l}P([\text{Spam}=\text{false}])=0.25\\ P([\text{Spam}=\text{true}])=0.75\end{array}\\ P(W_n\mid <!--\; \mid \; -->\text{Spam}):\{\begin{array}{l}P(W_n\mid <!--\; \mid \; -->[\text{Spam}=\text{false}])\\ =\frac{1+a_f^n}{2+a_f}\\ P(W_n\mid <!--\; \mid \; -->[\text{Spam}=\text{true}])\\ =\frac{1+a_t^n}{2+a_t}\end{array}\end{array}\end{array}\\ \text{Identification (based on }\mathrm{\delta <!--\; \delta \; -->})\end{array}\\ Qu:P(\text{Spam}\mid <!--\; \mid \; -->w_0\wedge <!--\; \wedge \; -->\dots <!--\; \dots \; -->\wedge <!--\; \wedge \; -->w_n\wedge <!--\; \wedge \; -->\dots <!--\; \dots \; -->\wedge <!--\; \wedge \; -->w_{N-<!--\; -\; -->1})\end{array}$$\Pr {\begin{cases}Ds{\begin{cases}Sp(\pi ){\begin{cases}Va:{\text{Spam}},W_{0},W_{1}\ldots W_{N-1}\\Dc:{\begin{cases}P({\text{Spam}}\land W_{0}\land \ldots \land W_{n}\land \ldots \land W_{N-1})\\=P({\text{Spam}})\prod _{n=0}^{N-1}P(W_{n}\mid {\text{Spam}})\end{cases}}\\Fo:{\begin{cases}P({\text{Spam}}):{\begin{cases}P([{\text{Spam}}={\text{false}}])=0.25\\P([{\text{Spam}}={\text{true}}])=0.75\end{cases}}\\P(W_{n}\mid {\text{Spam}}):{\begin{cases}P(W_{n}\mid [{\text{Spam}}={\text{false}}])\\={\frac {1+a_{f}^{n}}{2+a_{f}}}\\P(W_{n}\mid [{\text{Spam}}={\text{true}}])\\={\frac {1+a_{t}^{n}}{2+a_{t}}}\end{cases}}\\\end{cases}}\\\end{cases}}\\{\text{Identification (based on }}\delta )\end{cases}}\\Qu:P({\text{Spam}}\mid w_{0}\land \ldots \land w_{n}\land \ldots \land w_{N-1})\end{cases}}$ 

Фильтр Байеса, фильтр Кальмана и скрытая модель МарковаПравить

Байесовские фильтры (которые часто называют рекурсивной байесовской оценкой^[en]) являются общими вероятностными моделями для процессов, разворачивающихся во времени. Многочисленные модели являются частными случаями этого общего подхода, например, фильтр Кальмана или скрытая марковская модель.

ПеременныеПравить

• Переменные $S^0,\dots <!--\; \dots \; -->,S^T$$S^{0},\ldots ,S^{T}$  — временной ряд переменных состояния, которые рассматриваются на временном горизонте в диапазоне от $0$$0$  до $T$$T$ .
• Переменные $O^0,\dots <!--\; \dots \; -->,O^T$$O^{0},\ldots ,O^{T}$  — временной ряд переменных наблюдения на этом же горизонте.

ДекомпозицияПравить

Декомпозиция основывается на:

• $P(S^t\mid <!--\; \mid \; -->S^{t-<!--\; -\; -->1})$$P(S^{t}\mid S^{t-1})$ , называемой моделью системы, моделью перехода или динамической моделью, которая формализует переход от состояния в момент времени $t-<!--\; -\; -->1$$t-1$  в состояние в момент времени $t$$t$ ;
• $P(O^t\mid <!--\; \mid \; -->S^t)$$P(O^{t}\mid S^{t})$ , называемой моделью наблюдения, которая выражает, что может наблюдаться в момент времени $t$$t$ , когда система находится в состоянии $S^t$$S^{t}$ ;
• исходном состоянии в момент времени $0$$0$ : $P(S^0\wedge <!--\; \wedge \; -->O^0)$$P(S^{0}\wedge O^{0})$ .

Параметрические формыПравить

Выбор параметрических форм не ограничен, и различные варианты ведут к различным хорошо известным моделям: см. ниже фильтры Кальмана и скрытые марковские модели.

ВопросПравить

Обычный вопрос для этих моделей — $P\left(S^{t+k}\mid <!--\; \mid \; -->O^0\wedge <!--\; \wedge \; -->\cdots <!--\; \cdots \; -->\wedge <!--\; \wedge \; -->O^t\right)$$P\left(S^{t+k}\mid O^{0}\wedge \cdots \wedge O^{t}\right)$ : каково распределение вероятности состояния в момент времени $t+k$$t+k$ , если известны наблюдения от момента $0$$0$  до $t$$t$ ?

Самый общий случай — это байесовская фильтрация, для которой $k=0$$k=0$ , что означает, что определяется состояние в настоящий момент времени при известных предыдущих наблюдениях.

Однако также возможно осуществлять и экстраполяцию $(k>0)$$(k>0)$  будущего состояния, используя прошлые наблюдения, или осуществлять сглаживание $(k<0)$ , чтобы восстановить прошлое состояние из наблюдений, сделанных или до, или после некоторого момента времени.

Могут задаваться и более сложные вопросы, как показано ниже в разделе СММ.

Байесовские фильтры $(k=0)$$(k=0)$  имеют очень интересное рекурсивное свойство, что значительно способствует их привлекательности. $P\left(S^t|O^0\wedge <!--\; \wedge \; -->\cdots <!--\; \cdots \; -->\wedge <!--\; \wedge \; -->O^t\right)$$P\left(S^{t}|O^{0}\wedge \cdots \wedge O^{t}\right)$  может быть вычислено просто с помощью $P\left(S^{t1}\mid <!--\; \mid \; -->O^0\wedge <!--\; \wedge \; -->\cdots <!--\; \cdots \; -->\wedge <!--\; \wedge \; -->O^{t-<!--\; -\; -->1}\right)$$P\left(S^{t1}\mid O^{0}\wedge \cdots \wedge O^{t-1}\right)$  по следующей формуле:

${\begin{array}{ll}&P\left(S^{t}|O^{0}\wedge \cdots \wedge O^{t}\right)\\=&P\left(O^{t}|S^{t}\right)\times \sum _{S^{t-1}}\left[P\left(S^{t}|S^{t-1}\right)\times P\left(S^{t-1}|O^{0}\wedge \cdots \wedge O^{t-1}\right)\right]\end{array}}$ 

Еще одна интересная точка зрения на это уравнение — рассмотреть существование двух фаз: фазы предвидения и фазы оценки:

• В течение фазы предвидения состояние предсказывается с помощью динамической модели и оценки состояния в предыдущий момент:

${\begin{array}{ll}&P\left(S^{t}|O^{0}\wedge \cdots \wedge O^{t-1}\right)\\=&\sum _{S^{t-1}}\left[P\left(S^{t}|S^{t-1}\right)\times P\left(S^{t-1}|O^{0}\wedge \cdots \wedge O^{t-1}\right)\right]\end{array}}$ 

• В течение фазы оценки предсказание или подтверждается, или признается недействительным с помощью последнего наблюдения:

${\begin{aligned}&P\left(S^{t}\mid O^{0}\wedge \cdots \wedge O^{t}\right)\\={}&P\left(O^{t}\mid S^{t}\right)\times P\left(S^{t}|O^{0}\wedge \cdots \wedge O^{t-1}\right)\end{aligned}}$ 

Байесовская программаПравить

$Pr{\begin{cases}Ds{\begin{cases}Sp(\pi ){\begin{cases}Va:\\S^{0},\cdots ,S^{T},O^{0},\cdots ,O^{T}\\Dc:\\{\begin{cases}&P\left(S^{0}\wedge \cdots \wedge S^{T}\wedge O^{0}\wedge \cdots \wedge O^{T}|\pi \right)\\=&P\left(S^{0}\wedge O^{0}\right)\times \prod _{t=1}^{T}\left[P\left(S^{t}|S^{t-1}\right)\times P\left(O^{t}|S^{t}\right)\right]\end{cases}}\\Fo:\\{\begin{cases}P\left(S^{0}\wedge O^{0}\right)\\P\left(S^{t}|S^{t-1}\right)\\P\left(O^{t}|S^{t}\right)\end{cases}}\end{cases}}\\Id\end{cases}}\\Qu:\\{\begin{cases}{\begin{array}{l}P\left(S^{t+k}|O^{0}\wedge \cdots \wedge O^{t}\right)\\\left(k=0\right)\equiv {\text{Filtering}}\\\left(k>0\right)\equiv {\text{Prediction}}\\\left(k<0\right)\equiv {\text{Smoothing}}\end{array}}\end{cases}}\end{cases}}$ 

Фильтр КальманаПравить

Хорошо известные фильтры Кальмана являются частным случаем байесовских фильтров.

Они задаются следующей байесовской программой:

$Pr{\begin{cases}Ds{\begin{cases}Sp(\pi ){\begin{cases}Va:\\S^{0},\cdots ,S^{T},O^{0},\cdots ,O^{T}\\Dc:\\{\begin{cases}&P\left(S^{0}\wedge \cdots \wedge O^{T}|\pi \right)\\=&\left[{\begin{array}{c}P\left(S^{0}\wedge O^{0}|\pi \right)\\\prod _{t=1}^{T}\left[P\left(S^{t}|S^{t-1}\wedge \pi \right)\times P\left(O^{t}|S^{t}\wedge \pi \right)\right]\end{array}}\right]\end{cases}}\\Fo:\\{\begin{cases}P\left(S^{t}\mid S^{t-1}\wedge \pi \right)\equiv G\left(S^{t},A\bullet S^{t-1},Q\right)\\P\left(O^{t}\mid S^{t}\wedge \pi \right)\equiv G\left(O^{t},H\bullet S^{t},R\right)\end{cases}}\end{cases}}\\Id\end{cases}}\\Qu:\\P\left(S^{T}\mid O^{0}\wedge \cdots \wedge O^{T}\wedge \pi \right)\end{cases}}$ 

• Переменные являются непрерывными.
• Модели перехода $P(S^t\mid <!--\; \mid \; -->S^{t-<!--\; -\; -->1}\wedge <!--\; \wedge \; -->\mathrm{\pi <!--\; \pi \; -->})$$P(S^{t}\mid S^{t-1}\wedge \pi )$  и наблюдения $P(O^t\mid <!--\; \mid \; -->S^t\wedge <!--\; \wedge \; -->\mathrm{\pi <!--\; \pi \; -->})$$P(O^{t}\mid S^{t}\wedge \pi )$  определяются с помощью распределения Гаусса, в котором средние значения являются линейными функциями условных переменных.

Используя эти гипотезы и рекурсивной формулу, задачу вывода для получения ответа на обычный вопрос $P(S^T\mid <!--\; \mid \; -->O^0\wedge <!--\; \wedge \; -->\cdots <!--\; \cdots \; -->\wedge <!--\; \wedge \; -->O^T\wedge <!--\; \wedge \; -->\mathrm{\pi <!--\; \pi \; -->})$$P(S^{T}\mid O^{0}\wedge \cdots \wedge O^{T}\wedge \pi )$  можно решать аналитически. Это дает чрезвычайно эффективный алгоритм, что объясняет популярность фильтров Кальмана и многочисленность их повседневных применений.

Когда очевидных линейных моделей перехода и наблюдения нет, часто все еще возможно, применяя разложение Тейлора первого порядка, считать эти модели линейными локально. Это обобщение обычно называют расширенным фильтром Кальмана^[en].

Скрытая марковская модельПравить

Скрытые марковские модели (СММ) — еще один очень популярный частный случай фильтров Кальмана.

Они задаются следующей байесовской программой:

$\Pr {\begin{cases}Ds{\begin{cases}Sp(\pi ){\begin{cases}Va:\\S^{0},\ldots ,S^{T},O^{0},\ldots ,O^{T}\\Dc:\\{\begin{cases}&P\left(S^{0}\wedge \cdots \wedge O^{T}\mid \pi \right)\\=&\left[{\begin{array}{c}P\left(S^{0}\wedge O^{0}\mid \pi \right)\\\prod _{t=1}^{T}\left[P\left(S^{t}\mid S^{t-1}\wedge \pi \right)\times P\left(O^{t}\mid S^{t}\wedge \pi \right)\right]\end{array}}\right]\end{cases}}\\Fo:\\{\begin{cases}P\left(S^{0}\wedge O^{0}\mid \pi \right)\equiv {\text{Matrix}}\\P\left(S^{t}\mid S^{t-1}\wedge \pi \right)\equiv {\text{Matrix}}\\P\left(O^{t}\mid S^{t}\wedge \pi \right)\equiv {\text{Matrix}}\end{cases}}\end{cases}}\\Id\end{cases}}\\Qu:\\\max _{S^{1}\wedge \cdots \wedge S^{T-1}}\left[P\left(S^{1}\wedge \cdots \wedge S^{T-1}\mid S^{T}\wedge O^{0}\wedge \cdots \wedge O^{T}\wedge \pi \right)\right]\end{cases}}$ 

• Переменные считаются дискретными.
• Модели перехода $P\left(S^t\mid <!--\; \mid \; -->S^{t-<!--\; -\; -->1}\wedge <!--\; \wedge \; -->\mathrm{\pi <!--\; \pi \; -->}\right)$$P\left(S^{t}\mid S^{t-1}\wedge \pi \right)$  и наблюдения $P\left(O^t\mid <!--\; \mid \; -->S^t\wedge <!--\; \wedge \; -->\mathrm{\pi <!--\; \pi \; -->}\right)$$P\left(O^{t}\mid S^{t}\wedge \pi \right)$  задаются с помощью матриц вероятностей.
• Вопрос, который чаще всего задают скрытым марковским моделям:

$\underset{S^1\wedge <!--\; \wedge \; -->\cdots <!--\; \cdots \; -->\wedge <!--\; \wedge \; -->S^{T-<!--\; -\; -->1}}{max}\left[P\left(S^1\wedge <!--\; \wedge \; -->\cdots <!--\; \cdots \; -->\wedge <!--\; \wedge \; -->S^{T-<!--\; -\; -->1}\mid <!--\; \mid \; -->S^T\wedge <!--\; \wedge \; -->O^0\wedge <!--\; \wedge \; -->\cdots <!--\; \cdots \; -->\wedge <!--\; \wedge \; -->O^T\wedge <!--\; \wedge \; -->\mathrm{\pi <!--\; \pi \; -->}\right)\right]$$\max _{S^{1}\wedge \cdots \wedge S^{T-1}}\left[P\left(S^{1}\wedge \cdots \wedge S^{T-1}\mid S^{T}\wedge O^{0}\wedge \cdots \wedge O^{T}\wedge \pi \right)\right]$ 

Какова наиболее вероятная последовательность состояний, ведущая к текущему состоянию при известных прошлых наблюдениях?

Ответ на данный вопрос можно получать посредством очень эффективного алгоритма — алгоритма Витерби.

Также для СММ был разработан алгоритм Баума-Велша.

ПрименениеПравить

Академические примененияПравить

В течение последних 15 лет байесовское программирование применялось во многих университетах для разработки как приложений в робототехнике, так и моделей в науках о жизни.

РобототехникаПравить

В робототехнике байесовское программирование применялось в автономной робототехнике, роботизированных САПР, системах расширенной помощи водителю^[en], роботизированном управлении манипуляторами^[en], мобильной робототехнике^[en], человеко-роботном взаимодействии, человеко-автомобильном взаимодействии (байесовские модели автономного водителя), программировании и обучении аватаров в видеоиграх и в стратегических играх реального времени (ИИ).

Науки о жизниПравить

В науках о жизни байесовское программирование применялось в науках о зрении для восстановления формы по движению, для моделирования зрительно-вестибулярной взаимодействия и исследования саккадического движения глаз; в восприятии и контроле речи для исследования раннего усвоения речи^[en] и появления артикулярно-акустических систем; для моделирования восприятия и контроля рукописного текста.

Распознавание образовПравить

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

Байесовское программирование и теории возможностейПравить

Сравнение вероятностных подходов (не только байесовского программирования) и теорий возможностей продолжает оставаться предметом дебатов.

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

Защита вероятностного подхода главным образом базируется на теореме Кокса^[en], которая состоит из четырех постулатов относительно рационального рассуждения в условиях неопределенности. Она показывает, что единственная математическая модель, которая удовлетворяет этим постулатам, это теория вероятности. Доказательство заключается в том, что любой другой подход отличный от теории вероятности нарушает один из этих постулатов.

Байесовское программирование и вероятностное программированиеПравить

Цель вероятностного программирования — объединение сферы классических языков программирования с вероятностным моделированием (особенно с байесовскими сетями) для того, чтобы быть в состоянии иметь дело с неопределенностью и в то же время пользоваться выразительной силы языков программирования для описания сложных моделей.

Расширенные классические языки программирования включают в себя логические языки, как предлагается в Вероятностной абдукции Горна^[en] (англ. Probabilistic Horn Abduction), Логике независимого выбора (англ. Independent Choice Logic), PRISM и ProbLog, являющимся расширением языка Prolog.

Оно также может быть расширением функциональных языков программирования (по сути LISP и Scheme), такими как IBAL или Church. Языки, лежащие в основе расширения, также могут быть объектно-ориентированными, как в случае BLOG и FACTORIE, или более стандартными, как в CES и FIGARO Архивная копия от 1 февраля 2016 на Wayback Machine.

Цель байесовского программирования несколько другая. Установка Джейнса о «вероятности как логике» отстаивает мнение, что вероятность является расширением и альтернативой логике, поверх которой может быть выстроена заново вся теория рациональности, алгоритмов и программирования. Байесовское программирование не ищет способа расширить классические языки, оно стремится заменить их новым подходом к программированию на основе вероятности, который учитывает неполноту и неопределенность.

Точное сравнение семантики и выразительной мощности байесовского и вероятностного программирования пока остается открытым вопросом.

См. такжеПравить

• Алгоритм распространения доверия
• Байесовская вероятность
• Байесовский вывод
• Байесовская фильтрация спама
• Вероятностная логика
• Графическая вероятностная модель
• EM-алгоритм
• Лаплас, Пьер-Симон
• Наивный байесовский классификатор
• Перл, Джуда
• Правило Байеса
• Скрытая марковская модель
• Субъективная логика^[en]
• Теорема Кокса^[en]
• Фактор-граф^[en]
• Фильтр Кальмана
• Язык вероятностного программирования^[en]

ЛитератураПравить

• Kamel Mekhnacha. Bayesian Programming (англ.). — Chapman and Hall/CRC, 2013. — ISBN 978-1-4398-8032-6.Bayesian Programming. Chapman and Hall/CRC. ISBN 978-1-4398-8032-6.

СсылкаПравить

• Сайт-спутник книги «Байесовское программирование», откуда можно скачать ProBT и машину вывода. Архивировано 23 ноября 2013 года.  (англ.)
• Сайт bayesian-programming.org Архивировано 23 ноября 2013 года., продвигающий байесовское программирование, с подробной информацией и многочисленными публикациями.  (англ.)