Strojové učení – rozhodovací stromy

Úvod do problematiky

Úvod a motivace

Naše stroje jsou nedokonalé:

potřebují údržbu

selhávají (hroutí se),

Rádi bychom dostali varování předem. Konstruktér (tvůrce) předem zná – tuší, co jeho stroj potřebuje, ale co běžný uživatel?

Můžeme běžného uživatele vybavit souborem jednoduchých instrukcí 'co dělat, když'?

Jak by měly tyto instrukce vypadat?

Jak je můžeme vytvořit?

Získávání odpovídajících znalostí pro reálné UI aplikace je tak náročné, že mnohdy může být řešení 'hrubou silou' (t.j. prohlédnutím všech možných alternativ) úspěšnější, např. koncovka hry v šachy.

Obtíže při získávání znalostí?

Znalost v odborných publikacích je vyjádřená pomocí náročných abstraktních pojmů (iniciativa, dobře chráněný král,).

V některých situacích či prostředích není člověk schopen popsat a zdůvodnit slovy své rozhodnutí. Přesto však jeho rozhodnutí „funguje“.

Není možné pojmy a strategie řešení předávat pomocí příkladů? Mohou se stroje učit z příkladů?

Definice

Simon [83]: Učení je schopnost systému měnit se (adaptovat) tak, že vzniklé změny umožňují systému vykonávat stejnou nebo podobnou úlohu při příští příležitosti účinněji nebo efektivněji.

Typy učení

získávání dovedností - skill refinement (plavání, jízda na kole, )

získávání znalostí (hodnocením zkušeností) – knowledge acquisition

Získávání znalostí

zapamatování zkušeností - Rote Learning (hry jako šachy, dáma), mechanické učení  - využívá např. heuristické hodnotící funkce stavu hry, která se postupně v průběhu hry upřesňuje v navštívených stavech tak, že se tyto rozvíjejí do omezené hloubky a jako hodnocení rozvíjeného stavu se používá hodnota získaná metodou MIN-MAX

případové usuzování - Case-Based Reasoning: rozhodnutí vzniká jako modifikace rozhodnutí použitého dříve pro „velmi podobný případ“ – potřebuje bohatou zásobu již vyřešených případů

přijímáním rad od rádce - Advice Taking, obtíž může být v 'interpretaci' nebo 'operacionalizaci' abstraktní rady – hledají se „podmínky použití“

analýzou rozdílů: „Winstonova brána“ – hypotéza se konfrontuje s klasifikovanými příklady a postupně se upravuje (pokud hypotéza pokývá negativní příklad => specializace, pokud hypotéza nepokrývá pozitivní příklad => zobecnění) 

učení z příkladů (s učitelem, hledání skrytého významu v datech, ) - klasifikace (do známých tříd), vytváření vhodných konceptů ve formě hypotéz

Prostor hypotéz o konceptu

Koncept:

Reálně existující třída objektů vymezená na známém definičním oboru (např. 3D vektory reálných čísel). Objekty klasifikujeme podle toho, zda ke konceptu patří nebo nepatří. Obvykle známe jen konečnou množinu příkladů prvků daného konceptu (pozitivní příklady), případně i množinu prvků, které ke konceptu nepatří (negativní příklady), t.j. trénovací množinu konceptu. Trénovací množina konceptu popisuje koncept implicitně (t.j. pomocí příkladů).

Hypotéza:

Pokus o formální charakterizaci konceptu, např. formule ve výrokové logice (pravidla) nebo množina aritmetických výtazů, která má být splněna. Hypotéza je pokus o explicitní popis konceptu.

Hypotéza je

korektní, když nepokrývá žádný negativní příklad.

úplná, když pokrývá všechny pozitivní příklady.

Hledáme korektní a úplnou hypotézu.

Prostor hypotéz pro daný koncept je tvořen pravidly, která jsou výsledkem učení z příkladů. Tento prostor je částečně uspořádaný a má maximální i minimální prvek:

Libovolný popis 1 konkrétního prvku z trénovací množiny do všech podrobností představuje nejspeciálnější hypotézu

Nejobecnější hypotéza (maximální prvek) pokrývá všechny možné (positivní i negativní) příklady

Operace v prostoru hypotéz: Specializace, Generalizace:

Rozhodovací stromy

Školní příklad na tvorbu rozhodovacího stromu

5 atributů:

Is_smiling I

Holding I

Has_tie I

Head_shape I

Body_shape I

2 klasifikace:

Tréninkové příklady:

Rozhodovací strom:

Algoritmus strojového učení TDIDT (ID3)

TDIDT: Top-Down Induction of Decision Trees

- indukce rozhodovacích stromů (pro definici konceptu na základě trénovací množiny, která postupuje) shora dolů

dáno: S trénovací množina (množina klasifikovaných příkladů)

Nalezneme 'nejlepší' atribut at (t.j. atribut, který nese největší množství informace o tom, zda nějaký prvek patří či nepatří k uvažovanému konceptu) a tím ohodnotíme kořen vytvářeného stromu.

Rozdělíme množinu S na podmnožiny S₁,S₂, ,S_n, kterých je tolik, kolik je hodnot atributu at. Právě tolik následníků bude mít uzel at. Dělení probíhá tak, že do podmnožiny S_i patří právě ty příklady, jejichž hodnota atributu at je v_i. Takto vzniklé množiny příkladů jsou přiřazeny odpovídajícím uzlům vytvářeného rozhodovacího stromu.

Pro každý uzel, kterému je přiřazena podmnožina S_i se postupuje takto:

Jestliže všechny příklady v S_i mají tutéž klasifikaci (všechny jsou pozitivní  nebo všechny jsou negativní),

pak uzel ohodnocený S_i je prohlášen za list vytvářeného rozhodovacího stromu (a tedy se už dále nevětví),

jinak jdi na bod 1 s tím, že S = S_i.

Praktický příklad použití metody TDIDT

Létání na simulátoru F16

Popis úlohy

     V této úloze, popsané v [Samuel, 95], bylo úkolem řešícího týmu sestavit řídící systém, který by byl schopen ovládat letecký simulátor F16, tak aby splnil předem definovaný plán letu. Plán se skládal z následujících bodů:

vzlet a výstup do výšky 2000 stop

let v dané výšce severním směrem až do vzdálenosti 32000 stop od místa startu

zahnout vpravo v kurzu 330°

ve vzdálenosti 42000 stop od místa startu (ve směru sever-jih) provést obrat vlevo a zamířit zpět do místa startu, obrat je ukončen při kurzu mezi 140° a 180°.

vyrovnat směr letu s přistávací dráhou, tolerance 5 pro kurz a 10° pro výchylku křídel oproti horizontu

klesat směrem k počátku přistávací dráhy

přistát

Tréninková data

Každý let popsán pomocí 1000 záznamů, které charakterizují

polohu a stav letounu

pilotem provedený (řídící) zásah

3 piloti á 30 letů 90 000 datových příkladů:

Každá ze 7 fází letu si vyžaduje vlastní typ řízení (jiné zásahy pilota). Proto jsou trénovací příklady rozděleny do 7 odpovídajících skupin. V každé skupině je zkonstruován zvlášť rozhodovací strom pro všechny řídící zásahy (rollers, elevator, thrust, flaps), t.j. 7 x 4 stromů

Příklady dalších algoritmů strojového učení

Algoritmus prostoru verzí (version space) – oboustranné prohledávání

Přípustná verze konceptu (Mitchell 1978) je postupně vymezována pomocí horní a dolní meze G a H. Horní mez G obsahuje všechny nejobecnější hypotézy o konceptu, které jsou přípustné z hlediska dosud zpracovaných příkladů. Dolní mez S obsahuje všechny nejspecifičtější hypotézy o konceptu, které jsou přípustné z hlediska dosud zpracovaných příkladů. Klasifikované příklady jsou nejprve uspořádány a pak jsou postupně zpracovávány, t.j. jsou použity pro eliminaci kandidátů v G a S.

Algoritmus pro nalezení konceptu pomocí eliminace kandidátů

G

S

Vyber další příklad p z trénovací množiny:

Je-li p pozitivní příklad, pak je použit k zobecnění S a k „proškrtání“ G, t.j.

Každý prvek v S nahraď jeho nejmenším zobecněním, které popisuje p

Z G odstraň ty koncepty, které nejsou zobecněním p.

Je-li p negativní příklad, pak je použit k „proškrtání“ S a ke specializaci G, t.j.

Z S odstraň ty koncepty, které pokrývají příklad p.

Každý prvek v G nahraď jeho nejmenší specializací, která nepopisuje p

Jsou-li G a S jednoprvkové množiny a platí G = S,

pak ohlas (HYPOTÉZA NALEZENA, KONEC )

jinak jdi na

Příklad použití:

Klasifikace aut popsaných atributy: Vyrobeno_v, Výrobce, Barva, Stáří_vozu, Typ_vozu

pokrývání  - Covering algorithm (AQ, CN2), sdola nahoru

AQ Algoritmus (Michalski 1969)

Popis : = Ø

Množina příkladů se skládá ze 2 disjunktních množin PE (obsahující právě všechny pozitivní příklady) a NE (obsahující právě všechny negativní příklady)

Vyber z množiny PE náhodně 1 příklad a označ jej jádro s (seed)

Nalezni všechny maximální generalizace Generalizace(s) popisu jádra s takové, že nepokrývají žádný příklad z NE

Nechť podle vhodného prefernčního kriteria je g nejlepší z popisů v Generalizace(s). Označme množinu všech prvků z PE, které vyhovují popisu g, Pokryto(g). Popis g je zařazen do množiny Popis, t.j.

Popis : = Popis +

Pokud každý prvek z množiny PE je pokryt nějakým prvkem z Popis, ukonči práci.

Kapitola 3 je nepovinná (je uvedena jen pro informaci)

Doporučená literatura

Kubát, M.: Strojové učení, Kap. 7 v  [Mařík et al.]

Mařík, V., Štěpánková, O., Lažanský, J.: Umělá inteligence (1), Academia, Praha 1993

Michalski, R., Bratko, I., Kubat, M.: Machine Learning and Data Mining, Methods and Applications, Addison Wesley 1998

Russel, S., Norvig, P.: Artificiall Intelligence. A Modern Approach, Prentice Hall 1995