KUI 10/11, R. Šára, CMP (p. 1/15)
Kybernetika a umělá inteligence, cvičení 10/11
Program
1. seminární cvičení: základní typy klasifikátorů a jejich princip2. 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. 2/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. 3/15)
Problém učení a klasifikace
• Objekty ω ∈ Ω výřezy obrázku o velikosti 13× 13 pixelů
• Třídy: mají identifikátory y ∈ Y Y : číslice 0,1,. . . ,9
• Příznaky: sloupcové vektory měření x ∈ X celý obsah výřezu obrázku po řádcích
x0 x1 x2 x3 x4 x5 x6 x7 x8 x9 – X . . . příznakový prostorzde vektorový prostor se vzdáleností
– Klasifikační funkce: zobrazení f : X → Y
– Trénovací množina (xi, yi) . . . vzoryT =
(xi, yi), 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žinyT 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ÿ, minimalizacechyby 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. 4/15)
Klasifikace na základě etalonu
• Je-li měření x bez šumu, pak každou třídu y ∈ Ymohu reprezentovat etalonem ey.
• Pro klasifikaci objektu ω na základě příznaku xpostačí zjistit, kterému etalonu se x rovná.
2D příznakový prostor
−1 −0.5 0 0.5 1−1
−0.8
−0.6
−0.4
−0.2
0
0.2
0.4
0.6
0.8
1minimum distance from etalons
• 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 λ ∈ 〈0, 1〉. ~
• Potom klasifikátor lze realizovat též jako modifikovanou úlohu nejbližšího etalonu:
f (x) = arg miny∈Y
(‖x− ey‖2 + oy
)• 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. 5/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 nadrovinamiv 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íma všechna rozdělení mají stejný rozptyl σ, pak jsounejlepšími etalony střední hodnoty
eydef= µy =
1|X y|
∑i∈X y
xyi
a rozdělující nadplochy jsou nadroviny kolmo půlící vzdá-lenosti mezi dvojicemi tříd.
−1 −0.5 0 0.5 1−1
−0.8
−0.6
−0.4
−0.2
0
0.2
0.4
0.6
0.8
1minimum distance from etalons
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. 6/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 −0.5 0 0.5 1−1
−0.8
−0.6
−0.4
−0.2
0
0.2
0.4
0.6
0.8
11−nearest neighbour classifier
−1 −0.5 0 0.5 1−1
−0.8
−0.6
−0.4
−0.2
0
0.2
0.4
0.6
0.8
1minimum distance from etalons
• 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
• není efektivní nutno pamatovat si celou T• složitý nebezpečí přeučení
KUI 10/11, R. Šára, CMP (p. 7/15)
Pokračování: Lineární klasifikátor
Třetí úvaha:
• Nejprve přepíšeme:
f (x) = arg miny∈Y
(‖x− ey‖2 + oy
)= arg min
y∈Y(x>x− 2 e>y x + e>y ey + oy) =
= arg miny∈Y
(x>x− 2
(e>y x−
12(e>y ey + oy)
))= arg min
y∈Y
(x>x− 2 (e>y x + by)
)=
= argmaxy∈Y(e>y x + by) = argmax
y∈Yfy(x). by = −
12(e>y ey + oy)
• 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) = 0Příznakový prostor je rozložen na konvexní množiny. ~
• Pokud bude existovat algoritmus pro nalezení parametrů rozdělujícíchnadploch ey, by z trénovací množiny, potom tento algoritmus najdeekvivalentní etalony a posuny oy.
• Takový existuje: Perceptronový algoritmus.
eb
ea
xc
KUI 10/11, R. Šára, CMP (p. 8/15)
Perceptronový algoritmus
• začne s etalony ey = µy a iterativně posouvá rozdělující nadplochy tak dlouho, až jsouvšechny prvky T klasifikovány správně
naučený ze středních etalonů naučený perceptronovým alg.
−1 −0.5 0 0.5 1−1
−0.8
−0.6
−0.4
−0.2
0
0.2
0.4
0.6
0.8
1minimum distance from etalons
−→
−1 −0.5 0 0.5 1−1
−0.8
−0.6
−0.4
−0.2
0
0.2
0.4
0.6
0.8
1perceptron
• jednoduchý• efektivní• omezení lineárního klasifikátoru: jedna třída = jedna konvexní oblast
KUI 10/11, R. Šára, CMP (p. 9/15)
Učení lineárního klasifikátoru perceptronovým algoritmem
Hledáme soubor parametrů K =(ey, by) | y ∈ Y
klasifikátoru
f (x) = argmaxy∈Y
(e>y x + by
)který docílí nulovou chybu na trénovací množině T =
(xi, yi), i = 0, 1, . . . ,m
ET (f ) =1m
m∑j=1
111(yj 6= f (xj)
), 111(s) =
1 s platí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
e>yixi + byi > e>yjxi + byj (1)
pro všechna i = 1, 2, . . . ,m a všechna yj 6= yi.
KUI 10/11, R. Šára, CMP (p. 10/15)
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, y1), . . . , (xm, ym) nalezni (xt, yt) takový, že
yt 6= y , kde y = argmaxy∈Y
(e>y x
t + by
).
(xt, yt) . . . 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 parametryklasifikátoru K takto
eyt := eyt + xt , ey := ey − xt ,byt := byt + 1 , by := by − 1 .posil správnou třídu 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. 11/15)
Nezávislé testování klasifikátoru
Nezávislá testovací množina: množina vzorů, na které nebyly učeny žádné parametryklasifikátoru (nebo procedury pro výpočet příznaků). například procedury pro normalizaci obrazu
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. 12/15)
Úkoly pro počítačové cvičení
Základní úkol
1. Seznámit se s podpůrným software.2. Prohlédnout si dodaná data v trénovací a testovací množině.3. Vyzkoušet klasifikátor na základě etalonů střední hodnoty.4. Implementovat vlastní klasifikátor podle nejbližšího souseda.5. Zařadit ho do hlavního skriptu.6. Vyzkoušet lineární klasifikátor, naučený perceptronovým algoritmem.7. 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 klasifikaciobecný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. 13/15)
Vyšší Level. . .
KUI 10/11, R. Šára, CMP (p. 14/15)
Literatura
[1] C. M. Bishop. Pattern Recognition and Machine Learning, chapter 4.1 Linear Models forClassification, Discriminant Functions, strany 179–196. Springer, 2006.
[2] R. O. Duda, P. E. Hart, a D. G. Stork. Pattern Classification, chapter 5. LinearDiscriminant 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íhorozpoznávání, chapter 5. Lineární diskriminační funkce, strany 164–169. VydavatelstvíČVUT, Praha, 1999.
Konec
