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

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

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

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

Формализм

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

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

${\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. Программа состоит из описания и вопроса.
2. Описание строится с использованием некоторой спецификации (${\displaystyle \pi }$), как указано программистом, и процесс идентификации или обучения для параметров, не полностью указанных в спецификации, с использованием набора данных (${\displaystyle \delta }$).
3. Спецификация строится из набора соответствующих переменных, декомпозиции и набора форм.
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)}$.^[5]

Уточнить предварительные знания ${\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^{th}}$ подмножество. Рекурсивное применение Теорема Байеса приводит к:

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

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

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

Формы

Каждая раздача ${\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\}}$на три набора: искомые переменные, известные переменные и свободные переменные.

3 переменные ${\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}}}$

где первое равенство следует из правила маргинализации, второе - из Теорема Байеса а третье соответствует второму применению маргинализации. Знаменатель выглядит как нормализационный член и может быть заменен константой. ${\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}$: двоичная переменная, false, если электронное письмо не является спамом, и true в противном случае.
2. ${\displaystyle W_{0},W_{1},\ldots ,W_{N-1}}$: ${\displaystyle N}$ бинарные переменные. ${\displaystyle W_{n}}$ верно, если ${\displaystyle n^{th}}$ Слово словаря присутствует в тексте.

Эти ${\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^{th}}$ слово в электронных письмах без спама и ${\displaystyle a_{f}}$ обозначает общее количество электронных писем без спама. По аналогии, ${\displaystyle a_{t}^{n}}$ обозначает количество появлений ${\displaystyle n^{th}}$ слово в спаме и ${\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)}$, чтобы восстановить прошлое состояние из наблюдений, сделанных до или после этого момента.

Также могут быть заданы более сложные вопросы, как показано ниже в разделе HMM.

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

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

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

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

${\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 )}$ Это приводит к чрезвычайно эффективному алгоритму, который объясняет популярность фильтров Калмана и количество их повседневных приложений.

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

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

Скрытые марковские модели (HMM) - еще одна очень популярная специализация байесовских фильтров.

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

${\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)}$ находятся

оба указаны с использованием матриц вероятностей.

• Наиболее часто задаваемый вопрос о HMM:

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

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

На этот конкретный вопрос можно ответить с помощью специального и очень эффективного алгоритма, называемого Алгоритм Витерби.

В Алгоритм Баума – Велча был разработан для HMM.

Приложения

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

С 2000 года байесовское программирование используется для разработки как робототехника приложения и модели наук о жизни.^[7]

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

В робототехнике байесовское программирование применялось к автономная робототехника,^{[8][9][10][11][12]} робот CAD системы,^[13] продвинутые системы помощи водителю,^[14] роботизированная рука контроль, мобильная робототехника,^[15][16] взаимодействие человека и робота,^[17] взаимодействие человека и автомобиля (байесовские модели автономных водителей)^{[18][19][20][21][22]} видео игра программирование и обучение аватаров ^[23] и стратегические игры в реальном времени (AI).^[24]

Науки о жизни

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

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

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

Теории возможностей

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

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

Защита вероятности в основном основана на Теорема Кокса, который исходит из четырех постулатов о рациональном мышлении в условиях неопределенности. Это демонстрирует, что единственной математической структурой, удовлетворяющей этим постулатам, является теория вероятностей. Аргумент состоит в том, что любой подход, отличный от вероятностного, обязательно нарушает один из этих постулатов и ценность этого нарушения.

Вероятностное программирование

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

Расширенные классические языки программирования включают логические языки, предложенные в Вероятностное похищение рога,^[35] Логика независимого выбора,^[36] ПРИЗМА,^[37] и ProbLog, который предлагает расширение Prolog.

Это также может быть расширение функциональные языки программирования (по сути Лисп и Схема ), например IBAL или CHURCH. Базовые языки программирования могут быть объектно-ориентированными, как в BLOG и FACTORIE, или более стандартными, как в CES и FIGARO.^[38]

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

Точное сравнение между семантика а сила выражения байесовского и вероятностного программирования - открытый вопрос.

Смотрите также

• Математический портал

• Правило Байеса
• Байесовский вывод
• Байесовская вероятность
• Байесовская фильтрация спама
• Распространение веры
• Теорема Кокса
• Алгоритм ожидания-максимизации
• Факторный график
• Графическая модель
• Скрытая марковская модель
• Жемчужина Иудеи
• Фильтр Калмана
• Наивный байесовский классификатор
• Пьер-Симон де Лаплас
• Вероятностная логика
• Вероятностный язык программирования
• Субъективная логика

Рекомендации

1. Джейнс, Э. Т. (10 апреля 2003 г.). Теория вероятностей: логика науки. Издательство Кембриджского университета. ISBN  978-1-139-43516-1.
2. Бессьер, Пьер; Мазер, Эммануэль; Мануэль Ахуакцин, Хуан; Мехнача, Камель (20 декабря 2013 г.). Байесовское программирование. CRC Press. ISBN  978-1-4398-8032-6.
3. «Графы выражений: объединяющие факторные графы и сети сумм-произведений» (PDF). bcf.usc.edu.
4. «Вероятностное моделирование и байесовский анализ» (PDF). ocw.mit.edu.
5. «Байесовские сети» (PDF). cs.brandeis.edu.
6. Кальман, Р. Э. (1960). «Новый подход к задачам линейной фильтрации и прогнозирования». Журнал фундаментальной инженерии. 82: 33–45. Дои:10.1115/1.3662552. S2CID  1242324.
7. Бессьер, Пьер; Ложье, Кристиан; Зигварт, Роланд (15 мая 2008 г.). Вероятностное мышление и принятие решений в сенсомоторных системах. Springer Science & Business Media. ISBN  978-3-540-79006-8.
8. Lebeltel, O .; Bessière, P .; Diard, J .; Мазер, Э. (2004). «Байесовское программирование роботов» (PDF). Продвинутая робототехника. 16 (1): 49–79. Дои:10.1023 / b: auro.0000008671.38949.43. S2CID  18768468.
9. Diard, J .; Gilet, E .; Симонин, Э .; Бессьер, П. (2010). «Пошаговое обучение байесовским сенсомоторным моделям: от низкоуровневого поведения до крупномасштабной структуры окружающей среды» (PDF). Связь Наука. 22 (4): 291–312. Bibcode:2010ConSc..22..291D. Дои:10.1080/09540091003682561. S2CID  216035458.
10. Pradalier, C .; Hermosillo, J .; Koike, C .; Braillon, C .; Bessière, P .; Ложье, К. (2005). «CyCab: робот, похожий на машину, автономно и безопасно перемещающийся среди пешеходов». Робототехника и автономные системы. 50 (1): 51–68. CiteSeerX  10.1.1.219.69. Дои:10.1016 / j.robot.2004.10.002.
11. Ferreira, J .; Lobo, J .; Bessière, P .; Castelo-Branco, M .; Диас, Дж. (2012). «Байесовская структура для активного искусственного восприятия» (PDF). Транзакции IEEE по системам, человеку и кибернетике - Часть B: Кибернетика. 99 (2): 1–13. Дои:10.1109 / TSMCB.2012.2214477. PMID  23014760. S2CID  1808051.
12. Ferreira, J. F .; Диас, Дж. М. (2014). Вероятностные подходы к восприятию роботов. Springer. ISBN  978-3-319-02005-1.
13. Мехнача, К .; Mazer, E .; Бессьер, П. (2001). «Разработка и реализация байесовского САПР-моделирования для робототехнических приложений». Продвинутая робототехника. 15 (1): 45–69. CiteSeerX  10.1.1.552.3126. Дои:10.1163/156855301750095578. S2CID  7920387.
14. Coué, C .; Pradalier, C .; Laugier, C .; Fraichard, T .; Бессьер, П. (2006). «Байесовская фильтрация занятости для отслеживания нескольких целей: автомобильное приложение» (PDF). Международный журнал исследований робототехники. 25 (1): 19–30. Дои:10.1177/0278364906061158. S2CID  13874685.
15. Васудеван, S .; Сигварт, Р. (2008). «Байесовская концептуализация пространства и классификация мест для семантических карт в мобильной робототехнике». Робототехника и автономные системы. 56 (6): 522–537. CiteSeerX  10.1.1.149.4189. Дои:10.1016 / j.robot.2008.03.005.
16. Perrin, X .; Chavarriaga, R .; Colas, F .; Seigwart, R .; Миллан, Дж. (2010). «Мозговое взаимодействие для полуавтономной навигации вспомогательного робота». Робототехника и автономные системы. 58 (12): 1246–1255. Дои:10.1016 / j.robot.2010.05.010.
17. Rett, J .; Dias, J .; Ахуакцин, Дж.М. (2010). «Байесовское рассуждение для анализа движения Лабана, используемого в человеко-машинном взаимодействии». Международный журнал интеллектуальных систем на основе рассуждений. 2 (1): 13–35. CiteSeerX  10.1.1.379.6216. Дои:10.1504 / IJRIS.2010.029812.
18. Möbus, C .; Эйлерс, М .; Garbe, H .; Зилински, М. (2009), «Вероятностное и эмпирическое моделирование агентов в (частичных) совместных сценариях движения», Даффи, Винсент Г. (ред.), Цифровое моделирование человека (PDF), Конспект лекций по информатике, том 5620, 5620, Вторая международная конференция, ICDHM 2009, Сан-Диего, Калифорния, США: Springer, стр. 423–432, Дои:10.1007/978-3-642-02809-0_45, ISBN  978-3-642-02808-3
19. Möbus, C .; Эйлерс, М. (2009), «Дальнейшие шаги к моделированию драйверов в соответствии с подходом байесовского программирования», в Даффи, Винсент Г. (ред.), Цифровое моделирование человека, Конспект лекций по информатике, том 5620, 5620, Вторая международная конференция, ICDHM 2009, Сан-Диего, Калифорния, США: Springer, стр. 413–422, CiteSeerX  10.1.1.319.2067, Дои:10.1007/978-3-642-02809-0_44, ISBN  978-3-642-02808-3
20. Эйлерс, М .; Мёбус, К. (2010). "Lernen eines modularen Байесовские автономные модели поведения драйверов (BAD MoB)" (PDF). In Kolrep, H .; Юргенсон, Т. (ред.). Fahrermodellierung - Zwischen kinematischen Menschmodellen und Dynamisch-kognitiven Verhaltensmodellen. Fortschrittsbericht des VDI in der Reihe 22 (Mensch-Maschine-Systeme). Дюссельдорф, Германия: VDI-Verlag. С. 61–74. ISBN  978-3-18-303222-8.
21. Эйлерс, М .; Мёбус, К. (2011). «Изучение соответствующих представлений о модульных иерархических байесовских моделях драйверов с использованием байесовского информационного критерия». В Даффи В. (ред.). Цифровое моделирование человека. LNCS 6777. Гейдельберг, Германия: Springer. С. 463–472. Дои:10.1007/978-3-642-21799-9_52. ISBN  978-3-642-21798-2.
22. Эйлерс, М .; Мёбус, К. (2011). «Изучение байесовской модели автономного поведения драйверов (BAD-MoB)». В Даффи В. (ред.). Достижения в прикладном цифровом моделировании человека. LNCS 6777. Бока-Ратон, США: CRC Press, Taylor & Francis Group. С. 436–445. ISBN  978-1-4398-3511-1.
23. Le Hy, R .; Arrigoni, A .; Bessière, P .; Лебетель, О. (2004). «Обучение байесовскому поведению персонажей видеоигр» (PDF). Робототехника и автономные системы. 47 (2–3): 177–185. Дои:10.1016 / j.robot.2004.03.012.
24. Синнаев, Г. (2012). Байесовское программирование и обучение для многопользовательских видеоигр (PDF).
25. Colas, F .; Droulez, J .; Wexler, M .; Бессьер, П. (2008). «Единая вероятностная модель восприятия трехмерной структуры из оптического потока». Биологическая кибернетика. 97 (5–6): 461–77. CiteSeerX  10.1.1.215.1491. Дои:10.1007 / s00422-007-0183-z. PMID  17987312. S2CID  215821150.
26. Laurens, J .; Дроулез Дж. (2007). «Байесовская обработка вестибулярной информации». Биологическая кибернетика. 96 (4): 389–404. Дои:10.1007 / s00422-006-0133-1. PMID  17146661. S2CID  18138027.
27. Colas, F .; Flacher, F .; Таннер, Т .; Bessière, P .; Жирар, Б. (2009). «Байесовские модели выбора движения глаз с ретинотопными картами» (PDF). Биологическая кибернетика. 100 (3): 203–214. Дои:10.1007 / s00422-009-0292-y. PMID  19212780. S2CID  5906668.
28. Serkhane, J .; Schwartz, J-L .; Бессьер, П. (2005). «Создание говорящего робота-младенца. Вклад в изучение развития и развития речи» (PDF). Исследования взаимодействия. 6 (2): 253–286. Дои:10.1075 / is.6.2.06ser.
29. Moulin-Frier, C .; Laurent, R .; Bessière, P .; Schwartz, J-L .; Диард, Дж. (2012). «Неблагоприятные условия улучшают различимость слуховых, моторных и перцептуомоторных теорий восприятия речи: исследовательское исследование с использованием байесовского моделирования» (PDF). Язык и когнитивные процессы. 27 (7–8): 1240–1263. Дои:10.1080/01690965.2011.645313. S2CID  55504109.
30. Gilet, E .; Diard, J .; Бессьер, П. (2011). Sporns, Олаф (ред.). "Байесовская вычислительная модель действия и восприятия: взаимодействие производства и распознавания курсивных букв". PLOS ONE. 6 (6): e20387. Bibcode:2011PLoSO ... 620387G. Дои:10.1371 / journal.pone.0020387. ЧВК  3106017. PMID  21674043.
31. «Новый алгоритм помогает машинам учиться так же быстро, как люди». www.gizmag.com. 2016-01-22. Получено 2016-01-23.
32. Заде, Лофти, А. (1965). «Нечеткие множества». Информация и контроль. 8 (3): 338–353. Дои:10.1016 / S0019-9958 (65) 90241-X.
33. Заде, Лофти, А. (1975). «Нечеткая логика и приблизительные рассуждения». Синтез. 30 (3–4): 407–428. Дои:10.1007 / BF00485052. S2CID  46975216.
34. Дюбуа, Д .; Прад, Х. (2001). "Possibility Theory, Probability Theory and Multiple-Valued Logics: A Clarification" (PDF). Анна. Математика. Артиф. Intell. 32 (1–4): 35–66. Дои:10.1023/A:1016740830286. S2CID  10271476.
35. Poole, D. (1993). "Probabilistic Horn abduction and Bayesian networks". Искусственный интеллект. 64: 81–129. Дои:10.1016/0004-3702(93)90061-F.
36. Poole, D. (1997). "The Independent Choice Logic for modelling multiple agents under uncertainty". Искусственный интеллект. 94 (1–2): 7–56. Дои:10.1016/S0004-3702(97)00027-1.
37. Сато, Т .; Kameya, Y. (2001). "Parameter learning of logic programs for symbolic-statistical modeling" (PDF). Журнал исследований искусственного интеллекта. 15 (2001): 391–454. arXiv:1106.1797. Bibcode:2011arXiv1106.1797S. Дои:10.1613/jair.912. S2CID  7857569. Архивировано из оригинал (PDF) в 2014-07-12. Получено 2015-10-18.
38. figaro на GitHub

дальнейшее чтение

• Kamel Mekhnacha (2013). Bayesian Programming. Чепмен и Холл / CRC. Дои:10.1201/b16111. ISBN  978-1-4398-8032-6.

внешняя ссылка

• A companion site to the Bayesian programming book where to download ProBT an inference engine dedicated to Bayesian programming.^{[постоянная мертвая ссылка ]}
• В Bayesian-programming.org site for the promotion of Bayesian programming with detailed information and numerous publications.