Sztuczna inteligencja/SI Moduł 4 - Wnioskowanie na podstawie wiedzy niepewnej i niepełnej

\maketitle

Niedoskonała wiedza we wnioskowaniu

Metody wnioskowania w logice predykatów są - pod warunkiem korzystania z poprawnego systemu wnioskowania - niezawodne jeśli chodzi o prawdziwość wyciąganych wniosków. Oparte są one jednak na koniecznym założeniu, że stwierdzenia zawarte w początkowej bazie wiedzy i uznawane za prawdziwe są rzeczywiście prawdziwe. Pod warunkiem ich prawdziwości prawdziwe są także stwierdzenia wyprowadzane w wyniku wnioskowania. Założenie to może często nie być spełnione w odniesieniu do wiedzy, którą posiada człowiek - a przecież od niego musi pochodzić początkowa zawartość bazy wiedzy. Wiedza pochodząca od człowieka może być niedoskonała. Stosując do takiej wiedzy metody zakładające doskonałą wiedzę jesteśmy narażeni na uzyskiwanie wniosków, które nie muszą być prawdziwe i o których prawdziwości nie potrafimy nic powiedzieć. Celowe jest w związku z tym wyposażanie systemów wnioskujących na podstawie niedoskonałej wiedzy w specjalne mechanizmy jej przetwarzania, dzięki którym będzie możliwe charakteryzowanie rodzaju i stopnia niedoskonałości wiedzy pochodzącej od człowieka, a także nowej wiedzy wyprowadzonej na jej podstawie przez system wnioskujący.

Rodzaje niedoskonałości wiedzy

Wnikając głębiej w naturę niedoskonałości ludzkiej wiedzy można wskazać przynajmniej jej trzy podstawowe rodzaje:

• niepewność: prawdziwość niektórych stwierdzeń nie jest pewna,
• niepełność: niektóre prawdziwe stwierdzenia nie są znane, lecz nie można z tego powodu zakładać ich nieprawdziwości,
• niedokładność: przynależność do niektórych relacji, odpowiadających predykatom występującym w stwierdzeniach, nie jest znana dokładnie.

W przypadku wiedzy niepewnej mamy do czynienia ze stwierdzeniami , o których w ogólnym przypadku nie można powiedzieć z pewnością, że są prawdziwe albo fałszywe. Potrzebne są w tym celu jakieś metody charakteryzowania stopnia przekonania o prawdziwości stwierdzeń - zarówno należących do początkowej bazy wiedzy, jak i uzyskiwanych w wyniku głosowania. Niepełność wiedzy oznacza, że status prawdziwości pewnych stwierdzeń potrzebnych do wnioskowania nie jest znany. Może to wymagać założenia ich prawdziwości w celu przeprowadzenia wnioskowania, lecz z pozostawieniem możliwości rewizji tego wnioskowania, gdyby następnie pojawiła się wiedza zaprzeczająca temu założeniu. Niedokładność polega na niemożliwości precyzyjnego odróżnienia w dziedzinie, na temat której zapisujemy wiedzę, obiektów należących do pewnej relacji od obiektów do niej nienależących.

Metody przetwarzania niedoskonałej wiedzy

Istnieje wiele technik przetwarzania wiedzy obarczonej różnymi rodzajami niedoskonałości w taki sposób, aby prowadzone na jej podstawie wnioskowanie prowadziło do wniosków, których „jakość” można w pewien sposób scharakteryzować, czyli odpowiedzieć na pytanie, jak bardzo doskonałe bądź niedoskonałe wnioski można wyciągnąć na podstawie niedoskonałej wiedzy. Do najbardziej znanych metod należą:

• wnioskowanie probabilistyczne: metoda przetwarzania wiedzy niepewnej oparta na bezpośrednim wykorzystaniu rachunku prawdopodobieństwa, w której poszczególnym stwierdzeniom przypisuje się prawdopodobieństwo ich prawdziwości,
• stopnie pewności: metoda przetwarzania wiedzy niepewnej, w której poszczególnym stwierdzeniom przypisuje się liczbowe stopnie pewności wyrażające subiektywne przekonanie człowieka o ich prawdziwości,
• teoria Dempstera-Schaffera: metoda przetwarzania wiedzy niepewnej, w której prawdopodobieństwa prawdziwości przypisuje się tylko wybranym stwierdzeniom bazowym, a ocenę wiarygodności innych stwierdzeń przeprowadza się na podstawie ich związków ze stwierdzeniami bazowymi,
• Logika rozmyta: metoda przetwarzania wiedzy niedokładnej, w której rozważa się „częściową” przynależność do relacji,
• Logiki niemonotoniczne: metody przetwarzania wiedzy niepełnej, w których dopuszcza się, że pojawienie się nowych stwierdzeń może anulować wyprowadzenie wcześniejszych formuł.

W dalszym ciągu skupimy się na dwóch podejściach: wnioskowaniu probabilistycznym i logice rozmytej.

Wnioskowanie bayesowskie

Wnioskowanie probabilistyczne nazywamy także wnioskowaniem bayesowskim, ze względu na kluczową rolę, jaką w nim pełni wzór Bayesa - jeden z klasycznych wyników rachunku prawdopodobieństwa. Dla dowolnych dwóch zdarzeń $A\,$ i $B\,$ wzór opisuje następującą zależność prawdopodobieństw warunkowych:

$\mathrm {Pr} (A|B)={\frac {\mathrm {Pr} (A)\mathrm {Pr} (B|A)}{\mathrm {Pr} (B)}}\,$(1)

Zobaczymy, jak w najbardziej bezpośredni sposób można zależność taką wykorzystać do wnioskowania.

Uprawdopodobnianie hipotez przez fakty

Przyjmijmy, że wśród stwierdzeń, jakie są przetwarzane przy wnioskowaniu, wyróżnimi dwie kategorie:

• fakty: stwierdzenia dotyczące dziedziny, których prawdziwość jest znana,
• hipotezy: stwierdzenia o nieznanym prawdopodobieństwie prawdziwości.

Interesuje nas wnioskowanie o prawdziwości możliwych hipotez przy założeniu prawdziwości pewnego zestawu faktów. Aby zademonstrować, jak to jest możliwe, zapiszmy wzór Bayesa ze zmienionymi oznaczeniami:

$\mathrm {Pr} (h|F)={\frac {\mathrm {Pr} (h)\mathrm {Pr} (F|h)}{\mathrm {Pr} (F)}}\,$(2)

gdzie $h\,$ oznacza pewna hipoteze a $F\,$ pewien zbiór faktów. Tak interpretowany wzór Bayesa mówi, w jaki sposób na prawdopodobieństwo rozważanej hipotezy wpływa znajomość faktów. Zwróćmy szczególną uwagę na dwa występujące w nim prawdopodobieństwa dotyczące hipotezy:

• $\mathrm {Pr} (h)\,$: prawdopodobieństwo a priori hipotezy $h\,$ (bez znajomości lub uwzględniania żadnych faktów),
• $\mathrm {Pr} (h|F)\,$: prawdopodobieństwo a posteriori hipotezy $h\,$ po uwzglednieniu faktow $F\,$.

Możemy powiedzieć, że wzór Bayesa, podając przepis na wyznaczenie prawdopodobieństwa a posteriori, określa wpływ faktów na uprawdopodobnienie (albo unieprawdopodobnienie) hipotezy. Bezpośrednie zastosowanie w przedstawiony sposób wzoru Bayesa można traktować jako elementarny krok wnioskowania bayesowskiego, który jest w pewnym sensie odpowiednikiem zastosowania reguły wnioskowania w logice.

Zauważmy, że prawdopodobieństwo występujące w mianowniku ułamka nie zależy od rozważanej hipotezy. Wynika z tego, że gdyby interesowało nas wyłącznie wybranie hipotezy najbardziej prawdopodobnej z pewnego zestawu, wystarczy ograniczyć się do obliczenia licznika ułamka. Aby poznać dokładne, bezwzględne wartości prawdopodobieństw \emph{a posteriori} poszczególnych hipotez, należy wziąć pod uwagę sytuację, w której mamy skończoną liczbę możliwych hipotez $h_{1},h_{2},\dots ,h_{n}\,$ wykluczających się parami i~wyczerpujących wszystkie możliwości (czyli takich, że dokładnie jedna z nich jest prawdziwa). Wówczas:

$\mathrm {Pr} (F)=\mathrm {Pr} (h_{1})\mathrm {Pr} (F|h_{1})+\dots +\mathrm {Pr} (h_{n})\mathrm {Pr} (F|h_{n})\,$(3)

czyli:

$\mathrm {Pr} (h_{i}|F)={\frac {\mathrm {Pr} (h_{j})\mathrm {Pr} (F|h_{i})}{\sum _{j=1}^{n}\mathrm {Pr} (h_{j})\mathrm {Pr} (F|h_{j})}}\,$(4)

Oczywiście dla takich hipotez mamy:

$\sum _{i=1}^{n}\mathrm {Pr} (h_{i}|F)=1\,$(5)

W szczególności biorąc pod uwagę dwie wykluczające się hipotezy $h\,$ i $\neg h\,$ dostajemy w ten sposób:

$\mathrm {Pr} (h|F)={\frac {\mathrm {Pr} (h)\mathrm {Pr} (F|h)}{\mathrm {Pr} (h)\mathrm {Pr} (F|h)+\mathrm {Pr} (\neg h)\mathrm {Pr} (F|\neg h)}}\,$	(6)
$\mathrm {Pr} (\neg h|F)={\frac {\mathrm {Pr} (\neg h)\mathrm {Pr} (F|\neg h)}{\mathrm {Pr} (h)\mathrm {Pr} (F|h)+\mathrm {Pr} (\neg h)\mathrm {Pr} (F|\neg h)}}\,$	(7)

Uwzględnianie pojedynczych faktów

Dotychczas pokazaliśmy, jak można wyznaczyć prawdopodobieństwo \emph{a posteriori} hipotezy $h\,$ na podstawie zbioru znanych faktow $F\,$, pod warunkiem znajomości prawdopodobieństwa a priori $\mathrm {Pr} (h)\,$ i prawdopodobieństwa faktów przy założeniu prawdziwości hipotezy $\mathrm {Pr} (F|h)\,$. Koniecznośc ustalenia prawdopodobieństwa a priori jest naturalną właściwością wnioskowania bayesowskiego - za pomocą tego prawdopodobieństwa wyrażamy aprioryczne przekonanie o prawdziwości hipotezy, bez uwzględniania jakichkolwiek faktów. Bardziej problematyczne jest określanie prawdopodobieństwa $\mathrm {Pr} (F|h)\,$, gdyz $F\,$ może oznaczać dowolny zbiór znanych faktów. Jeśli mamy ustalony pewien zbiór $\mathbb {F} \,$ wszystkich możliwych faktów, które mogą być uwzględniane przy wnioskowaniu, to $F\,$ może być jego dowolnym podzbiorem. Bezpośrednie przypisanie każdemu podzbiorowi prawdopodobieństwa na ogół przekraczałoby możliwości eksperta czy użytkownika systemu wnioskującego.

Szczęśliwie przy pewnych założeniach można uniknąc konieczności określania $\mathrm {Pr} (F|h)\,$ dla dowolnego $F\subseteq \mathbb {F} \,$, opierając się wyłącznie na prawdopodobieństwach dla pojedynczych faktów $\mathrm {Pr} (f|h)\,$, gdzie $f\in \mathbb {F} \,$. Dla dowolnego faktu $f_{1}\,$ możemy stosując wzór Bayesa uzyskać:

$\mathrm {Pr} (h|f_{1})={\frac {\mathrm {Pr} (h)\mathrm {Pr} (f_{1}|h)}{\mathrm {Pr} (f_{1})}}\,$(8)

Jeśli teraz dokładając kolejny znany fakt $f_{2}\,$ rozważymy dwuelementowy zbiór faktów $\{f_{1},f_{2}\}\,$, otrzymujemy:

Parser nie mógł rozpoznać (nieznana funkcja „\begin{split}”): {\displaystyle \begin{split} \mathrm{Pr}(h|f_1\land f_2) = & \frac{\mathrm{Pr}(h|f_1)\mathrm{Pr}(f_2|f_1\land h)} {\mathrm{Pr}(f_2|f_1)} = & \frac{\mathrm{Pr}(h)\mathrm{Pr}(f_1|h)\mathrm{Pr}(f_2|f_1\land h)} {\mathrm{Pr}(f_1)\mathrm{Pr}(f_2|f_1)} = & \frac{\mathrm{Pr}(h)\mathrm{Pr}(f_1|h)\mathrm{Pr}(f_2|f_1\land h)} {\mathrm{Pr}(f_1\land f_2)} \end{split} \,} (9)

Jeśli teraz założymy, że pojedyncze fakty są warunkowo niezależne względem hipotezy, czyli:

$\mathrm {Pr} (f_{2}|f_{1}\land h)=\mathrm {Pr} (f_{2}|h)\,$	(10)
$\mathrm {Pr} (f_{1}|f_{2}\land h)=\mathrm {Pr} (f_{1}|h)\,$	(11)

to możemy dalej uzyskać:

$\mathrm {Pr} (h|f_{1}\land f_{2})={\frac {\mathrm {Pr} (h)\mathrm {Pr} (f_{1}|h)\mathrm {Pr} (f_{2}|h)}{\mathrm {Pr} (f_{1}\land f_{2})}}\,$(12)

Wyprowadzenie to można analogicznie powtórzyć dla dowolnej liczby pojedynczych faktów, co prowadzi do ogólnego wzoru:

$\mathrm {Pr} (h|f_{1}\land f_{2}\land \dots \land f_{m})={\frac {\mathrm {Pr} (h)\prod _{k=1}^{m}\mathrm {Pr} (f_{k}|h)}{\mathrm {Pr} (f_{1}\land f_{2}\land \dots \land f_{k})}}\,$(13)

Aby posłużyć się nim w celu obliczenia bezwzględnych prawdopodobieństw a posteriori, należy tak jak poprzednio wziąć pod uwagę zbiór $\{h_{1},h_{2},\dots ,h_{n}\}\,$ hipotez wykluczających się parami i wyczerpujących wszystkie możliwości. Wówczas, przy założeniu warunkowej niezależności faktów względem każdej hipotezy, mianownik powyższego ułamka może być wyznaczony w następujący sposób:

$\mathrm {Pr} (f_{1}\land f_{2}\land \dots \land f_{m})=\sum _{i=1}^{n}\mathrm {Pr} (h_{i})\prod _{k=1}^{m}\mathrm {Pr} (f_{k}|h_{i})\,$(14)

W szczególności dla zbioru dwóch wykluczających się hipotez $\{h,\neg h\}\,$ dostajemy w ten sposób:

$\mathrm {Pr} (f_{1}\land f_{2}\land \dots \land f_{m})=\mathrm {Pr} (h)\prod _{k=1}^{m}\mathrm {Pr} (f_{k}|h)+\mathrm {Pr} (\neg h)\prod _{k=1}^{m}\mathrm {Pr} (f_{k}|\neg h)\,$

(15)

W ten sposób uzyskaliśmy prosty mechanizm wnioskowania bayesowskiego, w którym możemy wyznaczać prawdopodobieństwa a posteriori dowolnych hipotez na podstawie znajomości dowolnych zbiorów faktów, pod warunkiem określenia prawdopodobieństw a priori każdej hipotezy oraz prawdopodobieństw każdego pojedynczego faktu pod warunkiem prawdziwości każdej hipotezy. Prawdopodobieństwa te stanowią reprezentację niepewnej wiedzy o dziedzinie wnioskowania, która musi być dostarczona systemowi wnioskującemu. Określenie tych prawdopodobieństw w rozsądny sposób jest często możliwe, chociaż oczywiście może niekiedy być trudne.

Ogólność przedstawionego mechanizmu wnioskowania bayesowskiego ogranicza przyjęte założenie o warunkowej niezależności faktów względem hipotez. Założenie to nie musi być spełnione w wielu praktycznych sytuacjach, a co gorsza - może być ono niekiedy1 niemożliwe do weryfikacji. Znane są bardziej zaawansowane algorytmy wnioskowania bayesowskiego odstępujące od tego założenia, oparte na tzw. sieciach bayesowskich.

Przykład: diagnostyka grypy. Rozważmy następującą prostą ilustrację przedstawionego mechanizmu wnioskowania, traktując rozważane w niej przykładowe fakty i hipotezy z należnym dystansem. Weźmiemy pod uwagę sytuację, w której diagnozując dolegliwości pacjenta ograniczono zbiór możliwych diagnoz do następujących dwóch wykluczających się hipotez:

• $h\,$: pacjent jest chory na grypę,
• $\neg h\,$: pacjent nie jest chory na grypę.

Podstawą do wnioskowania mogą być następujące pojedyncze fakty:

• $f_{1}\,$: pacjent ma katar,
• $f_{2}\,$: pacjent ma kaszel,
• $f_{3}\,$: pacjent ma gorączkę.

Przyjmijmy, że dostarczający wiedzę do systemu diagnostycznego ekspert ustalił następujące wartości prawdopodobieństw:

$\mathrm {Pr} (h)=\;0.1\;\mathrm {Pr} (\neg h)=\;0.9\,$

$\mathrm {Pr} (f_{1}|h)=\;0.5\;\mathrm {Pr} (f_{1}|\neg h)=\;0.3\,$

$\mathrm {Pr} (f_{2}|h)=\;0.3\;\mathrm {Pr} (f_{2}|\neg h)=\;0.3\,$

$\mathrm {Pr} (f_{3}|h)=\;0.8\;\mathrm {Pr} (f_{3}|\neg h)=\;0.4\,$

Na tej podstawie możemy obliczyć prawdopodobieństwa faktów:

$\mathrm {Pr} (f_{1})=\mathrm {Pr} (h)\mathrm {Pr} (f_{1}|h)+\mathrm {Pr} (\neg h)\mathrm {Pr} (f_{1}|\neg h)=0.1\cdot 0.5+0.9\cdot 0.3=0.32\,$

$\mathrm {Pr} (f_{2})=\mathrm {Pr} (h)\mathrm {Pr} (f_{2}|h)+\mathrm {Pr} (\neg h)\mathrm {Pr} (f_{2}|\neg h)=0.1\cdot 0.3+0.9\cdot 0.3=0.3\,$

$\mathrm {Pr} (f_{3})=\mathrm {Pr} (h)\mathrm {Pr} (f_{3}|h)+\mathrm {Pr} (\neg h)\mathrm {Pr} (f_{3}|\neg h)=0.1\cdot 0.8+0.9\cdot 0.4=0.44\,$

Aby wyznaczyć prawdopodobieństwa a posteriori rozważanych hipotez na podstawie każdego z pojedynczych objawów stosujemy bezpośrednio wzór Bayesa:

$\mathrm {Pr} (h|f_{1})={\frac {\mathrm {Pr} (h)\mathrm {Pr} (f_{1}|h)}{\mathrm {Pr} (f_{1})}}={\frac {0.1\cdot 0.5}{0.32}}=0.15625\,$

$\mathrm {Pr} (h|f_{2})={\frac {\mathrm {Pr} (h)\mathrm {Pr} (f_{2}|h)}{\mathrm {Pr} (f_{2})}}={\frac {0.1\cdot 0.3}{0.33}}=0.1\,$

$\mathrm {Pr} (h|f_{3})={\frac {\mathrm {Pr} (h)\mathrm {Pr} (f_{3}|h)}{\mathrm {Pr} (f_{3})}}={\frac {0.1\cdot 0.8}{0.44}}=0.18182\,$

Przeprowadzenie obliczeń prawdopodobieństw a posteriori rozważanych hipotez na podstawie dowolnych dwóch objawów oraz wszystkich trzech objawów pozostawiamy jako ćwiczenie.