ML: Вероятностная логика


Введение

При накоплении обыденных знаний в форме фактов и правил, человек редко использует бинарную логику.
Так как знание является обобщением опыта, степень его истинности носит вероятностный характер. Выводы из знаний, при помощи полученной информации, также делаются в условиях неопределённости. В этом документе рассмотрен вероятностный подход к логике. Предварительно имеет смысл ознакомится с основами вероятностных методов и формулой Байеса. Небесполезным будет также прочтение неформального введения в логику. Непосредственным продолжением данной темы является обсуждение нечёткой и интервальной логик.


Вероятность истинности

В бинарной логике любое утверждение $A$ либо истинно ($\mathbb{T}$), либо ложно ($\mathbb{F}$). В вероятностной логике каждое утверждение характеризуется вероятностью $P(A)$ его истинности. Для всегда истинного утверждения $P(\mathbb{T})=1$, а для ложного $P(\mathbb{F})=0$. Промежуточные значения основываются на статистике (objectivist interpretation) или вере данного субъекта (subjectivist interpretation).

Истинность отличная от $\mathbb{T},\mathbb{F}$ характерна для будущих утверждений $A:$ "Завтра будет дождь" или когда информация неполна - $A:$ "Графа убил дворецкий" (но этого никто не видел). Важно, что для таких событий выполняется закон исключения третьего: $P(A\vee \neg A)=1$, $P(A\,\& \,\neg A)=0$ т.е., либо "дождь будет", либо "дождя не будет" и третьего не дано. Эти утверждения отличаются от оценочных суждений типа: "Маша красивая" (но бывают и краше), "Кофе горячий" (но не кипяток) и т.п. Такими суждениями оперирует нечёткая логика.

Вероятностью отрицания утверждения $A$ будем считать: $$ P(\neg A)=1-P(A). $$ Как обычно, предполагается выполнение тождеств теории вероятности $P(A\vee B)=P(A)+P(B)-P(A\,\&\,B)$ и всех тождеств булевой алгебры: $P\bigr(\neg(A\,\&\,B)\bigr) = P\bigr(\neg A\vee \neg B)\bigr)$ и т.д.


Импликация

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

$W$ $\neg W$ Tot
$B$ 8 2 10
$\neg B$ 32 58 90
Tot 40 60 100
В вероятностной логике импликацией можно считать, либо условную вероятность $P(B|A)$,
либо вероятность события $P(\neg A \vee B)$. Эти варианты приводят, вообще говоря, к различным результатам. В примере с умными блондинками, для правила

$B\to W$: "если некто является блондинкой, то она умна",
имеем: $P(W|B)=0.8$ и $P(\neg B \vee W) = 0.98$. Интуитивно более подходящим кажется первый результат. Далее будем считать, что импликацию выражает условная вероятность: $P(A\to B)\equiv P(B|A)$.


Modus ponens

Вывод modus ponens: $A,~A\to B ~~\Rightarrow~~ A$ в булевой логике означает, что, если истинно утверждение $A$ и из $A$ следует $B$ (импликация), то можно считать истинным (и выводимым) утверждение $B$. В вероятностной логике по формуле полной вероятности имеем: $$ P(B) = P(A)\,P(A\to B) + P(\neg A)\,P(\neg A \to B). $$

Истинности как импликации $A\to B$, так и утверждения $A$ могут быть отличными от 1. Рассмотрим сначала случай истинного правила $P(A\to B)=1$ и вероятностной посылки $P(A) \le 1.$ Если значение $P(\neg A \to B)$ неизвестно, то можно получить только ограничение на вероятность $P(B)$: $$ ~~~~~~P(A)~\le~ P(B)~\le~ 1. $$ Графически это очевидный результат. Если всегда, когда происходит событие $A$ также происходит и событие $B$: $P(A\to B)=1$, то это означает, что событие $A$ является подмножеством события $B$. Минимально возможная площадь $B$ не меньше площади $A$ (рисунок справа). При другой информации для отрицания $B$ имеем $0~\le~ P(\neg B)~\le~ P(A)$.

Пусть есть всегда истинное правило $R\, \&\,F \to W $ с такой интерпретацией:

"Если завтра пойдёт дождь ($R$) и я забуду зонтик ($F$), то я намокну (W)".
Будем считать заданными истинности утверждений в посылке $P(R)=0.2$, $P(F)=0.5$ и предположим, что они независимы: $P(R\,\&\,F)=P(R)P(F) = 0.1$. Тогда истинность факта намокания не меньше $0.1$. Ложность этого утверждения больше нуля, но не более $0.1$.


Интервальная вероятность

Неопределённая ситуация, описанная в предыдущем разделе, вынуждает в ряде случаев характеризовать событие не одним, а двумя числами. Это могут быть минимальные значения ложности и истинности утверждения: $$ A:~~~\{a_0,a_1\}=\{\min P(\neg A),~\min P(A)\}. $$ Если $a_0+a_1=1$, то вероятность события определена. Когда $a_0=a_1=0$, т.е. $A:~[0,~0]$, то вероятность события полностью неопределена. Можно считать $a_1$ является степенью веры в истинность утверждения (оно будет доказано), а $a_0$ - степень веры в его ложность (будет опровергнуто $A$).

В примере вывода modus ponens $B:\{0,~P(A)\}$. Это означает, что не существует данных считать $B$ ложным, тогда как есть шанс $P(A)$ считать его истинным.

Детективное утверждение "Графа убил дворецкий" в начале расследования имеет неопределённую истинность $[0,\,0]$. По мере расследования оно может подкрепляться фактам за ($a_1$), так и опровергаться фактами против ($a_0$).


Примеры выводов

Пусть есть два истинных правила $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. $$ В случае, если посылки независимы $$ \min P(B) = P(A_1)+P(A_2)-P(A_1)P(A_2). $$ Таким образом истинность утвержения $B$ интервальная: $\{0,~p_1+p_2-p_1p_2\}$, где $p_i=P(A_i)$.
Рассмотрим два истинных правила $A_1\,\&\,\neg A_2\to B$, $A_2\,\&\,\neg A_1\to \neg B$. В булевой логике посылки не могут быть одновременно истинными, иначе будет получено противоречие: $B,\,\neg B$. Это учтено в конъюнкциях посылок. В данном случае имеем: $$ \min P(B) = P(A_1\,\&\,\neg A_2),~~~~~~~~\min P(\neg B) = P(\neg A_1\,\&\,A_2). $$ Если утверждения $A_1, A_2$ независимы, то для $B$ имеем интервальную оценку: $\{(1-p_1)p_2,~p_1\,(1-p_2)\}$, т.е. отличны от нуля обе границы интервала и $b_0+b_1=p_1+p_2 - 2p_1 p_2 \le 1$.

Если известно, что $A\to B$ и истинным является $B$, то в классической логике вывести $A$, вообще говоря, нельзя. Тем не менее, информация о $B$ должна как-то повлиять на наши выводы. В вероятностной логике это соответствует апостериорному изменению вероятности утверждении $A$ по формуле Байеса: $$ P(A|B) = P(B|A)\,P(A)/P(B). $$


Пример: Шкатулка и сундук

Рассмотрим мир прямоугольных закрытых ящиков с всегда истинной аксиомой

$(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} 0.8\le P(с~\neg\text{in}~ш) \le 1 \\ 0.1\le P(ш~\neg\text{in}~с) \le 1 \end{array} \right. ~~~~~~~\Rightarrow~~~~~~~ \left\{ \begin{array}{lll} 0\le P(с~\text{in}~ш) \le 0.2\\ 0\le P(ш~\text{in}~с) \le 0.9 \end{array} \right. $$

Таким образом утверждение "шткатулка находится в сундуке" имеет интервальную вероятность: $\{0.1,~0\}$. У нас есть небольшие ($0.1$) сомнения, что шкатулка может находиться в сундуке. Впрочем, нет ни каких подкреплений гипотезы, что она там находится (может находиться, а может и нет).