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

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

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

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

Формализм

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

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

{ displaystyle { text {Program}} { begin {cases} { text {Description}} { begin {cases} { text {Specification}} ( pi) { begin {cases} { text { Переменные}} { text {Decomposition}} { text {Forms}} end {case}} { text {Идентификация (на основе}} delta) end {cases}} { text {Вопрос}} end {case}}}

Программа состоит из описания и вопроса.
Описание строится с использованием некоторой спецификации ( ${ displaystyle pi}$ ), как указано программистом, и процесс идентификации или обучения для параметров, не полностью указанных в спецификации, с использованием набора данных ( ${ displaystyle delta}$ ).
Спецификация строится из набора соответствующих переменных, декомпозиции и набора форм.
Формы - это либо параметрические формы, либо вопросы к другим байесовским программам.
В вопросе указывается, какое распределение вероятностей необходимо вычислить.

Описание

Цель описания - указать эффективный метод вычисления совместное распределение вероятностей на наборе переменные ${ 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}$ , программист должен выполнить следующее:

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

Разложение

Учитывая раздел ${ 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 {align} & P left (X_ {1} wedge X_ {2} wedge cdots wedge X_ {N} mid delta wedge pi right) = {} & P left (L_ {1} wedge cdots wedge L_ {K} mid delta wedge pi right) = {} & P left (L_ {1} mid delta wedge pi справа) times P left (L_ {2} mid L_ {1} wedge delta wedge pi right) times cdots times P left (L_ {K} mid L_ {K-1 } клин cdots клин L_ {1} клин дельта клин пи право) конец {выровнен}}}

Условная независимость тогда гипотезы допускают дальнейшие упрощения. Гипотеза условной зависимости для переменной ${ displaystyle L_ {k}}$ определяется выбором некоторой переменной ${ displaystyle X_ {n}}$ среди переменных, входящих в конъюнкцию ${ Displaystyle L_ {к-1} клин cdots клин L_ {2} клин 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} середина R_ {k} wedge delta wedge pi right)}

Тогда получаем:

{ displaystyle { begin {align} & P left (X_ {1} wedge X_ {2} wedge cdots wedge X_ {N} mid delta wedge pi right) = {} & P left (L_ {1} mid delta wedge pi right) times P left (L_ {2} mid R_ {2} wedge delta wedge pi right) times cdots раз P left (L_ {K} mid R_ {K} wedge delta wedge pi right) end {align}}}

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

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

Формы

Каждая раздача ${ 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}} клин { 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} клин дельта клин пи вправо)}$ получается с помощью некоторых выводов, сделанных другой байесовской программой, определенной спецификациями ${ 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 (Поиск 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 {align} & P left ({ text {Searched}} mid { text {Known}} wedge delta wedge pi right) = {} & sum _ { text {Free}} left [P left ({ text {Searched}} wedge { text {Free}} mid { text {Known}} wedge delta wedge pi right) справа] = {} & { 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 {Известно }} 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}} середина дельта клин пи вправо) вправо] конец {выровнено}}}

где первое равенство следует из правила маргинализации, второе - из Теорема Байеса а третье соответствует второму применению маргинализации. Знаменатель выглядит как нормализационный член и может быть заменен константой. ${ displaystyle Z}$ .

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

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

{ displaystyle { begin {align} & P left ({ text {Searched}} mid { text {Known}} wedge delta wedge pi right) = {} & { frac { 1} {Z}} sum _ { text {Free}} left [ prod _ {k = 1} ^ {K} left [P left (L_ {i} mid K_ {i} wedge пи право) право] право] конец {выровнено}}}

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

Пример

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

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

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

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

Переменные

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

${ displaystyle Spam}$ : двоичная переменная, false, если электронное письмо не является спамом, и true в противном случае.
${ Displaystyle W_ {0}, W_ {1}, ldots, W_ {N-1}}$ : ${ displaystyle N}$ бинарные переменные. ${ displaystyle W_ {n}}$ верно, если ${ displaystyle n ^ {th}}$ Слово словаря присутствует в тексте.

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