====== Jak vyřešit numerické potíže? ======
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.

===== Řídkost trénovacích dat =====
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?

==== Laplacova korekce ====
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}.$$

==== Snížení počtu úrovní jasu obrázku ====
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:
  * Aplikujete-li tuto transformaci při odhadu pravděpodobností na trénovací data, nezapomeňte stejnou transformaci aplikovat také na testovací obrázky, které chcete klasifikovat.
  * Tato metoda dokáže velmi snížit pravděpodobnost toho, že by v trénovacích datech chyběly nějaké případy, ale nevyřeší problém zcela. Je vhodné ji kombinovat s předchozí metodou (Laplacova korekce).

===== Násobení mnoha pravděpodobností =====
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$.