\subsection{Bajeso klasifikatorius}
Bajeso klasifikatoriaus vardas kil�s i� Bajeso teoremos, kuri nurodo tok� s�ry�� tarp s�lygini� tikimybi�:
\begin{equation}
    P(Y|X) = \frac{P(X|Y)\, P(Y)}{P(X)}. \label{eq:Bajeso}
\end{equation}
Tikimybi� teorijoje $X$ ir $Y$ yra bet kokie �vykiai. Ta�iau klasifikavimo atveju
atsiranda tam tikra asimetrija tarp $X$ ir $Y$, nes �ia bet kokia $X$ realizacija laikoma duomenimis,
o $Y$ - klase. D�l �ios asimetrijos naudojamos tokios s�vokos:
\begin{itemize}
\item $P(Y)$ apriorin� (�inoma prie� bandym�) klas�s $Y$ tikimyb�.
\item $P(Y|X)$ s�lygin� klas�s $Y$ tikimyb�, kai �inomi duomenys $X$.
\item $P(X|Y)$ s�lygin� duomen� $X$ tikimyb�, kai �inoma, kad jie yra klas�s $Y$. �i tikimyb� vadinama {\em tik�tinumu}.
\item $P(X)$ apriorin� duomen�  $X$ tikimyb�.
\end{itemize}
Klasifikuojant $P(X)$ tikimyb� vaidina normuojan�io daliklio vaidmen� ir ne�takoja klasifikavimo rezultat�.
Susipa�insime su Bajeso klasifikatoriumi pritaikydami j� atpa�inti MNIST duomen� baz�s ra�ytinius skaitmenis.
$X$ duomenimis laikysime skaitmen� $28\times28$ binarizuotus vaizdus.
Kadangi pradiniai MNIST vaizdai sudaryti i� pilkumo lygmen� reik�mi�, reikia apibr��ti
binarizacijos slenkst�. Mes paimsime trivial� slenkst� $treshold=127.5$, t.y.
laikysime, kad bibarizuoto vaizdo reik�m� kokioje nors $28\times28$ matricos pozicijoje lygi $0$,
jei pilkumo lygmuo toje pozicijoje nevir�ija $127.5$ ir lygi $1$ prie�ingu atveju.
$Y$ elementai sudaryti i� de�imties skaitmen�, t.y. galimos $Y$ reik�m�s yra $\{0,1,2,\cdots,9\}$.
MNIST duomen� baz�je yra $60000$ mokymo duomen� ir $10000$ testavimo duomen�.
Tod�l galime laikyti, kad turime $60000$ $X$ ir $Y$ egzempliori�
$$
 \{X_i, Y_i\}_{i=1}^{60000},
$$
kuriuos galime naudoti Bajeso klasifikatoriaus apmokymui. Atpa��stant ne�inom� skai�i�
mes tur�sime $28\times28$ binarin� matric� $X$ ir tur�sime �iai matricai priskirti �ym� $Y$,
t.y. pasakyti koks skaitmuo pavaizduotas matricoje. M�s� klasifikatoriaus tikslumui
�vertinti naudosime $10000$ testavimo duomen� (skaitmen� paveiksliuk�), kuri� �ymes �inome, ta�iau �i� duomen� nenaudosime kuriant klasifikavimo taisykl�.
Vis� galim� skirting� paveiksliuk� yra $2^{28\times 28} = 2^{784}$. Tai yra did�iulis skai�ius
ir turima $60000$ skaitmen� mokymo aib� sudaro tik menkut� $2^{784}$ dal�.
Tiksliau ta dalis lygi $\frac{60000}{2^{784}}=5.9 10^{-232}$.
Tai yra tipin� klasifikavimo u�davini� problema - mokymo duomen�, lyginant su vis� galim� skirting� duomen� $X$ skai�iumi, yra labai nedaug.
Bet koks klasifikavimo algoritmas (taisykl�) stengiasi apibendrinti turimus mokymo duomenis
ir algoritmo kokybei �vertinti naudojami nauji nesantys mokymo duomen� imtyje duomenys.
Klaid� procentas, kur� daro klasifikatorius atpa�indamas ne�inomus duomenis, vadinamas {\em apibendrinimo } klaida.
Kad �vertinti klasifikatoriaus apibendrinimo klaid�, reikia tiksliai �inoti duomen�
skirstin� ir vis� galim� vaizd� klasifikavimo bei tikr�sias reik�mes. Ta�iau prakti�kai
tiksliai apskai�iuoti apibendrinimo klaidos ne�manoma, nes ne�inomas nei tikslus duomen� skirstinys
nei vis� galim� duomen� tikslios �ym�s ($y_j\in Y$), nes prie�ingu atveju nereik�t�
kurti klasifikatoriaus. Tod�l prakti�kai apibendrinimo paklaida �vertinama panaudojant testavimui skirtus duomenis.
Did�iausia b�da �ia, kad labai da�nai tobulinant klasifikavimo algoritm� jo kokyb� daug kart� �vertinama panaudojant testavimo duomenis
ir tod�l galutinio algoritmo klasifikavimo apibendrinimo paklaida b�na �vertinama per daug optimisti�kai, t. y.
algoritmo k�rimo metu parenkant optimalius klasifikatoriaus parametrus b�na netiesiogiai atsi�velgiama � tarpinius algoritmo testavimo rezultatus.

Kad i�spr�sti �i� problem�, rekomenduojama naudoti {\em kry�minio patikrinimo} (angl. {\em cross validation} metod�.
Pagal �� metod� turima mokymo duomen� aib� suskaidoma � pana�aus dyd�io poaibius ir
mokinimui skiriami visi poaibiai, i�skyrus vien�, kuris naudojamas testavimui.
Testavimui skirtas poaibis yra kei�iamas ir, jei leid�ia skai�iavimo laiko resursai,
pereina visas galimus mokymo imties suskaidymo poaibius. D�l �ios savyb�s metodas ir yra vadinamas
kry�minio patikrinimo. Algoritmo parametrai yra optimizuojami kry�min�s patikros poaibiams
ir galutin� algoritmo klasifikavimo apibendrinimo paklaida �vertinama vien� kart� algoritmo k�rimo pabaigoje
paskai�iuojant kiek galutin� algoritmo versija daro klaid� atpa�indama testinius duomenis.

Kadangi mokymo duomen� visada tr�ksta, gana da�nai naudojamas {\em naivusis} Bajeso klasifikatorius.
Naivusis klasifikatorius daro prielaid�, kad duomen� visos komponent�s yra nepriklausomos, t. y.
\begin{equation}
 P(X|Y) = P(\{x_1,x_2,...,x_{784}\}|Y) = P(x_1|Y) P(x_2|Y) \dots P(x_{784}|Y). \label{naivusBajes}
\end{equation}
Naiviojo Bajeso klasifikatoriaus prielaid� (\ref{naivusBajes}) u�ra��me MNIST duomen� atveju.
Epitetas "naivusis" pabr��ia, kad realiai tokia s�lyga tiksliai niekada netenkinama.
Ta�iau prakti�kai naivusis Bajeso klasifikatorius da�nai duoda neblogus rezultatus.
Viena pagrindini� to prie�as�i� yra kas pavieni� komponen�i� skirstiniai gali b�ti
patikimai �vertinti naudojant net ir nedidelias mokymo duomen� imtis. M�s� atveju kiekviena duomen� komponent� gali �gyti tik dvi reik�mes: $0$ arba $1$.
Tai dar labiau supaprastina skirstinio �vert�, nes mums reikia �vertinti tik 
$$
 p_i^y = P(x_i=1|y), \ i = 1, 2, \dots, 784, \ y = 0, 1, \dots, 9,
$$
tikimybes, o likusias $q_i^y = P(x_i=0|y)$ rasime i� s�ry�io $p_i^y+q_i^y = 1$.
$p_i^y$ tikimybes �vertinsime panaudodami mokymo duomenis. Viso turime $60000$ pavyzd�i�. o atsi�velgus � skaitmen� reikmes,
gauname tokius mokymo duomenis atskiriems skaitmenims:

%\begin{table}\label{tab:mokymoDuomKiekis}
\begin{tabular}{||c|c|c|c|c|c||}
\hline \hline 
y& 0 & 1 & 2 & 3 & 4 \\ & 5 & 6 & 7 & 8 & 9 \\ \hline
\# & 5923 & 6742 & 5958 & 6131 & 5842 \\ & 5421 & 5918 & 6265 & 5851 & 5949 \\ 
\hline
$P(Y=y)$ & $\frac{5923}{60000} $ & $\frac{6742}{60000} $ & $\frac{5958}{60000} $ & $\frac{6131}{60000} $ & $5\frac{842}{60000} $ \\
 & $\frac{5421}{60000} $ & $\frac{5918}{60000} $ & $\frac{6265}{60000} $ & $\frac{5851}{60000} $ & $\frac{5949}{60000} $\\
\hline \hline 
\end{tabular}
%\end{table}
Pateikti lentel�je duomenys naudojami �vertinti apriorin� skaitmen� tikim� $P(Y=y)$.
Lentel�s apatin�je eilut�je pateiktos �ver�io reik�m�s.

Kad �vertinti fiksuotai pozicijai $i$ ir skaitmeniui $y$ tikimyb� 
$p_i^y = P(x_i=1|y)$, pakanka suskai�iuoti kiek i� $60000$ paveiksl�li� turi �ym� $y$ ir
turintiems �ym� $y$ suskai�iuoti vienetuk� skai�i� pozicijoje $i$.
�emiau pateiktoje lentel�je nurodyti vienetuk� kiekiai pozicijose $i=1, 289, 293, 297 , 401 , 405 , 409 , 513 , 517 , 521 , 784 $.
Kra�tin�s pozicijos $i$ reik�m�s atitinka paveiksl�lio kairyj� vir�utin� ($i=1$) ir de�inyj� apatin� ($i=784$) kamp�.
I� \ref{venetukuKiekis} lentel�s duomen� matyti, kad visuose mokymui skirtuose paveiksliukuose
visi skaitmenys kra�tin�se pozicijose tur�jo tik juodas spalvas, tod�l �iose pozicijose bendras vienetuk� kiekis lygus $0$.
Vadinasi kra�tin�s pozicijos nesuteikia jokios naudingos informacijos skaitmen� klasifikacijai.
Vidurin�s $i$ reik�m�s parinktos taip, kad jos atitikt� $28\times 28$ paveiksl�lio $(14\pm 4,14\pm 4)$ pozicijas.
�iose pozicijose skirtingiems skaitmenims vienetuk� kiekis reik�mingai skiriasi ir jos naudingos klasifikacijai.
Padalin� vienetuk� kiek� i� skaitmens mokymo imties dyd�io gausime tikimybes $p_i^y$.
Pavyzd�iui
$$
p_1^0 =0, \ p_{289}^0 = \frac{2301}{5923}, \ p_{405}^0 = \frac{519}{5923}, \ p_{521}^0 = \frac{485}{5923};\\
$$ $$
p_1^1 =0, \ p_{289}^1 = \frac{23}{6742}, \ p_{405}^1 = \frac{1590}{6742}, \ p_{521}^1 = \frac{4071}{6742};\\
$$ $$
p_1^9 =0, \ p_{289}^9 = \frac{2162}{5949}, \ p_{405}^9 = \frac{2760}{5949}, \ p_{521}^9 = \frac{3627}{5949}.
$$

\begin{table}\label{venetukuKiekis}
{\small
\begin{tabular}{||c|c|c|c|c|c|c|c|c|c|c|c||}
\hline\hline
y/i & 1 & 289 & 293 & 297 & 401 & 405 & 409 & 513 & 517 & 521 & 784 \\ \hline

0 & 0	& 2301	&  3484	&  1253	& 4041	& 519	& 146	& 3788	& 485	& 2125	& 0\\
1 & 0	& 23	&  728	&  4187	& 16	& 1590	& 1617	& 109	& 4071	& 772	& 0\\	
2 & 0	& 586	&  613	&  2199	& 623	& 1929	& 3395	& 3050	& 3991	& 3522	& 0\\	
3 & 0	& 384	&  1048	&  3872	& 703	& 3790	& 3843	& 541	& 277	& 2002	& 0\\	
4 & 0	& 1872	&  1981	&  1626	& 4035	& 2591	& 4628	& 823	& 1401	& 3343	& 0\\	
5 & 0	& 1295	&  2918	&  1229	& 1556	& 3064	& 2291	& 759	& 532	& 2052	& 0\\	
6 & 0	& 996	&  3325	&  427	& 2325	& 2463	& 3831	& 2606	& 3701	& 2977	& 0\\	
7 & 0	& 2958	&  3200	&  3592	& 730	& 180	& 4113	& 122	& 1186	& 3660	& 0\\	
8 & 0	& 1527	&  2694	&  1746	& 543	& 4276	& 4126	& 1524	& 3060	& 2558	& 0\\	
9 & 0	& 2162	&  2345	&  2118	& 2950	& 2760	& 4958	& 388	& 982	& 3627	& 0\\	
\hline\hline
\end{tabular}
}
\caption{Mokymo imties vienetuk� kiekis nurodytose paveikzl�li� pozicijose}
\end{table}
Naivusis Bajeso klasifikatorius naudoja visas $p_i^y$ ir $q_i^y = 1 - p_i^y$ tikimybes.
Tarkime turime klasifikacijai pateikt� paveiksliuk� $X=\{x_1, x_2, \dots, x_{784}$.
Tuomet  tikimyb� , kad �is paveiksliukas bus skaitmens $y$ vaizdas pagal naiviojo Bajeso modelio algoritm�
bus apskai�iuojama formule 
$$
P(Y=y|X) = \frac{P(X|Y=y)\, P(Y=y)}{P(X)} = \frac{P(Y=y) \prod_{i=1}{784} (x_i p_i^y + (1-x_i) q_i^y)}{P(X)}.
$$
Vardiklio, t. y. tikimyb�s $P(X)$ mes apskai�iuoti negalime. Ta�iau klasifikacijai jis n�ra b�tinas,
nes pagal naiviojo Bajeso klasifikatori� skaitmuo $y$ parenkamas taip, kad $P(Y=y|X)$ b�t� maksimalus,
o tam pakanka �inoti tik de�imties skaitikli� reik�mes, kurioms apskai�iuoti visi duomenys �inomi.
Tarkime
$$
x_1 = 0, \dots, x_{289}= 0, \dots, x_{293}= 0 , \dots, x_{297}= 1 , \dots,$$ $$ x_{401}= 1, \dots, x_{405}= 1, \dots, x_{409}= 0 , \dots,$$ $$ x_{513}= 1, \dots, x_{517}= 0 , \dots, x_{521}= 1 , \dots, x_{784}= 0.
$$
Tuomet 

$$
\begin{array}{rcl}
P(Y=0|X) &=& \frac{5923}{60000}(1-\frac{0}{5923})\cdots (1-\frac{2301}{5923})\cdots(1-\frac{3484}{5923})\cdots\\
&&\frac{1253}{5923}\cdots\frac{4041}{5923}\cdots\frac{519}{5923}(1-\frac{146}{5923})\cdots\frac{3788}{5923}\cdots\\
&&(1-\frac{485}{5923})\cdots\frac{2125}{5923}\cdots(1-\frac{0}{5923})/P(X) \ ,
\end{array}
$$
$$
\begin{array}{rcl}
P(Y=1|X) &=& \frac{6742}{60000}(1-\frac{0}{6742})\cdots (1-\frac{23}{6742})\cdots(1-\frac{728}{6742})\cdots\\
&&\frac{4187}{6742}\cdots\frac{16}{6742}\cdots\frac{1590}{6742}(1-\frac{1617}{6742})\cdots\frac{109}{6742}\cdots\\
&&(1-\frac{485}{4071})\cdots\frac{772}{6742}\cdots(1-\frac{0}{6742})/P(X) \ ,
\end{array}
$$
$$\ \ \ \cdots$$
$$
\begin{array}{rcl}
P(Y=2|X) &=& \frac{5949}{60000}(1-\frac{0}{5949})\cdots (1-\frac{2162}{5949})\cdots(1-\frac{2345}{5949})\cdots\\
&&\frac{2118}{5949}\cdots\frac{2950}{5949}\cdots\frac{2760}{5949}(1-\frac{4958}{5949})\cdots\frac{3788}{388}\cdots\\
&&(1-\frac{982}{5949})\cdots\frac{2125}{3627}\cdots(1-\frac{0}{5949})/P(X) \ .
\end{array}
$$
�ia daugta�kiai �ymi praleistu sandaugos d�menis, kuri� reik�mi� neturime \ref{venetukuKiekis} lentel�je.
Kad i�renkti maksimali� tikimyb�, pakanka apskai�iuoti tik skaitiklius, nes vis� trukmen� vardiklis tas pats (nors ir yra ne�inomas).
Skai�iuojant prakti�kai patartina skai�iuoti ne skaitiklio sandaugas, o sandaugos d�men� logaritm� sumas, kad i�vengti labai ma�� skai�i� aritmetikos.
Skai�iuojant pagal naiviojo Bajeso taisykl� tikimybes tur�sime problem�, kai kokia nors tikimyb� lygi nuliui.
Tuomet tokios tikimyb�s logaritmas neapibr��tas ir gausime, kad tokios �ym�s tikimyb� lygi nuliui.
Tai nelabai logi�ka, ypa� kai mokymo duomen� nedaug, vienas i� $784$ ta�keli� gali nulemti visos sandaugos reik�m�.
Tod�l rekomenduojama, jei kokio nors po�ymio $x_i$ tikimyb� lygi nuliui arba $1$ priskirti $\epsilon$ ar $1-\epsilon$,
kur $\epsilon$ ma�as teigiamas skai�ius, kurio reik�m� pasirenkama eksperimentiniu b�du maksimizuojant teisingai klasifikuojam� duomen� kiek�.

Klasifikavimas pagal naivijo Bajeso taisykl� yra labai spartus. I� tikr�j�, jei visos 
$P(Y=y)$ ir $p_i^y$ tikimyb�s jau apskai�iuotos arba nuskaitytos i� failo, tai klasifikuojant vien� skaitmen�
pakanka apskai�iuoti $784\times 10$ sumas ir i� gaut� de�imties skai�i� i�rinkti maksimum� ir
klasifikacijos rezultatui pateikti maksimum� atitinkan�i� �ym�. Klasifakotoriaus suk�rimas taip pat labai spartus - 
u�tenka prab�gti vien� kart� visus mokymo duomenis, sukaupti tikimyb�ms apskai�iuoti reikaling� statistik� ir, turint
vienetuk� ir nuliuk� skaitiklius, apskai�iuoti $P(Y=y)$ ir $p_i^y$ tikimybes.

Naivusis Bajeso klasifikatorius (kaip ir kiti) negarantuoja, kad visi mokymo imties duomenys yra klasifikuojami teisingai.
Tod�l �emiau pateikiamos lentel�s apie klasifikavimo rezultatus mokymo ir testavimo imtims atskirai.
\begin{itemize}
\item Mokymo imties dydis: 60000     
\item Teisingai klasifikuota (atpa�inta): 50384 arba 83.9733 \%
\item Neteisingai klasifikuota skaitmen�: 9616 arba 16.0267 \%
\item Atskir� skaitmen� klasifikavimas:
$$
\begin{array}{|cccccccccc|c|}
\hline\hline
    0  &  1  &  2 &   3  &  4  &  5  &  6  &  7  &  8  &  9 &  <--\\
\hline
 5371  &  1  & 50 &  15 &  21 &  99 & 166  &  1 & 153 &  46 &   0\\
    0 & 6446 &  59 &  16 &   2 &  84 &  36 &  15 &  68 &  16 &    1\\
   77 &  69 & 4919 & 145 &  68 & 16 & 277 &  90 & 256  & 41 &   2\\
   44 &  81 & 344 & 4966 & 8 & 151 &  60  & 81 & 214 & 182 &   3   \\
   12 &  20  & 48  &  4 & 4469 & 36 & 116 &  11 & 106 & 1020 &   4  \\
  109 &  36 & 106 & 569 & 112 & 3885 & 137  & 15 & 206 & 246 &   5  \\
   66 &  74 & 136  &  2 & 48  & 207 & 5318  &  0  & 59 & 8 &  6   \\
   84 & 141  & 89  & 33 & 191  &  4 & 6 5355 & & 72 & 290 &   7  \\
   57  & 89  &104  & 209 & 60  & 202 &  80  & 8 & 4718 & 324 &   8 \\
   59  & 63  & 64  & 66 & 384  & 77  & 10 & 129 & 160 & 4937 &   9  \\
\hline\hline
\end{array}
$$
\item Naiviojo Bajeso modelio suk�rimo laikas: 2.25 sek.
\item Mokymo duomen� klasifikavimo laikas: 48.69 sek.

\end{itemize}

\begin{itemize}
\item Testavimo imties dydis: 10000     
\item Teisingai klasifikuota (atpa�inta): 8454 arba 84.54 \%
\item Neteisingai klasifikuota skaitmen�: 1546 arba 15.46 \%
\item Atskir� skaitmen� klasifikavimas:
$$
\begin{array}{|cccccccccc|c|}
\hline\hline
    0  &  1  &  2 &   3  &  4  &  5  &  6  &  7  &  8  &  9 &  <--\\
\hline
  913  &  0&    3 &   3 &   0 &  10&   21&    2&   22&    6 &    0\\
    0 & 1095&   12 &   1 &   0&    7&    8&    2&   10&    0 &   1  \\
   14 &  14 & 833 &  36 &   7&    1&   45&   18&   53&   11 &    2 \\
    4  &  3  & 54 & 845  &  0 &  26 &   7 &  21&   28 &  22 &    3\\
    2   & 3  &  7 &   1 & 740  &  7  & 21  &  1&   21 & 179 &    4\\
   13&    4&   10 &  96&   22&  653&   26 &   2&   31&   35 &    5\\
   18 &   6 &  19 &   1 &  14 &  30 & 855  &  0&   13 &   2 &    6\\
    8  & 28  & 33 &   1 &  15  &  1  &  1&  871&   18&   52 &    7\\
   10   & 6 &  12 &  41  & 11 &  30 &  11 &   6&  791&   56 &   8\\
   13   & 9  &  8 &  10  & 60  & 16 &   1  & 10&   24 & 858 &   9\\
\hline\hline
\end{array}
$$
\item Testavimo duomen� klasifikavimo laikas: 8.1 sek.

\end{itemize}

Gauta naiviojo Bajeso klasifikatoriaus kokyb� yra gana gera, nes jei klasifikavimas b�t� atsitiktinis, gautum�me tik apie $10$ \% teisingai klasifikuot� skaitmen�. Lyginant mokymo ir testavimo
duomen� teisingai klasifikuot� skaitmen� dal� matome, kad testuojami duomenys klasifikuojami net �iek tiek geriau - tai byloja, kad klasifikatorius "nepersimok�", t.y. per daug nesiadaptavo prie mokymo imties specifini� paveiksl�li�.
\ref{fig:MNISTtankiai} paveiksl�lis iliustruoja tankio funkcij� �vertint� pagal naiviojo Bajeso model� MNIST mokymo duomenims.
Matyti, kad reik�m�s $x_i=1$ yra labiausiai tik�tinos ten kur da�niausiai ra�omas skaitmuo.
Taip atsitinka d�l to, kad visi MNIST paveiksliukai yra standartinio dyd�io ir centruoti.
Kadangi testavimui skirti duomenys parinkti i� tos pa�ios NIST �ra�� duomen� baz�s,
labiausiai tik�tina, kad skaitmens $x_i=1$ pozicijos bus nelabai nutolusios nuo mokymo imties tankio $P(x_i=1)$ maksimum�
ir tod�l tikimyb� �vertinta pagal naiviojo Bajeso taisykl� bus did�iausia tuo atveju, kai �ym�s $y$ reik�m� sutaps su tikr�ja skaitmens reik�me.
\begin{figure}
\centering
\includegraphics{figures/MNISTtankiai}  
\caption{Naivijo Bajeso MNIST duomen� modelio tankio funkcijos vizualizacija. �vieseni ta�kai �ymi didesn� tank� ir atvirk��iai, tamsesni ma�esn� tank�. Vir�utin�se dviejose eilut�se $P(x_i=0)$ reik�m�s, apatin�se - $P(x_i=0)$.} 
 \label{fig:MNISTtankiai}
\end{figure}

\subsection{MNIST klasifikavimo pagerinimas i�lyginant skaitmen� nuo�ulnum�}
\begin{figure}
\centering
\includegraphics{figures/MNISTpakreipimas}  
\caption{MNIST binarizuoti pradiniai duomenys (kairiau) ir su i�lygintu nuo�ulnumu (de�iniau)} 
 \label{fig:MNISTpakreipimas}
\end{figure}
