Uczenie maszynowe

Jest konieczne w nieznanym środowisku, tj. gdy projektant systemu nie posiada wszechwiedzy Jest przydatne jako metoda konstrukcji systemu, tj. konfrontuje agenta z rzeczywistością zamiast próby napisania jego programu Modyfikuje mechanizm decyzyjny agenta, aby poprawić wydajność Wszystkie typy uczenia mogą byc rozważane jako uczenie reprezentacji funkcji.

Uczenie indukcyjne

Element uczący otrzymuje poprawną wartość funkcji dla poszczególnych danych wejściowych i na tej podstawie modyfikuje reprezentację funkcji tak, aby pasowała do dostarczonej informacji.

Formalnie: Obiekty: dane opisujące stan lub obiekt; tworzą przestrzeń obiektów X.

Decyzja: Funkcja dec : X → V_{dec} przypisująca obiektom ze zbioru X wartość decyzji z ustalonego zbioru V_{dec}.

Zbiór przykładów: Ustalony zbiór obiektów z X z przypisanymi wartościami decyzji: tj. zbiór par (x_{i}, dec(x_{i})) dla i = 1, …, n.

Zadanie: Z danego zbioru przykładów nauczyć się funkcji (hipotezy) h : X → V_{dec} aproksymującej decyzję dec tak, aby możliwie najbardziej poprawnie przypisywała ją obiektom z przestrzeni X, dla których nieznana jest wartość decyzji dec.

Przykład – kółko i krzyżyk

Uczenie funkcji z przykładów (tabula rasa) f jest funkcją docelową

Przykład to para (x, f(x)), tj., \begin{aligned}O & O & X \\ & X \\ X \end{aligned} , +1

Problem: znaleźć hipotezę h taką że h ≈ f dla danego zbioru przykładów

Hipoteza h jest spójna na zbiorze {(x_{1}, dec(x_{1})), …, (x_{n}, dec(x_{n}))} jeśli

h(x_{i}) = dec(x_{i}) dla każdego 1 ≤ i ≤ n

Rodzaje decyzji

Decyzja może przyjmować wartości: • rzeczywiste

• dyskretne

• binarne (TRUE, fALSE)

Przestrzeń hipotez

W ogólności może być wiele hipotez dla tego samego zbioru przykładów. Ile jest różnych hipotez (funkcji) binarnych dla n atrybutów binarnych? = liczba funkcji binarnych dla dziedziny z 2^{n} obiektami = 2^{2^{n}} Przestrzeń hipotez można ograniczyć do ustalonej klasy hipotez. Z drugiej strony zwiększanie przestrzeni hipotez:

• zwiększa szansę, że funkcja docelowa może być wyrażona

• zwiększa liczbę hipotez zgodnych ze zbiorem przykładów

Empiryczna miara jakości hipotezy

Sposób postępowania:

• Dane X dzielimy na dwa podzbiory – zbiór treningowy Z_{trn} i zbiór testowy Z_{tst}.

• Hipoteza h : X → V_{dec} jest indukowana na podstawie zbioru treningowego Z_{trn}.

• Skuteczność hipotezy Acc(h) jest mierzona proporcją poprawnie sklasyfikowanych obiektów ze zbioru testowego do rozmiaru zbioru testowego, tj.

Acc(h) = \frac{| \{x ∈ Z_{tst} : h(x) = dec(x)\} |}{| Z_{tst} |}

Stosowane podejścia

Zależą od reprezentacji modułu decyzyjnego agenta:

1. drzewa decyzyjne

2. wnioskowanie oparte na podobieństwie - k najbliższych sąsiadów

3. sieci neuronowe

4. sieci bayessowskie

5. systemy regułowe

Drzewa decyzyjne

Wejście: obiekt lub stan opisany przez zbiór własności (atrybutów). Wyjście: decyzja tak/nie (wartości wyjściowych może być więcej). Opisują funkcje boolowskie.

Reprezentacja:

Węzły wewnętrzne: Każdy związany z jednym atrybutem - reprezentuje test wartości tego atrybutu.

Gałęzie: Każda związana z wartością lub podzbiorem wartości atrybutu węzła, z którego wychodzi - odpowiada obiektom danych z pasującymi wartościami atrybutu.

Liście: Każdy związany z decyzją lub rozkładem decyzji - odpowiada obiektom danych pasującym do ścieżki prowadzącej do danego liścia.

Przykład

Example  Attributes  Target
Alt Bar F ri Hun P at P rice Rain Res T ype  Est  WillWait
X_{1}  T  F  F  T  Some  $$$  F  T French 0–10  T
X_{2}  T  F  F  T  Full  $  F  F  Thai  30–60  F
X_{3}  F  T  F  F  Some  $  F  F Burger 0–10  T
X_{4}  T  F  T  T  Full  $  F  F French 10–30  T
X_{5}  T  F  T  F  Full  $$$  F  T  Thai  >60  F
X_{6}  F  T  F  T  Some  $$  T  T  Italian 0–10  T
X_{7}  F  T  F  F  None  $  T  F Burger 0–10  F
X_{8}  F  F  F  T  Some  $$  T  T  Thai  0–10  T
X_{9}  F  T  T  F  Full  $  T  F Burger  >60  F
X_{10}  T  T  T  T  Full  $$$  F  T  Italian 10–30  F
X_{11}  F  F  F  F  None  $  F  F  Thai  0–10  F
X_{12}  T  T  T  T  Full  $  F  F Burger 30–60  T

Drzewo decyzyjne

12

Drzewa decyzyjne– moc wyrażania

Dla każdego zbioru przykładów istnieje spójne drzewo decyzyjne – jedna ścieżka do liścia dla każdego przykładu (chyba, że f jest niedeterministyczna).

Zadanie: Szukanie bardziej zwartego drzewa decyzyjnego.

Uczenie drzewa decyzyjnego

Cel: znalezienie małego drzewa zgodnego ze zbiorem treningowym. Pomysł: rekurencyjne wybieranie najbardziej znaczącego atrybutu jako korzenia poddrzewa.

Wybór atrybutu

Idea: dobry atrybut rozdziela przykłady na podzbiory, których elementy są wszystkie “pozytywne” lub wszystkie “negatywne”.

P atrons? jest lepszym wyborem – daje informację o klasyfikacji.

Informacja

Rozwiązaniem jest informacja. Im większa ignorancja w kwestii odpowiedzi na początku, tym więcej informacji zawiera odpowiedź. Skala: 1bit = odpowiedź na pytanie boolowskie z prawdopodobieństwem ⟨0.5, 0.5⟩

Entropia

Dany jest rozkład prawdopodobieństwa

⟨P_{1}, …, P_{n}⟩.

Miara informacji (entropia prawdopodobieństwa) wyznacza ile informacji niesie ten rozkład

H(⟨P_{1}, …, P_{n}⟩) = Σ_{i=1}^{n} − P_{i} log_{2} P_{i} S –zbiór danych S_{d} –zbiór obiektów z decyzją d

H(S) = Σ_{d∈V_{dec}} − \frac{| S_{d} |}{| S |}log_{2} \frac{| S_{d} |}{| S |}

Entropia = średnia liczba bitów potrzebna do zakodowania decyzji d dla losowo wybranego obiektu ze zbioru S. Optymalne kodowanie przydziela −log_{2}p bitów do decyzji występującej z prawdopodobieństwem p.

Entropia: przypadek 2 decyzji

Dane są dwie decyzje: pozytywna (+) i negatywna (-) p_{+} = \frac{|S_{+} |}{|S|} – częstość obiektów z decyzją pozytywną w S p_{−} = \frac{|S_{−}|}{|S|} – częstość obiektów z decyzją negatywną w S

H(S) = −p_{+} log_{2}p_{+} − p_{−}log_{2}p_{−}

Zysk informacji

Zysk informacji G(S, a)=

redukcja entropii przy podziale zbioru względem atrybutu a. S_{v} – zbiór obiektów w S z wartością atrybutu a = v

G(S, a) = H(S) − Σ_{v∈V alue(a)} \frac{| S_{v} |}{| S |}H(S_{v})

Przykład cd.

Drzewo decyzyjne wyuczone z 12 przykładów

Atrybut numeryczny

W przypadku atrybutu numerycznego zbiór jego wartości dzielimy na dwa podzbiory poprzez wykonanie cięcia. Zysk informacji obliczamy względem wybranego cięcia. Zysk informacji G(S, a, c)=

redukcja entropii względem cięcia binarnego c na atrybucie a. c – wartość cięcia S_{a<c} – zbiór obiektów z wartościami atrybutu a poniżej cięcia S_{a≥c} – zbiór obiektów z wartościami atrybutu a powyżej cięcia

G(S, a) = H(S) − \frac{| S_{a<c} |}{| S |}H(S_{a<c}) − \frac{| S_{a≥c} |}{| S |}H(S_{a≥c})

Wybór cięcia

Drzewo decyzyjne wybiera atrybut rozpatrując najlepsze cięcia dla atrybutów numerycznych. Ten sam atrybut numeryczny może być wybrany kilkakrotnie na jednej ścieżce od korzenia do liścia. Ale każdy atrybut symboliczny może być wybrany conajwyżej raz!

Klasyfikacja obiektu

Example  Attributes  Target
Alt Bar F ri Hun P at P rice Rain Res T ype  Est WillWait
X  T  F  F  T  Full $$$  F  T French 0–10  ??

P atrons = F ull → Hungry = Y es → T ype = F rench → W illW ait =

T

Klasyfikacja obiektu – brakujące wartości

Co robić, gdy informacja o klasyfikowanym obiekcie jest niepełna, np.

Example  Attributes  Target
Alt Bar F ri Hun P at P rice Rain Res T ype  Est WillWait
X  T  F  F  T  ??  $$$  F  T French 0–10  ??

Pomysł: zejście wszystkimi ścieżkami przy atrybutach z nieustaloną wartością

[figure: Patrons; Hungry; Type; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; None; Some; Full; Yes; No; French; Italian; Thai; Burger; F 2; T 4; T 1]

Odpowiedź: Maksimum z sumy rozkładów decyzji obiektów uczących w osiągniętych liściach:

2 × F ∧ (4 + 1) × T → W illW ait = T

Przycinanie drzewa.

Problem: Rzadkie wyjątki lub błędy w przykładach uczących mogą powodować niepotrzebne rozwinięcie gałęzi drzewa.

Rozwiązanie: Dodanie fazy walidacji do procesu uczenia. Węzły rozdzielające, które nie potwierdzą swojej przydatności są zamieniane na liście.

Dokładniej:

1. Wybieramy węzeł cand, którego wszystkie następniki są liśćmi.

2. Niech d_{cand} – najczęstsza decyzja przypisana obiektom budującym ten węzeł.

3. Jeśli zastąpienie węzła cand przez decyzję d_{cand} nie pogorszy skuteczności na zbiorze testowym, to zastąp podrzewo o wierzchołku cand przez liść z decyzją d_{cand}.

4. Powtarzaj 1.-3. dopóki zbiór kandydatów jest niepusty.

Miara efektywności.

Skąd wiadomo, że h ≈ f

1) Teoria obliczeń/ statystyka

2) Testowanie funkcji h na nowym zbiorze testowym Krzywa uczenia = % poprawności na zbiorze testowym jako funkcja jego rozmiaru

Miara efektywności cd.

Krzywa uczenia zależy od

- realizowalności (wyrażalność funkcji docelowej) vs. nierealizowalności (spowodowanej np. brakiem atrybutu lub nadmiernym ograniczeniem klasy hipotez)

- redundancji w wyrażalności (np. nierelewantne atrybuty)

33