\documentclass[draft,a4paper]{article} \usepackage{lt} \usepackage{amsmath} \usepackage{latexsym} \title{Dirbtiniai neuroniniai tinklai \\ {\large Š. Raudžio paskaitų konspektas}} \author{Marius Gedminas} \date{2003 m. pavasaris \\ (VU MIF informatikos magistrantūros studijų 2 semestras)} \newcommand{\Def}{\emph} \begin{document} \maketitle % ---------------------------------------------------------------------------- \begin{quote}\footnotesize Šis konspektas rinktas \LaTeX{}u Š. Raudžio paskaitų metu. Poroje paskaitų paskaitų aš nedalyvavau ir jas paskui nusirašiau nuo kolegų (3, 4, 5, 15, 16, 17 skyriai). Deja, laiko tvarkingai viską patikrinti ir suredaguoti dar neradau, tad patariu per daug šiuo konspektu nepasitikėti. Jei rasite klaidų ar turėsite kokių pastabų, galite jas atsiųsti man elektroninio pašto adresu \texttt{marius@gedmin.as}. \end{quote} % --- 1 paskaita \section{Neuroniniai tinklai} % 1 % Smegenyse yra 1e10 ... 1e14 ląstelių (niekas nežino, kaip reiktų jas % suskaičiuoti). % neuronai, aksonai, dendritai. % Neuronas: yra n inputų (n ~ 5000) ir vienas outputas 1943 m. neurono modelis: \[ s = w_0 + \sum_{i=1}^p w_i x_i \] čia $x_1, \dots, x_p$ -- įėjimai. Paskui pritaikomas slenkstis ir reikšmė keičiama į $0$ arba $1$. Tai -- neurono išėjimas. Vėliau buvo sugalvota rezultatą perleisti pro \Def{sigmoidinę} funkciją (angl. \emph{logistic sigmoid}) \[ f(s) = \frac{1}{1+e^{-s}} \] Šios funkcijos ypatybės: \begin{itemize} \item $f(s)$ beveik tiesinė, kai $|s|$ yra mažas; \item $f(s)$ artėja prie $0$, kai $s \to -\infty$; \item $f(s)$ artėja prie $1$, kai $s \to \infty$. \end{itemize} % čia būtų gerai grafiką įdėti. Kartais vietoje sigmoidinės funkcijos naudojamas hiperbolinis tangentas, duodantis atsakymą iš intervalo $(-1; 1)$. \paragraph{Atpažinimo uždavinys} Reikia suskirstyti duomenis į klases. Tarkime, kad turime du požymius: $x_1$ -- svoris, $x_2$ -- ūgis. Norime atskirti berniukus nuo mergaičių. Tai gali padaryti vienas neuronas, tinkamai parinkus svorius $w_i$: \[ s = x_1 w_1 + x_2 w_2 + w_0 \] $s = 0$ yra skeliamasis paviršius. $s > 0$ -- berniukai, $s < 0$ -- mergaitės. Jei įtrauksime sigmoidinę funkciją, tuomet $f(s) > 0.5$ -- berniukai, $f(s) < 0.5$ -- mergaitės. Sudėtingesniais atvejais vieno neurono nepakanka -- reikia tinklo, sudaryto iš kelių sluoksnių. Pvz., keturi neuronai pirmajame sluoksnyje duoda rezultatus $y_1$, \dots, $y_4$, o penktasis neuronas antrajame sluoksnyje juos ima kaip įvestis. Dirbtinis neuroninis tinklas -- rinkinys tarpusavyje sujungtų neuronų. Labiausiai paplitusios yra dvi dirbtinių neuroninių tinklų rūšys: \begin{itemize} \item \Def{vienasluoksnis perceptronas} arba tiesiog perceptronas (angl. \emph{single layer perceptron}; \Def{SLP}) -- tiesiog vienas neuronas. \item \Def{daugiasluoksnis perceptronas} (angl. \emph{multilayer perceptron}; \Def{MLP}) -- daug neu\-ro\-nų, išdėstytų sluoksniais. Kiekvieno sluoksnio neuronų išėjimai sujungti su kito iš eilės sluoksnio neuronų įėjimais. Įėjimo sluoksnis -- pradiniai duomenys; išėjimo sluoksnis -- paskutiniame sluoksnyje esantys neuronai ir jų išėjimai; visi kiti sluoksniai vadinami paslėptais. \end{itemize} Didžioji dauguma dirbtinių neuroninių tinklų yra SLP arba MLP. MLP su vienu paslėtu sluoksniu gali modeliuoti bet kokio sudėtingumo atpažinimo paviršių. \paragraph{Prognozavimo uždavinys} Perceptronus galima naudoti ir prognozavimui. MLP su vienu paslėtu sluoksniu gali aproksimuoti bet kokią funkciją (jei tame sluoksnyje yra pakankamai neuronų). % Periodinių reisinių modeliavimas. Sūkuriai. Refraktorinis periodas. % Emocijų modeliavimas. \section{Vienasluoksniai ir daugiasluoksniai perceptronai ir jų mokymo principas} % 2 Kas yra vienasluoksniai ir daugiasluoksniai perceptronai parašyta praeitame skyriuje. Problema: kaip reikėtų rasti perceptrono koeficientus $w_i$? Sprendimas: perceptroną reikia apmokyti. % Repetitio est mater studiorum Turime rinkinį mokymo vektorių $(x_{11}, \dots, x_{1p}, t_1)$, \dots, $(x_{n1}, \dots, x_{np}, t_n)$. Čia $x_{ji}$ -- įėjimo reikšmės, $t_j$ -- tikslas (\emph{desired target}). Apibrėžkime kainos funkciją \[ c = \sum_{j=1}^n \big(t_j - f(w_1x_{j1} + \dots + w_px_{jp} + w_0)\big)^2 \] Norime ją minimizuoti. Tai būtų trivialu, jei nebūtų netiesinės f-jos f. Minimizavimui (apmokymui) yra daug įvairių metodų -- \emph{error back propagation}, \emph{conjugate gradient} ir t.t. % --- 2 paskaitą praleidau, nusirašiau nuo Ramūno \section{Klasifikavimo uždavinys. Statistinis klasifikavimas. Mokymas vienasluoksniu perceptronu.} % 3 Kas yra klasifikavimo uždavinys -- žr. pirmąjį skyrių. \paragraph{Statistinis klasifikavimas} Įvertiname kiekvienos klasės pasiskirstymo tankį $f_i(x)$. Tarkime, kad klasių yra dvi. Jei kažkuriame taške $f_1(x) > 0$, o $f_2(x) = 0$, aišku, jog šis taškas priklauso pirmajai klasei ir atvirkščiai, jei $f_1(x) = 0$, o $f_2(x) > 0$, taškas priklauso antrajai klasei. Ką daryti, jei $f_1(x) > 0$ ir $f_2(x) > 0$? Galime tiesiog imti klasę, kurios tankis tame taške didesnis: \[ g(x) = \ln\Big(\frac{f_1(x)}{f_2(x)}\Big) \] Jei $g(x) > 0$, reiškia, $f_1(x) > f_2(x)$ ir $x$ priskiriame pirmajai klasei; jei $g(x) < 0$, reiškia, $f_1(x) < f_2(x)$ ir $x$ priskiriame antrajai. Kai kurios klasės pasitaiko dažniau nei kitos. Jei klasių pasirodymo tikimybės yra $q_1$ ir $q_2$ ($q_1 + q_2 = 1$), galime lyginti ne $f_1(x)$ ir $f_2(x)$, o $q_1 f_1(x)$ ir $q_2 f_2(x)$. Galima taip pat atsižvelgti į klaidos kainą (geriau suklysti į saugesnę pusę). \paragraph{Sprendimas vienasluoksniu perceptronu} Žr. pavyzdį pirmame skyriuje. % Konkrečiai šią paskaitą buvo kiek kitas pavyzdys: % % grafikėlis: x1 -- ūgis, x2 -- klubų apimtis. Du debesėliai -- vyrai ir % moterys. % % skiriamoji linija x2 = a + x1 * tg alpha % % neuronas g(x) = x1 w1 + x2 w2 + w0 % g(x) > 0 -- berniukai % g(x) < 0 -- mergaitės % % bet esmė ta pati. Turime perceptroną: \[ g(x) = x_1 w_1 + x_2 w_2 + w_0 \] Kaip rasti koeficientus? Nuostolių funkcija: \[ c = \sum_{j=1}^n \big(t_j - f(w_1x_{j1} + \dots + w_px_{jp} + w_0)\big)^2 \] $n$ -- mokymo duomenų kiekis, $p$ -- požymių skaičius, $x_j$ -- mokymo vektorius, $t_j$ -- trokštamas išėjimas tam vektoriui. Kas toliau? \begin{enumerate} \item \Def{atsitiktinė paieška} -- prigeneruojame $10^{20}$ variantų svorių ir ieškome geriausio rezultato \item \Def{genetiniai algoritmai} -- ieškome rajono, kuriame yra teisingas variantas ir toliau dirbame tame rajone \item \Def{mažiausiųjų kvadratų metodas} -- sprendžiame lygčių sistemą \[ \left\{\begin{array}{l} \frac{\partial c}{\partial w_1} = 0 \\ \frac{\partial c}{\partial w_2} = 0 \\ \vdots \end{array}\right. \] Jei f-ja turi daug minimumų, gali būti sunku surasti teisingą atsakymą. Niutono metodu \[ w_{t+1} = w_t - \eta \frac{\partial c}{\partial w} \] $\eta$ -- mokymo žingsnis. Jei jis per didelis, diverguosime. % $t \to \infty$, $\eta \to 0$ tada artėjame prie tikslo. % grafikėlis kreivė artėjanti prie 0, statesnė kreivė, kuri prie 0 % priartėja anksčiau, ir visai stati kreivė, kuri staiga užsilenka % ir šoka į viršu, o paskui pradeda šokinėti aukštyn žemyn. % namų darbams: pakaitalioti mokymo žingsnį 1 užduotyje Mokymo žingsnį galima reguliuoti pagal sėkmę: jei sekasi -- didiname, jei nesiseka -- mažiname. Beje, galima ir atsisakyti nuo atsakymo pateikimo, t.y. atsakyti „nežinau, modelis per silpnas šiam atvejui“. Pradedant mokyti reikia paduoti pradinius svorius. Vienasluoksniam perceptronui jų reikšmės nesvarbios, tad galime imti nuliukus. \end{enumerate} \section{Tiesinė ir kvadratinė diskriminantinės funkcijos} % 4 % (statistika) Prielaida: duomenys yra normaliai pasiskirstę. $\mu x = Ex$ -- vidurkis (aka matematinė viltis), $\sigma^2 = E(x-\mu)^2$ -- variacija, $\sigma$ -- dispersija. Normalinis tankis yra \[ f(x) = \frac{1}{\sqrt{2\pi}\sigma} e^{-\frac{1}{2}(x-\mu)\sigma^{-2}(x-\mu)} \] % \int_{-\infty}^y f(x)dx -- tikimybė, kad atsitiktinis dydis < y? Bendru atveju $p$-matėje erdvėje (daugiamatis) normalinis tankis yra \[ f(x) = \frac{1}{(2\pi)^{p/2} |\Sigma|^{1/2}} e^{-\frac{1}{2}(x-\mu)^T \Sigma^{-1} (x-\mu)} \] Čia $\Sigma$ -- kovariacinės matrica. $x$ bei $\mu$ šiuo atveju yra vektoriai. % Matlabe kovariacinę matricą gauname šitaip: % D1 = (x11, ..., x1p; x21, ..., x2p; ...); % S1 = cov(D1); Taigi, jei turime dvi klases su vidurkiais $\mu_1$, $\mu_2$ ir kovariacinėmis matricomis $\Sigma_1$, $\Sigma_2$, gauname štai tokią diskriminantinę funkciją: \[ g(x) = -\frac{1}{2} (x-\mu_1)^T \Sigma_1^{-1} (x-\mu_1) - \frac{1}{2}ln(|\Sigma_1|) +\frac{1}{2} (x-\mu_2)^T \Sigma_2^{-1} (x-\mu_2) + \frac{1}{2}ln(|\Sigma_2|) \] Ji vadinama \Def{kvadratine diskriminantine funkcija}. Jei $g(x) > 0$, tai $x$ priklauso pirmajai klasei, jei $g(x) < 0$, antrajai. Dar galime pridėti kitus daugiklius (tikimybes, klaidos kainos įverčius, etc. -- žr. aukščiau). \medskip Problema: kaip turint mažai duomenų gauti kovariacinę matricą? Tada galime nutarti, kad $\Sigma_2 = \Sigma_1 = \Sigma$, nors tai netiesa. Gauname tiesinę funkciją \[ g(x) = w^T x + w_0 = \sum_i w_i x_i + w_0 \] kur $w = \Sigma(\mu_1 - \mu_2)$, $w_0 = \frac{1}{2} w^T(\mu_1 + \mu_2)$ Tai -- \Def{Fišerio tiesinė diskriminantinė funkcija}. \section{Perceptrono evoliucija mokymo metu (klasifikavimo uždavinys)} % 5 % Pakartojam, kas yra perceptronas: % \[ f(w^T x + w_0) % \] % XXX šį skyrių reiktų pertvarkyti Klaidos funkcija \[ w_{sf} = \frac{1}{N} \sum_{\alpha=1}^N \big(t_\alpha - f(w^Tx_\alpha + w_0) \big)^2 \] % ten sf ar st ar kas? šią funkciją minimizuojam. % čia kitas puslapis, tik kažko neskilijuoja...? Tarkime, kad koordinates perkeliam į duo\-me\-nų vidurkį, t.y. vidurkis visada yra 0. % Šito totaliai nesupratau: $\Sigma \Sigma_\alpha = 0$ -- vidurkis, $N_1 = N_2$ -- objektų nėra(?), $w_{t=0} = 0$ -- pradiniai svoriai. $t_\alpha \in \{ -1, +1 \}$. Funkcija pas mus tiesinė $f(x) = x$ % čia kiek suprantu imam 'purelin' neuroną $w_1 = w_0 - \frac{\partial cost}{\partial w^t} = const (\overline{x}^{(1)} - \overline{x}^{(2)}$. Geometrinė prasmė tokia: sujungiame sričių vidurkius atkarpa ir per jos vidurį išvedame statmeną tiesę. Tai -- \Def{Euklidinio atstumo klasifikatorius}. $D(X, \overline{X}^{(2)}) - D(X, \overline{X}^{(1)})$ -- atstumai nuo vidurkio iki tiesės lygūs. Fišerio atveju gautume $W_F = S^{-1} (\overline{X}^{(1)} - \overline{X}^{(2)})$. Per vidurį gauname \[ W_t = \big(S + \underbrace{\frac{2}{\eta(t-1)}}_\text{Haley narys} \begin{pmatrix} 1 & 0 & \ldots\\ 0 & 1 & \ldots\\ \vdots & \vdots & \ddots \end{pmatrix} \big)^{-1} (\overline{X}^{(1)} - \overline{X}^{(2)}) \] T.y. perceptronas duoda tą patį Fišerio klasifikatorių, tik prie diagonalinių elementų pridėtas šioks toks triukšmas, kuris artėja prie nulio, kai $t \to \infty$. \bigskip \paragraph{Atraminių vektorių klasifikavimas} Idėja: tarp artimiausių kaimynų atstumas -- ma\-žiau\-sias. Imame tris artimiausius kaimynus (du iš vienos klasės, trečią iš kitos) ir brėžiam tarp jų tiesę, kad ji būtų labiausiai nuo jų visų nutolusi. % Ar kažkas panašaus. % Šito nesupratau: % "Perceptronas dar gali apversti matricą, kai ši neapsiverčia." % --- 3 paskaita: 2003-03-06 % Pakalbėsim apie regresiją, paskui vėl apie apmokymą. % Klausimas nr 6. Statistinis prognozavimas. \section{Statistinis prognozavimas} % 6 % aka tiesinis prognozavimas? Po klasifikavimo dažniausiai sutinkamas uždavinukas yra prognozavimas. Galima prognozuoti taip: \[ y = \sum w_i x_i + w_0 \] % Pora paveiksliukų iš statistikos. Normalinis bei „atvirkščias U“ (x -- kiek % studentas laiko mokėsi, y -- kokį balą gauna. Kreivė atrodo /~\) % Paveiksliukai Palme. Formulė tinka, jei turime normalinį pasiskirstymą. % Prognozavimas: pvz., metalurgija. Vaistų pramonė (superkompiuteriai) -- % vienas iš pagrindinių taikymų. Valiutų kursai (5 metams į priekį! Ford % Research Labs, Raudys ten dirbo. Kaip sekės, tiesa, neaišku.). Prognozuoja % politiką, akcijų kursus, ... Svarbiausias dalykas -- atrinkti visus rodiklius $x_i$. Na ir žinoti, ką nori prognozuoti (y). % Formulė, programa -- easy. Sunku suformuluoti uždavinį. Vienas iš prognozavimo būdų -- imti vidurkį. Kitas -- imti artimiausią variantą iš turimos imties. Trečias -- mažiausiųjų kvadratų metodas: minimizuojam paklaidų kvadratų sumą \[ c = \frac{1}{n}\sum_{\alpha=1}^n \left(y_\alpha - \sum_{i=1}^p w_i x_i^\alpha + w_0\right)^2 \] Taip daro statistikai. Su neuroniniais tinklais turime \[ c = \frac{1}{n}\sum_{\alpha=1}^n \left(y_\alpha - f\big(\sum_{i=1}^p w_i x_i^\alpha + w_0\big)\right)^2 \] Reikia normuoti prognoziojamą dydį, kad būtų kitimas tarp 0 ir 1: \[ c = \frac{1}{n}\sum_{\alpha=1}^n \left(y_\alpha - \left(f\big(\sum_{i=1}^p w_i x_i^\alpha + w_0\big) - 0.5\right) \cdot \beta \right)^2 \] Šitas daiktas vadinamas standartine regresija Yra ir kitas sprendimo būdas. Kas, jei yra didelių nukrypimų? % pav % Olandai turi atominę elektrinę ant sienos su Belgija, miestuke Borel. Iš ten % ateina 64 rodikliai. Pagal 63 iš jų prognozuoja 64-tąjį. Iš pradžių % mokymas. Paskui jei kas ne taip, iškart turi prognozė sustreikuoti ir turi % užsidekti raudona lemputė. (Ten kažko neuroninis tinklas nelabai tiko, o va % standartinė regresija pats tas.) % Medicina: daaaug indikatorių, jokia seselė nesusigaudys. Reikia kažkaip % prisiderinti prie paciento ir pastebėti nukrypimus. % Tai va, avarinių situacijų detektavimas irgi vienas pritaikymas. % Per egzą gali būti klausimas: išvardinti 20 sričių, kur regresija gali būti % pritaikyta. Ar kažkas tokio. Klausimas „ant galvojimo“. % Ok. Klasikinė regresija: naudojamas matematinis vidurkis. Dideli, % netipiniai nukrypimai negerai. Statistikai turi spec. priemonių su tuo % kovoti. Neuroniniai tinklai tai daro automatiškai. Vidurkis skaičiuojamas \[ \overline{x} = \frac{1}{n} \sum_{i=1}^n x_i \] netipinius nukrypimus reiktų išmesti: \[ \overline{x} = \overline{x}_n \qquad \overline{x}_k = \frac{1}{\sum_{i=1}^k f(x_i - \overline{x}_{k-1})} \sum_{i=1}^k x_i f(x_i^\alpha - \overline{x}_{k-1}) \] kur $f$ stengiasi numesti nukrypimus (žr paveiksliukus palme. Pvz., $f(x) = |1-x|$ kai |x| didelis arba $1$, kai $x$ mažas). Tai yra robastinė regresija. (Robust -- atsparus nukrypimams.) Nuostolių funkcija (kurią reikia minimizuoti) viensluoksniam perceptronui norint robastinės regresijos: \[ c = \frac{1}{n}\sum_{\alpha=1}^n \Psi\Big( y_\alpha - \big(\sum_{i=1}^p w_i x_i^\alpha + w_0\big) \Big) \] Kur $\Psi(x) = x^2$ kai $|x| <= z$ ir $\Psi(x) = \Psi(z)$ kai $|x| > z$. Arba galima dar užapvalinti kampus ties $|x| \approx z$. Problema: kokio platumo $z$ imti? Jei bus platu, bus ta pati klasikinė regresija. Jei bus siaura, ims tik labai siaurius duomenis. Menas yra nusakyti, kas yra „dideli nukrypimai“. % Tiek apie regresiją. % Ok, kiek apie atsiskaitymą. Pagrindindinis rodiklis -- savarankiškas % darbas. Jis po vieną darbelį mailina kad palengvintų mums įsivažiavimą. % Bus paskui robastinė regresija -- prognozuosim Londono biržą. 23 rodikliai % per 3.5 metų, 5 kartus į savaitę. Dvidešimt ketvirtas (tiksliau, pirmas) % -- biržos indeksas. Galima prognozuoti tai pačiai, galima vienai dienai į % priekį (labai gerai gaunasi). Dviems jau nieko neišeis. Mes bandysim % prognozuoti vienai dienai į priekį. Hint, hint: geriausiai veikia alpha = % 17 (alpha = z? regresijos plotis) Yra programėlė order. Reikės kažką % pakaitalioti. Raudžiui pakako dviejų rodiklių 1 ir 11, tik iš dviejų dienų. % % Birža -- ne ekonominis procesas, o (labai primityvus) lošėjų elgesys. % Smulkios žuvys naudoja strategiją „šiandien kilo, reiškia ir rytoj kils“ ir % pralaimi. Didieji rykliai turi gerus kompus, turi specialistų, surenka daug % duomenų, prognozuoja ir laimi. % Reikia žmones matyti kuo dažniau, tada jie geriau vertins. % Savarankiškas darbas: svarbiausiai reikia mokėti savarankiškai formuluoti % uždavinius. % Neigiamas rezultatas irgi rezultatas. Reikia pateikti savo samprotavimus, % kodėl nesigavo. % Tokia formulytė: \sigma^2_{poen?} = \sigma^2_0 (1 + \frac{p}{n-p}) % ateityje bus % Darbo pateikimo forma: % pradžioje turi būti uždavinio formulavimas. Ką noriu pademonstruoti, % gauti, etc. Po to: kokius naudosiu metodus, iš kur duomenis gausiu (pvz % internete). Po to pats darbas: ką dariau, ką bandžiau, ką gavau. Na ir % išvados, pvz., teorinis ir experimentinis grafikas, va kiek nesutapo, % imho todėl ir todėl, lia lia lia. % Kukliai galima sutalpinti į 3 psl. Normaliai 4--5 psl. Nereikia grūsti 30 % psl pilnų visokių neaiškių lentelių. % Visad reikia įvado ir išvadų. Įvado pagrindinė dalis: ką aš darysiu. Jei % sudėtingesnis projektas, reikia dar ir paaiškinti, kodėl tą darysiu. \section{Robastiniai algoritmai klasifikacijoje} % 7 % pav 19:10: du rinkiniai, yra didelių nukrypimų, kurie numeta vidurkį toli. % robastiškumas atmeta tuos nukrypimus ir vidurkis artėja šalia reikiamos % vietos. % Didelė dalis Lietuvos karvių yra su leukoze. Sovietų laikais į tai dėmesio % niekas nekreipdavo (na, CK nariai gaudavo pieną iš atskiros bandos). Dabar % turbūt dar mažiau dėmesio... % Ok, trokštami išėjimai tarp 0 ir 1. Viena klasė 0, kita 1. Pradedam % mokyti. PS čia kartojimas Paklaida \[ c = \sum_\alpha \big( t_\alpha - f\big(\sum w_i x_i^\alpha - w_0\big) \Big) \] ($t_\alpha$ -- norima reikšmė (target)) Apmokymo metu svoriai laiko momentu $t+1$ skaičiuojami \[ W(t+1) = W(t) - \eta \frac{\partial c}{\partial W} \] ($W$ -- vektorius iš $w_i$. $\eta$ -- mokymo žingsnis (kažkaip pasirinktas)) Kadangi f-ja $f$ užsiriečia, tai per dideli nukrypimai nuo diskriminantinės plokštumos duoda daugmaž tokią pat paklaidos vertę, kaip ir maži. Tad perceptronas automatiškai nereaguoja į tolimus nukrypimus. Perceptronas yra automatiškai robastiškas dideliems nukrypimams. O matematikai/ statistikai tik neseniai tai sugalvojo (robastinei statistikai apie 30 metų). % diskriminantinė plokštuma % BTW f-jos f ir \Psi yra tokios, nes jos primena jų grafikus. Asociative % memories. Beje, apie gradientinį mokymo algoritmą. Yra du režimai: stochastinis ir totalinis. Stochastinis metodas: skaičiuojam gradientą kiekvienam mokymo vektoriui atskirai ir darom pataisymą. Jei skaičiuojam gradientą visiems kartu (imam vidurkį) prieš darydami pataisymą, turime totalinį gradientą (dar kartais vadinama batch mode). Stochastinsi lengviau išlenda iš lokalinių minimumų. Totalinis geriau konverguoja jei yra vienas gražus minimumas. Vienasluoksniams perceptronams geriau totalinis, daugiasluoksniams geriau sto\-chas\-ti\-nis. \section{Minimalios klasifikavimo klaidos ir atraminių vek\-to\-rių klasifikatoriai} % 8 % čia su vienasluoksniu perceptronu % Pav 19:31 Prielaida: pasiskirstymas normalinis. Tada gaunam optimalų klasifikatorių. Bet jei prielaida nepatenkinta, negausim mažiausio klaidų kiekio. Kaip padaryti tiesinę diskriminantinę funkciją, kad minimizuotume mokymo metu gautų klaidų kiekį? Literatūroje yra kokie 14-15 būdų. O perceptronai tai daro automatiškai. Mokant perceptroną svoriai auga ir dideli nukrypimai nebeturi įtakos (suveikia funkcijos $f$ užsirietimai). Kuo svoriai didesni, tuo tai labiau pasireiškia. Pvz., atimam $\lambda W'W$ \[ c' = \sum_\alpha \big( t _\alpha - f\big(\sum w_i x_i^\alpha - w_0\big) \Big)^2 - \lambda W'W \] Tai skatina svorių augimą. ($W'$ yra transponuotas vektorius $W$) Po truputį auginant svorius po truputį mažėja klaidų skaičius. Ten faktiškai gaunasi $f$ outputai 0 ir 1, t.y. $c$ (variantas be $\lambda W'W$) sumuoja klaidų skaičių. Jei padalintume iš $n$, gautume klaidų dažnį. % Per egzą galima naudotis viena lapo dydžio špera. Šperą paims ir ten ieškos % klaidų :) Jei klaidų nėra, svoriai auga patys. Jei jie neauga, pridedam tą $-\lambda W' W$ ir pri\-ver\-čiam juos augti. O dabar apie atraminių vektorių klasifikatorius. Jei klasės yra nutolusios viena nuo kitos, tinka daug diskriminantinių plokštumų, kurios daro po 0 klaidų. Kurią reikia pasirinkti? Reikia papildomo kriterijaus. Kokio? Skonio reikalas. Vienas sprendimas: per vidurį -- maksimizuoti atstumą iki artimiausių klasių atstovų. Tuos tris artimiausius vektoriukus (dvimatėj erdvėj; trimatėj bus keturi ir t.t.), nuo kurių imam tiesę, vadinam atraminiais (support vector). Kad gražiau skambėtų, turime ne klasifikatorių, o support vector machine. Beje, atraminių vektorių skaičių galima paimti pagal skonį. Galima spresti matematiškai, taikant kvadratinį programavimą. Žmonės ilgai galvojo, pirmas straipsnis apie tai buvo 1992 m. O perceptronas tai daro automatiškai, dažnai ir geriau. % Ateityje dar bus atraminių vektorių regresija. Mes nagrinėsime atvejį, kai klaidų nėra (klasės nesikerta) Manykim, kad perceptronas jau apmokytas. Kiekvienas taškas ($\equiv$ vektorius) turi indėlį į nuostolių funkciją. $f(...)$ kiekvienam taškui yra labai arti 0 arba 1. Didžiausią indėlį duoda arčiausiai plokštumos esantys vektoriai. Mokai, mokai, gauni maksimalios klaidos klasifikatorių ir jei mokai toliau, svoriai vis dar auga, plokštuma stengiasi patekti į viduriuką. Ir gauni atraminių vektorių klasifikatorių (support vector classifier arba support vector machine). % Šį metodą sugalvojo vienas Raudžio draugas senai senai. Maskvoj jį vadino % obobschionnyj portret, 1974 m. Paskui išvažiavo į Ameriką. Ten sugalvojo % kitą pavadinimą -- support vector machine. Krūčiau skamba ;) Vietoj dvimatės ervdės galima padaryti penkiamatę: $x_1, x_2$ turim, dar pridedam $x_1^2, x_2^2, x_1x_2$. Penkiamatėj erdvėj jau lengviau sudalinti taškus, kad liktų 0 klaidų (jei neišeina gauti 0 klaidų). Ir t.t. $x_1^3, x_2^3, x_1^2 x_2, x_1 x_2^2, ...$. Mokom iki nulinės klaidos ir tada laukiam, kol svoriai išaugs (vienas iš būdų -- palaipsniui didinti žingsnį $\eta$ kai pasiekiam nulinę klaidą, kitas iš būdų -- įvesti tą narį $\lambda W'W$). % Jei turim 100 taškų, galime 99-matėj erdvėj sudalinti į dvi klases be problemų. % Mažesnėse erdvėse sunku. Apibendrinimas: yra du kriterijai. Vienas -- minimizuoti mokymo klaidų kiekį. Antras -- kai jų nelieka, maksimizuoti tarpą. % Praeitą paskaitą buvo: % mokai perceptroną -- gauni Euklidinio atstumo klasifikatorių. % jei duomenys yra gražiuose apskritimuose, gausime iškart idealų atsakymą % po pirmos iteracijos Perceptronas palaipsniui realizuoja visus algoritmus: \begin{enumerate} \item euklidinio atstumo \item reguliarizuota \item fišerio algoritmas arba \item pseudo-inversija \item robastinė \item minimalios klaidos \item atraminių vektorių klasifikatorius \end{enumerate} % apie porą iš jų mums nekalbėjo. % --- 4 paskaita: 2003-03-20 % Kiekvienoj iteracijoj perskaičiuojam svorius: % W_naujas = W_senas - \eta \frac{\partial c}{\partial W} % % kai atsiranda nulinė klaida, išvestinė pasidaro labai maža, tad W pokytis % irgi labai sumažėja. Todėl apsimoka didinti mokymo žingsnį \eta: % % \eta_naujas = \eta_senas * 1.001 % % tai va taip ir veikia atraminių vektorių klasifikatorius -- žr. jo atsiųstą % KeliKlasifikatoriai.m % \section{Klasifikavimo ir prognozavimo klaidų rūšys} % 9 Prognozuoti galima viską -- bet reikia žinoti, kokiu tikslumu. % Oro prognozės prieš daugelį metų: % mesi monetą -- pataikysi 50% % sakysi, kad bus kaip šiandien -- pataikysi 75% % pritaikysi visas meteorologijos žinias -- bus 85% % dabar gal geriau Kaip vertinti tikslumą? Paskaičiuoti paklaidos vidurkį. \[ \sigma_{pr} = \sqrt{\frac{1}{N}\sum_{j=1}^N (y_{tikra,j} - y_{prognozuota,j})^2} \] Bet jei N labai didelis (pvz., prognozuojam kažką visiems Žemės žmonėms)? Jei turim tik dalį duomenų, tai apsimoka juos sudalinti į dvi dalis: mokymui ir testavimui. Jei viską panaudosim mokymui, gausim labai gerą prisitaikymą bet tik tiems duomenims... „Kaip meluoti su statistika.“ Didėjant duomenų kiekiui (kai $N \to \infty$), $\sigma_t \to \sigma_0$, kur $\sigma_0 = \sigma_{pr}$, o $\sigma_t$ -- testinė klaida, Galima apytiksliai įvertinti \[ E \sigma_t^2 = \sigma_0^2 (1 + \frac{p}{N-p}) \] kur $p$ -- požymių skaičius (duomenų dimensija). % Generalizavimo klaida = minimali arba asimptotinė klaida kart kažkas Generalizavimo klaida -- testinės klaidos matematinė viltis. Kitaip tariant, laukiama testinė klaida. % O kas po perkūnais yra \sigma_t??? Perceptrono daromų klaidų skaičius? Klasifikavimo klaidos yra dviejų rūšių: \begin{enumerate} \item objektą iš klasės A neteisingai priskyrėm klasei B \item objektą iš klasės B neteisingai priskyrėm klasei A \end{enumerate} Vienos rūšies klaidos gali kainuoti daugiau, nei kitos. Bendra klaida \[P = q_1 P_1 + (1-q_1) P_2\] kur $q_1$ -- tikimybė, kad objektas priklauso klasei A, $P_1$ -- pirmos rūšies klasifikavimo klaida, $P_2$ -- antros rūšies klasifikavimo klaida. Jei turim du duomenų gabalus su normaliniu pasiskirstymu $N(\mu_1, I)$ ir $N(\mu_2, I)$ ($\mu_1, \mu_2$ -- centrai, $I$ -- vienetinė kovariacijos matrica) su atstumu $\delta$ tarp klasių (Euklidinis atstumas, t.y. $\delta = |\mu_1 - \mu_2|$), tuomet asimptotinė klasifikavimo klaida $P_\infty = \Phi(-\frac{\delta}{2})$ (kur $\Phi$ yra pasiskirstimo funkcija ar kažkas panašaus iš statistikos -- $\Phi(x) = \int_0^x \phi(x)$, kur $\phi$ yra ta monontoniškai didėjanti nuo 0 iki 1 tankio f-ja, atrodo, $\phi(x) = $ tikimybė, kad atsitiktinis dydis yra $< x$). % Beje, $\delta = |\mu_1 - \mu_2|$, kur $\mu_1, \mu_2$ -- klasių vidurkiai % (vektoriai) ir imame jų Euklidinį atstumą. Jei pasiskirstymas nėra toks gražus apvalus, paprastas atstumas nelabai veikia. Yra gudresnė Machaonobi formulė. Apibendrintas atstumas tarp klasių \[ \delta_M^2 = (\mu_1 - \mu_2)' \Sigma^{-1} (\mu_1 - \mu_2) \] kur $\mu_1, \mu_2$ -- klasių vidurkiai (vektoriai), $v'$ -- vektoriaus transponavimas, $\Sigma$ -- tokia baisi kovariacinė matrica (įstrižainėje dispersijos, kitur kovariacija padauginta iš kvadratinių nuokrypių sandaugos ar kžk. panašaus). Paėmę $\delta_M$ vietoje $\delta$ anoje formulėje gauname kitą klasifikavimo klaidos įvertį. Taigi, skirtingi metodai (šiuo atveju buvo Euklido ir Fišerio) duoda skirtingas klasifikavimo klaidas. Svarbu. Kartoju: klasifikavimo klaida priklauso nuo metodo. Pati primityviausia prognozė (turi kažkokį paprastą pavadinimą) -- kitas duomuo bus toks pats, koks šitas. Apsimoka savo prognozę palyginti su šita -- jei pagerini, gerai, jei pablogini, pradėk nuo pradžių. % Kiek suprantu, imi $\sigma_pr$ formulėje $y_{prognoze,j} = y_{tikras,j-1}$. Dar yra koreliacijos koeficientas, kuris kažką pasako. Vidutinė kvadratinė paklaida 5 -- o kas tie 5? ką tai sako? Priklauso nuo uždavinio. Fordui 51\% tikslumo akcijų kurso prognozė yra priežastis padvigubinti laboratorijos finansavimą, kitur gal reikia 99\% tikslumo. NB sakoma 'klasifikavimo klaida', bet 'prognozavimo paklaida'. \section{Klasifikavimo ir prognozavimo klaidų įvertinimo \\ būdai} % 10 % Teoriniu paklaidų skaičiavimu Raudys nepasitiki -- tariam, kad normalinis % pasiskirstymas, imam Machaonobi atstumą, statom į formulę gaunam įvertį. O % jei prielaida apie normalinį daugiamatį pasiskirstymą yra klaidinga? Geriau % tikrinti su tikrais eksperimentiniais duomenimis. Tik duomenys turi būti % homogeniški! Primityviausias metodas -- savos imties metodas (\emph{resubstitution}): ant tų pačių padarau, ant tų pačių testuoju. Bet jei duomenų nedaug, yra pavojus, kad prisiderinsim prie tų duomenų. Jei $N$ ir $p$ artimi, galim gauti labai artimą nuliui paklaidą, bet paėmus kitus duomenis gali būti nei į tvorą, nei į mietą. \[ E\sigma^2_R \approx \frac{\sigma^2_0}{1 - \frac{p}{N-p}} \] $\sigma_0$ -- tikra paklaida, $E\sigma_R$ -- $\sigma_R$ matematinė viltis, $R$ reiškia \emph{resubstitution}. Kitas būdas -- testiniai duomenys (\emph{hold-out} arba \emph{cross-validation} metodas): ap\-mo\-kom su vienais duomenimis, su kitais testuojam. (Galima dar ir pakartoti kelis kartus tuos pačius duomenis skirtingai sudalinus į mokymo ir testinius.) % Matlabe randperm(100) duos išmaišytą masyvą su skaičiais nuo 1 iki 100 Kartais duomenų yra mažai ir gaila dalį aukoti tikrinimui. Tada mokom ant visų išskyrus vieną ir tikrinam ant to vieno. Paskui jį grąžinam ir išmetam kitą, mokom, ant to kito tikrinam. Ir taip su visais iš eilės. Slenkantis egzaminas (\emph{leaving out}). Standartinė cross-validation -- dalinam į dvi dalis, ant vienos mokinam, su kita tikrinam, ir taip 2 kartus -- 2-fold cross-validation. N-fold cross-validation yra tas pats, kas leaving one out. Tas tinka ir klasifikavimui, ir prognozavimui. Šis metodas tinka ir normaliniams ir nenormaliniams duomenims, bet yra jautrus duomenų homogeniškumui (mokom su Lietuvos miestų duomenim, testuojam su Mozambiko, gaunam šnipštą). Grįžtam prie rodiklių: prognozavime tai -- vidutinis kvadratinis nukrypimas bei koreliacijos koeficienta; klasifikavime -- klasifikavimo klaidos įvertis $\hat{P} = \frac{n_\text{klaidų}}{N}$. Beje, $\hat P$ yra atsitiktinis dydis, pasiskirstęs pagal binominį dėsnį $B(P, N)$. Jo dispersija \[\sigma(\hat P) = \sqrt{\frac{P(1-P)}{N}} \approx \sqrt{\frac{\hat P(1-\hat P)}{N}}\] (kadangi binominio skirstymo parametro $P$ nežinome, imame $\hat P$ ir dėl to gauname apytiksliai). Taigi, jei žinome, kad iš 100 stebėjimų paklaida yra 10\%, tai galime tikėtis realiai, kad ji bus 7\%--13\% (pagal vienos sigmos taisyklę), arba 3\% -- 16\% (pagal dviejų sigmų taisyklę). Jei turime 1000 stebėjimų, tai patiklumo intervalas bus tarp 9.4\% ir 10.6\% (dviejų sigmų taisyklė duoda $\sim$96\%). Svarbiausia suprasti, kad įvertinimas yra atsitiktinis dydis. Kuo tiksliau norime įvertinti paklaidą, tuo didesnio $N$ reikia (didesnis $N$ mažina dispersiją ir galime tiksliau įvertinti paklaidą). % Digression į statistiką: 95% patiklumo intervalas -- iš 100-o vidutiniškai % 95 stebėjimai paklius į tą intervalą. Jis daugmaž atitinka 1.96\sigma % taisyklę. 1 sigmos taisyklė -- gal 50% ar kažkas panašaus. Lia lia. % Dažniausiai pateikia vieną sigmą, o toliau galima pasiskaičiuoti. % Londono birzos pvz: alpha yra regresija, su maza alpha gaunam standartine % kvadratine regresija, su didelia alpha gaunam robastiskuma; alpha labai % priklauso nuo duomenu ir niekas nezino, kaip ja parinkineti -- cia galima % pasidaryti PhD is to; londono birzoje alpha=17 buvo geriausias ir dave % 2x maziau paklaidu nei standartine regresija; alpha tame pvz yra paskutinis % parametras. Viena gudrybė apmokant neuroninius tinklus: verta normalizuoti duomenis (pa\-da\-ry\-ti kad sigma = 1 o vidurkis = 0). Kitas "fintas" yra juos dar ir dekoreliuoti. \section{Algoritmo sudėtingumo, mokymo duomenų kiekio ir kokybės ryšys} % 11 \[ E \sigma_t^2 = \sigma_0^2 (1 + \frac{p}{N-p}) \] kur $p$ atspindi algoritmų sudėtingumą, $N$ -- duomenų kiekį, na o $\sigma_t$ -- kokybę. % Generalizavimo klaida = minimali arba asimptotinė klaida kart kažkas % Ten toks grafikėlis... sigma_t artėja prie sigma_0 iš viršaus, o sigma_R iš % apačios (viršus -- klaidų sk. testiniuose duomenyse, apačioje -- mokymo % duomenyse; pagal tą formulę gauname, kad sigma_R <=0 kai N <= p, t.y. kai % algoritmo sudėtingumas viršyja duomenų kiekį, gauname idealų modelį, % nedarantį klaidų. Klasifikavimo klaidos pagal Euklido metodą (Euklidas BTW tai perceptronas po pirmos iteracijos): \[ EP_N \approx \Phi\left(-\frac{\delta}{2} \cdot \frac{1}{\sqrt{1+\frac{2p}{N\delta^2}}}\right) \] Jei mokom percpeptroną iki Fišerio lygio, gaunam \[ EP_N \approx \Phi\left(-\frac{\delta}{2} \cdot \frac{1}{\sqrt{1+\frac{2p}{N\delta^2}}} \cdot \frac{1}{\sqrt{1+\frac{p}{2N+1-p}}} \right) \] ($N$ -- stebėjimų sk., $N_1$ -- stebėjimų skaičius vienoje klasėje) Klaida iš pradžių didesnė, linksta smarkiau. Kitaip tariant, kuo ilgiau mokom percpetroną (daugiau iteracijų), tuo daugiau mo\-ky\-mo duomenų reikia. Kuo didesnis sudėtingumas (tik čia sudėtingumas jau yra algoritmo sudėtingumas, o ne $p$ įvertis), tuo daugiau duomenų reikia mokymui. Viena iš problemų -- „permokymo“. Kuo sudėtingesnis organizmas, tuo ilgiau mokosi. Palyginimas: katė ir studentas. % Pritaikymai realiam gyvenimui: laikas nustoti mokytis iš tėvų/dėstytojų etc. % Pasaulis keičiasi. Už sudėtingesnį algoritmą moki didesniu duomenų kiekiu. % TANSTAAFL Vienas iš būdų, kaip patikrinti, ar duomenų algoritmui pakanka -- naudoti slenkantį egzaminą. Su vienu paskirstymu gaunam 5\% klaidų, su kitu paskirstymu gaunam 15\% -- blogai, didelis skirtumas, duomenų nepakanka. Reikia imti paprastesnį algoritmą. Arba galima vertinti paklaidas teoriškai (jei duomenys normaliniai) ir paskui žiū\-rė\-ti, ar praktiškai klaidų tikimybė panaši. Jei ne, blogai, nepakanka duomenų arba per sudėtingas algoritmas. Beje, iš anksčiau: viena idėja -- reikia triukšmo duomenyse. Algoritmas turi prisitaikyti prie triukšmo! Duosim idealiai švarius mokymo duomenis ir bus neatsparus tikram gyvenimui. % Higiena: per daug higienos kenkia, organizmas pasidaro neatsparus. % Back to now: viena iš sekančių temų -- kaip mažinti požymių kiekį, ir % apskritai algoritmo sudėtingumą. % --- 5 paskaita: 2003-04-03 % Namų darbai vėl: iniciatyva, kūribingumas! % Pakanka pastangų, o ne rezultato. Jei stengsimės, mūsų neskriaus. % Paskaita bus ne gegužės 1, o gegužės 8 % Paskutinė paskaita gegužės 15 % Taigi, liko paskaitos: 04-03, 04-17, 05-08, 05-15. % Egzas: leidžiama špera -- 1 didelis lapas % Per perlaikymą bus sunkiau, jokių šperų \section{Daugiasluoksnis percpetronas ir jo mokymas} % 12 % Perceptrono su 1 paslėptu sluoksniu diagrama: % kriterijai x_1 ... x_p % paslėptas sluoksnis: h neuronų % s_i = \sum_{j=1}^p W_{ij} x_j + W_{i0} kur i = 1..h % y_i = f(s_i) = (1+e^{-s}_i)^{-1} % išorinis sluoksnis: k neuronų % \sigma_i = f(\sum_{j=1}^h v_{ij} y_j + v_{i0}) kur i = 1..k % flashback f(x) := (1+e^{-x})^{-1} -- sigmoidinė funkcija; angl logistic % sigmoid Galima taikyti atpažinimui. Pvz, angliško teksto atpažinimas: $k=26$, po vieną klasę kiekvienai raidei. Kurioj klasėj $\sigma_i$ reikšmė didžiasia, pagal tai ir atpažįstam. Trokštamas išėjimas: $\sigma_i = 1$, $\sigma_j = 0$ jei $i \ne j$. Jei naudojam prognozavimui, dažniausiai apsieinam be sigmoidinės f-jos: \[ \sigma_i' = \sum_{j=1}^h v_{ij} y_j + v_{i0} kur i = 1..k \] Arba galima normuoti į intervalą $[0, 1]$, bet praktikoje to niekas nedaro. Praktiškai visi naudoja neuroninį tinklas be netiesinių elementų išėjimo sluoksnyje. Va tokia daugiasluoksnio perceptrono architektūra. Jo mokymas sudėtingesnis, nei vienasluoksnio perceptrono. Daugiasluoksnis perceptronas gali daryti netiesinius atskyrimo paviršius. Daugiasluoksnis perceptronas su vienu paslėptu sluoksniu yra universalus aproksimatorius: galima gauti bet kokio sudėtingumo atskyrimo paviršių. Funkcijos neteisiškos, turi lokalių maksimumų, optimizavimas sudėtingas. Kaip jį mokyti? Kaip visad, reikia įsivesti nuostolių funkciją ir ją minimizuoti. Didžiulė nuostolių funkcijos formulė: \[ cost = \sum_{l=1}^k \sum_{s=1}^k \sum_{t=1}^{N_s}(t^l_{st} - \sigma^l_{st})^2 \] $t^l_{st}$ -- trokštamas išėjimas ($1 \le l \le k$ -- išėjimo neurono numeris, $st$ -- mokymo vektoriaus numeris), $\sigma^l_{st}$ -- gautas $l$-tasis išėjimas testavimo vektoriui $x_{st}$, $k$ -- klasių skaičius $N_s$ -- mokymo vektorių skaičius $s$-tajai klasei. Išėjimas skaičiuojamas \[ \sigma^l_{st} = f(\sum_{j=1}^h v_{lj} y_j^{st} + v_{l0}) \] kur \[ y_j^{st} = f(\sum_{i=1}^p w_{ji} x_i^{st} + w_{j0}) \] paslėptų vektorių išėjimai. Čia įėjimo vektoriai yra $\mathbf{x^{st}} = (x_i^{st})$ ($s$-tosios klasės $t$-asis vektorius, $1 \le s \le k$, $1 \le t \le N_s$, $1 \le i \le p$). Mokymo algoritmo bendras principas: \[ \mathbf{W}_{z+1} = \mathbf{W}_{z} - \eta \frac{\partial cost}{\partial \mathbf{W}}\Bigg|_z \] kur $z$ -- mokymo žingsnis (iteracijos numeris), $\mathbf{W}$ -- bendras visų perceptronų svorių vektorius. \[ \mathbf{W} = (w_{10}, w_{11}, \dots, w_{1p}, \dots, w_{h0}, \dots, w_{hp}, v_{10}, v_{11}, \dots, v_{1h}, \dots, v_{k0}, \dots, v_{kh}) \] Išvestinė \[ \frac{\partial cost}{\partial \mathbf{W}} = 2 (t^l_{st} - \sigma^l_{st}) \cdot f'(\sum_{j=1}^h v_{lj}y_j^{st} + v_{l0}) \dots \] Algoritmas vadinamas error back-propagation. % error back-propagation -- klaidos sklidimas atgal. % s/išvestinė/gradientas/ ? Kai svoriai maži, išvestinė didelė. Kai svoriai išauga, išvestinė priartėja prie $0$, mokymas labai labai smarkiai sulėtėja. % Atskiras klausimas, % Matlabe yra Nguen widrow[sic?] initialization % Džoukas: kodėl Paksas gali būti geru prezidentu? Nes turi požiūrį iš % viršaus. % Prieš 13 m. neuroniniai tinklai turėdavo po 100000 svorių. Mokė juos po 7 % mėnesius. OCRui. Source'as: 20x30 -- 600 pixelių. Bet į kiekvieną neuroną % paduodavo 5x5 kvadratėlius, paslinktus po truputį. Pirmame sluoksnyje daug % neuronų buvo vienodų, in fact, buvo tik 4 rūšys neuronų: atpažindavo % vertikalią tiesią liniją, horizontalią, dvi diagonalias. Taip sumažino % svorių kiekį. Tinklas turėjo 7 sluoksnius. Mokė jį su back-propagation % algoritmu. % Tai - viena iš "weight sharing technique". % Prieš porą metų kvapų atpažinimo tinklus mokė 3 paras, \section{Daugiasluoksnio perceptrono mokymo ypatybės} % 13 Pirma ypatybė -- jis labai lėtai mokosi. Svoriams padidėjus išvestinė labai smarkiai sumažėja. Svorių labai daug. Pakliūna į lokalinius minimumus, iš jų ne visada iššoka. % Laibai vaizdinga demonstracija ant lentos: papiešti poros svorių kitimą % laikui einant: pasisukioja, pradeda eiti tiesiai, lėtėja, lėtėja, lėteja... % beveik sustoja. Padidinus \eta vėl paeina ta pačia kryptim ir vėl sulėtėja % iki sustojimo. Kaip su tuo kovoti? Vienas iš būdų -- antros eilės metodai (skaičiuoja antros eilės išvestines, bet jie jautresni lokaliniams minimumams). Levenberg-Market ar tai conjugate gradients metodas ima antros eilės išvestines, o kadangi jų daug ($|W|^2/2$), ima tik diagonalines. Konverguoja greičiau, bet labau greitai patenka į lokalinį minimumą. Su lokaliniais minimumais kovoja multistart metodas. Mokai 10 kartų nuo 0 su skirtingais pradiniais svoriais. Iš jų 3 kartus gaunas gerai (3-5\% klaidų), 7 labai prastai (15\% klaidų)... % Raudys jau back-propagation nebenaudoja, naudoja šitą, gradientinį. % O šiaip daug kas jį tebenaudoja. Būtent dėl lokalinių minimumų. % Dar ateity pasakos apie genetinius alg. Jie geriau susidoroja su % lokaliniais min, bet konverguoja lėčiau už gradientinį. Kitas būdas -- didinam mokymo žingsnį. Pvz, kas $50$ iteracijų pažiūrim, ar su\-ma\-žė\-jo nuostolių funkcija. Jei sumažėjo, padidinam $\eta$ (padauginam iš $1.07$). Jei padidėjo, sumažinam $\eta$ (padauginam iš $0.7$). % Šitą galima ir su vienasluoksniu perceptronu daryti. Tas jau buvo: % atraminiai vektoriai. Kiek konkrečiai didinti \eta priklauso ir nuo % duomenų. 1986 m. Rumelharto ir dar kažkieno straipsnis pradėjo naują erą neuroniniuose tinkluose: sigmoidinė funkcija. Jie pasiūlė trokštamų išėjimų reikšmes imti 0.1 ir 0.9 vietoje 0 ir 1, kad svoriai neišaugtų per daug dideli. Tada ir išvestinė bus toli gražu ne 0. Sumažėja plokščios vietos išėjimo sluoksnyje (paslėptame sluoksnyje nesumažėja) % TANSTAAFL. Lygiai taip pat nėra ir to blogo, kas neišeitų į gerą. Išlošiam didesnę išvestinę -- greitesnis mokymas. Pralošiam va ką: jei t = 0/1, tai funkcija cost yra lygi klaidų kiekui -- taigi oficialiai mes minimizuojam klaidų kiekį, which gives us a warm and fuzzy feeling. Su 0.1/0.9 jau matuojam nežinia ką. Už tai mokam dar didesniu skirtumu nuo klasifikavimo klaidos. % Ką daryti? Apie tai kalbės vėliau. Baisiausiais svarbus dalykas yra pradinės sąlygos. $\mathbf{W_0}$ Vienasluoksniu atveju apsimoka nustumti centrą tarp klasių į koordinačių pradžią, ir pradėti mokyti nuo nulinių svorių. Čia neišeis: jei visus paslėptus neuronus mokysim su tai pačiais pradiniais svoriais, jie visi bus vienodi... nebebus jokio daugiasluoksnio perceptrono. Pradinė sąlyga: $\mathbf{W}_0$ svoriai skirtingi. Paprastai juos parenka intervale $[-a, a]$. $a$ parenkam tokį, kad pradinės įėjimo sluoksnio perceptronų reikšmės \[ \sum_{i=1}^p w_{ji} x_i^{st} + w_{j0} \] reikšmės būtų pakankamai mažos. Dažnai dar įėjimo reikšmės normalizuojamos, kad pakliūtų į intervalą $[0, 1]$ (taip daro Matlabas), arba kad jų dispersija būtų arti $1$, o vidurkis $0$ (taip daro Raudys). Tai labai svarbu! % Perka paketą už $10,000 ir nieko jiems neveikia. Meta į šiukšlių dėžę. % Ištraukia, normalizuoja duomenis ir viskas veikia! % Nguen-Widrow inicializavimas. Paslėptas sluoksnis bei išėjimo sluoksnis % inicializuojami vienodai. Dar apie pradines sąlygas: jei pradedi nuo gerų pradinių sąlygų ir laiku sustoji, rezultatas būna geresnis. % Vaizdingas grafikėlis. Kuo geriau inicializuoji, tuo geriau -- vidutiniškai % arčiau tikro minimumo. Ir svarbu laiku sustoti! % Kuo geriau pradedam, tuo anksčiau reikia sustoti. % Yra krūva būdų gerai pradėti. Ateityje: gabalais tiesinis klasifikatorius. % Dar vienas iš būdų: pirma pamokyk su paprastesniu algoritmu, o jau paskui su % tikrais duomenimis. % Data mining: dėsningumų paieška dideliuose duomenyse. Duomenys netelpa. % Tarkim, turim 10 Gb. Skaldom į 10 gabalų po 1 GB. Apmokom su 1, laiku % sustojam. Pradedam nuo tos galutinės padėties, apmokom su 2 gabalu. Ir % t.t. Kartojam: \begin{enumerate} \item kai $|W|$ auga, $f' \to 0$, \item lokaliniai minimumai, \item didinam arba mažinam mokymo žingsnį priklausomai nuo pasisekimo. \item trokštami išėjimai -- imam ne 0 ir 1, o 0.1 ir 0.9. \item pralošiam lygybę cost = klaidų kiekis \item pradinės sąlygos: svoriai skirtingi ir pakankamai maži \item pradiniai duomenys normalizuoti -- arba $0 <= x_i <= 1$, arba $Ex = 0$ (vidurkis) ir $\sigma = 1$ (dispersija) \item gerai pradėti ir laiku sustoti! \end{enumerate} % Trečias namų darbas: daugiasluoksnis perceptronas. Reikia pademonstruoti % kai kuriuos iš šių efektų. % Namų darbo reikia ant popieriaus % VU vieną kartą 5 studai pateikė tą patį darbą -- 100% identiška išskyrus % pavardę. Bet tik 1 kartą, aukštas nusirašinėjimo lygis! % Dar apie namų darbą: % „kas yra ant ašių“? Paveiksliukai be captionų, ašys be labelių, nėr % paaiškinimų, kas yra kas, etc -- atkreipti dėmesį. \section{Duomenų nuosavos reikšmės ir mokymo žingsnis. Duomenų transformavimas prieš mokant} % 14 % Paveiksliukas: labai sunku atskirti klases, jei jos yra tokios siauros greta % viena kitos ir labai siauras tarpas tarp jų. Atsiskiria 100%, bet % perceptronas mokosi nepaprastai sunkiai, labai lėtai konverguoja, ypač % daugiamatėse erdvėse. % Vadovėliuose labai retai į tai kas kreipia dėmesį. Pagal Raudį šis dalykas % yra labai svarbus. Nuostolių funkcija \[ cost = \frac{1}{N_1+N_2} \sum_{i=1}^2 \sum_{j=1}^{N_i} (t_{ij} - W'x_{ij} - W_0)^2 \] Jei $Ex = 0$, galima imti $W_0 = 0$ ir supaprastėja funkcija: \[ cost = \frac{1}{N_1+N_2} \sum_{i=1}^2 \sum_{j=1}^{N_i} (t_{ij} - W'x_{ij})^2 \] Tarkime $\widehat{W}$ yra minimumas: \[ cost_{min} = \frac{1}{N_1+N_2} \sum_{i=1}^2 \sum_{j=1}^{N_i} (t_{ij} - \widehat{W}'x_{ij})^2 \] tuomet \begin{align*} cost & = \frac{1}{N_1+N_2} \sum_{i=1}^2 \sum_{j=1}^{N_i} (t_{ij} - (W + (\widehat{W}-W)'x_{ij})^2 \\& = cost_{min} + (W - \widehat{W})' K (W - \widehat{W}) \\& = cost_{min} + (W - \widehat{W})' \Phi \lambda \Phi' (W - \widehat{W}) \\& = cost_{min} + U' \lambda U \end{align*} kur \[ K = \frac{1}{N_1 + N_2} \sum \sum x_{ij} x_{ij}' \quad\text{(kovariacinė matrica)} \] ir \[ U = \Phi'(W - \widehat{W}) \] Kovariacinė matrica \[ K = \Phi \lambda \Phi' \] kur $\Phi$ -- ortogonali matrica ($\Phi \Phi' = \Phi' \Phi = I$ -- vienetinė matrica). Matricos $\Phi$ eilutės bus matricos $K$ tikriniai vektoriai. $\lambda$ yra įstrižaininė matrica, kurios įstrižainėje juos atitinkančios tikrinės reikšmės $\lambda_1, \dots \lambda_p$ -- dispersijos. Vektoriai yra kryptys, liambdos -- dispersijos tomis kryptimis. % [U, D, V] = svd(K) -- signular value decomposition -- skaido matricą į % tikrines reikšmes, U = \Phi, D = diagonalinė matrica, V = U jei matrica % simetrinė, o jei ne, bala žino kas Išvestinė nepriklauso nuo $cost_{min}$ nario, tik nuo to $U'\lambda U$. Kitaip tariant, pasukam erdvę ir vietoje W gauname U. Čia lengviau konverguos. Mokymas yra \[ U_{z+1} = U_z - \eta \frac{\partial cost}{\partial U} \] Išvestinė \[ \frac{\partial cost}{\partial U} = 2 \lambda U_z \] tad \[ U_{z+1} = (I - 2\eta \lambda) U_z \] Kad seka konverguotų, turi būti \[ \forall i: |1 - 2\eta \lambda_i| < 1 \] (Pakanka paimti tik maksimalią $\lambda$ reikšmę). Tad reikia parinkti pakankamai mažą $\eta$: \[ \eta < \frac{1}{\lambda_{max}} \] Bet kuo mažesnė $\eta$, tuo lėtesnis mokymas. Taigi, jei duomenys tokie bjaurūs ir nesimoko, vienas iš būdų yra pasukti erdvę ir sunormuoti duomenis: \[ Z = \lambda^{-\frac{1}{2}} \Phi X \] Tuomet visomis kryptimis $\lambda$ yra vienodi ir turime vieną bendrą $\eta$ visoms kryptims. Tas labai pagreitina. Jei duomenys normaliniai, tai jau po pirmos iteracijos gauname teisingą Euklidinį klasifikatorių. % Šita formulė yra išvesta regresija. Nėra netiesinės f-jos etc, bet tai % regresija. Ką daryti su daugiasluoksniu perceptronu, vienas Dievas težino -- daug per\-cep\-tro\-nų, neaišku, kuria kryptimi sukti.... Prie tų punktų prirašom \begin{enumerate} \item[9.] reikia pasukti duomenis, transformacija yra $\lambda^{-1/2} \Phi$ \end{enumerate} % --- 6 paskaita: 2003-04-24; pražiopsojau... % Kartojimas Daugiasluoksnio perceptrono atveju duomenų nepasukiosi/nepanormalizuosi, kad lengviau būtų mokytis. Jei skiriamasis paviršius labai jau sudėtingas ir perceptronas lėtai mokosi, tai galime pridėti triukšmo -- aplink rutuliukus pribarstyti atsitiktinai daugiau rutuliukų, t.y. padidinam mokymo duomenų kiekį. Tada skiriamasis paviršius „išsitiesins“ -- supaprastės (nors atsiras daugiau klaidų). Kad svoriai neišaugtų pridedamas reguliarizavimo narys (weight decay) prie cost funkcijos: \[ ... + \lambda W' W\] priešingas efektas gaunamas (kad svoriai augtų), kai atimamas narys \[ ... - \lambda V' V\] (t.y. yra aspektų, kai šito reikia) % Raudžio atsiųsta programėlė mokosi Levenbergo-Market ar tai back-propagation % metodu. Šitas metodas lengvai įkrenta į lokalų minimumą. \section{Duomenų transformacija} % 15 % Kaip sumažinti požymių kiekį? Bus 2 metodai Prognozavimo paklaida lygi $\sigma_{pr}^2 = \sigma_0^2 \left(1 + \frac{p}{n-p}\right)$, t.y., kuo daugiau požymių imame, tuo didesnę paklaidą gauname. Fišerio klasifikatoriaus paklaida: \[ EP_{kl} = \Phi \left(\frac{\delta}{2} \frac{1}{\sqrt{(1+\frac{2p}{N\delta^2})(1+\frac{p}{N_1+N_2})}}\right) \] elgiasi taip pat. Taigi, požymių skaičius $p$ turi būti nedidelis. Kaip žinoti, kuriuos požymius imti? Vienas iš būdų -- \Def{požymių išrinkimas}. Pvz., turime požymius \[ X = \left[ \begin{array}{l} x_1\\x_2\\\vdots\\x_p \end{array}\right] \] ir atrenkame \[ X' = \left[ \begin{array}{l} x_7\\x_{1012}\\x_{38779} \end{array}\right] \] Kitas būdas -- \Def{transformacija (išskyrimas)} Pvz., turime požymius \[ X = \left[ \begin{array}{l} x_1\\x_2\\\vdots\\x_p \end{array}\right] \] ir išvedame \[ Y' = \left[ \begin{array}{l} y_1\\\vdots\\y_r \end{array}\right] = T \cdot X \] kur $r << p$, o $T$ -- transformacijos matrica. \[ y_i = \sum_{j=1}^p t_{ij} x_j \] \paragraph{Pagrindinių komponenčių metodas} % populiariausias Reikia taip suprojektuoti duomenis, kad viena (pirma) kryptimi jų išsibarstymas būtų didžiausias, antra -- mažesnis, trečia -- dar ma\-žes\-nis ir t.t. Kaip tų krypčių ieškoma: suskaičiuojam duomenims kovariacinę matricą \[ K = \frac{1}{n-1} \sum_{j=1}^n (X_j - \overline{X}) (X_j - \overline{X})^T \] % Matlabe K = cov(Dx); % kur Dx -- matrica iš p stulpelių ir n eilučių Matricą $K$ galima užrašyti tokiu pavidalu: $K = G \cdot D \cdot G'$, kur $D$ yra diagonalinė matrica, o $G$ -- ortogonali matrica ($GG' = I$). % Matlabe G ir D radimui yra komanda % (G, D, Ga) = svd(K); -- singular value decomposition $G$ -- posūkio matrica (gaunama su minimalia paklaida). % jei duomenys neužsivertę; jei užsivertę, gali neišeiti. % XXX: o ką tai reiškia??? Tai va, vietoje matricos $T$ galima naudoti matricą $G$: $Y = X' G$ ($X'$ turi vieną eilutę ir $p$ stulpelių, iš $G$ imame $p$ eilučių ir tik pirmuosius $r$ stulpelių; likusius stul\-pe\-lius išmetame). $Y$ kovariacinė matrica yra $D$ (tiksliau, pirmos $r$ eilutės/stulpeliai). Beje, šis metodas leidžia iš mažesnio skaičiaus komponenčių atstatyti likusias -- t.y. turint $Y$ galima gan tiksliai atgaminti $X$. \bigskip Dažnai iš pradžių požymiai išrenkami, o paskui transformuojami, t.y. naudojami abu būdai. % Žr. Fooley-Sammon optimal discriminant plane (optimali diskriminantinė % plokštuma). % Žr. dar straipsnį apie požymių išskyrimus % Jei turime $t_{1j}$, tai $t_{2j}$ ieškomas toks, kad \sum_j t_{2j}t_{1j} = 0 % t.y. daromas 2 perceptronas su tokia sąlyga ir % min_{t_2} Cost(t_2) = Cost_{SLP}(t_2) + \lambda (\sum_j t_{2j}t_{1j})^2 % t.y. ieškom tokios krypties, statmenos pirmai, kad geriausiai skirtų klases. \section{Požymių atrinkimo algoritmai} % 16 \begin{enumerate} \item „Daryk, kaip darė kiti“ % -- apie ką čia??? \item Imti požymius po vieną, su jais klasifikuoti/prognozuoti ir išrinkti tuos po\-žy\-mius, su kuriais geriausiai gaunasi. Bet šitai ne visada gerai pasiteisina: būna, kad po vieną nelabai gerai parodo, o poroj išprognozuoja klasifikatorių be klaidų, \item Nagrinėti požymius po 2 ar daugiau. Jei požymių nedaug, tai viskas gerai, bet jei daug, tai tokių tuplų susidarys labai daug. Tada galima iš pradžių išrinkti tarkime 100 geriausių ir jau tada nagrinėti po 2 (bendru atveju po n). Arba galima atsitiktinai parinkti pvz. 5000 derinių po 2 ir iš jų išsirinkti geriausią. \item Požymių atrinkimas su paskatinimu -- remiantis tuo, kad geriausi požymiai dažniau pasitaiko, nei blogesni. Tai kažkaip (kaip??) atskirti $m$ dažniausiai pa\-si\-tai\-kan\-čių požymių ir iš jų rinkti pilnu perrinkimu $n|$ reikalingų požymių. Apriorinėm tikimybėm išrenkam kažkokį požymių rinkinį. Įvertinam -- pvz., paskaičiuojam klaidą. Ir taip daaaug rinkinių. Išrenkam tada dešimt geriausių rinkinių. Ir pažiūrime tuose dešimtyje, kokie požymiai geriausiai pasirodo. \item \emph{forward selection} -- atrenkam 1 geriausią. Tada bandom jo kombinacijas su likusiais. Atrenkame antrą požymį -- jau turime porą. Tada bandome tų dviejų kombinacijas su likusiais ir t.t. Šis būdas vadinamas \Def{nuosekliu pridėjimu}. Yra dar \Def{nuoseklus atmetimas} -- analogiškai, tik atvirkščiai: atmetame blogiausius požymius. Yra dar ir šių dviejų metodų kombinacijos. \item Genetiniai algoritmai. \end{enumerate} Požymių rinkiniai skirtingais metodais gaunami skirtingai, bet dažniausiai jų paklaida yra panaši. Moralas: nereikia siekti tobulumo. \section{Požymių išskyrimas su neuroniniu tinklu} % 17 Klasikinis būdas išskirti požymius yra toks: turime perceptroną su $x_1, \dots, x_p$ įėjimais, kažkiek paslėptų neuronų ir $p$ išėjimų. Paslėptų neuronų turėtų būti $r$ -- tiek, kiek mums reikia požymių. Idėja tokia: išėjimų reikšmės turi būti tokios pačios, kaip ir įėjimų. O vidinis paslėptas sluoksnis juos suspaudžia. Išskirti požymiai yra vidinių paslėptų neuronų duodamos reikšmės prieš paduodant jas sigmoidinei funkcijai. % paveiksliukas iš dviejų sluoksnių % modifikuojame su daugiau neuronų % kitas paveiksliukas iš trijų sluoksnių % viduriniame -- tiek neuronų, kiek požymių norime palikti Žr. AANN -- auto asociatyviniai neuroniniai tinklai % Antras būdas: kažkoks paveiksliukas, kažkoks skiriamojo paviršiaus grafikas % Tokio tinklo tikslas: pavaizduoti ekrane, t.y. atskirti dvimatėj plokštumoj % Taigi daugiasluoksnis perceptronas gali būti panaudomas požymių išskyrimui Galima pritaikyti duomenų vizualizacijai (pavaizdavimui dvimatėje ar trimatėje erdvėje). % --- 7 paskaita: 2003-05-08 % 10 minučių vėlavau. čia mano science fiction: \section{Duomenų klasterizavimas (grupavimas)} % 18 Problema: nehomogeniniai duomenys, modeliavimas nesiseka. Reikia sus\-kai\-dy\-ti duo\-me\-nis į klasterius ir juos modeliuoti atskirai. % va čia įėjau. lenta dar buvo tuščia % Grafikėlis: x -- income per capita, y -- gyvenimo trukmė. Toks įdomus % išsidėstymas. Pasirodo, yra 2 gyvenimo būdai: Olandija etc -- kuo daugiau % uždirbi, tuo geriau gyveni; Mozambikas etc -- kuo daugiau uždirbi, tuo % daugiau kenksmingų įpročių gali sau leisti, tuo trumpiau gyveni. % Picas kameroj % Šios paskaitos tema: kaip nagrinėti duomenis, jei jie nehomogeniški. % Kažką bendro su regresija. % Paveiksliukas. Dviejų neuronų suma -- gaunam tokią \Phi formos kreivę Nehomogeniniai duomenys. Pasiskirstymo tankis \[ f(x) = \sum_{i=1}^{k} q_i f_i(x) \] yra $k$ komponenčių suma. % Paveiksliukas: dviejų komponenčių suma -- pasiskirstymas va toks. Reikia nehomogeninius duomenis suskirstyti į tokias klases prieš nagrinėjant. % Anecdote: anglijoj gyventojų surašymas, kažkoks bankas bandė pagal tai % nustatyti, kam reikia duoti paskolas. Išsiaiškino, kad pagal pašto indeksą. % :) Pasirodo, ten pas juos gyvenimo rajonas labai priklauso nuo visuomeninės % padėties. Dažniausiai $f_i(x)$ yra normalinio pasiskirstymo -- $f(x, \mu_i, \Sigma_i)$. Bet labai daug parametrų. Galime supaprastinti tardami, kad visos $\Sigma_i$ yra diagonalinės matricos -- netiesa, bet paprasčiau. Daug greitesni algoritmai yra euristiniai. Euristika -- paimta iš lubų sveiko proto taisyklė pagal principą „man taip atrodo“. Pavyzdys: n tašku. "Man atrodo", kad yra tiek grupių -- taip ir suskirstom, paimam kiekvienos grupės centrą, tada tiesiog ieškom, prie kurio centro taškas artimiausias, tai grupei ir priskiriam. Šis algoritmas vadinamas $k$ vidurkių algoritmu ($K$-means algorithm). Jis labai dažnai naudojamas. Pirmasis. O paskui sugalvojo dar 200 ar 400. Prieš 20 metų buvo disertacijų bumas -- sugalvojam naują, parodom, kad veikia, ginam disertaciją. Paskui pamatė, kad naudos 0 ir grįžo prie paprasčiausių algoritmų. % Jei kas nori, Raudys gali duoti kažkokių jo draugo programų. Google for % Duin (pavardė) Delf ar tai Delft (miestas Olandijoje, kažkada buvo sostinė). % Duin Pattern Recognition Group or somefing. % Užsieniečiai -- programas reikia pirkt, o mokesčių nereikia slėpt. O mes va % dabar užsirašysim į jų Europos sąjungą. Ir pamokysim juos :-) Paprasčiau paaiškinti, jei yra tik du centrai. Imam du taškus ir vedam per vidurį statmenį. Tada vienai grupei suskaičiuojam vieną vidurkį, kitai grupei antrą. Užmirštam pirmą skiriamąją liniją ir vedam statmenį per tų dviejų vidurkių vidurį. Kartojam. Po kelių iteracijų jis nusistovi ir nustoja slankioti. Paskui pradedi nuo pradžių su kitais pradiniais taškais -- ir taip kokius 8 kartus. Paimi tą variantą, su kuriuo vidutinis atstumas iki centro yra mažiausias. % XXX: o čia tas pats, ar jau kitas algoritmas? % Žmogaus akis -- geras daiktas, daugelį algoritmų praneša. Dvimatėj erdvėj. % Trimatėj jau sunkiau, o keturmatėj išvis kapas. % Pora picų su 3 taškais. % labels = Kmeans(D, k, m) % D -- duomenys, k -- kiek grupių, m -- kiek bandymų \medskip Kitas algoritmas: suskaičiuojam atstumus tarp visų mokymo vektorių porų. Artimiausias poras sujungiam poromis. Tada jungiam poras, kurių vidurkiai panašiausi. Jei kas labai toli, nejungiam. Ir t.t. Gaunam tokį medį. Tada pasirenkam kažkurį lygį ir kiek šakų yra žemiau jo, tiek ir bus klasių. Tai vadinama \Def{dendrograma}. % Paveiksliukas. % Kažkas sudarė pasaulio kalbų dendrogramą. Dvi: pagal žodžių panašumą ir pagal % gramatikos panašumą. Viena neišpręsta problema -- o kokią $k$ reikšmę pasirinkti? Niekas nežino. Reikia kažkaip pasirinkti, kad išeitų paskui geriausiai. % Klausimas baigėsi. % Egzas: Žemaičio auditorija, 3 vienodi klausimai visiems, mes parašom % Namų darbai: dabar visi gaus po max. jei ne tragiški ND, visi kas vėliau, % turės apsiginti "kodėl tu pridėjai kažką naujo". % Egzas 4 d. 9:30 atrodo % Perlaikymas 20 d. % Apie kažkurią užduotį šneka -- atrodo 3-iosos 1 dalį. Pvz. galima paimti % 50% duomenų mokymui, 50% testavimui. Iš pirmos pusės apmokom su mažu % gabaliuku, testuojam, gaunam 5% klaidų. Apmokom su visais, test, gaunam 4% % klaidų. Darom išvadą: kuo daugiau duomenų apmokymui, tuo geriau. Šito % pakanka. % O dabar antrą. % Kas geriausiai gaus, gaus 1 balą per egzą. Kiti du/trys irgi. % 3 darbas -- juokas: paleidi ir aprašai. Jei ne paskutiniu momentu atneši, % 4 užduotis: tą patį, ką darėm su 1,2,3, tik reikia suformuluoti savo sąlygą. % Paimti savo duomenis. Etc. % Vertinimas: už pratybų 1, 2, 3 -- 2 balai, už pratybų 4 -- 2 balai, už egzą % -- 6 balai. Galima susitarti, kad už egzą 5 ir už pratybas 5 (4-toji užd. % 50%). % Duoda extra 11-tą balą už namų darbus -- originalumas, idėjos, etc. % 4tą darbą galima atnešti ir į konsultaciją. % Konsultacija: pirmadienį (birželio 2 d) vakare 18 val. po darbo čia fakultete. % Recap: perlaikymas 20 d. 15 val. pas jį MII. \section{Radialinių bazinių funkcijų neuroninis tinklas} % 19 Jie -- antri pagal populiarumą po perceptronų. Tinka ir klasifikavimui, ir prognozavimui. Idėja: prielaida, kad duomenys nehomogeniški. Pavyzdys: turim $x$, bandom prognozuoti $y$. Sugrupuojam į grupes su centrais $c_1$, \dots. Kiekvieną centrą $c_i$ atitinka kažkoks $y_i$. Idėja daryti prognozę taip: \[ y(x) = \sum_{i=1}^k y_i \cdot \frac{1}{D(x, c_i)} \] $D(x, c_i)$ -- atstumas nuo $x$ iki centro. T.y. tie, kas arčiau turi didesnę įtaką. % Čia daug neteisybės -- čia tik supraprastina idėja. % Čia vėl buvo statistinis metodas -- su neuroniniu tinklu tą D surasim patys Iš tikrųjų funkcija yra kitokia: \[ y(x) = \sum_{i=1}^k y_i \cdot K(\frac{D(x, c_i)}{\lambda_i}) \] $K$ yra varpo formos kreivė. $\lambda$ įtakoja varpo platumą. Toks būtų statistinis algoritmas. Neuroninis tinklas mokymo metu suras ir $c_i$ ir $\lambda_i$. % Vakarų univeruose už doktorantą univeras gauna 40000 guldenų per metus. Panašiai kaip ir su perceptronu: imam pradines $c_i$ ir $\lambda_i$ reikšmes (su klasterizavimu), tada imam kainos funkciją $c$ ir gradientiniu metodu ieškom minimumo pagal visus $\lambda_i$ ir $c_i$. \[ c = \sum (y_z - y(x_i))^2 \] Minusas: reikia daug skaičiavimo. Galima paprasčiau: tiesiog kvantuoti pagal mokymo vektorius. T.y. jei yra arti centro, imam to centro vidurkį o nebandom skaičiuoti atstumų. % Dabar mada: kvantiniai neuroniniai tinklai. Niekuo nesiskiria nuo paprastų % Schematinis vaizdavimas % "Dėstymas -- idėjų lygyje." % "Mokėjimas -- tas, kas lieka, kai viską viską užmiršti" Klasifikavimas: kiekvienam klasteriui trys parametrai $q_i$, $c_i$ bei $\lambda_i$: \[ y(x) = \sum_{i=1}^k q_i \cdot K(\frac{D(x, c_i)}{\lambda_i}) \] Pradinė $q_i$ ($i$-tojo klasterio apriorinė tikimybė) reikšmė -- vektorių skaičius $i$-tajame klaseryje padalintas iš visų vektorių skaičiaus. Funkcija $K(s)$ paprastai yra $e^{-s}$. Radialinių bazinių funkcijų neuroniniame tinkle gaunama reikšmė yra daugmaž tankio įvertinimas. Kiek suprantu, paskui taikom skirtingiems klasteriams skirtingus jų modelius ir kombinuojam atsakymą pagal tą tankį. Bet kadangi skaičiavimų daug galima tiesiog kvantuoti ir taikyti tik vieną modelį. Iš principo klaserių skaičiais skirtingose klasėse gali būti skirtingi. Pvz., klasifikuojam į sveikus ir sergančius. Sveiki beveik visi vienodi -- vienas ar du klasteriai. Sergantys yra skirtingi -- daug klasterių. Klasteriai gali persidengti. Kvantavime ne -- griežtai nubrėšime ribas. % 10x mažiau tyrimų naudoja šitas radialines f-jas, nei perceptronus. % Čia daugiau skaičiavimo, bet mokymas labai mažas. % Po mokymo klasterių nebelieka -- galima tuos blobus vadinti kvantais? % Per egzą paklaus, kurį (?) ar du išmesti -- mes turim iki to laiko % susitarti. Reikia bent 3 palikti :) % Okay, back to klusterizavimas: % radial etc. -- skaičiuojam atstumus iki visų klasteriių, dauginam tų % klasterių vidurkius iš to atstumo perleisto pro K ir sumuojam -- gaunam % atsakymą % klasterizavimas -- skaičiuojam atstumus iš visų klasterių, parenkam % mažiausią atstumą ir tiesiog imam to klasterio vidurkį. % Dabar bus genetiniai algoritmai ARBA sprendimo medžiai. \section{Sprendimo medžiai} % 20 Pagrindinė idėja: reikia suklasifikuoti/suprognozuoti daugiamatį vektorių. Dalinam sritį į dvi dalis, etc. Gaunam tokį medį, kurio šakose yra kažkurio požymio palyginimas (daugiau/mažiau), o medžio lapai yra klasės. Paskui leidžiamės tuo medžiu ir žiūrim, kurioj kas pusėje. Tai ir yra sprendimo medis. % Anekdotas. Sprendimo medis nebūtinai binarinis. Ir sprendimus galima daryti pagal daugiau nei vieną požymį. % Google for Quinlan[d]? ten yra 4.5, 5 versija etc -- populiariausi % algoritmai pasaulyje. Padarius sprendimų medį galime iš jo padaryti neuroninį tinklą. Kaip su klasterizavimu galima pradėti inicializuoti radialinių bazinių funkcijų neu\-ro\-ni\-nį tinklą, taip su sprendimų medžiu galima pradėti inicializuoti perceptroną. Kaip tą medį parinkinėti? Pereinam visus požymius, randam slenkstį, kad kiek galima mažiau klaidų būtų. Beje, čia irgi svarbu laiku sustoti. Per ilgai mokant bus blogai. Galima imti maksimalų klaidų skaičių lape (jei mažiau, nebeskaidom). Arba riboti medžio gylį. Sprendimų medis naudojamas klasifikavimui vadinamas klasifikavimo medžiu. Spren\-di\-mų medis naudojamas prognozavimui vadinamas regresijos medžiu. Egzistuoja ir sprendimų miškai. Šakojimo kriterijus gali būti bet koks -- kai kas stato ten neuroninius tinklus... Kaip iš sprendimų medžio gauti neuroną: Iš naujo: kiekviena sąlyga yra neuronas įėjimo sluoksnyje. Gauna reikiamus $x_i$ ir grąžina 0 arba 1 vietoje true/false. Ten slenksčiai statūs, t.y. visi atsakymai yra 0 arba 1 Antras sluoksnis: po vieną kiekvienam lapui (atsakymui). Duoda 1 jei kiekviena šaka kelyje buvo atitinkamai 0 arba 1. % --- 8 paskaita: 2003-05-15 \section{Genetiniai algoritmai} % 21 % Problema: lokaliniai minimumai Vienas iš būdų, kaip optimizuoti daugiamatėje erdvėje, kur yra daug lokalinių mi\-ni\-mu\-mų, yra Monte-Karlo metodas (arba atsitiktinė paieška) -- primėtai randomu daug taškų ir išrenki minimumą. Modifikacija: primėtom daug taškų, randam erdvės sritį, kur geriau, tada mėtom taškus toje srityje ir t.t. Kita modifikacija -- genetiniai algoritmai. Bandoma kopijuoti gamtą. Turime (iš pradžių susigeneruojame atsitiktinai, o galima ir neatsitiktinai) seką vienetukų ir nu\-liu\-kų, kurie nusako kažkokį svorių vektorių. Tiksliau, turime daug tokių rinkinių (tarkim, 1000). Apskaičiuojam kainos funkcijos reikšmę visiems. Išrikiuojam (geriausius į priekį) ir sudalinam į dvi dalis -- pirmi 100 dauginsis, kiti ne. „Dauginimasis“: imam dvi sekas, sudalinam gabaliukais, imam dalį gabaliukų iš vieno, dalį iš kito. Ir t.t. Šis algoritmas irgi gali įlįsti į lokalinį minimumą. Su tuo galima kovoti įvedam mutacijas -- su tam tikra tikimybe keičiam kai kuriuos vienetukus nuliukais ir atvirkščiai. Algoritmas labai lėtas, bet stabilus, mažiau jautrus lokaliniams minimumams. Toks yra bazinis algoritmas, paskui galima fantazuoti. % Inercija, paveldėjimas iš senelių Variantai: pirma apmokom kiekvieną kartą truputį gradientiniu metodu, o jau tada vertinam kainas ir skaičiuojam naują kartą. Idėja: visada pasilaikyti 10 geriausių genų iš praeitos kartos. % Antrą idėją pramiegojau Idėja: sudalinti į kelias grupes, jas mokyti atskirai, ir karts nuo karto suleisti tarpusavyje. Galima dirbti ne su svoriais, o svorių skirtumu. % Kaukė nusako kryžminimą: turim du genus, sukeičiam kaukėje nurodytus bitus % tarp jų ir gaunam du naujus. Kaip kaukę pasirinkti -- fantazijos reikalas. Galima iš pradžių padidinti mutacijų tikimybę ir sumažinti kryžminimo skaičių, o paskui, kai truputį pasimoko, mažinti mutacijų ir didinti kryžminimą. Taip galima išlošti laiko (algoritmas greičiau mokosi). Galima lygiagrečiai vertinti skirtingas kainos funkcijas (skirtingus kriterijus). Dalis blogiausių pagal kiekvieną kriterijų žūsta. % Reminiscence: svoriai dideli -- SLP lėtai mokosi. Triukšmas sumažina % svorius. % Katastrofa: radikaliai pasikeičia duomenų pobūdis. % Genetika: lėtai besimokantys neuronai miršta. Jei yra daug katastrofų, % triukšmo lygis didesnis, jei mažai, mažesnis. Taip sakant, paveldimas % triukšmo lygis. % Dabar apie savarankišką darbą: % idealus variantas -- susirandam savo duomenis. % galima prašyti Raudžio. galima ieškoti Duin Delfto web puslapyje % galima prašyti Giedriaus. % "pasikniskit", čia kūrybinis darbas. Už naujumą/originalumą extra balai. % % darbą galima daryti po du ar net po tris. ta prasme įvadas bendras etc., % bet aiškiai parodyta, kas kurią dalį darė. \section{Neuroninių tinklų kooperavimas} % 22 Labai svarbus klausimas. Kiekvienais metais vyksta konferencijos šia tema. Kuo sudėtingesnis tinklas, tuo lengviau jis pakliūna į lokalinį minimumą ir tuo ilgiau mokosi, tuo daugiau resursų reikalauja. Idėja: paimti keletą neuroninių tinklų ir paskui kažkaip apjungti jų atsakymus. % Situacija panaši į žmonių grupės bendrą sprendimą. Vienas, bet labai neįdomus variantas: paimti vieno tinklo atsakymą. Kitas: imti vidurkį. Arba svorinį vidurkį. Arba balsuoti. Arba gali būti pasvertas balsavimas. % balsavimas == majority voting Galima skirstyti uždavinius į grupes ir apmokyti skirtingus tinklus kiekvienai grupei. Ir taip toliau. Galima daug tokių būdų prigalvoti. % Čia buvo įvadas. Arba galima tų tinklų atsakymus paduoti kaip įėjimus naujam tinklui. Tokios sistemos skirtumas nuo daugiasluoksnio perceptrono yra tas, kad visi tie perceptronai apmokomi atskirai. Be to galima naudoti skirtingo tipo tinklus -- pvz. radial-ir-taip-toliau, sprendimų medį etc. Paslėptas akmuo: neuroniniai tinklai prisiderina prie mokymo duomenų ir „giriasi“, kad daro mažesnę klaidą, nei iš tiesų. Reikia tai įvertinti. Kuo sudėtingesnis tinklelis, tuo jis labiau giriasi. Reikia duomenis skirstyti ne tik į mokymo ir testinius, bet ir į daugiau dalių ir nemokyti „boso“ su tais duomenimis, su kuriais apmokyti „pavaldiniai“. "Boso taisyklė". Sudėtingas klausimas. Neišspręstas. % Alegorijos su bosu ir pavaldiniais. Angl. toks tinklų sujungimas yra "fusion" arba "gating rule", "combiner". Daug tų terminų yra. Behaviour knowledge space (BKS) metodas -- bandom visas neuroninių tinklų kombinacijas ir žiūrim, kokie atsakymai gaunasi. % Skystoka, bet negaliu dabar aiškiau suformuluoti % Real life: sovietai, daug skirtingų radarų. Reikia apjungti į vieną % sprendimą: ar reikia kelti aliarmą, ar ne. % OT: Radarai lėktuvuose matydavo nuo Maskvos iki Olandijos. \section{Geriausio varianto parinkimo tikslumas} % 23 % Yra daug modelių. Kurį parinkti? Neuroniniai tinklai dar taikomi ir optimizavimo uždaviniams. % Re pradiniai svoriai: vienasluoksniam ypač jei jie pastumti/pasukti, nuliai % tinka. Daugiasluoksniams NEGALIMA naudoti vienodų nulinių svorių, nes tada % visi paslėpti neuronai tada bus vienodi. Dar papildomas reikalavimas, kad % būtų ortogonalūs paslėptų neuronų svorių vektoriai. Svorių parinkimas -- % atskira problema. Variantų yra daug. Kartais nuo pradinių mokymo sąlygų priklauso klaidų skaičius -- 7 ar 17\%. Vienas iš sprendimų -- bandyti kelis variantus su tais pačiais duomenimis ir parinkti geriausią. Pvz.: apmokom 6 tinklus su mokymo duomenimis. Tikrinam testinius duomenis, gaunam skirtingas klaidas. Natūralu išsirinkti variantą su mažiausia klaida. Bet ta klaida yra testiniams duomenims. Realiai klaida yra kitokia ir galbūt ją žinodami pasirinktumėme kitą. Tada imam dar daugiau testinių duomenų: mokymo duomenimis apmokome, tik\-ri\-ni\-mo duomenimis paimame geriausią, testiniais duomenimis užsakovas tikrina. Įsivaizduojama klaida -- mažiausia klaida su testiniais duomenimis. Ideali klaida -- mažiausia tikroji klaida (bet jos niekas nežino). Faktinė klaida -- mūsų pasirinkto varianto (to, kurio testinė klaida mažiausia) tikroji klaida (kurios irgi niekas nežino). Kuo daugiau variantų, tuo mažėja įsivaizduojama klaida. Faktinė klaida iš pradžių mažėja, o paskui pradeda augti. Kuo daugiau variantų nagrinėji, tuo labiau apsirinki. % Ta pati tema -- laiku sustoti. (Jei tavo kriterijus netikslus). Praktinis pasiūlymas: padalinti testinius duomenis į dvi dalis, vieną naudoti pa\-rin\-ki\-mui, kitą naudoti faktinės klaidos paskaičiavimams, pasipaišyti dvi kreives (įsi\-vaiz\-duo\-ja\-mos ir faktinės klaidos bandymams). Paskui sukeisti tas dvi dalis pasipaišyti dar dvi kreives. Ir paskui pagal tai žiūrėti, kiek variantų apsimoka imti. Tradicinis apgavystės būdas: nerodyti blogų variantų -- užsakovui pateikti tik vieną, geriausią variantą. Šiaip moralas: neturėdamas informacijos, nieko gero nepadarysi. Jei duomenų mažai, nieko nepadarysi. % Viskas, paskutinė paskaita. % Už nepilnų dviejų savaičių paliekam pas Dičiūną (arba iš bėdos pas Mitašiūną) % trečiąją užduotį. Ketvirtą atnešam į konsultaciją. % Konsulacija birželio 2 d., egzas 4 d. \appendix \newpage \section{Egzamino klausimai} \begin{enumerate} \item Dirbtiniai neuroniniai tinklai (DKT) klasifikavimo ir prognozavimo uždaviniuose. \item Vienasluoksnis perceptronas (SLP) ir jo mokymo principai. \item Tiesinė klasifikavimo taisyklė. Jos gavimas SLP pagalba. SLP mokymo algoritmas. \item Tiesinė ir kvadratinė diskriminantinės funkcijos. \item SLP evoliucija mokymo metu. \item Tiesinis prognozavimas statistiniu metodu ir su SLP. \item Robastiniai algoritmai klasifikavimo ir prognozavimo uždaviniuose. \item Minimalios klasifikavimo klaidos ir atraminių vektorių (SVM) klasifikatoriai. \item Klasifikavimo ir prognozavimo klaidų rūšys, tikslumo rodikliai. \item Klasifikavimo ir prognozavimo klaidų įvertinimas. \item Algoritmo sudėtingumo, mokymo duomenų kiekio ir gauto tikslumo ryšys. \item Daugiasluoksnis perceptronas (DSP) ir jo mokymas. \item DSP mokymo ypatybės. \item Pagrindinių komponenčių ir kiti metodai duomenims vizualizuoti ir jiems transformuoti. \item Duomenų nuosavos reikšmės ir mokymo žingsnis. Duomenų transformavimas mokymui pagreitinti. \item Požymių atrinkimo algoritmai. \item Daugiasluoksnio perceptrono panaudojimas informatyvių požymių išskyrimui. \item Duomenų klasterizacija ir jos panaudojimai. \item Radialinių bazinių funkcijų (RBF) ir mokymo vektoriaus kvantavimo (LVQ) DNT. \item Sprendimo medžiai klasifikavimo ir prognozavimo (regresijos) uždaviniuose. \item Genetiniai mokymo algoritmai. \item Neuroninių tinklu kooperavimas. \item Geriausio varianto parinkimo tikslumas. \end{enumerate} % Konsultacija % Ideali prognozavimo paklaida kvadratu: sigma_0^2 = avg(y - (um w_i x_i + w_0))^2 % sigma_n^2 -- kur gaunam su testiniais duomenimis % avg sigma_n^2 = sigma_0^2 (1 - p/N-p)). % Išmesti klausimai: 6, 15; 14 ir taip neduos. % Egzas 9:30 fakultete \end{document}