Sztuczna inteligencja - Podręcznik do wykładów i ćwiczeń - Piotr Fulmański, Marta Grzanek.pdf

(2134 KB) Pobierz
ai.dvi
Sztuczna inteligencja
Podręcznik do wykładów i ćwiczeń
PIOTR FULMAŃSKI, MARTA GRZANEK
154020035.001.png
Piotr Fulmański 1
Wydział Matematyki i Informatyki,
Marta Grzanek 2
Uniwersytet Łódzki
Banacha 22, 90238, Łódź
Polska
email 1: fulmanp@math.uni.lodz.pl, 2: marta@math.uni.lodz.pl
Data ostaniej modyfikacji: 25 maja 2009
154020035.002.png
Spis treści
Wprowadzenie
i
Zawartość podręcznika i uwagi
iii
1 Sztuczna inteligencja 1
1.1 Zarys materiału . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Sztuczna Inteligencja czym jest? . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Cele i zadania szucznej inteligencji . . . . . . . . . . . . . . . . . . . . . . 5
1.4 Wiedza i jej reprezentowanie . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.5 Dziedziny sztucznej inteligencji . . . . . . . . . . . . . . . . . . . . . . . . 7
1.6 Test Turinga . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.6.1 Idea tesu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.6.2 Zarzuty . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.7 Dwa różne pokoje . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.7.1 Chiński Pokój . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.7.2 odpowidz systemu . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.7.3 Jasny Pokój . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2 Reprezentacja i przeszukiwanie 15
2.1 Problem reprezentacji . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2 Problem przeszukiwania . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.3 Kółko i krzyżyk – przykład . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.4 Heurystyka . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.4.1 Heurystyka a algorytm . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.4.2 Pytanie 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.5 Co dalej? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3 Wiedza a język 27
3.1 Logika . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2 Proste fakty . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.3 Rachunek predykatów . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.4 W kierunku języka – postać klauzulowa . . . . . . . . . . . . . . . . . . . 32
3.5 Zapis klauzul . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.6 Rezolucja . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.7 Klauzule Horna . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.8 Co z tego wynika? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
Sztuczna inteligencja. Podręcznik. . . c2008 by P. Fulmański, M. Grzanek (ostatnia modyfikacja: 25 maja 2009)
4
SPIS TREŚCI
4 Podstawowe informacje 41
4.1 Graf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.2 Drzewo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.3 Podstawowe pojęcia z zakresu rachunku prawdopodobieństwa . . . . . . . 41
4.4 Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.4.1 Wektory i wartości własne macierzy . . . . . . . . . . . . . . . . . 45
4.4.2 Określoność macierzy . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.5 Analiza matematyczna . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.5.1 Wzór Taylora . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.5.2 Przestrzeń unitarna . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.5.3 Nierówność Cauchy’egoSchwarza . . . . . . . . . . . . . . . . . . . 48
5 Trochę kalsyki 49
5.1 Przeszukiwanie grafu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
5.1.1 Niezbędne definicje . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
5.1.2 Przechowywanie grafów . . . . . . . . . . . . . . . . . . . . . . . . 50
5.1.3 Rozwiązanie zadania . . . . . . . . . . . . . . . . . . . . . . . . . . 52
6 Algorytmy zachłanne 61
6.1 Wprowadzenie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
6.1.1 Problem wydawania reszty . . . . . . . . . . . . . . . . . . . . . . . 61
6.1.2 Problem plecakowy . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
6.2 Charakterystyka metod zachłannych . . . . . . . . . . . . . . . . . . . . . 63
6.3 Hill climbing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
7 Poszukiwanie optymalnej ścieżki 69
7.1 Best First Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
7.1.1 Opis algorytmu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
7.2 Algorytmy typu brute force . . . . . . . . . . . . . . . . . . . . . . . . . . 79
8 MeansEnds Analysis
81
9 Problem wyboru optymalnego ruchu 91
9.1 Minimax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
9.2 Opis algorytmu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
10 Automaty komórkowe
99
11 Symulacja pożaru 101
11.1 Podejście pierwsze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
11.2 Podejście drugie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
11.3 Podejście trzecie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
12 Symulacja zachowania
105
13 Drzewo decyzyjne jako reprezentacja bazy reguł 107
13.1 Algorytm konstruowania drzewa decyzyjnego . . . . . . . . . . . . . . . . 107
13.1.1 Zadanie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
13.2 Dodatek entropia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
Sztuczna inteligencja. Podręcznik. . . c2008 by P. Fulmański, M. Grzanek (ostatnia modyfikacja: 25 maja 2009)
154020035.003.png
SPIS TREŚCI
5
14 Programowanie dynamiczne
113
14.1 Istota programowania dynamicznego, czyli kiedy programowanie nie jest
programowaniem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
14.1.1 Optymalna podstruktura . . . . . . . . . . . . . . . . . . . . . . . 114
14.1.2 Overlapping subproblems . . . . . . . . . . . . . . . . . . . . . . . 115
14.2 Przykłady zastosowania . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
14.2.1 Dopasowywanie ciągów – algorytm NeedlemanaWunscha . . . . . 117
15 Elementarne wiadomości z biologii 123
15.1 Mózg jako biologiczne CPU . . . . . . . . . . . . . . . . . . . . . . . . . . 123
15.2 Malutkie cegiełki – neurony . . . . . . . . . . . . . . . . . . . . . . . . . . 123
15.3 Budowa komórki nerwowej . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
15.4 Przydatne klasyfikacje . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
15.5 Mózg a rozum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
16 Sztuczna sieć neuronowa 127
16.1 Model neuronu dla informatyka . . . . . . . . . . . . . . . . . . . . . . . . 129
16.2 Elementarny model neuronu . . . . . . . . . . . . . . . . . . . . . . . . . . 130
16.3 Podstawowe architektury sieci neuronowych . . . . . . . . . . . . . . . . . 133
16.4 Nauka sieci – podstawowe modele . . . . . . . . . . . . . . . . . . . . . . . 134
16.5 Podstawowe metody uczenia nadzorowanego w sieciach jednokierunkowych 136
16.5.1 Reguła perceptronowa . . . . . . . . . . . . . . . . . . . . . . . . . 136
16.5.2 Przypadek ciągłej funkcji aktywacji . . . . . . . . . . . . . . . . . . 147
16.5.3 Zasada propagacji wstecznej . . . . . . . . . . . . . . . . . . . . . . 149
16.5.4 Uogólniona reguła delta . . . . . . . . . . . . . . . . . . . . . . . . 155
17 Algorytmy gradientowe uczenia sieci wielowarstwowych skierowanych
do przodu 157
17.1 Metoda najszybszego spadku . . . . . . . . . . . . . . . . . . . . . . . . . 157
17.1.1 Metoda najszybszego spadku z minimalizacją kierunkową . . . . . 159
17.2 Metoda Newtona . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
17.3 Adaptacyjny dobór współczynnika uczenia . . . . . . . . . . . . . . . . . . 163
17.4 Metoda momentu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
17.5 Metody zmiennej metryki . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
17.6 Algorytm gradientów sprzężonych . . . . . . . . . . . . . . . . . . . . . . . 166
17.7 Algorytm LevenbergaMarquardta . . . . . . . . . . . . . . . . . . . . . . 166
18 Sieci samouczące 175
18.1 Wprowadzenie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
18.2 Sieci Kohonena . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
18.2.1 Mechanizm współzawodnictwa . . . . . . . . . . . . . . . . . . . . 177
18.2.2 Miary odległości . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178
18.2.3 Mechanizm zmęczenia neuronów . . . . . . . . . . . . . . . . . . . 180
18.2.4 Miara organizacji sieci . . . . . . . . . . . . . . . . . . . . . . . . . 180
18.2.5 Algorytmy uczenia . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
18.2.6 Funkcja błędu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
18.2.7 Sieć odwzorowań – mapy . . . . . . . . . . . . . . . . . . . . . . . 182
18.3 Uogólniona reguła Hebba . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
Sztuczna inteligencja. Podręcznik. . . c2008 by P. Fulmański, M. Grzanek (ostatnia modyfikacja: 25 maja 2009)
154020035.004.png

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin