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

Проста баєсова мережа. Дощ (Шаблон:Lang-en) впливає на те, чи вмикається розбризкувач (Шаблон:Lang-en), і як дощ, так і розбризкувач, впливають на те, чи є трава мокрою (Шаблон:Lang-en).

Ба́єсова мере́жа, мере́жа Ба́єса, мере́жа перекона́нь, ба́єсова моде́ль або ймові́рнісна орієнто́вана ациклі́чна гра́фова моде́ль (Шаблон:Lang-en) — це ймовірнісна графова модель (різновид статистичної моделі), яка представляє набір випадкових змінних та їхніх Шаблон:Нп за допомогою орієнтованого ациклічного графу (ОАГ, Шаблон:Lang-en). Наприклад, баєсова мережа може представляти ймовірнісні зв'язки між захворюваннями та симптомами. Таку мережу можна використовувати для обчислення ймовірностей наявності різних захворювань за наявних симптомів.

Формально баєсові мережі є ОАГ, чиї вершини представляють випадкові змінні у баєсовому сенсі: вони можуть бути спостережуваними величинами, латентними змінними, невідомими параметрами або гіпотезами. Ребра представляють умовні залежності; не з'єднані вершини (такі, що в Баєсовій мережі не існує шляху від однієї змінної до іншої) представляють змінні, що є Шаблон:Нп одна від одної. Кожну вершину пов'язано із функцією ймовірності, що бере на вході певний набір значень батьківських вершин, і видає (на виході) ймовірність (або розподіл імовірності, якщо застосовно) змінної, представленої цією вершиною. Наприклад, якщо $m$ батьківських вершин представляють $m$ булевих змінних, то функцію ймовірності може бути представлено таблицею $2^m$ записів, по одному запису для кожної з $2^m$ можливих комбінацій істинності або хибності її батьків. Схожі ідеї можуть застосовуватися до неорієнтованих та, можливо, циклічних графів, таких як марковські мережі.

Існують ефективні алгоритми, що виконують висновування та навчання в баєсових мережах. Баєсові мережі, що моделюють послідовності змінних (наприклад, сигнали мовлення, або послідовності білків), називають динамічними баєсовими мережами. Узагальнення баєсових мереж, що можуть представляти та розв'язувати задачі ухвалення рішень за умов невизначеності, називають Шаблон:Нп.

Приклад

Проста баєсова мережа з Шаблон:Нп

Припустімо, що існують дві події, які можуть спричинити мокрість трави: або увімкнено розбризкувач, або йде дощ. Також припустімо, що дощ має прямий вплив на використання розбризкувача (а саме, коли йде дощ, розбризкувач зазвичай не увімкнено). Тоді цю ситуацію може бути змодельовано баєсовою мережею (показаною праворуч). Всі три змінні мають два можливі значення, T (істина, Шаблон:Lang-en) та F (хиба, Шаблон:Lang-en).

Функцією спільного розподілу ймовірності є

$\mathrm{Pr}(G,S,R)=\mathrm{Pr}(G|S,R)\mathrm{Pr}(S|R)\mathrm{Pr}(R)$

де назви змінних є скороченнями G = трава мокра (Шаблон:Lang-en, так/ні), S = розбризкувач увімкнено (Шаблон:Lang-en, так/ні) та R = іде дощ (Шаблон:Lang-en, так/ні).

Ця модель може відповідати на такі питання, як «Якою є ймовірність того, що йде дощ, якщо трава мокра?» шляхом застосування формули умовної ймовірності та підбиття сум за всіма Шаблон:Нп:

$\mathrm{Pr}(R=T|G=T)=\frac{\mathrm{Pr}(G=T,R=T)}{\mathrm{Pr}(G=T)}=\frac{\sum _{S\in \{T,F\}}\mathrm{Pr}(G=T,S,R=T)}{\sum _{S,R\in \{T,F\}}\mathrm{Pr}(G=T,S,R)}$

Використовуючи розклад спільної функції ймовірності $\mathrm{Pr}(G,S,R)$, та умовні ймовірності з Шаблон:Нп, зазначених у діаграмі, можна оцінити кожен член у сумах чисельника та знаменника. Наприклад,

$\begin{array}{cc}\mathrm{Pr}(G=T,S=T,R=T)& =\mathrm{Pr}(G=T|S=T,R=T)\mathrm{Pr}(S=T|R=T)\mathrm{Pr}(R=T)\\ & =0.99\times 0.01\times 0.2\\ & =0.00198.\end{array}$

Тоді числовими результатами (з пов'язаними значеннями змінних в індексах) є

$\mathrm{Pr}(R=T|G=T)=\frac{0.00198_{TTT}+0.1584_{TFT}}{0.00198_{TTT}+0.288_{TTF}+0.1584_{TFT}+0.0_{TFF}}=\frac{891}{2491}\approx 35.77\mathrm{\%}.$

З іншого боку, якщо ми хочемо відповісти на втручальницьке питання «Яка ймовірність того, що піде дощ, якщо ми намочимо траву?», то відповідь визначатиметься післявтручальною функцією спільного розподілу $\mathrm{Pr}(S,R|\text{do}(G=T))=\mathrm{Pr}(S|R)P(R)$, отриманою усуненням коефіцієнту $\mathrm{Pr}(G|S,R)$ із довтручального розподілу. Як і очікувалося, на ймовірність дощу ця дія не впливає: $\mathrm{Pr}(R|\text{do}(G=T))=\mathrm{Pr}(R)$.

Понад те, якщо ми хочемо передбачити вплив умикання розбризкувача, то ми маємо

$\mathrm{Pr}(R,G|\text{do}(S=T))=\mathrm{Pr}(R)\mathrm{Pr}(G|R,S=T)$

з усуненим членом $\mathrm{Pr}(S=T|R)$, що показує, що ця дія має вплив на траву, але не на дощ.

Ці передбачення не можуть бути здійсненними, якщо якісь змінні є неспостережуваними, як у більшості задач оцінки стратегій. Вплив дії $\text{do}(x)$ все ще можна передбачувати, проте лише якщо задовольняється критерій «чорного ходу». Він заявляє, що якщо може спостерігатися множина вузлів Z, яка о-розділює (або блокує) всі чорні ходи (Шаблон:Lang-en) з X до Y, то $\mathrm{Pr}(Y,Z|\text{do}(x))=\mathrm{Pr}(Y,Z,X=x)/\mathrm{Pr}(X=x|Z)$. Чорний хід є таким, що закінчується стрілкою в X. Множини, які задовольняють критерій чорного ходу, називають «достатніми» (Шаблон:Lang-en) або «прийнятними» (Шаблон:Lang-en). Наприклад, множина Z = R є прийнятною для передбачування впливу S = T на G, оскільки R о-розділює (єдиний) чорний хід S ← R → G. Проте якщо S не спостерігається, то не існує іншої множини, яка би о-розділювала цей шлях, і вплив умикання розбризкувача (S = T) на траву (G) не може бути передбачено з пасивних спостережень. Тоді ми кажемо, що множина P(G | do(S = T)) є не пізннаною (Шаблон:Lang-en). Це віддзеркалює той факт, що за умови браку даних втручання ми не можемо визначити, чи завдячує спостережувана залежність між S та G випадковому зв'язкові або є фальшивою (видима залежність, що випливає зі спільної причини, R). (див. парадокс Сімпсона)

Для з'ясування того, чи є причинний зв'язок пізнанним із довільної баєсової мережі з неспостережуваними змінними, можна застосовувати три правила числення дій (Шаблон:Lang-en), і перевіряти, чи всі do-члени може бути усунено з виразу для цього співвідношення, підтверджуючи таким чином, що бажана величина є оцінкою із частотних даних.

Застосування баєсової мережі може заощаджувати значні обсяги пам'яті, якщо залежності в спільному розподілі є розрідженими. Наприклад, наївний спосіб зберігання умовних імовірностей для 10 двозначних змінних як таблиці вимагає простору для зберігання $2^{10}=1024$ значень. Якщо локальні розподіли жодної зі змінних не залежать більше ніж від трьох батьківських змінних, то представлення як баєсової мережі потребує зберігання щонайбільше $10\cdot 2^3=80$ значень.

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

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

Для баєсових мереж існує три основні завдання для висновування.

Отримування висновків про неспостережувані змінні

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

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

Навчання параметрів

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

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

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

Навчання структури

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

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

1. $X\to Y\to Z$
2. $X\leftarrow Y\to Z$
3. $X\to Y\leftarrow Z$

Типи 2 та 3 представляють однакові залежності ($X$ та $Z$ є незалежними за заданого $Y$), і, відтак, є нерозрізнюваними. Проте тип 3 може бути унікально виявлено, оскільки $X$ та $Z$ є відособлено незалежними, а всі інші пари є залежними. Таким чином, в той час як кістяки (Шаблон:Lang-en, графи із зачищеними стрілками) цих трьох трійок є однаковими, напрямок стрілок частково підлягає виявленню. Таке саме розрізнення застосовується й тоді, коли $X$ та $Z$ мають спільних батьків, тільки спочатку треба зробити обумовлення за цими батьками. Було розроблено алгоритми для систематичного визначення кістяка графу, що лежить в основі, а потім спрямовуванні всіх стрілок, чия спрямованість диктується спостережуваними умовними незалежностями.

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

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

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

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

Баєсова мережа може доповнюватися вузлами та ребрами із застосуванням методик машинного навчання на основі правил. Для добування правил та створення нових вузлів може застосовуватися Шаблон:Нп. Підходи Шаблон:Нп (СНВ, Шаблон:Lang-en) використовують Шаблон:Нп, що ґрунтується на структурі баєсової мережі, для спрямовування структурного пошуку та доповнення мережі. Поширеною оцінковою функцією СНВ є площа під кривою РХП.

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

Статистичне введення

Для заданих даних $x$ та параметру $\theta$ простий баєсів аналіз починається з апріорної ймовірності (апріорного) $p(\theta )$ та правдоподібності $p(x\mid \theta )$ для обчислення апостеріорної ймовірності $p(\theta \mid x)\propto p(x\mid \theta )p(\theta )$.

Часто апріорне $\theta$ залежить у свою чергу від інших параметрів $\phi$, які не згадуються в правдоподібності. Отже, апріорне $p(\theta )$ мусить бути замінено правдоподібністю $p(\theta \mid \phi )$, і потрібним апріорним $p(\phi )$ нововведених параметрів $\phi$, що дає в результаті апостеріорну ймовірність

$p(\theta ,\phi |x)\propto p(x|\theta )p(\theta |\phi )p(\phi ).$

Це є найпростішим прикладом ієрархічної баєсової моделі (Шаблон:Lang-en).Шаблон:Clarify

Цей процес може повторюватися; наприклад, параметри $\phi$ можуть у свою чергу залежати від додаткових параметрів $\psi$, які потребуватимуть свого власного апріорного. Зрештою цей процес мусить завершитися апріорними, які не залежать від жодних інших незгаданих параметрів.

Ввідні приклади

Припустімо, що ми виміряли величини $x_1,\dots ,x_n$, кожна із нормально розподіленою похибкою відомого стандартного відхилення $\sigma$,

$x_i\sim N({\theta }_i,{\sigma }^2)$

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

${\theta }_i=x_i$

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

$x_i\sim N({\theta }_i,{\sigma }^2),$

${\theta }_i\sim N(\phi ,{\tau }^2)$

з некоректними апріорними $\phi \sim$flat, $\tau \sim$flat$\in (0,\mathrm{\infty })$. При $n\ge 3$ це є пізнанною моделлю (тобто, існує унікальний розв'язок для параметрів моделі), а апостеріорні розподіли окремих ${\theta }_i$ будуть схильні рухатися, або Шаблон:Нп (Шаблон:Lang-en) від оцінок максимальної правдоподібності до свого спільного середнього. Це стискання (Шаблон:Lang-en) є типовою поведінкою ієрархічних баєсових моделей.

Обмеження на апріорні

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

Визначення та поняття

Існує декілька рівнозначних визначень баєсової мережі. Для всіх наступних, нехай G = (V,E) є орієнтованим ациклічним графом (або ОАГ), і нехай X = (X_v)_{v ∈ V} є множиною випадкових змінних, проіндексованою за V.

Множникове визначення

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

$p(x)=\prod _{v\in V}p\left(x_v\right|x_{\mathrm{pa}(v)})$

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

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

$\mathrm{P}(X_1=x_1,\dots ,X_n=x_n)=\prod _{v=1}^n\mathrm{P}(X_v=x_v\mid X_{v+1}=x_{v+1},\dots ,X_n=x_n)$

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

$\mathrm{P}(X_1=x_1,\dots ,X_n=x_n)=\prod _{v=1}^n\mathrm{P}(X_v=x_v\mid X_j=x_j$ для кожного $X_j$ що є батьком $X_v)$

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

Локальна марковська властивість

X є баєсовою мережею по відношенню до G, якщо вона задовольняє локальну марковську властивість (Шаблон:Lang-en): кожна змінна є Шаблон:Нп від своїх не-нащадків за заданих її батьківських змінних:Шаблон:Sfn

$X_v\perp \perp X_{V\setminus \mathrm{de}(v)}\mid X_{\mathrm{pa}(v)}$ для всіх $v\in V$

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

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

$\mathrm{P}(X_v=x_v\mid X_i=x_i$ для кожного $X_i$ що не є нащадком $X_v)=P(X_v=x_v\mid X_j=x_j$ для кожного $X_j$ що є батьківським для $X_v)$

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

Розробка баєсових мереж

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

Марковське покриття

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

Шаблон:AnchorШаблон:Anchorо-розділеність

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

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

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

$X_u\perp \perp X_v\mid X_Z$

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

Ієрархічні моделі

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

Причинні мережі

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

$a\to b\to c$ та $a\leftarrow b\leftarrow c$

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

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

Складність висновування та алгоритми наближення

1990 року під час праці в Стенфордському університеті над великими застосунками в біоінформатиці Грег Купер довів, що точне висновування в баєсових мережах є NP-складним. Цей результат спричинив сплеск досліджень алгоритмів наближення з метою розробки розв'язного наближення ймовірнісного висновування. 1993 року Шаблон:Нпні та Майкл Любі довели два несподівані результати стосовно складності наближення ймовірнісного висновування в баєсових мережах. По-перше, вони довели, що не існує розв'язного детермінованого алгоритму, який міг би наближувати ймовірнісне висновування в межах абсолютної похибки ɛ< 1/2. По-друге, вони довели, що не існує розв'язного увипадковленого алгоритму, який міг би наближувати ймовірнісне висновування в межах абсолютної похибки ɛ < 1/2 з довірчою ймовірністю понад 1/2.

Приблизно в той же час Шаблон:Нп довів, що точне висновування в баєсових мережах фактично є Шаблон:Нп (і відтак настільки ж складним, як і підрахунок числа задовільних присвоєнь КНФ-формули), і що наближене висновування, навіть для баєсових мереж із обмеженою архітектурою, є NP-складним.

З практичної точки зору, ці результати стосовно складності підказали, що хоча баєсові мережі й були цінними представленнями для застосунків ШІ та машинного навчання, їхнє застосування у великих реальних задачах вимагатиме пом'якшення або топологічними структурними обмеженнями, такими як наївні баєсові мережі, або обмеженнями на умовні ймовірності. Алгоритм обмеженої дисперсії (Шаблон:Lang-en) був першим алгоритмом довідного швидкого наближення для ефективного наближення ймовірнісного висновування в баєсових мережах з гарантією похибки наближення. Цей потужний алгоритм вимагав другорядних обмежень умовних імовірностей баєсової мережі, щоби отримати відмежування від нуля та одиниці на 1/p(n), де p(n) є будь-яким поліномом від числа вузлів мережі n.

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

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

Програмне забезпечення

• libDAI Шаблон:Webarchive Вільна відкрита бібліотека C++ дискретного наближеного висновування (Шаблон:Lang-en) в графових моделях. libDAI підтримує такі методи висновування як точне висновування перебором грубою силою, точне висновування Шаблон:Нп, Шаблон:Нп, Шаблон:Нп, Шаблон:Нп, обумовленого поширення переконання (Шаблон:Lang-en) та деякі інші.
• Mocapy++ Шаблон:Webarchive Інструментарій динамічних баєсових мереж, реалізований мовою C++. Він підтримує дискретні, багаточленні, ґаусові, кентові, фон мізесові та пуассонові вузли. Висновування та навчання здійснюються вибіркою за Ґіббсом/стохастичним очікуванням-максимізацією.
• Шаблон:Нп Одна з перших обчислювальних реалізацій вибірок МКМЛ. Більше не підтримується й не рекомендується для активного застосування.
• Шаблон:Нп (сайт Шаблон:Webarchive), подальша (відкрита) розробка WinBUGS.
• Шаблон:Нп (JAGS) (сайт) Інша відкрита альтернатива WinBUGS. Використовує вибірку за Ґіббсом.
• Шаблон:Нп (сайт Шаблон:Webarchive) Відкритий пакет для отримування баєсового висновування із застосуванням безрозворотної вибірки (Шаблон:Lang-en), одного з варіантів Шаблон:Нп. Він в чомусь подібний до BUGS, але з іншою мовою для вираження моделей та іншою вибіркою для відбору зразків з їхніх апостеріорних. RStan це інтерфейс R до Stan. Його підтримують Шаблон:Нп з колегами.
• Direct Graphical Models Шаблон:Webarchive (DGM) — відкрита бібліотека C++, яка реалізує різні завдання в імовірнісних графових моделях із попарними залежностями.
• OpenMarkov Шаблон:Webarchive — відкрите програмне забезпечення та ППІ, реалізовані в Java
• Graphical Models Toolkit (GMTK) — відкритий загальнодоступний інструментарій для швидкого прототипування статистичних моделей із застосуванням динамічних графових моделей (ДГМ, Шаблон:Lang-en) і динамічних баєсових мереж (ДБМ, Шаблон:Lang-en). GMTK можливо застосовувати для застосунків та досліджень в обробці мовлення та мови, в біоінформатиці, Шаблон:Нп та будь-яких застосунках часових рядів.
• PyMC Шаблон:Webarchive — модуль Python, який реалізує баєсові статистичні моделі та алгоритми допасовування, включно з Монте-Карло марковських ланцюгів. Його гнучкість та розширюваність роблять його застосовним для великого набору задач. Поряд із ядровою функційністю вибірки, PyMC включає методи підсумовування виходу, графічного представлення, а також діагностування якості допасовування та збіжності.
• GeNIe&Smile Шаблон:Webarchive — SMILE це бібліотека C++ для баєсових мереж та діаграм впливу, а GeNIe це ГІК для неї
• SamIam Шаблон:Webarchive — система на основі Java з ГІК та ППІ Java
• Bayes Server Шаблон:Webarchive — користувацький інтерфейс та ППІ для баєсових мереж, включає підтримку часових рядів та послідовностей
• Blip — вебінтерфейс, який пропонує структурне навчання баєсових мереж безпосередньо з дискретних даних. Він може обробляти набори даних із тисячами змінних, і пропонує і пропонує як необмежене, так і обмежене деревною шириною навчання структури.
• Belief and Decision Networks на AIspace Шаблон:Webarchive
• BayesiaLab Шаблон:Webarchive від Bayesia
• Hugin Шаблон:Webarchive
• AgenaRisk Шаблон:Webarchive
• Netica Шаблон:Webarchive від Norsys
• Bayesian network application library Шаблон:Webarchive
• dVelox від Apara Software
• System Modeler від Inatas AB
• UnBBayes Шаблон:Webarchive від GIA-UnB (Intelligence Artificial Group — University of Brasilia)
• [1] Шаблон:Webarchive із застосуванням технології новітнього аналізу лицьової дисморфології (Шаблон:Lang-en)
• Uninet Шаблон:Webarchive — неперервні баєсові мережі, які моделюють неперервні змінні, з широким спектром параметричних та непараметричних відособлених розподілів, і залежністю з паруванням. Також підтримуються гібридні дискретно-неперервні моделі. Безкоштовне для некомерційного використання. Розроблено компанією LightTwist Software.
• Tetrad Шаблон:Webarchive — відкритий проект, написаний на Java, та розроблений Факультетом філософії університету Карнегі-Меллон, який займається причинними моделями та статистичними даними.
• Dezide Шаблон:Webarchive
• bnlearn Шаблон:Webarchive — пакет R
• RISO Шаблон:Webarchive (розподілені мережі переконань)
• BANSY3 Шаблон:Webarchive — Безкоштовне. Від the Non Linear Dynamics Laboratory. Mathematics Department, Science School, UNAM.
• MSBNx Шаблон:Webarchive — компонентно-орієнтований інструментарій для моделювання та висновування з баєсовими мережами (від Microsoft Research)
• Bayes Net Toolbox Шаблон:Webarchive для Matlab

Історія

Термін «баєсові мережі» (Шаблон:Lang-en) було запроваджено Йудою Перлом 1985 року для підкреслення трьох аспектів:

1. Часто суб'єктивної природи вхідної інформації.
2. Покладання на баєсове обумовлювання як основу для уточнення інформації.
3. Відмінності причинної та доказової моделей міркування, яка підкреслює працю Томаса Баєса, опубліковану посмертно 1763 року.

Наприкінці 1980-х років праці Йуди Перла «Імовірнісне міркування в інтелектуальних системах» та Річарда Неаполітана «Імовірнісне міркування в експертних системах» підсумували властивості баєсових мереж та утвердили баєсові мережі як область дослідження.

Неофіційні варіанти таких мереж було вперше застосовано 1913 року юристом Джоном Генрі Вігмором у вигляді Шаблон:Нп для аналізу процесуальних доказів.Шаблон:Rp Інший варіант, що називається Шаблон:Нп, було розроблено генетиком Сьюелом Райтом, і застосовано в суспільній та поведінковій науці (переважно в лінійних параметричних моделях).

В своїй книзі 2018 року «Книга про Чому» Перл зізнався, що хоч і признає їх успішність в цілому, баєсові мережі не виправдали його сподівань (наблизити машинний інтелект до людського). Він також пояснив чому: мережі виводили висновки через спостережені ймовірності, але не враховували причинність. Думка про ймовірну помилковість конструкції баєсових мереж виникла у нього одразу ж після публікації книги «Імовірнісне міркування в інтелектуальних системах», що і призвело до появи причинних мереж.

Див. також

• Алгоритм очікування-максимізації
• Шаблон:Нп
• Баєсова ймовірність
• Шаблон:Нп
• Баєсове висновування
• Баєсове програмування
• Вирівнювання послідовностей
• Глибока мережа переконань
• Шаблон:Нп
• Графова модель
• Шаблон:Нп
• Динамічна баєсова мережа
• Шаблон:Нп
• Шаблон:Нп
• Ієрархічна часова пам'ять
• Джуда Перл
• Злиття давачів
• Машинне навчання
• Шаблон:Нп
• Наївний баєсів класифікатор
• Шаблон:Нп
• Обчислювальний інтелект
• Шаблон:Нп
• Шаблон:Нп
• Шаблон:Нп
• Розпізнавання мовлення
• Світогляд
• Система пам'яті—передбачування
• Шаблон:Нп
• Шаблон:Нп
• Сумішевий розподіл
• Теорема Баєса
• Шаблон:Нп — узагальнення теореми Баєса
• Фільтр Калмана
• Штучний інтелект

Джерела

• Шаблон:Cite encyclopedia Шаблон:Ref-en
• Шаблон:Cite book Шаблон:Ref-en
• Шаблон:Cite book Шаблон:Ref-en
• Шаблон:Cite encyclopedia Шаблон:Ref-en
• Шаблон:Cite book Шаблон:Ref-en
• Шаблон:Cite journal Шаблон:Ref-en
• Шаблон:Cite book (Ця праця ставить дерева рішень у внутрішніх вузлах баєсових мереж із застосуванням мінімальної довжини повідомлень Шаблон:Webarchive (Шаблон:Lang-en). Готову до друку кінцеву версію було представлено 15 жовтня 2003 року. Раніша версія: Comley and Dowe (2003) Шаблон:Webarchive, .pdf Шаблон:Webarchive.) Шаблон:Ref-en
• Шаблон:Cite book Шаблон:Ref-en
• Dowe, David L. (2010). MML, hybrid Bayesian network graphical models, statistical consistency, invariance and uniqueness Шаблон:Webarchive, in Handbook of Philosophy of Science (Volume 7: Handbook of Philosophy of Statistics), Elsevier, [2] Шаблон:Webarchive ISBN 978-0-444-51862-0, pp 901–982 Шаблон:Webarchive. Шаблон:Ref-en
• Fenton, Norman; Neil, Martin E. (November 2007). Managing Risk in the Modern World: Applications of Bayesian Networks — A Knowledge Transfer Report from the London Mathematical Society and the Knowledge Transfer Network for Industrial Mathematics. London (England): London Mathematical Society. Шаблон:Ref-en
• Шаблон:Cite news Шаблон:Ref-en
• Шаблон:Cite book Шаблон:Ref-en
• Шаблон:Cite book.

Також з'являється як Шаблон:Cite journal

Раніша версія з'являється як, Microsoft Research, March 1, 1995. Ця праця як про параметричне, так і про структурне навчання в баєсових мережах. Шаблон:Ref-en

• Шаблон:Cite book Шаблон:Ref-en
• Шаблон:Cite journal Шаблон:Ref-en
• Шаблон:Cite book Шаблон:Ref-en
• Шаблон:Cite journal Шаблон:Ref-en
• Шаблон:Cite journal Шаблон:Ref-en
• Шаблон:Cite journal Шаблон:Ref-en
• Шаблон:Cite book Шаблон:Ref-en
• Шаблон:Cite book Шаблон:Ref-en
• Шаблон:Russell Norvig 2003
• Шаблон:Cite journal This paper presents variable elimination for belief networks. Шаблон:Ref-en

Література

• Computational Intelligence: A Methodological Introduction by Kruse, Borgelt, Klawonn, Moewes, Steinbrecher, Held, 2013, Springer, ISBN 9781447150121 Шаблон:Ref-en
• Graphical Models — Representations for Learning, Reasoning and Data Mining, 2nd Edition, by Borgelt, Steinbrecher, Kruse, 2009, J. Wiley & Sons, ISBN 9780470749562 Шаблон:Ref-en
• Bayesian Netwrks and BayesiaLab — A practical introduction for researchers by Stefan Conrady and Lionel Jouffe Шаблон:Ref-en
• Шаблон:Cite journal

Посилання

• A tutorial on learning with Bayesian Networks Шаблон:Ref-en
• An Introduction to Bayesian Networks and their Contemporary Applications Шаблон:Webarchive Шаблон:Ref-en
• Інтернет-посібник з баєсових мереж та імовірності Шаблон:Webarchive Шаблон:Ref-en
• Вебзастосунок для створення баєсових мереж та виконання їх методом Монте-Карло Шаблон:Ref-en
• Continuous Time Bayesian Networks Шаблон:Webarchive Шаблон:Ref-en
• Баєсові мережі: пояснення та аналогія Шаблон:Ref-en
• Живий урок з навчання баєсовим мережам Шаблон:Webarchive Шаблон:Ref-en
• A hierarchical Bayes Model for handling sample heterogeneity in classification problems Шаблон:Webarchive, пропонує модель класифікації, яка враховує невизначеність, пов'язану з вимірюванням повторюваних зразків. Шаблон:Ref-en
• Hierarchical Naive Bayes Model for handling sample uncertainty Шаблон:Webarchive, показує, як виконувати класифікацію та навчання з неперервними та дискретними змінними з повторюваними вимірюваннями. Шаблон:Ref-en
• Сергей Николенко. Лекции № 8 Шаблон:Webarchive, № 9 Шаблон:Webarchive и № 10 Шаблон:Webarchive, посвященные байесовским сетям доверия. Курс «Самообучающиеся системы» Шаблон:Ref-ru