TSM - Machine Learning la modul practic

Sergiu Indrie - Software Engineer@iQuest

Consider că software de calitate înseamnă a face viața utilizatorului cât de ușoară posibil. Această calitate nu constă doar în îndeplinirea sarcinii în mod corect și eficient, dar și în simplificarea operaţiei fără a pierde funcționalitate. Foarte multe din sarcinile noastre zilnice ar putea fi simplificate dacă software-ul nostru ar fi capabil să facă sugestii, să încerce să ghicească și să automatizeze munca noastră. Aceasta este o posibilă utilizare pentru tehnicile machine learning. Pe lângă aceasta, aplicaţii precum motoare de căutare web, sisteme de recunoaștere a imaginilor și a sunetelor, detectarea spam-ului și multe altele folosesc machine learning pentru a soluționa probleme care altfel ar fi aproape irezolvabile.

Explicația

Cu toate că machine learning poate apărea ca o tehnică complexă și grea de aplicat, asemănător cu toate conceptele din domeniul calculatoarelor, totul se rezumă la secvențe de 1 și 0 (poate chiar mai mult ca de obicei). Principiul de bază din spatele acestei idei este matematică simplă. Dacă vreau să determin gradul de asemănare dintre două elemente complexe, dar definirea declarativă a unor funcții de comparare este mult prea dificilă, atunci voi transforma elementele complexe în numere și voi lăsa calculatorul să determine similitudinea lor.

Exemplu

Avem o bază de utilizatori cu următoarele informații:

Dorim să oferim utilizatorilor similari conținut asemănător despre hobby-uri (ideea fiind că oamenii asemănători preferă lucruri similare). Astfel, prin transformarea datelor de intrare în date numerice (în mod manual sau automat) ca în tabelul următor:

putem să trasăm următorul grafic:

Pe baza graficului putem observa faptul că cele două puncte din partea superioară sunt mai apropiate (mai ales dacă atribuim greutăți caracteristicilor importante). Acestă apropiere a punctelor indică asemănarea utilizatorilor (utilizatorii cu id-ul 2 și 3). În acest caz, această asemănare este dată de valorile apropiate ale vârstei.

Determinarea acestei asemănări în mod matematic s-ar realiza prin calcularea distanței dintre cele 2 puncte, o funcție similară cu distanța Euclidiană dar cu parametri de greutate:

unde u și v sunt doi vectori, reprezentând 2 puncte (elemente), iar fiecare vector este compus din 2 valori, vârstă și oraș (uage, ucity) ; iar uage și ucity reprezintă greutățile celor 2 atribute, vârstă și oraș.

Cu ajutorul a numeroase exemple pozitive și negative (training data), algoritmul se poate ajusta astfel încât să determine în mod corect asemănarea a două elemente.

Trei utilizări importante pentru machine learning care utilizează principiul de mai sus sunt:

  1. Recomandări - analizează preferințele unui utilizator și ,pe baza asemănării dintre utilizatori, oferă sugestii privind potențiale preferințe noi.

  2. Clustering - grupează elemente similare (nu necesită training data explicit).

  3. Clasificare - atribuie categorii elementelor pe baza atribuirilor anterioare.

Exemplificarea aplicației

Una din cele mai populare librării de machine learning în Java este Weka. Vom folosi API-urile Weka pentru a scrie un simplu program de clasificare machine learning.

Dorim să replicăm funcționalitatea Gmail Priority Inbox în aplicația desktop de e-mail Geary, astfel încât la recepționarea unui nou e-mail, vom putea determina în mod automat apartenența acestuia la una din cele cinci categorii: Principal, Social, Promoții, Noutăți și Forum.

Reprezentarea datelor

Primul pas este reprezentarea datelor. Definirea celor 5 categorii este simplă, vom folosi un index de la 1 la 5. Codificarea conținutului unui e-mail este puțin mai dificilă. În acest gen de probleme, soluția este de obicei reprezentarea unui segment de text prin utilizarea modelului bag-of-words. Ideea din spatele acestui model este ilustrarea segmentului de text printr-un vector de numărare a cuvintelor.

Să luăm următoarele enunțuri:

  1. Eu mănânc mere.
  2. Eu mănânc. Eu programez.

Utilizând cele două texte de mai sus, putem crea un dicționar comun atribuind indecși fiecărui cuvânt unic.

Astfel putem obține următoarele reprezentări ale celor două segmente de text:

1, 1, 1, 0
2, 1, 0, 1

Fiecare număr din vectorii de mai sus indică numărul de apariții ale cuvântului cu acel index în dicționar. (Al 2-lea vector începe cu numărul 2, indicând 2 apariții ale cuvântului "Eu").

Pentru a simplifica această aplicație vom folosi un model parțial bag-of-words. Vom defini un dicționar care va conține doar un cuvânt cheie relevant pentru fiecare categorie.

Folosind dicționarul de mai sus vom reprezenta următorul e-mail:

Salut tată. Să nu uiți să mă iei de la grădiniță. A și tată, să nu întârzii!

în următorul vector de cuvinte:

2, 0, 0, 0, 0

Cod Weka

Pentru a începe să scriem programul folosind API-ul Weka, în prima fază trebuie să definim formatul de date. Vom începe prin a descrie un rând de date.

// create the 5 numeric attributes corresponding to 
// the 5 category keywords
Attribute dadCount = new Attribute("dad");
Attribute congratulateCount = new Attribute("congratulate");
Attribute discountCount = new Attribute("discount");
Attribute reminderCount = new Attribute("reminder");
Attribute groupCount = new Attribute("group");

Fiecare rând trebuie să fie asociat cu una din cele 5 categorii, astfel continuăm cu definirea atributului pentru categorie.

// Declare the class/category attribute along with 
// its values
FastVector categories = new FastVector(5);
categories.addElement("1");
categories.addElement("2");
categories.addElement("3");
categories.addElement("4");
categories.addElement("5");
Attribute category = new Attribute("category", categories);

În final colectăm toate atributele într-un vector de atribute.

// Declare the feature vector (the definition of one data row)
FastVector rowDefinition = new FastVector(6);
rowDefinition.addElement(dadCount);
rowDefinition.addElement(congratulateCount);
rowDefinition.addElement(discountCount);
rowDefinition.addElement(reminderCount);
rowDefinition.addElement(groupCount);
rowDefinition.addElement(category);
Training Data

Algoritmii de clasificare de tip machine learning necesita date de antrenament pentru ajustarea parametrillor interni cu scopul de a oferi cele mai bune rezultate. În scenariul nostru, trebuie să oferim programului exemple de categorizări a e-mail-urilor.

Pentru scopul acestui program vom genera training data prin utilizarea clasei de mai jos:

public class TrainingDataCreator {
   public static void main(String[] args) 
   throws IOException {
   ICombinatoricsVector valuesVector = Factory.createVector(new String[]{"0", "1", "2", "3", "4"});

   Generator gen = Factory.
      createPermutationWithRepetitionGenerator(valuesVector, 5);

      File f = new File("category-training-data.csv");
      FileOutputStream stream = FileUtils.openOutputStream(f);
     for (ICombinatoricsVector perm : gen) {
     if (Math.random() < 0.3) {   
     // restrict the training set size

String match = determineMatch(perm.getVector()); // first highest count wins

    String features = StringUtils.join(perm.getVector(), ",");
    IOUtils.write(String.format("%s,%s\n", features, match), stream);

        }
       }
       stream.close();
   }
}

Clasa TrainingDataCreator folosește permutări pentru a genera toate rândurile de antrenament cu numărul maxim de apariții 4 (numărul de apariții al fiecărui cuvânt variază de la 0 la 4). Deoarece dorim ca acesta să fie un set de date de antrenament real, vom folosi doar 30% din permutări. De asemenea, dorim ca algoritmul de clasificare să poată extrage o logică de atribuire a categoriilor din aceste date, astfel că vom asigna pentru fiecare rând generat de date prima categorie cu cel mai mare număr de apariții (ex. Pentru vectorul de cuvinte tată=2, felicitări=3, reducere=0, alertă=1, grup=3; felicitări este primul cuvânt cu numărul cel mai mare de apariții, 3).

Fișierul generat va conține linii precum:

3,1,1,0,0,1
4,1,1,0,0,1
3,3,2,4,1,4

Acum că am generat datele de antrenament, trebuie să antrenăm clasificatorul. Începem prin a crea setul de date de antrenament.

// Create an empty training set and set the class (category) index

Instances trainingSet = new Instances("Training", rowDefinition, TRAINING_SET_SIZE);

trainingSet.setClassIndex(5);
addInstances(rowDefinition, trainingSet, "category-training-data.csv");

În interiorul metodei addInstances vom citi fișierul CSV și vom crea un obiect de tip Instance pentru fiecare rând din fișierul CSV, care va reprezenta o atribuire de categorie unui e-mail.

// Create the instance
Instance trainingRow = new Instance(6);
trainingRow.setValue((Attribute) rowDefinition.elementAt(0), Integer.valueOf(values[0]));
trainingRow.setValue((Attribute) rowDefinition.elementAt(1), Integer.valueOf(values[1]));

trainingRow.setValue((Attribute) rowDefinition.elementAt(2), Integer.valueOf(values[2]));

trainingRow.setValue((Attribute) rowDefinition.elementAt(3), Integer.valueOf(values[3]));

trainingRow.setValue((Attribute) rowDefinition.elementAt(4), Integer.valueOf(values[4]));

trainingRow.setValue((Attribute) rowDefinition.elementAt(5), values[5]);

// add the instance
trainingSet.add(trainingRow);

Următorul pas este construcția clasificatorului utilizând setul generat de date.

// Create a naïve bayes classifier
Classifier cModel = new NaiveBayes();
cModel.buildClassifier(trainingSet);

Pentru a testa algoritmul nostru de clasificare, să zicem că am primit un e-mail care conține cuvântul tată de 5 ori, iar restul cuvintelor cheie au 0 apariții. (Observăm faptul că setul de date de antrenament conține numărul maxim de apariții 4, obligând clasificatorul să extrapoleze pentru a determina categoria corectă, și anume, 1 - Principal)

// Create the test instance
Instance incomingEmail = new Instance(6);
incomingEmail.setValue((Attribute) rowDefinition.elementAt(0), 5);
incomingEmail.setValue((Attribute) rowDefinition.elementAt(1), 0);
incomingEmail.setValue((Attribute) rowDefinition.elementAt(2), 0);

incomingEmail.setValue((Attribute) rowDefinition.elementAt(3), 0);

incomingEmail.setValue((Attribute) rowDefinition.elementAt(4), 0);
incomingEmail.setDataset(trainingSet);    
  // inherits format rules
double prediction = cModel.classifyInstance(incomingEmail);
System.out.println(trainingSet.classAttribute().value((int) prediction));

Codul de mai sus va afișa 1, adică categoria Principal. Câteva exemple de date de test sunt prezente în tabelul de mai jos:

După cum putem vedea, acuratețea de predicție nu este niciodata 100%, dar prin ajustarea parametrilor algoritmilor și selecția atentă a atributelor din vectorul de date, precum și datele de antrenament, se poate obține o rată mare de corectitudine.

Weka oferă API-uri pentru a evalua soluțiile implementate. Prin crearea a două seturi de date, setul de date inițial conținând 30% din permutări și un al 2-lea set conținând toate permutările pentru numărul de apariții maxim 4; și utilizarea clasei Evaluation obținem o rată de corectitudine de 95%.

// Test the model
Evaluation eTest = new Evaluation(trainingSet);
eTest.evaluateModel(cModel, testSet);
System.out.println(eTest.pctCorrect());

Concluzie

Codul de mai sus a fost scris folosind Weka deoarece am considerat că API-urile expuse sunt mai ușor de folosit și de înțeles comparativ cu o altă librărie comună de machine learning, Apache Mahout. Dacă aveți un scenariu care acceptă o rată de acuratețe mai mică de 100% și există posibilitatea construcției de date de antrenament, avantajele pot depăși costurile. În ceea ce privește performanța, am rulat teste care indică faptul că prin alegerea celui mai performant algoritm pentru setul de date, se pot obține timpi de antrenament de sub o secundă pentru 28000 de rânduri de antrenament (5 atribute + categorie) și timpi similari de predicție pentru 1000 de rânduri de date.

Machine Learning are un mare potențial pentru a fi utilizat în toate domeniile software (chiar și aplicații mobile), și după cum am văzut în exemplul de mai sus, nu trebuie să fii un matematician pentru a folosi uneltele existente. Să înceapă învățarea!

Bibliografie

http://architects.dzone.com/articles/machine-learning-measuring

http://en.wikipedia.org/wiki/Bag-of-words_model

http://www.cs.waikato.ac.nz/ml/weka/

https://github.com/rjmarsan/Weka-for-Android

https://github.com/fgarcialainez/ML4iOS

Introduction to Machine Learning, by Alex Smola, S.V.N. Vishwanathan

Mahout in Action, by Sean Owen, Robin Anil, Ted Dunning, Ellen Friedman