SYSTEM DIAGNOSTYCZNY OPARTY NA LOGICE DOMNIEMAŃ

Ewa Madalińska

na podstawie prac:

[1] Łukaszewicz,W. (1988) “Considerations on Default Logic: An Alternative Approach”. Computational Intelligence, 44[1], 1-16.

[2] Reiter, R. (1987) “A theory of Diagnosis from First Principles”. Artificial Intelligence, 32, 57-95.

Problem diagnozy

Problemem diagnozy nazywamy nast_{}epuj _{}ace zadanie: dane jest urz _{}adzenie U, składaj _{}ace si_{}e z elementów c_{1}, …, c_{n}, oraz zestaw obserwacji o_{1}, …, o_{k} dotycz _{}acych jego działania. Należy sprawdzić, czy obserwacje o_{1}, …, o_{k} s _{}a zgodne z zakładanym działaniem urz _{}adzenia i, jeśli nie, określić te elementy spośród e_{1}, …, e_{n}, których wadliwe działanie może mieć na to wpływ.

Podejścia do rozwi _{}azania problemu

Dwa podejścia:

• Diagnoza formalna

– opis systemu – urz _{}adzenia fizycznego czy dziedziny świata rzeczywistego

– obserwacja zachowania si_{}e tego systemu.

Niezgodność oznacza, że pewne jego elementy działaj _{}a wadliwie. Powstaje wtedy problem diagnostyczny polegaj _{}acy na wyznaczeniu elementów, których wadliwe działanie tłumaczyłoby rozbieżnośc mi_{}edzy obserwowanym a przewidywanym zachowaniem systemu.

• Diagnoza empiryczna

– informacja statystyczna o poprzednich zachowaniach systemu, np. “Jeżeli obserwujesz takie to a takie wadliwe działanie, to w 90% zepsuty jest element X”.

Diagnoza formalna

J_{}ezyk reprezentacji systemów – j_{}ezyk logiki pierwszego rz_{}edu.

Opis systemu – specyfikacja jego zachowania przy założeniu, że wszystkie elementy działaj _{}a poprawnie.

Problem diagnostyczny – obserwowane działanie jest niezgodne z przewidywanym.

Diagnoza nie musi być unikalna; może być wiele alternatywnych wyjaśnień dla tego samego wadliwego systemu.

Problem obliczeniowy – wyznaczenie wszystkich możliwych diagnoz dla pewnego wadliwego systemu.

Formalizacja problemu

Definicja 1 System jest to para (OS,ELEM), gdzie:

(1) OS - opis systemu - jest zbiorem zdań logiki pierwszego rz_{}edu.

(2) ELEM - elementy systemu - skończony zbiór stałych indywiduowych.

W opisie systemu wyróżnia si_{}e predykat unarny ab(.), interpretowany jako “wadliwy” (ang. abnormal).

Przykład 1 Rozważmy układ zbudowany z bramek logicznych:

X1 i X2 s _{}a bramkami XOR (sumy wyłacznej), A1 i A2 s _{}a bramkami AND, O1 jest bramk _{}a OR.

Układ ten może być reprezentowany przez system z 5 elementami X1,X2,O1,A1,A2 oraz nast_{}epuj _{}acy opis:

a) opis funkcjonowania poszczególnych elementów,

AND(x) ∧ ¬ab(x) ⇒ out(x) ≡ in1(x) ∧ in2(x), XOR(x) ∧ ¬ab(x) ⇒ out(x) ≡ ¬in1(x) ∧ in2(x) ∨ in1(x) ∧ ¬in2(x), OR(x) ∧ ¬ab(x) ⇒ out(x) ≡ in1(x) ∨ in2(x),

b) opis rodzajów poszczególnych elementów,

AND(A1), AND(A2), XOR(X1), XOR(X2), OR(O1), c) opis powi _{}azań poszczególnych elementów,

out(X1) ≡ in2(A2), out(X1) ≡ in1(X2), out(A1) ≡ in1(O1), out(A2) ≡ in2(O1), in1(A2) ≡ in2(X2), in1(X1) ≡ in1(A1), in2(X1) ≡ in2(A1),

Obserwacje systemu

Definicja 2 Obserwacj _{}a systemu nazywamy skończony zbiór zdań logiki pierwszego rz_{}edu. System z obserwacjami jest to trójka (OS,ELEM,OBS).

Przykład 2 Załóżmy, że do systemu z przykładu 1. podano na wejściu 1,0,1 i otrzymano na wyjściu 1,0. Obserwacja ta może być zapisana jako,

in1(X1), ¬in2(X1), in1(A2), out(X2), ¬out(O1)

Obserwacja ta wskazuje, że układ jest wadliwy; oba wyniki na wyjściu s _{}a niepoprawne.

Wadliwość systemu (OS,{c_{1}, ..., c_{n}},OBS) – obserwacje OBS s _{}a rozbieżne z wynikaj _{}acym z opisu zachowaniem systemu.

Diagnozy

{¬ab(c_{1}), ..., ¬ab(c_{n})} – przypuszczenie, że wszystkie elementy systemu działaj _{}a właściwie.

Fakt, że obserwacje OBS s _{}a niezgodne z działaniem systemu przy założeniu, że wszystkie jego elementy działaj _{}a poprawnie, może być sformalizowany przez:

OS ∪ {¬ab(c_{1}), ..., ¬ab(c_{n})} ∪ OBS (1)

jest sprzeczny.

Intuicyjnie, diagnoza – założenie, że pewne elementy s _{}a wadliwe, a pozostałe działaj _{}a dobrze.

Zadanie – wyspecyfikować wadliwe elementy tj. wyjaśnić źródło sprzeczności (1).

Naturaln _{}a drog _{}a jest usuni_{}ecie dostatecznej ilości przypuszczeń ¬ab(c_{i}), gdzie 1 ≤ i ≤ n, aż do otrzymania niesprzeczności.

Racjonalnie b_{}edzie zastosować zasad_{}e:

Diagnoza jest założeniem, że pewien minimalny zbiór elementów jest wadliwy.

Definicja 3 Diagnoz _{}a dla (OS,ELEM,OBS) jest minimalny zbiór Δ ⊆ ELEM taki, że,

OS ∪ OBS ∪ {ab(c) | c ∈ Δ} ∪ {¬ab(c) | c ∈ ELEM − Δ}

jest niesprzeczny.

Diagnoza jest wyznaczona przez minimalny zbiór elementów o nast_{}epuj _{}acej własności:

założenie, że każdy z tych elementów jest wadliwy (abnormal) wraz z założeniem, że wszystkie pozostałe s _{}a dobre (not abnormal) jest zgodne (niesprzeczne) z opisem systemu i obserwacj _{}a.

Przykład 3 Z układem z przykładu 2. zwi _{}azane s _{}a 3 diagnozy: {X1}, {X2,O1}, {X2,A2}.

Własności diagnoz

Twierdzenie 1 Dla systemu (OS,ELEM,OBS) istnieje diagnoza wtt OS ∪ OBS jest niesprzeczny.

Twierdzenie 2 { } jest diagnoz _{}a ( i jest to jedyna diagnoza) dla (OS,ELEM,OBS) wtt

OS ∪ OBS ∪ {¬ab(c) | c ∈ ELEM }

jest niesprzeczny.

Znaczy to, że obserwacje s _{}a zgodne z opisem systemu i wszystkie jego elementy działaj _{}a poprawnie.

Twierdzenie 3 Jeżeli Δ jest diagnoz _{}a dla (OS,ELEM,OBS), to dla każdego c_{i} ∈ Δ

OS ∪ OBS ∪ {¬ab(c) | c ∈ ELEM − Δ} ⊧ ab(c_{i})

Twierdzenie 4 Δ ⊆ ELEM jest diagnoz _{}a dla (OS,ELEM,OBS) wtt Δ jest minimalnym zbiorem takim, że

OS ∪ OBS ∪ {¬ab(c) | c ∈ ELEM − Δ}

jest niesprzeczny.

Wpływ dodatkowych obserwacji na diagnozy

Załóżmy, że (OS,ELEM,OBS) ma wi_{}ecej niż jedn _{}a diagnoz_{}e. Wybór jednej z nich wymaga dodatkowych informacji o systemie tj. dokonania dalszych pomiarów np. przeprowadzenie testu laboratoryjnego na pacjencie, wstawienie miernika w obwód. Wynik pomiaru b_{}edzie skończonym ci _{}agiem zdań pierwszego rz_{}edu POM.

Jaki jest zwi _{}azek pomi_{}edzy diagnozami dla (OS,ELEM,OBS) a (OS,ELEM,OBS ∪ POM) ?

Definicja 4 Mówimy, że diagnoza Δ dla (OS,ELEM,OBS) implikuje Π (zdanie pierwszego rz_{}edu) wtt

OS ∪ OBS ∪ {ab(c) | c ∈ Δ} ∪ {¬ab(c) | c ∈ ELEM − Δ} ⊧ Π Twierdzenie 5 Załóżmy, że każda diagnoza dla (OS,ELEM,OBS) implikuje jedn _{}a z Π lub ¬Π . Wtedy:

1. Każda diagnoza dla (OS,ELEM,OBS), która implikuje Π jest diagnoz _{}a dla (OS,ELEM,OBS ∪ Π ).

2. Żadna diagnoza dla (OS,ELEM,OBS), która implikuje ¬Π nie jest diagnoz _{}a dla (OS,ELEM,OBS ∪ Π).

3. Diagnoza dla (OS,ELEM,OBS ∪ Π), która nie jest diagnoz _{}a dla (OS,ELEM,OBS), jest właściwym nadzbiorem pewnej diagnozy dla (OS, ELEM,OBS), która implikuje ¬Π.

Z twierdzenia wynika, że:

• pomiar, który nie jest sprzeczny z żadn _{}a diagnoz _{}a, nie wnosi nowej informacji.

• dodatkowa informacja Π pozwala rozróżniać konkurencyjne diagnozy w ten sposób, że:

– zachowuj _{}a si_{}e te diagnozy, które implikuj _{}a Π,

– odrzuca si_{}e te, które implikuj _{}a ¬Π,

– mog _{}a powstać nowe diagnozy.

Obliczanie diagnoz nie jest możliwe w najbardziej ogólnym przypadku, ponieważ definicja diagnozy odwołuje si_{}e do testu niesprzeczności dla zbioru formuł pierwszego rz_{}edu. Problem ten jest nierozstrzygalny.

Niemniej jednak, jest wiele praktycznych zastosowań opieraj _{}acych si_{}e na takich podzbiorach rachunku predykatów pierwszego rz_{}edu, dla których niesprzeczność jest rozstrzygalna i diagnozy s _{}a obliczalne. Należy do nich mi_{}edzy innymi przypadek sieci logicznych.

W problemach, które maj _{}a modele prowadz _{}ace do teorii nierozstrzygalnych należy zastosować podejście heurystyczne.

Zastosowanie logiki domniemań do obliczania diagnoz

Wnioskowanie diagnostyczne – niemonotoniczne: dodatkowe informacje mog _{}a obalić pewne diagnozy systemu.

Istnieje ścisły zwi _{}azek mi_{}edzy wnioskowaniem diagnostycznym opartym na logice pierwszego rz_{}edu a logik _{}a domniemań.

Z systemem (OS,ELEM) wraz z obserwacjami OBS wi _{}ażemy teori_{}e domniemań DT = ⟨A, D⟩, gdzie:

A = OS ∪ OBS

D = {: ¬ab(c)/¬ab(c) | c ∈ ELEM }.

Wzajemnie jednoznaczn _{}a odpowiedniość pomi_{}edzy diagnozami dla (OS,ELEM,OBS) a rozszerzeniami powyższej teorii domniemań wyznacza nast_{}epuj _{}ace twierdzenie:

Twierdzenie 6 E jest rozszerzeniem dla DT wtt dla pewnej diagnozy Δ dla (OS,ELEM,OBS)

E = {Π | Δ implikuje Π}.

Posługuj _{}ac si_{}e poj_{}eciem domniemań generuj _{}acych rozszerzenie, twierdzenie to można by sformułować nast_{}epuj _{}aco:

E jest rozszerzeniem dla DT wtt dla pewnej diagnozy Δ zachodzi:

Δ = ELEM − {c ∈ ELEM | (: ¬ab(c)/¬ab(c)) ∈ GD(E)}.