ML: Інтервальна ймовірнісна логіка

Вступ

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

Кілька прикладів

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

Розглянемо кілька прикладів тверджень про подібні події.

1. Ймовірність. Твердження "Монета, яку зараз підкинуть, впаде гербом угору" традиційно відносять до теорії ймовірностей. Якщо монета чесна (симетрична) і її кидають чесно ("випадково"), то твердження $A$ наділяється властивою йому числовою характеристикою $P(A)=1/2$, що називається ймовірністю події $A$. Практично це число вимірюване лише за великої кількості повторів, та й то за припущення постійності "справжньої" ймовірності. Відхід від "чистої" теорії ймовірностей починається, якщо ми бачимо цю монету вперше і вона знаходиться в руках сумнівного суб'єкта.

2. Невизначеність. "У кімнаті знаходиться кіт". Хоча кіт уже знаходиться (або не знаходиться) у кімнаті, це твердження виявиться істинним або хибним у майбутньому (до кімнати необхідно зайти). Якщо ми вперше в цій кімнаті, то істинність твердження не визначена (кіт там може бути, а може його там і не бути).
Цю невизначеність важливо відрізняти від ймовірності $P(A)=1/2$ у випадку монети, оскільки в нас немає причин вважати знаходження кота в кімнаті рівноймовірною подією. Звичайно, якщо ця кімната наша і в нас немає кота, невизначеність знижується, хоча й не повністю (наприклад, якщо йдучи ми забули зачинити вікно).

3. Переконаність. "Графа, швидше за все, убив дворецький; у нього був мотив і немає алібі". Подія вбивства вже сталася, причому, на відміну від монети, вона принципово неповторювана. Тим не менш, подібні прецеденти в минулому (з іншими злочинами) дозволяють висловлювати деякі судження.
Спочатку, за повної відсутності інформації (ніхто не бачив самого злочину), не можна дати однозначну оцінку істинності твердження. У міру появи сукупності доказів і мотивів можна надавати доводи за і проти істинності цього твердження, зменшуючи його невизначеність.

4. Унікальність. "У цьому столітті Земля зіткнеться з Місяцем" — це подія, як і всі попередні, або станеться, або ні. Однак вона унікальна і чисто ймовірнісні міркування не годяться. Водночас її не можна вважати повністю невизначеною, оскільки ми маємо накопичений досвід, на підставі якого ця подія здається малоймовірною. На відміну від ситуації з дворецьким, такий досвід може лише спростовувати істинність, але не підтверджувати її (у нас є досвід того, що зіткнень не було, але не того, що вони були).

5. Оцінка. "Ця кава міцна і гаряча", "Маша красива і сильна", "Стара машина їде швидко" — це усі оціночні судження, пов'язані з нечіткими множинами ("чашки кави різної температури", "множина красивих жінок" тощо). На відміну від попередніх прикладів, у яких твердження "насправді" або істинне, або хибне, тут закон виключення третього $A\vee \neg A ~=~ \mathbb{T}$ (істина) не працює. Про такі оціночні твердження може бути відомо все, але тим не менш їх не можна вважати ані істинними, ані хибними. Оціночні судження можуть комбінуватися з ймовірнісними: "Завтра, швидше за все, піде сильний дощ".

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

Ймовірність істинності

Далі, якщо це не призводитиме до неоднозначності, замість ймовірності $P(A)$ події будемо просто писати $A$, аналогічно $A\,\&\,B$ замість $P(A\,\&\,B)$ тощо. Крім цього, використовуватимуться два способи опису істинності твердження $A$ про деяку подію або процес.

Точкова міра $A$, як зазвичай, означає ймовірність того, що подія відбудеться (або вже відбулася).
Чим ближче $A$ до одиниці, тим "істинніше" твердження. Заперечення $\neg A$ або $\bar{A}$ твердження $A$ має ймовірність: $$ \bar{A}=1-A. $$ При цьому передбачається виконання тотожностей теорії ймовірності $A\vee B=A+B-(A\,\&\,B)$ і всіх тотожностей булевої алгебри: $\neg(A\,\&\,B) = \bar{A}\vee \bar{B}$ тощо, включно із законом виключення третього $(A\,\&\,\bar{A})=0$.

Інтервальна оцінка — це другий спосіб задання ступеня істинності твердження $A$. Нижню межу інтервалу позначимо як $a$, а верхню — як $1-\bar{a}$: $$ A=[a,\,1-\bar{a}],~~~~~~~~~~a~\le~A ~\le~ 1-\bar{a},~~~~~~~~a+\bar{a}~\le~1, $$ де остання нерівність означає, що верхня межа не повинна бути меншою за нижню. Коли $a+\bar{a}=1$, ймовірність події повністю визначена. І навпаки, при $a=\bar{a}=0$, тобто $A=[0,~1]$ — значення ймовірності невизначене. Інтервальна оцінка дозволяє відрізняти ймовірнісне, але визначене судження $A=[0.5,\,0.5]$ (підкидання монети) від невизначеного $A=[0,\,1]$ (кіт у невідомій кімнаті).

Враховуючи, що завжди $\bar{A}=1-A$, для інтервалу ймовірності істинності заперечення слід написати: $$ \bar{A}=[\bar{a},\,1-a]. $$ Інтервали висловлювання та його заперечення можуть не перетинатися ($a+\bar{a} \gt 0.5$) — більш визначена ситуація, або перетинатися (якщо $a+\bar{a} \le 0.5$) — менш визначена:

На площині $(A,\bar{A})$ можливі значення ймовірностей твердження та його заперечення знаходяться на відрізку, зображеному на рисунках жирною лінією.

Детективна гіпотеза "Графа вбив дворецький" на початку розслідування має невизначену істинність $[0,\,1]$. У міру розслідування вона може підкріплюватися фактами за ($a$), так і спростовуватися при появі фактів проти ($\bar{a}$). Звичайно, навіть при усуненні невизначеності $(a+\bar{a}=1)$, отримане число є лише ймовірністю істинності минулої або майбутньої події. Якщо дворецький убив графа з імовірністю $A=0.75$, це означає, що в чверті "паралельних всесвітів" він не винний. Чи варто його засуджувати в нашому всесвіті?

Множина гіпотез

При розгляді твердження $A$ та його заперечення $\bar{A}$ ми бачили, що їхні інтервали не можуть бути довільними і визначаються двома ($a$, $\bar{a}$), а не чотирма параметрами. У загальному випадку, нехай є множина $\mathbb{H}=\{H_1,...,H_n\}$ несумісних подій $H_i\,\&\,H_j = 0$ при $i\neq j$ (гіпотез), які утворюють розбиття простору випробувань (у кожному випробуванні відбувається рівно одна з $\mathbb{H}$). У цьому випадку: $$ H_1+...+H_n = 1,~~~~~~~~~~h_i \le H_i \le 1-\bar{h}_i,~~~~i=1...n $$ і умови несуперечливості сукупності пар $(h_i,\,\bar{h}_i)$ для меж інтервалів складніші. Один із підходів до задоволення цих обмежень був запропонований у теорії Демпстера-Шафера.

Опишемо інший, простіший спосіб.
Зафіксуємо значення нижніх меж гіпотез $\mathbf{h}=\{h_1,...,h_n\}$, так, щоб їхня сума не перевищувала одиниці. У векторних позначеннях таку суму можна виразити за допомогою вектора з одиничними компонентами $\mathbf{t}=\{1,...,1\}$ (це координати вершини $n$-вимірного одиничного куба, що знаходиться "навпроти" початку координат): $$ \mathbf{h}\,\mathbf{t} ~=~ \sum^n_{i=1} h_i ~\le~ 1. $$ Вектор "справжніх" (але невідомих) імовірностей $H_i$ гіпотез задовольняє рівнянню площини $\mathbf{H}\mathbf{t}=1$. Оскільки $\mathbf{t}^2=n$, нескладно бачити, що точка $$ \mathbf{h}' = \mathbf{h} + \frac{1-\mathbf{h}\,\mathbf{t}}{n}\,\mathbf{t} $$ також лежить у цій площині ($\mathbf{h}'\mathbf{t}=1$). Якщо зсунутися на подвійний вектор $\mathbf{h}'-\mathbf{h}$, ми опинимося з протилежного боку площини на такій же відстані (див. рисунок для $n=2$). Ця точка і визначатиме верхню межу інтервалів істинності гіпотез: $$ H_i = [h_i,~h_i+\frac{2}{n}\,(1-\mathbf{h}\,\mathbf{t})]. $$

Розглянемо як приклад $n=4$ гіпотези. Нехай $\mathbf{h}=\{0.0,~0.2,~0.2,~0.4\}$, тоді $\mathbf{h}\mathbf{t}=0.8$ і узгоджені інтервали ймовірностей істинності гіпотез дорівнюють: $$ H_1=[0.0,\,0.1],~~~H_2=[0.2,\,0.3],~~~H_3=[0.2,\,0.3],~~~H_4=[0.4,\,0.5]. $$

Кон'юнкція, диз'юнкція та імплікація

Нехай задані точкові значення ймовірностей $A$ і $B$ двох подій і більше про них нічого не відомо.
Тоді інтервали для логічного І (кон'юнкції) і логічного АБО (диз'юнкції) у теорії ймовірностей дорівнюють:

$$ \begin{array}{lccclcccccc} \max[0,~A+B-1]&\le& A\,\&\,B &\le& \min[A,\,B]\\[2mm] \max[A,\,B]&\le& A\vee B &\le&\min[1,~A+B] \end{array} $$

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

У бінарній логіці імплікація $A\to B$ хибна для $\mathbb{T}\to \mathbb{F}$ (з істини не можна отримати хибу) і істинна в інших випадках. Крім цього, вона виражається через диз'юнкцію та заперечення: $A\to B~~\equiv~~\bar{A} \vee B.$

$W$ $\bar{W}$ Tot
$B$ 8 2 10
$\bar{B}$ 32 58 90
Tot 40 60 100
У ймовірнісній логіці імплікацією можна вважати, або умовну ймовірність $P(A\to B)$,
або ймовірність події $P(\bar{A} \vee B)$. У загальному випадку завжди $P(A\to B) \le P(\bar{A} \vee B)$. Тому вибір одного з варіантів призводить, взагалі кажучи, до різних результатів. У прикладі з розумними блондинками, для правила

$B\to W$ : "якщо хтось є блондинкою, то вона розумна",
маємо: $P(B\to W)=0.8$ і $P(\bar{B} \vee W) = 0.98$. Інтуїтивно більш підходящим здається перший результат. Далі вважатимемо, що імплікацію виражає умовна ймовірність. Символ ймовірності, як і раніше, опускатиметься, тобто $A\to B$ позначає число або, у загальному випадку, інтервал всередині відрізка $[0...1]$.

З визначення $P(A\to B)=P(A,B)/P(A)$, за відомих точкових ймовірностей $A$, $B$ (і за відсутності іншої інформації), маємо $$ \max\bigr[0,~1-\frac{1-B}{A}\bigr]~~~~~~~\le~~~~A\to B~~~~\le~~~~~~\min\bigr[1,~B/A\bigr]. $$ Верхня межа цього інтервалу збігається з визначенням імплікації Гогена у багатозначній логіці.

Інтервальні співвідношення

Якщо відомі лише інтервальні ймовірності $A=[a,~1-\bar{a}]$, $B=[b,~1-\bar{b}]$ і іншої інформації немає, то інтервали для кон'юнкції та диз'юнкції мають вигляд: $$ \begin{array}{lclclcccccc} A\,\&\,B &=& \bigr[ \max(0,~a+b-1) &,& 1-\max(\bar{a},\,\bar{b})\bigr]\\[2mm] A\vee B &=& \bigr[ \max(a,b) &,& 1-\max(0,~\bar{a}+\bar{b}-1)\bigr]\\[2mm] \end{array} $$

Для нижньої межі інтервалу імплікації $P(A\to B)=P(A\,\&\,B)/P(B)$ необхідно взяти мінімальну кон'юнкцію $A\,\&\,B$ і максимальну ймовірність $A$. Для верхньої межі — навпаки (але не перевищуючи $1$): $$ \begin{array}{lclclcccccc} A\to B &=& \Bigr[ \max\Bigr(0,~\displaystyle\frac{a+b-1}{1-\bar{a}}\Bigr),~~~ 1- \max\Bigr(0,~ 1+\frac{\max(\bar{a},\,\bar{b})-1}{a}\Bigr)\Bigr]. \end{array} $$

Інтервали для кон'юнкції та диз'юнкції нескладно отримати зі співвідношень попереднього розділу. Можливі також такі корисні міркування.

Уявімо, що існує велика кількість рівноймовірних елементарних подій $\mathbb{E}=\{E_1,...,E_n\}$.
Будь-яка подія $A$ є об'єднанням деякої частини елементарних подій (підмножина множини $\mathbb{E}$). Запишемо це у вигляді послідовності $A=(01110?1??011)$ довжини $n$, де наявність $1$ на $i$-тому місці означає, що $E_i\in A$, а $0$ — що $E_i\not\in A$. Знак питання позначає факт невизначеної належності (невідомо $E_i\in A$ чи $E_i\not\in A$). Число відомих одиниць дорівнює $a\cdot n$, а число відомих нулів $\bar{a}\cdot n$, тому $A = [a,~1-\bar{a}]$.
Якщо питань немає, то це точкова, однозначна ймовірність $a+\bar{a}=1$ (монета). Якщо ж уся послідовність складається з питань, то ймовірність $A=[0,\,1]$ повністю невизначена (кіт у кімнаті).

Нехай для подій відомі лише $(\bar{a},a)$, $(\bar{b},b)$, а порядок символів $0,1,?$ у послідовностях невідомий. Мінімальне значення їхньої кон'юнкції буде, коли всі $?=0$ (рівно $a\cdot n$ одиниць) і одиниці обох послідовностей максимально не перетинаються. Максимальне значення кон'юнкції отримується, коли $?=1$ (рівно $\bar{a}\cdot n$ нулів) і послідовності максимально перетинаються на одиницях: $$ \min(A\,\&\,B) = \begin{array}{lclll} ~\overbrace{1...111}^{a}\,\overbrace{0...0}^{1-a}\\ ~\underbrace{0...0}_{1-b}\,\underbrace{1...111}_{b} \end{array} =\max(0,~a+b-1), ~~~~~~~~~~~~ \max(A\,\&\,B) = \begin{array}{lclll} ~\overbrace{1...11}^{1-\bar{a}}\,\overbrace{0...0}^{\bar{a}}\\ ~\underbrace{1...111}_{1-\bar{b}}\,\underbrace{0...0}_{\bar{b}} \end{array} =\min(1-\bar{a},\,1-\bar{b}). $$

Звичайно, будь-яка значуща інформація зменшує ступінь невизначеності. Наприклад, якщо відомо, що події незалежні $P(A,B)=P(A)\,P(B)$, то $$ A\Prep B:~~~~~~~A\,\&\,B = [a\cdot b,~~~(1-\bar{a})\cdot(1-\bar{b})]. $$

В апріорному припущенні рівноймовірності положення символів $0,1,?$ у послідовності можна отримати ймовірність розподілу "справжнього значення" $P(A)$ в інтервалі $A=[a,~1-\bar{a}]$.

Логічний висновок

У бінарній логіці з $P$ логічно випливає $Q$, якщо завжди, коли формула $P$ істинна, то істинна й формула $Q$. Це позначається так: $P\Rightarrow Q$. Логічний висновок — це спосіб отримання одних істинних формул з інших, також істинних. Не варто плутати висновок і імплікацію $P\to Q$, яка є логічною зв'язкою, що набуває значень $0$ або $1$.

Висновок modus ponens: $A,~A\to B ~~\Rightarrow~~ B$ у булевій логіці означає, що якщо істинне твердження $A$ і з $A$ випливає $B$ (імплікація), то можна вважати істинним (і вивідним) твердження $B$.

В інтервальній ймовірнісній логіці, крім зазначення правила висновку, необхідно також знати інтервал істинності для вивідної формули. Нехай відомо, що $A~=~[a,~1-\bar{a}]$ і $A\to B~=~[r,~1-\bar{r}]$ Використовуючи тотожність повної ймовірності, можна написати: $$ P(A)\cdot P(A\to B) = P(A,B) ~~~~\le~~~ P(B)~~~~ \le~~~ 1. $$ З іншого боку $\min\bigr(A\cdot (A\to B)\bigr) ~=~ a\cdot r$, тому modus ponens виглядає таким чином: $$ A~=~[a,~1-\bar{a}],~~~A\to B~=~[r,~1-\bar{r}]~~~~~~~~~~~\Rightarrow~~~~~~~~~~B~=~[a\cdot r,~1]. $$

Якщо $r=1$, то $B=[a,~1]$. Графічно це очевидний результат. Якщо завжди, коли відбувається подія $A$, також відбувається й подія $B$, тобто умовна ймовірність $P(A\to B)=1$. Це означає, що подія $A$ є підмножиною події $B$. У просторі випробувань мінімально можлива площа $B$ не менша за площу $A$ (рисунок праворуч).

◊ Розглянемо як приклад завжди істинне правило $(R\, \&\,F \to W)~=~[1,1] $ з такою інтерпретацією:
"Якщо завтра піде дощ ($R$) і я забуду парасольку ($F$), то я змокню (W)".
Будемо вважати заданими істинності тверджень у засновку $R~=~[0.6,\,0.8]$, $F=[0.9,\,0.9]$.
1) Якщо зв'язок між цими двома подіями невідомий, для обчислення їхньої кон'юнкції необхідно користуватися загальною формулою: $$ R\,\&\,F ~=~ [0.6+0.9-1,~~~1-\max(0.2,0.1)]~=~[0.5,~0.8],~~~~~~\Rightarrow~~~~~~W=[0.5,~1]. $$ 2) Якщо ж відомо, що події дощу та забування парасольки незалежні, оцінка для інтервалу ймовірності $B$ виходить трохи вужчою: $$ R\,\&\,F~=~R\cdot F ~~=~~ [0.6\cdot 0.9,~0.8\cdot 0.9] ~~~=~~~ [0.54,~0.72]~~~~~~~\Rightarrow~~~~~~~W=[0.54,~1]. $$

Приклад: Шкатулка і скриня

Розглянемо світ прямокутних закритих ящиків із завжди істинною аксіомою

$(Y \lt X) ~\to~ \neg(X~\text{in}~Y)$: "якщо ящик $Y$ менший за ящик $X$, то ящик $X$ не може знаходитися всередині ящика $Y$".
Нехай є два види ящиків — шкатулки і скрині. Шкатулки зазвичай менші за скрині (хоча іноді бувають дуже маленькі скриньки). Можливі також непорівнянні шкатулки і скрині (наприклад, вузькі-високі шкатулки і широкі-низькі скрині). Тому нехай: $$ P(ш \lt с) = 0.8,~~~~~~~~~~P(с \lt ш) = 0.1. $$ За допомогою modus ponens отримуємо: $$ \left\{ \begin{array}{lll} P(с~\neg\text{in}~ш) ~=~ [0.8,~ 1] \\ P(ш~\neg\text{in}~с) ~=~ [0.1,~1] \end{array} \right. ~~~~~~~\Rightarrow~~~~~~~ \left\{ \begin{array}{lll} P(с~\text{in}~ш) ~=~[0,~ 0.2]\\ P(ш~\text{in}~с) ~=~[0,~ 0.9] \end{array} \right. $$

Таким чином твердження "шкатулка знаходиться у скрині" має інтервальну ймовірність: $[0,~0.9]$. У нас є невеликі ($\bar{a}=0.1=1-0.9$) сумніви, що шкатулка може знаходитися у скрині. Втім, немає жодних підкріплень гіпотези, що вона там знаходиться (може знаходитися, а може й ні). Для твердження "скриня знаходиться у шкатулці" обмеження на ймовірність суттєво жорсткіші.

Приклади висновків

Нехай є два істинні правила $$ A_1\to B,~~~~~ A_2\to B $$ і ймовірнісні точкові засновки $P(A_1),~P(A_2)$. Тоді (див. рисунок): $$ \left\{ \begin{array}{lll} A_1\to B\\ A_2\to B\\ \end{array} \right. ~~~~~~~~~~~\Rightarrow~~~~~~~~~~P(A_1\vee A_2)~\le~ P(B)~\le~ 1. $$ У випадку, якщо засновки незалежні, то $B = [a_1+a_2-a_1a_2,~~1].$
Розглянемо два істинні правила $$ A_1\,\&\,\bar{A}_2\to B,~~~~~~~ A_2\,\&\,\bar{A}_1\to \bar{B}. $$ У булевій логіці засновки не можуть бути одночасно істинними, інакше буде отримано суперечність: $B,\,\bar{B}$. Це враховано в кон'юнкціях засновків. У даному випадку маємо: $$ b = \min B = \min(A_1\,\&\,\bar{A}_2),~~~~~~~~ \bar{b}~=~\min \bar{B} = \min(\bar{A}_1\,\&\,A_2). $$ Якщо твердження $A_1, A_2$ незалежні, то для $B$ маємо інтервальну оцінку: $[a_1\,(1-a_2),~1-(1-a_1)\,a_2]$, тобто відмінні від нуля обидві межі інтервалу.

Якщо відомо, що $A\to B$ і істинним є $B$, то в класичній логіці вивести $A$, взагалі кажучи, не можна. Тим не менш, інформація про $B$ повинна якось вплинути на наші висновки. У ймовірнісній логіці це відповідає апостеріорній зміні ймовірності твердження $A$ за формулою Баєса: $$ P(B\to A) = P(A\to B)\,P(A)/P(B). $$