Metody sztucznej inteligencji
Politechnika ÅšlÄ…ska
Katedra Podstaw Konstrukcji Maszyn
Rok akademicki 2005/2006
Wykład 7
1
System doradczy (ekspertowy) (1)
Ekspert  specjalista z danej dziedziny
System doradczy  narzędzia komputerowe
wspomagające rozwiązywanie zadań będących
wcześniej domeną ekspertów,
Pierwsze systemy powstały w latach 70-tych
XX w.
2
System doradczy
3
System doradczy (ekspertowy) (2)
Program wykorzystujÄ…cy wiedzÄ™ i procedury
rozumowania dla wspomagania rozwiÄ…zywania
problemów na tyle trudnych, że do ich
rozwiÄ…zywania wymagana jest pomoc eksperta.
Program ten może być traktowany jako model
wiedzy najlepszych praktyków w danej dziedzinie.
W systemie doradczym wyróżnia się moduł wiedzy
o dziedzinie podanej w formie zbioru faktów, reguł i
innych środków reprezentacji wiedzy
4
System doradczy (ekspertowy) (3)
System doradczy powinien:
" zadawać pytania
" wyjaśniać sposób swojego rozumowania
" uzasadniać konkluzje
" modyfikować sposób wykonywania zadań
oraz
" wnioskować w sytuacjach kiedy informacje są
nieprecyzyjne, niepewne i niekompletne
5
Przykłady systemów doradczych
ABEL Wyznaczanie relacji przyczynowo-skutkowych
w diagnostyce medycznej,
CAA Interpretowanie postaci kardiogramów
DART Diagnostyka maszyn cyfrowych
DENTRAL Identyfikacji wyników spektrografiii masowej
FAULTFINDER Diagnostyka komputerów
INTERNIST Diagnostyka medyczna
REACTOR Diagnostyka siłowni jądrowych
GUIDON Kształcenie lekarzy
STEAMER Szkolenie operatorów w siłowni jądrowej
HEARSAY I, II Rozpoznawanie tekstów mówionych w języku angielskim
MYCIN Stawianie diagnozy i ustalanie terapii podczas
leczenia zakażenia krwi oraz zapalenia opon
mózgowo-rdzeniowych
6
System MYCIN
" Pierwszy duży system doradczy, którego
działanie może zastępować człowieka eksperta
" Powstał na uniwersytecie w Stanford w połowie
lat 70-tych XX w.
" Techniki wnioskowania i reprezentacji wiedzy
zastosowane w tym systemie stały się podstawą
opracowywania innych systemów doradczych
" Działanie systemu polega na dialogu z lekarzem
prowadzonego za pomocÄ… klawiatury
7
Przykład dialogu z systemem MYCIN
8
Główne elementy systemu
doradczego
9
Baza danych
Baza danych stałych zawiera ogólne dane
o pacjencie i wyniki badań laboratoryjnych.
Baza danych zmiennych zawiera odpowiedzi
użytkownika systemu (lekarza) oraz wyniki
pośrednie (wnioski), które są formułowane na
podstawie danych stałych i danych zmiennych.
Bazy są zbiorami stwierdzeń (faktów) o postaci:
< ,, WARTOŚĆ>>
10
Baza wiedzy
Baza wiedzy zawiera ogólne informacje o dziedzinie
wiedzy medycznej w określonym zakresie
Informacje takie gromadzi się zwykle podczas długotrwałej
współpracy osób opracowujących bazę wiedzy
i specjalistów z danej dziedziny
Informacje nie dotyczą określonego pacjenta ale są
regułami działania w określonych przypadkach o postaci:
if (WARUNEK) then (DZIALANIE_1) else (DZIALANIE_2)
Inna postać to:
(WARUNEK) => (DZIALANIE_1) v (DZIALANIE_2)
11
Układ wnioskujący
Układ wnioskujący (interpreter reguł) to
podstawowy element systemu doradczego.
Działanie układu wnioskującego polega na:
" wyszukiwaniu reguł (w bazach wiedzy) oraz
stwierdzeń (w bazach danych)
" ustaleniu kolejności analizy wyszukanych reguł
" wykonaniu działań określonych przez reguły
" uaktualnieniu bazy danych zmiennych
12
Przykład przebiegu
wnioskowania
13
Sterowanie dialogiem
" System powinien zadawać pytania w
języku naturalnym
" System jest wyposażony w słownik.
Słownik systemu MYCIN zawierał około
800 słów w języku angielskim
" Odpowiedzi i pytania formułowane są za
pomocą stałych fragmentów tekstów
przypisanych odpowiednim regułom
14
Układ objaśniający
" Układ objaśniający rozpoczyna działanie
po zadaniu pytania przez użytkownika.
" Pytania mogą dotyczyć:
 reguł działania (pytania związane i
niezwiÄ…zane z przebiegiem dialogu)
 danych stałych i zmiennych (związane z
występowaniem określonych zależności,
związane z przykładami postaci odpowiedzi)
15
Reprezentacja danych
i wiedzy
16
Reprezentacja danych
w bazach danych (1)
" Dane w bazach danych sÄ… gromadzone w
wyniku obserwacji lub pomiarów.
" Wyróżnia się:
 dane ilościowe
(np. temperatura = 37°C)
 dane jakościowe
(np. temperatura = podwyższona)
17
Reprezentacja danych
w bazach danych (2)
" Przykładami struktur baz danych są:
 struktura relacyjna,
 struktura sieciowa,
 struktura obiektowa.
" Reprezentacja danych powinna
umożliwiać zapis wartości różnych cech
obiektu
18
Reprezentacja wiedzy
w bazach wiedzy (1)
" Reprezentacja danych to niezależny od
dziedziny, ogólny formalizm
przekazywania, zapisywania i
gromadzenia informacji
" Przykłady reprezentacji:
 język naturalny
 zapis matematyczny
" Główny cel reprezentacji danych to
uproszczenie zdań trudnych i złożonych
19
Reprezentacja wiedzy
w bazach wiedzy (2)
" Wiedza to informacje pozyskane od specjalistów oraz
konkluzje uzyskane w procesie wnioskowania z
zastosowaniem dostępnej wiedzy i danych
" Reprezentacja wiedzy powinna być:
 prosta,
 kompletna (wyczerpujÄ…ca),
 zwięzła,
 zrozumiała (niezawierająca elementów domyślnych
i niejednoznacznych).
" Wymagania te nie zawsze są spełnione.
" Reprezentacja wiedzy powinna uwzględniać
ograniczenia
20
Typy reprezentacji wiedzy
" Reprezentacja proceduralna:
 Polega na określeniu zbioru procedur, których
działanie reprezentuje wiedzę o dziedzinie (np.
procedura obliczania pierwiastka kwadratowego);
 Zaleta: wysoka efektywność.
" Reprezentacja deklaratywna:
 Polega na określaniu specyficznych dla danej
dziedziny faktów, reguł, drzew decyzyjnych i in.
 Zaleta: każdy element wiedzy zapisywany jest tylko
raz, co umożliwia szybką modyfikację bazy wiedzy i
ogranicza możliwość wystąpienia niespójności i
powtórzeń
21
Åšrodki reprezentacji wiedzy
" Zdania rachunku predykatów
" Stwierdzenia i stwierdzenia dynamiczne
" Reguły i reguły rozmyte
" Tablice decyzyjne - temat ćwiczeń tablicowych nr 2
" Sieci semantyczne
" Ramy
" Scenariusze
" Drzewa decyzyjne
" Sieci przekonań
" Sieci neuronowe
" & & ..
Najczęściej stosuje się połączenie wymienionych technik.
22
Techniki bazujÄ…ce na rachunku
predykatów
Reprezentacja wiedzy z zastosowaniem
rachunku zdań jest trudna.
Lepszym sposobem jest zastosowanie
rachunku predykatów. Zapis ten stosowany
jest w niektórych językach programowania
pozwalajÄ…cych na budowÄ™ baz wiedzy
23
Stwierdzenia (1)
Stwierdzenie (fakt) opisuje to co zaszło lub zwykle zachodzi
w rzeczywistości.
Stwierdzenie, że atrybut A i jego wartość V są przypisane do
obiektu O zapisuje siÄ™ w postaci:
=<,,>
Nazwa atrybutu jest parÄ…:
=<,
>
Charakter posiadania cechy ma wartość:  posiada lub  jest .
24
Stwierdzenia (2)
Przykład:
=  krzesło
=  nogi
=  posiada
=  cztery
< posiada nogi ,  krzesło ,  cztery >
Jako predykat:
posiada_nogi (krzesło,cztery)
25
Stwierdzenia (3)
" Wadą zapisu stwierdzeń jest trudność w
kodowaniu negacji np.  krzesło nie posiada
czterech nóg . Zapis takich stwierdzeń powoduje
znaczne zwiększenie rozmiarów bazy wiedzy.
Uwaga:
" Zapis takiego stwierdzenia w rachunku
predykatów jest bardzo prosty:
Źposiada_nogi (krzesło,cztery)
26
Stopień pewności
Stopień pewności (ang. Certainty Factor, CF) wprowadza się
do zapisu stwierdzeń w celu umożliwienia zapisu stwierdzeń
niepewnych, hipotez i przypuszczeń.
Stwierdzenie zawierające stopień pewności ma postać:
=<,,atrybutu>,>
27
Stwierdzenia dynamiczne
Stwierdzenie dynamiczne to takie stwierdzenie, któremu
można przypisać przedział czasu T , w którym przysługuje mu
określony stopień prawdziwości CF.
Stwierdzenia dynamiczne mogą być ze sobą sklejane
w procesie wnioskowania.
Stwierdzeniom przypisuje się także wagi W, które są brane
pod uwagÄ™ w procesie wnioskowania.
Ogólna postać stwierdzenia dynamicznego:
=<,,
,,
,>
28
Reguły
Reguły zapisuje się w postaci implikacji:
if PRZESA
ANKA then KONKLUZJA
lub
jeżeli PRZESA
ANKA to KONKLUZJA
Przesłanka jest wyrażeniem złożonym z prostych zdań
logicznych połączonych funktorami  and lub  or (koniunkcje
lub alternatywy).
Przesłanka określa warunki, dla których są spełnione
konkluzje.
Warunki są określane dla stwierdzeń o postaci: lub
.
29
Stwierdzenia i reguły przybliżone
Reguły stosowane w systemach doradczych są
prawdziwe w większości przypadków ale nie we
wszystkich, co oznacza, że są one niepewne i
niedokładne
Zapis stwierdzeń przybliżonych lub reguł
przybliżonych charakteryzuje się wprowadzeniem
stopnia prawdziwości.
Stopień prawdziwości to liczba rzeczywista T
z przedziału [0,1], która określa stopień przekonania
o prawdziwości stwierdzenia lub reguły.
30
Sieci semantyczne
Zapis stwierdzeń bez informacji o relacjach występujących
między nimi utrudnia lub uniemożliwia przeprowadzenie
skutecznego wnioskowania.
Do opisu relacji między stwierdzeniami stosuje się między
innymi sieci semantyczne.
Sieć semantyczna to graf S zapisywany jako trójka
uporządkowana S= (P  zbiór pojęć, wierzchołków
grafu, T- zbiór typów relacji, zbiór typów gałęzi grafu, R 
zbiór relacji, zbiór wszystkich gałęzi grafu).
Związki między relacjami są rozpatrywane jako relacje na
iloczynach kartezjańskich zbiorów: obiektów, nazw cech oraz
wartości cech.
31
Fragment sieci semantycznej
32
Ramy
Rama jest semantyczną definicją wybranego pojęcia
lub obiektu.
Rama jest strukturą posiadającą nazwę i składa się z
klatek nazywanych szczelinami, które są zbiorami
elementów klatek nazywanych fasetami (ang. facet).
Różnicą między reprezentacją w postaci ram i w
postaci trójek jest to, że w przypadku ram
wartość zapisana w klatce jest jednym z wielu
możliwych elementów klatki (to element typu  value).
33
Przykład ramy
opisujące pojęcie daty
Pokazana rama jest ramÄ…-wzorcowÄ…, a nie zapisem konkretnej daty
34
Scenariusze
Scenariusz to struktura reprezentacji wiedzy przeznaczona do
opisu stereotypowych ciągów zdarzeń lub działań zachodzących
w określonym kontekście.
Scenariusz jest zbudowany ze szczelin.
Szczeliny zawierają opisy ciągów zdarzeń, które mogą wystąpić z
uwzględnieniem zależności występujących między tymi zdarzeniami.
Podstawowe elementy scenariusza to:
-warunki wejściowe (muszą być spełnione aby mogły zajść
zdarzenia),
-wyniki (są zbiorem warunków spełnionych.
Scenariusz pozwala na efektywny zapis wiedzy o złożonych
zdarzeniach oraz ciągów zdarzeń. Scenariusze umożliwiają także
wnioskowanie i porównywanie zdarzeń domyślnych
35
Przykład
struktury
scenariusza
36
Drzewa decyzyjne
Drzewo decyzyjne jest środkiem reprezentacji wiedzy w sposób
deklaratywny.
Drzewo decyzyjne składa się z:
" liści, wskazujących klasę stanu, bądz
rozwiÄ…zanie problemu (ostatnie
węzły decyzyjne na danej gałęzi),
" gałęzi łączących węzły decyzyjne,
" węzłów decyzyjnych,
" korzenia (pierwszy węzeł decyzyjny).
Drzewo decyzyjne może być stosowane jako narzędzie
wspomagajÄ…ce proces wnioskowania. Zastosowanie drzewa
rozpoczyna się od korzenia i odbywa się aż do osiągnięcia liścia.
Drzewa decyzyjne buduje siÄ™:
" metodÄ… indukcji drzew decyzyjnych
37
" na podstawie wiedzy specjalisty/specjalistów
Przykład drzewa decyzyjnego
Patrons?
Some Full
None
No Yes
WaitEstimate?
0-10
>60 30-60
10-30
Alternate? Hungry? Yes
No
Yes No
No Yes
Reservation?
Fri/Sat? Yes Alternate?
No Yes No Yes Yes
No
Bar?
Yes No Yes Yes Raining?
Yes
No No Yes
No Yes No Yes
38
Sieci przekonań
Sieć przekonań jest acyklicznym (nie zawierającym cykli) grafem
skierowanym składającym się z węzłów i łączących je gałęzi
skierowanych.
Węzłom przypisuje się zestawy stwierdzeń i wektory ich wartości.
Gałęziom skierowanym przypisuje się tablice zawierające wartości
prawdopodobieństw warunkowych. Prawdopodobieństwa te
wyznaczane sÄ… na podstawie twierdzenia Bayesa.
W sieci wyróżnia się węzły będące rodzicami i dziećmi.
Prawdopodobieństwa dla węzłów  dzieci zależą od
prawdopodobieństw ich rodziców.
Sieć przekonań może być stosowana jako narzędzie
wspomagania procesu wnioskowania.
39
Przykład sieci przekonań
40
Sieci neuronowe
Sieć neuronowa jest zbudowana z pewnej liczby elementów
przetwarzajÄ…cych nazywanych neuronami. PodstawÄ… budowy sieci
jest system nerwowy człowieka.
Każdemu neuronowi przyporządkowana jest pewna funkcja (funkcja
aktywacji), która określa kiedy dany neuron działa.
Neurony w sieci tworzą warstwy (sieć ma budowę warstwową).
W sieci wyróżnia się warstwę wejściową, wyjściową i warstwy ukryte,
których może być wiele.
Sieć neuronowa może być stosowana jako narzędzie
wspomagania procesu wnioskowania.
41
Dwuwarstwowa sieć neuronowa
Neuron wyjściowy
Neurony ukryte
Neurony wejściowe
42
Tablice decyzyjne
Tablice decyzyjne sÄ… sposobem reprezentacji wiedzy
zapisanej w postaci reguł. Są także jednym z głównych
narzędzi wspomagających proces wnioskowania.
Tablica decyzyjna składa się z:
- części warunków, zapytań i testów, która odpowiada części
przesłankowej reguł,
- części działania i wniosków, która odpowiada częściom
konkluzji reguł,
- wyjść z tablicy decyzyjnej.
Warunkiem koniecznym do uznania tablicy decyzyjnej za
kompletną jest wystąpienie każdej możliwej kombinacji
warunków tylko jeden raz. W przypadku dużych tablic
sprawdzenie tego warunku jest trudne. W tym celu
wprowadza siÄ™ dodatkowe oceny tablicy.
43
Budowa tablicy decyzyjnej
Część Część
opisu warunków
warunków
Część opisu Część
działań
działań
R1 R2
Zazwyczaj dopuszczalnymi
odpowiedziami na zapytania sÄ…
Jeżeli C1 T N
TAK lub NIE (YES, NO). Znak  -
oznacza, że odpowiedz
nie ma
i C2 -T
znaczenia. Działania i wyjścia
zaznacza siÄ™ znakiem  X
to A1 X
to A2 X
44
Tablica decyzyjna - przykład
R1 R2 R3 R4
C1 grypa T T N N
C2 zapalenie płuc T N T N
A1 terapia 1 X - - -
A2 terapia 2 - X - -
A3 terapia 3 - - X -
A4 bez terapii - - - X
Stop X X X X
45
Binarne drzewo decyzyjne
C1
N
T
C2 C2
T N
N
T
A1
A2 A4
A3
R1
R1
R1 R1
46