Баєсове програмування

Ба́єсове програмува́ння — це формальна система та методологія визначення ймовірнісних моделей та розв'язання задач, коли не вся необхідна інформація є доступною.

^[cs] запропонував, щоби ймовірність могла розглядатися як альтернатива та розширення логіки для раціонального міркування з неповною та непевною інформацією. У своїй засадничій книзі «Теорія ймовірностей: логіка науки» він розробив цю теорію та запропонував те, що він назвав «роботом», що було не фізичним пристроєм, а рушієм висновування для автоматизації ймовірнісних міркувань — щось на кшталт Прологу для ймовірності замість логіки. Баєсове програмування є формальним та конкретним втіленням цього «робота».

Баєсове програмування також можна розглядати як алгебраїчну формальну систему для визначення графових моделей, таких як, наприклад, баєсові мережі, фільтри Калмана або приховані марковські моделі. Дійсно, баєсове програмування є загальнішим за баєсові мережі, і має виразну потужність, еквівалентну ймовірнісним ^[en].

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

Баєсова програма є засобом визначення сімейства розподілів імовірності.

Нижче представлено складові елементи баєсової програми:

${\displaystyle {\text{Program}}{\begin{cases}{\text{Description}}{\begin{cases}{\text{Specification}}(\pi ){\begin{cases}{\text{Variables}}\\{\text{Decomposition}}\\{\text{Forms}}\\\end{cases}}\\{\text{Identification (based on }}\delta )\end{cases}}\\{\text{Question}}\end{cases}}}$

1. Програма будується з опису (англ. description) та питання (англ. question).
2. Опис будується із застосуванням якогось визначення (${\displaystyle \pi }$, англ. specification), заданого програмістом, та ідентифікації (англ. identification) або навчального процесу для параметрів, не повністю описаних у визначенні, із застосуванням набору даних (${\displaystyle \delta }$).
3. Визначення будується з набору доречних змінних (англ. variables), розкладу (англ. decomposition) та набору форм (англ. forms).
4. Форми є або параметричними формами, або питаннями до інших баєсових програм.
5. Питання визначає, який розподіл імовірності повинно бути розраховано.

Опис

Задачею опису є визначення ефективного методу обчислення спільного розподілу ймовірності набору змінних ${\displaystyle \left\{X_{1},X_{2},\cdots ,X_{N}\right\}}$ для заданого набору експериментальних даних ${\displaystyle \delta }$ та деякого визначення ${\displaystyle \pi }$. Цей спільний розподіл позначається як ${\displaystyle P\left(X_{1}\wedge X_{2}\wedge \cdots \wedge X_{N}\mid \delta \wedge \pi \right)}$.

Для визначення попереднього знання ${\displaystyle \pi }$ програміст мусить виконати наступне:

1. Визначити набір доречних змінних ${\displaystyle \left\{X_{1},X_{2},\cdots ,X_{N}\right\}}$, на якому визначено спільний розподіл імовірності.
2. Розкласти спільний розподіл (розбити його на доречні незалежні або умовні ймовірності).
3. Визначити форми кожного з цих розподілів (наприклад, для кожної змінної, один з переліку розподілів імовірності).

Розклад

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

${\displaystyle {\begin{aligned}&P\left(X_{1}\wedge X_{2}\wedge \cdots \wedge X_{N}\mid \delta \wedge \pi \right)\\={}&P\left(L_{1}\wedge \cdots \wedge L_{K}\mid \delta \wedge \pi \right)\\={}&P\left(L_{1}\mid \delta \wedge \pi \right)\times P\left(L_{2}\mid L_{1}\wedge \delta \wedge \pi \right)\times \cdots \times P\left(L_{K}\mid L_{K-1}\wedge \cdots \wedge L_{1}\wedge \delta \wedge \pi \right)\end{aligned}}}$

Потім гіпотези ^[en] дозволяють подальші спрощення. Гіпотеза умовної незалежності для змінної ${\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\}}$ на три набори: досліджувані (англ. searched) змінні, відомі (англ. known) змінні та вільні (англ. free) змінні.

Три змінні ${\displaystyle Searched}$, ${\displaystyle Known}$ та ${\displaystyle Free}$ визначаються як кон'юнкція змінних, що належать до цих наборів.

Питання визначається як набір розподілів

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

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

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

Висновування

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

${\displaystyle {\begin{aligned}&P\left({\text{Searched}}\mid {\text{Known}}\wedge \delta \wedge \pi \right)\\={}&\sum _{\text{Free}}\left[P\left({\text{Searched}}\wedge {\text{Free}}\mid {\text{Known}}\wedge \delta \wedge \pi \right)\right]\\={}&{\frac {\displaystyle \sum _{\text{Free}}\left[P\left({\text{Searched}}\wedge {\text{Free}}\wedge {\text{Known}}\mid \delta \wedge \pi \right)\right]}{\displaystyle P\left({\text{Known}}\mid \delta \wedge \pi \right)}}\\={}&{\frac {\displaystyle \sum _{\text{Free}}\left[P\left({\text{Searched}}\wedge {\text{Free}}\wedge {\text{Known}}\mid \delta \wedge \pi \right)\right]}{\displaystyle \sum _{{\text{Free}}\wedge {\text{Searched}}}\left[P\left({\text{Searched}}\wedge {\text{Free}}\wedge {\text{Known}}\mid \delta \wedge \pi \right)\right]}}\\={}&{\frac {1}{Z}}\times \sum _{\text{Free}}\left[P\left({\text{Searched}}\wedge {\text{Free}}\wedge {\text{Known}}\mid \delta \wedge \pi \right)\right]\end{aligned}}}$

де перше рівняння випливає з правила відособлення, друге випливає з теореми Баєса, а третє відповідає другому застосуванню відособлення. Знаменник виявляється нормувальним членом, і його може бути замінено сталою ${\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}$-те слово словника присутнє в тексті.

Ці ${\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] для подолання проблеми нульової частоти досі ніколи не бачених слів):
   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}}}$

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

Добре відомі фільтри Калмана є окремим випадком баєсових фільтрів.

Вони визначаються наступною баєсовою програмою:

${\displaystyle Pr{\begin{cases}Ds{\begin{cases}Sp(\pi ){\begin{cases}Va:\\S^{0},\cdots ,S^{T},O^{0},\cdots ,O^{T}\\Dc:\\{\begin{cases}&P\left(S^{0}\wedge \cdots \wedge O^{T}|\pi \right)\\=&\left[{\begin{array}{c}P\left(S^{0}\wedge O^{0}|\pi \right)\\\prod _{t=1}^{T}\left[P\left(S^{t}|S^{t-1}\wedge \pi \right)\times P\left(O^{t}|S^{t}\wedge \pi \right)\right]\end{array}}\right]\end{cases}}\\Fo:\\{\begin{cases}P\left(S^{t}\mid S^{t-1}\wedge \pi \right)\equiv G\left(S^{t},A\bullet S^{t-1},Q\right)\\P\left(O^{t}\mid S^{t}\wedge \pi \right)\equiv G\left(O^{t},H\bullet S^{t},R\right)\end{cases}}\end{cases}}\\Id\end{cases}}\\Qu:\\P\left(S^{T}\mid O^{0}\wedge \cdots \wedge O^{T}\wedge \pi \right)\end{cases}}}$

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

З цими гіпотезами та із застосуванням рекурсивної формули задачу висновування для отримання відповіді на звичайне питання ${\displaystyle P(S^{T}\mid O^{0}\wedge \cdots \wedge O^{T}\wedge \pi )}$ можна розв'язувати аналітично. Це веде до надзвичайно ефективного алгоритму, що пояснює популярність фільтрів Калмана та численність їхніх повсякденних застосувань.

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

Прихована марковська модель

Приховані марковські моделі (ПММ) є іншою дуже популярною спеціалізацією фільтрів Калмана.

Вони визначаються наступною баєсовою програмою:

${\displaystyle \Pr {\begin{cases}Ds{\begin{cases}Sp(\pi ){\begin{cases}Va:\\S^{0},\ldots ,S^{T},O^{0},\ldots ,O^{T}\\Dc:\\{\begin{cases}&P\left(S^{0}\wedge \cdots \wedge O^{T}\mid \pi \right)\\=&\left[{\begin{array}{c}P\left(S^{0}\wedge O^{0}\mid \pi \right)\\\prod _{t=1}^{T}\left[P\left(S^{t}\mid S^{t-1}\wedge \pi \right)\times P\left(O^{t}\mid S^{t}\wedge \pi \right)\right]\end{array}}\right]\end{cases}}\\Fo:\\{\begin{cases}P\left(S^{0}\wedge O^{0}\mid \pi \right)\equiv {\text{Matrix}}\\P\left(S^{t}\mid S^{t-1}\wedge \pi \right)\equiv {\text{Matrix}}\\P\left(O^{t}\mid S^{t}\wedge \pi \right)\equiv {\text{Matrix}}\end{cases}}\end{cases}}\\Id\end{cases}}\\Qu:\\\max _{S^{1}\wedge \cdots \wedge S^{T-1}}\left[P\left(S^{1}\wedge \cdots \wedge S^{T-1}\mid S^{T}\wedge O^{0}\wedge \cdots \wedge O^{T}\wedge \pi \right)\right]\end{cases}}}$

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

${\displaystyle \max _{S^{1}\wedge \cdots \wedge S^{T-1}}\left[P\left(S^{1}\wedge \cdots \wedge S^{T-1}\mid S^{T}\wedge O^{0}\wedge \cdots \wedge O^{T}\wedge \pi \right)\right]}$

Якою є найімовірніша послідовність станів, що веде до поточного стану за відомих минулих спостережень?

Відповідь на дане окреме питання можна отримувати за допомогою особливого та дуже ефективного алгоритму, що називається алгоритмом Вітербі.

Для ПММ також було розроблено особливий алгоритм навчання, що називається Алгоритм Баума — Велша.

Застосування

Академічні застосування

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

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

В робототехніці баєсове програмування застосовувалося в автономній робототехніці, роботизованих САПР,передових системам допомоги водієві, роботизованому керуванні маніпуляторами, ^[en], людино-роботній взаємодії, людино-автомобільній взаємодії (баєсові автономні моделі водія), програмуванні та навчанні аватарів у відеоіграх та в стратегічних іграх реального часу (ШІ).

Науки про життя

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

Баєсове програмування та теорії можливостей

Порівняння ймовірнісних підходів (не лише баєсового програмування) та теорій можливостей обговорювалося вже тривалий час, і, на жаль, є дуже спірним питанням.

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

Захист імовірності головним чином базується на ^[en], яка, починаючи з чотирьох постулатів щодо раціонального міркування в умовах невизначеності, демонструє, що лише математична модель, яка задовольняє ці постулати, є теорією ймовірності. Аргументація потім іде таким чином: якщо ви використовуєте інший підхід, ніж імовірність, то ви обов'язково порушуєте один з цих постулатів. Подивимося, який саме, та обговоримо його корисність.

Баєсове програмування та ймовірнісне програмування

Метою ^[en] є об'єднання сфери класичних мов програмування з імовірнісним моделюванням (особливо з баєсовими мережами) для того, щоби бути в змозі мати справу із невизначеністю, але все ще отримувати користь від виразної сили мов програмування для опису складних моделей.

Розширені класичні мови програмування можуть бути логічними мовами, як запропоновано в Імовірнісній абдукції Горна, Логіці незалежного вибору, PRISM та ProbLog, що пропонує розширення мови Prolog.

Воно також може бути розширеннями функційних мов програмування (по суті LISP та Scheme), такими як IBAL або ^[en]. Мовами, що дають натхнення, можуть бути навіть об'єктно орієнтовані, як у BLOG та FACTORIE, або стандартніші, як у CES та FIGARO [ 1 лютого 2016 у Wayback Machine.].

Мета баєсового програмування є іншою. Настанова Джейнса про «ймовірність як логіку» обстоює те, що ймовірність є розширенням та альтернативою логіці, над якою може бути перебудовано повну теорію раціональності, обчислення та програмування. Баєсове програмування шукає способу не розширити класичні мови, а швидше замінити їх новим підходом програмування на основі ймовірності та повного врахування неповноти та ^[en].

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

Див. також

• Правило Баєса
• Баєсове висновування
• Баєсова ймовірність
• Баєсове фільтрування спаму
• ^[en]
• ^[en]
• Алгоритм очікування-максимізації
• ^[en]
• Графова модель
• Прихована марковська модель
• Джуда Перл
• Фільтр Калмана
• Наївний баєсів класифікатор
• П'єр-Симон де Лаплас
• Ймовірнісна логіка
• ^[en]
• ^[en]

Примітки

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

Література

• Kamel Mekhnacha (2013). Bayesian Programming. Chapman and Hall/CRC. ISBN . (англ.)

Посилання

• Сайт-супутник книги «Баєсове програмування», де можна завантажити ProBT та рушій висновування, що присвячено баєсовому програмуванню. [Архівовано 23 листопада 2013 у Archive.is] (англ.)
• Сайт bayesian-programming.org [Архівовано 23 листопада 2013 у Archive.is] для просування баєсового програмування з детальною інформацією та численними публікаціями. (англ.)