Note de curs, clasele 11-12, 29 martie 2013

Recapitulare

• probabilități condiționate
• evenimente independente
• legea probabilității totale
• teorema lui Bayes

Clasificare bayesiană

Generalități

Clasificarea bayesiană face parte dintr-o problemă mai generală, pattern recognition, împreună cu:

• învățarea supervizată (clasificare învățată pe baza unui set de antrenament)
• învățarea nesupervizată (clustering -- partiționarea în grupuri apropiate)
  • exemple: gruparea speciilor de vietăți, a comunităților online
• regresie: găsirea unei curbe dându-se punctele (liniară, pătratică etc.)
• sequence labeling (categorisirea unei secvențe de elemente)
  • discuție despre PoS tagging; exemplu: time flies like an arrow
• parsing; exemplu: l-am văzut pe Ion pe deal cu telescopul

Ideea centrală a clasificării este antrenarea unui clasificator pe un set de date. Aplicații:

• filtrare de spam
• recunoașterea vorbirii (speech to text)
• recunoașterea scrisului (OCR)
• calculul poliței de asigurare
  • discuție despre mașini roșii: nu mașina roșie reprezintă un pericol, ci tipul de șofer care o conduce
• diagnosticarea unui pacient
  • discuție despre diagnostice greșite în cazul Parkinson
• Google Sets (încă în viață în ca Easter egg în Google Spreadsheet)

Clasificatoarele pot fi multi-clasă sau binare. Cele binare sunt mult mai studiate.

Clasificatoarele pot fi deterministe sau probabilistice:

• asignează probabilități tuturor claselor posibile
• aleg o clasă, dar precizează un grad de încredere în alegerea făcută
• se abțin când nu se pot decide

Clasificarea bayesiană examinează un vector de trăsături și alege clasa vectorului.

Clasificare liniară

Clasificarea liniară pornește de la un set de antrenament constând din n vectori a căror clasă este cunoscută (specii de animale, puncte albe și negre în plan etc.). Trebuie să determine o dreaptă de ecuație ax + by + c = 0 (sau, pe cazul general, un plan sau un hiperplan) care să trieze cât mai bine cele două clase.

Odată ce găsim a, b și c, un punct (x, y) trebuie clasificat astfel încât

• punctele mult în stânga dreptei să aibă probabilitate tinzând spre 0
• punctele mult în dreapta dreptei să aibă probabilitate tinzând spre 1
• punctele din apropierea dreptei să aibă probabilitate apropiată de 0,5

O astfel de funcție este:

$P((x,y)\to +1)=\frac{1}{1+e^{-(ax+by+c)}}$

Trebuie să găsim a, b și c care clasifică cât mai bine punctele date. Deci punctul (x_i, y_i), despre care știm că are semnul s_i (+1 sau -1), trebuie clasificat cu încredere cât mai mare. Dorim deci să maximizăm expresia

$\prod _{i=1}^{n}P((x_i,y_i)\to s_i)=\prod _{i=1}^n\frac{1}{1+e^{s_i(a{x}_i+b{y}_i+c)}}$

sau, echivalent, să minizăm expresia

$\sum _{i=1}^n\log (1+e^{s_i(a{x}_i+b{y}_i+c)})$

Găsirea lui a, b, și c se face cu un proces iterativ (cu gradienți).

Clasificare bayesiană naivă

Clasificarea naivă presupune că trăsăturile apar independent. Astfel,

$P(S|F_1,F_2,...F_n)=\frac{P(S)P(F_1,F_2,...F_n|S)}{P(F_1,F_2,...,F_n)}$

Numitorul se calculează apriori, trecând prin setul de date de antrenament și observând frecvența celor n trăsături. În privința numărătorului,

$P(F_1,F_2,...F_n|S)=P(F_1|S)P(F_2,...F_n|S,F_1)=...=P(F_1|S)...P(F_i,F_{i+1},...F_n|S,F_1,F_2,...,F_{i-1})...$

Aici presupunem că P(F_i | F_j) = P(F_i). Această presupunere se comportă bine în practică și simplifică mult modelul de calcul:

$P(F_1,F_2,...F_n|S)=P(F_1|S)P(F_2|S)...P(F_n|S)$

În plus, putem calcula „coeficientul de spam” pentru un cuvânt. Pentru simplitate, facem presupunerea că P(Spam) = P(Ham) = 50%. Aceasta este o presupunere conservatoare, căci statisticile arată că circa 80% din mesajele care circulă astăzi sunt spam.

$P(S|W)=\frac{P(W|S)}{P(W|S)+P(W|H)}$

Calculăm acest coeficient pentru fiecare cuvânt din mesaj, apoi decidem scorul total, luând în considerare și alți factori (headere etc.).

Compresie

Generalități

• nu merge pe orice fișier, ci pe clasele particulare pe care se întâmplă să le folosim noi
• un fișier random nu poate fi comprimat cu niciun compresor
• explicația intuitivă: funcția care mapează fișiere decomprimate la fișiere comprimate este bijectivă
• tehnicile de compresie sunt compromisuri între
  • viteza de comprimare
  • viteza de decomprimare
  • rata de compresie
  • memoria necesară
• NOU accesul aleator în fișiere comprimate este un bonus util (altfel este nevoie să decomprim tot fișierul ca să pot citi un octet)

RLE

• aplicații: fax, formate grafice
• explicația algoritmului (foarte pe scurt)
• variante: pe biți / bytes
• direcții: pe linii, pe coloane, pe mici suprafețe de 4x4 pixeli
• ca să nu codăm serii de un singur octet, folosim un steguleț: 255 5 4 înseamnă „vezi că urmează 5 caractere de 4”
• stegulețul însuși trebuie codat, căci altfel va introduce o ambiguitate
• contorul frecvenței are o limită superioară (256, de exemplu)
• divagație despre COPY86M, RLE în timp real, folosirea memoriei grafice ca spațiu de stocare

Huffman static

• frecvențele caracterelor
• definiția costului unui cod
• exemplu de comprimare și decomprimare
  • rezultă că este necesar să stocăm arborele
• un cod de lungime variabilă poate obține un cost total mai mic decât codul de lungime fixă
• codul trebuie să fie fără prefixe (niciun cod nu poate fi prefixul altui cod, căci apar ambiguități)
• soluție: arbore binar unde simbolurile stau în frunze
• arborele este binar strict
• algoritmul Huffman (de tip greedy), exemplu
  • rezultă că este nevoie de două parcurgeri, din care prima este pentru a calcula frecvențele
• implementare:
  • „naiv” cu un heap: O(n log n)
  • cu două cozi: O(n) -- Mihai Andreescu
  • cu o listă sortată, în care mențin pointerul ultimei inserări: O(n) -- Paul Gramatovici
• stocarea arborelui: (2n - 1) + (n log n) biți
  • parcurgere de arbore, emit 0 pentru noduri interne și 1 pentru frunze
• arborele Huffman canonic
  • permite stocarea arborelui în numai n log n biți (256 de octeți pentru cazul ASCII)
• demonstrație de optimalitate a algoritmului Huffman:
  • alegerea de a combina cele mai infrecvente două noduri este bună (există un arbore optim cu această structură)
  • dacă înlocuiesc nodurile x și y printr-un nou z și obțin un arbore optim pentru noul alfabet, pot să sparg nodul z ca să obțin un arbore optim pentru alfabetul inițial.

Va urma: Shannon-Fano, Huffman adaptiv, LZ77, posibil FFT.