1.
Wnioskowanie symboliczne w niepewno ci
1.1.
Niepewno i niekompletno wiedzy.
Rodzaje niepewno ci:
• Niepewno wiedzy podstawowej
• Niepewno działa
• Niepewno postrzegania
Podej cia do rozwi zania problemu niepełnej wiedzy
• Wnioskowanie niemonotoniczne
• Woskowanie statystyczne
• Logika rozmyta
1.2.
Monotoniczno i niemonotoniczno wnioskowania.
Rozszerzane s aksjomaty i reguły, aby móc wnioskowa z nich przy niepełnej
informacji.
W danej chwili system:
• Zapewnia, e zdanie jest prawdziwe, b d bł dne
• Stwierdza ze „nie istniej przesłanki”, e zdanie jest prawdziwe, czy fałszywe.
Logika predykatów jest wystarczaj ca, gdy:
• Informacja jest pełna w okre lonej dziedzinie (posiada wszystkie fakty potrzebne do
rozwi zania)
• Informacja jest spójna (ci gła)
• Jedyny sposób na zmian faktów jest dodanie nowego (nie mo na usuwa
istniej cych).
Monotoniczno – nowe fakty s spójne ze wszystkimi pozostałymi i nic, co zostało
wyprowadzone nie mo e by wycofane z faktów, które s niepodwa alnie prawdziwe.
System inteligentny:
• Daje mo liwo dostosowania do zmian rodowiska
• Gdy pojawi si nowa informacja mo e doda lub wyci gn wnioski
• Wymaga wnioskowania niemonotonicznego
Niemonotoniczno umo liwia:
• U ycie stwierdze niepewno ci „nie wiemy czy …”
• Brak wiedzy uzupełniamy domysłami (zło eniami)
• Nowe stwierdzenia mog zaprzecza poprzednim (jest du e prawdopodobie stwo, e
to nast pi)
• Fragmenty wiedzy s spójne lokalnie, a globalnie nie s spójne.
• Podczas wnioskowania badane s ró ne zestawy alternatywnych przesłanek
niepowoduj cych sprzeczno ci.
Cechy logiki niemonotonicznej:
• Opis zdarze tak jak w logice monotonicznej
• Mo liwo stwierdzenia, e jeste my przekonani do jednego modelu bardziej ni do
drugiego.
• Poleganie na intuicji w ocenie działania wnioskowania
1.3.
Metody reprezentacji wiedzy niepewnej.
Zało enia:
• Je eli brak podstaw by uwa a inaczej zakładamy, e zdanie jest prawd –
normalny(x)
• Domy lnie zakładamy, e wszystko jest normalne
• Nale y dostarczy informacj o wyj tkach
Reprezentacja zdarze uznanych za prawdziwe:
• Logika niemonotoniczna (NLM) – j zyk logiki predykatów poszerzony o operator M,
który odczytujemy jako „jest zgodny z” (brak wyj tku). Zgodno taka nie mo e by
w prosty sposób wykazana tak jak w logice predykatów. Problemem jest brak ró nicy
znaczenia poszczególnych operatorów M, co mo e prowadzi do braku rozwi zania
(romb Nixona).
• Logika zało e (DL) – Np, „je eli A jest mo liwe do udowodnienia i jest spójne z B
to konkluzj jest C” (A:B) / C
Techniki wnioskowania:
• Abduction – w logice klasycznej stosujemy dedukcj , a we wnioskowaniu wstecz
abdukcj (znajdujemy przyczyn znaj c skutek). Próbujemy wykorzysta konkluzje
do wyja nienia obserwowanych faktów. Stosujemy w logice niemonotonicznej.
• Przez dziedziczenie – wnioskowanie mo e odbywa si na podstawie dziedziczenia
atrybutów klas do których obiekt przynale y (warto ci z klas bli szych maj
pierwsze stwo przed warto ciami klas ogólniejszych).
Para (T,A) nazywa si teori niemonotoniczn , gdzie T to zbiór zda , które s
prawdziwe, a A to zbiór zało e , które chcemy poczyni .
Uwa na konsekwencja jest, gdy wszystkie argumenty s za.
Odwa n konsekwencj jest, gdy istniej za i przeciw.
1.4.
Wnioskowanie niemonotoniczne – rozwi zywanie problemów ci gło ci wnioskowania i
wyprowadzanie poprawnych wniosków.
Zadania programów do rozwi zywania problemów NM:
• Budowanie istotnych konkluzji dla problemu
• Od wie anie bazy wiedzy w trakcie wnioskowania
Budowa systemu:
• Problem solver – mechanizmy wnioskowania
o
Wnioskowanie w przód – działa jak wnioskowanie monotoniczne.
o
Wnioskowanie wstecz – okre la czy pewne zdanie jest prawd i szuka zbioru, dla
którego to zdanie jest prawdziwe. Działa jak wnioskowanie niemonotoniczne.
Mo e budowa argumenty „na korzy ”, b d „niekorzy ” i na podstawie
dodatkowej wiedzy stwierdza, które jest silniejsze.
• Truth Maintance System (TMS) – zapewnia spójno i wprowadza nowe fakty
o
System podtrzymywania prawdy oparty na uzasadnieniach (JTMS) – twierdzenia
poł czone s sieci zale no ci, a system nic nie wie o strukturze twierdze .
Konkluzje (w zły) s prawdziwe, je li przesłanki w li cie „do” s prawdziwe i nic
z listy „z” nie jest prawdziwe. Twierdzenie jest niemonotoniczne, gdy w li cie „z”
jest jakie twierdzenie lub w li cie do jest niemonotoniczne uzasadnienie. Przez
„z” oznaczamy w zeł, o którym nic nie wiemy, b d my limy, e jest kłamstwem.
o
System podtrzymywania prawdy oparty na logice (LTMS)
o
System podtrzymywania prawdy oparty na zało eniach (ATMS) – brak wstecznej
propagacji; alternatywne cie ki badane s równolegle; wszystkie twierdzenia
niezaprzeczalnie prawdziwe s przycinane, a do osi gni cia sprzeczno ci.
• Mechanizmy przeszukiwania:
o
W gł b – ledzimy najbardziej prawdopodobna cie k a znajdziemy informacj ,
lub obieramy inn drog .
o
W szerz – rozwa amy wszystkie mo liwo ci jako równie prawdopodobne i
eliminujemy tylko niektóre, gdy dost pne s nowe fakty.
2.
Wnioskowanie statyczne i oparte na współczynnikach pewno ci
2.1.
Wnioskowanie statyczne
Prawdopodobie stwo wyst pienia zdarzenia jest odsetkiem jego wyst pie .
Symbole: p – prawdopodobie stwo powodzenia, q – prawdopodobie stwo pora ki, f –
liczba pora ek, s – liczba powodze .
Wzór:
, q=1-p
• Zdarzenie niezale ne – wzajemnie wykluczaj ce si .
• Zdarzenie zale ne – wyst puj równolegle i wzajemnie wpływaj na
prawdopodobie stwo wyst pienia.
• Prawdopodobie stwo warunkowe – wyst pi A pod warunkiem, e wyst pi B:
• Prawdopodobie stwo ł czne:
Reguła Bayes`a:
Interpretacja:
• Je eli zdarzenie A zale y od zdarzenia B, to ich warunkowe wyst pienie opisuje
zale no nazwan „reguł Bayes`a”
• Rozpatrywanie wielu zdarze :
Z tego wynika, e:
Wnioskowanie probabilistyczne:
• Dane dostarczane s do systemu przez ekspertów lub wynikaj ze zgromadzonych
danych i oblicze .
• Je li jest wiele hipotez to musz si one wzajemnie wyklucza .
• Gdy pojawi si wiele hipotez i dowodów:
• Wska niki:
o
L – wska nik wiarygodno ci
LS – miara ufno ci w hipotez H, gdy spełniony został dowód D
LN – miara pomniejszenia przekonania o hipotezie H, gdy brak dowodu D
o
O – iloraz szans
• Nie trzeba wykorzystywa prawdopodobie stw warunkowych tylko iloraz szans i
wska nik wiarygodno ci
Przykłady:
2.2.
Wnioskowanie ze współczynnikami ufno ci
Alternatywa dla wnioskowania Bayes`a. Znajduje zastosowanie, gdy brak jest spójnych
danych statystycznych. Na laduje procesy my lowe prowadzone przez człowieka.
MYCIN – medyczny system ekspertowy stosuj cy współczynniki ufno ci. Nie jest oparty
na matematycznych, czy logicznych zale no ciach mi dzy danymi. Jego celem było
wyznaczanie terapii i stawianie diagnoz przy chorobach krwi.
Współczynniki:
• Współczynnik „cf” – miara przekona eksperta (-1 fałsz, 1 prawda, >0 przekonanie o
hipotezie, <0 brak przekonania).
• Współczynnik „MB” – miara przekonania o hipotezie. Ekspert ocenia jak bardzo,
przedstawiony dowód redukuje jego w tpliwo ci w wypadku braku dowodu. Je eli
dowód b dzie słaby to w tpliwo ci nie ulegn zmianie. Przyjmuje od 0 do 1.
• Współczynnik „MD” – ekspert ocenia jak bardzo przedstawiony dowód D redukuje
jego przekonanie o hipotezie p(H).
Z tego wynika:
Dla pojedynczego dowodu mamy:
2.3.
Porównanie technik
Wykorzystanie sieci Bayes`a:
• Planowanie, tam gdzie dost pne s dane statystyczne
• Matematycznie poprawny (teoria prawdopodobie stwa)
• Przykład: PROSPECTOR – geologia
Wykorzystanie współczynnika pewno ci:
• Prognozowanie tam gdzie brak jest danych statystycznych
• Break poprawno ci matematycznej. Dane pochodz z ocen ekspertów danej
dziedziny.
• Przykład: MYCIN – medycyna.
Cechy wspólne:
• Propagowanie przekona wzrasta wykładniczo, dlatego nie nadaje si dla bardzo
du ych baz wiedzy
• Problemem jest znalezienie wła ciwej metody okre lania prawdopodobie stw i
współczynników, poniewa ludzie s tendencyjnie w ocenach.
3.
Logika rozmyta
3.1.
Teoria zbiorów rozmytych
Ukazuje, e nie wszystko jest czarne lub białe, a e istniej te stany po rednie. Mówi, e
element nale y do zbioru z danym stopniem przynale no ci.
Rodzaj stosowanej funkcji jest dobierany przez eksperta lub ekspertów, b d poprzez
efekt nauki sieci neuronowej.
Sformułowania:
• Suport – baza
• Core – jadro
• a-cut – ci cie
• Wysoko
Operacje:
• Dopełnienie – jak bardzo element nie przynale y do zbioru
• Zawieranie si – który zbiór rozmyty nale y do innych zbiorów rozmytych
• Iloczyn – jak bardzo element przynale y do obu zbiorów
• Suma – jak bardzo element przynale y do jednego z obu zbiorów
• Przeci cie
• Unia
Cechy:
• Przemienno
• Ł czno
• Rozdzielno OR wzgl dem AND i AND wzgl dem OR
• Podwójne zaprzeczenie
• Przechodnio
• Prawo de Morgana
3.2.
Zmienne lingwistyczne
3.3.
Reguły rozmyte
Czynno ci wst pne:
• Okre lenie reguł rozmytych
• Okre lenie funkcji przynale no ci do warto ci wej i wyj
Główne kroki:
• Rozmycie wej poprzez u ycie funkcji przynale no ci (fuzyfikacja)
• Ł czenie rozmytych przesłanek (wej ) poprzez rozmyte reguły by uzyska rozmyte
konsekwencje (z wielu reguł)
• Ł czenie wniosków by otrzyma ostateczny rozkład wyj cia
• Defuzyfikacja wyj cia, gdy musimy uzyska jednoznaczn odpowied
Fuzyfikacja:
• Wej cia do systemu s jednoznaczne (liczbowe, ostre)
• Dane mog mie ró ne pochodzenie
• Ka de wej cie jest zamieniane na warto rozmyt poprzez funkcj przynale no ci
Agregacja reguł – proces ł czenia wszystkich reguł wyj ciowych w jeden zbiór rozmyty.
Najcz ciej wykorzystuje si operator „max”.
Defuzyfikacja – proces uzyskiwania jednoznacznej (ostrej) warto ci jako wyniku
wnioskowania. Stosuje si metody:
•
rodka ci ko ci (Center of Gravity) – najpopularniejsza
•
rodka maksimum (Mean of Maximum)
• Pierwszego maksimum (First of Maxima)
3.4.
Wnioskowanie rozmyte:
3.4.1.
typu Mamdani
Wnioskowanie typu Mamdani nie jest korzystnie obliczeniowo, poniewa nale y
wyznacza centra dwuwymiarowych figur.
3.4.2.
typu Sugeno
Stosuje pojedyncze warto ci (singeltony) jako funkcje przynale no ci
znalezionych konsekwencji. Maj one warto ci ró ne od zera tylko w jednym
punkcie.
3.4.3.
Porównanie
Segueno:
• Efektywny obliczeniowo
• Pracuje poprawnie z technikami liniowymi
• Jest wydajny dla technik optymalizacji i adaptacji
• Gwarantuje ci gło płaszczyzny wyj ciowej
• Dopasowany do analiz matematycznych
Mamdani:
• Jest intuicyjny
• Metoda szeroko wykorzystywana i akceptowana
• Dobrze dopasowana do wej opisywanych przez człowieka
3.4.4.
Zastosowanie
• Wsz dzie tam, gdzie trudno jest utworzy matematyczny model, ale daje si
opisa sytuacj w sposób jako ciowy, za pomoc reguł rozmytych
• Kontrolery rozmyte (przemysł)
• Inteligentne lodówki, pralki, windy, aparaty fotograficzne
• Zastosowania medyczne – nieprecyzyjny j zyk daje si przeło y na reguły
rozmyte
• Technika: synteza j drowa, ustalanie drogi przelotu samolotu, sterowanie
procesem spalania paliw w elektrowniach, kontrola pr dko ci ci arówki,
sterowanie procesem produkcji penicyliny, kontrola ruchu ulicznego,
mikrokontrolery (68HC12 MCU)
4.
Sztuczne sieci neuronowe
4.1.
Model sztucznego neuronu
Neurony poł czone s powi zaniami o nadanych parametrach zwanymi „wagami”, które
s modyfikowane podczas uczenia. Rozwi zaniem sieci neuronowej s warto ci
pojawiaj ce si na wyj ciu dla zadanych warto ci wej ciowych.
Model McCulloch-Pitts`a:
• Pierwszy opis matematyczny neuronu – 1943
• Neuron jako przetwornik
• Ka de wej cie jest mno one przez jego wag
• Sygnały wej ciowe s sumowane i poddawane działaniu „funkcji aktywacji”
Typy funkcji aktywacji:
• Nieci głe
o
Progowa
o
Signum
• Ci głe
o
Liniowa
o
Sigmoidalna
o
Gaussa
Typy sieci neuronowych (ze wzgl du na 3x funkcj aktywacji / 3x architektur )
• Liniowe
• Nieliniowe
• Radialne (funkcja Gaussa)
• Jednokierunkowe
• Ze sprz eniami zwrotnymi
• Mieszane
4.2.
Perceptron prosty
Składa si z jednej warstwy neuronów. Wymy lił j Rosenblatt w 1962. Jest najstarsz
koncepcj sieci neuronowych.
4.3.
Uczenie reguł DELTA
Algorytm uczenia reguł DELTA wymaga podania dla ka dego zestawu wej U,
warto ci odpowiedzi Z. Neuron na zadane sygnały U odpowiada pewn warto ci Y.
Je eli jest ona ró na od Z to neuron nie jest nauczony odpowiedzi na sygnał U. Bł d
popełniany przez sie jest równy:
Celem procesu uczenia jest uzyskanie odpowiedzi Y zgodnych z zadanymi
odpowiedziami Z, co mo na okre li jako proces minimalizacji funkcji:
4.4.
Metoda gradientowa DELTA
Perceptronowi funkcja kryterium: J(W) jest sum odległo ci od płaszczyzny decyzyjnej
le sklasyfikowanych wektorów z podzbioru U.
Je eli J(W)=0 to klasyfikacja jest poprawna.
4.5.
Uczenie DELTA dla sieci wielowarstwowych
Cechy:
• Funkcja aktywacji musi by ci gła i ró niczkowalna w całej dziedzinie
• Problemem jest wyznaczenie korekty wag w warstwach ukrytych
• Algorytm nazywa si uczeniem metod wstecznej propagacji
• Uczenie z „nauczycielem”
Wsteczna propagacja:
• Pocz tkowo wagi przybierane s losowo
• Modyfikacja wag nast puje dla ka dej pary wej cie-wyj cie (znana odpowied )
• Ka da para wymaga przej cia oblicze w przód i wstecz
• Krok w przód oblicza dla zadanych wej sygnał wyj ciowy
• Krok wstecz, porównuje otrzymane wyj cie z oczekiwanym wynikiem i obliczany jest
bł d dla jednostek wyj ciowych
• Zmiana wag poł cze ma doprowadzi do zmniejszenia bł du
• Bł d propagowany jest wstecz przez poł czenia ukryte
• Jedna epoka jest to prezentacja wszystkich wzorców (zazwyczaj jest kilka epok)
Zadania sieci jednokierunkowych:
• Klasyfikacja
• Projektowanie układów VLSI
• Rozpoznawanie wzorców
4.6.
Uczenie bez nauczyciela (nienadzorowane)
Sieci przedstawia si tylko wzorce (bez poprawnych odpowiedzi). Celem sieci jest
znalezienie ukrytych zale no ci pomi dzy danymi. Sie próbuje nauczy si struktury
danych.
4.6.1.
Reguła Hebba
Wzmocnieniu ulegaj te wagi, których wej cia U s aktywne w sytuacji, gdy du e
jest wzbudzenie neuronu Y. Reguła prowadzi do uzyskania najlepszej korelacji
pomi dzy sygnałami wej ciowymi, a zapami tanymi w wagach wzorcami.
Sie autoasocjacyjna – je eli pewien wzór wzbudze jest sygnalizowany przez
pewne wyj cie Y, to w miar upływu czasu ta sygnalizacja staje si coraz
wyra niejsza.
Zalety:
• Sama organizuje sygnały wej ciowe w klastry
• Silnie zale y od wylosowanych na pocz tku procesu uczenia wag. Warto ci te
oznaczaj wrodzone skłonno ci sieci i b d si one pogł bia w trakcie uczenia.
• Liczba neuronów powinna by wi ksza, ni liczba klas
• Nie wiemy, który neuron b dzie odpowiedzialny za rozpoznanie konkretnej
klasy (np. rozpoznawanie liter)
• Mo e si zdarzy , e aden neuron nie nauczy si rozpoznawania jednej z klas
• Du a wra liwo na szumy
• Wagi rosn bez ograniczenia
Współczynnik zapominania – Decay Rate:
• Rozwi zuje problem wzrostu wag
• Eliminuje małe szumy
• Je eli systematycznie nie prezentuje si danego wzorca, to zostanie on zniesiony
przez współczynnik zapominania
• Znacznie dłu ej trwa eliminacja szumu
4.6.2.
Instar
Wagi pomniejszane s tylko, gdy wyj cie jest aktywne. Wektor wag przemieszcza
si w kierunku wektora wej .
Koncepcja:
• Wybiera si jeden neuron i narzuca mu strategi uczenia, by zapami tywał i
potrafił rozpozna sygnał U
• Inne neurony s w tym czasie bezczynne
• Stosuje si , gdy trzeba nauczy sie rozpoznawania okre lonego sygnału U
4.6.3.
Outstar
Wagi s zmniejszane tylko, gdy wej cia s aktywowane. Wektor wag przemieszcza
si w kierunku wektora wyj .
Koncepcja:
• Rozwa a si wagi wszystkich neuronów w całej warstwie, ale wybiera si tylko
wagi ł cz ce neurony z pewnym ustalonym wej ciem (arbitralnie)
• Stosuje si , gdy sie ma wytwarza okre lony wzorzec zachowa Y w
odpowiedzi na pewien inicjuj cy sygnał.
4.6.4.
Sieci Kohonena
Uczenie z rywalizacj . Reguła ta wywodzi si z Instar. Wektor wej U musi by
znormalizowany. Nie wybiera si arbitralnie neuronu do uczenia, tylko uczy si ten,
który „zwyci a” (ma najwi kszy sygnał wyj ciowy). Tylko zwyci zca jest uczony,
a jego wagi zmieniane s tak, aby najlepiej dopasował si do wektora wej ciowego,
którego si uczy. Inne wektory wag nie zmieniaj si .
Algorytm:
• Wybiera obiekt ze zbioru ucz cego
• Znajduje w zeł najbli szy wybranej danej (odległo pomi dzy W i danymi U
jest minimalna)
• Zmie wektor wag wybranego w zła i jego s siadów zgodnie z reguł
• Powtarzaj zgodnie z ustalon ilo ci razy
4.7.
Sie ze sprz eniem zwrotnym – Hopfielda
Brak podziału na warstwy. W pierwowzorze ka dy neuron poł czony jest z ka dym, a
sygnały wyj ciowe przekierowywane s jako wej cia.
Pami :
• Jest adresowana zawarto ci , a nie przez miejsce przechowywania
• Przypomnienie nast puje poprzez pami tanie pewnych cech: koloru, włosów, zapachu
• Pewna liczba wzorców jest przechowywana w sieci
• Aby odzyska wzorzec wystarczy poda jego fragment
• Sie automatycznie znajdzie najbli szy podobny
Reprezentacja rozproszona:
• Wspomnienie jest przechowywane jako wzorzec aktywacji zbioru elementów
• Wspomnienia mog by nakładane na siebie
• Ró ne wspomnienia s reprezentowane przez ró ne wzorce tego samego zbioru
elementów
Sterowanie rozproszone, asynchroniczne:
• Ka dy element przetwarzaj cy (neuron) podejmuje decyzje na podstawie jego
lokalnych partnerów
• Lokalne zmiany dodawane s do ogólnego rozwi zania
Tolerancja bł du
• Je eli jaki element sieci pomyli si lub zadziała niepoprawnie, sie jako cało nadal
b dzie działa poprawnie
Model sieci:
• Poł czenia ka dy z ka dym
• Poł czenia dwukierunkowe
Warunki stabilno ci:
• Wyj cie neuronu M nie jest kierowane ja jego wej cie
• Wagi poł cze neuronu M i K s symetryczne:
4.8.
Model Hopfielda
Elementy sieci s albo aktywne (czarne), albo nieaktywne (białe). Elementy poł czone s
poprzez wa one symetryczne poł czenia. Warto ci dodatnie poł cze oznaczaj , e
elementy nawzajem si aktywuj , a poł czenia ujemne, e dezaktywuj .
Algorytm:
• Wybieramy losowo neuron
• Je eli jakikolwiek s siad jest aktywny obliczamy wa on sum poł cze do
aktywnych s siadów
• Je eli suma jest dodatnia to neuron si aktywuje, je li nie to si dezaktywuje
• Losujemy kolejny neuron i post pujemy według algorytmu, a do uzyskania stanu
stabilnego. Proces nazywa si równoległ relaksacj .
Funkcja energii:
• Stan sieci Hopfielda składaj cej si z N w złów w czasie t mo na opisa przez wektor
(y
i
(t),…, y
n
(t)), gdzie y(t) jest wyj ciem i-tego neuronu w czasie t
• Energi sieci w jednostce czasu definiuje si jako:
Działanie sieci Hopfielda mo e by uto samiane z procesem minimalizacji funkcji
energii. Sie sprowadza poziom energii do najbli szego wzorca przykładowego. Pozycje
minimów funkcji energii s zdeterminowane przez warto ci wag.