\newcommand{\alp}{{\bf \alpha}}
\newcommand{\X}{{\bf X}}
\newcommand{\Y}{{\bf Y}}
\newcommand{\w}{{\bf w}}
\newcommand{\wt}{{\bf w}^T}
\newcommand{\wtx}{\wt\X}
\newcommand{\sgn}{\mathop{\mathrm{sgn}}}

\section{Atramini� vektori� klasifikatorius}

\subsection{Vapniko-�ervonenkio dimensija}
Atramini� vektori� klasifikatoriai (AVK) (angl {\it Support Vector Machines SVM}), panaudodami mokymo duomenis $(X_i,Y_i)$, sukuria klasifikavimo taisykles.
Pradiniai AVK variantai buvo pasi�lyti Vladimiro Vapniko 1970-�j� pabaigoje \cite{bib:VVapnik}.
1990 metais jis i� Maskvos persikraust� dirbti � JAV ir kartu su savo mokiniais ir kolegomis i�vyst� AVK metod�.
AVK gr�stas Vapniko-�ervonenkio dimensija \cite{bib:VapnikCernovenkis}.
Vapniko-�ervonenkio dimensija skaiti�kai �vertina klasifikatoriaus sud�tingum�.
Tarkime tiesinis klasifikatorius gali daryti daugiau u� kvadratin� klasifikacijos klaid�, ta�iau jo sud�tingumas yra ma�esnis ir � tai reikia atsi�velgti priimant sprendim� vertinant kuris i� dviej� klasifikatori� yra geresnis
(tiesinis, paprastesnis, turintis ma�iau parametr�, bet darantis daugiau klasifikavimo klaid�,
ar kvadratinis, sud�tingesnis, turintis daugiau parametr�, bet darantis ma�iau klasifikavimo klaid�).
Apibr��ime formaliai Vapniko-�ervonenkio dimensij�.
\begin{apibrezimas}
Sakysime turime klasifikatori� $f$, charakterizuojam� parametr� rinkiniu $\Theta$, ir testavimo
duomenis $X_1, X_2, \dots, X_N$. Sakysime, kad klasifikatorius $f$ {\bf atskiria} duotus duomenis $X_i$,
jei bet kokioms binarin�ms �ym�ms $Y_i\in\{-1,1\}$\footnote{Apra�ant atramini� vektori� klasifikatori� patogiau laikyti, kad binarin�s �ym�s yra -1 ir 1, o ne 0 ir 1}, $i = 1, 2, \dots, N$, egzistuoja klasifikatoriaus
$f$ parametr� rinkinys $\Theta$ su kuriuo visi duomenys yra teisingai klasifikuojami.

Klasifikatoriaus $f$ Vapniko-�ervonenkio (VC) dimensija $D_{VC}$ vadinamas maksimalus duomen� $X_i$ kiekis, kur� klasifikatorius {\bf atskiria}.
\end{apibrezimas}
Pavyzd�iui, jei klasifikatorius yra ties� plok�tumoje, o klasifikuojami duomenys plok�tumos ta�kai,
tai bet kokius nekomplanarius tris plok�tumos ta�kus su bet kokiomis binarin�mis �ym�mis
galime atskirti tiese, ta�iau ne visada keturis plok�tumos ta�k� gal�sime atskirti tiese (�i�r. \ref{fig:VC} iliustracij�).
Vadinasi tiesinio plok�tumos ta�k� klasifikatoriaus dimensija yra $3$. Galima parodyti, kad tiesinio klasifikatoriaus klasifikuojan�io
$D$-at�s erdv�s ta�kus VC dimensija yra $D+1$ (plok�tumos ta�k� atveju $D=2$ ir $D+1=3$).

\begin{figure}
\centering
\includegraphics[scale=0.75]{figures/VC3-4}  
\caption{Plok�tumos ta�k� tiesinio klasifikatoriaus Vapniko-�ervonenkio dimensija. Bet kaip su�ym�tus tris ta�kus 
galime atskirti tiese, o keturis neb�tinai.}
 \label{fig:VC}
\end{figure}
                                                                  
Vapnikas ir �ervonenkis �rod�, kad jei klasifikatorius ne�inom� duomen� klasifikavimo klaida gali b�ti �vertinta i� vir�aus tokia i�rai�ka
\begin{eqnarray}\label{klasifikavimoKlaidosYvertis}
 P(\mbox{Klasif. pagal f}) &\le& P(\mbox{Klasif. pagal f testavimo duom.}) + \nonumber\\
 && \sqrt{(\frac{D_{VC}(\log(2N/D_{VC})+1)-\log(\delta/4)}{N}}.
\end{eqnarray}
�ia $1-\delta$ tikimyb� su kuria galioja klasifikavimo klaidos �vertis, o $N$ - testavimo duomen� kiekis.
(\ref{klasifikavimoKlaidosYvertis}) nelygyb� suteikia galimyb� �vertinti pasirinkto klasifikatoriaus
kokyb� ir nurodo galim� strategij� konstruojant klasifikatori�. Atramini� vektori� klasifikatorius
yra viena tokios strategijos realizacij�.

\subsection{Tiesinis atramini� vektori� klasifikatorius}
Tarkime turime mokymo duomen� imt� $(X_i,Y_i)$, $i = 1, 2, \dots, L$, $Y_i\in\{-1,1\}$.
MNIST skaitmen� atveju $L=60000$, o $X_i$ gali b�ti $28\times 28=784$ pilkumo lygmen� matrica, t. y.
kiekvienas duomuo $X_i$ yra $784$ dimensij� vektorius, kurio kiekviena komponent� �gyja reik�mes pilkumo lygmen� aib�je $\{0, 1, \dots, 255\}$.
Kadangi patogiausia vizualizuoti dvima�ius duomen� vektorius, tai toliau pateiksime klasifikuojam� plok�tumos ta�k� iliustracijas.
\ref{fig:VSMklasif} paveiksl�lyje pateiktas tiese pilnai atskiriam� plok�tumos ta�k� pavyzdys.

\begin{figure}
\centering
\includegraphics[scale=0.66]{figures/VSMklasif}  
\caption{Dviej� r��i� plok�tumos ta�kai (skrituliukai ir trikampiukai) pilnai atskiriami linija. 
Palyginkite du galimus iliustracijoje pateiktus tiesin�s klasifikacijos variantus.}
 \label{fig:VSMklasif}
\end{figure}

Tiesinis klasifikatorius gali b�ti u�ra�ytas lygtimi
$$ 
\wtx + b = 0,$$
kur $^T$ �ymi vektoriaus-stulpelio transponavimo operacij�.
Daugiama�i� duomen� atveju tokia lygtis apibr��ia erdv�je hiperplok�tum� (dvimat�s erdv�s atveju ties�).
Klasifikuojant sieksime, kad 
\begin{eqnarray*}
\wtx_i + b &>& 0, \mbox{ kai  } Y_i = 1, \\
\wtx_i + b &<& 0, \mbox{ kai  } Y_i = -1.
\end{eqnarray*}
Tod�l klasifikavimo taisykl� $f$ testavimo duomenims $\X$ apibr��ime formule
$$f(\X) = \sgn(\wtx + b ).$$
Tarkime kokiame nors ta�ke $\X_i$ i�rai�ka $\wtx_i+b=1$. Tuomet  skai�ius $\frac{\wtx_i+b}{||\w||}=\frac{1}{||\w||}$
�ymi hiperplok�tumos (ties�s) $ \wt (\X-\X_i) = 0 $ atstum� iki koordina�i� prad�ios ta�ko. Tod�l skai�ius
$$\frac{2}{||\w||}=\frac{2}{\sqrt{(\wt\w)}}$$
lygus atstumui tarp hiperplok�tum� $\wtx+b=\pm 1$.

Intuityviai ai�ku, kad tiesinis klasifikatorius, pilnai atskiriantis duomenis, tuo geresnis, kuo didesnis atstumas tarp toki� hiperplok�tum�.
Vapnikas ir �ervonenkis pateikia tiksli� atstumo tarp ta�kus atskirian�i� hiperplok�tum� maksimizavimo interpretacij� klasifikacijos patikimumo terminais,
bet mes apsiribosime tik �io principo panaudojimu. Taigi mums reikia rasti tok� svori� vektori�
$\w$ ir poslink� $b$, kad 
\begin{eqnarray}
\min_{\w,b} &&\frac12 \wt \w, \label{minVSP}\\ 
\mbox{kai }&& Y_i(\wtx_i+b) \ge 1, \ i = 1, 2, \dots L.\label{restrVSP}
\end{eqnarray}

\subsection{Tiesi�kai neatskiriam� duomen� klasifikavimas atramini� vektori� metodu}

Pateiktas atramini� vektori� klasifikatorius turi du akivaizd�ius tr�kumus.
\begin{itemize}
\item Jei duomenys yra bent kiek sud�tingesni, gali neatsirasti tiesinio klasifikatoriaus, kuris visiems duomen� indeksams $i$ garantuot�
(\ref{restrVSP}) nelygyb�. Pavyzd�iui plok�tumoje galima rasti dviej� klasi� keturis ta�kus, kuri� ne�manoma atskirti viena tiese (�i�r. \ref{fig:VC} pvz.).
\item Skirting� �ymi� duomenys gali gerai atsiskirti nesud�tinga kreive, kuri n�ra ties�. \ref{fig:VSMapskr}
paveiksl�lis iliustruoja toki� duomen� pavyzd�.
\end{itemize}
Kad i�spr�sti pirm�j� problem�,  1995 metais Cortes ir Vapnikas \cite{bib:CortesVapnik1995} pasi�l� lanks�i� (\ref{restrVSP})
ir reguliarizuot� (\ref{minVSP}) lyg�i� versij�. Antra problema sprend�iama padidinus pradini� duomen� dimensij�, kur papildomos dimensijos sudarytos i� pradini� kintam�j� netiesini� darini�.

\begin{figure}
\centering
\includegraphics{figures/VSMapskr}  
\caption{Dviej� �ymi� plok�tumos ta�kai, kuriuos lengva atskirti apskritimu, ta�iau klasifikavimo bet kokia tiese rezultatai bus labai �emos kokyb�s.}
 \label{fig:VSMapskr}
\end{figure}
 Netiesin� atramini� vektori� klasifikacijos u�davin� galima u�ra�yti taip:
\begin{eqnarray}
\min_{\w,b,{\bf \xi}} &&\frac12 \wt \w + C\sum_{i=1}^L \xi_i, \label{minNetVSP}\\ 
\mbox{kai }&& Y_i(\wt\phi(\X_i)+b) \ge 1-\xi_i,\label{restrNetVSP}\\
\mbox{ir }&& \xi_i \ge 0, \ i = 1, 2, \dots L. \label{ksiRestr}
\end{eqnarray}
�ia $C\ge 0$ yra {\em baudos} parametras. Jei $C$ reik�m� didel�, kiekviena teigiama $\xi_i$
reik�m� stipriai didina minimizuojam� funkcional�. Tod�l kuo baudos daugiklio $C$ reik�m� didesn�, tuo labiau atsi�velgiama � blogiausiai klasifikuojamus duomenis ir atvirk��iai, kai  $C$ ma�as minimizuojamo funkcionalo vert� lemia narys $\frac12 \wt \w$. Funkcija 
$\phi = \phi(\X)$ tiesin� klasifikatori� padaro netiesiniu.
Pavyzd�iui, jei $X\in R^2$, tai $\phi(\X)\in R^6$ galima apibr��ti taip:
$$
\phi(X) = (1,\sqrt2 x_1,\sqrt2 x_2,x_1^2, \sqrt2 x_1x_2, x_2^2).
$$
I� vektoriaus $\phi(X)$ komponen�i� nesunku sudaryti bet kokio plok�tumos apskritimo lygt� ir tod�l nesunku rasti netiesin� atramini� vektori� klasifikatori�, kuris pilnai atskirt� \ref{fig:VSMapskr} paveiksl�lio mokymo duomenis. Bendru atveju ie�komas svori� vektorius gali b�ti begalinio matavimo, jei $\phi = \phi(X)$ turi be galo daug komponen�i�. Pavyzd�iui kartais vienma�iams duomenims naudojama tokia i�rai�k�
$$\phi(x) = \exp{(-\frac{x^2}{2})} \large(1, \sqrt{\frac{1}{1!}}x, \sqrt{\frac{1}{2!}}x^2, \sqrt{\frac{1}{3!}}x^3,\dots,\sqrt{\frac{1}{n!}}x^n,\dots\large).$$
Sekan�iame skyrelyje bus ai�ki tokio pasirinkimo motyvacija.

\subsection{Atramini� vektori� klasifikatoriaus paie�ka sprend�iant dual� u�davin�}

Minimizavimo u�daviniai da�nai sprend�iami netiesiogiai, o pirma i�sprend�iami jiems dual�s u�daviniai, kuri� sprendiniai panaudojami u�ra�ant pradinio u�davinio sprendin�. M�s� atveju
(\ref{minNetVSP}-\ref{ksiRestr}) u�daviniui dualus formuluojamas taip:
\begin{eqnarray}
\min_{\alp} && \frac12 \alp^T Q \alp - {\bf e}^T\alp, \label{funkAlp}\\
\mbox{kai } && 0\le\alpha_i\le C, i = 1, 2, \dots, L, \label{restrAlp}\\
\mbox{ir } && {\bf Y}^T \alp = 0. \label{restrY}
\end{eqnarray}
�ia ${\bf e}=(1,1,\dots,1)\in R^L$, $Q_{i,j}=Y_iY_j\phi(\X_i)\phi(\X_j)$.
�inant dualaus u�davinio sprendin�, atraminio vektoriaus klasifikatoriaus svoriai $\w$ randami taip:
\begin{equation}
\w = \sum_{i=1}^L \alpha_i Y_i \phi(X_i).
\end{equation}

I�rai�ka
\begin{equation} \label{branduolys}
 K(\X,\Y) = \phi(\X)^T \phi(\Y)
\end{equation}
vadinama {\em branduoliu}. Kad branduol� b�t� galima efektyviai apskai�iuoti, siekiama, kad jis b�t�
$$\X^T\Y$$
skaliarin�s sandaugos funkcija. Pavyzd�iui, jei $X\in R^2$ ir
$$
\phi(X) = (1,\sqrt2 x_1,\sqrt2 x_2,x_1^2, \sqrt2 x_1x_2, x_2^2),
$$
tai
\begin{eqnarray*}
K(\X,\Y) = \phi(\X)^T \phi(\Y) &=& 1 + 2 x_1 y_1 + 2 x_2 y_2 + x_1^2y_1^2 + 2x_1x_2y_1y_2 +x_2^2y_2^2\\
	&=&
	(1 + x_1 y_1 + x_2 y_2 ) ^ 2.
\end{eqnarray*}
Populiar�s atraminio vektoriaus klasifikatoriaus branduoliai:
\begin{eqnarray}
K(\X,\Y) &=& \exp(-\gamma||\X-\Y||^2)\label{RBFKerlel}\\
K(\X,\Y) &=& (1 + \X^T\Y/a)^b\label{polinominis}
\end{eqnarray}
Pirmasis vadinamas RBF (angl. {\em Radial Basis Function} ), o antrasis polinominiu branduoliu.
RBF branduoliui galima surasti kintam�j� pakeitim� � begalin�s dimensijos erdv�,
kurioje skaliarin� sandauga $ \phi(\X)^T\phi(\Y) $ sutampa su $K(\X,\Y) = \exp(-\gamma||\X-\Y||^2)$.
�rodysime �� teigin�, kai $\X=x, \Y=y \in R^1$. I� tikr�j�, kadangi pagal Teiloro skleidin�
\begin{eqnarray*}
\exp(-\gamma||\X-\Y||^2) &=& \exp(-\gamma(x-y)^2) = \exp(-\gamma x^2-\gamma y^2 + 2\gamma xy)\\
	&=&\exp(-\gamma x^2-\gamma y^2)\Large(\sum_{i=0}^{+\infty}\sqrt{\frac{2\gamma}{i!}}x^i\cdot \sqrt{\frac{2\gamma}{i!}}y^i\Large)\\
	&=& \phi(x)^T\phi(y),
\end{eqnarray*}
kur
$$
\phi(x) = \exp(-\gamma x^2)\Large(1,\sqrt{\frac{2\gamma}{1!}}x,\sqrt{\frac{2\gamma}{2!}}x^2,\dots,\sqrt{\frac{2\gamma}{i!}}x^i,\dots\Large).
$$
Polinominis branduolys atitinka baigtinio matavimo atvaizd� $\phi=\phi(\X)$.

Branduolio savyb�, kai j� galima i�reik�ti funkcija nuo pradini� kintam�j� skaliarin�s sandaugos,
vadinama "branduolio gudrybe" (angl. {\em kernel trick}). "Gudryb�s" esm� ta, kad skai�iuojant
branduol� pagal (\ref{branduolys}) i�rai�k� galima susidurti su rimtomis skai�iavimo problemomis
(pvz. begalin�s $(\phi(\X))$ dimensijos atveju), o d�l min�tos branduolio savyb�s, j� galima skai�iuoti panaudojant pradin�s dimensijos duomenis,
kuri yra baigtin� ir, kaip taisykl�, �ymiai ma�esn� nei $\phi(\X)$ transformacijos.

Kod�l klasifikavimo metodas vadinamas "atramini� vektori�" metodu? Taip yra tod�l, kad jo klasifikavimo rezultatus lemia tik tie mokymo vektoriai, kuri� $\alpha_i > 0$. Tai nesunku suprasti analizuojant pradin� tiesin� metodo versij�.
Geometri�kai akivaizdu, kad pilnai atskiriam� plok�tumos ta�k� klasifikacija atramini� vektori� metodu remsis da�niausiai tik trimis mokymo ta�kais, kuri� du bus vienos klas�s, o lik�s kitos klas�s. Pana�i tendencija i�lieka ir bendru atveju, nes dauguma "lengvai" klasifikuojam� mokymo duomen� $\X_i$ tur�s $\alpha_i=0$.
Mokymo vektoriai, kuri� $\alpha_i>0$ vadinami {\em atraminiais}. \ref{fig:VSMatraminiai}
paveiksl�lis iliustruoja mokymo duomen� atramini� vektori� pozicijas.
I� pateikto pavyzd�io matyti, kad nema�a mokymo duomen� dalis ne�takoja klasifikavimo rezultat�, nes, grubiai tariant, tose pozicijose klasifikavimo rezultatas yra akivaizdus ir SVM klasifikatorius koncentruojasi tik � sud�tingiausius mokymo duomen� atvejus. Kuo labiau atsiskiria skirting� �ymi� mokymo duomenys, tuo santykinai ma�esn� dalis mokymo duomen� tampa atraminiais.

\begin{figure}
\centering
\includegraphics[scale=0.66]{figures/VSMatraminiai}  
\caption{Plok�tumos ta�k� klasifikavimas SVM metodu. Raudonais pliusiukais pa�ym�ti atraminiai mokymo duomenys. Iliustracija paimta i� \cite{bib:VSMvideo}}
 \label{fig:VSMatraminiai}
\end{figure}

\subsection{MNIST duomen� klasifikavimas SVM metodu}
Kaip matyti i� pateikto apra�ymo, atramini� vektori� klasifikatoriaus suk�rimas yra nelengva u�davinys.
Tod�l eksperimentuojant mes remsim�s WEKA biblioteka, kuri� suk�r� ir toliau tobulina Naujosios Zelandijos Waikato universiteto studentai (\cite{bib:WEKA}).
�ioje bibliotekoje yra realizuotas atramini� vektori� klasifikatorius su RBF ir polinominiais branduoliais.
Deja pateikus binarizuot� $28\times 28$ duomen� matricas WEKA-i, neu�tenka kompiuterio 1.5 GB atminties, kad b�t� sukurtas SVM algoritmas.
Tod�l tenka ma�inti mokymo vektori� dimensijas. Buvo atlikti keturi eksperimentai, kuriuose naudojamas nutylimasis WEKA SVM klasifikatorius su skirtingomis po�ymi� sistemomis.
\begin{itemize}
\item Po�ymiai sudar� vidurkint� skaitmen� ekstremum� kiek� telpant� � 3x3 gretimus langelius.

Gautas SVM klasifikatoriaus tikslumas: 86.3 \% mokymo duomenims ir 86.2 \% testavimo duomenims.
\item Po�ymiai vidurkinto vaizdo gradiento komponent�s paimtos keturis kartus i�retintame tinklelyje (28x28/4=7x7).

Gautas SVM klasifikatoriaus tikslumas: 91.8 \% mokymo duomenims ir 91.6 \% testavimo duomenims.

\item Po�ymiai vidurkinto vaizdo gradiento komponent�s paimtos du kartus i�retintame tinklelyje (28x28/2=14x14).

Gautas SVM klasifikatoriaus tikslumas: 96.38 \% mokymo duomenims ir 95.43 \% testavimo duomenims.

\item Po�ymiai gauti naudojant tik�tinumus gautus Naiviojo Bajeso metodu. Fiksuotam skai�iui randami vis� skaitmen� tik�tinumai ir z-tuojo po�ymiu laikomas tik�tinumo, kad tai yra z skaitmuo, ir dviej� did�iausi� tik�tinum� aritmetinio vidurkio skirtumas. Kiekvienam paveiksl�liui tokiu b�du gauname de�imt po�ymi�.

Gautas SVM klasifikatoriaus tikslumas: 99.84 \% mokymo duomenims ir 98.16 \% testavimo duomenims.

\end{itemize}
Geriausi rezultatai gaunami paskutiniu atveju, kai po�ymiams naudojami Naiviojo Bajeso klasifikatoriumi gauti normuoti skaitmen� tik�tinumai.
Ta�iau toks rezultatas nelabai d�iugina, nes klasifikuojant tiesiogiai pagal Naiviojo Bajeso tik�tinumus gaunamas 98.04 \% tikslumas testavimo duomenims.
Tik�tina, kad tok� ne�ym� pager�jim� galima gauti paprastesniais b�dais. Taip pat galima pasteb�ti,
kad pagal m�s� eksperiment� rezultatus, ger�jant po�ymi� sistemai, ger�ja klasifikacijos rezultatai,
ta�iau kartu stebimas ir persimokymas, pasirei�kiantis �enkliu skirtumu tarp mokymo ir testavimo
duomen� klasifikavimo kokyb�s.
