Inteligenta Computationala Integrata

Universitatea “Politehnica” din București

Facultatea de Electronică, Telecomunicații și Tehnologia Informației

Platformă educațională

“inteligența computațională integrată”, implementare în F#

Proiect de diplomă

prezentat ca cerință parțială pentru obținerea titlului de

Inginer în domeniul domeniul Calculatoare și Tehnologia Informației

programul de studii de licență Ingineria Informației

Conducător științific, Absolvent,

Șl. Dr. Ing. Ioana DOGARU Ștefan STOIAN

Prof. Dr. Ing. Radu DOGARU

2016

Cuprins

Introducere…………………………………………………………………………………………………….7

Limbajul de programareF#………………………………………………………………………………………..8

Prezentare generală………………………………………………………………………………………..8

Scurt Istoric…………………………………………………………………………………………………..8

Evoluția limbajului…………………………………………………………………………………………9

Tehnici de programare…………………………………………………………………………………..10

Programare Funcțională……………………………………………………………10

Programare Imperativă……………………………………………………………..11

Programare orientată pe obiect…………………………………………………..11

Programare asincronă ………………………………………………………………12

Instrumente de dezvoltare……………………………………………………………………………….12

De ce F#?:…………………………………………………………………………………………………….14

F# vs C# :……………………………………………………………………………………………………..15

Avantaje ale F# fată de C# :………………………………………………………16

Dezavantaje ale limbajului F#……………………………………………………17

Concluzii……………………………………………………………………………………………………..18

Platforma educațională – implementare în F#………………………………………………………………19

2.1 Instalarea programelor necesare………………………………………………………………………19

2.1.1 Microsoft Visual Studio 2015……………………………………………………….19

2.1.2 NuGet………………………………………………………………………………………..20

2.1.3 Octave……………………………………………………………………………………….21

2.1.4Matlab………………………………………………………………………………………..21

2.2 Machine Learning………………………………………………………………………………………….23

2.2.1Introducere………………………………………………………………………………….23

2.2.2 Puncte Cheie ale Machine Learning………………………………………………23

2.2.3 Alegerea corectă a algoritmului…………………………………………………….24

2.2.4 Pași în dezvoltarea unei aplicații machine learning………………………….24

2.3 Compararea celor 2 implementări……………………………………………………………………25

2.3.1 Informații despre algoritm……………………………………………………………25

2.3.2 Caracteristicile stației de lucru………………………………………………………25

2.3.3 Modulul de conversie a datelor:…………………………………………………….25

2.3.4 Seturi de date………………………………………………………………………………26

2.3.5 Teste realizate în OCTAVE 4.0.2………………………………………………….26

2.3.6 Teste realizate in Visual Studio 2015 – algoritm F#…………………………30

2.3.7 Compararea Rezultatelor………………………………………………………………31

3. Alte implementări…………………………………………………………………………………………………….34

3.1 Clasificarea cifrelor scrise de mână…………………………………………………………….34

3.2 Clasificarea punctelor………………………………………………………………………………..41

Concluzii…………………………………………………………………………………………………………………46

Bibliografie……………………………………………………………………………………………………………..47

Lista figurilor și a tabelelor

Figura 1.1 Logo F#

Figura 1.2 Logo Visual Studio 2015

Figura 1.3 Logo Emacs

Figura 1.4 Logo MonoDevelop

Figura 1.5 Logo SharpDevelop

Figura 1.6 Logo Mbrace

Figura 1.7 Logo Xamarin Studio

Figura 1.8 Logo WebSharper

Figura 1.9 Implementarea in F# vs implementarea în C# a unui modul ce realizează adunarea a două numere.

Figura 2.1 Interfața grafică a mediului de dezvoltare Visual Studio 2015

Figura 2.2 Interfața grafică Visual Studio 2015 – accesarea meniului “Package Manager Console”

Figura 2.3 Interfața grafică Visual Studio 2015 – accesarea meniului “Manage Nuget Package”

Figura 2.4 Setul de date USPS

Figura 3.1 Vizualizarea graficului ce conține setul de date”stranse”

Figura 3.2 Vizualizarea graficului ce conține setul de date”libere”

Figura 3.3 Grafic ce conține vectorii suport identificați de algoritm –pentru datele “libere”

Figura 3.4 Grafic ce contine vectorii suport identificati de algoritm –pentru datele “stranse”

Figura 3.5 Granița de decizie –pentru datele “stranse”

Figura 3.6 Granița de decizie –pentru datele “libere”

Tabelul 1.1 Istoricul versiunilor limbajului F#

Tabelul 2.2 Tabel ce conține rezultatele obținute în urma rulării celor două implementări in Octave si F#

Tabelul 2.3 Tabel ce conține diferențele de performanțe între cele două implemetări și pune în evidență performanțele mai bune ale implementării in F#

Lista acronimelor

CLI – Command Line Interface – interfața liniei de comandă

GPU – Graphics Processing Unit – unitatea grafică de procesare

CLR – Common Language Runtime

.NET – framework de software dezvoltat de Microsoft

ML – Machine Learning

XML – Extensible Markup Language – limbaj de marcare, care reprezintă un set de reguli de formatare a documentelor, inteligibil atât de oameni, cât și de calculatoare;

SVM – Support Vector Machine – vector mașină suport

MUPAD – sistem algebric pentru calculatoare

LCF – logic for computable functions – program interactiv automatizat pentru demonstrarea teoremelor dezvoltat de universitățile din Edinburgh și Standford

Introducere

În ultimele două decenii, Machine Learning a devenit unul dintre pilonii principali ai tehnologiei informației și odată cu asta, o parte importantă a vieților noastre. Având în vedere cantitățile uriașe de date la care avem acces, apariția unor sisteme inteligente pentru analiza si prelucrarea datelor era inevitabilă.

Am ales această temă pentru că mi se pare foarte interesant cum putem ghida un calculator, prin repetarea anumitor date sau caracteristici (set de antrenare), să recunoască forme, modele sau dacă o propoziție este adevarată sau falsă, bazându-se pe anumite presupuneri inițale. Cel de-al doilea motiv pentru care am ales această temă este gradul ridicat de aplicabilitate al problemei recunoașterii formelor în viața de zi cu zi.

Studierea problemei recunoașterii formelor în limbajul F# reprezintă o provocare pentru mine datorită noutații pe care o aduce limbajul de programare. Deși este un superset al lui C#, în F# se pot face anumite lucruri care nu sunt posibile in C#. Pentru cultura mea generală, F# reprezintă un element de noutate și acesta a fost unul dintre motivele pentru care am ales implementarea algoritmului în acest limbaj de programare.

Tema de licență constă în implementarea în F# a algoritmului de recunoastere a formelor studiat la laboratul de Inteligență Computațională, rularea in paralel a celor două implementări pe aceleași seturi de date și prezentarea rezultatelor obținute. Pentru testarea algoritmilor am folosit aceleași seturi de date, două seturi de date consacrate ce conțin imagini ale unor cifre scrise de mână: USPS și OPTD64. Algoritmii afișează timpul de antrenare, timpul de testare, acuratețea si parametrul Gamma optim. Pe partea de implementare în F#, pe lângă rescrierea algoritmului studiat la laborator am dezvoltat incă două programe. Primul program recunoaște imagini cu cifre scrise de mână ce provin din setul de date Semeion și recunoaște o anumită cifră (în cazul nostru este vorba despre cifra 5), încadrând-o într-o anumită clasă. Cel de-al doilea program generează puncte la întâmplare într-un plan XOY, pe care mai apoi le clasifică în funcție de valorile pe care le au atribuite acele puncte.

Pentru realizarea proiectului de licență am folosit limbajul de programare F#, mediul de dezvoltare Microsoft Visual Studio 2015, mediul de dezvoltare Matlab, mediul de dezvoltare Octave și managerul de pachete Nuget cu pachetele necesare.

Limbajul de programare F#

1.1 Prezentare generală

F#(pronunțat F Sharp) este un limbaj de programare care înglobează tehnici de programare funcțională, imperativă și orientată pe obiect. F # este mai des folosit ca un limbaj CLI cross-platform, dar poate fi de asemenea utilizat pentru a genera JavaScript sau cod GPU.

F# este dezvoltat de F# Software Foundation, Microsoft și alți colaboratori. F# Software Foundation pune la dispoziție și un compilator open source pentru F#. F# este de asemenea un limbaj pe deplin acceptat de Visual Studio. Alte tool-uri prin care se poate folosi F# sunt: Mono, MonoDevelop, SharpDevelop, Mbrace și WebSharper. [1]

Limbajul de programare F# face parte din familia de limbaje .NET care include C#, Visual Basic.NET, Jscript.NET și altele. Fiind un limbaj .NET, codul sursă în limbajul F# compilează în cod binar Common Language Infrastructure(CLI) sau Microsoft Intermediate Language (MSIL) care rulează deasupra Common Language Runtime (CLR). Toate limbajele .NET împărtășesc această stare intermediară care le permite să interacționeze foarte ușor între ele și să folosească framework-ul Base Class Library (BCL) al .NET – ului. [1]

1.2 Scurt Istoric:

În zilele noastre sunt folosite în mod predominant trei paradigme de programare: funcțională, imperativă și programarea orientată pe obiect. Programarea funcțională este cea mai veche dintre cele trei, începând cu Limbajul de Procesare al Informației în 1956, devenind populară odată cu apariția limbajului LISP în 1958. De asemenea, fiind o competiție foarte mare în lumea limbajelor de programare, programarea imperativă a ajuns alegerea preferată pentru cercetătorii de știință și afaceri, odată cu apariția limbajului Fortran în anul 1957 și a limbajului COBOL în anul 1959.

În timp ce limbajele de programare imperativă au devenit populare in lumea afacerilor, limbajele de programare funcțională au continuat să se dezvolte în principal ca limbaje de nișă. Limbajul ML a fost dezvoltat de Robin Milner în anul 1973 pentru a îmbunătăți tehnicile de demonstrație ale teoremei LCF. Succesul limbajului ML a dus la dezvoltarea unei întregi familii de limbaje derivate din acesta, incluzând ML Standard, Caml și Ocaml care unifică programarea orientată pe obiect cu programarea funcțională. F# a fost dezvoltata in anul 2005 la Microsoft Research. În multe moduri, F# este o implementare a limbajului Ocaml, combinând puterea și sintaxa expresiilor ale programării funcționale cu zecile de mii de clase care alcătuiesc librăria .NET. [2]

1.3 Evoluția limbajului:

F# utilizează un proces de dezvoltare și inginerie deschisă. Procesul de evoluție al limbajului este gestionat de Don Syme de la Microsoft Research (BDFL-Director benevol pe viață) pentru proiectarea limbajului, în colaborare cu F# Software Foundation. Versiunile anterioare de F# au fost proiectate de Microsoft și Microsoft Research folosind un proces închis de dezvoltare.

F# provine de la Microsoft Research, Cambridge, iar limbajul a fost inițial proiectat și implementat de Don Syme. Andre Kennedy a contribuit la proiectarea de unități de măsură. Visual F# Tools pentru Visual Studio au fost dezvoltate de Microsoft. F# Software Foundation a dezvoltatat compilatorul F# care este open-source și instrumente, încorporând implementarea compilatorului open-source furnizat de Microsoft Visual F# Tool Team. [1]

În cursul dezvoltării sale, limbajul F# a trecut prin mai multe versiuni:

1.4 Tehnici de programare

1.4.1 Programare Funcțională

În cadrul limbajului se utilizează tipul de inferență. Programatorul nu este obligat să declare tipuri de date, compilatorul deduce tipurile de date în timpul compilării. De asemenea, F# admite adnotări explicite de tip și le cere în anumite situații.

Fiecare declarație în F#, incluzând expresiile ce conțin "IF", expresiile de încercare și buclele, este o expresie compusă cu un tip static. Funcțiile și expresiile care nu returnează nici o valoare au un tip de unitate de returnare. F# folosește cuvântul "let" pentru a atribui o valoare unui nume. Exemplu:

Let y=4+9

Îi atribuie lui y valoarea 9

Noile tipuri sunt definite utilizând cuvântul "type". Pentru programarea funcțională, F# oferă tupluri, înregistrări, liste și tipuri opțiuni. Un tuplu reprezintă o colecție de n valori, unde n>=0. Valoarea „n” este numită rangul tuplului. Un 3-tuplu va fi reprezentat că (A,B,C), unde A,B și C sunt valori care pot fi de tipuri diferite. Un tuplu poate fi folosit pentru a stoca valori numai în cazul în care numărul de valori este cunoscut la timpul de implementare și rămâne constant în timpul execuției. [1]

O înregistrare este un tip în care membrii sunt denumiți în felul următor:

{Nume:string; Varsta:int}.

Înregistrările pot fi create ca :

{Nume=”BC”; Varsta=20}.

Cuvântul cheie "with" este folosit pentru a crea o copie a unei înregistrări, ca în { a with Nume="BC" }, care crează o nouă înregistrare, copiind „a” și schimbând valoarea câmpului Nume (presupunând că înregistrarea creată în ultimul exemplu a fost numită a).

Tipul listă este o listă care nu poate fi schimbată, reprezentată fie cu ajutorul unei notații cap::coadă (:: este operatorul cons) sau o prescurtare că [item1; item2; item3]. O listă goală este notată cu []. Tipul de opțiune este un tip de union cu alegeri Some(x) sau None. Tipurile F# pot fi generice, implementate ca tipuri .Net generice. [1]

În F# pot fi folosite funcții lambda și pointeri la funcții ce permit forme rudimentare de închidere (closure). Toate funcțiile în F# sunt funcții de prima clasă și nu se pot schimba. Fiind funcții de prima clasă, înseamnă că ele pot fi folosite ca argumente pentru alte funcții. La fel ca și alte limbaje de programare, F# admite folosirea compunerii funcțiilor utilizând operatorul ”and”. F# admite folosirea expresiilor de secvență care definesc o secvența secv {……}, listă [……….] sau vector […..] printr-un cod care generează valori. De exemplu:

Secv{for b in 0..100 do

If b<20 then

Yield b*b}

formează o secvență de numere ridicate la pătrat de la 0 la 19, filtrând toate numerele care se află în intervalul 0 – 100.

F# folosește modelul de potrivire pentru a atribui valori unor nume. Potrivirea de model este de asemenea utilizată când se folosește union-ul disjunct – union-ul reprezintă potrivirea valorilor împotriva regulilor de model și o regulă este selectată atunci când o potrivire are succes. F# permite folosirea ActivePatterns ca o extensie de potrivire de model. Este folosit, de exemplu, când există mai multe căi de potrivire a unui tip. În F# există o sintaxă generală pentru a defini calcule de compoziție, definite expresii de compoziție. Expresiile de secvență, calculele asincrone și interogările sunt tipuri particulare de expresii de calcul. Expresiile de calcul sunt o implementare a modelului monad. [1]

1.4.2 Programare Imperativă

Support-ul F# pentru programarea imperativă include [1]:

– bucle „for”

– bucle „while”

– liste (vectori), create cu sintaxa [|…|]

– tabele „hash”, create cu sintaxa dict […] sau cu System.Collections.Generric.Dictionary<_,_> tip)

Valorile și înregistrările câmpurilor etichetate ca „mutable”.

//Definim ‚y’ cu valoarea initiala ‚2’

Let mutable y=2

//Schimbam valoarea lui ‚y’ in ‚3’

y<-3

1.4.3 Programare orientată pe obiect

La fel ca alte limbaje CLI, F# poate folosi tipuri CLI și obiecte prin programare orientată pe obiect. Support-ul F# pentru programare orientată pe obiect în expresii include [1]:

– notații „.” (Ex: x.Nume)

– expresii Obiect (Ex: {new obiect() with member x.ToString () = „buna”})

– crearea de obiecte (EX new Forma())

– denumirea argumentelor (Ex: x.Metoda(argumente=1))

– tipuri test (Ex y:? string)

– argumente opționale (Ex x.Metoda (ArgumentOptional=1)

Definițiile tipurilor de obiecte din F# pot fi clase, structuri, interfețe sau enumerări. De exemplu, aici avem o clasă cu un constructor care primește un nume și o vârstă și declară două proprietăți:

Type Persoana(nume: string, varsta: int) =

membru x.nume= nume

membru x.varsta=varsta

1.4.4 Programare asincronă

În F# se poate folosi programarea asincronă prin metode asincrone de lucru. O metodă asincronă de lucru este definită că o secvență de comenzi înăuntrul unui bloc async{..} [1]

let asynctask =

async { let req = WebRequest.Create(url)

let! response = req.GetResponseAsync()

use stream = response.GetResponseStream()

use streamreader = new

System.IO.StreamReader(stream)

return streamreader.ReadToEnd() }

Construcția let! indică faptul că expresia din dreapta trebuie făcută asincron dar flow-ul trebuie să continue numai atunci când rezultatul este disponibil. Blocul asincron poate fi folosit utilizând funcția Async.RunSynchronously. Mai multe blocuri async pot fi executate în paralel utilizând funcția Async.Parallel care ia o lista de obiecte async și crează un alt obiect async care rulează task-urile din lista în paralel. [1]

1.5 Instrumente de dezvoltare:

Instrumentele Visual F# de la Microsoft includ integrare completă în Visual Studio. În momentul în care avem pachetul de limbaj instalat, Visual Studio poate fi folosit pentru a crea proiecte F# și debugger-ul Visual Studio poate fi folosit pentru a face debugging pe cod F#. [4]

• F# poate fi dezvoltat în orice editor de text, cel specific pentru acest limbaj este Emacs.

• MonoDevelop este un mediu de dezvoltare pe Linux în care se poate face programare în F#.

• În SharpDevelop se poate programa în F# încă de la versiunea 3.0

• Mbrace este un framework pentru dezvoltarea aplicațiilor în cod F# pentru cloud.

• Xamarin Studio este o unealtă de dezvoltare foarte utilă în care se poate folosi programare F# încă de la versiunea 3.0

• F# este o parte centrală din framework-ul WebSharper în care codul sursă scris în F# este executat pe server că și cod .NET și este executat că și cod JavaScript pe partea de client.

• Există o pagină web pe care se poate crea si compila cod-ul scris în F# și care conține

resurse pentru dezvoltarea codului în F#: http://www.tryfsharp.org/Create

1.6 De ce F#?:

Limbajul de programare F# se axează pe programare orientată pe date, dar poate fi folosit pentru programarea paralelă sau dezvoltarea algoritmilor. Un avantaj pe care F# îl are în fața altor limbaje de programare cum ar fi C#, C++ sau Visual Basic, este construcția limbajului dezvoltată cu foarte multă grijă în așa fel încât să faciliteze rezolvarea problemelor orientate pe date și manipularea lor într-un mod funcțional. Unul dintre aspectele cheie ale programării funcționale este de a reduce rata bug-urilor pentru a face manipulări de rutină peste structuri de date. [12]

F# este un limbaj funcțional de programare iar una dintre principalele caracteristici este că datele sunt reprezentate într-un mod care se numește imuabil. Acest lucru înseamnă că avem descrierea datelor, ca un fel de design al lor, deci ne putem imagina că facem o fotografie iar programarea este mai mult orientată pe transformarea a ceea ce avem și producerea unei noi imagini ca rezultat. Instagram sau Excel sunt sisteme funcționale în care se iau datele și se menționează cum dorim ca datele să se schimbe in cadrul lor [12]

F# reduce timpul de implementare pentru componentele de software analitic. Regăsim acest tip de programare în special în industria finanțelor și asigurărilor, dar și în domeniul programării orientate pe date sau cel al programării științifice.

Microsoft contribuie la dezvoltarea limbajului F# pentru că dorește o experiență de vârf a programării funcționale pe platformele lor. Ei contribuie cu 3 lucruri:

Visual F# tools, care vine la pachet cu Visual Studio

design-ul limbajului de programare

site-ul Try F# unde se pot găsi informații estențiale despre modul în care funcționează și se utilizează limbajul, cât și un mediu unde se poate dezvolta și testa.

Nu în ultimul rând, comunitatea celor care folosesc limbajul F# este foarte mare. De exemplu, pe StackOverFlow(referință) se găsesc mai mult de 6000 de întrebări despre F# și există foarte multe publicații despre modul în care se poate folosi limbajul de programare.[12]

1.7 F# vs C# :

Motivele pentru dezvoltarea unui limbaj de programare diferit de C# au fost următoarele:

trecerea de la paradigma orientată pe obiect la cea functională care este mult mai potrivită pentru calcule si manipulări de date

punerea in evidență a conceptelor de programare care nu au fost incluse in C# datorită ideologiei diferite

evitarea problemelor de moștenire din C# care nu au fost rezolvate. [14]

F# este un superset al lui C#, așa că orice se poate face în C# se poate face și în F#. În sens invers nu este la fel: în F# se pot face anumite lucruri de care C# nu este capabil. Între F# și alte limbaje .NET există interoperabilitate completă. Odată ce codul din F# este compilat într-un asamblor, acesta poate fi folosit din orice limbaj din familia .NET cum ar fi C# sau VB.NET. [14]

1.7.1 Avantaje ale F# fată de C# :

+ Variante de evitare a referințelor NULL:

În C# există posibilitatea folosirii valorilor NULL în schimbul obiectelor. Acest lucru determină apariția unui număr foarte mare de bug-uri care sunt foarte greu de detectat.

F# nu permite folosirea valorilor NULL, în schimb, trebuie folosit tipul opțiune. Acest tip garanteaza siguranță și deservește același scop: reprezentarea obiectelor care lipsesc, la fel cum fac NULL-urile în C# [14]

+ Tipurile algebrice de date:

C# nu permite folosirea tipurilor algebrice de date care permit crearea structurilor complexe de date din cele simple. Acesta permite tipurile produs sub formă de clase și structuri, dar permite acces limitat pentru tipurile sumă, care sunt reprezentate doar prin enumerări.

F# permite folosirea tipurilor de date algebrice și face posibilă descrierea precisă a entităților de business în termeni de structuri de date, reducând șansele de interpretare greșită a datelor, fapt ce duce la un cod de o calitate înaltă. [14]

+ Transformări vs Mutații :

Limbajul C# incurajeaza mutațiile datelor și folosirea ‚stărilor’. Asta înseamnă că, odată ce un obiect a fost creat, el poate suferi mutații de-a lungul existenței care îi vor schimba ‚starea’. În funcție de ‚starea’ în care se află obiectul la un anumit moment, anumite operații pot sau nu pot fi făcute. Este nevoie de o verificare pentru a vedea dacă un obiect se află sau nu în ‚starea’ potrivită. O verificare incorectă a ‚stării’ obiectelor va duce la apariția bug-urilor și programul nu va rula.

Pe de altă parte, F# încurajează folosirea transformărilor decât a mutațiilor. O transformare nu modifică obiectul și astfel nu îi modifică starea. Aceasta crează un obiect nou și asta înseamnă că vom păstra intact obiectul original, ceea ce înseamnă că un obiect poate fi într-o singură ‚stare’, cea pe care o are de la crearea lui. Faptul că avem de-a face cu o singură ‚stare’ ne va simplifica semnificativ procesul de dezvoltare și se va reduce cantitatea de cod, pentru că, de fiecare dată când vom vedea un obiect vom ști că nu există posibilitatea să fie în altă ‚stare’ decât în cea în care a fost creat și nu va mai fi nevoie să facem verificări ulterioare [14]

+ Expresii vs Declarări:

Având în vedere că C# se bazează pe ‚stări’ și mutații ale obiectelor, ordinea în care mutațiile sunt aplicate este esențială. Acest lucru înseamnă că ordinea în care sunt declarate obiectele în C# este încă un lucru de care trebuie să ne facem griji.

În mod contrar, un program în F# este o expresie foarte mare (o formulă) alcătuită din formule mai mici care mapează valorile de input la valori de output. Ordinea în care diferite bucăți ale expresiei sunt evaluate nu este importantă. Acest lucru ne duce la un cod mai sigur și lipsit de buguri apărute din cauza ordinii în care se fac declarările. [14]

+ Separarea datelor si a logicii:

C# încurajează amestecarea datelor cu logică prin faptul că permite declararea metodelor și a proprietăților sub aceeași clasă sau structura. În momentul în care vine vorba de serializare, logica atașată claselor trebuie distrusă, iar din această cauză clasele trebuie transformate în obiecte simple de date fără nici o logică și doar după acest proces să fie trimise la serializare.

Programarea funcțională sugerează să nu amesteci datele cu logică; că și rezultat, serializarea Json sau Xml este mult mai simplă. [13]

+ Tipul deducție și sintaxa concisă:

Sintaxa limbajului C# este foarte încărcată. Timpul de care avem nevoie pentru a exprima lucruri în C este mult mai mare față de timpul de care avem nevoie pentru a exprima aceleași lucruri în F#. Faptul că C# este un limbaj diluat (încărcat), se datorează nevoii de a specifica tipuri ale parametrilor, metodelor și valorile returnate de acestea. F# are sistem avansat prin care deduce tipurile, valorile, din modul în care acestea sunt folosite, așa că în cele mai multe cazuri este recomandat să omitem specificarea tipurilor de date în codul nostru pentru a lăsa limbajul să își dea seama singur. Mai puțin cod înseamnă productivitate mai mare. [14]

+ Rularea in paralel cu costuri minime

Rularea în paralel a codului C# este un lucru complicat datorită competiției care poate apărea când două fire de execuție încearcă să modifice un obiect în același timp. F# elimină complet această problema prin interzicerea modificării obiectelor după crearea lor, de fiecare dată când este nevoie de o schimbare ce crează un obiect nou prin aplicarea unei transformări a obiectului inițial.[14]

+ Modularitate mai bună

Unitatea logicii de bază în F# este o funcție, în timp ce în C# este o clasă. Funcțiile în F# sunt funcții de prim rang care pot fi folosite ca parametri pentru alte funcții și pot fi returnate ca rezultate ale unei funcții. Scrierea funcțiilor necesită mai puțin efort decât scrierea unei clase. Toate acestea permit un nivel mai fin de modularitate și scenarii de compoziție mult mai complicate cu costuri scăzute. [14]

+ Rezolvarea problemelor generice și nu a celor specifice

F# încurajează folosirea tipurilor generice de date în schimbul folosirii tipurilor concrete. Acelasi algoritm scris pentru tipuri generice va funcționa pe diferite tipuri concrete cum ar fi numere sau strîng-uri sau obiecte complexe. Având doar o implementare generică pentru tipuri diferite, va permite refolosirea codului și lasă mai puțin loc pentru greșeli.[14]

+ Unelte standard pentru generarea parsărilor:

F# are 2 unelte standard pentru generarea parsărilor bazate pe o gramatică formală: FsLex și FsYacc. Aceste unelte sunt numite după Lex și Yacc, două utilizatoare de generare a parsărilor din lumea Unix. FsLex și FsYacc au capacitatea de diagnosticare și pot fi încorporate în procesul de construire ajutând la raționalizarea dezvoltării. [14]

1.7.2 Dezavantaje ale limbajului F#

Următoarele dezavantaje apar numai în cazul în care F# este folosit după principiile programării funcționale. Dacă alegem să nu respectăm aceste principii, dezavantajele vor dispărea.

Curba de învățare abruptă

Pentru o persoană care nu a mai avut experiențe cu programarea funcțională poate fi dificil să se adapteze la un nou mod de gândire în timp ce programează în F#. [14]

Structuri de date complexe

Odată cu folosirea transformărilor în loc de mutații este necesară utilizarea structurilor de date mult mai avansate pentru a manipula eficient datele. [14]

Atribuirea de nume – mult mai dificilă

F# nu are o funcție de încărcare cum are C# pentru metode. Două funcții din F# care ‚stau’ în același modul nu pot împărți aceleași nume, ceea ce crează o dificultate suplimentară în denumirea lor în mod unic. Încă de la bun început trebuie gândită o convenție de nume.[14]

Mai puține unelte avansate

Microsoft investește foarte mult pentru a face cele mai bune unelte pentru programatorii în C#. Din păcate, în F# nu există la fel de multe, ceea ce face scrierea de cod mai puțin confortabilă.[14]

1.8 Concluzii

F# este un limbaj funcțional modern care a fost proiectat ca o alternativă pentru C# și Visual Basic, care onorează caracteristica de limbaj orientat pe obiect. F# a împrumutat cele mai bune caracteristici ale lor și a scăpat de cele care lăsau loc de interpretare și de aceea codul scris în F# este mult mai sigur și mai ușor de întreținut. Deși sunt anumite tipuri de proiecte în care F# ar fi o alegere nepotrivită, acesta trebuie avut în vedere pentru proiecte care se axează pe calcule și manipulări de date. Abilitatea lui F# de a descrie mult mai precis problemele de business decât C# îi oferă statutul de canditat ideal pentru aplicații la nivel de server.

Platforma educațională – implementare în F#

2.1 Instalarea programelor necesare

2.1.1 Microsoft Visual Studio 2015

Pentru implementarea algoritmilor avem nevoie de instalarea Microsoft Visual Studio 2015. Aici ne vom ajuta de programul Dreamspark prin care se oferă acces gratuit studenților la software profesional din gama de programe Microsoft. Site-ul de unde putem descarca programul https://e5.onthehub.com/WebStore/ProductsByMajorVersionList.aspx?ws=4088bd35-a68b-e011-969d-0030487d8897&vsro=8, iar logarea în cont se face în baza adresei de e-mail și a parolei primite de la facultate. Pe lângă faptul că putem descarca gratuit programul, vom avea acces și la cheia de înregistrare care ne dă posibilitatea să folosim toate funcționalitățile programului Microsoft Visual Studio 2015.

În următoarea imagine putem vizualiza meniul aplicație Visual Studio. Din partea de sus se pot accesa toate funcțiile aplicației. În partea dreaptă se regăsește ‚Solution Explorer’ în care putem vizualiza componentele proiectului creat. De aici se pot accesa, pe rând, atât programele dezvoltate cât și algoritmul pe care îl folosim în interiorul lor. În interiorul proiectului, la ‚References’ se regăsesc toate pachetele NuGet necesare acestui proiect iar în fisierul packages.config, care este un fișier de configurare de tip XML, se regăsesc inforrmatii detaliate despre pachetele NuGet instalate cum ar fi numele, versiunea și framework-ul folosit.

În fereastra din partea dreaptă denumită F# Interactive se regăsesc rezultatele rulării cod-ului sursă și aici putem vedea exact ordinea în care se execută programul. În partea centrală se regăsește codul sursă al unuia dintre programele dezvoltate.

2.1.2 NuGet

NuGet este un manager de pachete gratuit și open-source creat special pentru platforma de dezvoltare Microsoft. Acesta este distribuit ca o extensie a programului Visual Studio. Începând cu Visual Studio 2012, NuGet este instalat automat odată cu instalarea programului. De asemenea, acesta poate fi folosit din linia de comandă și automatizat prin scripturi. NuGet poate fi folosit împreună cu mai multe limbaje de programare cum ar fi [15]:

pachete .Net framework

pachete native scrise in C++

Pentru a afla exact de ce pachete avem nevoie, putem accesa site-ul https://www.nuget.org/ la secțiunea Packages, unde găsim în jur de 58 000 de pachete și de asemenea găsim și o scurtă descriere a acestora pentru a ști exact la ce le putem folosi. Programele dezvoltate în acest proiect se folosesc de următoarele pachete:

Fsharp.Core

MathNet.Numerics.Fsharp – oferă metode și algoritmi pentru calcule din domeniul științei, ingineriei și din viața de zi cu zi.

MathNet.Numerics

MSDN.FsharpChart – ajută la crearea de grafice interactive cu date din F# Interactive

mscorlib

System

System.Drawing

System.Numerics

System.Windows.Forms.DataVisualization

Pentru a putea instala pachetele menționate mai sus vom accesa din meniul orizontal din Microsoft Visual Studio 2015: Tools – > NuGet Package Manager – > Package Manager Console

În urmă selectării acestei opțiuni putem vizualiza în partea de jos Package Manager Console unde tastăm comanda ‚install-package’, urmată de numele programului și apoi apăsăm tasta enter. După instalare vom primi un mesaj de succes. Pentru a vizualiza pachetele instalate și adăugate la proiectul actual cât și versiunile lor, putem accesa următorul meniu: Project – > Manage Nuget Packages:

2.1.3 Octave

Octave este un limbaj de programare proiectat în special pentru calculele numerice. Acesta oferă capacitatea de a trata soluțiile numerice ale problemelor liniare și non-liniare și , de asemenea, oferă posibilitatea creării de grafice extensive pentru vizualizarea și manipularea datelor. În mod normal, acesta este folosit prin interfață interactivă de linie de comandă, dar poate fi folosit și pentru a scrie programe mai puțin interactive. Limbajul Octave este similar cu Matlab și de aceea majoritatea programelor sunt portabile. Octave este programul în care se rulează cod-ul sursă al aplicațiilor din laborator. Acesta se poate descarca gratuit de pe pagina oficială https://www.gnu.org/software/octave/ . Pentru executarea programelor am folosit ultima versiunea a programului, Octave 4.0.2 [16]

2.1.4 Matlab

Matlab este un mediu de dezvoltare pentru calculele numerice ce conține limbajul de programare cu același nume. Limbajul de programare a fost dezvoltat de MathWorks și acesta permite manipularea matricilor, plotarea funcțiilor și a datelor, implementarea algoritmilor și crearea de interfețe cu userul. Deși Matlab are ca scop principal calculele numerice, o unealtă suplimentară folosește motorul de simboluri MuPAD care permite accesul la calculele cu simboluri. La acest

program se poate adauga un pachet suplimentar, Simulink, care permite simularea graficelor în mai multe domenii pentru sistem dinamice și încorporate. În 2004, Matlab avea în jur de 1 milion de utilizatori care provin din domenii diverse cum ar fi domeniul ingineriei, al științei sau al economiei. [17]

Varianta gratuită a programului se poate descărca de la https://uk.mathworks.com/programs/trials/trial_request.html, iar pentru acces la toate funcțiile este nevoie de achiziționarea unei licențe. Varianta folosită de mine în proiect este R2012a iar în momentul de față, programul a ajuns la versiunea R2016a, lansată pe 3 martie 2016.

În Matlab am realizat conversia datelor din format .mat în format .csv, pentru a fi citite și încărcate în programul realizat în F#.

Machine Learning

2.2.1 Introducere

Machine Learning este o ramură a științei calculatoarelor care a evoluat din studiul recunoașterii modelelor și teoria computațională de învățare în inteligență artificială. În 1959, Arhur Samuel a definit Machine Learning că: ‘Ramură a studiului care oferă calculatoarelor posibilitatea de a învăța fără a fi programate în mod explicit.’[18]

Machine learning se află la intersecția dintre știinta calculatoarelor, inginerie și statistică și de cele mai multe ori apare și în alte discipline. Este un instrument care poate fi aplicat la mai multe tipuri de probleme. Orice câmp care are nevoie să interpreteze sau să acționeze asupra datelor poate beneficia de tehnicile machine learning. Machine learning se folosește de statistică. Pentru cea mai mare parte dintre oameni, statistică este un subiect ezoteric folostit de către companii pentru a minți despre cât de grozave sunt produsele lor. De aici se naște întrebarea: de ce, pentru restul dintre noi, e nevoie de statistică? În domeniul ingineriei suntem obișnuiți să rezolvăm o problema deterministă unde soluția noastră va rezolva întotdeauna problema. Dacă suntem nevoiți să scriem un program pentru a controla un automat de cafea, este bine că acesta să funcționeze tot timpul, indiferent de câte butoane se apasă sau câți bani se introduc în el. În viață există foarte multe probleme ale căror soluție nu este deterministă. [18]

2.2.2 Puncte Cheie ale Machine Learning

În această secțiune vom pune în evidență punctele cheie ce trebuie atinse pentru a crea un mediu de lucru ce ne ușurează muncă de a transformă un algoritm de machine learning într-o aplicație care funcționează.

O sarcina importantă în machine learning este clasificarea. În acest pas este nevoie să prezicem din ce clasa trebuie să facă parte o anumită parte din date. Regresia reprezintă prezicerea unei valori numerice. Clasificarea și regresia sunt exemple de învățare supervizată. Acest set de probleme se numește supervizat deoarece noi îi spunem algoritmului ce anume să prezică. Opusul este reprezentat de învățarea nesupervizata. În învățarea nesupervizata nu avel etichete sau valori date pentru datele noastre. Aici avem nevoie să găsim valori statistice pentru a descrie datele (estimarea densității). [19]

2.2.3 Alegerea corectă a algoritmului

În primul rând avem nevoie să stabilim la ce rezultat avem nevoie să ajungem și ce încercăm să facem din acest algoritm. Dacă avem nevoie să prezicem o valoare țintă atunci trebuie să ne folosim de învățarea supervizată. Dacă alegem învățarea supervizată trebuie că mai apoi să ne dăm seama care este valoarea țintă la care vrem să ajungem:[19]

Da/nu , 1/2/3 , a/b/c , roșu/galben/abastru – dacă este de genul acesta atunci trebuie să ne folosim de clasificare

Valori de la 0-100 sau de la -555 la 555 – de este de genul acesta atunci trebuie să ne folosim de regresie.

Dacă nu avem nevoie să prezicem o valoarea țintă atunci trebuie să ne folosim de învățarea nesupervizata. În cazul în care încercăm să încadrăm datele în anumite grupuri atunci avem nevoie de grupare. În cazul în care avem nevoie de o estimare numerică a cât de bună este gruparea atunci ne putem folosi de un algoritm de estimare a densității.

În oricare dintre cazurile prezentate mai sus ne aflăm, trebuie petrecut ceva timp pentru a ne cunoaște cât mai bine datele pentru care dorim să aplicăm algoritmul și cu cât vom ști mai multe despre ele, cu atât vom putea să construim o aplicație de succes. [19]

2.2.4 Pași în dezvoltarea unei aplicații machine learning

Modul în care am implementat și dezvoltat programele prezentate în acest proiect urmează o procedura similară cu:

a) Colectarea datelor. Putem extrage datele de pe un site web, api, dispozitiv care colectează anumite măsurători și trimite datele sau direct dintr-un fișier.

b) Prepararea datelor de intrare. Din momentul în care am reușit să încărcăm datele e nevoie să ne asigurăm că sunt într-un format în care le putem utiliza. În cazul algorimilor noștri, datele sunt structurate sub formă de matrice de anumite dimensiuni ce conține valori de 1 și 0 – reprezentând cifra scanată și apoi un vector de 10 elemente care conține valoarea 1 pe poziția corespunzătoare cifrei scanate. Prepararea datelor este în funcție de algoritmul folosit.

c) Analiza datelor de intrare. Acest pas se poate rezuma la citirea și înțelegerea datelor parsate într-un editor de text pentru a fi sigur că pașii 1 și 2 funcționează și că avem valori. Plotarea datelor în una sau mai multe dimensiuni poate fi de ajutor.

d) Antrenarea algoritmului. În acest moment are loc învățarea mașinii. Aici oferim algorimului date bune și clare de la primii doi pași și extragem informații despre ele. Aceste informații sunt necesare pentru următorii doi pași.

e) Testarea algoritmului. În acest pas se folosec informațiile extrase mai devreme. Când evaluăm un algoritm, îl vom testa că să vedem cât de bine se descurcă. În cazul învățării supervizate, avem câteva valori cunoscute pe care le putem folosi pentru a evalua performanța algoritmului. În cazul învățării nesupervizate, trebuie să folosim alte metrice pentru a evalua performanțele.

f) Folosirea algoritmului. La acest pas realizăm un program care să se foloseasca de algoritmul ales și încercăm și tot la acest pas ne putem da seama dacă pașii anteriori au funcționat așa cum ne așteptăm. [19]

2.3 Compararea celor 2 implementări

2.3.1 Informații despre algoritm

Introducere teoretică:

In Machine Learning, metodele Kernel sunt o clasă de algoritmi pentru analiza modelelor, al caror cel mai cunoscut membru este Vectorul Mașină Suport (SVM). Sarcina principală a analizei de model este sa găsească și să studieze tipurile generale de relații in seturi de date. Pentru mulți algoritmi care rezolvă aceste probleme, seturile de date trebuie sa fie transformate din forma lor brută in vectori care au și o hartă de reprezentare. In contrast, metodele kernel au nevoie doar de un kernel specificat de utilizator.[20]

Vectorii mașină suport au fost inventați de Vladimir Vapnik în anul 1979. În forma liniară, aceștia reprezintă un hiperplan care separă un set de exemple pozitive față de un set de exemple negative cu margine maximă. În cazul liniar, marginea este definită ca fiind distanța de la hiperplan la cel mai apropiat exemplu pozitiv, respectiv negativ. [23]

Optimizarea secvențială minimă (SMO) este un algoritm simplu care poate rezolva foarte rapid problema QP fara alte matrici de înmagazinare și fără a folosi absolut deloc pași de optimizare.[23]

Programul creat pentru recunoașterea cifrelor scrise de mână se folosește de algoritmul SMO,care functioneaza in felul urmator:

– asignăm coeficienți Alpha fieăarei observații;

– iterăm prin observații, alegem la întâmplare o altă observație pe care încercăm să o pivotăm updatând coeficienții Alpha pentru perechea selectată, respectând câteva constrângeri;

– până când niciun coeficient Alpha nu va mai fi modificat pentru un timp. [21]

Coeficienții Alpha au valori cuprinse între 0 și o limită superioară C, iar odată ce algoritmul termină de rulat, observațiile cu Alpha> 0, vectorii suport, sunt folosite pentru a genera o limită de separare.[21]

2.3.2 Caracteristicile stației de lucru

Stația pe care au fost rulate testele are urmatoarele caracteristici:

procesor Intel® Core™ i3-4000M Processor

(3M Cache, 2.40 GHz)

4 gb memorie RAM

placă video Nvidia Geforce GT 740M

sistem de operare Windows 10 , 64 biti.

2.3.3 Modulul de conversie a datelor:

În platforma de laborator se folosesc date de antrenare și de testare din fișiere aflate pe mașina locală. Fișierele sunt în format .MAT . Pentru citirea datelor în programul implementat în F# a fost nevoie ce conversia lor la formatul .csv. Conversia datelor a fost realizat în Matlab:

>> FileData = load('optd64_train.mat');

csvwrite('optd64_train.csv', FileData.M);

Am rulat această secvență de cod pentru fiecare dintre seturile de antrenare și testare ale fisierelor cu date.

2.3.4 Seturi de date

■ USPS

-USPS(US Poștal) este un set de date derivat dintr-un proiect de recunoaștere a caracterelor scrise de mâna pe plicuri.

† Set de antrenare: 7291 – conține 7291 imagini 16 X 16 și un vector de etichete cu 7291 valori

† Set de testare: 2007 – conține 2007 imagini 16 x 16 și un vector de etichete cu 2007 valori

■ OPTD64

† Set de antrenare: 3823 – conține 3823 imagini 8 x 8 și un vector de etichete cu 3823 de valori

† Set de testare: 1797 – conține 1797 imagini 8 x 8 și un vector de etichete cu 1797 de valori

2.3.5 Teste realizate în OCTAVE 4.0.2

Setul de date OPTD64 cu parametrul gamma cuprins în intervalul [0.1 1]. Limita superioară a intervalului este de 10 ori mai mare decât limita inferioară a intervalului:

[best_conf, best_acc, best_par, model]=osusvm(2,[0.1 1],'optd64'); best_acc, best_par, sum(model.nSV),

Kernel_type: 2

Kernel_par: 0.1

Antrenarea a durat 4.8443 secunde

Testarea a durat 2.124 secunde

Kernel_par: 0.28

Antrenarea a durat 15.44 secunde

Testarea a durat 9.6838 secunde

Kernel_par: 0.46

Antrenarea a durat 18.09 secunde

Testarea a durat 3.8217 secunde

Kernel_par: 0.64

Antrenarea a durat 18.538 secunde

Testarea a durat 3.9097 secunde

Kernel_par: 0.82

Antrenarea a durat 17.323 secunde

Testarea a durat 4.3706 secunde

Kernel_par: 1

Antrenarea a durat 22.912 secunde

Testarea a durat 6.2164 secunde

best_acc = 98.442

best_par = 0.10000

ans = 1399

Se observă că, pentru acest interval, acuratețea este de 98,442 % .

La valoarea parametrului = 0,1 , antrenarea a durat 4,8443 secunde iar testarea a durat 2,124 secunde, cu un număr de 1399 de vectori suport.

În continuare, vom restrânge intervalul și vom verifică rezultatele. Aplicăm algoritmul pentru gamma cuprins în intervalul 0.01 și 0.1:

[best_conf, best_acc, best_par, model]=osusvm(2,[0.01 0.1],'optd64'); best_acc, best_par, sum(model.nSV),

Kernel_type: 2

Kernel_par: 0.01

Antrenarea a durat 1.4914 secunde

Testarea a durat 1.1618 secunde

Kernel_par: 0.028

Antrenarea a durat 1.6246 secunde

Testarea a durat 1.1608 secunde

Kernel_par: 0.046

Antrenarea a durat 2.1462 secunde

Testarea a durat 1.4431 secunde

Kernel_par: 0.064

Antrenarea a durat 2.8719 secunde

Testarea a durat 1.6597 secunde

Kernel_par: 0.082

Antrenarea a durat 3.6634 secunde

Testarea a durat 1.8668 secunde

Kernel_par: 0.1

Antrenarea a durat 6.0833 secunde

Testarea a durat 1.9033 secunde

best_acc = 98.442

best_par = 0.046000

ans = 1076

Observăm că la un interval cu valori de 10 ori mai mici obținem rezultate mai bune. Acuratețea este de 98,442 %, iar cele mai bune rezultate le obținem pentru valoarea parametrului=0,046. Antrenarea durează 2.1462 secunde, iar testarea durează 1.4431 secunde, cu un număr de 1076 de vectori suport.

Mai facem încă o încercare și micșorăm intervalul, de dată această verificăm capacitatea de antrenare și testare a algoritmului pentru gamma cuprins în intervalul 0.001 și 0.01:

>> [best_conf, best_acc, best_par, model]=osusvm(2,[0.001 0.01],'optd64'); best_acc, best_par, sum(model.nSV),

Kernel_type: 2

Kernel_par: 0.001

Antrenarea a durat 2.3675 secunde

Testarea a durat 1.8563 secunde

Kernel_par: 0.0028

Antrenarea a durat 1.6382 secunde

Testarea a durat 1.3885 secunde

Kernel_par: 0.0046

Antrenarea a durat 1.8193 secunde

Testarea a durat 1.3675 secunde

Kernel_par: 0.0064

Antrenarea a durat 1.5566 secunde

Testarea a durat 1.3469 secunde

Kernel_par: 0.0082

Antrenarea a durat 1.5497 secunde

Testarea a durat 1.1718 secunde

Kernel_par: 0.01

Antrenarea a durat 1.431 secunde

Testarea a durat 1.1993 secunde

best_acc = 97.551

best_par = 0.010000

ans = 764

Se observă că rezultatele sunt mai slabe decât cele obținute în testul anterior. Acuratețea este de 97,551 %, iar cele mai bune valori ale timpului de antrenare – 1.431 secunde și ale timpului de testare – 1.1993 secunde se obțin pentru gamma = 0.01.

-setul de date USPS cu parametrul gamma cuprins în intervalul 0.01 și 0.1. Limita superioară a intervalului este de 10 ori mai mare decât limita inferioară a intervalului:

>> [best_conf, best_acc, best_par, model]=osusvm(2,[0.01 0.1],'usps'); best_acc, best_par, sum(model.nSV),

Kernel_type: 2

Kernel_par: 0.01

Antrenarea a durat 12.078 secunde

Testarea a durat 5.1792 secunde

Kernel_par: 0.028

Antrenarea a durat 27.069 secunde

Testarea a durat 7.5473 secunde

Kernel_par: 0.046

Antrenarea a durat 50.174 secunde

Testarea a durat 10.729 secunde

Kernel_par: 0.064

Antrenarea a durat 70.768 secunde

Testarea a durat 12.615 secunde

Kernel_par: 0.082

Antrenarea a durat 90.539 secunde

Testarea a durat 15.557 secunde

Kernel_par: 0.1

Antrenarea a durat 108.239 secunde

Testarea a durat 16.573 secunde

best_acc = 95.466

best_par = 0.010000

ans = 1521

Cele mai bune rezultate au fost obținute pentru gamma = 0.01 cu o acuratețe de 95.466 %, timp de antrenare de 12.078 secunde și un timp de testare de 5.1792 secunde, cu un număr de 1521 de vectori suport.

În continuare, vom aplică același algoritm dar pentru parametri cuprinși în intervalul [0.001 0.01]:

[best_conf, best_acc, best_par, model]=osusvm(2,[0.001 0.01],'usps'); best_acc, best_par, sum(model.nSV),

Kernel_type: 2

Kernel_par: 0.001

Antrenarea a durat 11.602 secunde

Testarea a durat 5.6405 secunde

Kernel_par: 0.0028

Antrenarea a durat 9.5343 secunde

Testarea a durat 4.8886 secunde

Kernel_par: 0.0046

Antrenarea a durat 10.049 secunde

Testarea a durat 4.6612 secunde

Kernel_par: 0.0064

Antrenarea a durat 10.698 secunde

Testarea a durat 4.9903 secunde

Kernel_par: 0.0082

Antrenarea a durat 10.981 secunde

Testarea a durat 4.9106 secunde

Kernel_par: 0.01

Antrenarea a durat 11.667 secunde

Testarea a durat 4.4186 secunde

best_acc = 95.466

best_par = 0.010000

ans = 1521

Se observă că, pentru acest interval, acuratețea este de 95,466 %. La valoarea parametrului=0,01 , antrenarea a durat 11.667secunde iar testarea a durat 4.4186 secunde, cu un număr de 1521 de vectori suport.

În continuare, vom restrânge intervalul și vom verifică rezultatele. Aplicăm algoritmul pentru gamma cuprins în intervalul 0.0001 și 0.001:

[best_conf, best_acc, best_par, model]=osusvm(2,[0.0001 0.001],'usps'); best_acc, best_par, sum(model.nSV),

Kernel_type: 2

Kernel_par: 0.0001

Antrenarea a durat 23.423 secunde

Testarea a durat 9.0194 secunde

Kernel_par: 0.00028

Antrenarea a durat 13.565 secunde

Testarea a durat 6.3605 secunde

Kernel_par: 0.00046

Antrenarea a durat 11.368 secunde

Testarea a durat 6.1128 secunde

Kernel_par: 0.00064

Antrenarea a durat 12.33 secunde

Testarea a durat 5.0571 secunde

Kernel_par: 0.00082

Antrenarea a durat 9.3126 secunde

Testarea a durat 4.8059 secunde

Kernel_par: 0.001

Antrenarea a durat 9.0194 secunde

Testarea a durat 4.6473 secunde

best_acc = 93.871

best_par = 0.0010000

ans = 1536

Se observă că pentru intervalul [0.0001 0.001], la valoarea parametrului egală cu 0.001 obținem acuratețe 93.871 % cu un timp de antrenare de 23.423 secunde și un timp de testare de 9.0194 secunde.

2.3.6 Teste realizate in Visual Studio 2015 – algoritm F#

Vom realiza aceleași teste pe aceleași baze de date și cu aceiași parametri, dar de această data testele vor fi făcute în Visual Studio 2015 cu ajutorul programului implementat în F#. Algoritmul implementat în F# face mai întâi o căutare a parametrului optim într-un interval menționat, după care evaluează performanțele algoritmului pentru acel parametru. Totuși, pentru relevanța testelor, vom rula programul pentru aceiași parametri testați și la implementarea în Octave.

† Setul de date OPTD64 cu parametrul gamma cuprins în intervalul [0.1 1] . Limita superioară a intervalului este de 10 ori mai mare decât limita inferioară a intervalului:

let model = smo setantrenare etichetaantrenare rbfKernel parametrii

let clasificare = classifier rbfKernel model

printfn "Antrenarea a durat"

evaluate clasificare (setantrenare, etichetaantrenare)

// validare pe restul de mostre

printfn "Testarea a durat "

evaluate clasificare (setvalidare, etichetavalidare)

printfn "Gata"

Antrenarea a durat 4,128 secunde

Testarea a durat 1,8411 secunde

Proportie corect clasificata: 98,77 %

parametrul gamma în intervalul [0.01 0.1]

Antrenarea a durat 1,8445secunde

Testarea a durat 0.9998 secunde

Proporție corect clasificată: 98,79 %

parametrul gamma în intervalul [0.001 0.01]

Antrenarea a durat 1.998 secunde

Testarea a durat 0.9772 secunde

Proporție corect clasificată: 97,85 %

Setul de date USPS

parametrul gamma în intervalul [0.01 0.1]

Antrenarea a durat 10,389 secunde

Testarea a durat 4.4452 secunde

Proporție corect clasificată: 96,01 %

parametrul gamma în intervalul [0.001 0.01]

Antrenarea a durat 9.9887 secunde

Testarea a durat 3.8522 secunde

Proporție corect clasificată: 96,01 %

parametrul gamma în intervalul [0.0001 0.001]

Antrenarea a durat 20.991 secunde

Testarea a durat 7.8244 secunde

Proportie corect clasificata: 94,22 %

2.3.7 Compararea Rezultatelor

După ce am aplicat algoritmii dezvoltați în Octave și F# pentru cele 2 seturi de date, OPTD64 și USPS, pentru aceiași parametri, am realizat următorul tabel în care putem vedea exact rezultatele rulării celor 2 algoritmi:

Prin culoarea albastră am evidențiat rezultatele obținute în urma rulării algoritmului dezvoltat în F# iar prin culoarea portocalie am evidențiat rezultatele obținute în urma rulării algoritmului dezvoltat în Octave.

În cele ce urmează am realizat un tabel în care putem observă diferențele de performanță dintre cele două programe.

Putem observa că rezultatele obținute în urmă rulării algoritmului în F# sunt mult mai bune față de cele în Octave. În funcție de setul de date și parametrul optim pentru care se face testarea, acuratețea în cazul algoritmului implementat în F# este mai bună cu un procent aflat în intervalul [0.299% 0.544%], timpul de antrenare este mai mic cu valori cuprinse în intervalul [0.2312 s 2.432 s] și timpul de testare este mai mic cu valori cuprinse în intervalul [0.2221 s 1.195s]

Având în vedere toate acestea, putem concluziona că algoritmul implementat în F# are rezultate mult mai bune decât cel implementat în Octave.

Alte implementări

3.1 Clasificarea cifrelor scrise de mână

Setul de date pe care îl folosim este setul Semeion, care se poate găsi pe pagină http://archive.ics.uci.edu/ml/index.html .

Setul de date constă în 1593 de cifre scanate, scrise de 80 de oameni diferiți. Fiecare poză este stocată ca 256 de valori (1 sau 0), reprezentând dimensiunea de 16×16 pixeli a cifrei scanate și 10 valori (1 sau 0), unde 1 marchează cifra care a fost scrisă. [23]

Mai întâi, avem nevoie să luăm datele de pe site :

#load "SupportVectorMachine.fs"

open System.IO

open System.Net

open MachineLearning.SupportVectorMachine

// colectarea datelor de la UC Irvine Machine Learning

let adresa = "http://archive.ics.uci.edu/ml/machine-learning-databases/semeion/semeion.data"

let cerere = WebRequest.Create(adresa)

let raspuns = cerere.GetResponse()

let flux = raspuns.GetResponseStream()

let cititor = new StreamReader(flux)

let date = cititor.ReadToEnd()

cititor.Close()

flux.Close()

Timpul de execuție: Real: 00:00:00.000, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0

Se observă că datele se încarcă instant, timpul de procesare fiind 0.

Creăm un web request și transformăm rezultatul în date, care la acel moment conține un strîng gigantic – setul nostru de date. Trebuie să transformăm setul de date în forma pe care programul nostru o necesită, care este un vector de observații și un vector de etichete. Pentru a putea face acestea, trebuie să împărțim datele în linii și să transformam fiecare linie în 256 de numere (observațiile noastre) și eticheta observației în felul următor:

// o linie în setul de date este 16 x 16 = 256 pixels,

// urmată de 10 cifre, 1 ne arată cifra

let parsare (line: string) =

let parsat = line.Split(' ')

let observatii =

parsat

|> Seq.take 256

|> Seq.map (fun s -> (float)s)

|> Seq.toList

let eticheta =

parsat

|> Seq.skip 256

|> Seq.findIndex (fun e -> (int)e = 1)

observatii, eticheta

// randează o cifră scanată ca "ASCII-art"

let randare observatii =

printfn " "

List.iteri (fun i pix ->

if i % 16 = 0 then printfn "" |> ignore

if pix > 0.0 then printf "■" else printf " ") observatii

// clasificator: cifra 5 si restul cifrelor

let setdate, etichete =

date.Split((char)10)

|> Array.filter (fun l -> l.Length > 0) // datorita ultimei linii

|> Array.map parsare

|> Array.map (fun (data, l) ->

data, if l = 5 then 1.0 else -1.0 )

|> Array.unzip

Timpul de execuție : Real: 00:00:00.209, CPU: 00:00:00.218, GC gen0: 9, gen1: 2, gen2: 0

Funcția de parsare va împărți linia în funcție de spații, iar primele 256 de elemente și le transformă într-o lista de valori de tip float (bucată de observare) și identifica cifra scanată verificând poziția marcată cu 1 în bucată finală de date (ex: ‘3’ este codat în felul următor: 0 0 0 1 0 0 0 0 0 0 ).

Clasificatorul SVM știe să facă diferența doar între 2 clase. În programul nostru vom încerca să recunoaștem cifra ‘5’ . Vom procesa strîng-ul de date, îl vom sparge într-un vector de 10 caractere, eliminăm ultima parte (fișierul se termină cu o linie de final), aplicăm funcția de parsare care transformă fiecare linie într-o combinație de observare/eticheta și reducem etichetele în valori de 1 sau -1. 1 pentru cifra 5 și -1 pentru restul cifrelor.

În partea de final a programului am afișat cifrele scrise de mâna și rezultatul recunoașterii cifrei:

// randează o cifră scanată ca "ASCII-art"

let randare observatii =

printfn " "

List.iteri (fun i pix ->

if i % 16 = 0 then printfn "" |> ignore

if pix > 0.0 then printf "■" else printf " ") observații

Exemplu de imagini cu cifre scrise de mână:

■■■■■■■■■■■■

■■

■■

■■

■■

■

■■

■■

■■■

■■

■■

■■

■■■■■■ ■■

■■■■■■ ■■

■■■■ ■■■

■■■■■

******************************************

Clasa 1.000000, clasificată ca 1.00000

■■■■

■■■■

■■■

■■■■

■■■■

■■■■

■■■■

■■■ ■■■

■■■■■■■■■■■■

■■■■■■■■ ■■■■

■■■■■ ■■■■

■■■■■■ ■■■■

■■■■■■■■■■■ ■■■

■■■■■■■■■■■■■■■

■■■■■■■■■■■■■

■■■■

******************************************

Clasa -1.000000, clasificată ca -1.000000

În prima imagine avem cifra ‘5’ pe care o clasifică corect și îi atribuie clasa 1, iar în cea de-a doua imagine avem cifra ‘6’ pe care o clasifică corect, atribuindui clasa -1.

Pentru a antrena clasificatorul am setat parametri de căutare și am ales un kernel de radial basis, am împărțit setul de date în 600 de observații pentru antrenare, iar restul pentru validare.Timpul de execuție pentru împărțirea setului de date într-un set de validare și unul de antrenare este:

Timpul de execuție : Real: 00:00:38.042, CPU: 00:00:36.984, GC gen0: 637, gen1: 3, gen2: 0

Procentul prin care fiecare grup este bine recunoscut se realizează în următorul bloc de cod :

let calitate clasificare sample =

sample

|> Array.map (fun (d, l) -> if (clasificare d) * l > 0.0 then 1.0 else 0.0)

|> Array.average

|> printfn "Proportie corect clasificata: %f"

// imparte setul de date după etichetă si calculează calitatea pentru fiecare grup

let evaluate clasificare (setdate, etichete) =

let grup1, grup2 =

Array.zip setdate etichete

|> Array.partition (fun (d, l) -> l > 0.0)

calitate clasificare grup1

calitate clasificare grup2

Timp de execuție: Real: 00:00:00.000, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0

Clasificatorul este o funcție care ia o observație și returnează o valoare de tip float: dacă rezultatul este mai mare decât 0.0, atunci predicția este grupul cu eticheta 1.0, altfel este grupul cu eticheta -1. ‘Mostră’este un vector de tupluri – o observație și eticheta 1 sau -1. ‘Calitate’ calculează procentul observațiilor bine clasificate prin înmulțirea predicțiilor pentru fiecare observație. Dacă predicita și eticheta au același semn, produsul lor este pozitiv iar predicția este corectă: mapam predicțiile corecte cu 1.0 și cu 0.0 pe cele incorecte. Procentul observațiilor bine clasificate este media predicțiilor. ‘Evaluate’ are aceeași structura, dar mai întâi împarte datele în 2 grupuri separate prin clasa. Ne putem imagina că avem un clasificator care prezice dacă o cifra nu este ‘5’ pentru fiecare observație. Acest clasificator ar fi corect în 90 % din cazuri deoarece 90 % din mostre se află în acea clasa. Pe de altă parte, împărțirea în clase va rezultă într-un procent de recunoaștere de 100% într-un grup și de 0% în celălat, această fiind o informație mult mai bună și mai exactă.

Prin rularea codului sursă de mai jos putem evalua rezultatele clasificatorului:

// verifică clasificarea setului de antrenare

printfn "Clasificare in setul de antrenare"

evaluare clasificare (setantrenare, etichetaantrenare)

// validare pe restul de mostre

printfn "Clasificare in setul de validare"

evaluare clasificare (setvalidare, etichetavalidare)

Clasificare in setul de antrenare

Proportie corect clasificata: 1.000000

Proportie corect clasificata: 0.988889

Clasificare in setul de validare

Proporție corect clasificată: 0.949495

Proporție corect clasificată: 0.980984

Timp de execuție : Real: 00:00:00.233, CPU: 00:00:00.218, GC gen0: 3, gen1: 0, gen2: 0

Clasificarea este foarte bună în setul de antrenare și destul de bună în setul de validare: 95% dintre cifrele de ‘5’ au fost recunoscute corect și 98% pentru restul de date.

Parametrii c=5.0 și sigma=10.0 pentru kernelul radial basis au fost aleși prin încercare și prin verificarea rezultatelor obținute cu fiecare varianta. La finalul scriptului avem o secvență de cod care testează valori diferite ale parametrilor C și Sigma și afișează procentele obținute.

for c in [ 0.1; 1.0; 10.0 ; 5.0] do

for s in [ 0.1; 1.0; 10.0 ] do

let parametrii = { C = c; Tolerance = 0.001; Depth = 10 }

let rbfKernel = radialBias s

printfn "Model cu C = %f, s = %f" c s

let model = smo setantrenare etichetaantrenare rbfKernel parametrii

let clasificare = classifier rbfKernel model

printfn "Clasificarea in setul de antrenare"

evaluare clasificare (setantrenare, etichetaantrenare)

// validare pe restul de mostre

printfn "Clasificarea in setul de validare"

evaluare clasificare (setvalidare, etichetavalidare)

printfn "Gata"

Timp de execuție:Real: 00:01:59.298, CPU: 00:01:54.937, GC gen0: 1849, gen1: 15, gen2: 2

Clasificarea punctelor

Pentru inceput vom crea 2 seturi de date cu puncte aranjate la intamplare intr-un sistem XoY, cu valori ale lui X si Y intre 0 si 100:

// set date aglomerate separate liniar : nu există margine între cele 2 grupuri

let datestranse =

[| for i in 1 .. 200 -> [ rang.NextDouble() * 100.0; rang.NextDouble() * 100.0 ] |]

let etichetestranse =

datestranse |> Array.map (fun el ->

if (el |> List.sum >= 100.0) then 1.0 else -1.0)

// set date libere separate liniar: este un spațiu gol intre cele 2 grupuri

let datelibere =

datestranse

|> Array.filter (fun e ->

let tot = List.sum e

tot > 110.0 || tot < 90.0)

let etichetelibere =

datelibere |> Array.map (fun el ->

if (el |> List.sum >= 100.0) then 1.0 else -1.0)

Primul set de date este împărțit în părțile de Nord – Vest și Sud – Est ale diagonalei: punctele care indeplinesc condiția X+Y>100 sunt clasificate că ‘1’, altfel vor fi clasificate că ‘-1’. Set-ul nostru de date este la baza un set de date liniar separabile.

Al doilea set de date (l-am numit noi ‘liber’): luăm primul set de date și filtrăm punctele care îndeplinesc condiția 90< X+Y<110. Punctele care îndeplinesc condiția mai sus menționată sunt cele apropiate de granița.

Vizualizarea seturilor de date se face cu următorul bloc de cod:

set amestecare (setdate: (float * float) seq) (etichete: 'a seq) =

let dupaeticheta = Seq.zip etichete setdate |> Seq.toArray

let eticheteunice = Seq.distinct etichete

FSharpChart.Combine

[ // separarea punctelor după clasă si amestecarea lor

for eticheta in eticheteunice ->

let date = Array.filter (fun e -> eticheta = fst e) dupaeticheta

|> Array.map snd

FSharpChart.Point(date) :> ChartTypes.GenericChart

|> FSharpChart.WithSeries.Marker(Size=10) ]

|> FSharpChart.Create

amestecare (tightData |> List.map (fun e -> e.[0], e.[1])) etichetestranse
amestecare (looseData |> List.map (fun e -> e.[0], e.[1])) etichetelibere

În continuare, vom vizualiza vectorii suport identificați de algoritm. Am mapat vectorii suport la 3 grupuri: 0 dacă Alpha este mai mare decât 0 (observația a fost selectată ca vector suport), iar pentru restul, 1 sau 2 în funcție de eticheta observației.

Proporție corect clasificată: 1.000000

Timp de execuție: Real: 00:00:00.001, CPU: 00:00:00.015, GC gen0: 0, gen1: 0, gen2: 0

Proporție corect clasificată: 0.995000

Real: 00:00:00.001, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0

Din graficele prezentate mai sus ne putem da seama că algoritmul funcționează. De o parte și de altă a diagonalei putem distinge două blocuri mari de observații și un grup mic de puncte roșii care se regăsesc foarte aproape de granița. Rezultatul nu este perfect (unele puncte sunt destul de depărtate față de granița) dar asta se așteaptă de la algoritm, să calculeze o aproximare.

Pentru a vizualiza granița de decizie vom rula următorul bloc de cod:

vizualizarelinieseparatoare datelibere etichetelibere estimatorliber

vizualizarelinieseparatoare datestranse etichetestranse estimatorstrans

Concluzii

Pentru finalizarea acestui proiect am parcurs toți pașii ce țin de dezvoltarea unei aplicații machine learning: colectarea datelor, analiza datelor de intrare, antrenarea algoritmului, testarea algoritmului si folosirea lui pentru a obține rezultate. În cadrul acestei lucrari am implementat algoritmul de recunoaștere a formelor în limbajul de programare F# folosind-mă de mediul de dezvoltare Microsoft Visual Studio 2015 și de pachete Nuget specifice Machine Leaning.

Rularea in paralel a celor două implementări ale algoritmilor de recunoaștere a formelor ne dezvaluie un rezultat mai bun în cazul implemntării algoritmului in F#. Rezultatele obținute sunt in medie cu jumătate de procent mai bune în cazul acurateții cu care sunt recunoscute datele introduse si cu 15-20% în cazul timpilor de antrenare și de testare.

Din punctul meu de vedere, rezultatele obținute sunt destul de bune dar sunt conștient că se pot obține rezultate mult mai bune de atât. Eu sunt de părere că un limbaj de programare se poate invăța într-o perioadă mai scurtă de timp, dar pentru a maximiza performanțele obținute prin dezvoltarea si implementarea unor algoritmi, este nevoie de multă experiență de lucru cu acel limbaj de programare.

F# este un limbaj complex de programare și acomodarea cu el depinde foarte mult de utilizator și de ceea ce a folosit înainte. Faptul ca este un superset al limbajului C# il face mult mai “accesibil” programatorilor care au folosit C# dar are și anumite caracteristici care pot fi mai greu de inteles. Un avantaj important al limbajului este că, odată ce codul din F# este compilat într-un asamblor, acest poate fi folosit din orice limbaj din familia #NET.

Ca și temă viitoare de cercetare poate fi luată in considerare imbunătațirea algoritmului, dar acest lucru presupune un studiu amănunțit al limbajului de programare si aprofundarea problemei recunoașterii formelor. Maximizarea rezultatelor duce la un potențial economic ridicat al aplicației, iar toate acestea se pot realiza cu o utilizare redusă de resurse.

Bibliografie

[1] https://en.wikipedia.org/wiki/F_Sharp_(programming_language) accesat la 22.02.2016

[2] https://en.wikibooks.org/wiki/F_Sharp_Programming/Introduction accesat la 18.04.2016

[3] https://en.wikibooks.org/wiki/F_Sharp_Programming accesat la 18.04.2016

[4] https://en.wikibooks.org/wiki/F_Sharp_Programming/Getting_Set_Up accesat la 19.04.2016

[5] http://bscsofucp.blogspot.ro/2015/11/visual-studio-professional-2015.html accesat la 21.04.2016

[6] https://lists.gnu.org/archive/html/emacs-devel/2015-10/msg01751.html accesat la 21.04.2016

[7] https://commons.wikimedia.org/wiki/File:Monodevelop_Logo.svg accesat la 21.04.2016

[8] http://www.zwodnik.com/software/windows/sharpdevelop/ accesat la 15.05.2016

[9] https://www.xamarin.com/branding accesat la 15.05.2016

[10] http://try.websharper.com/example/todo-list accesat la 20.05.2016

[11] http://www.infoworld.com/article/2613049/development-tools/article.html accesat la 03.06.2016

[12] http://www.slideshare.net/alexeyraga/f-intro accesat la 03.06.2016

[13] http://www.codeproject.com/Articles/741874/What-is-Fsharp accesat la 15.06.2016

[14] https://en.wikipedia.org/wiki/NuGet accesat la 17.06.2016

[15] https://en.wikipedia.org/wiki/GNU_Octave accesat la 17.06.2016

[16] https://en.wikipedia.org/wiki/MATLAB accesat la 17.06.2016

[17] https://en.wikipedia.org/wiki/Machine_learning accesat la 17.06.2016

[18] http://www2.ift.ulaval.ca/~chaib/IFT-4102-7025/public_html/Fichiers/Machine_Learning_in_Action.pdf accesat la 17.06.2016

[19] https://en.wikipedia.org/wiki/Sequential_minimal_optimization accesat la 25.06.2016

[20] http://clear-lines.com/blog/post/Support-Vector-Machine-in-FSharp.aspx accesat la 25.06.2016

[21] https://www.mathworks.com/matlabcentral/mlc-downloads/downloads/submissions/48567/versions/1/screenshot.jpg accesat la 26.06.2016

[22] http://archive.ics.uci.edu/ml/index.html accesat la 26.06.2016

[23] https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/tr-98-14.pdf accesat la 27.06.2016

ANEXE

Program Clasificarea Punctelor

#load "SVM.fs"

#r @"..\..\ProiectLicenta\pachete\MSDN.FSharpChart.dll.0.60\lib\MSDN.FSharpChart.dll"

#r "System.Windows.Forms.DataVisualization"

open MachineLearning.SupportVectorMachine

open System

open System.Drawing

open System.Windows.Forms.DataVisualization

open MSDN.FSharp.Charting

// ******** Evaluation utilities ********

// cream o amestecare de puncte pe axele X si Y, cu o formatare diferita pe fiecare eticheta

let amestecare (setdate: (float * float) seq) (etichete: 'a seq) =

let dupaeticheta = Seq.zip etichete setdate |> Seq.toArray

let eticheteunice = Seq.distinct etichete

FSharpChart.Combine

[ // separarea punctelor dupa clasa si amestecarea lor

for eticheta in eticheteunice ->

let date =

Array.filter (fun e -> eticheta = fst e) dupaeticheta

|> Array.map snd

FSharpChart.Point(date) :> ChartTypes.GenericChart

|> FSharpChart.WithSeries.Marker(Size=10)

]

|> FSharpChart.Create

// vizualizare vectori support selectati din setul de date

let vizualizaresuport (data: float list []) (etichete: float []) estimator =

let etichete =

estimator

|> (fst)

|> Seq.map (fun row ->

if row.Alpha > 0.0 then 0

elif row.Label < 0.0 then 1

else 2)

let date =

estimator

|> (fst)

|> Seq.map (fun row -> (row.Data.[0], row.Data.[1]))

amestecare date etichete

// afisare set de date si a 'liniei de separare'

let separare (setdate: (float * float) seq) (etichete: 'a seq) (line: float -> float) =

let dupaeticheta = Seq.zip etichete setdate |> Seq.toArray

let eticheteunice = Seq.distinct etichete

FSharpChart.Combine

[ // separarea punctelor dupa clasa si amestecarea lor

for eticheta in eticheteunice ->

let date =

Array.filter (fun e -> eticheta = fst e) dupaeticheta

|> Array.map snd

FSharpChart.Point(date) :> ChartTypes.GenericChart

|> FSharpChart.WithSeries.Marker(Size=10)

// printare linie intre dreapta si stanga – majoritatea punctelor

let x = Seq.map fst setdate

let minX, maxX = Seq.min x, Seq.max x

let datelinie = [ (minX, line minX); (maxX, line maxX)]

yield FSharpChart.Line (datelinie) :> ChartTypes.GenericChart

]

|> FSharpChart.Create

let vizualizarelinieseparatoare (date: float list []) (etichete: float []) estimator =

let w = weights (fst estimator)

let b = snd estimator

let line x = – b / w.[1] – x * w.[0] / w.[1]

separare (date |> Seq.map (fun e -> e.[0], e.[1])) etichete line

// Proportie a celor corect clasificate

let calitate (date: float list []) (etichete: float []) classify =

let performanta =

date

|> Array.map (fun row -> classify row)

|> Array.zip etichete

|> Array.map (fun (a, b) -> if a * b > 0.0 then 1.0 else 0.0)

|> Array.average

printfn "Proportie corect clasificata: %f" performanta

////Testare seturi de date

let rang = new Random()

// set date aglomerate separate linear : nu exista margine intre cele 2 grupuri

let datestranse =

[| for i in 1 .. 200 -> [ rang.NextDouble() * 100.0; rang.NextDouble() * 100.0 ] |]

let etichetestranse =

datestranse |> Array.map (fun el ->

if (el |> List.sum >= 100.0) then 1.0 else -1.0)

// set date libere separate linear: este un spatiu gol intre cele 2 grupuri

let datelibere =

datestranse

|> Array.filter (fun e ->

let tot = List.sum e

tot > 110.0 || tot < 90.0)

let etichetelibere =

datelibere |> Array.map (fun el ->

if (el |> List.sum >= 100.0) then 1.0 else -1.0)

// set date mari separate linear (1000 observatii, 10 dimensiuni)

let datemari =

[| for i in 1 .. 5000 -> [ for d in 1 .. 10 -> rang.NextDouble() * 100.0 ] |]

let etichetemari =

datemari |> Array.map (fun x ->

if (x |> List.sum >= 500.0) then 1.0 else -1.0)

// Set date separate non-linear (discul razei este=30, centrat in (40, 60))

let datecirculare =

[| for i in 1 .. 1000 -> [ rang.NextDouble() * 100.0; rang.NextDouble() * 100.0 ] |]

let centru = [ 40.0; 60.0 ]

let distanta (coord1: float list) coord2 =

List.map2 (fun c1 c2 -> (c1-c2)*(c1-c2)) coord1 coord2

|> List.sum

|> sqrt

let etichetecirculare =

datecirculare

|> Array.map (fun data -> dist data centru)

|> Array.map (fun dist -> if dist >= 30.0 then 1.0 else -1.0)

// validarea mostrelor

// printare set date initiale

// identificare vectori support

let parametri = { C = 0.6; Tolerance = 0.001; Depth = 50 }

let kernelliniar = dot

// set date aglomerate

printfn "Set date aglomerate"

amestecare (datestranse |> Array.map (fun e -> e.[0], e.[1])) etichetestranse

let estimatorstrans = smo datestranse etichetestranse kernelliniar parametri

vizualizaresuport datestranse etichetestranse estimatorstrans

vizualizarelinieseparatoare datestranse etichetestranse estimatorstrans

let clasificatorstrans = classifier kernelliniar estimatorstrans

calitate datestranse etichetestranse clasificatorstrans

// set date libere

printfn "Set date libere"

amestecare (datelibere |> Array.map (fun e -> e.[0], e.[1])) etichetelibere

let estimatorliber = smo datelibere etichetelibere kernelliniar parametri

vizualizaresuport datelibere etichetelibere estimatorliber

vizualizarelinieseparatoare datelibere etichetelibere estimatorliber

let clasificatorliber = classifier kernelliniar estimatorliber

calitate datelibere etichetelibere clasificatorliber

// Set date circulare

let biasKernel = radialBias 30.0

printfn "Set date circulare"

amestecare (datecirculare |> Array.map (fun data -> data.[0], data.[1])) etichetecirculare

let estimatorcircular = smo datecirculare etichetecirculare biasKernel parametri

vizualizaresuport datecirculare etichetecirculare estimatorcircular

let clasificatorcircular = classifier biasKernel estimatorcircular

calitate datecirculare etichetecirculare clasificatorcircular

// Set de date mare

printfn "Set date mare"

let estimatormare = smo datemari etichetemari kernelliniar parametri

let clasificatormare = classifier kernelliniar estimatormare

calitate datemari etichetemari clasificatormare

Program Recunoașterea Cifrelor scrise de mână

#load "SVM.fs"

open System.IO

open System.Net

open MachineLearning.SupportVectorMachine

// colectarea datelor de la UC Irvine Machine Learning

let adresa = "http://archive.ics.uci.edu/ml/machine-learning-databases/semeion/semeion.data"

let cerere = WebRequest.Create(adresa)

let raspuns = cerere.GetResponse()

let flux = raspuns.GetResponseStream()

let cititor = new StreamReader(flux)

let date = cititor.ReadToEnd()

cititor.Close()

flux.Close()

// prepararea datelor

// o linie in setul de date este 16 x 16 = 256 pixels,

// urmata de 10 cifre, 1 ne arata cifra

let parsare (line: string) =

let parsat = line.Split(' ')

let observatii =

parsat

|> Seq.take 256

|> Seq.map (fun s -> (float)s)

|> Seq.toList

let eticheta =

parsat

|> Seq.skip 256

|> Seq.findIndex (fun e -> (int)e = 1)

observatii, eticheta

// randeaza o cifra scanata ca "ASCII-art"

let randare observatii =

printfn " "

List.iteri (fun i pix ->

if i % 16 = 0 then printfn "" |> ignore

if pix > 0.0 then printf "■" else printf " ") observatii

// clasificator: cifra 5 si restul cifrelor

let setdate, etichete =

date.Split((char)10)

|> Array.filter (fun l -> l.Length > 0) // datorita ultimei linii

|> Array.map parsare

|> Array.map (fun (data, l) ->

data, if l = 5 then 1.0 else -1.0 )

|> Array.unzip

let parametrii = { C = 5.0; Tolerance = 0.001; Depth = 20 }

let rbfKernel = radialBias 10.0

// imparte setul de date in date de validare si data de antrenare

let dimensiunemostra = 600

let setantrenare = setdate.[ 0 .. (dimensiunemostra – 1)]

let etichetaantrenare = etichete.[ 0 .. (dimensiunemostra – 1)]

let setvalidare = setdate.[ dimensiunemostra .. ]

let etichetavalidare = etichete.[ dimensiunemostra .. ]

printfn "Clasificator de antrenare"

let model = smo setantrenare etichetaantrenare rbfKernel parametrii

let clasificare = classifier rbfKernel model

//arata media corect clasificata

let calitate clasificare mostra =

mostra

|> Array.map (fun (d, l) -> if (clasificare d) * l > 0.0 then 1.0 else 0.0)

|> Array.average

|> printfn "Proportie corect clasificata: %f"

// imparte setul de date dupa eticheta si calculeaza calitatea pentru fiecare grup

let evaluare clasificare (setdate, etichete) =

let grup1, grup2 =

Array.zip setdate etichete

|> Array.partition (fun (d, l) -> l > 0.0)

calitate clasificare grup1

calitate clasificare grup2

// verifica clasificarea setului de antrenare

printfn "Clasificare in setul de antrenare"

evaluare clasificare (setantrenare, etichetaantrenare)

// validare pe restul de mostre

printfn "Clasificare in setul de validare"

evaluare clasificare (setvalidare, etichetavalidare)

// Calibrarea

for c in [ 0.1; 1.0; 10.0 ; 5.0] do

for s in [ 0.1; 1.0; 10.0 ] do

let parametrii = { C = c; Tolerance = 0.001; Depth = 10 }

let rbfKernel = radialBias s

printfn "Model cu C = %f, s = %f" c s

let model = smo setantrenare etichetaantrenare rbfKernel parametrii

let clasificare = classifier rbfKernel model

printfn "Clasificarea in setul de antrenare"

evaluare clasificare (setantrenare, etichetaantrenare)

// validare pe restul de mostre

printfn "Clasificarea in setul de validare"

evaluare clasificare (setvalidare, etichetavalidare)

printfn "Gata"

// afiseaza primele 100 de cifre scanate si clasificarea lor

Array.sub (Array.zip setdate etichete) dimensiunemostra (dimensiunemostra + 99)

|> Array.iter (fun (d, l) ->

printfn ""

printfn "******************************************"

let predicted = if (clasificare d) > 0.0 then 1.0 else -1.0

printfn "Clasa %f, clasificata ca %f" l predicted

randare d)

Algoritm SVM

namespace MachineLearning

module SVM=

open System

// O observatie, eticheta ei, si estimarea curenta pentru Alpha

type VectorSuport = { Data: float list; Label: float; Alpha: float }

// Un kernel transforma doua puncte de date intr-un float

type Kernel = float list -> float list -> float

// Parametri de input pentru algoritmul SVM

type parametri = { toleranta: float; C: float; adancime: int }

// Descrierea tipurilor de bucle pentru cei doi algoritmi

type bucla = Full | Subset

let switch bucla =

match bucla with

| Full -> Subset

| Subset -> Full

type Constructor() =

member this.Bind(x, f) =

match x with

| Some(x) -> f(x)

| _ -> None

member this.Delay(f) = f()

member this.Return(x) = Some x

// Limita pentru ceea ce este considera prea mic pentru schimbare

let modificaremica = 0.00001

// Produsul vectorilor

let punct (vector1: float list)

(vector2: float list) =

List.fold2 (fun acc v1 v2 ->

acc + v1 * v2) 0.0 vec1 vec2

// distanta dintre doi vectori

let distanta (vector1: float list)

(vector2: float list) =

List.fold2 (fun acc v1 v2 ->

acc + (v1 – v2) * (v1 – v2)) 0.0 vector1 vector2

// functia radial bias

let rbf sign2 x = exp ( – x / sign2 )

// kernel-ul radial bias

let radialBiaskernel sigma

(vector1: float list)

(vector2: float list) =

rbf (sigma * sigma) (distanta vector1 vector2)

// prinderea unei valori x care este in afara limitelor de min si de max

let prindere (min, max) x =

if (x > max)

then max

elif (x < min)

then min

else x

// identificam daca un vector support are limita

let estegranita parametri sv = sv.Alpha <= 0.0 || sv.Alpha >= parametri.C

// identificam limitele ale schimbarilor acceptate pentru alpha

let gasirejossus (jos, sus) sv1 sv2 =

if sv1.Label = sv2.Label

then max jos (sv1.Alpha + sv2.Alpha – high), min sus (sv2.Alpha + sv1.Alpha)

else max jos (sv2.Alpha – sv1.Alpha), min sus (high + sv2.Alpha – sv1.Alpha)

// calculam limitele schimbarilor pentru Alpha, daca este posibil

let schimbaregranite (jos, sus) sv1 sv2 =

let l, h = gasirejossus (jos, sus) sv1 sv2

if h > l then Some(l, h) else None

// calculul erorilor pentru vectorii support, cu valorile curente ale lui alpha

let eroare (randuri, b) kernel sv =

randuri

|> Seq.filter (fun r -> r.Alpha > 0.0)

|> Seq.fold (fun acc r ->

acc + r.Label * r.Alpha * (kernel r.Data sv.Data)) (b – sv.Label)

// verificare daca alpha poate fi modificat pentru vector suport, avand in vedere predictia curenta a erorii si a parametrului C

let schimbare parametri sv eroare =

(eroare * sv.eticheta < – parametri.toleranta && sv.Alpha < parametri.C)

|| (eroare * sv.eticheta > parametri.toleranta && sv.Alpha > 0.0)

// functia de utilitate

let f kernel sv1 sv2 alpha1 alpha2 =

sv1.eticheta * (alpha1 – sv1.Alpha) * (kernel sv1.Data sv2.Data) +

sv2.eticheta * (alpha2 – sv2.Alpha) * (kernel sv1.Data sv2.Data)

// facem update pe constanta de model b

let updateb kernel b sv1 sv2 alpha1' alpha2' iError jError C =

let b1 = b – iError – f kernel sv1 sv2 alpha1' alpha2'

let b2 = b – jError – f kernel sv2 sv1 alpha2' alpha1'

if (0.0 < alpha1' && alpha1' < C)

then b1

elif (0.0 < alpha2' && alpha2' < C)

then b2

else (b1 + b2) / 2.0

let calculeta kernel sv1 sv2 =

let eta = 2.0 * kernel sv1.Data sv2.Data – kernel sv1.Data sv1.Data – kernel sv2.Data sv2.Data

if eta >= 0.0 then None else Some(eta)

//alegerea unui index la intamplare altul decat i in [0 .. (numar-1) ]

let alegerealtul (rng: System.Random) i count =

let j = rng.Next(0, count – 1)

if j >= i then j + 1 else j

// gasirea celui de-al doilea vector pentru pivotarea cu vectorul suport i

let identificarecanditat (svs: vectorsuport []) b kernel (rng: Random) parametri i =

let sv1 = svs.[i]

let error1 = error (svs, b) kernel sv1

match (schimbare parametri sv1 error1) with

| false -> None

| true ->

let candidati =

Seq.mapi (fun i sv -> (i, sv)) svs

|> Seq.filter (fun (i, sv) -> not (estegranita parametri sv))

|> Seq.toArray

if (Array.length candidati > 1)

then // returneaza vector suport cu cea mai mare diferenta de eroare

let (j, sv2, error2) =

candidati

|> Seq.map (fun (i, sv) -> (i, sv, error (svs, b) kernel sv))

|> Seq.maxBy (fun (i, sv, e) -> abs (error1 – e))

Some((i, sv1, error1), (j, sv2, error2))

else // incercare random

let j = pickAnother rng i (Array.length svs)

let sv2 = svs.[j]

let error2 = error (svs, b) kernel sv2

Some((i, sv1, error1), (j, sv2, error2))

let poate = MaybeBuilder()

// incercare pivotare o pereche de vectori suport

let pivotarepereche (svs: vectorsuport []) b kernel parametri data1 data2 =

let (i, sv1, error1) = data1

let (j, sv2, error2) = data2

maybe {

let! lo, hi = schimbaregranite (0.0, parameters.C) sv1 sv2

let! eta = calculeta kernel sv1 sv2

let! alpha2' =

let candidat = prinde (lo, hi) (sv2.Alpha – (sv2.Label * (error1 – error2) / eta))

if (abs (candidat – sv2.Alpha) < schimbaremica) then None else Some(candidat)

// pivotul a reusit; continua cu alpha updatati

let alpha1' = sv1.Alpha + (sv1.Label * sv2.Label * (sv2.Alpha – alpha2'))

let b' = updateB kernel b sv1 sv2 alpha1' alpha2' error1 error2 parametri.C

let svsupdatat =

svs

|> Array.mapi (fun index value ->

if index = i

then { value with Alpha = alpha1' }

elif index = j

then { value with Alpha = alpha2' }

else value)

return (svsupdatat, b') }

// Optimizare minima secventiala

let smo setdate etichete (kernel: Kernel) parametri =

// prepararea datelor

let dimensiune = setdate |> Array.length

let svsinitial =

Array.zip etdate etichete

|> Array.map (fun (d, l) -> { Data = d; Label = l; Alpha = 0.0 })

let b = 0.0

let rang = new Random()

// cauta prin bucla recursiva prin observatii, updateaza alpha

let rec cautare (current: vectorsuport []) b iter bucla =

let pivoti =

match bucla with

| Full -> seq { 0 .. size – 1 }

| Subset ->

seq { 0 .. size – 1 }

|> Seq.filter (fun i -> not (estegranita parametri current.[i]))

let schimbari = 0 // numara perechile schimbare in buca

// updateaza vectorii suport si b, incercand sa se faca un pivot pe fiecare index

Seq.fold (fun (svs, b, chs) index ->

match (identificarecandidat svs b kernel rang parametri index) with

| None -> (svs, b, chs)

| Some(sv1, sv2) ->

match (perechepivot svs b kernel parametri sv1 sv2) with

| None -> (svs, b, chs)

| Some(svs', b') -> (svs', b', chs + 1))

(current, b, changes) pivots

let (svs, b, changes) = updated

if (changes = 0 && loop = Subset)

then

printfn "Convergenta atinsa: nici o schimbare in vectorii suport."

(svs, b)

elif (iter > parametri.Depth)

then

printfn "Nici o convergenta, iterarea a atins limita."

(svs, b)

else cautare svs b (iter + 1) (switch loop)

// cautare

search svsinitia b 0 Full

// calculeaza greutatile folosing vectorii supor rezultati din SVM

let greutati svs =

svs

|> Seq.filter (fun sv -> sv.Alpha > 0.0)

|> Seq.map (fun sv ->

let multiplicare = sv.Alpha * sv.eticheta

sv.Data |> List.map (fun e -> mult * e))

|> Seq.reduce (fun acc row ->

List.map2 (fun a r -> a + r) acc row )

// creaza o functie de calsificare din rezultatele svm

let clasificator (kernel: Kernel) estimator =

// functia clasificator

fun obs ->

let (svs, b) = estimator

svs

|> Seq.filter (fun sv -> sv.Alpha > 0.0)

|> Seq.fold (fun acc sv ->

acc + sv.Label * sv.Alpha * (kernel sv.Data obs)) b