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

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

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

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

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

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

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

${\displaystyle {\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. Описание строится с помощью какого-либо определения (${\displaystyle \pi }$, англ. specification), заданного программистом, и идентификации (англ. identification) или процесса обучения для параметров, не полностью описанных в определении, с применением набора данных (${\displaystyle \delta }$).
3. Определение строится из набора значимых переменных (англ. variables), декомпозиции (англ. decomposition) и набора форм (англ. forms).
4. Формы являются или параметрическими формами, или вопросами к другим байесовским программам.
5. Вопрос задает распределение вероятности, которое необходимо вычислить.

Описание

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

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

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

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

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

${\displaystyle {\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}}}$

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

${\displaystyle 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)}$

Получаем

${\displaystyle {\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}}}$

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

Это обеспечивает, чтобы каждая переменная появлялась слева от черточки условности не менее одного раза, что является необходимым и достаточным условием написания математически верных выкладок^{[источник не указан 3219 дней]}.

Формы

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

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

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

Вопрос

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

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

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

${\displaystyle P\left(Searched\mid {\text{Known}}\wedge \delta \wedge \pi \right)}$

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

${\displaystyle P\left({\text{Searched}}\mid {\text{Known}}\wedge \delta \wedge \pi \right)}$

Вывод

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

${\displaystyle {\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), и его можно заменить постоянной ${\displaystyle Z}$.

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

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

${\displaystyle {\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. ${\displaystyle Spam}$: двоичная переменная, ложь, если электронное письмо не является спамом, и истина в противном случае.
2. ${\displaystyle W_{0},W_{1},\ldots ,W_{N-1}}$: ${\displaystyle N}$ двоичных переменных. ${\displaystyle W_{n}}$ является истиной, если ${\displaystyle n}$-ое слово словаря присутствует в тексте.

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

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

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

${\displaystyle {\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}}}$

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

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

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

${\displaystyle P(W_{1}\mid {\text{Spam}}\land W_{0})=P(W_{1}\mid {\text{Spam}})}$

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

${\displaystyle 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}})]}$

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

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

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

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

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

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

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

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

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

Вопрос

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

${\displaystyle P({\text{Spam}}\mid w_{0}\wedge \cdots \wedge w_{N-1})}$

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

${\displaystyle {\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}}}$

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

${\displaystyle {\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}}}$

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

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

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

${\displaystyle \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}}}$

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

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

Переменные

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

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

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

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

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

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

Вопрос

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

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

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

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

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

${\displaystyle {\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}}}$

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

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

${\displaystyle {\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}}}$

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

${\displaystyle {\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}}}$

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

${\displaystyle 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}}}$

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

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

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

${\displaystyle 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}}}$

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

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

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

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

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

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

${\displaystyle \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}}}$

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

${\displaystyle \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 лет байесовское программирование применялось во многих университетах для разработки как приложений в робототехнике, так и моделей в науках о жизни^[4].

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

В робототехнике байесовское программирование применялось в автономной робототехнике^{[5][6][7][8][9]}, роботизированных САПР^[10], системах расширенной помощи водителю^{[англ.][11]}, роботизированном управлении манипуляторами^[англ.], мобильной робототехнике^{[англ.][12][13]}, человеко-роботном взаимодействии^[14], человеко-автомобильном взаимодействии (байесовские модели автономного водителя)^{[15][16][17][18][19][20]}, программировании и обучении аватаров в видеоиграх^[21] и в стратегических играх реального времени (ИИ).^[22]

Науки о жизни

В науках о жизни байесовское программирование применялось в науках о зрении для восстановления формы по движению^[23], для моделирования зрительно-вестибулярной взаимодействия^[24] и исследования саккадического движения глаз^[25]; в восприятии и контроле речи для исследования раннего усвоения речи^{[англ.][26]} и появления артикулярно-акустических систем^[27]; для моделирования восприятия и контроля рукописного текста^[28].

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

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

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

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

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

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

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

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

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

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

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

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

См. также

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

Примечания

1. Jaynes, Edwin T. Probability Theory: The Logic of Science (англ.). — Cambridge University Press, 2003. — ISBN 0-521-59271-2. Архивировано 21 февраля 2016 года.
2. Bessière, P.; Mazer, E.; Ahuactzin, J-M.; Mekhnacha, K. Bayesian Programming (англ.). — Chapman & Hall/CRC, 2013. — ISBN 9781439880326.
3. Kalman, R. E. A New Approach to Linear Filtering and Prediction Problems (англ.) // Transactions of the ASME--Journal of Basic Engineering : journal. — 1960. — Vol. 82. — P. 33——45. — doi:10.1115/1.3662552.
4. Bessière, P.; Laugier, C. & Siegwart, R. Probabilistic Reasoning and Decision Making in Sensory-Motor Systems (англ.). — Springer^[англ.], 2008. — ISBN 978-3-540-79007-5.
5. Lebeltel, O.; Bessière, P.; Diard, J.; Mazer, E. Bayesian Robot Programming (англ.) // Advanced Robotics. — 2004. — Vol. 16, no. 1. — P. 49——79. — doi:10.1023/b:auro.0000008671.38949.43.
6. Diard, J.; Gilet, E.; Simonin, E.; Bessière, P. Incremental learning of Bayesian sensorimotor models: from low-level behaviours to large-scale structure of the environment (англ.) // Connection Science : journal. — 2010. — Vol. 22, no. 4. — P. 291——312. — doi:10.1080/09540091003682561.
7. Pradalier, C.; Hermosillo, J.; Koike, C.; Braillon, C.; Bessière, P.; Laugier, C. The CyCab: a car-like robot navigating autonomously and safely among pedestrians (англ.) // Robotics and Autonomous Systems : journal. — 2005. — Vol. 50, no. 1. — P. 51——68. — doi:10.1016/j.robot.2004.10.002.
8. Ferreira, J.; Lobo, J.; Bessière, P.; Castelo-Branco, M.; Dias, J. A Bayesian Framework for Active Artificial Perception (англ.) // IEEE Transactions on Systems, IEEE Transactions on Systems, Man, and Cybernetics, Part B : journal. — 2012. — Vol. 99. — P. 1——13.
9. Ferreira, J. F.; Dias, J. M. Probabilistic Approaches to Robotic Perception (англ.). — Springer^[англ.], 2014.
10. Mekhnacha, K.; Mazer, E.; Bessière, P. The design and implementation of a Bayesian CAD modeler for robotic applications (англ.) // Advanced Robotics : journal. — 2001. — Vol. 15, no. 1. — P. 45——69. — doi:10.1163/156855301750095578.
11. Coué, C.; Pradalier, C.; Laugier, C.; Fraichard, T.; Bessière, P. Bayesian Occupancy Filtering for Multitarget Tracking: an Automotive Application (англ.) // International Journal of Robotics Research^[англ.] : journal. — 2006. — Vol. 25, no. 1. — P. 19——30. — doi:10.1177/0278364906061158.
12. Vasudevan, S.; Siegwart, R. Bayesian space conceptualization and place classification for semantic maps in mobile robotics (англ.) // Robotics and Autonomous Systems : journal. — 2008. — Vol. 56, no. 6. — P. 522——537. — doi:10.1016/j.robot.2008.03.005.
13. Perrin, X.; Chavarriaga, R.; Colas, F.; Seigwart, R.; Millan, J. Brain-coupled interaction for semi-autonomous navigation of an assistive robot (англ.) // Robotics and Autonomous Systems : journal. — 2010. — Vol. 58, no. 12. — P. 1246——1255. — doi:10.1016/j.robot.2010.05.010.
14. Rett, J.; Dias, J.; Ahuactzin, J-M. Bayesian reasoning for Laban Movement Analysis used in human-machine interaction (англ.) // Int. J. of Reasoning-based Intelligent Systems : journal. — 2010. — Vol. 2, no. 1. — P. 13——35. — doi:10.1504/IJRIS.2010.029812.
15. Möbus, C.; Eilers, M.; Garbe, H.; Zilinski, M. (2009), "Probabilistic and Empirical Grounded Modeling of Agents in (Partial) Cooperative Traffic Scenarios", in Duffy, Vincent G. (ed.), Digital Human Modeling, Lecture Notes in Computer Science, Volume 5620, Second International Conference, ICDHM 2009, San Diego, CA, USA: Springer, pp. 423–432, doi:10.1007/978-3-642-02809-0_45, ISBN 978-3-642-02808-3, Архивировано 11 июня 2018, Дата обращения: 3 октября 2017{{citation}}: Википедия:Обслуживание CS1 (location) (ссылка) Источник  (неопр.). Дата обращения: 3 октября 2017. Архивировано 11 июня 2018 года.
16. Möbus, C.; Eilers, M. (2009), "Further Steps Towards Driver Modeling according to the Bayesian Programming Approach", in Duffy, Vincent G. (ed.), Digital Human Modeling, Lecture Notes in Computer Science, Volume 5620, Second International Conference, ICDHM 2009, San Diego, CA, USA: Springer, pp. 413–422, doi:10.1007/978-3-642-02809-0_44, ISBN 978-3-642-02808-3, Архивировано 10 июня 2018, Дата обращения: 3 октября 2017{{citation}}: Википедия:Обслуживание CS1 (location) (ссылка) Источник  (неопр.). Дата обращения: 3 октября 2017. Архивировано 10 июня 2018 года.
17. Eilers, M.; Möbus, C. (2010). "Lernen eines modularen Bayesian Autonomous Driver Mixture-of-Behaviors (BAD MoB) Modells" (PDF). In Kolrep, H.; Jürgensohn, Th. (eds.). Fahrermodellierung - Zwischen kinematischen Menschmodellen und dynamisch-kognitiven Verhaltensmodellen. Fortschrittsbericht des VDI in der Reihe 22 (Mensch-Maschine-Systeme). Düsseldorf, Germany: VDI-Verlag. pp. 61–74. ISBN 978-3-18-303222-8. Архивировано из оригинала (PDF) 3 февраля 2014.
18. Möbus, C.; Eilers, M. Handbook of Research on Ambient Intelligence and Smart Environments: Trends and Perspectives (англ.) / Mastrogiovanni, F.; Chong, N.-Y.. — Hershey, Pennsylvania (USA): IGI Global publications, 2011. — P. 460—512. — ISBN 9781616928575. — doi:10.4018/978-1-61692-857-5.ch023. Архивировано 24 сентября 2015 года.
19. Eilers, M.; Möbus, C. (2011). "Learning the Relevant Percepts of Modular Hierarchical Bayesian Driver Models Using a Bayesian Information Criterion". In Duffy, V.G. (ed.). Digital Human Modeling. LNCS 6777. Heidelberg, Germany: Springer. pp. 463—472. doi:10.1007/978-3-642-21799-9_52. ISBN 978-3-642-21798-2. {{cite conference}}: |archive-url= требует |url= (справка)
20. Eilers, M.; Möbus, C. (2011). "Learning of a Bayesian Autonomous Driver Mixture-of-Behaviors (BAD-MoB) Model". In Duffy, V.G. (ed.). Advances in Applied Digital Human Modeling. LNCS 6777. Boca Raton, USA: CRC Press, Taylor & Francis Group. pp. 436—445. ISBN 978-1-4398-3511-1. Архивировано из оригинала 1 февраля 2014.
21. Le Hy, R.; Arrigoni, A.; Bessière, P.; Lebetel, O. Teaching Bayesian Behaviours to Video Game Characters (англ.) // Robotics and Autonomous Systems : journal. — 2004. — Vol. 47, no. 2—3. — P. 177——185. — doi:10.1016/j.robot.2004.03.012.
22. Synnaeve, G. Bayesian Programming and Learning for Multiplayer Video Games (англ.). — 2012. Архивировано 13 сентября 2014 года.
23. Colas, F.; Droulez, J.; Wexler, M.; Bessière, P. A unified probabilistic model of the perception of three-dimensional structure from optic flow (англ.) // Biological Cybernetics : journal. — 2008. — P. 132——154.
24. Laurens, J.; Droulez, J. Bayesian processing of vestibular information (англ.) // Biological Cybernetics. — 2007. — Vol. 96, no. 4. — P. 389——404. — doi:10.1007/s00422-006-0133-1.
25. Colas, F.; Flacher, F.; Tanner, T.; Bessière, P.; Girard, B. Bayesian models of eye movement selection with retinotopic maps (англ.) // Biological Cybernetics : journal. — 2009. — Vol. 100, no. 3. — P. 203——214. — doi:10.1007/s00422-009-0292-y.
26. Serkhane, J.; Schwartz, J-L.; Bessière, P. Building a talking baby robot A contribution to the study of speech acquisition and evolution (англ.) // Interaction Studies : journal. — 2005. — Vol. 6, no. 2. — P. 253——286. — doi:10.1075/is.6.2.06ser.
27. Moulin-Frier, C.; Laurent, R.; Bessière, P.; Schwartz, J-L.; Diard, J. Adverse conditions improve distinguishability of auditory, motor and percep-tuo-motor theories of speech perception: an exploratory Bayesian modeling study (англ.) // Language and Cognitive Processes : journal. — 2012. — Vol. 27, no. 7—8. — P. 1240——1263. — doi:10.1080/01690965.2011.645313.
28. Gilet, E.; Diard, J.; Bessière, P. Bayesian Action–Perception Computational Model: Interaction of Production and Recognition of Cursive Letters (англ.) // PLOS One : journal / Sporns, Olaf. — 2011. — Vol. 6, no. 6. — P. e20387. — doi:10.1371/journal.pone.0020387. — Bibcode: 2011PLoSO...620387G.
29. New algorithm helps machines learn as quickly as humans  (неопр.). www.gizmag.com (22 января 2016). Дата обращения: 23 января 2016. Архивировано 24 января 2016 года.
30. Zadeh, Lofti, A. Fuzzy sets (англ.) // Information and Control^[англ.] : journal. — 1965. — Vol. 8, no. 3. — P. 338——353. — doi:10.1016/S0019-9958(65)90241-X.
31. Zadeh, Lofti, A. Fuzzy logic and approximate reasoning (англ.) // Synthese^[англ.] : journal. — 1975. — Vol. 30, no. 3——4. — P. 407——428. — doi:10.1007/BF00485052.
32. Dubois, D.; Prade, H. Possibility Theory, Probability Theory and Multiple-Valued Logics: A Clarification (англ.) // Ann. Math. Artif. Intell. : journal. — 2001. — Vol. 32, no. 1——4. — P. 35——66. — doi:10.1023/A:1016740830286.
33. Poole, D. Probabilistic Horn abduction and Bayesian networks (англ.) // Artificial Intelligence. — 1993. — Vol. 64. — P. 81—129. — doi:10.1016/0004-3702(93)90061-F.
34. Poole, D. The Independent Choice Logic for modelling multiple agents under uncertainty (англ.) // Artficial Intelligence : journal. — 1997. — Vol. 94. — P. 7—56. — doi:10.1016/S0004-3702(97)00027-1.
35. Sato, T.; Kameya, Y. Parameter learning of logic programs for symbolic-statistical modeling (англ.) // Journal of Artificial Intelligence Research^[англ.] : journal. — 2001. — Vol. 15. — P. 391——454. Архивировано 12 июля 2014 года.

Литература

• 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 года., продвигающий байесовское программирование, с подробной информацией и многочисленными публикациями.  (англ.)