Note de curs, clasele 11-12, 29 martie 2013: Difference between revisions

From Algopedia
Jump to navigationJump to search
No edit summary
 
(No difference)

Latest revision as of 15:56, 29 March 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:

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

sau, echivalent, să minizăm expresia

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,

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,

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

Î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.

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.