Баєсова мережа

Оскільки баєсова мережа є повною моделлю змінних та їхніх взаємозв'язків, її можна використовувати для отримання відповідей на ймовірнісні запити стосовно них. Наприклад, цю мережу можна використовувати для з'ясовування уточненого знання про стан якоїсь підмножини змінних, коли спостерігаються інші змінні (змінні свідчення, англ. evidence). Цей процес обчислення апостеріорного розподілу змінних для заданого свідчення називається ймовірнісним висновуванням (англ. probabilistic inference). Це апостеріорне дає універсальну достатню статистику для застосувань для виявлення, коли потрібно підбирати значення підмножини змінних, які мінімізують певну функцію очікуваних втрат, наприклад, імовірність помилковості рішення. Баєсову мережу відтак можна розглядати як механізм автоматичного застосування теореми Баєса до комплексних задач.

Найпоширенішими методами точного висновування є: виключення змінних, яке виключає (інтегруванням або підсумовуванням) неспостережувані не запитові змінні одну по одній шляхом розподілу суми над добутком; поширення деревом злук, яке кешує обчислення таким чином, що одночасно можна робити запит до багатьох змінних, а нові свідчення можуть поширюватися швидко; та рекурсивне обумовлювання й пошук ТА/АБО, які передбачають просторово-часовий компроміс та підбирають ефективність виключення змінних при використанні достатнього простору. Всі ці методи мають експоненційну складність відносно деревної ширини мережі. Найпоширенішими алгоритмами наближеного висновування є вибірка за значимістю, стохастична імітація МКМЛ, міні-блокове виключення (англ. mini-bucket elimination), петельне поширення переконання, поширення узагальненого переконання та варіаційні методи.

Щоби повністю описати баєсову мережу, і відтак повністю представити спільний розподіл імовірності, необхідно для кожного вузла X вказати розподіл імовірності X, обумовлений батьками X. Цей розподіл X, обумовлений батьками X, може мати будь-який вигляд. Є звичним працювати з дискретними або ґаусовими розподілами, оскільки це спрощує обчислення. Іноді відомі лише обмеження на розподіл; тоді можна застосовувати принцип максимальної ентропії для визначення єдиного розподілу, який має найбільшу ентропію для заданих обмежень. (Аналогічно, в конкретному контексті динамічних баєсових мереж зазвичай вказують такий умовний розподіл розвитку в часі прихованих станів, щоби максимізувати ентропійну швидкість цього неявного стохастичного процесу.)

Ці умовні розподіли часто включають параметри, які є невідомими, і мусять бути оцінені з даних, іноді із застосуванням підходу максимальної правдоподібності. Пряма максимізація правдоподібності (або апостеріорної ймовірності) часто є складною, коли є неспостережувані змінні. Класичним підходом до цієї задачі є алгоритм очікування-максимізації, який чередує обчислення очікуваних значень неспостережених змінних за умови спостережуваних даних із максимізацією повної правдоподібності (або апостеріорного), виходячи з припущення про правильність попередньо обчислених очікуваних значень. За м'яких умов закономірності цей процес збігається до значень параметрів, які дають максимальну правдоподібність (або максимальне апостеріорне).

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

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

Автоматичне навчання структури баєсової мережі є проблемою, якою займається машинне навчання. Основна ідея сходить до алгоритму виявлення, розробленого Ребане та Перлом 1987 року,[6] який спирається на розрізнення між трьома можливими типами суміжних трійок, дозволеними в орієнтованому ациклічному графі (ОАГ):

1. ${\displaystyle X\rightarrow Y\rightarrow Z}$
2. ${\displaystyle X\leftarrow Y\rightarrow Z}$
3. ${\displaystyle X\rightarrow Y\leftarrow Z}$

Типи 2 та 3 представляють однакові залежності (${\displaystyle X}$ та ${\displaystyle Z}$ є незалежними за заданого ${\displaystyle Y}$), і, відтак, є нерозрізнюваними. Проте тип 3 може бути унікально виявлено, оскільки ${\displaystyle X}$ та ${\displaystyle Z}$ є відособлено незалежними, а всі інші пари є залежними. Таким чином, в той час як кістяки (англ. skeletons, графи із зачищеними стрілками) цих трьох трійок є однаковими, напрямок стрілок частково підлягає виявленню. Таке саме розрізнення застосовується й тоді, коли ${\displaystyle X}$ та ${\displaystyle Z}$ мають спільних батьків, тільки спочатку треба зробити обумовлення за цими батьками. Було розроблено алгоритми для систематичного визначення кістяка графу, що лежить в основі, а потім спрямовуванні всіх стрілок, чия спрямованість диктується спостережуваними умовними незалежностями.[1][7][8][9]

Альтернативний метод навчання структури застосовує пошук на основі оптимізації. Він потребує оцінкової функції та стратегії пошуку. Поширеною оцінковою функцією є апостеріорна ймовірність структури за заданих тренувальних даних, така як БІК або BDeu. Часові вимоги вичерпного пошуку, що повертає структуру, яка максимізує оцінку, є суперекспонентними відносно числа змінних. Стратегія локального пошуку робить поступові зміни, спрямовані на поліпшення оцінки структури. Алгоритм глобального пошуку, такий як метод Монте-Карло марковських ланцюгів, може уникати потрапляння в пастку локального мінімуму. Фрідман та ін.[10][11] обговорюють застосування взаємної інформації між змінними, та пошуку структури, яка її максимізує. Вони роблять це шляхом обмеження набору кандидатів у батьки k вузлами, і вичерпним пошуком серед таких.

Особливо швидким методом точного навчання БМ є розгляд цієї задачі як задачі оптимізації, й розв'язання її із застосуванням цілочисельного програмування. Обмеження ациклічності додаються цілочисельній програмі під час розв'язання у вигляді січних площин.[12] Такий метод може впоруватися із задачами, що мають до 100 змінних.

Щоби мати справу із задачами з тисячами змінних, необхідно застосовувати інший підхід. Одним з них є спочатку вибирати одне впорядкування, і потім знаходити оптимальну структуру БМ по відношенню до цього впорядкування. Це означає роботу на просторі пошуку можливих впорядкувань, що є зручним, оскільки він менший за простір мережних структур. Потім вибираються й оцінюються декілька впорядкувань. Було доведено, що цей метод є найкращим із доступних в наукових працях, коли число змінних є величезним.[13]

Інший метод полягає в зосередженні на підкласах розкладаних моделей, для яких оцінка максимальної правдоподібності має замкнений вигляд. Тоді можливо виявляти цілісну структуру для сотень змінних.[14]

Баєсова мережа може доповнюватися вузлами та ребрами із застосуванням методик машинного навчання на основі правил. Для добування правил та створення нових вузлів може застосовуватися індуктивне логічне програмування.[15] Підходи статистичного навчання відношень (СНВ, англ. statistical relational learning, SRL) використовують оцінкову функцію, що ґрунтується на структурі баєсової мережі, для спрямовування структурного пошуку та доповнення мережі.[16] Поширеною оцінковою функцією СНВ є площа під кривою РХП.

Як зазначено раніше, навчання баєсових мереж із обмеженою деревною шириною є необхідним для уможливлення точного розв'язного висновування, оскільки складність висновування в найгіршому випадку є експонентною по відношенню до деревної ширини k (за гіпотези експонентного часу). Проте, будучи глобальною властивістю графу, вона значно підвищує складність процесу навчання. В цьому контексті для ефективного навчання можливо застосовувати поняття k-дерева.[17]

Припустімо, що ми виміряли величини ${\displaystyle x_{1},\dots ,x_{n}\,\!}$, кожна із нормально розподіленою похибкою відомого стандартного відхилення ${\displaystyle \sigma \,\!}$,

${\displaystyle x_{i}\sim N(\theta _{i},\sigma ^{2})}$

Припустімо, що нас цікавить оцінка ${\displaystyle \theta _{i}}$. Підходом буде оцінювати ${\displaystyle \theta _{i}}$ із застосуванням методу максимальної правдоподібності; оскільки спостереження є незалежними, правдоподібність розкладається на множники, і оцінкою максимальної правдоподібності є просто

${\displaystyle \theta _{i}=x_{i}}$

Проте, якщо ці величини є взаємопов'язаними, так що, наприклад, ми можемо думати, що окремі ${\displaystyle \theta _{i}}$ було й самі вибрано з розподілу, що лежав в основі, то цей взаємозв'язок руйнує незалежність, і пропонує складнішу модель, наприклад,

${\displaystyle x_{i}\sim N(\theta _{i},\sigma ^{2}),}$

${\displaystyle \theta _{i}\sim N(\varphi ,\tau ^{2})}$

з некоректними апріорними ${\displaystyle \varphi \sim }$flat, ${\displaystyle \tau \sim }$flat${\displaystyle \in (0,\infty )}$. При ${\displaystyle n\geq 3}$ це є пізнанною моделлю (тобто, існує унікальний розв'язок для параметрів моделі), а апостеріорні розподіли окремих ${\displaystyle \theta _{i}}$ будуть схильні рухатися, або стискатися (англ. shrink) від оцінок максимальної правдоподібності до свого спільного середнього. Це стискання (англ. shrinkage) є типовою поведінкою ієрархічних баєсових моделей.

При виборі апріорних в ієрархічній моделі потрібна деяка обережність, зокрема на масштабних змінних на вищих рівнях ієрархії, таких як змінна ${\displaystyle \tau \,\!}$ у цьому прикладі. Звичайні апріорні, такі як апріорне Джеффріса, часто не працюють, оскільки апостеріорний розподіл буде некоректним (його неможливо буде унормувати), а оцінки, зроблені мінімізуванням очікуваних втрат будуть неприйнятними.

X є баєсовою мережею по відношенню до G, якщо функцію її спільної густини ймовірності (по відношенню до добуткової міри) може бути записано як добуток окремих функцій густини, обумовлених їхніми батьківськими змінними:[18]

${\displaystyle p(x)=\prod _{v\in V}p\left(x_{v}\,{\big |}\,x_{\operatorname {pa} (v)}\right)}$

де pa(v) є множиною батьків v (тобто, тих вершин, які вказують безпосередньо на v через єдине ребро).

Для будь-якої множини випадкових змінних імовірність будь-якого члену спільного розподілу може бути обчислено з умовних імовірностей із застосуванням ланцюгового правила (для заданого топологічного впорядкування X) наступним чином:[18]

${\displaystyle \mathrm {P} (X_{1}=x_{1},\ldots ,X_{n}=x_{n})=\prod _{v=1}^{n}\mathrm {P} \left(X_{v}=x_{v}\mid X_{v+1}=x_{v+1},\ldots ,X_{n}=x_{n}\right)}$

Порівняйте це із наведеним вище визначенням, що його може бути записано наступним чином:

${\displaystyle \mathrm {P} (X_{1}=x_{1},\ldots ,X_{n}=x_{n})=\prod _{v=1}^{n}\mathrm {P} (X_{v}=x_{v}\mid X_{j}=x_{j}}$ для кожного ${\displaystyle X_{j}\,}$ що є батьком ${\displaystyle X_{v}\,)}$

Різницею між цими двома виразами є умовна незалежність змінних від будь-якого з їхніх не-нащадків за заданих значень їхніх батьківських змінних.

X є баєсовою мережею по відношенню до G, якщо вона задовольняє локальну марковську властивість (англ. local Markov property): кожна змінна є умовно незалежною від своїх не-нащадків за заданих її батьківських змінних:[19]

${\displaystyle X_{v}\perp \!\!\!\perp X_{V\setminus \operatorname {de} (v)}\mid X_{\operatorname {pa} (v)}\quad }$ для всіх ${\displaystyle v\in V}$

де de(v) є множиною нащадків, а V \ de(v) є множиною не-нащадків v.

Це також може бути виражено в подібних до першого визначення термінах як

${\displaystyle \mathrm {P} (X_{v}=x_{v}\mid X_{i}=x_{i}}$ для кожного ${\displaystyle X_{i}\,}$ що не є нащадком ${\displaystyle X_{v}\,)=P(X_{v}=x_{v}\mid X_{j}=x_{j}}$ для кожного ${\displaystyle X_{j}\,}$ що є батьківським для ${\displaystyle X_{v}\,)}$

Зауважте, що множина батьків є підмножиною множини не-нащадків, оскільки граф є ациклічним.

Для розробки баєсових мереж ми часто спочатку розробляємо такий ОАГ G, що ми переконані, що X задовольняє локальну марковську властивість по відношенню до G. Іноді це робиться шляхом створення причинного ОАГ. Потім ми з'ясовуємо умовні розподіли ймовірності для кожної змінної за заданих її батьків у G. В багатьох випадках, зокрема, в тому випадку, коли змінні є дискретними, якщо ми визначаємо спільний розподіл X як добуток цих умовних розподілів, то X є баєсовою мережею по відношенню до G.[20]

Марковське покриття вузла є множиною вузлів, яка складається з його батьківських вузлів, його дочірніх вузлів, та всіх іншиї батьків його дочірніх вузлів. Марковське покриття робить вузол незалежним від решти мережі; спільний розподіл змінних у марковському покритті вузла є достатнім знанням для обчислення розподілу цього вузла. X є баєсовою мережею по відношенню до G, якщо кожен вузол є умовно незалежним від всіх інших вузлів мережі за заданого його марковського покриття.[19]

Це визначення можна зробити загальнішим через визначення о-розділеності (англ. d-separation) двох вузлів, де «о» значить «орієнтована» (англ. directional).[21][22] Нехай P є ланцюгом від вузла u до v. Ланцюг — це ациклічний неорієнтований шлях між двома вузлами (тобто, напрям ребер при побудові цього шляху ігнорується), в якому ребра можуть мати будь-який напрям. Тоді про P кажуть, що він о-розділюється множиною вузлів Z, якщо виконуються будь-які з наступних умов:

1. P містить орієнтований шлях, ${\displaystyle u\ldots \leftarrow m\leftarrow \ldots v}$ або ${\displaystyle u\ldots \rightarrow m\rightarrow \ldots v}$, такий, що середній вузол m належить Z,
2. P містить розгалуження, ${\displaystyle u\ldots \leftarrow m\rightarrow \ldots v}$, таке, що середній вузол m належить Z, або
3. P містить обернене розгалуження (або колайдер), ${\displaystyle u\ldots \rightarrow m\leftarrow \ldots v}$, таке, що середній вузол m не належить Z, і жодні з нащадків m не належать Z

X є баєсовою мережею по відношенню до G, якщо для будь-яких двох вузлів u та v

${\displaystyle X_{u}\perp \!\!\!\perp X_{v}\mid X_{Z}}$

де Z є множиною, яка о-розділює u та v. (Марковське покриття є мінімальним набором вузлів, які о-відділюють вузол v від решти вузлів.)

Термін ієрархічна модель (англ. hierarchical model) іноді вважається окремим типом басової мережі, але він не має формального визначення. Іноді цей термін резервують для моделей з трьома або більше шарами випадкових змінних; в інших випадках його резервують для моделей із латентними змінними. Проте в цілому «ієрархічною» зазвичай називають будь-яку помірно складну баєсову мережу.

Хоч баєсові мережі й використовують часто для представлення причинних взаємозв'язків, це не обов'язково повинно бути так: орієнтоване ребро з u до v не вимагає, щоби X_v причинно залежало від X_u. Про це свідчить той факт, що баєсові мережі на графах

${\displaystyle a\rightarrow b\rightarrow c\qquad }$ та ${\displaystyle \qquad a\leftarrow b\leftarrow c}$

є рівнозначними: тобто, вони накладають точно такі ж вимоги умовної незалежності.

Причи́нна мере́жа (англ. causal network) — це баєсова мережа з явною вимогою того, що взаємозв'язки є причинними. Додаткова семантика причинних мереж вказує, що якщо вузлові X активно спричинено перебування в заданому стані x (дія, що записується як do(X = x)), то функція густини ймовірності змінюється на функцію густини ймовірності мережі, отриманої відсіканням з'єднань від батьків X до X, і встановленням X у спричинене значення x.[1] Застосовуючи ці семантики, можна передбачувати вплив зовнішніх втручань на основі даних, отриманих до втручання.

• libDAI Вільна відкрита бібліотека C++ дискретного наближеного висновування (англ. Discrete Approximate Inference) в графових моделях. libDAI підтримує такі методи висновування як точне висновування перебором грубою силою, точне висновування методами дерева злук, осередненого поля, петельного поширення переконання, вибірки за Ґіббсом, обумовленого поширення переконання (англ. Conditioned Belief Propagation) та деякі інші.
• Mocapy++ Інструментарій динамічних баєсових мереж, реалізований мовою C++. Він підтримує дискретні, багаточленні, ґаусові, кентові, фон мізесові та пуассонові вузли. Висновування та навчання здійснюються вибіркою за Ґіббсом/стохастичним очікуванням-максимізацією.
• WinBUGS Одна з перших обчислювальних реалізацій вибірок МКМЛ. Більше не підтримується й не рекомендується для активного застосування.
• OpenBUGS (сайт), подальша (відкрита) розробка WinBUGS.
• Just another Gibbs sampler (JAGS) (сайт) Інша відкрита альтернатива WinBUGS. Використовує вибірку за Ґіббсом.
• Stan (програмне забезпечення) (сайт Архівовано 3 вересня 2012 у Wayback Machine.) Відкритий пакет для отримування баєсового висновування із застосуванням безрозворотної вибірки (англ. No-U-Turn sampler), одного з варіантів гамільтонового Монте-Карло. Він в чомусь подібний до BUGS, але з іншою мовою для вираження моделей та іншою вибіркою для відбору зразків з їхніх апостеріорних. RStan це інтерфейс R до Stan. Його підтримують Андрій Гельман з колегами.
• Direct Graphical Models (DGM) — відкрита бібліотека C++, яка реалізує різні завдання в імовірнісних графових моделях із попарними залежностями.
• OpenMarkov — відкрите програмне забезпечення та ППІ, реалізовані в Java
• Graphical Models Toolkit (GMTK) — відкритий загальнодоступний інструментарій для швидкого прототипування статистичних моделей із застосуванням динамічних графових моделей (ДГМ, англ. dynamic graphical models, DGM) і динамічних баєсових мереж (ДБМ, англ. dynamic Bayesian networks, DBN). GMTK можливо застосовувати для застосунків та досліджень в обробці мовлення та мови, в біоінформатиці, розпізнаванні діяльності та будь-яких застосунках часових рядів.
• PyMC — модуль Python, який реалізує баєсові статистичні моделі та алгоритми допасовування, включно з Монте-Карло марковських ланцюгів. Його гнучкість та розширюваність роблять його застосовним для великого набору задач. Поряд із ядровою функційністю вибірки, PyMC включає методи підсумовування виходу, графічного представлення, а також діагностування якості допасовування та збіжності.
• GeNIe&Smile — SMILE це бібліотека C++ для баєсових мереж та діаграм впливу, а GeNIe це ГІК для неї
• SamIam — система на основі Java з ГІК та ППІ Java
• Bayes Server — користувацький інтерфейс та ППІ для баєсових мереж, включає підтримку часових рядів та послідовностей
• Blip — веб-інтерфейс, який пропонує структурне навчання баєсових мереж безпосередньо з дискретних даних. Він може обробляти набори даних із тисячами змінних, і пропонує і пропонує як необмежене, так і обмежене деревною шириною навчання структури.
• Belief and Decision Networks на AIspace
• BayesiaLab від Bayesia
• Hugin
• AgenaRisk
• Netica від Norsys
• Bayesian network application library
• dVelox від Apara Software
• System Modeler від Inatas AB
• UnBBayes від GIA-UnB (Intelligence Artificial Group — University of Brasilia)
• із застосуванням технології новітнього аналізу лицьової дисморфології (англ. Facial Dysmorphology Novel Analysis, FDNA)
• Uninet — неперервні баєсові мережі, які моделюють неперервні змінні, з широким спектром параметричних та непараметричних відособлених розподілів, і залежністю з паруванням. Також підтримуються гібридні дискретно-неперервні моделі. Безкоштовне для некомерційного використання. Розроблено компанією LightTwist Software.
• Tetrad — відкритий проект, написаний на Java, та розроблений Факультетом філософії університету Карнегі-Меллон, який займається причинними моделями та статистичними даними.
• Dezide
• bnlearn — пакет R
• RISO (розподілені мережі переконань)
• BANSY3 — Безкоштовне. Від the Non Linear Dynamics Laboratory. Mathematics Department, Science School, UNAM.
• MSBNx — компонентно-орієнтований інструментарій для моделювання та висновування з баєсовими мережами (від Microsoft Research)
• Bayes Net Toolbox для Matlab