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.