ML: Висновок у ймовірнісних моделях

Вступ

Навіть якщо $n$ випадкових величин бінарні, для задання їхньої спільної ймовірності потрібно $2^n-1$ чисел, що при великих $n$ стає проблематичним у обчислювальному відношенні і неможливим у практичному. Мережі довіри або баєсівські мережі — це графічні моделі, які дозволяють провести декомпозицію (спрощення) спільної ймовірності великої кількості випадкових величин.

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

Баєсівська мережа

Розглянемо функцію спільної ймовірності $P(X_1,...,X_n)$ для $n$ подій або випадкових величин $X_1,...,X_n$. Ланцюгове правило: $$ P(X_1,...,X_n) = P(X_1)\cdot P(X_1\to X_2)\cdot P(X_1,X_2\to X_3)\cdot....\cdot P(X_1,X_2,...,X_{n-1}\to X_n), $$ представимо у вигляді спрямованого ациклічного графа. Вузли графа — це випадкові величини, а стрілки, що входять у даний вузол, є умовами в ланцюговій тотожності. Оскільки в тотожності порядок аргументів у правій частині можна вибирати довільним чином, існує $n!$ різних графів, що описують спільну ймовірність. Нижче на першому рисунку наведено граф для $n=4$. Решту 23 графів отримують перестановками вузлів:

Якщо деякі випадкові величини є умовно незалежними, то граф спрощується (частина ребер зникає). Вище другий приклад наведено для випадку, коли $X_2$, $X_3$ умовно незалежні за наявності $X_1$, а для $X_4$ виконується $P(X_1,X_2,X_3\to X_4)=P(X_2,X_3\to X_4)$, тобто він умовно незалежний від $X_1$. Спільна ймовірність у цьому випадку має вигляд: $$ P(X_1,X_2,X_3,X_4) = P(X_1)\,P(X_1\to X_2)\,P(X_1\to X_3)\,P(X_2,X_3\to X_4). $$

Зазвичай мережа будується з міркувань безпосередніх причинних залежностей випадкових величин. Після того як вона побудована, у кожному вузлі задаються умовні ймовірності $P(X_1,...,X_k\to X)$, де $X_1,...,X_k$ — що входять у вузол $X$. Потім можна записувати спільну ймовірність як добуток усіх цих імовірностей. Маючи спільні ймовірності, можна отримати відповідь на будь-яке питання про складені або умовні події.

Фред і його сигналізація

Розглянемо класичний приклад. Нехай Фред із Каліфорнії встановив у своєму будинку сигналізацію, яка може спрацьовувати, якщо стався землетрус (Earthquake).
Він їде в машині і отримує повідомлення про тривогу (Alarm). Слухаючи радіо (Radio), він не чує повідомлення про землетрус (хоча його могли і не зробити). Яка ймовірність того, що в будинок заліз злодій (Burglar)? Відповідна баєсова мережа наведена праворуч (на сигналізацію безпосередньо може впливати грабіжник або землетрус, а на повідомлення по радіо — лише землетрус). Для цієї мережі спільна ймовірність дорівнює: $$ P(B,E,A,R) = P(B)\cdot P(E)\cdot P(B,E \to A)\cdot P(E\to R) = \frac{P(B,E,A)\,P(E,R)}{P(E)}. $$ Для її запису перемножуються всі вузли мережі. Якщо у вузол ребер не входить (вище $B$ і $E$), то множник дорівнюватиме ймовірності величини: $P(B) P(E)$. Для вузлів, у які входять ребра, множником служить умовна ймовірність, де умовами виступають величини, від яких ідуть ребра.

Фреду відомо, що сталася подія $A=a$ (була тривога) і $R=\bar{r}$ (по радіо не було повідомлення про землетрус). І його цікавить значення випадкової величини $B$ (злодій заліз у будинок): $$ P(a,\bar{r}\to B) = \frac{P(B,a,\bar{r})}{P(a,\,\bar{r})}. $$ Спільні ймовірності в чисельнику і знаменнику обчислюємо, підсумовуючи повну спільну ймовірність $P(B,E,A,R)$ за відсутніми змінними $E:\,\{e,\bar{e}\}$ і $B:\,\{b,\bar{b}\}$: $$ P(B,a,\bar{r}) = \sum_E P(B,E,a,\bar{r}),~~~~~~~~~~~~~P(a,\bar{r}) = \sum_{B,E} P(B,E,a,\bar{r}). $$ Якщо всі умовні ймовірності на графі відомі, нескладно отримати потрібну умовну ймовірність, підставляючи в ці співвідношення спільну ймовірність $P(B,E,A,R)$.

Зауважимо, що безумовно незалежними подіями в цій задачі очевидно є ($B$, $E$) і ($B$, $R$). Перша пара перевіряється підсумовуванням $P(B,E,A,R)$ по $R$ (сума $P(E\to R)$ дорівнює 1) і по $A$ (сума $P(B,E \to A)$ дорівнює 1). У результаті отримуємо $P(B,E)=P(B)\cdot P(E)$. Аналогічно доводиться незалежність $B$ і $R$: $$ P(B,R) = \sum_{E,A} P(B,E,A,R) = P(B)\cdot \sum_{E,A} P(E)\cdot P(B,E \to A)\cdot P(E\to R) = P(B)\cdot \sum_{E} P(E)\cdot P(E\to R) $$ і далі: $$ P(B,R) = P(B)\cdot \sum_{E} P(E, R) = P(B)\cdot P(R). $$

Типи баєсових мереж

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

Приклади з вилкою і колайдером були розглянуті при введенні умовної незалежності (морозиво і кидання кісток). Доведемо умовну незалежність для ланцюга. Відповідна їй спільна ймовірність дорівнює $P(X,Y,Z)~=~P(X)\,P(X\to Y)\,P(Y\to Z)=P(X,Y)\,P(Y\to Z)$. Тому $$ P(Y\to X,Z) = \frac{P(X,Y,Z)}{P(Y)} =\frac{P(X, Y)\,P(Y\to Z)}{P(Y)} = P(Y\to X)\,P(Y\to Z). $$

Дві множини вузлів мережі $\mathbb{A}$ і $\mathbb{B}$ є умовно незалежними за наявності множини вузлів $\mathbb{C}$, якщо всі шляхи між $\mathbb{A}$ і $\mathbb{B}$ розділені вузлами $\mathbb{C}$.

Баєсівська мережа називається причинною (казуальною), якщо в усіх її зв'язках $X_i\to X_j$ подія $X_i$ є причиною для появи події $X_j$. Задача з сигналізацією Фреда є прикладом такого графа.