1

Metody sztucznej inteligencji

Politechnika Śląska

Katedra Podstaw Konstrukcji Maszyn

Rok akademicki 2005/2006

Wykład 7

2

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.

3

System doradczy

4

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

5

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

6

Przykłady systemów doradczych

ABEL

Wyznaczanie relacji przyczynowo-skutkowych
w diagnostyce medycznej,

FAULTFINDER Diagnostyka komputerów

REACTOR

Diagnostyka siłowni jądrowych

STEAMER

Szkolenie operatorów w siłowni jądrowej

HEARSAY I, II

Rozpoznawanie tekstów mówionych w języku angielskim

GUIDON

Kształcenie lekarzy

INTERNIST

Diagnostyka medyczna

CAA

Interpretowanie postaci kardiogramów

DART

Diagnostyka maszyn cyfrowych

DENTRAL

Identyfikacji wyników spektrografiii masowej

MYCIN

Stawianie diagnozy i ustalanie terapii podczas
leczenia zakażenia krwi oraz zapalenia opon
mózgowo-rdzeniowych

7

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

8

Przykład dialogu z systemem MYCIN

9

Główne elementy systemu

doradczego

10

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:
< <ATRYBUT>,<OBIEKT>, WARTOŚĆ>>

11

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)

12

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

13

Przykład przebiegu

wnioskowania

14

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

15

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)

16

Reprezentacja danych

i wiedzy

17

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)

18

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

19

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

20

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

21

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ń

22

Ś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.

23

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

24

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:
<A,O,V>=<<Nazwa atrybutu>,<Obiekt>,<Wartość atrybutu>>

Nazwa atrybutu jest parą:
<Nazwa atrybutu>=<<Charakter posiadania cechy>,

<nazwa cechy>>

Charakter posiadania cechy ma wartość: „posiada” lub „jest”.

25

Stwierdzenia (2)

Przykład:

<„posiada nogi”, „krzesło”, „cztery”>

Jako predykat:
posiada_nogi (krzesło,cztery)

<Nazwa obiektu>

= „krzesło”

<Nazwa cechy>

= „nogi”

<Charakter posiadania cechy>

= „posiada”

<Wartość cechy>

= „cztery”

26

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)

27

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ć:
<A,O,V,CF>=<<Nazwa atrybutu>,<Obiekt>,<Wartość
atrybutu>,<Stopień pewności>>

28

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:
<A,O,V,W,T,CF>=<<Nazwa atrybutu>,<Obiekt>,

<Wartość atrybutu>,<Waga>,

<Przedział czasu>,<Stopień pewności>>

29

Reguły

Reguły zapisuje się w postaci implikacji:

if PRZESŁANKA then KONKLUZJA
lub
jeżeli PRZESŁ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: <A,O,V> lub
<A,O,V,CF>.

30

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.

31

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,T,R> (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.

32

Fragment sieci semantycznej

33

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 <A,O,V> jest to, że w przypadku ram
wartość zapisana w klatce jest jednym z wielu
możliwych elementów klatki (to element typu „value).

34

Przykład ramy

opisujące pojęcie daty

Pokazana rama jest ramą-wzorcową, a nie zapisem konkretnej daty

35

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

36

Przykład
struktury
scenariusza

37

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ądź 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
• na podstawie wiedzy specjalisty/specjalistów

38

Przykład drzewa decyzyjnego

Yes

Patrons?

No

Reservation?

Bar?

Yes

No

WaitEstimate?

Alternate?

Hungry?

Yes

Fri/Sat?

Yes

Alternate?

Yes No

Yes

Yes

Raining?

No

Yes

No

None

Some

Full

0-10

10-30

30-60

>60

No

Yes

No

Yes

No

Yes

No

Yes

No

Yes

No

Yes

No

Yes

39

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.

40

Przykład sieci przekonań

41

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.

42

Dwuwarstwowa sieć neuronowa

Neuron wyjściowy

Neurony ukryte

Neurony wejściowe

43

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.

44

Budowa tablicy decyzyjnej

Część

opisu

warunków

Część

warunków

Część opisu

działań

Część

działań

R1 R2

Jeżeli C1
i C2

T N
-

T

to A1
to A2

X

X

Zazwyczaj dopuszczalnymi
odpowiedziami na zapytania są
TAK lub NIE (YES, NO). Znak „-”
oznacza, że odpowiedź nie ma
znaczenia. Działania i wyjścia
zaznacza się znakiem „X”

45

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

46

Binarne drzewo decyzyjne

C1

C2

C2

A1

A2

A3

A4

T

T

T

N

N

N

R1

R1

R1

R1