Techniki wykrywania i

eliminowania niespójności w

regułowych bazach wiedzy

Robert Florczyk
Stanisław Zych

Struktura prezentacji



Tworzenie bazy wiedzy



Systemy regułowe



Wykrywanie niespójności



Przykładowe algorytmy wykrywania i
eliminacji niespójności



Systemy wykrywania i eliminowania

Umiejscowienie bazy wiedzy w

systemie ekspertowym

Tworzenie bazy wiedzy



Baza wiedzy - to zbiór: reguł, modeli,
stwierdzeń, wyrażeń o określonej
wartości logicznej, rad oraz relacji
zachodzących między nimi

Metody reprezentacji wiedzy



logika matematyczna (klasyczna,

niestandardowa),



sieci semantyczne (semantic networks),



fakty,



reguły (rules), ewentualnie wzbogacone

o współczynniki wiarygodności,



ramy (frames),



sieci neuronowe (neural nets)

Rodzaje reguł



Postać reguły

IF [przesłanka] THEN [konkluzja]



reguły proste - takie, które mają postać wniosków

pośrednich



reguły złożone - takie, które umożliwiają bezpośrednie

wyznaczenie wniosków przez system.

Przykład reguły złożonej:
IF spełnione są wszystkie warunki podpisanej umowy

THEN towar można odebrać z magazynu

Proces pozyskiwania wiedzy

 
Ekspert
dziedziny

 
Inżynier
wiedzy

 
Baza
wiedzy

 
Dane, problemy,
pytania

Wiedza
struktuali
zowana

Wiedza, koncepcje,
rozwiązania

Systemy regułowe



Systemy regułowe takie jak PCShell

pracują wykorzystując zbiór reguł z

których każda zapisana jest w postaci

klauzuli. Pojedyncza reguła Ri składa się z

warunków aktywacji p1, p2, ... , pn i

wniosku hi, wniosek staje się prawdą

wtedy gdy wszystkie warunki aktywacji są

prawdą. Można to zapisać następująco:

R i : p1  p2



...



pn  h i

Systemy regułowe



Warunki aktywacji jak i wniosek
przyjmują w systemie PCShell postać
trójek Obiekt-Atrybut-Wartość (OAW)



Przykładowa trójka stwierdzająca prosty
fakt może wyglądać następująco:

Długość(droga) = 5

Systemy regułowe



Przy budowaniu systemów bardzo
ważne jest aby baza wiedzy spełniała
określone warunki:

–

czytelność i duża łatwość interpretacji,

–

graficzne wspomaganie konstrukcji
poprawnych reguł,

–

wbudowane mechanizmy weryfikacji (dla
wprowadzonych reguł).

Niespójność w bazach wiedzy



Do najczęściej występujących
niespójności w regułowych zbiorach
wiedzy możemy zaliczyć:

–

Nadmiarowość reguł

–

Sprzeczność reguł

–

Niedobór reguł

–

Pętle

Graficzna reprezentacja

niespójności

Nadmiarowość reguł



Sytuacja występuje wtedy gdy na podstawie aktualnych

przesłanek system może aktywować kilka reguł i z każdej z nich

osiągnąć podobny wniosek. Może wtedy wystąpić tzw.

pochłanianie reguł. Jeżeli dwie reguły spełniają powyższe

kryterium i warunki aktywacji pierwszej reguły są słabsze

(bardziej ogólne), a jej wniosek silniejszy (bardziej szczegółowy)

to reguła pierwsza pochłania regułę drugą. Poniżej zostały

przedstawione przykłady obrazujące nadmiarowość reguł.

–

Reguły nieosiągalne:

p





p



q

–

Zduplikowane reguły:

p



q



r

q



p



r

–

Zawieranie się reguł:

p



q



r

p



r

–

Reguły redundantne:

p



q,

q



r,

p



r

Sprzeczność reguł



Rzecz ma się podobnie do sprzeczności reguł. System na

podstawie tych samych przesłanek może aktywować kilka reguł o

odmiennych wnioskach. Sytuacja taka zwykle nie jest anomalią

ale celowym działaniem projektanta systemu regułowego. Dzieje

się tak np. wtedy gdy do systemu są wprowadzane najpierw

reguły o silniejszych warunkach aktywacji w celu odpowiednich

reakcji na sytuacje specyficzne, a następnie reguły o słabszych

warunkach w celu opisu bardziej ogólnych sytuacji wcześniej nie

uwzględnionych. Przykład reguł sprzecznych:

–

Reguły sprzeczne:

p



q



r

p





r

–

Reguły ambiwalentne:

p



q,

q



r,

p





r

Niedobór reguł



Anomalia ta występuje jeżeli istnieją takie wartości atrybutów

terminalnych (tych których wartość definiowana jest przez system,

a nie w drodze wnioskowania) dla których nie da się określić

wartości celu. Niedobór istnieje (system nie jest zupełny) jeżeli

przykładowo p jest zadeklarowane jako wejście ale w formule
…



p



…



…

nie odnajdujemy reguł dla p więc jest ono nieużywanym

wejściem, sugeruje to, że reguła dotycząca tej danej została

utracona. Bardziej ogólne zjawisko występuje wtedy gdy mamy

podane logiczne reguły, mamy daną i jej wartość zadeklarowaną

jako wejście ale nie płynie żaden wniosek z systemu ani nie ma

rezultatu działania reguł na tej danej. Dla twórcy baz wiedzy

bardzo ważne i użyteczne jest aby wiedział on czy niedobór reguł

jest nieszkodliwy dla systemu (nie podejmuje żadnej akcji) czy

trzeba poprawić tą anomalię.

Pętle



Ten problem w specyfikacji wiedzy pojawia się często tam
gdzie mamy do czynienia z wysokim stopniem
współzależności pomiędzy danymi. Pętle w ciągu
wnioskowania, mogą doprowadzić do niemożności
zakończenia wnioskowania w sposób deterministyczny.
Wnioskowanie które utknęło w pętli powinno być zakończone
po określonej ilości iteracji, bądź gdy system wnioskujący
stwierdzi że nie ma ono szans na wyjście z pętli. Przykład
reguł tworzących pętle:

–

p  q

q  p

Wykrywanie niespójności



Formalna definicja niespójności

Definicja niespójności: Zbiór reguł Rg jest niespójny dla
g jeżeli covered(g, Eg, Rg) nie startuje dla pewnego
EgUg. Niepokryte otoczenia wskazują brakujące

reguły. Na przykład niepokryte otoczenie {<a, a2>,
<b ,b2>} sugerują brak reguł z poprzednikiem: a = a2,
b = b2.

UWAGA: Funkcja covered(g, E, Rg) jest prawdziwa jeżeli E

jest pokrywane przez Rg dla celu g. Każde otoczenie
celu dla g jest pokrywane przez Rg.

Algorytm wykrywania

niespójności

określić D

g

oraz R

g

;

dopóki jest niesprawdzone otoczenie E

g

{

generuj(E

g

, R

g

);

jeżeli nie covered(g, E

g

, R

g

) wtedy

wyjście (E

g

);

}

Algorytm wykrywania

niespójności

1

)

1

)

(

(

























g

D

d

g

d

vals

U

Nowe podejście do wykrywania

niespójności



Procedura COVER dla wykrywania niespójności została

zaprojektowana, aby spełnić następujące warunki dotyczące

baz wiedzy:

–

dostarczyć pełnej sprawdzalności

–

maksymalizować względny wskaźnik szumów do raportowania

niespójności

–

dostarczyć maksimum kontroli przez użytkownika

Metoda COVER używa poprawionej wersji prostego algorytmu

typu „generuj i sprawdzaj”. Ideą jego jest zredukować liczbę

otoczeń generowanych dwojako: po pierwsze generowanie

tylko tych otoczeń które zawierają pewne kombinacje danych

rzeczowych; po drugie generowanie najpierw małych

(ogólnych) i później ich zacieśnianie do coraz bardziej

sprecyzowanych. Powyższe metody należa do grupy

heurystyków. Wykorzystują one założenia dotyczące możliwych

niespójności w bazach wiedzy.

Heurystyki do wykrywania

niespójności



Rozważanie istotnych kombinacji
danych rzeczowych



Rozważanie generalizowanych otoczeń

Systemy wykrywania i

eliminowania



KRUST



COVADIS



IMPROVER



CONKRET



IN-DEPTH

KRUST



KRUST (Knowledge Refinement Using
Semantic Trees – Oczyszczanie wiedzy
przy pomocy drzew semantycznych)
oczyszcza bazy reguł rozważając
priorytet reguł

Architektura KURST



Zestaw przykładów szkoleniowych, które nie zostały rozwiązane

przez system ekspertowy jest podawany na wejście. Wykrywane

są możliwe przyczyny, a reguły są grupowane w odpowiednich

kategoriach.



Generowane są zestawy możliwych rafinacji. Każdy z nich

zawiera zestaw zmian reguł. Reguły mogą zostać wzmocnione

lub osłabione.



Pierwszy filtr pomija rafinacje, które są słabe. Te które pozostają

są zarejestrowane w bazie wiedzy, tworząc zestaw

oczyszczonych baz wiedzy.



Dla utworzonych baz wiedzy uruchamiane są przykłady

szkoleniowe. Bazy wiedzy, które nie znajdą rozwiązania dla

zadanych problemów są odrzucane.



Pozostałe bazy wiedzy są przedstawiane ekspertowi lub oceniane

przez szczegółowe procesy. Wybierane są najbardziej

odpowiednie bazy wiedzy.

COVADIS



System COVADIS jest systemem
sprawdzającym niespójności wykorzystującym
wymuszone techniki propagacji
zaprojektowane do współdziałania z
systemami ekspertowymi zaprojektowanymi w
powłoce MORSE. System ten na podstawie
bazy reguł generuje specyfikację wszystkich
baz faktów, z których wydedukowane mogą
zostać niepoprawne rozwiązania.

IMPROVER



Kolejnym podejściem pomagającym oczyścić bazę wiedzy w

systemie ekspertowym jest IMPROVER, wykorzystujący

priorytety błędów. Konieczne jest posiadanie klasyfikacji

błędów, obejmującej typ błędu oraz elementy powodujące

błąd.



Do oczyszczania wykorzystywane są następujące operatory:

–

Generalizowanie/specjalizowanie warunków znajdujących się

po lewej stornie reguł oraz meta-reguł.

–

Modyfikowanie współczynnika prawdopodobieństwa (CF) reguł

oraz meta-reguł.

–

Modyfikowanie CF w konkluzjach reguł typu up-down.

–

Modyfikowanie prawych stron meta-reguł.

–

Dodawanie warunków znajdujących się po lewej stronie reguł

oraz meta-reguł.

–

Dodawanie reguł oraz meta-reguł do KB.

CONKRET



CONKRET (CONtrol Knowledge REfinement Tool) jest

narzędziem służącym do oczyszczania wiedzy

kontrolnej. Sprawdza on funkcjonalność meta-reguł

odpowiedzialnych za dynamiczne generowanie celów i

strategii systemu ekspertowego. Bezwarunkowa

kontrola nie jest uwzględniania. Warunkowa kontrola

jest wyrażana poprzez meta-reguły. Przed

uruchomieniem CONKRET zakłada się, że baza wiedzy

została sprawdzona i nie zawiera żadnych

strukturalnych anomalii. Przy pomocy CONKRET

użytkownik stara się zoptymalizować sposób

znalezienia rozwiązania optymalnego.

IN-DEPTH



IN-DEPTH II jest inkrementacyjnym systemem

wykrywania niespójności, który może

weryfikować część KB. Proces inkrementacyjnej

weryfikacji jest formułowany w następujący

sposób: niech KB0 będzie weryfikowaną bazą

wiedzy, na której zastosowano operator

modyfikacji Θ do obiektu obj, generujący nową

bazę wiedzy KB1.

KB1=KB0 + Θ(obj)

gdzie, Θ{DODAJ, MODYFIKUJ, USUŃ} i

obj{reguła, moduł, meta-reguła}.

IN-DEPTH



Realizacja weryfikacji

–

Jeżeli KB1 zawiera nowe obiekty, które nie
występują w KB0, to te obiekty powinny
zostać zweryfikowane.

–

Zmiany w KB1 mogą wpływać wyniki
weryfikacji obiektów KB1  KB0.

Dziękujemy za uwagę