Warning
This page is located in archive.

Poznámka 1. úloze - bayesovské klasifikaci písmen

Autor textu: Eduard Bakštein
Úprava: Tibor Strašrybka

Stručné shrnutí

Vzhledem k velkému počtu možných obrázků mnoho intenzit v trénovací množině chybí a v tabulce odhadnutých pravděpodobností jejich výskytu pro danou třídu budou tedy nuly. Protože se celková podmíněná pravděpodobnost počítá jako produkt, i jediné chybějící pozorování způsobí nulový celkový výsledek, a tedy špatnou klasifikaci. Možným řešením je kvantování jasových hodnot do menšího počtu kroků. Ani tak ale nebudou velmi pravděpodobně zahrnuty všechny možnosti. Dalším krokem tedy může být regularizace celé odhadnuté pravděpodobnostní tabulky přičtení malé konstanty, která problém nulových pravděpodobností odstraní.

Vysvětlení

Na cvičení jsme si řekli, že během procesu učení Bayesovského klasifikátoru v úloze klasifikace písmen odhadujeme z trénovacích dat pravděpodobnostní model $P(\overline{x}|s)$, reprezentovaný tabulkou pravděpodobností výskytu hodnot jednotlivých příznaků $x_i, i \in \langle1, 100\rangle$ pro různé třídy $s \in \{A, B, \ldots, Z \}$. Celkový počet odhadovaných pravděpodobností $P(x_i|s)$ je tak roven počtu příznaků (pixelů) krát počet tříd (písmen). Každá pravděpodobnost $P(x_i|s)$ je sama o sobě diskrétním rozdělením (tabulkou, výčtem) pravděpodobnosti $P(x_i = I_j|s = S_k)$, kde $I_j$ je intenzita daného pixelu z oboru možných intenzit (ve výchozím uspořádání 0 až 255), a $S_k$ je některá ze tříd (A až Z), jinými slovy pravděpodobnost pozorování hodnoty $I_j$ u příznaku $x_i$ za předpokladu, že pochází z třídy $S_k$. Celá pravděpodobnostní tabulka, která musí být vypočtena, tedy dosahuje počtu prvků rovnému počtu příznaků krát počtu tříd krát počtu možných intenzit, ve výchozím nastavení tedy:

$$N_{\text{pravdepodobnosti}} = N_{\text{priznaku}} \cdot N_{\text{trid}} \cdot N_{\text{intenzit}} = 100 \cdot 23 \cdot 256 = 588\:800\quad(1)$$

I při zjednodušení úlohy snížením počtu intenzit na např. 5 bude celkový počet odhadovaných pravděpodobností roven 11 500 (4 600 v případě 2 stupňů intenzity). To je tabulka velká a obtížně vyplnitelná, a to i uvážíme-li v praxi velmi obstojný počet 1 000 trénovacích příkladů (100 000 hodnot intenzity). Je zřejmé, že pravděpodobnostní tabulka $P(\overline{x}|s)$ bude obsahovat řadu chybějících pozorování (a tedy nulových hodnot). Uvážíme-li na cvičení uvedený postup výpočtu pravděpodobnosti $P(\overline{x}|s)$, (pozorování $\overline{x}$ pochází ze třídy $s$), používaný pro klasifikaci1):

$$P(\overline{x}|s) = \prod\limits_{i=1}^{100}P(x_i|s)\quad(2)$$

je zřejmé, že pro většinu možných klasifikovaných pozorování bude alespoň některá z dílčích pravděpodobností $P(x_i|s)$ nulová. Nule bude tedy roven i výsledek $P(\overline{x}|s)$ pro všechny nebo alespoň většinu tříd, a to i v případě, kdy budou ostatní pravděpodobnosti nebývale velké2). Aby se předešlo podobné situaci, kterou lze popsat jako vliv rušení, zavádí se následující korekce, která přičítá ke každé násobené pravděpodobnosti drobný korekční příspěvek $\epsilon$:

$$P(\overline{x}|s) = \prod\limits_{i=1}^{100}[P(x_i|s)+\epsilon]\quad(3)$$

I přes vychýlení výsledné pravděpodobnosti tímto příspěvkem způsobené by měl být vliv na výsledek klasifikace minimální, přičemž problém s nulovými hodnotami pravděpodobností byl eliminován.
Pozorování pak klasifikujeme do takové třídy (uděláme rozhodnutí $d$), pro kterou platí:

$$d = \arg \max\limits_{s}P(\overline{x},s) = \arg \max\limits_{s}P(s) \cdot \prod\limits_{i=1}^{100}[P(x_i|s)+\epsilon]\quad(4)$$

1)
Platí pouze za předpokladu nezávislosti pozorování. Právě v případě, kdy se závislost předpokládá, ale ignorujeme ji pro omezení kombinatorické exploze, mluvíme o naivní Bayesovské klasifikaci.
2)
Uvažujme např. obrázek dokonale jasného a ostrého písmene A, v jehož levém horním rohu je černý bod. Je velmi nepravděpodobné, že by některý z trénovacích příkladů pro písmeno A obsahoval černý bod na tomto místě a jeho pravděpodobnost tedy bude nulová. Nulová pak vyjde i celková pravděpodobnost, že předložený příklad pochází ze třídy a, přestože podle ostatních příznaků se o zcela jasné A jedná.

courses/a3b33kui/cviceni/03.txt · Last modified: 2017/03/01 01:52 by xnovakd1