Русская Википедия:Байесовское программирование

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

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

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

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

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

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

<math>

\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} </math>

1. Программа строится из описания (Шаблон:Lang-en) и вопроса (Шаблон:Lang-en).
2. Описание строится с помощью какого-либо определения (<math>\pi</math>, Шаблон:Lang-en), заданного программистом, и идентификации (Шаблон:Lang-en) или процесса обучения для параметров, не полностью описанных в определении, с применением набора данных (<math>\delta</math>).
3. Определение строится из набора значимых переменных (Шаблон:Lang-en), декомпозиции (Шаблон:Lang-en) и набора форм (Шаблон:Lang-en).
4. Формы являются или параметрическими формами, или вопросами к другим байесовским программам.
5. Вопрос задает распределение вероятности, которое необходимо вычислить.

Описание

Описание задает эффективный метод вычисления Шаблон:Нп5 набора переменных <math>\left\{ X_{1},X_{2},\cdots,X_{N}\right\}</math> для заданного набора экспериментальных данных <math>\delta</math> и некоторого определения <math>\pi</math>. Это совместное распределение обозначается как <math>P\left(X_{1}\wedge X_{2}\wedge\cdots\wedge X_{N}\mid\delta\wedge\pi\right)</math>.

Чтобы задать предварительное знание <math>\pi</math>, программист должен выполнить следующее:

1. Определить набор значимых переменных <math>\left\{ X_{1},X_{2},\cdots,X_{N}\right\}</math>, на которых задано совместное распределение вероятности.
2. Разложить совместное распределение (разбить его на подходящие независимые или условные вероятности).
3. Определить формы каждого из этих распределений (например, для каждой переменной выбрать одно из Шаблон:Нп5).

Декомпозиция

Пусть множество <math>\left\{ X_{1},X_{2},\ldots,X_{N}\right\}</math> содержит <math>K</math> подмножеств, переменные <math>K</math> определены как <math>L_{1},\cdots,L_{K}</math>, каждая из которых соответствует одному из этих подмножеств. Каждая переменная <math>L_{k}</math> получается как конъюнкция переменных <math>\left\{ X_{k_{1}},X_{k_{2}},\cdots\right\}</math>, относящихся к <math>k</math>-тому подмножеству. Рекурсивное применение теоремы Байеса приводит к

<math>

\begin{align}

& 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{align} </math> Применение гипотезы условной независимости позволяют проделать дальнейшие упрощения. Гипотеза условной независимости для переменной <math>L_{k}</math> определяется выбором некоторой переменной <math>X_{n}</math> среди переменных, присутствующих в конъюнкции <math>L_{k-1}\wedge\cdots\wedge L_{2}\wedge L_{1}</math>. Обозначая через <math>R_{k}</math> конъюнкцию выбранных переменных и принимая

<math>

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) </math> Получаем

<math>

\begin{align}

& 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{align} </math> Такое упрощение совместного распределения в виде произведения более простых распределений называется декомпозицией, выведенной с помощью Шаблон:Нп5.

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

Формы

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

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

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

Вопрос

Пусть дано описание (то есть <math>P\left(X_{1}\wedge X_{2}\wedge\cdots\wedge X_{N}\mid\delta\wedge\pi\right)</math>), вопрос получается разбиением <math>\left\{ X_{1},X_{2},\cdots,X_{N}\right\}</math> на три множества: исследуемые (Шаблон:Lang-en) переменные, известные (Шаблон:Lang-en) переменные и свободные (Шаблон:Lang-en) переменные.

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

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

<math>

P\left(Searched\mid \text{Known}\wedge\delta\wedge\pi\right) </math> составленный из «конкретизированных вопросов» как кардинал <math>Known</math>, где каждый конкретизированный вопрос является распределением

<math>

P\left(\text{Searched}\mid\text{Known}\wedge\delta\wedge\pi\right) </math>

Вывод

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

<math>

\begin{align}

& 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{align} </math> где первое равенство следует из правила обособления (Шаблон:Lang-en), второе вытекает из теоремы Байеса, а третье соответствует второму применению обособления. Знаменатель оказывается нормирующим членом (Шаблон:Lang-en), и его можно заменить постоянной <math>Z</math>.

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

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

<math>

\begin{align}

& 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{align} </math> которое обычно является выражением, значительно более простым для вычисления, поскольку размерность задачи значительно снижена разложением на произведение распределений меньшей размерности.

Пример

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

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

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

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

Переменные

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

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

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

Декомпозиция

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

<math>

\begin{align}

& 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{align}

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

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

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

<math>

P(W_1\mid\text{Spam} \land W_0) = P(W_1\mid\text{Spam}) </math> и в итоге получить

<math>

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})]

</math>

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

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

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

1. <math>P(\text{Spam})</math> определено априорно, например, как <math>P([\text{Spam}=1]) = 0.75 </math>
2. Каждая из <math>N</math> форм <math>P(W_n\mid\text{Spam})</math> может быть задана с помощью Шаблон:Нп5 (это Шаблон:Нп5 на базе Шаблон:Нп5 для преодоления проблемы нулевой частоты до сих пор не встречавшихся слов):
   1. <math>P(W_n\mid[\text{Spam}=\text{false}])=\frac{1+a^n_f}{2+a_f}</math>
   2. <math>P(W_n\mid[\text{Spam}=\text{true}])=\frac{1+a^n_t}{2+a_t}</math>

где <math>a^n_f</math> — количество появлений <math>n</math>-го слова в неспамовых электронных письмах, а <math>a_f</math> — общее количество неспамовых электронных писем. Аналогично, <math>a_t^n</math> — количество появлений <math>n</math>-го слова в спамовых электронных письмах, а <math>a_t</math> — общее количество спамовых электронных писем.

Идентификация

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

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

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

Вопрос

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

<math>P (\text{Spam}\mid w_0 \wedge\cdots\wedge w_{N-1} )</math>

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

<math>\begin{align}

& 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{align}</math> В этом выражении знаменатель оказывается Шаблон:Нп5. Его не обязательно вычислять для того, чтобы выяснить, имеем ли мы дело со спамом. Например, простой прием для вычисления отношения:

<math>

\begin{align}

& \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{align} </math> Такое вычисление является более быстрым и удобным, поскольку оно требует всего лишь <math>2N</math> произведений.

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

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

<math>

\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^n_f}{2+a_f} \\
              P(W_n\mid[\text{Spam}=\text{true}])\\
              =\frac{1+a^n_t}{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} </math>

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

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

Переменные

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

Декомпозиция

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

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

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

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

Вопрос

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

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

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

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

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

<math>

\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} </math> Еще одна интересная точка зрения на это уравнение — рассмотреть существование двух фаз: фазы предвидения и фазы оценки:

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

<math>

\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} </math>

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

<math>

\begin{align}

& 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{align} </math>

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

<math>

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} </math>

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

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

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

<math>

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} </math>

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

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

Когда очевидных линейных моделей перехода и наблюдения нет, часто все еще возможно, применяя разложение Тейлора первого порядка, считать эти модели линейными локально. Это обобщение обычно называют Шаблон:Нп5.

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

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

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

<math>

\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} </math>

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

<math>

\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] </math> Какова наиболее вероятная последовательность состояний, ведущая к текущему состоянию при известных прошлых наблюдениях?

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

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

Применение

Академические применения

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

Робототехника

В робототехнике байесовское программирование применялось в автономной робототехнике, роботизированных САПР, Шаблон:Нп5, Шаблон:Нп5, Шаблон:Нп5, человеко-роботном взаимодействии, человеко-автомобильном взаимодействии (байесовские модели автономного водителя), программировании и обучении аватаров в видеоиграх и в стратегических играх реального времени (ИИ).

Науки о жизни

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

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

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

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

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

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

Защита вероятностного подхода главным образом базируется на Шаблон:Нп5, которая состоит из четырех постулатов относительно рационального рассуждения в условиях неопределенности. Она показывает, что единственная математическая модель, которая удовлетворяет этим постулатам, это теория вероятности. Доказательство заключается в том, что любой другой подход отличный от теории вероятности нарушает один из этих постулатов.

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

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

Расширенные классические языки программирования включают в себя логические языки, как предлагается в Шаблон:Нп5 (Шаблон:Lang-en), Логике независимого выбора (Шаблон:Lang-en), PRISM и ProbLog, являющимся расширением языка Prolog.

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

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

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

Литература

• Шаблон:КнигаBayesian Programming. Chapman and Hall/CRC. ISBN 978-1-4398-8032-6.

Ссылка

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