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




Главная
Новости
Статьи
Строительство
Ремонт
Дизайн и интерьер
Строительная теплофизика
Прочность сплавов
Основания и фундаменты
Осадочные породы
Прочность дорог
Минералогия глин
Краны башенные
Справочник токаря
Цементный бетон




05.03.2021


03.03.2021


01.03.2021


27.02.2021


27.02.2021


27.02.2021


23.02.2021





Яндекс.Метрика
         » » Байесовское программирование

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

19.12.2020


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

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

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

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

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

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

Program { Description { Specification ( π ) { Variables Decomposition Forms Identification (based on  δ ) Question {displaystyle { ext{Program}}{egin{cases}{ ext{Description}}{egin{cases}{ ext{Specification}}(pi ){egin{cases}{ ext{Variables}}{ ext{Decomposition}}{ ext{Forms}}end{cases}}{ ext{Identification (based on }}delta )end{cases}}{ ext{Question}}end{cases}}}
  • Программа строится из описания (англ. description) и вопроса (англ. question).
  • Описание строится с помощью какого-либо определения ( π {displaystyle pi } , англ. specification), заданного программистом, и идентификации (англ. identification) или процесса обучения для параметров, не полностью описанных в определении, с применением набора данных ( δ {displaystyle delta } ).
  • Определение строится из набора значимых переменных (англ. variables), декомпозиции (англ. decomposition) и набора форм (англ. forms).
  • Формы являются или параметрическими формами, или вопросами к другим байесовским программам.
  • Вопрос задает распределение вероятности, которое необходимо вычислить.
  • Описание

    Описание задает эффективный метод вычисления совместного распределения вероятности набора переменных { X 1 , X 2 , ⋯ , X N } {displaystyle left{X_{1},X_{2},cdots ,X_{N} ight}} для заданного набора экспериментальных данных δ {displaystyle delta } и некоторого определения π {displaystyle pi } . Это совместное распределение обозначается как P ( X 1 ∧ X 2 ∧ ⋯ ∧ X N ∣ δ ∧ π ) {displaystyle Pleft(X_{1}wedge X_{2}wedge cdots wedge X_{N}mid delta wedge pi ight)} .

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

  • Определить набор значимых переменных { X 1 , X 2 , ⋯ , X N } {displaystyle left{X_{1},X_{2},cdots ,X_{N} ight}} , на которых задано совместное распределение вероятности.
  • Разложить совместное распределение (разбить его на подходящие независимые или условные вероятности).
  • Определить формы каждого из этих распределений (например, для каждой переменной выбрать одно из перечня распределений вероятности).
  • Декомпозиция

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

    P ( X 1 ∧ X 2 ∧ ⋯ ∧ X N ∣ δ ∧ π ) = P ( L 1 ∧ ⋯ ∧ L K ∣ δ ∧ π ) = P ( L 1 ∣ δ ∧ π ) × P ( L 2 ∣ L 1 ∧ δ ∧ π ) × ⋯ × P ( L K ∣ L K − 1 ∧ ⋯ ∧ L 1 ∧ δ ∧ π ) {displaystyle {egin{aligned}&Pleft(X_{1}wedge X_{2}wedge cdots wedge X_{N}mid delta wedge pi ight)={}&Pleft(L_{1}wedge cdots wedge L_{K}mid delta wedge pi ight)={}&Pleft(L_{1}mid delta wedge pi ight) imes Pleft(L_{2}mid L_{1}wedge delta wedge pi ight) imes cdots imes Pleft(L_{K}mid L_{K-1}wedge cdots wedge L_{1}wedge delta wedge pi ight)end{aligned}}}

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

    P ( L k ∣ L k − 1 ∧ ⋯ ∧ L 1 ∧ δ ∧ π ) = P ( L k ∣ R k ∧ δ ∧ π ) {displaystyle Pleft(L_{k}mid L_{k-1}wedge cdots wedge L_{1}wedge delta wedge pi ight)=Pleft(L_{k}mid R_{k}wedge delta wedge pi ight)}

    Получаем

    P ( X 1 ∧ X 2 ∧ ⋯ ∧ X N ∣ δ ∧ π ) = P ( L 1 ∣ δ ∧ π ) × P ( L 2 ∣ R 2 ∧ δ ∧ π ) × ⋯ × P ( L K ∣ R K ∧ δ ∧ π ) {displaystyle {egin{aligned}&Pleft(X_{1}wedge X_{2}wedge cdots wedge X_{N}mid delta wedge pi ight)={}&Pleft(L_{1}mid delta wedge pi ight) imes Pleft(L_{2}mid R_{2}wedge delta wedge pi ight) imes cdots imes Pleft(L_{K}mid R_{K}wedge delta wedge pi ight)end{aligned}}}

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

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

    Формы

    Каждое распределение P ( L k ∣ R k ∧ δ ∧ π ) {displaystyle Pleft(L_{k}mid R_{k}wedge delta wedge pi ight)} , встречающееся в произведении, далее связывается или с параметрической формой (то есть функцией f μ ( L k ) {displaystyle f_{mu }left(L_{k} ight)} ), или с вопросом к другой байсовской программе P ( L k ∣ R k ∧ δ ∧ π ) = P ( L ∣ R ∧ δ ^ ∧ π ^ ) {displaystyle Pleft(L_{k}mid R_{k}wedge delta wedge pi ight)=Pleft(Lmid Rwedge {widehat {delta }}wedge {widehat {pi }} ight)} .

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

    Важная особенность байесовского программирования — это способность использовать вопросы к другим байесовским программам как составляющую определения новой байесовской программы. P ( L k ∣ R k ∧ δ ∧ π ) {displaystyle Pleft(L_{k}mid R_{k}wedge delta wedge pi ight)} получается выводом, произведенным другой байесовской программой, заданной определением π ^ {displaystyle {widehat {pi }}} и данными δ ^ {displaystyle {widehat {delta }}} . Это похоже на вызов подпрограммы в классическом программировании, и предоставляет простой способ построения иерархических моделей.

    Вопрос

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

    Три переменные S e a r c h e d {displaystyle Searched} , K n o w n {displaystyle Known} и F r e e {displaystyle Free} определяются как конъюнкция переменных, принадлежащих к этим множествам.

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

    P ( S e a r c h e d ∣ Known ∧ δ ∧ π ) {displaystyle Pleft(Searchedmid { ext{Known}}wedge delta wedge pi ight)}

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

    P ( Searched ∣ Known ∧ δ ∧ π ) {displaystyle Pleft({ ext{Searched}}mid { ext{Known}}wedge delta wedge pi ight)}

    Вывод

    Для заданного совместного распределения P ( X 1 ∧ X 2 ∧ ⋯ ∧ X N ∣ δ ∧ π ) {displaystyle Pleft(X_{1}wedge X_{2}wedge cdots wedge X_{N}mid delta wedge pi ight)} всегда возможно вычислить любой вопрос, применяя следующий общий вывод:

    P ( Searched ∣ Known ∧ δ ∧ π ) = ∑ Free [ P ( Searched ∧ Free ∣ Known ∧ δ ∧ π ) ] = ∑ Free [ P ( Searched ∧ Free ∧ Known ∣ δ ∧ π ) ] P ( Known ∣ δ ∧ π ) = ∑ Free [ P ( Searched ∧ Free ∧ Known ∣ δ ∧ π ) ] ∑ Free ∧ Searched [ P ( Searched ∧ Free ∧ Known ∣ δ ∧ π ) ] = 1 Z × ∑ Free [ P ( Searched ∧ Free ∧ Known ∣ δ ∧ π ) ] {displaystyle {egin{aligned}&Pleft({ ext{Searched}}mid { ext{Known}}wedge delta wedge pi ight)={}&sum _{ ext{Free}}left[Pleft({ ext{Searched}}wedge { ext{Free}}mid { ext{Known}}wedge delta wedge pi ight) ight]={}&{frac {displaystyle sum _{ ext{Free}}left[Pleft({ ext{Searched}}wedge { ext{Free}}wedge { ext{Known}}mid delta wedge pi ight) ight]}{displaystyle Pleft({ ext{Known}}mid delta wedge pi ight)}}={}&{frac {displaystyle sum _{ ext{Free}}left[Pleft({ ext{Searched}}wedge { ext{Free}}wedge { ext{Known}}mid delta wedge pi ight) ight]}{displaystyle sum _{{ ext{Free}}wedge { ext{Searched}}}left[Pleft({ ext{Searched}}wedge { ext{Free}}wedge { ext{Known}}mid delta wedge pi ight) ight]}}={}&{frac {1}{Z}} imes sum _{ ext{Free}}left[Pleft({ ext{Searched}}wedge { ext{Free}}wedge { ext{Known}}mid delta wedge pi ight) ight]end{aligned}}}

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

    Теоретически это позволяет решать любые задачи байесовского вывода. Однако на практике почти во всех случаях затраты на исчерпывающее и точное вычисление P ( Searched ∣ Known ∧ δ ∧ π ) {displaystyle Pleft({ ext{Searched}}mid { ext{Known}}wedge delta wedge pi ight)} оказываются слишком большими.

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

    P ( Searched ∣ Known ∧ δ ∧ π ) = 1 Z ∑ Free [ ∏ k = 1 K [ P ( L i ∣ K i ∧ π ) ] ] {displaystyle {egin{aligned}&Pleft({ ext{Searched}}mid { ext{Known}}wedge delta wedge pi ight)={}&{frac {1}{Z}}sum _{ ext{Free}}left[prod _{k=1}^{K}left[Pleft(L_{i}mid K_{i}wedge pi ight) ight] ight]end{aligned}}}

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

    Пример

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

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

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

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

    Переменные

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

  • S p a m {displaystyle Spam} : двоичная переменная, ложь, если электронное письмо не является спамом, и истина в противном случае.
  • W 0 , W 1 , … , W N − 1 {displaystyle W_{0},W_{1},ldots ,W_{N-1}} : N {displaystyle N} двоичных переменных. W n {displaystyle W_{n}} является истиной, если n {displaystyle n} -ое слово словаря присутствует в тексте.
  • Эти N + 1 {displaystyle N+1} двоичных переменных суммируют всю информацию об электронной почте.

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

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

    P ( Spam ∧ W 0 ∧ ⋯ ∧ W N − 1 ) = P ( Spam ) × P ( W 0 ∣ Spam ) × P ( W 1 ∣ Spam ∧ W 0 ) × ⋯ × P ( W N − 1 ∣ Spam ∧ W 0 ∧ ⋯ ∧ W N − 2 ) {displaystyle {egin{aligned}&P({ ext{Spam}}wedge W_{0}wedge cdots wedge W_{N-1})={}&P({ ext{Spam}}) imes P(W_{0}mid { ext{Spam}}) imes P(W_{1}mid { ext{Spam}}wedge W_{0})& imes cdots & imes Pleft(W_{N-1}mid { ext{Spam}}wedge W_{0}wedge cdots wedge W_{N-2} ight)end{aligned}}}

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

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

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

    P ( W 1 ∣ Spam ∧ W 0 ) = P ( W 1 ∣ Spam ) {displaystyle P(W_{1}mid { ext{Spam}}land W_{0})=P(W_{1}mid { ext{Spam}})}

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

    P ( Spam ∧ W 0 ∧ … ∧ W N − 1 ) = P ( Spam ) ∏ n = 0 N − 1 [ P ( W n ∣ Spam ) ] {displaystyle P({ ext{Spam}}land W_{0}land ldots land W_{N-1})=P({ ext{Spam}})prod _{n=0}^{N-1}[P(W_{n}mid { ext{Spam}})]}

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

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

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

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

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

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

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

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

    Вопрос

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

    P ( Spam ∣ w 0 ∧ ⋯ ∧ w N − 1 ) {displaystyle P({ ext{Spam}}mid w_{0}wedge cdots wedge w_{N-1})}

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

    P ( Spam ∣ w 0 ∧ ⋯ ∧ w N − 1 ) = P ( Spam ) ∏ n = 0 N − 1 [ P ( w n ∣ Spam ) ] ∑ Spam [ P ( Spam ) ∏ n = 0 N − 1 [ P ( w n ∣ Spam ) ] ] {displaystyle {egin{aligned}&P({ ext{Spam}}mid w_{0}wedge cdots wedge w_{N-1})={}&{frac {displaystyle P({ ext{Spam}})prod _{n=0}^{N-1}[P(w_{n}mid { ext{Spam}})]}{displaystyle sum _{ ext{Spam}}[P({ ext{Spam}})prod _{n=0}^{N-1}[P(w_{n}mid { ext{Spam}})]]}}end{aligned}}}

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

    P ( [ Spam = true ] ∣ w 0 ∧ ⋯ ∧ w N − 1 ) P ( [ Spam = false ] ∣ w 0 ∧ ⋯ ∧ w N − 1 ) = P ( [ Spam = true ] ) P ( [ Spam = false ] ) × ∏ n = 0 N − 1 [ P ( w n ∣ [ Spam = true ] ) P ( w n ∣ [ Spam = false ] ) ] {displaystyle {egin{aligned}&{frac {P([{ ext{Spam}}={ ext{true}}]mid w_{0}wedge cdots wedge w_{N-1})}{P([{ ext{Spam}}={ ext{false}}]mid w_{0}wedge cdots wedge w_{N-1})}}={}&{frac {P([{ ext{Spam}}={ ext{true}}])}{P([{ ext{Spam}}={ ext{false}}])}} imes prod _{n=0}^{N-1}left[{frac {P(w_{n}mid [{ ext{Spam}}={ ext{true}}])}{P(w_{n}mid [{ ext{Spam}}={ ext{false}}])}} ight]end{aligned}}}

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

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

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

    Pr { D s { S p ( π ) { V a : Spam , W 0 , W 1 … W N − 1 D c : { P ( Spam ∧ W 0 ∧ … ∧ W n ∧ … ∧ W N − 1 ) = P ( Spam ) ∏ n = 0 N − 1 P ( W n ∣ Spam ) F o : { P ( Spam ) : { P ( [ Spam = false ] ) = 0.25 P ( [ Spam = true ] ) = 0.75 P ( W n ∣ Spam ) : { P ( W n ∣ [ Spam = false ] ) = 1 + a f n 2 + a f P ( W n ∣ [ Spam = true ] ) = 1 + a t n 2 + a t Identification (based on  δ ) Q u : P ( Spam ∣ w 0 ∧ … ∧ w n ∧ … ∧ w N − 1 ) {displaystyle Pr {egin{cases}Ds{egin{cases}Sp(pi ){egin{cases}Va:{ ext{Spam}},W_{0},W_{1}ldots W_{N-1}Dc:{egin{cases}P({ ext{Spam}}land W_{0}land ldots land W_{n}land ldots land W_{N-1})=P({ ext{Spam}})prod _{n=0}^{N-1}P(W_{n}mid { ext{Spam}})end{cases}}Fo:{egin{cases}P({ ext{Spam}}):{egin{cases}P([{ ext{Spam}}={ ext{false}}])=0.25P([{ ext{Spam}}={ ext{true}}])=0.75end{cases}}P(W_{n}mid { ext{Spam}}):{egin{cases}P(W_{n}mid [{ ext{Spam}}={ ext{false}}])={frac {1+a_{f}^{n}}{2+a_{f}}}P(W_{n}mid [{ ext{Spam}}={ ext{true}}])={frac {1+a_{t}^{n}}{2+a_{t}}}end{cases}}end{cases}}end{cases}}{ ext{Identification (based on }}delta )end{cases}}Qu:P({ ext{Spam}}mid w_{0}land ldots land w_{n}land ldots land w_{N-1})end{cases}}}

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

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

    Переменные

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

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

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

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

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

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

    Вопрос

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

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

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

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

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

    P ( S t | O 0 ∧ ⋯ ∧ O t ) = P ( O t | S t ) × ∑ S t − 1 [ P ( S t | S t − 1 ) × P ( S t − 1 | O 0 ∧ ⋯ ∧ O t − 1 ) ] {displaystyle {egin{array}{ll}&Pleft(S^{t}|O^{0}wedge cdots wedge O^{t} ight)=&Pleft(O^{t}|S^{t} ight) imes sum _{S^{t-1}}left[Pleft(S^{t}|S^{t-1} ight) imes Pleft(S^{t-1}|O^{0}wedge cdots wedge O^{t-1} ight) ight]end{array}}}

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

    • В течение фазы предвидения состояние предсказывается с помощью динамической модели и оценки состояния в предыдущий момент:
    P ( S t | O 0 ∧ ⋯ ∧ O t − 1 ) = ∑ S t − 1 [ P ( S t | S t − 1 ) × P ( S t − 1 | O 0 ∧ ⋯ ∧ O t − 1 ) ] {displaystyle {egin{array}{ll}&Pleft(S^{t}|O^{0}wedge cdots wedge O^{t-1} ight)=&sum _{S^{t-1}}left[Pleft(S^{t}|S^{t-1} ight) imes Pleft(S^{t-1}|O^{0}wedge cdots wedge O^{t-1} ight) ight]end{array}}}
    • В течение фазы оценки предсказание или подтверждается, или признается недействительным с помощью последнего наблюдения:
    P ( S t ∣ O 0 ∧ ⋯ ∧ O t ) = P ( O t ∣ S t ) × P ( S t | O 0 ∧ ⋯ ∧ O t − 1 ) {displaystyle {egin{aligned}&Pleft(S^{t}mid O^{0}wedge cdots wedge O^{t} ight)={}&Pleft(O^{t}mid S^{t} ight) imes Pleft(S^{t}|O^{0}wedge cdots wedge O^{t-1} ight)end{aligned}}}

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

    P r { D s { S p ( π ) { V a : S 0 , ⋯ , S T , O 0 , ⋯ , O T D c : { P ( S 0 ∧ ⋯ ∧ S T ∧ O 0 ∧ ⋯ ∧ O T | π ) = P ( S 0 ∧ O 0 ) × ∏ t = 1 T [ P ( S t | S t − 1 ) × P ( O t | S t ) ] F o : { P ( S 0 ∧ O 0 ) P ( S t | S t − 1 ) P ( O t | S t ) I d Q u : { P ( S t + k | O 0 ∧ ⋯ ∧ O t ) ( k = 0 ) ≡ Filtering ( k > 0 ) ≡ Prediction ( k < 0 ) ≡ Smoothing {displaystyle Pr{egin{cases}Ds{egin{cases}Sp(pi ){egin{cases}Va:S^{0},cdots ,S^{T},O^{0},cdots ,O^{T}Dc:{egin{cases}&Pleft(S^{0}wedge cdots wedge S^{T}wedge O^{0}wedge cdots wedge O^{T}|pi ight)=&Pleft(S^{0}wedge O^{0} ight) imes prod _{t=1}^{T}left[Pleft(S^{t}|S^{t-1} ight) imes Pleft(O^{t}|S^{t} ight) ight]end{cases}}Fo:{egin{cases}Pleft(S^{0}wedge O^{0} ight)Pleft(S^{t}|S^{t-1} ight)Pleft(O^{t}|S^{t} ight)end{cases}}end{cases}}Idend{cases}}Qu:{egin{cases}{egin{array}{l}Pleft(S^{t+k}|O^{0}wedge cdots wedge O^{t} ight)left(k=0 ight)equiv { ext{Filtering}}left(k>0 ight)equiv { ext{Prediction}}left(k<0 ight)equiv { ext{Smoothing}}end{array}}end{cases}}end{cases}}}

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

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

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

    P r { D s { S p ( π ) { V a : S 0 , ⋯ , S T , O 0 , ⋯ , O T D c : { P ( S 0 ∧ ⋯ ∧ O T | π ) = [ P ( S 0 ∧ O 0 | π ) ∏ t = 1 T [ P ( S t | S t − 1 ∧ π ) × P ( O t | S t ∧ π ) ] ] F o : { P ( S t ∣ S t − 1 ∧ π ) ≡ G ( S t , A ∙ S t − 1 , Q ) P ( O t ∣ S t ∧ π ) ≡ G ( O t , H ∙ S t , R ) I d Q u : P ( S T ∣ O 0 ∧ ⋯ ∧ O T ∧ π ) {displaystyle Pr{egin{cases}Ds{egin{cases}Sp(pi ){egin{cases}Va:S^{0},cdots ,S^{T},O^{0},cdots ,O^{T}Dc:{egin{cases}&Pleft(S^{0}wedge cdots wedge O^{T}|pi ight)=&left[{egin{array}{c}Pleft(S^{0}wedge O^{0}|pi ight)prod _{t=1}^{T}left[Pleft(S^{t}|S^{t-1}wedge pi ight) imes Pleft(O^{t}|S^{t}wedge pi ight) ight]end{array}} ight]end{cases}}Fo:{egin{cases}Pleft(S^{t}mid S^{t-1}wedge pi ight)equiv Gleft(S^{t},Aullet S^{t-1},Q ight)Pleft(O^{t}mid S^{t}wedge pi ight)equiv Gleft(O^{t},Hullet S^{t},R ight)end{cases}}end{cases}}Idend{cases}}Qu:Pleft(S^{T}mid O^{0}wedge cdots wedge O^{T}wedge pi ight)end{cases}}}
    • Переменные являются непрерывными.
    • Модели перехода P ( S t ∣ S t − 1 ∧ π ) {displaystyle P(S^{t}mid S^{t-1}wedge pi )} и наблюдения P ( O t ∣ S t ∧ π ) {displaystyle P(O^{t}mid S^{t}wedge pi )} определяются с помощью распределения Гаусса, в котором средние значения являются линейными функциями условных переменных.

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

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

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

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

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

    Pr { D s { S p ( π ) { V a : S 0 , … , S T , O 0 , … , O T D c : { P ( S 0 ∧ ⋯ ∧ O T ∣ π ) = [ P ( S 0 ∧ O 0 ∣ π ) ∏ t = 1 T [ P ( S t ∣ S t − 1 ∧ π ) × P ( O t ∣ S t ∧ π ) ] ] F o : { P ( S 0 ∧ O 0 ∣ π ) ≡ Matrix P ( S t ∣ S t − 1 ∧ π ) ≡ Matrix P ( O t ∣ S t ∧ π ) ≡ Matrix I d Q u : max S 1 ∧ ⋯ ∧ S T − 1 [ P ( S 1 ∧ ⋯ ∧ S T − 1 ∣ S T ∧ O 0 ∧ ⋯ ∧ O T ∧ π ) ] {displaystyle Pr {egin{cases}Ds{egin{cases}Sp(pi ){egin{cases}Va:S^{0},ldots ,S^{T},O^{0},ldots ,O^{T}Dc:{egin{cases}&Pleft(S^{0}wedge cdots wedge O^{T}mid pi ight)=&left[{egin{array}{c}Pleft(S^{0}wedge O^{0}mid pi ight)prod _{t=1}^{T}left[Pleft(S^{t}mid S^{t-1}wedge pi ight) imes Pleft(O^{t}mid S^{t}wedge pi ight) ight]end{array}} ight]end{cases}}Fo:{egin{cases}Pleft(S^{0}wedge O^{0}mid pi ight)equiv { ext{Matrix}}Pleft(S^{t}mid S^{t-1}wedge pi ight)equiv { ext{Matrix}}Pleft(O^{t}mid S^{t}wedge pi ight)equiv { ext{Matrix}}end{cases}}end{cases}}Idend{cases}}Qu:max _{S^{1}wedge cdots wedge S^{T-1}}left[Pleft(S^{1}wedge cdots wedge S^{T-1}mid S^{T}wedge O^{0}wedge cdots wedge O^{T}wedge pi ight) ight]end{cases}}}
    • Переменные считаются дискретными.
    • Модели перехода P ( S t ∣ S t − 1 ∧ π ) {displaystyle Pleft(S^{t}mid S^{t-1}wedge pi ight)} и наблюдения P ( O t ∣ S t ∧ π ) {displaystyle Pleft(O^{t}mid S^{t}wedge pi ight)} задаются с помощью матриц вероятностей.
    • Вопрос, который чаще всего задают скрытым марковским моделям:
    max S 1 ∧ ⋯ ∧ S T − 1 [ P ( S 1 ∧ ⋯ ∧ S T − 1 ∣ S T ∧ O 0 ∧ ⋯ ∧ O T ∧ π ) ] {displaystyle max _{S^{1}wedge cdots wedge S^{T-1}}left[Pleft(S^{1}wedge cdots wedge S^{T-1}mid S^{T}wedge O^{0}wedge cdots wedge O^{T}wedge pi ight) ight]}

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

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

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

    Применение

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

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

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

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

    Науки о жизни

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

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

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

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

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

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

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

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

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

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

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

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

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