8 Strojové u ení a adaptace D ležitou vlastností živých organism je schopnost p izp sobovat se m nícím se podmínkám (adaptovat se), eventuáln se u it na základ vlastních zkušeností. Schopnost u it se bývá n kdy dokonce považována za definici inteligence. Je proto p irozené, že vybavit touto vlastností i systémy technické je jedním z cíl um lé inteligence. Navíc v ad praktických p ípad , kdy není dostatek apriorních znalostí o ešeném problému, ani jinak postupovat nelze. V zásad lze rozlišit dva typy u ení: u ení se znalostem (knowledge acquisition) a u ení se dovednostem (skill refinement). První typ hledá koncepty, obecné zákonitosti apod. (nap . jak rozpoznat defraudanta) u druhého typu jde o to zdokonalit své schopnosti na základ procvi ování n jaké innosti (nap . jak nalézt cestu v bludišti). Na tomto míst je t eba zd raznit, že „um lé“ metody u ení nedosahují možností metod „p irozených“: •
formalizmus použitý pro popis situací nebo koncept , které se má systém nau it je pom rn jednoduchý,
•
koncepty, které se systém u í asto odpovídají pouze jedné úrovni abstrakce zatímco lov k je schopen své koncepty uspo ádávat do hierarchií,
•
v tšina metod spoléhá na u itele, který dohlíží na celý výukový proces,
•
v tšina metod p edpokládá, vše všechna pot ebná data jsou k dispozici p ed za átkem u ení; lov k je schopen na základ další zkušenosti pr b žn aktualizovat své znalosti.
P esto se „um lé“ metody u ení studují (a úsp šn používají) adu let. V sou asné dob procházejí zvýšeným zájmem p edevším v souvislosti se získáváním znalostí z databází. Zde se používají metody u ení se koncept m ale k dispozici jsou i alternativní (statistické) p ístupy. V centru naší pozornosti tedy budou empirické metody u ení se koncept m na základ p íklad rozhodnutí resp. na základ pozorování a objevování. Použitým p ístupem bude induktivní inference kdy na základ kone ného po tu p íklad budeme hledat obecný popis konceptu (a už daného u itelem nebo vytvo eného systémem).
8.1 Úloha empirického u ení Úlohu empirického u ení se koncept m s u itelem (tedy úlohu vytvo it na základ dat klasifika ní model) m žeme formáln definovat následujícím zp sobem. P edpokládejme, že analyzovaná data jsou uložena v tabulce D, tvo ené n ádky a m sloupci.
1
D=
x11 x 21
x12 x 22
: x n1
: xn 2
...... x1 m ...... x 2 m : ...... x n m
ádky tabulky reprezentují sledované objekty. N kdy se místo termínu objekt používají termíny záznam (v databázi), p íklad, p ípad, pozorování apod. i-tý objekt je tedy ádek xi. .
x i = [ xi1 xi 2 . . . xim ] Sloupce datové tabulky odpovídají atribut m. Podobn jako v p ípad objekt , i zde se používají další termíny – veli ina, prom nná, znak. j-tý atribut (j-tý sloupec) ozna íme symbolem Aj .
Aj :
x1 j x2 j : x nj
V tuto chvíli nebudeme rozlišovat, zda se jedná o atributy kategoriální (symbolické, diskrétní) nebo atributy numerické (spojité). Tato informace bude d ležitá až pro jednotlivé typy metod. U klasifika ních úloh p edpokládáme, že existuje atribut, který obsahuje informaci o za azení objekt do t íd (v p ípad klasifikace v užším smyslu) nebo který obsahuje predikovanou hodnotu (v p ípad predikce). íkejme tomuto atributu cílový a ozna me ho symbolem C.
C:
y1 y2 : yn
Ostatním, necílovým atribut m Aj budeme íkat vstupní atributy. Op t m žeme v literatu e nalézt adu dalších názv : cílovému atributu se n kdy íká závislá prom nná, závislá veli ina nebo vysv tlovaná veli ina, vstupním atribut m se n kdy íká nezávislé prom nné, nezávislé veli iny nebo vysv tlující veli iny. P idáme-li cílový atribut do datové tabulky, získáme data vhodná pro použití n které metody u ení s u itelem. Cílem t chto metod je na základ dat tvo ených hodnotami vstupních atribut i cílového atributu odvodit znalosti použitelné pro klasifikaci nových objekt . Dat m používaným k tomuto ú elu se obvykle íká trénovací data (trénovací p íklady). P íslušnou datovou tabulku budeme zna it DTR
2
D TR =
x11 x 21
x12 x 22
:
:
x n1
xn 2
...... x1 m ...... x 2 m :
y1 y2 :
...... x n m
yn
Objekt (trénovací p íklad) z této tabulky budeme zna it
oi = [ x , y i ] P edpokládejme, že pro každý objekt oi známe všechny hodnoty xi i hodnotu yi . V drtivé v tšin situací p edpokládáme, že nezáleží na po adí objekt v datové tabulce1 . Budeme tedy data považovat za množinu objekt D TR = {oi , i=1,..,n} Klasifika ní úlohu m žeme chápat jako úlohu nalézt takové znalosti (reprezentované rozhodovací funkcí f), které by umož ovaly k hodnotám vstupních atribut n jakého objektu p i adit vhodnou hodnotu atributu cílového f: x → y.
Rozhodovací funkci f p itom chápeme v dosti širokém významu. Je-li klasifikace založena na algoritmu používajícím rozhodovací stromy, je tato funkce (a tedy i hledané znalosti) reprezentována jedním konkrétním rozhodovacím stromem. Je-li klasifikace založena na neuronové síti, je tato funkce (a tedy i hledané znalosti) reprezentována topologií konkrétní sít a váhami vazeb mezi neurony. V pr b hu klasifikace se tedy pro hodnoty vstupních atribut x n jakého objektu o odvodí hodnota cílového atributu. Ozna me tuto odvozenou hodnotu . = f (x). Odvozená hodnota se pro objekty z trénovacích dat m že lišit od skute né hodnoty y. M žeme tedy pro každý objekt oi ∈ DTR vy íslit chybu klasifikace Qf(oi, i). V p ípad numerického atributu C m že být touto chybou nap íklad tverec rozdílu skute né a odvozené hodnoty cílového atributu (oi ,
)
)2
v p ípad kategoriálního atributu C m že být touto chybou informace o tom že se odvozená a skute ná hodnota vzájemn liší,
1
Výjimku tvo í prostorová data (nap . data z geografických informa ních systém ), nebo asová data (nap . vývoj cen akcií), kdy uspo ádání mezi objekty vyplývá z povahy t chto dat.
3
( ,
pro pro
)
≠
Pro celou trénovací množinu D pak m žeme vy íslit souhrnnou chybu Err(f,DTR), nap íklad jako st ední chybu )
Cílem u ení je nalézt takové znalosti
( ,
)
které by minimalizovaly tuto chybu =
)
V p íad , že trénovací data neobsahují kontradikce, tedy že platí ∀ o1, o2 ∈ DTR :
x1 = x2
y1 = y2
lze teoreticky nalézt takovou reprezentaci koncept f*, že Err(f*,DTR) = 0. M žeme tedy nalézt znalosti bezchybn klasifikující p íklady v trénovací množin . Naším cílem je ale samoz ejm nalézt znalosti obecn jší, použitelné i pro klasifikaci objekt nových. Ne vždy je nulová chyba Err(f*,DTR) dosažená na trénovacích datech zárukou kvality nalezených znalostí. P ílišná orientace na trénovací data m že vést k „p eu ení systému“ (overfitting); získané znalosti pak nereflektují obecn jší zákonitosti, ale pouze kopírují strukturu použitých p íklad (viz Obr. 1 a Obr. 2). D raz tedy klademe na to, že v pr b hu u ení zobec ujeme použité p íklady na celou aplika ní oblast. Schopnost nalezených znalostí generalizovat se obvykle ov uje experimentáln na tzv. testovacích datech DTST; tedy pomocí chyby Err(f*,DTST). Testovací data mají stejnou strukturu atribut , jako data trénovací, obsahují tedy i cílový atribut. Jedná se ale o objekty, které nabyly použity v pr b hu u ení. Empirické metody u ení vycházejí z p edpokladu, že jednotlivé objekty (p íklady, pozorování) lze popsat pomocí charakteristik takových, že objekty pat ící k témuž konceptu mají podobné charakteristiky (tyto metody bývají n kdy nazývány u ení na základ podobnosti - similarity-based learning). Pokud jsou objekty popsány hodnotami atribut , lze je reprezentovat jako body v mnohorozm rném prostoru, jehož dimenze je dána po tem t chto atribut 2. U ení na základ podobnosti pak vychází z p edstavy, že objekty p edstavující p íklady téhož konceptu vytvá ejí shluky v tomto prostoru. Cílem u ení je tedy nalézt vhodný popis t chto shluk . Hlavním problémem p i použití výše uvedeného p ístupu je nalezení on ch vhodných charakteristik. Z hlediska procesu dobývání znalostí z databází je toto úkolem krok p edzpracování dat. Ovšem ani ve chvíli, kdy máme nalezeny vhodné charakteristiky, není ješt vyhráno. Otázkou z stává dostate né množství dostate n reprezentativních dat. Tento problém je ilustrován na obrázcích Obr. 1 a Obr. 2. V obou p ípadech se snažíme na základ výše p íjmu a výše konta v bance nalézt popis klient , kterým banka p j í (klienti ) a kterým nep j í (klienti ). Na základ n kolika p íklad klient se zdá, že shluky odpovídající klient m obou skupin jsou zachyceny na Obr. 1. Další p íklady spolehlivých klient nás ale p esv d í o našem omylu (p íklady v šedém oválu na Obr. 2). 2
4
Atribut m se n kdy íká p íznaky (features), odtud anglický název tohoto prostoru – feature space.
Popis konceptu, který byl nalezen na základ použitých p íklad tedy nemusí odpovídat jiným (dosud nezpracovaným) p íklad m téhož konceptu. Z tohoto d vodu se obvykle data použitá p i induktivním získávání znalostí rozd lují na ást trénovací a ást testovací. Trénovací data se použijí ve fázi u ení, testovací data pak p edstavují p íklady, které slouží k prov ení získaných znalostí. V n kterých p ípadech se používají dokonce t i soubory dat: data trénovací, data valida ní (používaná pro eventuelní modifikaci znalostí získaných na základ trénovacích dat) a data testovací.
Obr. 1 Málo dat
Obr. 2 Více dat
8.1.1 U ení jako prohledávání
P ijmeme-li p edstavu, že ešit výše popsanou úlohu strojového u ení znamená nalézt vhodné rozd lení dat do shluk (a tyto shluky pak následn popsat modelem ve zvolené reprezentaci), m žeme chápat u ení jako prohledávání prostoru všech shluk (model ). Tento prostor m žeme uspo ádat podle obecnosti model (Obr. 3). Nejobecn jší model (MGM) odpovídá situaci, kdy všechna data tvo í jeden shluk; tento model bude všechny p íklady klasifikovat do majoritní t ídy. Nejspeciáln jší model (MSM) odpovídá situaci, kdy každý p íklad tvo í samostatný shluk; takový model bude obvykle mít nulovou schopnost generalizace a nebude
5
tedy vhodný pro klasifikaci nových p íklad . Model M1 je obecn jší než model M2 (vznikne jeho generalizací), model M2 je speciáln jší než model M1 (vznikne jeho specializací). Krok specializace tedy znamená rozd lení jedné ze skupin obsažených v modelu M1 do dvou skupin (vznikne model M2) a krok generalizace znamená spojení dvou skupin obsažených v modelu M2 do jedné skupiny (vznikne model M1).
Obr. 3 Prostor model
Prostor všech model je ovšem obrovský. Pro ur ení po tu všech možných zp sob jak rozd lit n p íklad do skupin lze použít tzv. Bellova ísla [Bell, 1934]. Tato ísla jsou definována následujícím rekurzivním p edpisem B(0) = 1, B(n) =
n −1 k
n −1 B(k ). k
Prvních n kolik Bellových ísel ukazuje tabulka 1. n B(n)
1 1
2 2
3 5
4 15
5 52
10 115975
Tab. 1 Bellova ísla
Ale i kdybychom uvažovali pro každý možný po et shluk to nejlepší rozd lení (model) – tak jak nap íklad postupují hierarchické metody shlukové analýzy – po et n z stává pro reálné úlohy p íliš vysoký.
6
Pro prohledávání prostoru model se nabízí ada zp sob dob e známých z jiných oblastí um lé inteligence [Winston, 1992]. Kritérii, pomoci kterých budeme posuzovat jednotlivé zp soby budou: •
Sm r: prohledávání od obecn jších model ke speciáln jším neboli shora dol , nebo od speciáln jších k obecn jším neboli zdola nahoru,
•
Strategie: prohledávání slepé (do hloubky nebo do ší ky), heuristické (obvykle se pro daný krok vybere nejlepší možnost- tato strategie se nazývá best-first, gready nebo hill-climbing), nebo náhodné,
•
Ší e: prohledávání jednoduché (pro daný krok uvažujeme jen jednu možnost), nebo paralelní.
8.1.2 U ení jako aproximace funkcí
Op t vycházíme z (již d íve uvedené) p edstavy, že objekty téže t ídy tvo í shluky v prostoru atribut . Jednotlivé shluky lze od sebe odd lit hranicí kterou m žeme popsat jako funkci hodnot jednotlivých atribut . P i u ení se tedy snažíme na základ p íklad objekt jednotlivých t íd nalézt tuto funkci. P i aproximaci n jaké funkce se na základ hodnot této funkce v kone ném po tu bod snažíme zrekonstruovat její obecnou podobu ( asto vyjád enou analyticky). Na rozdíl od interpolace nepožadujeme, aby nalezená funkce procházela známými body. Cílem je nalézt takovou funkci, která by co možná nejlépe vystihovala funk ní hodnoty i v bodech, které nemáme k dispozici. Hledání takového popisu je založeno na vyhodnocení odchylky mezi skute nou funk ní hodnotou ve známém bod a mezi funk ní hodnotou v tomto bod , která vychází z hledaného popisu funkce. Naším cílem je minimalizovat celkovou odchylku ve všech známých bodech (Obr. 4).
Obr. 4 Lineární aproximace
P i aproximování funkcí se obvykle používá metoda nejmenších tverc popsaná v kapitole v nované statistickým metodám. P ipome me zde tedy jen to, že p i použití této metody minimalizujeme sou et druhých mocnin odchylek mezi skute nou hodnotou y a „vypo ítanou“ hodnotou . P i výpo tu hodnoty y p itom p edpokládáme ur itý typ funk ní
7
závislosti y = f(x) specifikovaný pouze svými parametry (ozna me je symbolem q), a metodou nejmenších tverc hledáme tyto parametry. Hledání minima celkové odchylky )2
)
se pak p evádí na ešení rovnice d dq
n
( y i - f ( x i ) )2 = 0
i =1
V p ípad analytického vyjád ení hledané funkce f(x) (to je p ípad regresní nebo diskrimina ní analýzy kdy se volí typ funkce) lze z výše uvedené rovnice spo ítat na základ p íklad oi = [xi, yi] její parametry q. V p ípad , že tvar hledané funkce neznáme, je t eba použít numerické metody. Minimum funkce se pak hledá itera ními gradientními metodami. Tyto metody jsou založeny na tom, že z daného místa (aktuální hodnoty funkce) se p i hledání minima pohybujeme ve sm ru nejv tšího spádu (gradientu) ∂Err ∂Err ∂Err . , ,..., ∂q 0 ∂q1 ∂qQ
∇ Err(q) =
Modifikace znalostí q = [q0, q1, ..., qQ] pak probíhá podle algoritmu
qj ← qj + ∆qj
kde
qj = -
∂Err ∂q j
a η je parametr vyjad ující „velikost kroku“ kterým se p ibližujeme k minimu funkce Err. Je-li nap . chybová funkce )2 =
)
)) 2
a p edpokládaná funkce f lineární kombinací vstup
f(x) = q . x , m žeme odvodit gradient funkce Err jako ∂ ∂
a tedy
8
=
∂ ∂
(
)
2
i =1
2(
∂
)∂ (
)
=
(
∂
)∂ (
)
=
(
)(
)
∆
η
(
)
8.2 Metody strojového u ení Zp sob, jakým jednotlivé metody reprezentují znalosti získané z dat p itom m že být zna n rozmanitý. Mohou to být reprezentativní p íklady-etalony (tak je tomu u metod založených na analogii), mohou to být funkce p i azené jednotlivým shluk m (to je p ípad subsymbolických metod), m že to být rozd lení prostoru atribut na snadno popsatelné, pravidelné útvary (to je p ípad metod symbolických – rozhodovacích strom nebo pravidel). Jednotlivé metody se ovšem neliší pouze zp sobem reprezentování hledaných znalostí. Další rozdíly mezi metodami spo ívají v tom: •
pro jaký typ úlohy dobývání znalostí jsou vhodné (p i deskrip ních úlohách jde o nalezení srozumitelných znalostí, které popisují základní nebo zajímavé souvislosti v datech, p i klasifika ních úlohách jde o nalezení znalostí, které lze použít pro klasifikaci nových p ípad ), • jak složité shluky dokáží reprezentovat (nap . otázka lineární separability), • do jaké míry jsou nalezené znalosti srozumitelné pro uživatele (symbolické vs. subsymbolické), • jak jsou nalezené znalosti efektivní p i klasifikaci nových p ípad , • pro jaký typ dat jsou vhodné (n které metody pracují pouze s kategoriálními daty, jiné metody umož ují analyzovat kategoriální i numerické atributy). Neexistuje p itom „nejlepší“ algoritmus, který bude dosahovat nejvyšší správnosti klasifikace pro libovolnou úlohu (no free lunch). My se na jednotlivé metody podíváme z výše uvedených dvou základních p ístup . Bude nás zajímat, zda se jedná o u ení jako prohledávání, p i kterém hledáme strukturu i parametry modelu, nebo zda se jedná o u ení jako aproximace, p i kterém hledáme parametry modelu v rámci dané t ídy model . 8.2.1 Rozhodovací stromy
Indukce rozhodovacích strom pat í k nejznám jším algoritm m z oblasti symbolických metod strojového u ení. P i tvorb rozhodovacího stromu se postupuje metodou "rozd l a panuj" (divide and concquer). Trénovací data se postupn rozd lují na menší a menší podmnožiny tak, aby v t chto podmnožinách p evládaly p íklady jedné t ídy. Obecné schéma algoritmu pro tvorbu rozhodovacích strom je na Obr. 5. Algoritmus tedy realizuje jednoduché heuristické prohledávání shora dol (to ostatn napovídá i používaný akronym TDIDT, neboli top-down induction of decision trees). Existují i varianty používající paralelní heuristické prohledávání shora dol (option trees nebo random forrest), p ípadn prohledávání náhodné. TDIDT algoritmus
9
1. zvol jeden atribut jako ko en díl ího stromu, 2. rozd l data v tomto uzlu na podmnožiny podle hodnot zvoleného atributu a p idej uzel pro každou podmnožinu, 3. existuje-li uzel, pro který nepat í všechna data do téže t ídy, pro tento uzel opakuj postup od bodu 1, jinak skon i.
Obr. 5 Algoritmus pro tvorbu rozhodovacích strom
8.2.2 Rozhodovací pravidla (pokrývání množin jako prohledávání)
Algoritmus pokrývání množin vidíme na Obr. 6. Op t se jedná o algoritmus založený na myšlence prohledávání. Na rozdíl od rozhodovacích strom lze ale prostor pravidel prohledávat (resp. pravidla vytvá et v kroku 1 algoritmu) jak „shora-dol “ postupnou specializací obecných pravidel, tak „zdola-nahoru“ postupnou generalizací speciáln jších pravidel. Prohledávání p itom m že být jak jednoduché (v daném kroku uvažujeme jen jedno potenciální pravidlo), tak paralelní (v daném kroku uvažujeme více potenciálních pravidel). Algoritmus pokrývání množin 1. najdi pravidlo, které pokrývá n jaké pozitivní p íklady a žádný negativní, 2. odstra pokryté p íklady z trénovací množiny DTR, 3. pokud v DTR zbývají n jaké nepokryté pozitivní p íklady, vra se k bodu 1, jinak skon i. Obr. 6 Algoritmus pokrývání množin
8.2.3 Asocia ní pravidla
Základem všech algoritm pro hledání asocia ních pravidel je generování kombinací (konjunkcí) hodnot atribut . P i generování vlastn procházíme (prohledáváme) prostor všech p ípustných konjunkcí a to sm rem shora dol . Používají se p itom jak slepé metody (zejména do ší ky), tak metody heuristické využívající kvantitativní charakteristiky jednotlivých pravidel. T mito charakteristikami jsou nej ast ji po et p íklad pokrytých uvažovaným pravidlem, p ípadn spolehlivost pravidla definovaná jako podíl po tu p íklad vyhovujících p edpokladu i záv ru pravidla a po tu p íklad vyhovujících p edpokladu pravidla. 8.2.4 Neuronové sít
Neuronové sít jsou modely, jejichž u ení je založeno na myšlence aproximace. Typickým p íkladem m že být vícevrstvý perceptron (Obr. 7). Pro u ení takovéto sít se nej ast ji používá zobecn ná gradientní metoda zvaná zp tné ší ení chyby (error backpropagation) viz Obr. 8 . U ení se neuronových sítí je tedy typický p íklad u ení jako aproximace funkce: známe topologii sít , což je implicitní vyjád ení typu funk ní závislosti mezi vstupy a výstupy sít , a hledáme „jen“ parametry modelu. 8.2.5 Genetické algoritmy
Genetické algoritmy jsou založeny na paralelním náhodném prohledávání. Zdrojem inspirace se stal mechanismus evoluce, chápaný jako Darwin v p irozený výb r: n jaký živo išný druh
10
se b hem svého vývoje zdokonaluje tak, že z generace na generaci se p enáší genetická informace jen t ch nejsiln jších jedinc . Genetická výbava jedinc z jedné populace m že p echázet do populace následující p ímo (v d sledku selekce), jen drobn modifikovaná (s využitím mutace), nebo prost ednictvím potomk (na základ k ížení). Z hlediska chápání procesu u ení jako prohledávání prostoru modelu realizují genetické algoritmy paralelní (uvažujeme více jedinc v populaci) náhodné (díky operacím k ížení a mutace) prohledávání.
Obr. 7 Vícevrstvý perceptron
Backpropagation algoritmus 1. inicializuj váhy sít malými náhodnými ísly (nap . z intervalu [-0.05,0.05]) 2. dokud není spln no kritérium pro zastavení 2.1. pro každý p íklad [x,y] z trénovacích dat 2.1.1. spo ítej výstup outu pro každý neuron u v síti 2.1.2. pro každý neuron v ve výstupní vrstv spo ítej chybu errorv = outv (1 - outv) (yv - outv) 2.1.3. pro každý neuron s ve skryté vrstv spo ítej chybu errors = outs (1 - outs) v∈výstup (ws,v errorv ) 2.1.4. pro každou vazbu vedoucí od neuronu j do neuronu k modifikuj váhu vazby wj,k = wj,k + ∆wj,k , kde ∆wj,k = η errork xj,k Obr. 8 Algoritmus zp tného ší ení chyby
8.2.6 Bayesovské metody
Bayesovské metody vycházejí z Bayesovy v ty o podmín ných pravd podobnostech. A koliv se tedy jedná o metody pravd podobnostní, jsou intenzivn studovány v souvislosti se
11
strojovým u ením a uplat ují se rovn ž v systémech pro dobývání znalostí. Bayes v vztah pro výpo et podmín né pravd podobnosti že platí hypotéza H, pokud pozorujeme evidenci E má podobu: ×
Bayesova v ta dává návod jak stanovit vliv jedné evidence na uvažovanou hypotézu. Jak ale postupovat, pokud je evidencí více? •
Naivní bayesovský klasifikátor vychází z p edpokladu, že jednotlivé evidence E1,…,EK jsou podmín n nezávislé p i platnosti hypotézy H. Tento zjednodušující p edpoklad umož uje spo ítat aposteriorní pravd podobnost hypotézy p i platnosti všech evidencí ×
∏
×
Hodnoty P(H) a P(Ek|H) odhadujeme z dat. Vzhledem k tomu, že struktura modelu je pevn dána (p edpokladem nezávislosti) a hledáme jen jeho parametry (hodnoty pravd podobností), pat í vytvo ení naivního bayesovského klasifikátoru mezi metody u ení založené na myšlence aproximace. •
Bayesovské sít umož ují reprezentovat znalosti o áste n nezávislých evidencích a tyto znalosti použít p i usuzování. Platí p itom, že sdruženou pravd podobnostní distribuci celé sít m žeme spo ítat jako
∏
!"#$
kde rodi e(u) jsou uzly, ze kterých vycházejí hrany do uzlu u. Pokud z dat odhadujeme strukturu sít , jde o u ení jako prohledávání, pokud je sí pevn dána a z dat odhadujeme jen podmín né pravd podobnosti p i azené jednotlivým uzl m, jde o u ení jako aproximaci.
Obr. 9 P íklad bayesovské sít
8.2.7 U ení založené na instancích
V p ípad u ení založeném na instancích jsou koncepty (t ídy) reprezentovány svými typickými p edstaviteli. Tyto p edstavitele m žeme získat tak, že si zapamatujeme (uložíme do databáze) trénovací p íklady. Není t eba ukládat vše, sta í uložit pouze ty p íklady, které nejsou zatím správn klasifikovány – jde tedy o jednoduché heuristické prohledávání shora dol . Tento zp sob tedy umož uje inkrementáln p idávat nové znalosti (p íklady) do báze
12
p íklad . V p ípad velkého množství p íklad , což je situace typická p i dobývání znalostí z databází, ale nelze uvažovat o uložení všech p íklad . Neobejdeme se tedy ve fázi u ení bez generalizace. Jednotlivé t ídy (resp. shluky p ípad v prostoru atribut ) pak m žeme reprezentovat tzv. centroidy. Neznáme-li p edem po et shluk , jedná se o u ení jako prohledávání (prohledávat m žeme shora-dol p i divizivním shlukování i zdola-nahoru p i aglomerativním shlukování). V p ípad , že po et shluk je p edem dán, jedná se o u ení jako aproximaci.
8.3 Hodnocení znalostí nalezených v pr b hu u ení U deskrip ních model je kritériem kvality nalezených znalostí subjektivní pohled experta, který posuzuje jejich zajímavost, novost a použitelnost. V p ípad klasifika ních model je kritériem úsp šnost klasifikace na datech. Existují r zné zp soby testování •
testování v celých trénovacích datech
•
k ížová validace (cross-validation)
•
leave-one-out
•
bootstrap
•
testování na testovacích datech
které se liší zejména ve zp sobu získání vhodných dat. Ve všech zp sobech se ale vyhodnocuje po et shod klasifikace modelem s informací obsaženou v testovacích datech o za azení p íkladu do t ídy. Tyto údaje se lze zobrazit v tzv. matici zám n (konfusion matrix) jako po et „true positive“ „true negative“ „false positive“ a „false negative“ klasifikací (viz Obr. 10). Na základ této matice se pak po ítají nejr zn jší charakteristiky kvality modelu jako správnost, chyba, p esnost a úplnost apod. % &' (&)$''*+ $ ,- ./ +0&1&0$ 2 3 3 45 4 5 Obr. 10 Matice zám n
8.4 Teoretické problémy strojového u ení 8.4.1 PAC teorie
Def: Koncept je reáln existující t ída objekt . Def: Trénovací množina je kone ná množina p íklad , z nichž n které jsou prvky daného konceptu (pozitivní p íklady) a n které nejsou prvky daného konceptu (negativní p íklady) Def: Hypotéza je formální, explicitní charakterizace konceptu. Def: Hypotéza je
13
•
konzistentní, práv když nepokrývá žádný negativní p íklad
•
úplná, práv když pokrývá všechny pozitivní p íklady
V ta: Cílem strojového u ení je nalézt konzistentní a úplnou hypotézu pro daná trénovací data.
Je dosažení výše uvedeného cíle vždy možné? A co nám íká konzistentní a úplná hypotéza pro trénovací data o kvalit této hypotézy obecn ? Def: Trénovací chyba je chyba, které se hypotéza dopustí na trénovacích datech. Tedy (pro klasifika ní úlohy) je to po et chybn klasifikovaných p íkladech z trénovací množiny. Def: Skute ná chyba je chyba, které se hypotéza dopustí na datech náhodn vybraných z téže populace, ze které pocházejí trénovací p íklady (princip stacionarity). Def: PAC U ení. Koncept je možno se nau it pravd podobn skoro správn (Probably Aproximately Correctly), pokud s pravd podobností alespo 1 - δ nalezneme hypotézu h takovou, že její skute ná chyba je menší nebo rovna ε.
Kolik trénovacích p íklad k tomu budeme pot ebovat? P edpokládejme nejprve, že trénovací chyba hypotézy h je rovna nule. Haussler v teorém: Je-li prostor hypotéz H kone ný a D je sekvence n nezávislých náhodných p íklad konceptu c, pak pravd podobnost, že h ∈ H má skute nou chybu v tší než ε je menší než
| H | e −εn Požadujeme-li, aby tato pravd podobnost byla menší než δ | H | e −εn < δ potom n≥
1
ε
(ln H
+ ln(1 / δ ) ) .
Tento vztah íká, kolik pot ebujeme p íklad pro PAC u ení konceptu c. P íklad: P edpokládejme že data jsou tvo ena m binárními (booleovskými) atributy.
•
Hledáme-li hypotézy v podob konjunkce pozitivních literál (pouze TRUE hodnot atribut ), pak |H| = 2m
Po et trénovacích p íklad , které pot ebujeme pro PAC u ení je tedy n≥
1
ε
(m ln 2 + ln(1 / δ ) )
Požadujeme-li, aby s pravd podobností alespo 95% byla chyba hypotézy menší než 0.1, pak pro 10 atribut pot ebujeme alespo 1 (10 ln 2 + ln(1 / 0.05) ) = 10(6,93 + 3) ≅ 100 p íklad . 0.1
14
•
Hledáme-li hypotézy v podob konjunkce literál , pak |H| = 3m
Po et trénovacích p íklad , které pot ebujeme pro PAC u ení je tedy n≥
1
ε
(m ln 3 + ln(1 / δ ) )
Požadujeme-li, aby s pravd podobností alespo 95% byla chyba hypotézy menší než 0.1, pak pro 10 atribut pot ebujeme alespo 1 (10 ln 3 + ln(1 / 0.05) ) = 10(10,93 + 3) ≅ 140 p íklad . 0.1
•
Hledáme-li hypotézy v podob disjunkce k konjunkcí literál , pak H = 3 mk
Po et trénovacích p íklad , které pot ebujeme pro PAC u ení je tedy n≥
1
ε
(mk ln 3 + ln(1 / δ ) )
Požadujeme-li, aby s pravd podobností alespo 95% byla chyba hypotézy tvo ené 3 konjunkcemi menší než 0.1, pak pro 10 atribut pot ebujeme alespo 10(30 ln 3 + ln(1/0.05)) ≅ 10(33 + 3) = 360 p íklad
•
Hledáme-li hypotézy v podob libovolné podmnožiny p íklad , pak H = 22
m
Po et trénovacích p íklad , které pot ebujeme pro PAC u ení je n≥
1
ε
(2
m
ln 2 + ln(1 / δ ) ).
Pot ebovali bychom tedy více p íklad , než lze pro dané binární atributy vytvo it. Jak vypadá pot ebný po et p íklad ve zbývajících situacích, tedy pro nenulovou trénovací chybu resp. pro nekone ný prostor hypotéz? V ta: Pokud trénovací chyba hypotézy h není rovna nule, tak v p ípad kone ného prostoru hypotéz H je po et p íklad pot ebných pro PAC u ení n≥
1 2ε 2
(ln H
+ ln(1 / δ ) )
V ta: Pokud prostor hypotéz H je nekone ný, tak po et p íklad pot ebných pro PAC u ení je
n≥
1
ε
(4 log 2 (2 / δ ) + 8VC( H ) log 2 (13 / ε )) ,
kde VC(H) (tzv. Vapnik- ervon nkisova dimenze) je maximální po et p íklad , pro které se lze jako koncept nau it s nulovou trénovací chybou libovolnou podmnožinu t chto p íklad .
15
P íklad: Uvažujme, že p íklady jsou popsány hodnotami dvou numerických atribut x1 a x2 (a lze je tedy reprezentovat jako body ve dvourozm rném prostoru atribut ). Nech H je množina všech lineárních diskrimina ních funkcí f = q0 + q1x1 + q2x2. Pak VC(H) = 3, nebo pro žádnou tve ici p íklad nem že být libovolná podmnožina t chto p íklad odd lena p ímkou od p íklad zbývajících (jde o analogii s XOR problémem u lineárního perceptronu), ale pro t i p íklady to možné je (Obr. 11).
Obr. 11 Klasifikace libovolné podmnožiny t í bod
V ta: VC dimenze množiny lineárních diskrimina ních funkcí v m-rozm rném prostoru je m+1. 8.4.2 Bias a variance
Dva d ležité pojmy, se kterými se setkáváme v souvislosti s hodnocením jednotlivých algoritm strojového u ení, jsou bias a variance. Bias (apriorní omezení, p edpojatost), je souhrnné ozna ení pro adu skrytých p edpoklad jednotlivých algoritm ). Obvykle se používá: •
Deklarativní bias (preferen ní relace mezi jednotlivými hypotézami)
•
Jazykový bias (preferen ní relace mezi jazykovými prost edky, které se používají pro popis koncept )
•
Prohledávací bias (po adí, v jakém jsou vyhodnocovány jednotlivé hypotézy)
V p ípad dvou stejn kvalitních (z hlediska trénovací chyby) hypotéz se obvykle preferuje ta jednodušší. Filozofické zd vodn ní tohoto p ístupu podal již ve 13. století William z Ockhamu (Entia non sunt multiplicanda praeter necessitatem) – proto se tomuto p ístupu íká Ockhamova b itva. Variance vyjad uje, do jaké míry je nalezená hypotéza citlivá na zm nu trénovacích dat. Bias a variance jsou spolu vzájemn svázány - bias vyjad uje kvalitu hypotézy, variance vyjad uje robustnost hypotézy: •
16
Jednoduché hypotézy, obsahující málo parametr , mají vysoký bias (vyšší chybu) a nízkou variance (nepodléhají velkým zm nám p i zm n trénovacích dat).
•
Složité hypotézy, obsahující mnoho volných parametr , mají nízký bias (nižší chybu), ale vysokou variance (jsou citlivé na zm nu dat)
Obr. 12 Vysoký bias, nízká variance
Obr. 13 Nízký bias, vysoká variance
8.4.2 D ležité teorémy
Otázkou, která napadne každého, kdo chce použít algoritmy strojového u ení je, zda existuje n jaký „univerzáln nejlepší“ algoritmus. Odpov je bohužel záporná. No free lunch teorém: Pro libovolné dva algoritmy A a B platí, že je-li algoritmus A lepší (ve smyslu chyby) než algoritmus B na n jakých k datových souborech (úlohách), pak existuje jiných k datových soubor (úloh), na kterých je algoritmus B lepší než algoritmus A.
(Algoritmem ve výše uvedeném teorému m že být i náhodné hádání p íslušnosti ke t íd ) Teorém ošklivé ka átko:
1. Pokud používáme pro popis p íklad , které chceme od sebe odlišit hodnoty atribut , pak po et atribut , ve kterých se popisy libovolných dvou p íklad shodují, je konstantní. 2. Pokud vyjad ujeme podobnost mezi p íklady po tem atribut ve kterých se jejich hodnoty shodují, pak libovolné dva p íklady jsou si stejn podobné.
8.5 Adaptace Pojmy „adaptivní systém“ a „u ící se systém“ lze nalézt v teorii ízení již v šedesátých létech. V uvedeném kontextu se v obou p ípadech jedná o systémy, které mají schopnost p izp sobovat se prost edí, ve kterém pracují. Tato schopnost je chápána jako minimalizace ztráty, které se systém dopouští v procesu rozhodování (klasifikace). Zatímco adaptivní systém se každé nové situaci p izp sobuje nezávisle na p edcházejících adaptacích a situacích, cílem u ícího se systému je dosáhnout dlouhodob ji optimálního chovaní; zkušenost z jednotlivých díl ích adaptací se zobec uje do obecn ji použitelného modelu. U ící se systém tedy v teorii ízení p edstavuje dokonalejší nástroj než systém adaptivní. V pon kud jiném významu se pojem „adaptivní“ objevil v posledních letech v souvislosti s inteligentními systémy, zejména se systémy z oblasti strojového u ení a soft computing. V obou p ípadech se jedná o systémy z oblasti um lé inteligence. Zatímco strojové u ení klade d raz na schopnost generalizovat z p íklad , a zabývá se tedy zp sobem získávání znalostí, soft computing klade d raz na schopnost rychle nalézat ešení (ne nutn optimální) vágn a neúpln popsaných problém , a zabývá se tedy zp sobem zpracovávání znalostí.
17
Vzhledem k tomu, že zp sob získávání znalostí jde asto ruku v ruce se zp sobem jejich zpracování, m žeme adit celou adu metod jak do oblasti strojového u ení tak do oblasti soft computing. Mezi metody strojového u ení pat í metody pro tvorbu rozhodovacích strom , asocia ních pravidel, rozhodovacích pravidel, neuronové sít , genetické algoritmy, metody založené na analogii, bayesovské metody, nebo induktivní logické programování. Do soft computing se obvykle adí systémy založené na fuzzy logice, neuronové sít a genetické algoritmy, p ípadn hybridní systémy využívající kombinaci více metod (nap . neuro-fuzzy systémy). Schopnost u ení je v tšinou nedílnou sou ástí uvedených metod. V kontextu inteligentních systém je tedy adaptivita „n co navíc“. Ve shod s evropským výzkumným projektem EUNITE (IST-2000-29207) budeme zde adaptivitu chápat jako (Anguita, 2001): •
schopnost inteligentního systému p izp sobit se zm nám prost edí,
•
schopnost inteligentního systému p izp sobit se novým podmínkám využívání,
•
schopnost inteligentního systému p izp sobit se nové aplikaci.
V prvním p ípad musí být inteligentní systém schopen rozpoznat asové nebo prostorové zm ny prost edí ve kterém p sobí a adekvátn reagovat. P íkladem m že být rozpoznání zm ny preferencí zákazník p i elektronickém obchodování nebo regulace nestacionárního systému. Ve druhém p ípad se jedná o schopnost systému pracovat i v jiných podmínkách, než pro které byl vyvinut. P íkladem m že být možnost p enést systém pro klasifikaci rizikovosti klient z jedné finan ní instituce (nap . banky) do jiné finan ní instituce (nap . pojiš ovny) bez nutnosti vývoje celého systému znovu. T etí p ípad se týká možnosti p enesení inteligentního systému do zcela jiné aplika ní oblasti. Aby byl inteligentní systém považován za adaptivní ve výše uvedeném smyslu, nemusí vykazovat všechny uvedené schopnosti. Zam íme se na adaptivní rysy systém z oblasti strojového u ení. Podrobn ji se podíváme na problémy související s •
inkrementálním u ením,
•
u ením a zapomínáním,
•
integrací znalostí,
•
metau ením,
•
revizí znalostí,
•
využitím analogií.
8.4.1 Inkrementální u ení
P i inkrementálním u ení lze, na rozdíl od dávkového u ení, dosud získané znalosti pr b žn modifikovat na základ nových p íklad . Na vstupu inkrementálního algoritmu je p vodní model a nový p íklad, výstupem je aktualizovaný model. N které algoritmy (nap . u ení založené na instancích) jsou inkrementální ze své podstaty, jiné algoritmy (nap . tvorba rozhodovacích strom ) je t eba podstatn modifikovat.
18
Obr. 14 Dávkové vs. inkrementální u ení
8.4.2 U ení a zapomínání
U ení a zapomínání hraje roli v úlohách, kdy koncepty, které je t eba se nau it, se pr b žn m ní. Na rozdíl od inkrementálního u ení, kdy považujeme za relevantní všechny p íklady, které postupn používáme, zde hrají roli jen p íklady nejnov jší. Obr. 15 ilustruje p ístup založený na použití okna, ve kterém jsou uchovávány jen aktuální p íklady. Na jedné stran jsou do okna p idávány nové p íklady (systém se u í), na druhé stran jsou z okna odstra ovány p íklady staré (systém zapomíná). P i u ení resp. zapomínání se modifikuje ta ást znalostí, která pokrývá p idávaný resp. odebíraný p íklad. u ení zapomínání
u−
u+ POS z+
u+ POT
u−
NEG
z−
z+
z−
Obr. 15 U ení a zapomínání
8.4.3 Integrování znalostí
Pod pojmem integrování znalostí chápeme proces kombinace znalostí získaných z r zných zdroj resp. r znými zp soby. K integrování znalostí m že docházet na úrovni usuzování nebo na úrovni reprezentace. Na úrovni usuzování se jedná o r zné zp soby kombinování model . Obecné schéma kombinování model vidíme na Obr. 16. K základním p ístup m pat í bagging, boosting a stacking. Bagging
U ení je založeno na vytvo ení „paralelních“ model na základ r zných podmnožin trénovacích dat (náhodný výb r s opakováním). Použije se týž algoritmus pro u ení. P i klasifikaci rovné hlasování model
Boosting
U ení má podobu vytvo ení sekvence model . Každý model se zam uje na ty p íklady, které se p edcházejícími modely nepoda ilo klasifikovat (vážení p íklad ). P itom se použije (týž) algoritmus pro u ení. P i klasifikaci vážené hlasování model .
19
Stacking
U ení má podobu vytvo ení „paralelních“ model . P itom se použijí r zné algoritmy na stejná data. Pak následuje tzv. meta-u ení (u ení z výsledk jednotlivých klasifikací).
Obr. 16 Kombinování model
Obecné schéma integrování znalostí na úrovni reprezentace ukazuje Obr. zp sobem se postupuje ve znalostním inženýrství.
17. Tímto
Obr. 17 Integrování na úrovni reprezentace
8.4.4 Integrace/revize znalostí
V p ípad revize znalostí vycházíme z toho, že p vodní, neúplné znalosti m žeme modifikovat na základ trénovacích p íklad . Výsledný model je konzistentní s p vodními znalostmi. Oblastí která tímto zp sobem p istupuje k úloze strojového u ení, je induktivní logické programování (ILP). Úlohu ILP m žeme definovat následujícím zp sobem: je dána po áte ní znalost B, a trénovací p íklady pozitivní E+ a negativní E- (z hlediska jedné t ídy). Cílem je nalézt nové znalosti H tak, aby:
20
•
z H a B byly odvoditelné všechny pozitivní p íklady
•
z H a B nebyl odvoditelný žádný negativní p íklad
•
H a B byly konzistentní
Obr. 18 Úloha revize znalostí
8.4.5 Analogie a adaptace
Základní myšlenkou usuzování na základ analogie je použít ešení, které se v minulostí osv d ilo na podobné úloze, kterou ešíme nyní. Tento princip našel své vyjád ení ve statistice (klasifikace dle nejbližšího souseda), p ípadovém usuzování i strojovém u ení. P ípadové usuzování (Case-Based Reasoning, CBR) pracuje zp sobem nazna eným na Obr. 19 (Watson, Marir, 1994): •
retrieve (najdi nejpodobn jší p ípady)
•
reuse (použij navržené ešení)
•
revise (p ípadn reviduj navržené ešení)
•
retain (uchovej nové ešení v bázi p ípad = u ení) Problém
R
R
retrieve
r e u s e
retain Báze p ípad
R
P ijaté ešení
revise Navržené ešení
Obr. 19 P ípadové usuzování
21
Cvi ení: 1) P íklad: Data o klientech banky, kte í žádají o úv r jsou tvo ena atributy p íjem (s hodnotami vysoký, nízký), konto (vysoké, nízké, st ední), pohlaví (muž, žena), nezam stnaný (ano, ne). Kolik trénovacích p íklad pot ebujeme pro PAC u ení hypotéz, tvo ených konjunkcemi pozitivních literál ? 2) P íklad: Data o klientech banky, kte í žádají o úv r jsou tvo ena atributy p íjem (s hodnotami vysoký, nízký), konto (vysoké, nízké, st ední), pohlaví (muž, žena), nezam stnaný (ano, ne). Kolik trénovacích p íklad pot ebujeme pro PAC u ení hypotéz, tvo ených konjunkcemi literál ? 3) P íklad: Data o klientech banky, kte í žádají o úv r jsou tvo ena atributy p íjem (s hodnotami vysoký, nízký), konto (vysoké, nízké, st ední), pohlaví (muž, žena), nezam stnaný (ano, ne). Kolik trénovacích p íklad pot ebujeme pro PAC u ení hypotéz, tvo ených libovolnou podmnožinou? 4) P íklad: Nech X je množina reálných ísel (vyjad ujících nap . výši p íjm ). Nech hypotézy jsou intervaly (a, b) (neboli hypotézy mají tvar a ≤ x ≤ b). Jaká je VC dimenze prostoru všech takových hypotéz?
22
