15

8. Strojové učení

S Strojové učení 16. prosince 2014

____________________________________________________________________________________________________________________ © Václav Matoušek 8-1

Úvod do znalostního inženýrství, ZS 2014/15


Klasifikace metod strojového u učení ení podle vynaloženého úsilí na získání nových znalostí Učení ení zapamatováním (rote learning, biflování) Pouhé zaznamenání dat nebo znalostí. Učení se z instrukcí (learning from instruction) Provádí se integrace se znalostmi již získanými. Učení ení se z analogie (learning by analogy) Zapamatování již vyř vyřešených případů. Učení na základě vysv vysvětlení (explanation explanation based learning) learning Založeno na několika kolika p příkladech íkladech a rozsáhlých znalostech z dané oblasti. oblasti Učení se z příkladů ů (learning from examples) Založeno na velkém množství p příkladů a indukci. Učení ení se pozorováním a objevováním (learning learning from observations and discovery) ____________________________________________________________________________________________________________________ © Václav Matoušek 8-2



Podoby informace o tom, že se systém učí u správně Příklady, zařazené řazené do ttříd (konceptů), ), které se má systém naučit (učení ení s uč učitelem, supervised learning)) Odměny ny za správné chování a tresty za nesprávné chování (posilované učení, čení, reinforcement learning) Nepřímé ímé náznaky (u (učení ení se napodobováním, apprenticeship learning) Žádná doplňková ková informace (u (učení bez učitele, čitele, unsupervised learning)

____________________________________________________________________________________________________________________ © Václav Matoušek 8-3



Metody strojového učení

Prohledávání prostoru verzí ((version version space search) search Techniky rozhodovacích strom stromů (decision decision tree learning) learning Techniky rozhodovacích pravidel ((learning learning sets of rules) rules Techniky konceptuálního shlukování ((conceptual conceptual clustering techniques) Posilované učení čení (reinforcement learning) Učení ení založené na vysv vysvětlování (explanation explanation based learning) learning Usuzování na základ základě analogií (analogical analogical reasoning) reasoning Bayesovské učení čení ((Bayesian learning) Fuzzy učení (fuzzy fuzzy learning learning) Evoluční ní techniky ((evolution techniques) Učení neuronových onových sítí ((artificial artificial neural networks) networks

____________________________________________________________________________________________________________________ © Václav Matoušek 8-4



Prohledávání prostoru verzí Prostor verzí (version space) Množina všech popisů konceptů konzistentních s trénovacími daty.

Algoritmy prohledávání prostoru verzí (Mitchell) • Algoritmus generalizace (specific to general search) search • Algoritmus specializace (general general to specific search) search • Algoritmus eliminace kandidát kandidátů (candidate candidate elimination algorithm). algorithm Tento algoritmus udržuje dv dvě množiny kandidujících konceptů. koncept G je množina maximálně obecných konceptů, S je množina maximálně maxi specifických koncept konceptů. Algoritmus specializuje G a generalizuje S. Uvedené algoritmy používají jak pozitivní, tak i negativní příklady p cílového konceptu. Je sice možné zobec zobecňovat ovat pouze z pozitivních příkladů,, ale negativní p příklady jsou důležité v prevenci přehnaného p zobecnění. ____________________________________________________________________________________________________________________ © Václav Matoušek 8-5



Algoritmus eliminace kandidát kandidátů 1. Vlož do G nejobecnější jší koncept a do S prvý pozitivní příklad. 2. Pro každý pozitivní příklad říklad p : 2.1. Odstraň z G všechny prvky, které nepokrývají p . 2.2. Každý prvek S , který nepokrývá p , nahraď jeho nejmenší generalizací, která pokrývá p . 2.3. Odstraň z S všechny prvky, které jsou obecn obecnější než nějaké ějaké jiné prvky S nebo obecnější než nějaké ějaké prvky G . 3. Pro každý negativní příklad říklad n : 3.1. Odstraň z S všechny prvky, které pokrývají n . 3.2. Každý prvek G , který pokrývá n , nahraď jeho nejmenší specializací, která nepokrývá n . 3.3. Odstraň z G všechny prvky, které jsou specifi specifičtější než nějaké ějaké jiné prvky G nebo specifičtější jší než nějaké prvky S . 4. Jsou-li G a S prázdné, postup kon končíí (neexistuje žádný koncept, který by pokrýval všechny pozitivní příklady říklady a žádný negativní). Je Je-li G = S a obě množiny jsou jednoprvkové, postup rovn rovněž končí (cílový koncept byl nalezen). V ostatních případech se vrať na krok 2. ____________________________________________________________________________________________________________________ © Václav Matoušek 8-6



Techniky rozhodovacích strom stromů Vycházejí z příkladů íkladů popsaných vektory atributů a indexy tříd. Vytváří se rozhodovací strom strom, jehož nelistové uzly odpovídají atributům a listové uzly jsou ohodnoceny indexy tříd t (každému atributu i každé ttřídě může že odpovídat několik n uzlů). Hrany vycházející z nelistového uzlu jsou ohodnoceny hodnotami příslušného říslušného atributu atributu. Základní algoritmy: • ID3 (Iterative Iterative Dichotomizer Dichotomizer) – Quinlan • TDITD (Top-Down Down Induction of Decision Trees) Trees Rozšířením ením algoritmu ID3 je systém C4.5. Rozhodovací strom př převedeme na soubor pravidel tak, že každé cestě z kořenového enového do listového uzlu odpovídá jedno pravidlo. pravidlo ____________________________________________________________________________________________________________________ © Václav Matoušek 8-7



Vytvoření ení rozhodovacího stromu (ID3) 1. Vybere se jeden atribut jako kořen stromu. 2. Množina trénovacích p příkladů se rozdělí ělí na podmnožiny podle hodnot tohoto atributu. 3. Postupně se zpracují všechny tyto podmnožiny takto: a) Obsahuje-lili podmnožina pouze p příklady íklady z téže třídy, t vytvoří se pro tuto podmnožinu listový uzel a ohodnotí se indexem inde příslušné třídy. b) V opačném ném př případě se vybere další atribut jako atribut podstromu. Tento atribut se pak zpracuje podle bodů bod 2 a 3. Jako nejvhodnější jší mů může být vybrán např.. atribut, který má • nejmenší entropii • největší informač informační zisk nebo největší poměrný rný informační informa zisk ____________________________________________________________________________________________________________________ © Václav Matoušek 8-8



Entropie atributu Nechť A je atribut, a1, a2, …, an jsou jeho hodnoty a c1, c2, …, cm jsou klasifikační ční tř třídy. Pak entropie atributu A se vypočte podle vztahů n H ( A) = ∑ P (a j ) H (a j ) j =1

H (a j ) = −∑ P (ci | a j ) log(P (ci | a j ) ) m

i =1

kde P znamená pravd pravděpodobnost, podobnost, logaritmus má základ větší tší než 1 (obvykle je základ roven 2) a pokud je pravděpodobnost podobnost rovna nule, pak se hodnota výrazu P⋅log(P) považuje za nulovou. ____________________________________________________________________________________________________________________ © Václav Matoušek 8-9



Informační zisk Informační zisk je míra odvozená z entropie: Zisk ( A) = H (C ) − H ( A), kde m H (C ) = −∑ P(ci ) log( P(ci ) ) . i =1

Nevýhodou entropie a informa informačního zisku může ůže být skutečnost, skute že neberou v úvahu po počet et hodnot atributu. Proto se někdy n používá poměrný rný informa informační zisk: Zisk ( A) , PoměrnýZis rnýZisk ( A) = Větvení ( A) kde Větvení( A) = − ∑ P (a j ) log(P (a j ) ) n

j =1

____________________________________________________________________________________________________________________ © Václav Matoušek 8-10



Prořezávání ezávání rozhodovacích strom stromů Možné problémy rozhodovacích strom stromů: • Příliš íliš velký rozsah stromu stromu,, snižující jeho srozumitelnost. • „Přeučení“ (overfitting overfitting) – dosažení neúměrné přesnosti esnosti stromu v situaci, že trénovací data jsou zatížena šumem. Strom je možno zjednodušit tak, že místo toho, aby listovému uzlu odpovídaly pouze př příklady jedné třídy, ídy, se spokojíme s tím, že příklady p jedné třídy ídy budou v listovém uzlu p převažovat. Zjednodušení (redukci) stromu je možno provést dvěma ma způsoby: způ • Původní vodní algoritmus se modifikuje doplněním nějakého ějakého kritéria, kritéria které indikuje, zda má uzel dále expandovat. Tímto zp způsobem ůsobem se redukovaný strom vytvoří přímo. římo. • Vytvoříí se úplný strom a následn následně se provede jeho prořezání pro (postprunning). ). Postupuje se zdola nahoru a u každého podstromu se podle nějakého jakého kritéria rozhoduje, zda se má podstrom nahradit listovým uzlem. Tento způsob ůsob je obvyklejší. ____________________________________________________________________________________________________________________ © Václav Matoušek 8-11



Zdokonalení technik rozhodovacích stromů strom Práce s numerickými atributy: V případě spojitých hodnot nebo velkého po počtu tu diskrétních hodnot se obor hodnot rozdělí ělí lí na intervaly, které se pak považují za diskrétní hodnoty atributu. Chybějící jící hodnoty atribut atributů: Jednou z možností je uvažovat místo chyb chybějící jící hodnoty nejčastější nej hodnotu příslušného ého atributu. Jinou možností je uvažovat všechny hodnoty atributu s vahami danými relativ relativními četnostmi etnostmi jejich výskytu v trénovacích datech. Ceny atributů: V některých kterých aplikacích m může hrát roli i cena zjištění ění hodnoty atributu. V takovém případě ě mů můžeme při tvorbě rozhodovacího stromu např. nap použít modifikované kritérium informa informačního zisku:

Zisk ( A) 2 ZC ( A) = Cena( A) ____________________________________________________________________________________________________________________ © Václav Matoušek 8-12



Techniky rozhodovacích pravidel Odvození množin pravidel z rozhodovacích strom stromů ů Algoritmy pokrývání množin: • algoritmus AQ (Michalski) • algoritmy CN2 (Clark, Niblet), CN4 (Bruha, Kočková) Ko U výše uvedených technik vytvá vytvářená á pravidla neobsahují proměnné. Naproti tomu v induktivním logickém logické programování pravidla mohou obsahovat prom proměnné nné a mají tvar Hornových klauzulí 1. řádu (prologovských klauzulí). Systémy induktivního logického programování: • FOIL (Quinlan) • PROGOL (Muggleton) • TILDE (Blockeel, De Raedt) ____________________________________________________________________________________________________________________ © Václav Matoušek 8-13



Algoritmus AQ Algoritmus AQ je určen rovn rovněž pro učení ení z klasifikovaných příkladů p popsaných pomocí atribut atributů. Jeho výstupem je soubor pravidel popisujících všechny pozitivní p příklady íklady z trénovací množiny. množiny Algoritmus lze shrnout do následujících bodů: 1. Rozděll množinu p příkladů na dvě podmnožiny: odmnožiny: podmnožinu P pozitivních příkladů ů a podmnožinu N negativních příkladů. př 2. Vyber z množiny P jeden příklad a označ jej s (seed seed neboli jádro). 3. Nalezni všechny maximální generalizace popisu jádra s tak, že jimi nesmí být pokryt žádný negativní příklad. 4. Podle vhodného preferen preferenčního kritéria vyber er nejlepší z těchto t popisů a zařaď jej do množiny popis popisů. Odstraň z množiny P všechny příklady pokryté tímto popisem. 5. Je-li množina P prázdná, ukon ukončii práci (výsledným popisem je disjundisjun kce všech nalezených popis popisů). V opačném případě ě se vrať vra na bod 2. ____________________________________________________________________________________________________________________ © Václav Matoušek 8-14



Poznámky k algoritmu AQ Případ více tříd: Základní podoba algoritmu uvažuje dv dvě třídy. ídy. Rozšíření Rozší se obvykle provede tak, že pro každou ttřídu ci se za pozitivní považují příklady p této třídy a za negativní všechny ostatní. Jinou možností je vytvářet vytvá pravidla ke všem třídám ídám souč současně (tak pracují algoritmy CN2, CN4). Data zatížená šumem: Algoritmus můžeme žeme upravit tak, že v kroku 3 nepožadujeme, aby pravidlo pokrývalo příklady íklady pouze jedné ttřídy. Rozhodovací seznam: Algoritmus AQ vytvář vytváří tzv. neuspořádaný ádaný soubor pravidel. Opakem Opake je uspořádaný ádaný soubor pravidel neboli rozhodovací seznam (decision list), ve kterém jsou pravidla propojena pomocí ELSE.. Podmínka za ELSE IF tedy implicitně obsahuje nega negaci podmínek všech předcházejících edcházejících pravidel. Algoritmy CN2 a CN4 umožňují tvorbu uspořádaného ádaného i neuspořádaného souboru pravidel. ____________________________________________________________________________________________________________________ © Václav Matoušek 8-15



Algoritmus konceptuálního shlukování 1. Z množiny všech p příkladů vyber k jader s1, …, … sk (hodnotu k zadává uživatel). Výb Výběr může že být proveden náhodně náhodn nebo pomocí nějaké selekční ní funkce. 2. Pro každé jádro vytvo vytvoř maximálně obecný popis, který by je odlišil od všech ostatních jader. Každý takový popis je nazýván protokonceptem. Vytvo Vytvořené ené protokoncepty nemusejí být disjunktní. 3. Uprav protokoncepty tak, aby byly disjunktní.. Zpravidla existuje několik různých řešení (množin koncept konceptů), ), z nichž se pomocí vyhodnocovací funkce vybere to nejlepší. 4. Není-li splněno no zvolené kritérium ukon ukončení, vyber nová jádra (z každého stávajícího jícího protokonceptu se vybere jedno) a přejdi p zpětt ke kroku 2. V opa opačném případě vyber nejlépe ohodnocené řešení ešení a proces ukon ukonči. ____________________________________________________________________________________________________________________ © Václav Matoušek 8-16



Příklad íklad tvorby disjunktních koncept konceptů 1. Vytvoří se seznam L příkladů pokrytých více protokoncepty. 2. Jako počáteční ní hodnoty vytvářených ených disjunktních konceptů koncept Ci se položí Ci = {si},, (i = 1, … , k). 3. Vezme se první př příklad ze seznamu L a odstraní se z tohoto seznamu. protokonceptů Pi pokrývajících vybraný příklad p e 4. Pro každý z protokoncept se pokusně vytvoř vytvoří nový, co nejobecnější jší popis tak, aby pokrýval příklad e a shluk Ci a nepřekrýval ekrýval se s žádným z ostatních konceptů konceptů. 5. Pomocí vyhodnocovací funkce vybereme nejlepší z těchto t popisů. Nechťť je to popis odpovídající protokonceptu Pj. Příklad e přidáme idáme ke shluku Cj . Je-lili seznam L prázdný, postup končí. í. V opa opačném případě se vracíme na krok 3. ____________________________________________________________________________________________________________________ © Václav Matoušek 8-17



Poznámky ke konceptuálnímu shlukování Vyhodnocovací funkce Může že zahrnovat řřadu kritérií, jako např.. míru rozdílnosti mezi shluky, počet et prom proměnných umožňujících ujících diskriminovat mezi shluky, jednoduchost popisu shluk shluků, apod. Ukončovací ovací kritérium Může že to být např např. počet et iterací, po které nedošlo k významnému zlepšení vyhodnocovací funkce. Volba jader ze stávajících shluk shluků V algoritmu CLUSTER/2 (Michals (Michalski) ki) se s využitím vhodné metriky vybírá prvek nej nejbližší středu edu každého shluku. V případě neuspokojivých shluk shluků,, které se po několik n iterací nezlepšují, se jako nová jádra vybírají prvky nejbližší k hranici shluku. ____________________________________________________________________________________________________________________ © Václav Matoušek 8-18



Učení ení založené na vysv vysvětlování Složky učení ní založeného na vysv vysvětlování: • cílový koncept, jehož ehož definici je ttřeba vytvořit, • trénovací příklad íklad jako instance cíle cíle, • doménová oménová teorie (množina pravidel a faktů,, které jsou používány k vysvětlení, pročč je trénovací p příklad lad instancí cílového konceptu), konceptu) • kritéria ritéria popisující tvar, kt který erý definice cíle mohou nabývat. nabývat V prvém kroku se pomocí doménové teorie konstruuje vysvětlení vysvě trénovacího příkladu. íkladu. Obvykle se jedná o d důkaz, že příklad íklad logicky vyplývá z teorie, přičemž tento důkaz ůkaz m může být reprezentován např. ř. pomocí stromové struktury. V dalším kroku je zobecn zobecněním tohoto vysvětlení tlení získána definice cílového konceptu. Zobecnění ění spo spočívá v substituci proměnných nných za z ty konstanty v důkazním kazním stromu, které závisejí pouze na trénovacím příkladu. Na základě zobecněného ěného d důkazního kazního stromu se definuje pravidlo, jehož závěr záv je kořen en stromu a předpoklad je konjunkcí list listů. ____________________________________________________________________________________________________________________ © Václav Matoušek 8-19



Konstrukce zobecn zobecněného důkazního kazního stromu Existuje řada způsobů sobů konstrukce zobecněného ného důkazního dů stromu. Jednou z možností je (Mitchell et al.) nejprve zkonstruovat důkazní d strom, který je specifický pro trénovací p příklad, íklad, a následně následn tento důkaz kaz zobecnit tzv. cílovou regresí ((goal goal regression). regression Cílová regrese unifikuje zobecn zobecněný cíl s kořenem enem důkazního dů stromu pomocí potřebných ebných substitucí. Algoritmus rekurzívně rekurzívn aplikuje tyto substituce na další uzly stromu, dokud všechny vhodné konstanty nejsou zobecněny. ěny. DeJong and Mooney navrhují alternativní p přístup, ístup, který v podstatě spočívá ívá v paralelním vytvá vytváření zobecněného i specifického stromu. s To je uskutečněno ěno pomocí tzv. vysv vysvětlovací tlovací struktury (explanation ( structure), ), která reprezentuje abstraktní strukturu důkazu. d Při vytváření ení této struktury se konstruují dva substituční substitu seznamy, jeden pro specifický strom a druhý pro obecný strom. ____________________________________________________________________________________________________________________ © Václav Matoušek 8-20



Metody tody založené na analogii Učení ení nových konceptů nebo odvozování nových řešení prostřednictvím použití podobných koncept konceptů a jejich řešení. Metody: • Případové ípadové usuzování ((Case-Based Reasoning, CBR) • Pravidlo nejbližšího souseda ((nearest neigbour rule) • Učení založené na instancích ((Instance-Based Based Learning, Learning IBL) • Líné učení (lazy lazy learning learning) • Paměťové učení (Memory Memory-Based Learning) Znalosti jsou reprezentovány v podob podobě báze již vyřešených ešených problémů. problém Při usuzování se k danému problému v této bá bázi zi hledá nejpodobnější nejpodobn případ a jeho řešení ešení se adaptuje na novou situaci. Fáze učení pak představuje edstavuje zapamatování znalosti z vyřešeného problému pro budoucí použití. Př Při učení se tedy neprovádí generalizace z příkladů (proto název líné učení ení). ____________________________________________________________________________________________________________________ © Václav Matoušek 8-21



Případové ípadové usuzování CBR je založeno na a vyhledávání a přizpůsobování sobování starých řešení novým problémům ům.. Obecný CBR cyklus lze popsat pomocí následujících čtyř krok kroků: 1. Vyhledání (retrieving retrieving)) nejvíce podobného případu p nebo případů. 2. Použití (reusing reusing) informací a znalostí z tohoto případu k vyřešení ešení daného problému. 3. Revize (revising)) navrženého řešení. 4. Uchování (retaining retaining) částí těchto chto zkušeností tak, aby byly použitelné pro řešení budoucích problém problémů. Kromě specifických znalostí reprezentovaných p případy řípady hrají určitou ur roli v tomto procesu i obecné znalosti z příslušného íslušného oboru. ____________________________________________________________________________________________________________________ © Václav Matoušek 8-22



Bayesovské učení čení Bayesovské uvažování • je základem pro algoritmy učení,, které přímo př manipulují s pravděpodobnostmi podobnostmi • je nástrojem pro analýzu a pochopení ostatních algoritmů algoritm strojového učení čení Výhodou metod bayesovského u učení je schopnost klasifikovat příklady do tříd říd s ur určitou pravděpodobností. Metody Bayesovského u učení: • Bayesovský optimální klasifikátor • Gibbsůvv algoritmus • Naivní bayesovský klasifikátor • Učení ení bayesovských sítí ____________________________________________________________________________________________________________________ © Václav Matoušek 8-23



Naivní bayesovský klasifikátor Naivní bayesovský klasifikátor vychází z předpokladu, př že jednotlivé evidence E1, … EK jsou podmíněně ěně nezávislé při platnosti hypotézy H. Pak platí K P( H ) P( H | E1,..., EK ) = P ( Ei | H ) ∏ P ( E1,..., EK ) i =1

Naivní bayesovský klasifikátor: K

H NB = arg max P ( H j )∏ P ( Ei | H j ) Hj

i =1

____________________________________________________________________________________________________________________ © Václav Matoušek 8-24



Vysvětlení tlení pojmů pojmů: AQ-Algorithm – algorithm quasi-optimal koncept – první předbežné ředbežné zpracování, návrh, náčrt črt (zejména textu); nákres, osnova, skica skica, rozvrh atribut – neodlučitelná itelná vlastnost, podstatný znak, přívlastek stek; dále atributy jsou speciální části ásti v kódu psaného v jazycích HTML nebo XHTML; atributy tributy jsou jakési parametry, které umožňují jednotlivým zna značkám přiřazovat spec. vlastnosti lastnosti … atribut (z lat. ad-tribuere tribuere, přidělovat, připisovat, ipisovat, přisuzovat) je dále rozlišovací rys, podstatn podstatná vlastnost nějakého jakého objektu a v obecném užití charakteristická vlastnost, v gramatice přívlastek ívlastek, symbol nebo emblém držitele úřadu řadu (nap (např.. rektorské žezlo, královská koruna), v ikonografii rozlišovací znak významné postavy, např. světce (korouhev sv. Václava) Václava), a také dodatečná ná informace připojená p k souboru v souborovém systému ____________________________________________________________________________________________________________________ © Václav Matoušek 8-25



Významná ýznamná jména z oblasti strojového učení: u Tom Mitchell – University Professor ([email protected] [email protected]) Machine Learning Department (chair) School of Computer Scienc Science Carnegie Mellon University University, Pittsburgh Pitts

____________________________________________________________________________________________________________________ © Václav Matoušek 8-26



John Ross Quinlan – is a computer science researcher in data mining and decision the theory.. He has contributed extensively to the development of decision tree algorithms, including inventing the canonical C4.5 and ID3 algorithms. He is currently running the company RuleQuest Research which he founded in 1997.

____________________________________________________________________________________________________________________ © Václav Matoušek 8-27


15

Recommend Documents