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:
Przykłady: Uczeń dostaje pozytywne i/lub negatywne przykłady. Przykłady mogą być zdobywane w sposób:
losowy: według pewnego znanego lub nieznanego rozkładu;
arbitralny;
złośliwy: (np. przez kontrolera, który chciałby wykryć sytuację, kiedy algorytm zachowuje się najgorzej);
specjalny przez życzliwego nauczyciela: (np., starającego ułatwiać proces uczenia się)
Zapytania: uczeń zdobywa informacje o dziedzinie przez zadawanie nauczycielowi zapytań.
Eksperymentowanie: aktywne uczenie się.
<+->Podejście indukcyjne: wnioskowanie na podstawie skończonego zbioru obserwacji;
<+-> Np. Pokazać, że dla każdego
![]() |
<+-> Jakie prawa rządzą w podejściu uczenia indukcyjnego?
Szukamy teorii pozwalającej na oszacowanie
Prawdopodobieństwa wyuczenia się pojęć;
Liczby niezbędnych przykładów treningowych;
Złożoności przestrzeni hipotez;
Skuteczności aproksymacji;
Jakość reprezentacji danych treningowych;
Skąd wiemy, czy uczeń się nauczył lub jak dobrze się nauczył?
Miara jakości wsadowa (ang. off-line, batch) i miara interaktywna (ang. on-line, interactive).
Jakość opisu vs. jakość predykcji
Skuteczność: obliczona na podstawie błędu klasyfikacji, dokładności opisu …
Efektywność uczenia: wymagana jest wielomianowa złożoność obliczeniowa.
Załóżmy, że chcemy nauczyć się pojęcia ”człowieka o średniej
budowie ciała”. Dane – czyli osoby – są reprezentowane przez punkty
i są etykietowane przez
dla pozytywnych
przykładów i
dla negatywnych.
Dodatkowa wiedza: szukane pojęcie można wyrazić za pomocą PROSTOKĄTA
Na przykład dany jest etykietowany zbiór:
,
,
,
,
,
,
,
Znajdź etykietę
Roważany problem możemy zdefiniować problem następująco:
<+-> Cel: Znaleźć w prostokąt
o bokach równoległych do osi.
<+-> Wejście: Zbiór zawierający przykłady w postaci punktów .
Punkty z tego zbioru zostały wygenerowane losowo.
<+-> Wyjście: Hipotetyczny prostokąt będący “'dobrą
aproksymacją”
.
<+-> Dodatkowe wymagania: Algorytm powinien być efektywny (ze wzgledu na złożoność obliczeniową) i powinien używać do uczenia jak najmniejszej liczby przykładów .
Przy ustalonych zbiorach pojęć (dotyczących obiektów ze zbioru
- skończonego lub nie) oraz hipotez
rozważamy następujacy problem
<+-> Dane:
skończona próbka obiektów
wraz z wartościami
pewnej funkcji
ze zbioru
na tych obiektach;
<+-> Szukane:
hipoteza będąca dobrą aproksymacją pojęcia
.
<+-> Żądania:
dobra jakość aproksymacji
szybki czas działania.
Uczenie półosi (lub dyskretyzacji):
![]() |
Uczenie hiperpłaszczyzny:
![]() |
gdzie .
Uczenie jednomianów Boolowskich:
![]() |
= zbiór jednomianów Boolowskich o
zmiennych.
Niech
– zbiór wszystkich obiektów.
– przestrzeń probabilistyczna określona na
.
Błąd hipotezy względem pojęcia
(funkcji docelowej):
![]() |
Dane jest pojęcie , hipoteza
i zbiór przykladów
. Jak
oszacować rzeczywisty błąd hipotezy
na podstawie jej błędu
na zbiorze
?
Jeśli przykłady z są wybrane zgodnie z miarą prawdopodobieństwa
niezależnie od tej hipotezy i niezależnie od siebie nawzajem oraz
, to
najbardziej prawdopodobną wartością jest
,
z prawdopodobieństwem
![]() |
Teoria zbiorów przybliżonych została wprowadzona w latach 80-tych przez prof. Zdzisława Pawlaka.
Głównym celem jest dostarczanie narzędzi dla problemu aproksymacji pojęć (zbiorów).
Zastosowania w systemach decyzyjnych:
Redukcja danych, selekcja ważnych atrybutów
Generowanie reguł decyzyjnych
Odkrywanie wzorców z danych: szablony, reguły asocjacyjne
Odkrywanie zależności w danych
Przykład
Pacjent | Wiek | Płeć | Chol. | ECG | Rytm serca | Chory? |
---|---|---|---|---|---|---|
![]() |
53 | M | 203 | hyp | 155 | Tak |
![]() |
60 | M | 185 | hyp | 155 | Tak |
![]() |
40 | M | 199 | norm | 178 | Nie |
![]() |
46 | K | 243 | norm | 144 | Nie |
![]() |
62 | F | 294 | norm | 162 | Nie |
![]() |
43 | M | 177 | hyp | 120 | Tak |
![]() |
76 | K | 197 | abnorm | 116 | Nie |
![]() |
62 | M | 267 | norm | 99 | Tak |
![]() |
57 | M | 274 | norm | 88 | Tak |
![]() |
72 | M | 200 | abnorm | 100 | Nie |
Tablica decyzyjna
Jest to struktura , gdzie
jest zbiorem obiektów:
![]() |
jest zbiorem atrybutów postaci
![]() |
jest specjalnym atrybutem zwanym decyzją
![]() |
Tablica decyzyjna powstaje ze zwykłych tablic danych poprzez sprecyzowanie:
Atrybutów (nazwanych warunkowymi): cechy, których wartości na obiektach są dostępne, np. pomiary, parametry, dane osobowe, …
Decyzji (atrybut decyzyjny):, t.j. cecha “ukryta” związana z pewną znaną częściowo wiedzą o pewnym pojęciu:
Decyzja jest znana tylko dla obiektów z (treningowej) tablicy decyzyjnej;
Jest podana przez eksperta (np. lekarza) lub na podstawie późniejszych obserwacji (np. ocena giełdy);
Chcemy podać metodę jej wyznaczania dla dowolnych obiektów na podstawie wartości atrybutów warunkowych na tych obiektach.
4.5cm Przedstawiona tablica decyzyjna zawiera:
8 obiektów będących opisami pacjentów
3 atrybuty: Headache Muscle pain, Temp.
Decyzję stwierdzącą czy pacjent jest przeziębiony czy też nie. lub nie
8cm\example
Ból głowy
Ból mięśni
Temp.
Grypa
p1
Tak
Tak
N
Nie
p2
Tak
Tak
H
Tak
p3
Tak
Tak
VH
Tak
p4
Nie
Tak
N
Nie
p5
Nie
Nie
H
Nie
p6
Nie
Tak
VH
Tak
p7
Nie
Tak
H
Tak
p8
Nie
Nie
VH
Nie
Dane są obiekty i zbiór atrybutów
,
mówimy, że
są rozróżnialne przez
wtw, gdy istnieje
taki, że
;
są nierozróżnialne przez
, jeśli one są
identyczne na
, tzn.
dla każdego
;
= zbiór obiektów nierozróżnialnych z
przez
.
Dla każdych obiektów :
albo ;
albo .
Relacja
![]() |
jest relacją równoważności.
Każdy zbiór atrybutów wyznacza podział
zbioru obiektów na klasy nierozróżnialności.
Dla
4.5cm
obiekty są nierozróżnialne;
są 3 klasy nierozróżnialności relacji :
8cm\example
Ból głowy
Ból mięśni
Temp.
Grypa
p1
Tak
Tak
N
Nie
p2
Tak
Tak
H
Tak
p3
Tak
Tak
VH
Tak
p4
Nie
Tak
N
Nie
p5
Nie
Nie
H
Nie
p6
Nie
Tak
VH
Tak
p7
Nie
Tak
H
Tak
p8
Nie
Nie
VH
Nie
<2> Aproksymacja funkcji \block
Sztuczna sieć neuronowa;
Twierdzenie Kolmogorowa;
Modele sieci.
Aproksymacja pojęć
Uczenie indukcyjne;
COLT;
Metody uczenia się.
Wnioskowanie aproksymacyjne
Wnioskowanie rozmyte;
Wnioskowanie Boolowskie, teoria zbiorów przybliżonych;
Inne: wnioskowanie Bayesowskie, sieci przekonań, …
Klasyfikatory (algorytmy klasyfikujące) i metody oceny klasyfikatorów
Metody rozumowania Boolowskiego
Teoria zbiorów przybliżonych
Reguły decyzyjne, drzewo decyzyjne i lasy decyzyjne
Klasyfikatory Bayesowskie
Sieci neuronowe
COLT: Obliczeniowa Teoria Uczenia się
Metody przygotowywania danych
SVM: Maszyna wektorów podpierających
Metody wzmacniania klasyfikatorów (ang. Boosting)
Znaleźć optimum nieznanej funkcji
(
), gdzie
są skończonymi zbiorami.
Działanie algorytmu przeszukiwania dla funkcji
jest identyfikowane z wektorem:
![]() |
Ocena algorytmu: . Np.
![]() |
Warunek NFL: Dla dowolnej funkcji , i dla dowolnych algorytmów
![]() |
jest zamknięta względem permutacji: dla dowolnej funkcji
i
dowolnej permutacji
mamy
Twierdzenie o NFL
Zachodzi równoważność
![]() |
Prawdopodobieństwo wylosowania niepustej klasy funkcji zamkniętej wzg. permutacji wynosi:
![]() |
Algorytm dobrze się uczy pojęcia
jeśli
jest mały.
Niech .
Czy można stwierdzić wiedzieć, że algorytm wyuczy się wszystkich pojęć z
lepiej niż algorytm
?
”No Free Lunch theorem” (Wolpert, Schaffer) w wersji problemów uczenia się głosi, że:
Żaden algorytm nie może być najlepszy w wyuczeniu wszystkich pojęć.
Każdy algorytm jest najlepszy dla takiej samej liczby pojęć
Ale interesuje nas tylko pewna klasa problemów czyli klasa pojęć
Wniosek: Należy znaleźć odpowiedni algorytm do każdego problemu.
Obecność: 20%
Projekt: 40%
Egzamin: 40%
Treść automatycznie generowana z plików źródłowych LaTeXa za pomocą oprogramowania wykorzystującego LaTeXML.
strona główna | webmaster | o portalu | pomoc
© Wydział Matematyki, Informatyki i
Mechaniki UW, 2009-2010. Niniejsze materiały są udostępnione bezpłatnie na licencji Creative Commons Uznanie autorstwa-Użycie niekomercyjne-Bez utworów zależnych 3.0 Polska.
Projekt współfinansowany przez Unię Europejską w ramach
Europejskiego Funduszu Społecznego.
Projekt współfinansowany przez Ministerstwo Nauki i Szkolnictwa Wyższego i przez Uniwersytet Warszawski.