# A simple example of feedforward neural network and image recognition

## Introduction

The new field, in which I’ve stepped a little bit is image processing or image recognition. This field has some similarities with the previous field (signal processing) and so it was not so difficult to try something new.

Today, we’re going to review a simple application, which I’ve written for my lab as a bonus for the final mark. The objection of the application is to recognize the areas in the picture, which has the most trees (the greenest ones). All the code can be downloaded here, especially, if you’re good in analyzing codes, the further description of this method is not necessarily to read in order to understand how everything works.

## Method

Firstly, we take a picture for training. Originally, images are 1000×1000 pixel size, but because I’m poor and my computer does not have lots of power and memory capacity, the image size is scaled by 0.40. The image size after the scale is 400×400 pixels.

Sample image

Next step is to use a sliding window (not sliding window protocol) to analyse the image. Basically, it is the same sliding window method, as for one dimensional signal, but this time, the samples are taken in two dimensions. The matlab implementation is extremely easy:

for i=2:size(I, 1)-1
clear j;
for j=2:size(I, 2)-1
Id(k,:) = I(j-1:j+1,i-1:i+1,:);
k = k + 1;
end
end

The code illustrates the use of 3×3 sliding window. The variable I is the image itself and because it is an RGB image, the selected window has three dimensions. The most important information from the image for the forest discovery problem is the green color, so the identification can be done by this feature. What we can do is not to save all RGB information of the window, but just green color information:

for i=2:size(I, 1)-1
clear j;
for j=2:size(I, 2)-1
Id(k) = mean(mean(I(j-1:j+1,i-1:i+1,2)))/9;
k = k + 1;
end
end

Using this code, we can work only with one dimensional feature data, not 27 dimensional data (as would be, using all RGB information).

Next problem is the uncertainty then the window sees the forest and then it is something else. Doing this by hand would be some sort of suicidal work, which could take ages to complete.. But there is a solution! It’s called the k-means clustering algorithm. What KM does, it divides the data by means. Logically, the green color mean of the forest area would be bigger.

It matlab it is realized quite simply:

IDX = kmeans(Id,2);

And this is it. The function returns the labels of the data of KM clusters.

The KM algorithm is sometimes a little bit random, for example – first time, doing KM it can label most green zones as 1, and not so green zones as 2. Do it again and the labels would be turned around. How well KM performed the clustering solution can be tested only after classification, then the forest would be recognized. If you see, that the algorithm does not work as good as it suppose to – you need to run it again, to give KM algorithm one more chance (okay, maybe not only one chance, but it is still better, than manually labeling data).

The next step, after KM is to separate original data, which we will need to train our Artificial Neural Network (FeedForward Neural Network (FFNN)), to do classification.

P1 = Id(IDX==1,:);
P2 = Id(IDX==2,:);
number = min(size(P1), size(P2));
number = number(1);

Here, P1 has one cluster of data, and P2 has the other. We’re searching with data cluster has less data, because the training algorithm require, that number of data samples in training set of both data clusters would be the same.

Next step is to train our super-awesome (and slow) FFNN with 10 hidden neurons (the number of neurons was chosen just randomly):

net = feedforwardnet(10);
P = [ P1(1:number,:); P2(1:number,:) ]';
T = [ zeros(1,number) ones(1,number) ];
net = train(net, P, T);

This can take some time.. The final algorithm does training using 4 different pictures of pictures. The classification tests was done using other 15 pictures. Here is some examples of classification done by this algorithm:

Acceptable classification result

Not acceptable classification result

On the left side of illustrations, there is an original image, in the middle there is classification result, and on the right side the mapped data. As we can see, the classification sometimes is done quite good, but sometimes is fails completely.

This algorithm requires more work (and more powerful computer to run on), but as a starting point it is quite good. The possible features to extract may be also mean of yellow color (to classify out roads).

## Conclusion

In this article, a simple image processing example is shown and discussed. As a feature to recognize the forest and not forest areas, the mean of green color was used. No dimensional reduction algorithm was used, because only one dimension is used. The data labeling was done using k-means clustering algorithm, which showed quite good results, but it is not recommended to use it for some very important tasks. This time it was more for fun, than for production. The classification was done, using FeedForward Neural Network (FFNN).

The complete code can be downloaded here. Just extract and run lab_10. After some time, you must see the same images, as shown in this short example.

# Pamąstymai apie slankiojančio lango signalų analizavimo metodą

Geriausios mintys kyla tuomet, kai darai ką nors visiškai pašalinio – šiuo atveju besėdint prie visiškai intelektro nereikalaujančio kompiuterinio žaidimo, kilo įdomi mintis kaip galima praplėsti slankiojančiu langu pagrįsta signalų analizavimo sistemą.

Visa idėja remiasi kintamo ilgio slankiojančiu langu (tiksliau jo ilgis kinta tik signalo analizavimo pradžioje), o toliau lieka pastovus. Taip galima praplėsti analizuojamo signalo ilgį, išsaugant mažą reakcijos laiką. Idėja dar reikalauja darbo, tačiau pačią pradžią jau galima publikuoti.

Tikiu, kad jau kažkas iki manęs apturėjo ir aprašė šitą idėja, tačiau vistiek ją aprašiau, kad nepamest.

Kadangi wordpress sistema yra labai, labai nedraugiška grafikams ir lygčių rašymui, nusprendžiau viską aprašyti LaTeX pagalba ir tiesiog patalpinti savo rašliavų interneto kampelyje.

Popierių galite atsisiųsti iš čia.

# Įžanga į Paslėptą Markovo modelį (skaidrės)

Šį kart trumpa prezentacija apie Paslėptą Markovo modelį, su trupučiu matematikos.

Skaidrėse pristatomi mašininio apmokymo tipai, parodyta pavyzdinė savybių erdvė, aptariamas Markovo procesas, Markovo grandinė, apibūdinti Paslėpto Markovo modelio parametrai, apžvelgiamas Viterbi kelio radimo algoritmas.

Viskas paruošta nėra super-idealiai, dėl didelio akademinio užimtumo. Skaidrės yra daugiau kaip špargalkė kalbai, negu kaip mokomoji priemonė. Mokomajai priemonei reikia knygas rašyti. Skaidres galite peržiūrėti slideshare, arba atsisiųsti pdf formatu.

# Kas iš tikrųjų yra Paslėptas Markovo modelis

## Įžanga

Truputi pamankštinęs rankas prie Paslėpto Markovo modelio, galiu pasidalinti ne teoriniais samprotavimas apie nagrinėjamą modelį, o apie konkretų įrankį, kuris veikia ir veikia pakankamai gerai.

## Paslėptas Markovo Modelis ir kiti klasifikatoriai

Jeigu padaryti prielaidą, kad Paslėptas Markovo Modelis (PMM) yra klasifikatorius, tuomet palyginus su kitais klasifikatoriais – mes turime labai galingą įrankį.

Pradėkime nuo NaiveBayes klasifikatoriaus, kuris yra labai paprastas – n dimensijų Gauso pasiskirstymas. Kai gauname tašką erdvėje – tiesiog pažiūrime kiekvieno cluster tikimybes ir išrenkam tą cluster, kuris turi didžiausią tikimybę. Paprasta, greita ir pigu. Tačiau kas nutinka, kai du Gauso pasiskirstymai yra arti vienas kito, o taškai iš šaltinio gaunami tik per delta skirtumą tarp dviejų pasiskirstymų – klasifikatorius mėtysis tarp vieno ir kito cluster. Taip mes gauname labai mažą accuracy ir presition.

Support Vector Machine yra kiek sudėtingesnis variantas. SVM’as ieško papildomų dimensijų duomenims atskirti. Tai ypač pagelbėja, kai duomenis linijiniu būdu atskirti tiesiog nėra įmanoma. Geras pavyzdys – naudojant polynomial kernel trick. Pagrindinis SVM darbo arklys yra radial basis function. Tai tas pats Gausas. Mano praktikos metu, SVM’as tik truputi geriau dirbo, negu NaiveBayes klasifikatorius, o kaikuriais atvėjais – net blogiau. Dirbtinio intelekto sistemose, visgi, daug kas priklauso nuo application. Reikia išnagrinėti kokias savybes signalas turi savyje, ką duoda dimensijų mažinimas.

PMM turi vieną labai didelį pranašumą, palyginus su kitais nagrinėtais klasifikatoriais – jis turi savyje laiko informaciją. Matematiškai šnekant, tai kai mes turime du duomenų cluster, kurių variacijos kertasi – mes virš dviejų variacijų galime aprašyti dar vieną variacija, kuri aprašo įvykių tikimybes, kurias atspindi clusters. Taip galima kontroliuoti sąlygas, kurios aprašo įvykio pasikeitimą.

Jeigu nustatyti, kad perėjimo tikimybė tarp vieno ir kito įvykio yra labai maža, tai nors, jeigu ir naujas duomenų taškas bus ant kito Gauso pasiskirstymo – klasifikatorius vistiek neskubės persijungti prie kito įvykio.

Paprastas klasifikatorius

Pagerintas (PMM) klasifikatorius

Paslėptas Markovo Modelis yra fantastiškas matematinis įrankis. Skirtingai nuo kitų klasifikatorių, jame lengvai gali būti saugoma bet kokia euristinė informacija apie nagrinėjamus duomenų clusters.

# Latex #3

## Įžanga

Kuomet norima pradėti rašyti su $LaTeX$, pradžioje yra išnagrinėjamos jo komandos ir, remiantis pavyzdžiais, pradedama rašyti paprasti dokumentai. Dabar norėčiau pasistūmėti nuo savo paskutinio įrašo apie LaTeX kiek toliau ir pasidalinti dokumento formatavimo su LaTeX patirtimi.

## Dokumento struktūra, grafika ir tekstas

1. Iliustracijai atvaizduoti visuomet naudokite \figure. Automatinis iliustracijų numeravimas vėliau jums labai atsipirks, kuomet reiks papildyti kokią iliustraciją dokumento pradžioje. Taip pat naudokite \figure ir kai norima atvaizduoti ne iliustraciją, o tarkim kokį grafiką ir netgi kodo fragmentą.
2. Lentelėms sudaryti visuomet naudokite \table. Pradžioje bus truputi nepatogu surašinėti tiek daug teksto, norint atvaizduoti tik vieną lentelę, tačiau lentelės atvaizdavimas atrodys žymiai geriau ir tvarkingiau.
3. Taip pat yra naudinga susidaryti dažniausiai naudojamų paketų sąrašą ir parašyti šabloninę latex bylą, kurioje būtų įtraukti visi tie paketai. Tai labai palengvina situacijas, kuomet reikia rašyti kelias ataskaitas toje pačioje srityje. Taip pat, sumažinama tikimybė kompiliavimo metu susidurti su kompiliavimo klaida ir garsiai nusikeikti.
4. Kaip įmantriau, venkite naudoti book ir report dokumento tipus. Book dokumento tipas yra sunkiai keičiamas ir nėra toks lankstus, kaip tarkim article dokumento tipas. Report tipo dokumento tipas automatiškai sukuria titulinį puslapį, kurio stilius retai atitinka norimą variantą, todėl geriau naudoti article dokumento tipą, kuris leidžia rašyti norimo stiliaus titulinius puslapius. Vienintelis article tipo trūkumas: nėra \chapter tag’o. Tai didelė problema, kuomet tenka rašyti labai didelius darbus ir tiesiog neužtenka \subsubsection. Tokiose situacijose galima išsisukti naudojantis enumerate tipo sąrašu:
\begin{enumerate}
\item Tai kas netelpa į subsub
Tolimesnis tekstas ...
Tolimesnis tekstas ...
\end{enumerate}
5. Labai rekomenduoju pasinagrinėti pgfplots, tikz bibliotekų galimybes. Naudojant šitas bibliotekas galima visiškai atsisakyti būtinybės grafikus braižyti su kita programine įranga – net signalines laiko diagramas. Galimybių jos suteikia tikrai pakankamai. Pavyzdžiui, jeigu su kažkokia programine įranga sugeneravote duomenų sekas, tai užtenka kelių eilučių, norint atvaizduoti gautus duomenis ataskaitoje.
6. Nebelieka būtinybės naudoti Excel’į ar kokią analoginę programinė įranga, norint sugeneruoti vieną kitą grafiką. Tokio metodo pagrindinis privalumas: kuomet pasikeičia duomenys – tereikia per naujo sugeneruoti latex bylą ir viskas – nauji duomenis atvaizduoti, kur Excel variantu reiktų jį atsidaryti, pakeisti duomenis, sugeneruoti grafiką, jį išsaugoti paveikslėlio formatu ir tik tuomet atnaujinti jį darbe.
7. Tekstą rašyti geriausia yra ne teksto blokais, o sakinys-eilutė principu. Kuomet yra rašoma teksto blokais – klaidos taisymas paliks teksto bloke skylę arba teksto bloko eilutė tiesiog išsitęs. Rašant sakinys-eilute būdu, kiekviena klaida nepaliks didelių tarpų tarp teksto ir teksto redagavimas bus patogesnis, lengvesnis akims.

Latex yra labai patogus sprendimas rašant tiek didelis, tiek mažus dokumentus. Šiuo metu net yra išleistas latex šablonas CV Europass formatui. Jeigu niekad nedirbot su Latex ir vis dar naudojate Office tipo programinius paketus, pažiūrėkit kokias galimybes suteikia Latex ir palyginkit su savo programine įranga.

# Užtikrintos karjeros grafiko paaiškinimas

Neseniai pateikiau vieną tokį faktą, kurį pastebiu kiekvieną kartą, kai tik baigiasi studijų semestras. Ir kas kart, tas pastebėjimas vis paaštrėja. Taip kilo priklausomybės idėja.

## Įžanga

Grafikas, kurį matote aukščiau, yra subtilus geek’ų humoras, kurį turbūt supras nedaug žmonių. Noriu iškarto pasakyti, kad sekanti iliustracija nėra kažkokia pašaipa ar kažkoks nusiskundimas kaip blogai yra universitete. Viskas visiškai ne taip. Ir viskas netgi atvirkščiai. Šiame įraše pabandysiu paaiškinti grafiko idėja ir galutinai apiforminti ką jis reiškia, kad neliktų nesupratusių.

Idėjos paaiškinimui pabandysiu iliustruoti paprastu uždaviniu, dviejų skaitmenų sudėtimi, sudėties operacija. Tarkim, kad ir 2+2. Kas gali būti paprasčiau, pasakysite Jūs. Tačiau, kai tik palysi giliau, viskas tampa ne taip ir paprasta.

Savo aiškinimą pradėsiu nuo mokyklos. Nuo žinių židinio, nuo pačios-pačios pradžios – paskalio. Tai iki istorinė programavimo kalba, kurią programavimo tik todėl, kad kitas pasirinkimas buvo tik asembleris ar fortranas ( nors aš turbūt geriau programuočiau asembleriu ).

Mūsų nagrinėjamos problemos sprendimas paskalio atveju atrodo taip:

program sudėtis;
var suma : integer
begin
suma := 2 + 2;
end;

Viskas kaip ir paprasta – apsibrėžėme kintamąjį, į kurį saugosime savo operacijos atsakymą. Kintamasis, šiuo atveju, yra fundamentalus dydis, su kuriuo programoje galime operuoti. Sumos operacija irgi yra fundamentalus operatorius, kadangi realiai procesorius ( o tiksliau jo ALĮ ( aritmetinis-loginis-įrenginys ) ) visiškai “nemoka” mums įprastas matematines operacijas.

Judėkime toliau, o tiksliau – giliau.

## Asembleris

Kiekvienas programinis kodas, nesvarbu kokia programavimo kalba jis būtų parašytas – yra transliuojamas į mašininį kodą ir jo asemblerinį analogą ( *.lst ). Pabandykime dabar parašyti analogišką Paskaliui dviejų kintamųjų sudėties operacijos programą Intel’io 8051 mikro-kontroleriui. Tai senas, geras 4 KB kodo atminties turintis ir 128 B duomenų atminties turintis įrenginys, kurį kai kurie, vis dar naudoja. Kaip atrodys kodas:

	.ORG 0H		; programos pradzios adresas

MOV A, #2D	; perkeliam 2 i ACC
ADDC A, #2D	; prie ACC pridedam 2

.END		; susirenkam zaislus ir einam namo

Šiuo atveju, mes jau operuojame su konkrečiu įrenginiu – ACC registru, akumuliatoriumi, tik su kuriuo iki-istoriniai procesoriai galėjo atlikti aritmetines operacijas ( tik nežinau kaip dabar su daugyba/dalyba ). Tačiau čia dar lieka viena fundamentali operacija – sudėtis, ADDC ( add with carry ). Mažą užuominą tam gali duoti transliacijos byla:

0000 7402                3             MOV A, #2D      ; perkeliam 2 i ACC
0002 3402                4             ADDC A, #2D     ; prie ACC pridedam 2

Pirmas stulpelis yra adresas ( kuris prasideda nuo 0000, kaip ir buvo nurodyta .org operatoriumi ). Mus labiau domina antras stulpelis, kuriame yra nurodytas mašininis kodas. Pirmi 8b yra operacijos kodas, kur prie sumatoriaus jis yra 0x34, o toliau jau seka pats kintamasis 0x02. Vadinasi, pirmiausiai procesorius sužino ko iš jo nori programuotojas, o paskui jau paima tą skaičių, su kuriuo bus atliekama operacija.

Judam tolyn, į aparatinį lygmenį!

## Aparatinis lygmuo

Aparatiniame lygmenyje mes pasiaiškinsime paprastą aparatinį įrenginį – sumatorių. Projektuoti savo sumatorių pradėsime nuo paprasčiausio jo varianto – dviejų 1b dydžių sumavimo. Štai kaip atrodo paprastas 1b sumatorius schematiškai:

Realiai, rezultatą duoda XOR loginis įtaisas, o kuomet mums nepakanka 1b atsakymui – pasijungia AND loginis įtaisas. Taigi, kai mes turime 0b1 + 0b0, tai atsakymą mes turime:

Ir atsakymas yra 0b1, o kuomet mes turime 0b1 + 0b1, tai atsakymas yra:

Teisingai, dabar mes jau turime persipildymą, kadangi 0b1 + 0b1 = 0b10 ( 1b neužtenka atsakymui išsaugoti ). Taigi, mūsų sumavimo įrenginys, turi turėti persipildymą apdorojančią grandinės dalį, todėl mums reikia papildyti duotą schemą. Galutinė schema atrodytų taip:

O taip atrodys 2b sumatorius:

Vedant iš vieno grandinės bloko į kitą grandinės bloką persipildymo išėjimą, galima sudaryti n bitų sudėjimo grandinę. Tačiau mūsų nagrinėjamai problemai užtenka ir 2b, su persipildymo kontrole, kadangi 2 yra 0b10, o 0b10 + 0b10 = 0b100, pažiūrėkime kaip tai atrodo loginėje grandinėje:

Ir štai – sudėjome du skaičius nesiremiant jokiais fundamentaliais operatoriais – kintamaisiais, aritmetiniais ženklais.

Aritmetines operacijas atlikome su loginiais įtaisais, tačiau ir juos juk reikia suprojektuoti. Pateiksiu vieną tokio projekto pavyzdį, panaudojus n ir p tipo MOSFET’us.

Schema nėra iškarto lengvai suprantama, tačiau ji puikiausiai veikia. Pabandykime schemoje pakelti vieną įėjimą:

O dabar pakelkime abu įėjimus:

Kaip matote, savo loginę užduotį AND grandinė atlieka kuo puikiausiai.

Nuo paprastos paskalio programos mes nusileidome iki pat aparatinio lygmens su loginėmis grandinėmis. Žemiau jau tik yra puslaidininkių teoriją, kurią bent kiek panagrinėti reiktų dar dviejų tokio pat ilgio įrašų.

Elektronikoje nėra žmogui įprastu matematinių operacijų, kaip sudėtis, atimtis, daugyba, dalyba. Nekalbu net apie integravimą. Elektronika siekia kiekvieną žmogui įprastą operaciją aproksimuoti. Sumavimą galima pavadinti idealizuotu uždaviniu. Mes turime tik du skaičius ( arba du objektus ) ir natūraliai išplaukia išvada, kad jeigu prie dviejų kiaušinių pridėsime dar du kiaušinius, tai jau turėsime keturis kiaušinius. Tuo galime įsitikinti net skaičiuodami ant pirštų. Elektronikoje toks idealizuotas uždavinys yra aproksimuojamas naudojant puslaidininkius, iš jų sudarant logines grandis, iš loginių grandžių sudarant aparatinius įrenginius ir t.t..

Kiekvienas iš išvardintų lygmenų turi savo iššūkius ir kylančias problemas. Kiekvienas lygmuo yra įdomus ir reikalauja specifinių žinių. Problema – o kurį pasirinkti? Kokiam lygmeniui atiduoti visą savo inžinerinę esmę? Kurioje specializacijoje būčiau geresnis specialistas?

Dar taip pat į nugarą kvėpuoja tokia, labai neapibrėžta ir sunkiai kur taikoma, dirbtinio intelekto patologija..

# Paslėptas Markovo modelis: Diskretinis Markovo procesas

Paimkime sistemą, kurią galima apibūdinti bet kokiu laiko momentu tam tikra būsenų seka $N$, kur galimos sistemos būsenos yra $S_1$, $S_2$, $..$, $S_N$, kaip pavaizduota iliustracijoje.

Markovo graindinė su 5 būsenomis ir perėjimo tikimybėmis

Per tam tikrą, periodinį laiko tarpą, sistema pakeičia savo būseną, priklausomai nuo ankščiau numatytų tikimybių. Mes nustatome laiko konstantas, susietas su būsenų kitimu, $t = 1$, $2$, $...$ ir nustatome sistemos būseną $q_t$, esant $t$ laikui. Pilnas probleminis sistemos apibūdinimas reikalauja žinoti sistemos būseną kiekvienu laiko momentu. Specialaus diskretinio, pirmojo tipo Markovo grandinei, toks probleminis sistemos apibūdinimas yra išskaidytas į dabartinę ir spėjamą būseną, pavyzdžiui:

Kur $P$ yra skaičiuojamoji tikimybė; $q_t$ yra $t$ laiko momentu sistemos būsena $S_N$.

Mes orientuojamės tik į procesus, kurioje aukščiau nurodytos lygties dešinėje dalyje, kuri yra nepriklausoma nuo laiko. Tai veda prie galimybės suformuoti tarpinių būsenų, sudarytų iš dabartinės ir spėjamos, tikimybes $a_{ij}$:

su tarpinės būsenos koeficientų apibrėžimais:

kadangi jos pilnai patenkina standartinio stochastinio proceso konstantas.

Aukščiau nurodytas stochastinis procesas gali būti vadinamas galimas Markovo modelis, kadangi proceso išėjimas yra sistemos būsena tam tikru laiko momentu, kur kiekviena būsena nusako fizikinį įvykį. Tam, kad įtvirtinti aptartas idėjas, paimkime trijų lygių Markovo oro modelį. Galima pasakyti, kad galimas pusiaudienį oras lauke gali būti trijų fazių:

• Būsena 1: lietus
• Būsena 2: debesuota
• Būsena 3: saulėta

Mes teigiame, kad oras, esant dienai $t$, yra charakterizuojamas pagal aukščiau nurodytas būsenas, o galimybių $a_{ij}$ matrica $A$ atrodytų taip:

Padarykime prielaidą, kad pirmą dieną ($t=1$) šviečia saulė. Ir paklauskime klausimo: kokia tikimybė, kad per sekančias septynias dienas oras bus “saulė-saulė-lietus-lietus-saulė-debesuota-saulė-..” ? Tikimybių seką O mes galime aprašyti kaip $O = \{S_3, S_3, S_3, S_1, S_1, S_3, S_2, S_3\}$, kuri sudaryta iš $t =1, 2, ..., 8$ laiko momentu atliktais stebėjimais. Mes norime nustatyti šio modelio tikimybę O. Tokia tikimybė gali būti išreiškiama taip:

panaudojome pažymėjimą

Taip pat galime paklausti dar vieno įdomaus klausimo (į kurį atsakyti galime pasitelkti modelį): Kokia tikimybė, kad modelis liks vienoje būsenoje tiksliai d dienų?

Tokia tikimybė yra randama stebėjimų seka:

modeliui, kuris yra:

Dydis $p_i(d)$ yra diskretinis dydis, kuris žymi funkcijos tankio tikimybę, kurios trukmė yra d, i būsenoje. Šitas eksponentinis tikimybės tankio dydis yra Markovo grandinės tikimybės būsenos ilgis. Remiantis $p_i(d)$, mes galime apskaičiuoti tikėtiną vienos būsenos stebėjimų skaičių

Iš čia galime apskaičiuoti, kad tikėtinas vienos būsenos stebėjimas esant saulėtam orui yra $\frac{1}{0.2}=5$, debesuotumui $\frac{1}{0.4}=2.5$, o tikimybė stebėti lietų $\frac{1}{0.6}=1.67$ dienos.

Šaltinis: “A tutorial on Hidden Markov Models and Selected Applications in Speech Recognition”

# Kaip veikia RSA

## Įžanga

RSA kodavimas yra labai įdomus pavyzdys, kaip abstraktų matematinį modelį galima sėkmingai panaudoti realiam gyvenime. Šiame įraše pabandysim išsiaiškinti kaip vyksta RSA duomenų kodavimas iš matematinės pusės.

## Paprastos funkcijos

Matematiškai funkcijos yra toks pats reiškinys, kaip ir programavime. Pavyzdžiui:

foo(x) = 10*x-2

Jeigu į funkciją perduosim 2, tuomet ji gražins 18. Viskas logiška. Mes taip pat galima parašyti funkciją, kuri daro lygiai tą patį, tik atvirkščiai:

bar(x) = (x+2)/10

Jeigu į funkciją perduosim 18, tuomet ji gražins 2. Kadangi bar(x) funkcija daro funkcijai foo(x) priešingus veiksmus, tai bar(x) funkcija yra atvirkštinė funkcijai foo(x).

Dabar pesikelkim į programavimo terpę. Pavyzdžiui, jeigu mes turim foo(x) funkcijos pradinį kodą, tačiau neturim bar(x) funkcijos pradinio kodo. Ar yra įmanoma parašyti bar(x) funkcija, kuri yra atvirkštinė funkcijai foo(x) ? Mes žinom kas bus siunčiama į bar(x) funkciją ir ką ji turėtų gražinti. Teoretiškai atsakymas būtų taip. Tačiau, yra keletas specialių funkcijų, kurių veikimo principas yra žinomas, tačiau parašyti jai atvirkštinę funkciją yra labai sunkus uždavinys.

## Modulių aritmetika

Daugelis programuotojų yra sutikę % operatorių, kuris gražina dalybos liekaną. Pavyzdžiui:

10 % 3 = 1

Matematikoje, idėja yra panaši, tačiau pati modulių teorija yra skirtinga. Modulių aritmetika sudaro begalinis skaičius, kuris yra sukamas apie realaus skaičiaus lanką. Skaičiai, kurie neužbaigia ciklo yra vadinami kartotiniai. Analogišką operaciją programavime, matematikoje galime užrašyti taip:

10 = 1 (mod 3)

Skamba tai kaip: “10 turi kartotinį 1, moduliu 3”.

Liekaną geriau pamatysime, jeigu išskaidysime skaičių į jo dedamąsias:

6 + 4 = 0(mod 3) + 1(mod 3) = 1(mod 3)

Šioje išraiškoje, skaičius 6 liekana yra 0, o 4 liekana yra 1. Į (mod 3) veiksmą galime žiūrėti kaip į trijų valandų laikrodį, kuriame ciklas kartojasi su kiekvienu apsisukimu.

Įdomiausia modulių aritmetikoje, kad veiksmuose mes galime pakeisti skaičius jų liekanomis ir vistiek gauti teisingą atsakymą:

4 = 1(mod 3 )
6 + 4 = 6 + 1 = 1(mod 3)

Jeigu naudojame kaip pagrindą 10 – mūsų visiškai nejaudina koks yra skaičius, mums svarbu kokiu skaičiumi yra baigiama:

37383 = 3(mod 10)
33313134 = 4(mod 10)

## Didžiausias bendras daliklis

Didžiausias bendras daliklis ( GCD funkcija ) yra dviejų skaičių didžiausias skaičius, iš kurio dalinasi abu skaičiai:

gcd(22,11) = 11
gcd(23,55) = 1
gcd(999,99) = 9

Kuomet dviejų skaičių didžiausias bendras daliklis yra lygūs vienam, tai yra sakoma, kad skaičiai vienas kitam yra pirminiai. Kaip pavyzdžiui 23 ir 55 yra vienas kitam pirminiai.

## Eulerio Totient Funkcija

Eurelio Totient Funkcija yra žymima graikiška raide phi(N) ir žymi skaičių kiekį (1;N-1) intervale, kurie yra pirminiai skaičiui N.

Pavyzdžiui:

phi(4) = 2 ( 1 ir 3 yra pirminiai skaičiui 4 )
phi(6) = 2 ( 1 ir 5 yra pirminiai skaičiui 6 )
phi(8) = 4 ( 1, 3, 5 ir 7 yra pirminiai skaičiui 8 )


Išsiskaičiuoti pirminius skaičius taip pat galima ir pasitelkus kitą išraišką:

phi(P*Q) = (P-1)*(Q-1)

Jeigu P ir Q yra pirminiai.

## Eurelio Totient Teorema

Šita teorema yra pats svarbiausias raktas, vedantis prie RSA algoritmo:

Jeigu gcd(T, R) = 1 ir T < R, tuomet T^(phi(R)) = 1 (mod R)

Mes galima patikrinti teoremą, panaudodami kelis mažus skaičius. Jeigu pažymėsime T = 5 ir R = 6, gausime:

phi(6) = (2-1)*(3-1) = 1 * 2 = 2
5^(phi(6)) = 5^2 = 25
25 = 24 + 1 = 6*4 +1 = 1(mod 6)

## Teoremos nagrinėjimas

Toliau paimkime Eurelio Totient teoremą ir su ja pažaiskime:

T^(phi(R)) = 1(mod R)

Padauginkime šitą teoremą iš jos paties. Dėka modulių daugybos viskas atrodys taip:

T^(phi(R))*T^(phi(R)) = 1*1(mod R)
T^(2*phi(R)) = 1(mod R)

Pakartoję ciklą gausime:

T^(3*phi(R)) = 1(mod R)

Galime tęsti kiek norime. Atradus tokį dėsningumą mes galime praplėsti Eurelio Totient Teoremą:

Jeigu GCD(T, R) = 1 ir T < R, tuomet T^(K*phi(R)) = 1(mod R), kur K bet koks skaičius

Galima pastebėti, jog K gali būti tik sveikasis skaičius, kas reiškia, kad K*phi(R) dalinsis be liekanos iš phi(R). Taigi dėsnį galime perfrazuoti:

Jeigu GCD(T, R) = 1 ir T < R, tuomet T^S = 1(mod R), kuomet S = 0(mod phi(R))

Tęskime savo žaidimą ir padauginkime gautą lygtį iš T:

T^S*T = 1*T(mod R)
T^(S+1) = T(mod R)

Pakartojam:

T^(S+1)*T = T*T(mod R)
T(S+2) = T^2(mod R)

Ir taip toliau. Matome dėsningumą. Iš jo galime nusręsti, kad S ne R kartotinis, o phi(R). Iš šito seka nauja taisyklė:

T^E = T^F(mod R), kuomet E = F(mod phi(R))

## Idėja

Grįžkime prie ankstesnės lygties ir panagrinėkime ją dėtaliau:

T^(S+1) = T(mod R)

Vienoje lygties pusėje mes turim T, pakeliam jį kvadratu. Kitoje lygties pusėje mes su T atliekame modulių aritmetikas. Mes turi dvi lygtis, kurios yra lygios ir kuriose dalyvauja tas pats vienas kintamasis.

Tačiau kas gi čia tokio stebuklingo? O stebuklinga yra tai, kad mes galime lengvai jas atskirti. Būtent šiuo atveju, paimkime kažkokius du nauju skaičius P ir Q, tuomet:

P*Q = S+1, kiekvienai S reikšmei

Arba:

P*Q = 1(mod phi(R))

Tuomet mes galima parašyti:

T^(P*Q) = T(mod R)

Kas yra tas pats, kas ir:

(T^P)^Q = T(mod R)

Ir tai mes jau galime perskelti į du žingsnius:

T^P = X(mod R) ir
X^Q = T(mod R)

## Generuojam raktų porą

Norint sugeneruoti tam tikrus raktus, pirmiausiai reikia parinkti reikšmę R. Taigi, galime pradėti atsitiktinai imdami du skaičius, U ir V, ir juos daugindami:

R = U*V

Abudu skaičiai turi būti pirminiai vienas kito atžvilgiu. Paskui bus galima lengvai rasti skaičiaus R pirminius skaičius:

phi(R) = (U-1)*(V-1)

## Pavyzdys

Tam, kad pamatyti, kaip viskas suskaičiuojama, paimkime mažus skaičius, tarkime U = 5, V = 11:

R = U*V = 5*11 = 55
phi(R) = phi(55) = (5-1)*(11-1) = 4*10 = 40

Dabar reikia rasti skaičius, kurie tinka lygčiai:

P*Q = 1(mod 40)

Žinoma, jų yra begalinis skaičius, tačiau pradėkime nuo P = 7.

7*Q = 1(mod 40)

Perrašom dešinę pusę:

7*Q = K*40 + 1

Pirmas skaičius, kuris tenkina lygtį yra Q = 23:

7*23 = 161 = 4 * 40 + 1

Taigi, mūsų viešas raktas yra P = 7, o privatus Q = 23.

Tarkime, norime išsiųsti žodį “VGTU”. Painaudoję ASCII kodų lentelę, skaičiais tai atrodytų taip:

86 71 84 85

Dabar užkoduojam kiekvieną simbolį su viešu raktu:

86^7 (mod 55)  = 26
71^7(mod 55) = 36
84^7(mod 55) = 39
85^7(mod 55) = 35

Gauvome tokį kodą:

26 36 39 35

Jeigu išversime visą tai pasitelkdami ASCII lentelę, gausime “SUB\$’#”, kas visiškai neturi nieko bendro su mūsų siunčiama žinute. Kuomet duomenys baigia savo kelią per nesaugią liniją, gavėjo pusėje vyksta duomenų dekodavimas pagal privatų raktą Q = 23.

26^23(mod 55) = 86
36^23(mod 55) = 71
39^23(mod 55) = 84
35^23(mod 55) = 85

Gavome kodą:

86 71 84 85

Kas iš ASCII kodų lentelės surenka “VGTU”.

Galite pabandyti atkoduoti:

68 10 20 20 34 43 23 29 07 17 12 36

Su privačiu raktu Q = 23 ir R = 55.

RSA yra gan paprastas kodavimo algoritmas, tačiau nežinant raktų, jį iškoduoti su dabartiniais kompiuteriais gali užtrukti ant tiek ilgai, kad saulė jau išnaudos visus savo resursus ir sprogs, o kompiuteris vis dar bandys iškoduoti RSA kodą.

Jis neparodo simbolių priklausomybės, kaip tarkim T (84) ir U (85) skiriasi tik viena eile, tačiau užkoduojant juos RSA, jų skirtumo eilė pasikeitė T (39) ir U (35) ir netgi tapo neigiama.

Šaltinis

# Paslėptas Markovo modelis: Įžanga

Po truputi ruošiames baigiamąjam darbui, todėl pradėjau versti vieną gerą paslėpto Markovo modelio vadovą “A tutorial on Hidden Markov Models and Selected Applications in Speech Recognition”. Pateikiu Jums išverstą įvadą.

Nors ir buvo pristatyti dar vėlesniais 1960-tais ir ankstyvais 1970-tais metais, statistinis Markovo metodas arba paslėptas Markovo metodas tapo labai populiarūs tik paskutiniais metais. Yra dvi pagrindinės priežastys kodėl taip nutiko. Pirma, modeliai yra stipriai pagrįsti matematiškai ir iš to galima suformuoti teoretinę bazę modelių taikymui. Antra, modeliai, reikiamai pritaikyti, labai gerai dirba praktikoje, svarbiuose įtaisuose. Šiame vadove pabandysime atsargiai ir metodiškai apžvelgti teoretinius šio tipo statistinio modelio aspektus ir parodyti kaip jie yra pritaikomi balso atpažinimo problemoms spręsti.

Realaus pasaulio procesus paprasčiausiai galime apibūdinti signalais. Signalai gamtoje gali būti diskretiniai (raidės iš žodyno) arba nuolatiniai (garsiniai signalai, temperatūros matavimai). Signalo šaltinis gali būti stacionarus (jo statistiniai apibrėžimai nepriklauso nuo laiko), ar nestacionarus (signalo apibrėžimai laikui bėgant kinta). Signalai gali būti gryni (siunčiami tiesiai iš šaltinio), ar pažeisti iš kitų signalų šaltinių (kaip pavyzdžiui triukšmo) arba dėl perdavimo trukdžių, aido, kt.

Fundamentinio tipo svarbi problema yra charakterizuoti tokius, realaus pasaulio, signalus į signalų modelį. Yra keletas priežasčių dėl ko šitą problemą yra būtina spręsti. Pirmiausiai, signalo modelis suteikia mums pradinę informaciją apie signalą, kuria remiantis yra galima apibrėžti reikalingą signalą sistemos išėjime. Pavyzdžiui, mus domina pokalbio, vykstančiu telefonu, signalo sustiprinimas. Signalas yra pažeistas triukšmo ir perdavimo kliūčių. Tokiam uždaviniui atlikti mes galime panaudoti signalų modelį ir suprojektuoti sistemą, kuri pašalins nereikalingą triukšmą ir anuliuos perdavimo iškraipymą. Antra priežastis kodėl signalų modelis yra toks svarbus yra tai, kad jis potencialiai mums gali pasakyti labai daug apie signalo šaltinį, net jeigu mes jo nematome. Ši savybė yra labai svarbi, kai yra būtina gauti tikslų signalą iš šaltinio. Šiuo atveju, su geru signalo modeliu, mes galime simuliuoti signalo šaltinį ir išmokti kuo daugiau iš tokių simuliacijų. Galiausiai, pagrindinė priežastis kodėl signalo modelis yra toks svarbus – jis velniškai gerai veikia praktikoje ir leidžia mums suvokti svarbias praktines sistemas, pavyzdžiui spėjimo sistemos, atpažinimo sistemos, identifikavimo sistemos, kt.

Galima pasirinkti keletą signalo modelio tipų, kuriais galima apibūdinti nagrinėjamo signalo ypatybes. Vienas signalas gali būti išskaidytas į keletas jo sudedamąsias klases: deterministinį modelį ir statistinį modelį. Deterministinis modelis parodo pagrindinę informaciją apie signalą: ar signalas yra sinusinės formos, ar yra eksponentinė suma, kt. Tokiais atvejais, signalo apibūdinimas yra gan paprastas uždavinys. Viskas, kas reikalaujama yra nustatyti signalo modelio parametrų reikšmes (amplitudę, dažnį, fazę, kt.). Antra signalo modelio plati klasė yra statistinis modelis, kuris bando charakterizuoti statistinius signalo parametrus. Tokių statistinių modelių pavyzdžiai yra Gauso procesas, Poisono procesas, Markovo procesas, paslėptas Markovo procesas. Paslėpta prielaida yra ta, kad signalas gali būti gerai charakterizuotas kaip parametrinis atsitiktinis procesas, ir jo stochastinio proceso parametrai gali būni nustatyti tiksliai, gerai apibūdintai.

Įdomumo dėlei, nusakytas kalbos atpažinimas, abudu deterministiniai ir stochastiniai signalo modeliai turi didelį pasisekimą. Šitame straipsnyje mes orientuosimės į vieną stochastinį signalo modelį, kuris pavadintas paslėptas Markovo modelis (angliškai: hidden Markov model (HMM)). Pirmiausiai mes apžvelgsime Markovo grandinės teoriją ir ją plėsdami prieisime prie paslėpto Markovo modelio, panaudodami kelis pavyzdžius. Tuomet sutelksime savo dėmesį į tris fundamentines problemas, su kuriomis susiduriama projektuojant HMM: stebėjimo eilės tikimybės vertinimas specifiniam HMM; geriausios modelio būsenos eilės nustatymas; modelio parametrų apibrėžimas, siekiant gauti norimą signalo atsakymą. Mes parodysime, kad kai šios tris fundamentinės problemos yra išspręstos, mes galime taikyti HMM nurodytoms problemos spręsti balso atpažinimo sistemose.

Nei paslėpto Markovo modelio, nei balso atpažinimas nėra naujas dalykas. Pagrindinė teorija buvo paskelbta Baumo ir jo kolegų dar vėlyvais 1960, ankstyvais 1970 metais ir pritaikyta balso atpažinimo sprendimams Bakerio CMU ir Jelinek su kolegomis IBM 1970 metais. Tačiau, paplitęs supratimas ir HMM teorijos kalbos atpažinimo sprendimai pasirodė tik prieš kelerius metus. Tai nutiko dėl kelių priežasčių. Pirma, paslėptas Markovo modelis buvo publikuotas matematiniuose žurnaluose, kurie pagrinde nebuvo skaitomi inžinierių, kurie dirbo prie balso atpažinimo. Antra priežastis yra ta, kad pagrindiniai balso atpažinimo sprendimai nebuvo gerai dokumentuoti daugeliams vartotojų, todėl buvo sunku suprasti kokiu principu veikia sprendimas ir inžinieriai negalėjo perkelti modelio į savo tyrimus. Kuomet detalūs vadovai buvo išleisti, inžinieriai perkėlė teoretinį modelį savo laboratorijas. Šitas vadovas yra skirtas suteikti pagrindinės HMM teorijos apžvalgą (kaip ją pateikė Baumas ir jo kolegos), sutekti praktines teorinio metodo diegimo detales ir aptarti keletą nurodytų teoretinių aiškių problemų sprendimų pavyzdžių kalbos atpažinime. Vadovas sudeda iš kelių sudėtų straipsnių ir suteikia vientisą vadovą, kuris suteikia reikiamą užnugarį norint dirbti šios sferos tyrimų srityje.

Šis vadovas susideda iš sekančių sekcijų. Antroje sekcijoje mes apžvelgsime diskrečią Markovo grandinę ir parodysime paslėptos būsenos koncepciją, kur stebėjimas yra problematiška būsenos funkcija, gali būti efektyviai panaudota. Teoriją iliustruosime dvejais pavyzdžiais: monetos supimas, klasikinė kamuoliuko ir urnos sistema. Trečioje sekcijoje mes aptarsime tris fundamentines HMM problemas, ir suteiksime tris praktines technikas jas sprendžiant. Ketvirtoje sekcijoje mes aptarsime skirtinus HMM tipus, kurie buvo išstudijuoti: ergodinis ir kairys-dešinys modelius. Šioje sekcijoje mes taip pat aptarsime skirtingas modelio ypatybes, kaip stebėjimo skaičiaus funkcija, būsenos trukmės skaičius ir optimizavimo kriterijus, pasirenkant teisingas HMM parametrų reikšmes. Penktoje sekcijoje mes aptarsime problemas, kuris kyla diegiant HMM, kaip mastelio keitimas, pradinių parametrų sąmatos, modelio dydis, modelio forma, duomenų praradimas ir daugialypės stebėjimo seką. Šeštoje sekcijoje mes aptarsime izoliuotą žodžių iš balso atpažinimą, kuris yra suprojektuotas, naudojantis HMM idėjomis ir parodysime kaip jis elgiasi, lyginant su kitomis, alternatyviomis sistemomis. Septintoje sekcijoje mes išplėsime idėjas, aptartas šeštoje sekcijoje, ir pritaikysime jas sakinio atpažinimui. Tam mes jungsime atskirus, kiekvieno žodžio HMM modelius. Aštuntoje sekcijoje mes trumpai apžvelgsime didelį balso atpažinimo žodyną ir galiausiai, devintoje sekcijoje mes apibendrinsime visas idėjas, kurias aptarinėjome per visą vadovą.

# Erasmus reziumė

Įsivaizduokite asmenis, kurie didžiąją paros dalį praleidžia prie kompiuterių. Jie nežino kaip gaminti, nežino kaip teisingai reikia skalbti rūbus. O dabar įdėkite juos dviem savaitėmis į stovyklavietę, kur nėra interneto ir tik kelios rozetės, nepažįstamoje Suomijoje, kur žmonės kalba nežinoma kalba. Sudominau?

Viskas prasidėjo ankstų, žvarbų Rugpjūčio 14d rytą. Žinoma, niekas nevyksta be problemų, iš pačio ryto atradau, jog mano transporto priemonėje ( 1986 metų VW Golf ) sudegė kažkoks saugiklis ir maitinimas neateina nei į automagnetolą, nei į pridegiklį ( “prikūrkė” ). Teko ardyti priekinę panelę ir ieškoti kur nugnybti 12V bent jau GPS’ui. Laimė nusišypsojo ir kilniam reikalui pasiaukojo signalizacija.

Truputi pavėlavę išvykti iš Vilniaus, pradėjome savo kelionę. Pirmą Erasmus dvasią turėjom progą pajausti už Rygos, kuomet kelias ėjo šalia Baltijos jūros. Negalėjome nesustoti ir nepasigrožėti. Toliau sekė Rygos hidroelektrinė, Estijos vėjo jėgainės, klaiki naktis prie terminalo esančioje “Statoil” degalinėje, vėjuotos dvi valandos ant kelto tiltelio. Neišdildomas jausmas, kai pamatai ką sugeba padaryti keli tūkstančiai arklio galių su vandeniu.

Ir kaip gi mus pasitiko Helsinkis – 2.50E už 30min stovėjimą miesto centre, požeminėje automobilių stovėjimo aikštelėje. Toliau sekė stovyklavietės paieška. Mano ankščiau suplanuota stovyklavietė kažkur buvo pradingus – į GPS’ą įvestas adresas nuvedė į kažkokį individualių namų rajoną. Tačiau gan greitai radome kitą alternatyvą. Ir štai, sustojome, pastatėme palapinę ir mes jau Helsinkyje, pagal tarptautinę studentų mainų programą, Erasmus.

Žinoma, kur gi be interneto. Stovyklavietėje jo nėra. Mums, kaip tam tikro žmonių sluoksnio atstovams jis būtinas kaip vanduo. Juk reikia pakeisti savo būvimo vietą facebook’e. Artimiausias žinomas taškas iki interneto – mūsų fakultetas. Iki jo 10km pėsčiom. Ko tik negali padaryti elektronikai dėl interneto.

Toli gražu, problemos dėl gyvenamosios vietos nesibaigia. Stovyklavietė užsidaro Rugpjūčio 29 dieną, o bendrabutį gausim tik Rugsėjo 1d. Čia mums pagelbėjo mūsų naujos Erasmus bičiulės – priglaudė mus valgomajame. Ten teko susipažinti su kolektyvinio gyvenimo ypatumais – dvi prancūzės, kurios gyveno tam pačiam kambarių bloke – nenorėjo, jog mes naudotume kambarių bloke esantį dušą, tai dušą naudojom kitame kambarių bloke. Tos prancūzės..

Apsigyvenus bendrabutyje įsijungė automatinis režimas – reikia mokytis. Iš prisiminimų galima ištraukti tik kelis, labiausiai įsimintinus įvykius. Pasidalinsiu su labiausiai įstrigusiu.

Tarp mūsų Erasmus bičiulių įsivyravo viena graži tradicija – kiekvieną šeštadienį rengiamas tarptautinės kulinarijos sesija. Teko paragauti ką valgo vokiečiai, estai, turkai. Teko gaminti ir mums. Asmeniškai pats virtuvės reikaluose nelabai gaudžiausi, tačiau su mažais pamokymais iš dailiosios lyties atstovių – kažkas, visgi ir pavyko. Gaminome bulvinius
blynus su mėsa ir kūgelius. Bulves skutome valandą, tarkavome irgi tiek pat, kepimas užtruko irgi daug laiko. Bendroje sumoje, galima statyti rekordą buvimą virtuvėje – keturios valandos. Tačiau, Erasmus bičiuliams patiko vyriškas gaminimas – virtuvėje stovėti dėl to vertėjo. Vertėjo skleisti Lietuvos dvasią.

Paskutinius savo žodžius norėčiau pašvęsti mokslo sričiai. Dažnas sako, jog Lietuvos švietimas yra blogas. Palaukit. Jūs esate visiškai ir totaliai neteisūs.

Fakultete, kur teko mokytis 4.5 mėnesio, mokslo lygis yra apgailėtinas. Taip, tikinu, jog parinkau tiksliai tam tinkantį būdvardį. Temos nagrinėjamos lėtai ir paviršutiniškai. Kai mokiausi VGTU, Lietuvoje – kiekviena paskaita buvo vis gilesnis žingsnis, vis tolesnis kritimas į visatos pažinimą. Bijau įžeisti Lietuvos kolegijas, bet man atrodo, jog tokiu lygiu, kaip man dėstė Helsinkyje – pas mus atitinka kolegijos lygį. Taigi, Lietuva turi didžiuotis savo dėstytojais ir mokslo sistema.

This slideshow requires JavaScript.