UČENI ZAZNAMENÁVÁNÍM PŘÍťADÚ
Lze použít v případech, kdy není možné vytvořil dohry mode!.
Knttfiistp.Hční heuristika: používá se k odhadování neznámých vlastností nových případů porovnaním s případy z líz n a men any mi:
Kdykoliv je zapotřehí odhadnout vlastnost nejakého objektu a iv n í k dispozici nit:, ne/ soubor zaznamenaných referenčních případů, postupuje se tak. že se najde nejpodobnější případ, jehož vlastnosti jsou známy. O neznámé hodnote atributu se pak předpokládá, zeje stejná jako u podobného, jiz zaznamenaného případu. Podobnost se určuje vhodně zvolenou metrikou.
Příklad: v paměti jsou uloženy údaje o osmi kvádrech různé velikosti a barvy. Jsuu-lí u noveno, dosud nezaznamenaného kvádru (případu) známy rozměry n není známa barva, pak — není-ti k dispozici jiné vodítko — se určí stejná barva jako u již zaznamenaného kvádru rozměrově nejpodobnějšího,
červen*
^žlulá
4        imiitrii
<*        ?
|> LI l|lLir[> VC|
oraníoví
í ii r vend
fialtwi
2
ÍLlLlíl
4            r,
Sirka
červen:!                                          í|ulá liiirpwrírvťí 4    modři      '    o       ■'"                       ■■*■ ca .M                                       ä           " ■"      ^n    ^b    ^b    ^k   ^h    ^h    am    — ■í-                      f 2                                !■ ŕ                                liiniiiŕuvji            *» *                        a c »oní červena fialová 0                2               4               6               K " Šířka
A                                                                         ■ červená                                          ž1lllÄ 4 ™ T ™ "7 -Ť                                                                                       -K 1    * 1                             zelenú Cüivcn.i            w finlnva
4              6             S
äiŕkíi
tá
.červena
mod r á       r>
°
iŽl isté
purpurová
oranžovú
[)
fialová 2            4
Ätíltíllá
Ěíf k a
Kvádr neznámé barvy je klasifikován jako modrý, nebul" je modrému vzorku nejhlíže kvou výškou a šířkou.
*     Konsistenčitíheuristika: umožňuje řešil obtížné dynamické problémy:
y
v/////////4wmmmwMfc
Mode] ramene robotu, přenášejícího míček, lze sestavit pomocí di-teiienciálních rovnic, kde točivé momenty motoru v kloubech JSOU funkci" ťihlu 0 a délek ramen /. Problém reálného s véla je však zcela jiný: požadované mementy závisejí ve skutečností na rychlostech {v jejích mocninách a součinech) a zrychleních pohybu ramen, což zahrnuje Corioltsovy a dostředivé síly a dále proměnné vzájemná závislé setrvačné tu o me n ty.
I kdyby se podařilo zachytit v rovnicích v/tahy mezi vSerm atributy, výsledky a řízením reálného ramene robota nebudou uspokojivé a neposkytnou vysvetlení, jak je schopno biologie ké rameno dobře vrhat míček — exiluje príiLš mnoho faktorů jež jif nutní) uvažovat ĺi příliš mnoho veličin, jež je nutno přesně měřit,
■ Metodu« ejblifSiho sou sada umožňuj e praktická řeSení podobných problému. L/e např. nechal více-iuénč náhodné konat rameno pokusné pohyby a zaznamenávat do tabulky hodnoty momentu, úhlů, rychlostí alp. Chceme-I i, aby byl míček dopraven po konkrétní trajektorii, pak jt rozdílíme na malé úseky a na tabulku budeme hledčt jako na m noha rozměru y prostor různých řešení. Pro každou pozici blízko požadované trajektorie zjistíme, které hodnoty parametrů (úhly. rychlosti, zrychlení ...) jí odpovídají a interpolací mezi nimi najdeme potřebné momenty odpovídající žádaně dráze.
Tabuíka ovšem nebude často dostatečně hustě vyplněná (tj. prostor řešení bude vyplněn řídce příslušnými body). Praktickým řešením je nechat udělal první pokus, kletý bude nejspíš Spalný- Po několika dalších pokusech (a lim i zápisu nových údajů do tabulky) začne docházel ke zlepšování — nové vstupní údaje budou lepší než staré a pohyb bude nakonec uspokojivý:
po prvním poku.su
________________________________________________________...                               ■                                         /      \
.-------------------------------------------------------------------------------------------------.--------------------i------------------------!■--------------
po druhém pokusu
po několikátém pokusu
•     Hledání nejbližšího sousedu — lze buď sekvenčně noho paralelně.
* Sekvenční: spočítá se vzdálenost Od ostatních připadli íi zvolí se nejbližší případ. Pro u ostatních případů existuje n výpočtů vzdáleností a n-J porovnání Ičchto hodnot. Přímočarý postup je použitelný pro malá n í napi. 1 OK ale ne napr pro n=\ O6.
Problém velkého počtu operací lze vyřeSit použitím rozhodovacích stm/tiii, ktiy je počet operací úmčmý log,n místo ti. Pro príklad kvádrů lze postupovat takto: kvádry se rozdělí na dvě množiny napf. podle výšky (menší než nejaká hodnota a větší) rak, aby obě části mely stejný počet prvku. Dále .se každá tato množina podobuč rozdčlí podle Sirky, pak zase podle výšky aid. Výsledkem je izv. k-d strom (k-dimensional trče):
k-d strom je reprezentace rozhodovacího stromu, v němž;
>       soubor možných odpovědí se skládá z. bodů, z nichž jeden může být nejbližším .sousedem daného bodu;
• každý test specifikuje souřadnici, práh a neutrální zónu v okolí prahu, která neobsahuje rádné body;
►      každý tesi dělí soubor bodů na dvě části v sou ladu s tím, na které straně prahu každý bod le-
7.1.
Nalezení nejbližšího kvádruje tedy pouze záležitostí sledování
příslušné cesty v rozhodovacím stromu, která reflektuje způ-soh,jak jsou objekty rozdělovány do podmnožin.
Obecně platí, že má-li rozhodovací strom faktor rozvetvení 2 a hloubku d, pak bude mít lú listu. Má-li být identifikováno n objektu, musí být splněno, že 2J > n. Logaritmováním obou stran dostáváme, že počet porovnání - logjti*
I   modr;i ILxi vci)flll|>Livpur
žlutá
Paralelní: Kdybychom mcii k dispozici masivně-paraklní počítač, kde pro každý případ by byl jeden procesor, pak není zapotřebí uvedene důmyslně hledaní. Ka/dé měření vzdálenosti by slo provést paralelně. Samozřejmě vSechay výsledky musí být nějak porovnány, aby byla stanovena nejmenší vzdálenost atributu s neznámou hodnotou. Bylo by napr. možné používat sousední procesory k porovnání jejich výsledků. Kazde takové d1* ouprocosorové minimum by opcí bylo porovnáno se soused uíiii dvoupíocesorovým minimem. Tento postup by nakonec dal globální minimum po počni sekvenčních kroku řádu logjitt kde/(je počet porovnávaných vzdáleností. Existují ovšem ]ep-fií způsoby jak najít minimální vzdálenost v konstatním čase na paralelním počítači.
Algoritmu* r o/.dolování případů do množin:
►       je-li jen jeden případ. STOP:
►       jde-!i o prvnídelení, zvol pro srovnávání vertikální osu, jinak zvol osu různou od osy použité na nejhližíí vyssí úrovni:
*■ vzhledem k ose delení, najeli polohu mezi dvěma prostředními objekty a ikizvj kilo po/ici práh; vytvoř teM rozhodovacího stromu j ľ ni porovnává neznámé objekty v uč i prahu; zaznamenej pozici obou prostředních objektu na nse srovnání a nazvi tytu pozice spadni a Storni luanicc;
►       rozdej väeehny objekty na d v; t pod so li hory podle toho, na klené stranS střední pozice leží;
ľ rozděl objekty v každé v, obou množin a vytvoř tak podstrom pro každou ? nich ?ti použití výše uvedené procedury.
Algoritmus k-íiprocedury pro hledáni':
*       urči. zda existuje pouze jediný element v uvažovaném souboru:
*■      pokud ano. zaz name nej j ej. jinak
*■ porovnej klasifikovaný objekt na ose porovnání vůči s oč tísnému prahu uzlu: výsledek určuje množinu podobných objektů;
*       použitím Léto procedury najdi v určené množine nejbližšího souseda;
*-      urči, zda vzdálenost k nejbližšímu sousedovi v
množině <, vzdálenost ke druhé hnniei munži-
ny níi ose porovnávaní:
►■ pokud ano. zaznamenej nejbližšího souseda v této množine, jinak
*■ otestuj dn.íhuu množinu touto procedurou; j^tko výsledek vrať bližšího z obou blízkých sousedů v o b öle množinách.
Heroda* k-t/A) <piLe^pßk@&d&.   ze^ vŠeeMťiy *>č/béa^y {**-H ,   tt&yfc&£i J4a,4&ůJ PteiéLkď mír&M&tS \& u-H&vi fw -
á(*i *i) = i 2 («*<M - *^J)'

•  AJtcttl* X^j ...j Jí-,   eJiurbťřt^ií^   A?  Mßr***c*   2.



ŕe*/e> J^ j& ■ih&toisfuasc-t  ťn*4tn,wyts  ťíéjjb&vZSt   k  Xf •
+■	
	^~
tsP\k^><^dCi   fiťe.rtQV&'Ct   ttttjoiZ***.),    áJ^tMs^UAy   Ohi&ftscA
he*
i-icfl^
Ol/Í
tówowéŕro <a/ia-*H£*/n (tfot-oviQJi 4-) - jfehff^ŕa/- t\A<duM.Q\fo.-
Apt-**CHMZ^ Smrtko! u*/ Sfo^llw U4*e't/*ŕs(A. :
Atikou 1-wn^s   k-wtJ JL-z& jn<24£*iQ a&tAýfJ&saJ-r ó&eÁ*! hodíteqI#s   U-n*fe £.{/£& %ch   mf&we*j fos-
y*r   ^ —
Pro pi-1padj iß- ^y Jí^. /?/^ö pŕe-s-nŕ hsn/tfo Jŕ^ ä, m~
w—á                           ť^ r^,)=c- •»>
i hdiuUh,vif\\ ih^ehöwcHi^ wre^cofft^ pen-í'i'Ajt-voA/ pn» pť?/owj?í [£ ŕi cfispo^ooK, qfe&+iiksT&ti útCŕfrovizsc-t&tt ťrf&é*
p+o vyfoťř&u^t faypef-eZy ^áJit£<iA3L- jeti pť^ť*<w2£w^.
Algorjtmy TBL
(lnstancc-tíased Learning — učení založené na instancích)
Algoritmy IRI Jsou odvozeny z metody klasifikace pomoci nejbližšího souseda k-d. IBL se velmi podobá ŕ ŕ/ v tom. že laké ukládá a používá pouze vybrané instance ke generování předpovědi klasifikace. IBL patrí k inkrementálním melo dám s učitelem.
Pokusy ukázaly, že u nejbližšího souseda lze snížit požadavky na pamôť s malými ztrátami přesností klasifikace, ale tuto úsporu nelze předpovědět Velikost předpokládaných paměťových požadavků je polynomiální; úměrná velikosti cílových hraníc v instanéníni prošlo ni. Algoritmy nejbližšího souseda dále nezlepšují přesnost klasifikace s lim. jak přicházejí nové instance a tím jsou ignorovány neklej č problémy reálného sveta, napf. šum preto jsou takové algoritmy málo robust n i f odolné).
IR I. algoritmy jsou v podstatě tvořeny čtyřmi základními skupinami;
1.      IB1 nejjednodušší, ukládají všechny tréninkové instance a jsou proto velmi náročné na paměť.
2.      IB2 modifikovaný ID 1, jenž ukládá pou/o chybní určené tréninkové instance lna začátku ovšem nejsou určené žádné). Lisí se tedy ve fázi učeni. Pokud je nově předložený příklad klasifikován správně, je ihned zapomenut. Jsou znatelně sníženy požadavky na pamČť na úkor velmi Tiialólio Kiiiženi přesnosti klasifikace. \H2 je ale značné citlivý na šum, protože nesprávní klasifikované instance jsou především ty, jež jsou na rozhraní více možnosti (hlízko hraníc konceptů), dále výjimky a konečné data s ;nmem.
3. ÍB3 — obecně odolnosi vůči šumu rozhoduje o robustnosti metod učení v praxi, pro rozhodovací stromy byly vyvinuty metody větvení založené na statistických testech k tolerování zašumených dat. Podobné metody existují pro rozhodovací pravidla. IR1 je IBL rozšířený o významový test, který' indikuje a rozlisuje zašumčné instance. Předpokládá se, že již uložené instance jsou spolehlivými klasiríkátory před tim. než jsou použity pro následně klasifikační úlohy. Jeli piílomen sum. přesnost klasifikace se zlepšuje za současného sníženi požadavku na paměť.
V principu se používají dva prahy důvěry:
— práh pro akceptováni nebo
— práh pro odmítnutí.
Významový lest rozhoduje o tom, zda instance je přijatelná nebo zašuměná. Přijatelná je lehdy, když jeji přesnost klasifikace je statisticky významne" vetší nez její pozorovaná frekvence ve třídě. V opačném případě je instance vypušLena. Zašuměné instance mají nuilou přesnost klasifikace, protože jejich nejbližší sousedé v inštancii í m prostoru mohou mít jinou klasifikaci. Uvedená metoda je tolerantní vůči šumu. ale nedokáže rozlišit zašuměná data od výjimek — každá výjimka vypadá jako instance obsahující sum.
Rozdíl IB3 oproti IB2: n) Udržuje klasifikační záznamy všech uložených instancí, tj. poťcr správných a nesprávných pokusů o klasifikaci, b) Akceptovány pro budoucí klasifikace jsou jen instance s dohrým klasifikačním záznamem, c) Algoritmus odolný sumu ničí ty uložené instance, které se jeví jako zašuměné (Ij. ty, jejichž klasifikace je spalná po několika klasifikačních pokusech).
4, IB4 — je rozšírením IB3 v tom smyslu, že ne-předpokládá stejnou závažnost všedi atributů pro predikci. IB4 je- úspěšný lam. kde je instance popsána mnoha ali ibuty. Zatímco u rozhodovacích stromů jo význam atributu stanoven pomocí entropie (mfbrmaíníbd zisku), IBL využívají jinou strategii:
Závažnost atributu (jeho relevance) jo dána nastavením vííhy pro daný atribut, Při učeni jsou zaznamenány vySSi váhy atrihutíím, které se podileji na správne klasifikaci. Každý cílový koncept má unikátní množinu vah atributu. 1131 nepředpokládá vyčerpávající 8 nepřekrývající se koncepty. Pro jednu instanci uvažuje jednu, rádnou či vice cílových hodnot. Pro rozhodnutí, která / možnosti je správná, používá funkci Eitirttace (odhadu členství). Zá vaznější prcdikiory jsou zvýhodňovány, irelevantní zeslabovány. Každá váho atrihutu je aktualizovánu po každém pokusu predikce během fáze učení.
• Princip IBL: Tyto algoritmy se hodí k řešení úloh. kde zdrojem příkladů (instanci) je vnější prostředí. Algoritmus, pasivné přijímá instance vnějšího procesu. Každá instance je reprezentována množinou hodnot atributů. Instance, jež je popsána n atributy» je uložena v M-dimenzionÄlním ínstančnim prostoru. Atributy jsou doliiiov ány nad množinou numerických nebo symbolických hodnot. IBL může tolerovat chyběj id hodnoty atributu.
Jeden ü atributů, použitých pro popis instancí, je použit jako tzv, ď lovy atribut, ostatní jsou tzv. prediktory. Základní vlastností algoritmu je schopnost naučit se předpovídal hodnotu cílového atributu u instance, jejíž cílová hodnota chybí.
Množina všech instancí v instančním prostoru, které mají stejnou hodnotu cílového atributu, se nazývá třída (též kategorie). Tzv. ktwcepi\c cílový popis kategorie. IBLjsou předkládány sekvence tréninkových instancí a koncepty k naučeni pro každou hodnotu cílového íitrihiitii (koncepty jsou funkce, rozdělující instance do tři d I Citem je přesné ttrčit citové atributy*
•     I HL se skládá ze éíyř základních funkcí: normalizace, podobnost, predikce, aktualizace pamčLi.
*■ normalizace — normalizuječíselné hodnoty predikčních aLributů, Při předzpracování instancí se udržuji a aktualizuji celkové informace týkající se hodnot každého číselného atributu během tréninkového procesu. Tato informace se používá pro normalizaci, která upravuje velikost každú numericko hodnoty atributu. Pomocí normalizace se dosahuje tollOj že každý atribut má stejnou závažnost. K normal iíhľi lze napr. použít jednoduchý lineami vztah využívající nejnižší a nejvyšší hodnotu atribútu:
'         min
Y      - X~
mai        min
kde v(r je nová (normalizovaná) hodnota atributu, i je načtená hodnota {skutečná) atributu, Xmm je minimálni
bodnula atributu a AwriTyje maximální hodnota atributu.
pvdobnmt — lun kec podobnosti pracuje s částečným konceptem a upravenou instancí, Výsledkem je numericky vyjádřená podobnost nové instance s každí ni instancí v částečném konceptu. Jednoduchou funkcí muže napr. být inverze Euklidovy vzdálenosti dvou bodů v a v v inštancii ím prostoru {usymholických atrihutůje vzdálenost nulová pří identické shodě, jinak je rovna 1}:
Podobnost (jc,v) =
^ Vzdálenost_airihiitu (x.. vr)
V.
kde funkce Vzaálenost_£ttřibutů = {x~y$ pro numerické hodnoty it .r, * v, pro symbolické hodnoty. Chybili obé hodnoty, pak je výsledek l, chybí-lí \\ resp. x^ pak je výsledek max(xrQ, 1 - vj, resp. max(yrO, I -y^J. P v uvedeném vztahu je počet predikčních atributů.
predikce — vstupem jsou vypočtené hodnoty podobnosti a výstupem predikce hodnot cílovýcll atributů instancí. Jednoduchou funkcí predikce múze být napr. metoda nejbližšího souseda (pro symbolické i numerické hodnoty]. Výstupem jsou hodnoty cílových atributů instancí s nejvyšší podobností do částečného konceptu, Mají-li aspoň dvé instance shodnou maximální podobnost, může být proveden náhodný výber jedné t. nich [a ta bude prediko-vat cílovou hodnotu), další možností je použití t7v. většinového hlasováni, především pro symbolické hodnoty. Prsdpovězená hodnota je pak to, kutá se stane nejčastější mezi R-nejpravděpodohnéjšími tréninkovými instancemi.
*■ aktuatizacť poutati ■ - Částečný koncept je aktualizován poté, co byla vypočtena podobnost, resp. váha každé tréninkové instance Částečný koncept se skládá z množiny instanci a z přidružené informace ve v/l ahn k prospešnosti uložených instancí a atributů, které je popisují. Jo možné, že lato funkce bude pusky lov at Ualši užitečné informace (napi. parametry pro predikce). Nejjednodušší mnkci aklualizace je jednoduche ukládání vícch tréninkových instanci do částečného konceptu, Složitější funkci je napr, vypouštěni instancí, které se jeví jako zaSu-rnčnč, i konto pln