Kybernetika a umělá inteligence, cvičení 10/11
Program 1. seminární cvičení: základní typy klasifikátorů a jejich princip 2. počítačové cvičení: procvičení na problému rozpoznávání číslic
~ . . . body za aktivitu malé modré písmo: poznámky
KUI 10/11, R. Šára, CMP (p. 1/15)
Úkol k procvičení: OCR modul pro čtení registračních značek
→
↓ ↓
→
OCR
Laskavostí CMP a firem Camea a Eyedea.
• Cíl cvičení: jak udělat OCR? KUI 10/11, R. Šára, CMP (p. 2/15)
Problém učení a klasifikace • Objekty ω ∈ Ω
výřezy obrázku o velikosti 13 × 13 pixelů
• Třídy: mají identifikátory y ∈ Y • Příznaky: sloupcové vektory měření x ∈ X x0 x1 x2 x3 x4 x5 x6 x7 x8 x9
Y : číslice 0,1,. . . ,9 celý obsah výřezu obrázku po řádcích
– X . . . příznakový prostor zde vektorový prostor se vzdáleností
– Klasifikační funkce: zobrazení f : X → Y i i – Trénovací množina (x , y ) . . . vzory i i T = (x , y ), i = 0, 1, . . . , m}
• Klasifikace:
Určit identifikátor třídy f (x), je-li dáno měření x.
• Problém učení: Nalezení klasifikační funkce f na základě konečné trénovací množiny T tak, aby pravděpodobnost chyby klasifikace na neznámých datech byla minimální. • Věta: Pokud se klasifikační funkce f při učení nevybírá ze „složité třídyÿ, minimalizace chyby na T vede k dobrým výsledkům. Důkaz tvrzení i přesná definice pojmu „složitá třídaÿ jsou velmi obtížné. KUI 10/11, R. Šára, CMP (p. 3/15)
Klasifikace na základě etalonu 2D příznakový prostor minimum distance from etalons 1 0.8
• Je-li měření x bez šumu, pak každou třídu y ∈ Y mohu reprezentovat etalonem ey . • Pro klasifikaci objektu ω na základě příznaku x postačí zjistit, kterému etalonu se x rovná.
0.6 0.4 0.2 0 −0.2 −0.4 −0.6 −0.8 −1 −1
−0.5
0
0.5
1
• Kolem etalonu ey existuje oblast Ry , g.m.b., které jsou k ey blíže než k ostatním. • Hranice oblastí: rozdělující nadroviny (obecně nadplochy) • Tyto oblasti tvoří rozklad příznakového prostoru na konvexní množiny Ry , y ∈ Y. R je konvexní, když pro každé x1, x2 ∈ R platí: λ x1 + (1 − λ) x2 ∈ R pro λ ∈ h0, 1i. ~
• Potom klasifikátor lze realizovat též jako modifikovanou úlohu nejbližšího etalonu: 2
f (x) = arg min kx − ey k + oy
y∈Y
• Takový klasifikátor funguje i v případě, kdy měření x je zatíženo malým šumem. • Hranice oblasti Ry mohu posouvat konstantou oy . na úkor ostatních oblastí KUI 10/11, R. Šára, CMP (p. 4/15)
Komplikace: Příznakové vektory v T nejsou bez šumu Předpoklad: Ale přesto lze třídy zastoupené v trénovací množině oddělit nadrovinami v příznakovém prostoru. • Otázka: Jak tyto roviny najít? • Odpověď: Zvolíme vhodné etalony a tím problém převedeme na jednoduchý. První úvaha: Pokud je chyba měření popsatelná normálním rozdělením a všechna rozdělení mají stejný rozptyl σ, pak jsou nejlepšími etalony střední hodnoty
minimum distance from etalons 1 0.8 0.6 0.4 0.2 0
1 ey = µy = y |X | def
X
xyi
i∈X y
−0.2 −0.4 −0.6 −0.8
a rozdělující nadplochy jsou nadroviny kolmo půlící vzdálenosti mezi dvojicemi tříd.
−1 −1
−0.5
0
0.5
1
X y . . . indexy prvků trénovací množiny, které odpovídají třídě y • velmi efektivní reprezentace klasifikátoru • klasifikátor je jednoduchý není nebezpečí přeučení • pokud předpoklady neplatí, lze očekávat velkou chybu klasifikace KUI 10/11, R. Šára, CMP (p. 5/15)
Pokračování: Idea nejbližšího souseda z T Druhá úvaha: Všechny prvky trénovací množiny T se stanou etalony‘ . ’ • klasifikátor podle nejbližšího souseda z T 1−nearest neighbour classifier
minimum distance from etalons
1
1
0.8
0.8
0.6
0.6
0.4
0.4
0.2
0.2
0
0
−0.2
−0.2
−0.4
−0.4
−0.6
−0.6
−0.8
−0.8
−1 −1
−0.5
0
0.5
1
−1 −1
−0.5
0
0.5
1
• je snadno implementovatelný, poměrně dobrý pro velkou trénovací množinu asymptoticky platí: chyba klasifikace není horší než dvojnásobek chyby klasifikace optimálního klasifikátoru nutno pamatovat si celou T
• není efektivní • složitý nebezpečí přeučení KUI 10/11, R. Šára, CMP (p. 6/15)
Pokračování: Lineární klasifikátor Třetí úvaha: • Nejprve přepíšeme: > x + e f (x) = arg min kx − ey k + oy = arg min(x>x − 2 e> y y ey + oy ) = 2
y∈Y
y∈Y
1 > > > = arg min x x − 2 − (ey ey + oy ) = arg min x x − 2 (ey x + by ) = y∈Y y∈Y 2 1 > = arg max(e> x + b ) = arg max f (x). b = − (ey ey + oy ) y y y y y∈Y y∈Y 2
>
e> yx
• výsledek: lineární klasifikátor ⇔ etalonový klasifikátor • rozdělující nadplocha mezi třídami a a b je nadrovina daná fa(x) = fb(x): (ea − eb)>x + (ba − bb) = (ea − eb)>(x − xc) = 0
eb
Příznakový prostor je rozložen na konvexní množiny. ~
• Pokud bude existovat algoritmus pro nalezení parametrů rozdělujících nadploch ey , by z trénovací množiny, potom tento algoritmus najde ekvivalentní etalony a posuny oy . • Takový existuje: Perceptronový algoritmus. KUI 10/11, R. Šára, CMP (p. 7/15)
xc ea
Perceptronový algoritmus • začne s etalony ey = µy a iterativně posouvá rozdělující nadplochy tak dlouho, až jsou všechny prvky T klasifikovány správně naučený ze středních etalonů
naučený perceptronovým alg.
minimum distance from etalons
perceptron
1
1
0.8
0.8
0.6
0.6
0.4
0.4
0.2
0.2
−→
0
0
−0.2
−0.2
−0.4
−0.4
−0.6
−0.6
−0.8
−0.8
−1 −1
−0.5
0
0.5
1
−1 −1
−0.5
0
• jednoduchý • efektivní • omezení lineárního klasifikátoru: jedna třída = jedna konvexní oblast KUI 10/11, R. Šára, CMP (p. 8/15)
0.5
1
Učení lineárního klasifikátoru perceptronovým algoritmem
f (x) = arg max
e> yx
Hledáme soubor parametrů K = (ey , by ) | y ∈ Y klasifikátoru
y∈Y
+ by
který docílí nulovou chybu na trénovací množině T = (xi, y i), i = 0, 1, . . . , m} 1 ET (f ) = m
m X
j
j
1 y 6= f (x ) ,
j =1
( 1 s platí 1 (s) = 0 s neplatí ET (f ) ≥ 0
Předpoklad lineární separability: trénovací množinu T lze rozložit na konvexní oblasti Ry , které mají po částech lineární hranici a jsou takové, že vzory každé třídy y v T jsou obsaženy v právě jedné Ry .
Předpoklad problém převede na úlohu řešitelnosti soustavy nerovnic i > i e> x + b > e i i y y y j x + by j
pro všechna i = 1, 2, . . . , m a všechna y j 6= y i. KUI 10/11, R. Šára, CMP (p. 9/15)
(1)
Perceptronový algoritmus 1. Nastav ey := µy a by := 0 pro všechny y ∈ Y.
není nutné začít se středním etalonem µy
2. Mezi trénovacími vzory T = {(x1, y 1), . . . , (xm, y m)} nalezni (xt, y t) takový, že t
y 6= yˆ ,
kde
yˆ = arg max y∈Y
t e> yx
+ by .
(xt, y t) . . . libovolný chybně klasifikovaný vzor
3. Pokud takový vzor neexistuje, skonči. Parametry K = {(ey , by ) | y ∈ Y} určují klasifikátor s nulovou trénovací chybou. 4. Jinak, nechť yˆ je klasifikace xt pomocí aktuálního klasifikátoru. Adaptuj parametry klasifikátoru K takto eyt := eyt + xt , byt := byt + 1 , posil správnou třídu
eyˆ := eyˆ − xt , byˆ := byˆ − 1 . oslab chybnou třídu
5. Pokračuj krokem 2. Věta [Novikoff] Pokud jsou vzory v trénovací množině lineárně separabilní, tj. soustava nerovnic (1) má řešení, skončí perceptronový algoritmus v konečném počtu kroků. ~~ KUI 10/11, R. Šára, CMP (p. 10/15)
Nezávislé testování klasifikátoru Nezávislá testovací množina: množina vzorů, na které nebyly učeny žádné parametry například procedury pro normalizaci obrazu klasifikátoru (nebo procedury pro výpočet příznaků).
Chyba na nezávislé testovací množině je nevychýleným odhadem střední chyby klasifikátoru. Chyba na trénovací množině je často významně menší než chyba na nezávislé testovací množině.
KUI 10/11, R. Šára, CMP (p. 11/15)
Úkoly pro počítačové cvičení
Základní úkol 1. 2. 3. 4. 5. 6. 7.
Seznámit se s podpůrným software. Prohlédnout si dodaná data v trénovací a testovací množině. Vyzkoušet klasifikátor na základě etalonů střední hodnoty. Implementovat vlastní klasifikátor podle nejbližšího souseda. Zařadit ho do hlavního skriptu. Vyzkoušet lineární klasifikátor, naučený perceptronovým algoritmem. Srovnat všechny tři klasifikátory podle chyby na trénovací a testovací množině. 8. Výsledky předložit k ohodnocení.
Úkoly pro aktivní ~ transformace problému klasifikace etalonovým klasifikátorem na klasifikaci obecným lineárním klasifikátorem (na cvičení), ~ vlastní implementace perceptronového algoritmu (na cvičení), ~ důkaz konvexity rozkladu příznakového prostoru množinou etalonů (str. 4) (domácí úkol), ~ důkaz Novikoffovy věty (str. 10) (domácí úkol). KUI 10/11, R. Šára, CMP (p. 12/15)
Vyšší Level. . .
KUI 10/11, R. Šára, CMP (p. 13/15)
Literatura
[1] C. M. Bishop. Pattern Recognition and Machine Learning, chapter 4.1 Linear Models for Classification, Discriminant Functions, strany 179–196. Springer, 2006. [2] R. O. Duda, P. E. Hart, a D. G. Stork. Pattern Classification, chapter 5. Linear Discriminant Functions, strany 215–235. Wiley, 2nd edition, 2001. [3] M. I. Schlesinger a V. Hlaváč. Deset přednášek z teorie statistického a strukturního rozpoznávání, chapter 5. Lineární diskriminační funkce, strany 164–169. Vydavatelství ČVUT, Praha, 1999.
KUI 10/11, R. Šára, CMP (p. 14/15)
Konec
