ML: Логіка та ймовірність. Частина II
Вступ
Формальна логіка є частковим випадком теорії ймовірностей. Цей документ є безпосереднім продовженням вступу до логіки і формальних теорій. Тепер ми обговоримо яким чином, за допомогою теорії ймовірностей, можна узагальнити бінарну логіку на випадок імовірнісних моделей.
Вивід у теорії ймовірностей
Обмежимося спочатку логічними теоріями, сигнатура яких містить тільки висловлювання. Будемо їх інтерпретувати як події. Підкреслимо, що на відміну від багатозначної або нечіткої логік, у розглядуваній тут імовірнісній логіці справедливий закон виключення третього. Це означає, що будь-яке висловлювання вважається або істинним або хибним (подія або відбудеться, або не відбудеться). Однак іноді ми здатні вказати тільки ймовірність того чи іншого значення.
Великими літерами у теорії ймовірності зручно позначати подію $A$, а малими $\{a,\bar{a}\}$ - її "значення" (відбулося, не відбулося). Таке узгодження дозволяє одноманітно розглядати події і випадкові величини, що приймають більше двох значень. Слід відрізняти позначення в яких $P(A)$ - ймовірність того, що подія відбулася, а $P(\bar{A})=1-P(A)$ - що не відбулася, від узгоджень в яких $P(A)$ - цей вектор з компонентами $\{P(a),P(\bar{a})\}$, а умовна $P(A\to B)$ або спільна $P(A,B)$ ймовірності - це матриці 2x2. Тепер запис $P(\bar{A})=1-P(A)$ означає дві формули $P(\bar{a})=1-P(a)$ і $P(a)=1-P(\bar{a})$, оскільки для подій вважаємо, що $\bar{\bar{a}}=a$.
Наділимо множину інтерпретацій "метрикою", присвоївши кожній інтерпретації
деяку ймовірність.
Ймовірність будь-якої формули дорівнює сумі ймовірностей інтерпретацій з області її істинності.
Крім цього, будемо вважати, що сумарна ймовірність інтерпретацій,
що задовольняють даній формальній теорії (всі її моделі) дорівнює одиниці. Відповідно,
ймовірності інших інтерпретацій у цій теорії рівні нулю.
Справа на рисунку зафарбована область (перетин областей істинності аксіом $A_1,A_2$) містить інтерпретації, сума ймовірностей яких дорівнює одиниці. Інтерпретації в незафарбованих областях мають нульові ймовірності. У результаті, кожна аксіома і вивідна в логіці з них теорема має одиничну ймовірність: $P(A_1)=P(A_2)=P(T)=1$. Тому, щоб з'ясувати, чи є твердження істинним у даній теорії, необхідно знайти його ймовірність.
Правила виводу
Нагадаємо, що ймовірність події $B$ за умови, що відбулася подія $A$, ми позначаємо на логічний манер, як $P(A\to B)$, замість загальноприйнятого $P(B\,|\,A)$. Спільна ймовірність настання двох подій позначається як $P(A\,\&\,B)$ або просто $P(A,\,B)$. Розглянемо кілька прикладів стандартних логічних виводів у термінах теорії ймовірностей.
✒ У логіці імплікацію $A\to B$ можна замінити на диз'юнкцію $\bar{A}\vee B$ і навпаки.
У теорії ймовірностей
виконується така рівність: $P(A)\,(1-P(A\to B)) = 1-P(\bar{A}\vee B)$.
Тому при будь-яких $A=\{a,\bar{a}\}$ і $B=\{b,\bar{b}\}$ і $P(A)\gt 0$
справедливий двосторонній вивід:
$$
P(A\to B) = 1 ~~~~~~~~~~~~~~\Leftrightarrow~~~~~~~~~~~~~P(\bar{A}\vee B) = 1.
$$
Нагадаємо також, що, в силу визначення умовної ймовірності, при цьому $P(A,B)=P(A)$,
що відразу призводить до $P(A,\bar{B})=0$, див. рисунок справа.
Це означає, що решта клітинок (інтерпретацій) у сумі мають одиничну ймовірність,
а вони рівні $\bar{A}\vee B$, що є об'єднанням першого рядка ($\bar{A}$) і другої колонки ($B$).
✒
Аналогічно правило обернення імплікації:
$
A\to B~~\Rightarrow~~\bar{B}\to \bar{A}
$
мовою теорії ймовірностей має вигляд:
$$
P(A\to B) = 1~~~~~~~~~~~~~\Leftrightarrow~~~~~~~~~~~P(\bar{B}\to \bar{A}) = 1.
$$
Для доведення можна скористатися попереднім правилом або отримати
$P(\bar{B}\to\bar{A})=1$ від супротивного, показавши, що $P(\bar{B}\to A)=0$:
$$
P(\bar{B})\,P(\bar{B}\to A) = P(A,\bar{B}) = P(A)\,P(A \to \bar{B}) = 0,
$$
де $P(A \to \bar{B})=0$ за формулою повної ймовірності з $P(A \to B)=1$.
Оскільки в логіці і в теорії ймовірностей для подій $\bar{\bar{A}}=A$, $\bar{\bar{B}}=B$,
цей вивід можна вважати двостороннім. Ще один спосіб доведення - це
використання того факту, що при $P(A\to B)=1$ у просторі випробувань
$A\subseteq B$, звідки очевидно, що $\bar{B}\subseteq \bar{A}$.
Завдяки цьому правилу, якщо відомо, що для конкретних значень
$P(a\to \bar{b})=1$, то і $P(\bar{a}\to b)=1$.
При цьому, за формулою повної ймовірності, решта значень рівні нулю: $P(a\to b)=P(\bar{a}\to \bar{b})=0$.
Таким чином, одинична умовна ймовірність фіксує умовні ймовірності для всіх інших значень.
✒ Ще одне двостороннє наслідок $C\to A,~C\to B~~~~\Leftrightarrow~~~~C\to A\,\&\,B~~$ має вигляд:
$$
P(C\to A) = P(C\to B) = 1 ~~~~~~~~~~~~~~\Leftrightarrow~~~~~~~~~~~~~P(C \to A,B) = 1.
$$
Справа-наліво воно доводиться за допомогою формули повної ймовірності. Оскільки $P(C\to A,B)=1$, то
$$
P(A,B,C) = P(C)= P(A,B,C) + P(A,\bar{B},C) + P(\bar{A},B,C) + P(\bar{A},\bar{B},C).
$$
Оскільки всі ймовірності невід'ємні, звідси випливає, що
$P(A,\bar{B},C)=P(\bar{A},B,C)=P(\bar{A},\bar{B},C)=0$ або $P(\bar{B},C)=P(\bar{A},C)=0$.
Тому $P(C)=P(A,C)+P(\bar{A},C)=P(A,C)$ і аналогічно $P(C)=P(B,C)$.
Слідування зліва-направо отримується аналогічно з $P(A,C)=P(C)$, $P(B,C)=P(C)$, розписуванням за формулою повної ймовірності правих і лівих частин.
✒ Односторонній вивід modus ponens $A,~A\to B~~\Rightarrow~B$:
$$
P(A)=P(A\to B)=1~~~~~~~~~~~\Rightarrow~~~~~~~~~~~P(B)=1
$$
доводиться за допомогою повної ймовірності $P(B)=P(A,B)+P(\bar{A},B)=1 + P(\bar{A},B)\le 1$,
де враховано, що засновки дають $P(A,B)=1$. Оскільки ймовірності невід'ємні, отримуємо $P(B)=1$.
На рисунку наведено графічний вивід. Оскільки $P(A,B)=P(A)=1$ маємо $P(A,\bar{B})=0$, $P(A,B)=1$.
Тому і у верхньому рядку стоять нулі. Ненульова область істинності є підмножиною
істинності $P(B)=1$ (друга колонка).
✒ Крім виводу modus ponens,
у формальній логіці існує безліч інших нетривіальних
способів отримання нових істинних формул.
Дуже потужним методом, широко використовуваним у машинному виводі,
є правило резолюції:
$$
A\vee C,~~~B\vee\bar{C}~~~~\Rightarrow~~~~A\vee B
$$
(засновки істинні, тому, якщо $C\equiv \F $, тоді $A\equiv \T $,
якщо ж $C\equiv \T $, то $B\equiv \T $, і в будь-якому випадку $A\vee B\equiv \T $).
Доведемо це правило за допомогою перелічення інтерпретацій:
Аналогічно варто перевірити справедливість виводу, що використовує властивість транзитивності імплікації: $ A\to B,~B\to C~~\Rightarrow~~A\to C, $ якому відповідають ймовірності: $$ P(A\to B) = P(B\to C) = 1 ~~~~~~~\Rightarrow~~~~~~~~P(A\to C) = 1. $$ Втім, воно також відразу випливає з методу резолюції.
Знову про Алісу і Боба
✒ Розглянемо імовірнісний логічний вивід у теорії про Алісу і Боба. Запишемо її аксіоми $(\mathbf{A_1})-(\mathbf{A_3})$ у вигляді: $$ P(l\to \bar{a}\vee \bar{b}) ~=~ P(\bar{l}\to a) ~=~ P(\bar{l}\to b) ~=~ 1. $$ Звернімо увагу, що в логіці аксіоми типу $\bar{L}\to A$ істинні при будь-яких значеннях висловлювань $L,\,A$ з області істинних інтерпретацій даної теорії. У теорії ймовірностей їх необхідно використовувати при "семантично вірних" конкретних значеннях, як записано вище. У протилежному випадку співвідношення $P(\bar{L}\to A)=1$ призводило б до суперечності: $P(\bar{L}\to a)=P(\bar{L}\to \bar{a})=1$ при $A=a$ і $A=\bar{a}$.
Застосовуючи правило обернення імплікації, можна відразу отримати:
$$
P( a,b \to \bar{l}) ~=~ P(\bar{a}\to l) ~=~ P(\bar{b}\to l) ~=~ 1,
$$
а з формули повної ймовірності, маємо (великі $A$, $B$ означають будь-яке значення):
$$
P(a,b,l)~=~P(\bar{a},B,\bar{l})~=~P(A,\bar{b},\bar{l}) ~=~ 0.
$$
Таким чином, аксіоми дозволяють зафіксувати нульові спільні ймовірності $P(A,B,L)$,
представлені в таблиці справа (ймовірності інтерпретацій), але не дають значення "позалогічних ймовірностей"
у порожніх клітинках. Відомо тільки, що їх сумарна ймовірність дорівнює одиниці.
Однак, логічні виводи із засновків, можна проводити як і в булевій логіці. Доведемо, наприклад, що з $A=a$ і $L=l$ випливає $B=\bar{b}$. Для цього скористаємося методом від супротивного. Якщо $P(a,l\to \bar{b})=1$, то за формулою повної ймовірності повинні мати $P(a,l\to b)=0$. Дійсно: $$ P(a,l \to b) = \frac{P(a,b,l)}{P(a,l)} = 0. $$
✒ Теорія ймовірностей більш гнучка порівняно з булевою логікою,
оскільки дозволяє виражати також не одиничні ймовірності.
Наприклад, нехай відомо, що Аліса у вітальні буває частіше Боба, і ймовірність
застати кого-небудь у вітальні дорівнює $1/3$:
$$
P(l\to \bar{a}, b) = \frac{1}{2},~~~~~~~~
P(l\to a, \bar{b})=\frac{1}{4},~~~~~~~~
P(l\to \bar{a}, \bar{b})=\frac{1}{4},~~~~~~~~~~P(\bar{l})=\frac{1}{3}.
$$
Разом з аксіомами, цієї інформації достатньо, щоб відповісти на будь-яке питання.
Відповідні спільні ймовірності наведені в таблиці справа.
Наприклад, у бінарній логіці з $L,\bar{A}$ не можна вивести, ні $B$, ні його заперечення $\bar{B}$. Дійсно, якщо у вітальні хтось є ($L$) і Аліса не у спальні, то Боб може бути, як з нею, у вітальні, так і у своїй спальні (повірте, що множина істинності $L\,\bar{A}$ не є підмножиною ні $B$, ні $\bar{B}$). У теорії ймовірностей однозначного виводу зробити, звичайно, також не можна, але допустимо імовірнісне міркування: $$ P(l,\bar{a}\to b) = \frac{P(\bar{a}, b, l)}{P(\bar{a},l)} = \frac{1/3}{1/2} = \frac{2}{3}. $$ В інтервальній логіці можливе отримання ще сильніших результатів в умовах невизначеностей.
Ймовірності предикатів
На завершення коротко розглянемо формальну теорію, побудовану за допомогою предикатів. Як і вище, будемо вважати, що ймовірність аксіоми виду $\forall_x \,A(x)$ дорівнює одиниці. Якщо ймовірність кон'юнкції дорівнює одиниці, то одиниці рівні ймовірності кожного аргументу кон'юнкції: $$ P(A(x_1)\,\&\,A(x_2)\,\&\,...) = 1~~~~~~~~~~\Rightarrow~~~~~~~~~~~~\forall_x \,[\,P\bigr(A(x)\bigr)= 1\,]. $$ Таким чином, теореми $\forall_x\, A(x)$ бінарної логіки предикатів мають одиничні ймовірності $P\bigr(A(x)\bigr)=1$ для будь-якого предмета теорії.
◊ Розглянемо як приклад відношення $(x\,\text{in}\,y)$ зі звичайних знань: об'єкт $x$ знаходиться всередині об'єкта $y$. Воно задовольняє таким аксіомам строгого деревного порядку (квантори загальності опущені): $$ \begin{array}{lll} \neg(x~\text{in}~x) & ~~~~~~ & (1) & \text{антирефлексивність}\\ (x~\text{in}~z)\,\&\,(z~\text{in}~y)~\to~(x~\text{in}~y) & & (2) & \text{транзитивність}\\ (z~\text{in}~x)\,\&\,(z~\text{in}~y)~\to~(x~\text{in}~y)\vee(y~\text{in}~x)\vee(x=y) & & (3) & \text{деревність} \end{array} $$
З антирефлексивності і транзитивності випливає асиметричність відношення: $$ \begin{array}{lll} (y~\text{in}~x)~\to~\neg (x~\text{in}~y) &~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ & (4) & \text{асиметричність}\\ \end{array} $$ Доведемо це за допомогою імовірнісних методів. Для будь-яких об'єктів з перших двох аксіом маємо такі співвідношення між ймовірностями: $$ P(x~\text{in}~x) = 0,~~~~~~~~~~~~~~~P(x~\text{in}~z,~z~\text{in}~y) = P(x~\text{in}~y). $$ Покладаючи $y=x$, отримуємо: $$ P(x~\text{in}~z,~z~\text{in}~x)=0~~~~~~\Rightarrow~~~~~ P\bigr(\,\neg(x~\text{in}~z~\,\&\,~z~\text{in}~x)\,\bigr)=P\bigr(\,\neg(x~\text{in}~z)\vee\neg(z~\text{in}~x)\,\bigr)=1. $$ Звідси, за правилом одиничності імплікації, отримуємо асиметричність: $P\bigr(\,(x~\text{in}~z)~\to~ \neg(z~\text{in}~x)\,\bigr)=1$.
