WikiSort.ru - Не сортированное

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

Пусть множество ${\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}}}$

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

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

Формы

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

Переменные

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

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}})}$ может быть задана с помощью правила следования Лапласа^[en] (это методика сглаживания^[en] на базе псевдосчетчика^[en] для преодоления проблемы нулевой частоты до сих пор не встречавшихся слов):
   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}}}$

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

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

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

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

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

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

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

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

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

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

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

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

Науки о жизни

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