Systemy decyzyjne MIM UW 2011, MIESI
[ Pobierz całość w formacie PDF ]
Matematykastosowana
Systemy decyzyjne
Hung Son Nguyen
son@mimuw.edu.pl
Uniwersytet Warszawski, 2011
Streszczenie.
Przegl¡d metod klasyfikacji i wspomagania podejmowania de-
cyzji na podstawie niepełnych i niepewnych informacji. Przedstawiane metody
pochodz¡ z ró»nych dziedzin, takich jak uczenie maszynowe (ang. machine le-
arning), statystyka, teoria zbiorów rozmytych (ang. fuzzy sets), teoria zbiorów
przybli»onych (ang. rough sets). Przewidziane s¡ zaj¦cia praktyczne z syste-
mami wspomagania decyzji oraz zadania projektowe polegaj¡ce na stworzeniu
własnych systemów decyzyjnych.
Wersja internetowa wykładu:
(mo»e zawiera¢ dodatkowe materiały)
Niniejsze materiały s¡ dost¦pne na
Uznanie autorstwa — U»ycie niekomercyjne — Bez utworów zale»nych
.
Copyright c
H.S. Nguyen, Uniwersytet Warszawski, Wydział Matematyki, Informatyki i Mechaniki, 2011. Ni-
niejszy plik PDF został utworzony 13 kwietnia 2011.
Projekt współfinansowany przez Uni¦ Europejsk¡ w ramach
Skład w systemie L
A
T
E
X, z wykorzystaniem m.in. pakietów
beamer
oraz
listings
. Szablony podr¦cznika i prezentacji:
Piotr Krzy»anowski; koncept: Robert D¡browski.
Spis tre±ci
1. Wprowadzenie do systemów decyzyjnych
. . . . . . . . . . . . . . . . . . . . . . . . . . .
5
1.1.
Wprowadzenie do systemów decyzyjnych
. . . . . . . . . . . . . . . . . . . . . . . . . . .
5
1.1.1.
Elementy systemów decyzyjnych
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
1.1.2.
Sprawy organizacyjne
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
2. Problem klasyfikacji i klasyfikatory
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
2.1.
Problem klasyfikacji i klasyfikatory
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
2.1.1.
Wprowadzenie
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
2.1.2.
Przegl¡d metod klasyfikacji
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
3. Metody oceny klasyfikatorów
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
3.1.
Metody oceny klasyfikatorów
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
3.1.1.
Skuteczno±¢ predykcji
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
3.1.2.
Przedział ufno±ci miar ocen
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
20
3.1.3.
Metody walidacji danych
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22
3.1.4.
Krzywy Lift i ROC
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
4. Zbiory przybli»one
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
25
4.1.
Zbiory przybli»one
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
25
4.1.1.
Wprowadzenie do teorii zbiorów przybli»onych
. . . . . . . . . . . . . . . . . . . .
25
4.1.2.
Zło»ono±¢ problemu szukania reduktów
. . . . . . . . . . . . . . . . . . . . . . . .
29
5. Wnioskowanie Boolowskie w obliczaniu reduktów i reguł decyzyjnych
. . . . . . . . .
30
5.1.
Wnioskowanie Boolowskie w obliczaniu reduktów i reguł decyzyjnych
. . . . . . . . . . .
30
5.1.1.
Metody wnioskowa« Boolowskich w szukaniu reduktów
. . . . . . . . . . . . . . .
30
5.1.2.
Systemy decyzyjne oparte o zbiory przybli»one
. . . . . . . . . . . . . . . . . . . .
36
6. Metoda drzew decyzyjnych
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
40
6.1.
Metoda drzew decyzyjnych
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
40
6.1.1.
Wprowadzenie
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
40
6.1.2.
Konstrukcja drzew decyzyjnych
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
44
7. Problem dyskretyzacji
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
48
7.1.
Problem dyskretyzacji
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
48
7.1.1.
Przypomnienia podstawowych poj¦¢
. . . . . . . . . . . . . . . . . . . . . . . . . .
48
7.1.2.
Problem dyskretyzacji
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
49
7.1.3.
Dyskretyzacja metod¡ wnioskowania Boolowskiego
. . . . . . . . . . . . . . . . . .
54
8. Sieci neuronowe
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
57
8.1.
Sieci neuronowe
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
57
8.1.1.
Sztuczne sieci neuronowe
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
57
9. Teoria systemów ucz¡cych si¦
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
65
9.1.
Teoria systemów ucz¡cych si¦
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
65
9.1.1.
Wst¦p do komputerowego uczenia si¦ poj¦¢
. . . . . . . . . . . . . . . . . . . . . .
65
9.1.2.
Model PAC (probably approximately correct)
. . . . . . . . . . . . . . . . . . . .
67
9.1.3.
Wyuczalno±¢ klasy poj¦¢
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
68
9.2.
Wymiar Vapnika-Chervonenkisa
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
69
9.2.1.
Wymiar Vapnika Chervonenkisa (ang. VC dimension)
. . . . . . . . . . . . . . . .
69
9.2.2.
Podstawowe twierdzenia teorii uczenia si¦
. . . . . . . . . . . . . . . . . . . . . . .
71
9.2.3.
Appendix: „Nie ma nic za darmo” czyli “Non Free Lunch Theorem”
. . . . . . . .
72
Systemy decyzyjne c
H.S. Nguyen, Uniwersytet Warszawski, 2011.
4
Spis tre±ci
10.SVM: Maszyny wektorów podpierajacych
. . . . . . . . . . . . . . . . . . . . . . . . . . .
74
10.1. SVM: Maszyny wektorów podpierajacych
. . . . . . . . . . . . . . . . . . . . . . . . . . .
74
10.1.1. Wprowadzenie
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
74
10.1.2. Brak liniowej separowalno±ci danych
. . . . . . . . . . . . . . . . . . . . . . . . . .
78
10.1.3. Implementacja
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
80
11.Metoda wzmacnienia klasyfikatorów (ang. Boosting)
. . . . . . . . . . . . . . . . . . . .
82
11.1.
Metoda wzmacnienia klasyfikatorów (ang. Boosting)
. . . . . . . . . . . . . . . .
82
11.1.1. Wst¦p
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
82
11.1.2. AdaBoost - opis algorytmu
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
82
11.1.3. AdaBoost - bł¡d na zbiorze treningowym
. . . . . . . . . . . . . . . . . . . . . . .
86
11.1.4. AdaBoost - bł¡d uogólnienia
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
88
11.1.5. Podsumowanie
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
88
12.Ukryty model Markowa
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
90
13.Sterowanie rozmyte
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
91
13.1. Sterowanie rozmyte
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
91
13.1.1. Wprowadzenie
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
91
13.1.2. Zagadnienia sterowania
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
94
13.1.3. Sterowanie rozmyte
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
95
Literatura
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
99
1. Wprowadzenie do systemów decyzyjnych
1.1. Wprowadzenie do systemów decyzyjnych
1.1.1. Elementy systemów decyzyjnych
Wprowadzenie do teorii uczenia si¦
Kto si¦ uczy?
Ograniczymy si¦ do programów komputerowych zwanych ”
algorytmami ucz¡cymi si¦
”.
Czego si¦ uczy?
—
poj¦¢
: – np. odró»nienie “krzeseł” od innych mebli.
—
nieznanych urz¡dze«
– np. u»ywanie VCR
—
nieznanych ±rodowisk
– np. nowe miasto
—
procesów
– np. pieczenie ciasta
—
rodzin podobnych wzorców
– np. rozp. mowy, twarzy lub pisma.
—
funkcji
: (np. funkcje boolowskie)
Wymagania
skuteczno±¢, efektywno±¢, ...
Ka»dy “ucze«” powinien mie¢ zdolno±¢ uogólnienia, t.j. zdolno±¢ rozpoznawania ró»nych
obiektów tego samego poj¦cia.
Np. je±li uczymy si¦ funkcji, to wa»ne jest aby “algorytm uczenia si¦” nie ograniczał
si¦ do jednej konkretnej funkcji. ¡damy aby “modele uczenia” działały skutecznie na
klasach funkcji.
Ucze« mo»e pozyska¢ informacje o dziedzinie poprzez:
1.
Przykłady:
Ucze« dostaje pozytywne i/lub negatywne przykłady. Przykłady mog¡ by¢
zdobywane w sposób:
a)
losowy:
według pewnego znanego lub nieznanego rozkładu;
b)
arbitralny
;
c)
zło±liwy:
(np. przez kontrolera, który chciałby wykry¢ sytuacj¦, kiedy algorytm zachowuje si¦ najgorzej);
d)
specjalny przez »yczliwego nauczyciela:
(np., staraj¡cego ułatwia¢ proces uczenia si¦)
2.
Zapytania:
ucze« zdobywa informacje o dziedzinie przez zadawanie nauczycielowi zapyta«.
3.
Eksperymentowanie:
aktywne uczenie si¦.
—
Podej±cie indukcyjne:
wnioskowanie na podstawie sko«czonego zbioru obserwacji;
— Np. Pokaza¢, »e dla ka»dego
n
2
N
1
2
+ 2
2
+
...
+
n
2
=
n
(
n
+ 1)(2
n
+ 1)
6
— Jakie prawa rz¡dz¡ w podej±ciu uczenia indukcyjnego?
Szukamy teorii pozwalaj¡cej na oszacowanie
Systemy decyzyjne c
H.S. Nguyen, Uniwersytet Warszawski, 2011.
[ Pobierz całość w formacie PDF ]