Search
Při práci na klasifikátorech (především u naivního bayesovského klasifikátoru) můžete narazit na různé typy numerických problémů. Zde jsou uvedeny cesty, kterými je můžete zkusit vyřešit. Byly představeny už na přednášce, zde jsou uvedeny jako reference.
Při odhadu pravděpodobností $P(x[i]|s)$ z trénovacích dat se snadno stane, že některé z těchto pravděpodobností budou nulové. Např. při odhadu $P(x[0]=255|s=1)$ se v trénovacích datech nevyskytne žádný obrázek číslice “1”, který by v prvním pixelu ($x[0]$) měl bílou barvu (odstín 255). Když pak budeme chtít klasifikovat nový obrázek $x$ číslice “1”, pro který bude platit $x[0]=255$, vyjde nám $P(s=1|x) = 0$, a obrázek bude zaklasifikován jako jiná číslice (jejíž alespoň 1 trénovací obrázek měl první pixel bílý).
Může se dokonce stát, že v žádném trénovacím obrázku nezávisle na číslici se nevyskytne $x[0]=255$. Při klasifikaci nového obrázku $x$ pak vyjdou všechny pravděpodobnosti $P(s=0|x) = P(s=1|x) = \ldots = P(s=9|x) = 0$ a my nebudeme mít podle čeho rozhodnout, o jakou číslici se jedná.
Co s tím?
Jedním ze způsobů řešení tohoto problému je Laplacova korekce (viz přednáška). Např. pravděpodobnost $P(x[0]=255|s=1)$ se odhadne jako $$P(x[0]=255|s=1) = \frac{N(x[0]=255, s=1)}{N(s=1)},$$ tj. jako podíl počtu trénovacích obrázků číslice 1, které mají bílý první pixel, ku celkovému počtu trénovacích obrázků číslice 1. Pokud žádný trénovací obrázek číslice 1 nemá první pixel bílý, je čitatel zlomku i celá pravděpodobnost rovna 0.
Laplacova korekce spočívá v tom, že budeme předstírat, že kromě skutečných trénovacích obrázků obsahují trénovací data ještě $k$ obrázků pro každou úroveň šedi, tedy $k$ obrázků číslice 1 s $x[0]=0$, $k$ obrázků číslice 1 s $x[0]=1$ až $k$ obrázků číslice 1 s $x[0]=255$. Odhad pravděpodobnosti se pak změní na $$P(x[0]=255|s=1) = \frac{N(x[0]=255, s=1) + k}{N(s=1) + 255k}.$$ V našem příkladu by to znamenalo, že pokud máme 100 trénovacích obrázků číslice 1, $k=1$ a obrázek s $x[0]=255$ v trénovacích datech vůbec nebude, odhad pravděpodobnosti se z 0 změní na $$P(x[0]=255|s=1) = \frac{N(x[0]=255, s=1) + k}{N(s=1) + 255k} = \frac{0 + 1}{100+255} = \frac{1}{355}.$$
Dalším způsobem, jak snížit pravděpodobnost, že se v trénovacích datech neobjeví žádný obrázek s nějakou úrovní šedi nějakého pixelu, je snížit počet úrovní šedi, které obrázek používá. V extrémním případě bychom počet odstínů mohli zredukovat na 2, tj. namapovat odstíny 0-127 na hodnotu 0 a odstíny 128-255 na hodnotu 1. Vhodnější ale může být kompromis, tj. použití např. 16 odstínů šedi, tj. namapovat odstíny 0-15 na hodnotu 0, odstíny 16-31 na hodnotu 1, atd. Implementace je jednoduchá, lze využít celočíselné dělení.
Pamatujte ale na 2 věci:
Naivní bayesovský klasifikátor rozhoduje o třídě tak, že pro klasifikovaný obrázek $x$ vypočte $P(s|x)$ pro všechny třídy $s$ a obrázek zaklasifikuje do třídy, pro kterou je $P(s|x)$ největší. Výraz $$P(s|x) = \frac{P(x|s)P(s)}{P(x)}$$ lze zjednodušit, když si uvědomíme, že pro jeden konkrétní obrázek $x$ je $P(x)$ stejné pro všechny třídy. Jmenovatel tedy můžeme ignorovat a stačí vědět, že $$P(s|x) \propto P(x|s)P(s),$$ kde symbol $\propto$ znamená, že výraz na levé straně je úměrný výrazu na pravé straně. (Pokud trénovací data obsahují stejný počet příkladů všech tříd, tj. jsou-li všechny třídy stejně pravděpodobné, lze dokonce psát $P(s|x) \propto P(x|s)$. Obecně to ale neplatí.) Díky podmíněné nezávislosti složek vektoru $x$ při dané třídě $s$ můžeme dále psát, že $$P(s|x) \propto P(x|s)P(s) = P(s) \cdot P(x[0]|s) \cdot P(x[1]|s) \cdot \ldots \cdot P(x[n]|s).$$
A tady narazíme na další problém - násobení mnoha pravděpodobností. I když zabráníme tomu, aby některé z $P(x[i]|s)$ byly nulové (viz výše), ve výpočtu budeme násobit tolik pravděpodobností, že nám brzy začne vycházet tak malé číslo, které nedokážeme v počítači reprezentovat, a stane se z něj 0.
Naštěstí nám nejde ani tak o přesný výpočet pravděpodobností $P(s|x)$ jako spíš o zjištění, která z těchto pravděpodobností je největší. Využijeme proto malý trik: použijeme logaritmy. Protože je $\log(.)$ monotónní funkce, $P(s|x)$ bude nabývat maxima pro stejnou třídu jako $\log P(s|x)$. Můžeme tedy psát, že $$\arg\max_s P(s|x) =$$ $$= \arg\max_s \log\left(P(s|x)\right)=$$ $$= \arg\max_s \log\left(P(s) \cdot P(x[0]|s) \cdot P(x[1]|s) \cdot \ldots \cdot P(x[n]|s)\right)=$$ $$= \arg\max_s \log\left(P(s)\right) + \log\left(P(x[0]|s)\right) + \log\left(P(x[1]|s)\right) + \ldots + \log\left(P(x[n]|s)\right)$$
Sčítání mnoha záporných čísel by už problém být neměl. I zde bychom ale měli zajistit, že žádná z pravděpodobností nebude 0, protože $\log(0) = -\infty$.