Úloha - rozpoznávání číslic Vojtěch Franc, Tomáš Pajdla a Tomáš Svoboda http://cmp.felk.cvut.cz 27. listopadu 2006
Abstrakt Podpůrný text pro cvičení předmětu X33KUI. Vysvětluje tři způsoby rozpoznávání obrazů číslic. Ukáže, že hlubší teorie má skutečný smysl, protože navrhnout algoritmus, který funguje lépe než jednoduchý, na který lze do jisté míry přijít „selským rozumemÿ.
1
Zadání
Úkolem je navrhnout klasifikátor jehož vstupem jsou šedotónové obrázky 13 × 13 a výstupem čísla 0, 1, . . . , 9. K dispozici je trénovací množina, která obsahuje příklady vstupních obrázků a jejich správnou klasifikaci. Navržený klasifikátor má minimalizovat pravděpodobnost chybné klasifikace. Chyba klasifikátoru bude ověřena na testovacích datech, která nejsou při návrhu klasifikátoru k dispozici. Druhým důležitým kritériem je efektivita klasifikátor, tedy rychlost klasifikace a velikost reprezentace tříd.
2
Teoretická část
Značení: Každý vstupní obrázek je reprezentován sloupcovým vektorem x ∈ Rn jehož složky obsahují jasové hodnoty pixelů. Dimenze vektoru x je rovna počtu pixelů ve vstupním obrázku, tj. n = 13 · 13 = 169. Výstup klasifikátoru (neboli třída obrázku) bude značena proměnnou y, která nabývá hodnot z konečné množiny Y = {0, 1, . . . , 9}. Klasifikátor můžeme vidět jako zobrazení f : Rn → Y. K dispozici je trénovací množina {(x1 , y 1 ), . . . , (xm , y m )}, která obsahuje m vzorů vstupních obrázků xi a jejich správnou klasifikací y i . 1
0 1 2 3 4 5 6 7 8 9 Obrázek 1: Obrazy číslic o rozměru 13 × 13 pixelů. Zvětšeno pro lepší viditelnost. Pod obrazy jejich vektorová reprezentace, to jsou x.
1−nearest neighbour classifier
1−nearest neighbour classifier
1.5
1.6 1.4
1
1.2 1
0.5 0.8 0.6 0 0.4 0.2
−0.5
0 −1 −1
−0.5
0
0.5
1
−0.2 −1.5
−1
−0.5
0
Obrázek 2: Příklady klasifikace podle nejbližšího souseda.
2
0.5
1
2.1
Klasifikátor podle nejbližšího souseda
Klasifikátor podle nejbližšího souseda klasifikuje vstupní obrázek x do stejné třídy f (x) jakou má nejbližší vzor z trénovací množiny, tj. f (x) = y j
j = argmin kx − xi k ,
kde
(1)
i∈{1,...,m}
Výhodou klasifikátoru (1) je jeho jednoduchost a relativně nízká chyba klasifikace. Velkou nevýhodou je paměťová náročnost (pamatuje si celou trénovací množinu) a dlouhá doba klasifikace úměrná počtu trénovacích vzorů a dimenzi obrázků.
2.2
Reprezentace tříd pomocí etalonu
Klasifikátor (1) lze urychlit pokud každou třídu y ∈ Y reprezentujeme pouze jedním vektorem, tzv. etalonem µy ∈ Rn . Celý klasifikátor je tedy určen množinou |Y| etalonů {µy ∈ Rn | y ∈ Y}. Vstupní obrázek x se pak klasifikuje do třídy f (x) podle toho, ke kterému etalonu je nejblíže, tj. f (x) = argmin kx − µy k .
(2)
y∈Y
Nejednodušší způsob, jak určit etalony, je spočítat průměrné hodnoty vstupních vzorů v jednotlivých třídách, tj. µy =
1 X i x , |Iy | i∈I
y∈Y,
(3)
y
kde Iy = {i | i ∈ {1, . . . , m} ∧ y j = y} značí množinu indexů trénovacích vzorů patřících do třídy y. Uvedený způsob výpočtu etalonů zajišťuje, že etalony reprezentují trénovací vzory s nejmenší sumou kvadratických odchylek, t.j. že platí X kxi − µk2 , ∀y ∈ Y . µy = argmin µ∈Rn
i∈Iy
Klasifikátor (2) používající etalony určené podle (3) je rychlý, ale má vysokou chybu klasifikace, protože použitá reprezentace tříd (resp. předpokládaný statistický model) nepopisuje trénovací data s dostatečnou přesností.
2.3
Učení klasifikátoru pomocí perceptronu
Lineární klasifikátor reprezentuje každou třídu y ∈ Y pomocí diskriminační funkce fy (x) = xT wy + by , která je lineární vzhledem k parametrům wy ∈ Rn a by ∈ R. 3
minimum distance from etalons 1.5
1
0.5
0
−0.5
−1 −1
−0.5
0
0.5
1
Obrázek 3: Klasifikace minimální vzdálenosti od etalonů. Povšimněte si, že klasifikátor klasifikuje některé příznaky (vektory) chybně. A to přesto, že data jsou lineárně separabilní. Srovnejte se klasifikací pomocí perceptronu, viz Obrázek 4. Vstupní obrázek x je klasifikován do třídy, jejíž diskriminační funkce je maximální, tj. (4) f (x) = argmax fy (x) = argmax xT wy + by . y∈Y
y∈Y
Vidime, že každý klasifikátor (2) lze ekvivalentně vyjádřit ve tvaru (4) následujícím způsobem f (x) = argmin kx − µy k2 y∈Y = argmin kxk2 − 2xT µy + kµy k2 y∈Y T 2 = argmax 2x µy − kµy k y∈Y T = argmax x wy + by y∈Y
z čehož vyplývá, že parametry lineárního klasifikátoru můžeme získat z etalonů wy = 2µy
a by = −kµy k2 .
Dále si ukážeme jiný způsob výpočtu parametrů klasifikátoru, který v mnoha praktických případech funguje lépe než metoda používající etalony. Cílem bude vybrat 4
perceptron 1.5
1 0.8
1
0.6 0.4
0.5 0.2 0 0 −0.2 −0.4
−0.5
−0.6 −1 −1
−0.5
0
0.5
1
−0.8 −1
−0.5
0
0.5
1
Obrázek 4: Vlevo: Lineárně separabilní data, bezchybná klasifikace pomocí perceptronu. Srovnej s chybnou klasifikací pomocí etalonů na stejných datech, viz Obrázek 3. Vpravo: Lineárně neseparabilní data. parametry lineárního klasifikátoru (4) tak, aby trénovací chyba m
1 X i Etrn (f ) = [[y = 6 f (xi )]] m i=1 byla minimální. V definici trénovací chyby jsme použili výraz [[y i 6= f (xi )]], který je roven 1, pokud platí y i 6= f (xi ) a v opačném případě je roven 0. To znamená, že trénovací chyba Etrn (f ) je rovena poměru počtu chybně klasifikovaných vzorů z trénovací množiny ku počtu všech vzorů v trénovací množině. Budeme předpokládat, že existují takové parametry lineárního klasifikátoru při nichž je trénovací chyba nulová. V tomto případě se trénovací množina označuje jako lineárně separabilní. Poznamenejme však, že tento předpoklad nemusí být v praxi vždy splněn a pokud tato situace nastane, je nutné použít jiných (složitějších) přístupů. Máme-li k dispozici lineárně separabilní data, lze nalézt lineární klasifikátor s nulovou chybou. To znamená, že je úloha minimalizace trénovací chyby shodná s úlohou hledání takových parametrů, při nichž je každý vzor z trénovací množiny klasifikován správně, tj. platí [[y i 6= f (xi )]] = 0 ,
∀i ∈ {1, . . . , m} , 5
a to nastane právě tehdy když i
i
i T
y = argmax fy (x ) = argmax (x ) wy + by , y∈Y
∀i ∈ {1, . . . , m} .
(5)
y∈Y
Dostali jsme tedy soustavu vztahů, z nichž chceme vyřešit neznámé parametry, {(wy , by ) ∈ Rn+1 | y ∈ Y}. Dále převedeme řešení (5) na ekvivalentní problém řešení soustavy lineárních nerovnic, pro nějž existují metody výpočtu. Uvažujme rovnici y i = argmax fy (xi ) y∈Y
pro libovolný vzor i ∈ {1, . . . , m}. Tato rovnice je splněna právě tehdy, když je hodnota diskriminační funkce fyi (xi ) pro správné y i větší než hodnoty diskriminační funkce fy (xi ) pro všechny ostatní y ∈ Y \ y i , tj. když platí (xi )T wyi + byi > (xi )T wy + by pro všechny y ∈ Y \y i . Pokud posledně uvedené nerovnice zapíšeme pro všechny trénovací vzory, dostaneme soustavu lineárních nerovnic (xi )T wyi + byi > (xi )T wy + by ,
∀i ∈ {1, . . . , m}, ∀y ∈ Y \ y i .
(6)
Nalezneme-li řešení soustavy (6) máme současně vyřešen i původní problém (5), tj. získali jsme parametry lineárního klasifikátoru s nulovou trénovací chybou. Soustava (6) obsahuje M = m · (|Y| − 1) lineárních nerovnic jejichž řešení lze nalézt efektivně pomocí perceptronového algoritmu. Pro zjednoduseni dalsiho vykladu zapiseme soustavu (6) v jednodussim, ale zcela ekvivalentnim tvaru (z i,y )T w > 0 ,
∀i ∈ {1, . . . , m} , y ∈ Y \ y i .
(7)
Vektor w ∈ R|Y|·(n+1) obsahuje vsechny hledane parametry {(wy , by ) ∈ Rn+1 | y ∈ Y} usporadane zasebou, tj. w = [w1 ; b1 ; w2 ; b2 ; . . . ; w|Y| ; b|Y| ]. Souradnice vektoru w tvori |Y| skupin po n + 1 souradnicich. Necht jsou souradnice vektoru z i,y ∈ R|Y|·(n+1) rozdeleny do skupin stejnym zpusobem. Potom vektor z i,y konstruujeme tak, ze y i -ta skupina souradnic obsahuje vektor [xi ; 1], y-ta skupina vektor [−xi ; −1] a zbyle souradnice jsou nulove. Perceptronový algoritmus pro řešení soustavy (7) má následující tvar: Algorithm 1: Perceptronový algoritmus 1. Nastav w := 0. 6
2. Mezi vstupními vektory {z 1 , . . . , z M } nalezni libovolný vektor z t , který splňuje (z t )T w ≤ 0 . Pokud takový vektor neexistuje skonči, neb w je řešením soustavy (7). 3. Použij vektor z t k adaptaci řešení w tak, že w := w + z t . Pokračuj krokem 2. Novikoffova věta: Za předpokladu, že data v trénovací množině jsou lineárně separabilní, tj. soustava (6) respektive (7) má řešení, skončí perceptronový algoritmus v konečném počtu kroků. Důkaz zabírající jen jednu stránku lze nalézt v [1]. Pokud se vrátíme k původní reprezentaci dat, tj. budeme řešit soustavu (6), lze perceptronový algoritmus zapsat ve tvaru: Algorithm 2: Perceptronový algoritmus 1. Nastav wy := 0 a by = 0 pro všechny y ∈ Y. 2. Mezi trénovacími vzory {(x1 , y 1 ), . . . , (xm , y m )} najdi libovolný špatně klasifikovaný vzor, tj. nalezni (xt , y t ) tak, že y t 6= yˆ , kde yˆ = argmax (xt )T wy + by . y∈Y
Pokud takový vzor neexistuje skonči neb parametry {(wy , by ) ∈ Rn+1 | y ∈ Y} určují klasifikátor s nulovou trénovací chybou. 3. Nechť (xt , y t ) je špatně klasifikovaný vzor a yˆ je klasifikace xt pomocí aktuálního klasifikátoru. Adaptuj parametry klasifikátoru tak, že wyt by t wyˆ byˆ
:= := := :=
w y t + xt , by t + 1 , wyˆ − xt , byˆ − 1 .
Pokračuj krokem 2.
Reference [1] Michail I. Schlesinger and Václav Hlaváč. Deset přednášek z teorie statistického a strukturního rozpoznávání. ČVUT, Prague, Czech Republic, 1999. 7
Obrázek 5: Příklad automatické lokalizace textu v obrazech. Více informací na http: //cmp.felk.cvut.cz/~zimmerk/lpd/index.html
8
Obrázek 6: Příklad komerční aplikace na rozpoznávání registračních značek ve videu. Demostrační videa lze nalézt na adrese http://cmp.felk.cvut.cz/cmp/courses/ X33KUI/Videos/RP_recognition/
9
