====== Bayes Naiv ====== De-a lungul secțiunilor anterioare, am învățat despre teoria probabilității și variabilelor aleatoare. Pentru a pune această teorie la treabă, să introducem clasificatorul //Bayes naiv//. Acesta nu folosește nimic altceva decât fundamente probabilistice pentru a ne permite să efectuăm clasificarea cifrelor. Învățarea este despre a face presupuneri. Dacă vrem să clasificăm un nou exemplu de date pe care nu l-am mai văzut niciodată înainte trebuie să facem unele presupuneri despre ce exemple de date sunt similare între ele. Clasificatorul Bayes naiv, un algoritm popular și remarcabil de clar, presupune că toate caracteristicile sunt independente unele de altele pentru a simplifica calculul. În această secțiune, vom aplica acest model pentru a recunoaște caractere în imagini. #@tab pytorch %matplotlib inline from d2l import torch as d2l import math import torch import torchvision d2l.use_svg_display() ===== Recunoașterea Optică a Caracterelor ===== MNIST ((LeCun.Bottou.Bengio.ea.1998)) este unul dintre seturile de date utilizate pe scară largă. Conține 60.000 de imagini pentru antrenare și 10.000 de imagini pentru validare. Fiecare imagine conține o cifră scrisă de mână de la 0 la 9. Sarcina este clasificarea fiecărei imagini în cifra corespunzătoare. Gluon oferă o clasă ''%%MNIST%%'' în modulul ''%%data.vision%%'' pentru a prelua automat setul de date de pe Internet. Ulterior, Gluon va folosi copia locală deja descărcată. Specificăm dacă solicităm setul de antrenare sau setul de testare setând valoarea parametrului ''%%train%%'' la ''%%True%%'' sau ''%%False%%'', respectiv. Fiecare imagine este o imagine în tonuri de gri cu lățimea și înălțimea de $28$ cu forma ($28$,$28$,$1$). Folosim o transformare personalizată pentru a elimina ultima dimensiune a canalului. În plus, setul de date reprezintă fiecare pixel printr-un întreg fără semn pe $8$-biți. Îi cuantificăm în caracteristici binare pentru a simplifica problema. #@tab pytorch data_transform = torchvision.transforms.Compose([ torchvision.transforms.ToTensor(), lambda x: torch.floor(x * 255 / 128).squeeze(dim=0) ]) mnist_train = torchvision.datasets.MNIST( root='./temp', train=True, transform=data_transform, download=True) mnist_test = torchvision.datasets.MNIST( root='./temp', train=False, transform=data_transform, download=True) Putem accesa un anumit exemplu, care conține imaginea și eticheta corespunzătoare. #@tab pytorch image, label = mnist_train[2] image.shape, label Exemplul nostru, stocat aici în variabila ''%%image%%'', corespunde unei imagini cu o înălțime și lățime de $28$ pixeli. #@tab all image.shape, image.dtype Codul nostru stochează eticheta fiecărei imagini ca un scalar. Tipul său este un întreg pe $32$-biți. #@tab pytorch label, type(label) Putem accesa de asemenea mai multe exemple în același timp. #@tab pytorch images = torch.stack([mnist_train[i][0] for i in range(10, 38)], dim=0) labels = torch.tensor([mnist_train[i][1] for i in range(10, 38)]) images.shape, labels.shape Să vizualizăm aceste exemple. #@tab all d2l.show_images(images, 2, 9); ===== Modelul Probabilistic pentru Clasificare ===== Într-o sarcină de clasificare, mapăm un exemplu într-o categorie. Aici un exemplu este o imagine în tonuri de gri $28\times 28$, și o categorie este o cifră. (Consultați pentru o explicație mai detaliată.) O modalitate naturală de a exprima sarcina de clasificare este prin întrebarea probabilistică: care este cea mai probabilă etichetă date fiind caracteristicile (i.e., pixelii imaginii)? Notați prin $\mathbf x\in\mathbb R^d$ caracteristicile exemplului și $y\in\mathbb R$ eticheta. Aici caracteristicile sunt pixeli de imagine, unde putem remodela o imagine $2$-dimensională într-un vector astfel încât $d=28^2=784$, iar etichetele sunt cifre. Probabilitatea etichetei date fiind caracteristicile este $p(y \mid \mathbf{x})$. Dacă suntem capabili să calculăm aceste probabilități, care sunt $p(y \mid \mathbf{x})$ pentru $y=0, \ldots,9$ în exemplul nostru, atunci clasificatorul va returna predicția $\hat{y}$ dată de expresia: $$\hat{y} = \mathrm{argmax} \> p(y \mid \mathbf{x}).$$ Din păcate, acest lucru necesită să estimăm $p(y \mid \mathbf{x})$ pentru fiecare valoare a lui $\mathbf{x} = x_1, ..., x_d$. Imaginați-vă că fiecare caracteristică ar putea lua una din $2$ valori. De exemplu, caracteristica $x_1 = 1$ ar putea semnifica faptul că cuvântul măr apare într-un document dat și $x_1 = 0$ ar semnifica faptul că nu apare. Dacă am avea $30$ de astfel de caracteristici binare, asta ar însemna că trebuie să fim pregătiți să clasificăm oricare din $2^{30}$ (peste 1 miliard!) valori posibile ale vectorului de intrare $\mathbf{x}$. Mai mult, unde este învățarea? Dacă trebuie să vedem fiecare exemplu posibil pentru a prezice eticheta corespunzătoare atunci nu învățăm cu adevărat un model ci doar memorăm setul de date. ===== Clasificatorul Bayes Naiv ===== Din fericire, făcând unele presupuneri despre independența condiționată, putem introduce o prejudecată inductivă (inductive bias) și construi un model capabil să generalizeze dintr-o selecție comparativ modestă de exemple de antrenare. Pentru a începe, să folosim teorema lui Bayes, pentru a exprima clasificatorul ca $$\hat{y} = \mathrm{argmax}_y \> p(y \mid \mathbf{x}) = \mathrm{argmax}_y \> \frac{p( \mathbf{x} \mid y) p(y)}{p(\mathbf{x})}.$$ Rețineți că numitorul este termenul de normalizare $p(\mathbf{x})$ care nu depinde de valoarea etichetei $y$. Ca rezultat, trebuie să ne facem griji doar despre compararea numărătorului peste diferite valori ale lui $y$. Chiar dacă calcularea numitorului s-ar dovedi a fi intractabilă, am putea scăpa ignorându-l, atât timp cât am putea evalua numărătorul. Din fericire, chiar dacă am dori să recuperăm constanta de normalizare, am putea. Putem oricând recupera termenul de normalizare deoarece $\sum_y p(y \mid \mathbf{x}) = 1$. Acum, să ne concentrăm pe $p( \mathbf{x} \mid y)$. Folosind regula lanțului a probabilității, putem exprima termenul $p( \mathbf{x} \mid y)$ ca $$p(x_1 \mid y) \cdot p(x_2 \mid x_1, y) \cdot ... \cdot p( x_d \mid x_1, ..., x_{d-1}, y).$$ De sine stătător, această expresie nu ne duce mai departe. Încă trebuie să estimăm aproximativ $2^d$ parametri. Totuși, dacă presupunem că //caracteristicile sunt condiționat independente una de alta, dată fiind eticheta//, atunci dintr-o dată suntem într-o formă mult mai bună, deoarece acest termen se simplifică la $\prod_i p(x_i \mid y)$, dându-ne predictorul $$\hat{y} = \mathrm{argmax}_y \> \prod_{i=1}^d p(x_i \mid y) p(y).$$ Dacă putem estima $p(x_i=1 \mid y)$ pentru fiecare $i$ și $y$, și să salvăm valoarea sa în $P_{xy}[i, y]$, aici $P_{xy}$ este o matrice $d\times n$ cu $n$ fiind numărul de clase și $y\in\{1, \ldots, n\}$, atunci putem folosi asta de asemenea pentru a estima $p(x_i = 0 \mid y)$, i.e., $$ p(x_i = t_i \mid y) = \begin{cases} P_{xy}[i, y] & \textrm{pentru } t_i=1 ;\\ 1 - P_{xy}[i, y] & \textrm{pentru } t_i = 0 . \end{cases} $$ În plus, estimăm $p(y)$ pentru fiecare $y$ și îl salvăm în $P_y[y]$, cu $P_y$ un vector de lungime $n$. Atunci, pentru orice nou exemplu $\mathbf t = (t_1, t_2, \ldots, t_d)$, am putea calcula $$\begin{aligned}\hat{y} &= \mathrm{argmax}_ y \ p(y)\prod_{i=1}^d p(x_t = t_i \mid y) \\ &= \mathrm{argmax}_y \ P_y[y]\prod_{i=1}^d \ P_{xy}[i, y]^{t_i}\, \left(1 - P_{xy}[i, y]\right)^{1-t_i}\end{aligned}$$ pentru orice $y$. Astfel presupunerea noastră de independență condiționată a dus complexitatea modelului nostru de la o dependență exponențială de numărul de caracteristici $\mathcal{O}(2^dn)$ la o dependență liniară, care este $\mathcal{O}(dn)$. ===== Antrenare ===== Problema acum este că nu cunoaștem $P_{xy}$ și $P_y$. Deci trebuie să estimăm valorile lor date fiind niște date de antrenare mai întâi. Aceasta este //antrenarea// modelului. Estimarea $P_y$ nu este prea grea. Deoarece avem de-a face doar cu $10$ clase, putem număra numărul de apariții $n_y$ pentru fiecare dintre cifre și să-l împărțim la cantitatea totală de date $n$. De exemplu, dacă cifra 8 apare $n_8 = 5,800$ ori și avem un total de $n = 60,000$ imagini, estimarea probabilității este $p(y=8) = 0.0967$. #@tab pytorch X = torch.stack([mnist_train[i][0] for i in range(len(mnist_train))], dim=0) Y = torch.tensor([mnist_train[i][1] for i in range(len(mnist_train))]) n_y = torch.zeros(10) for y in range(10): n_y[y] = (Y == y).sum() P_y = n_y / n_y.sum() P_y Acum la lucruri puțin mai dificile $P_{xy}$. Deoarece am ales imagini alb-negru, $p(x_i \mid y)$ denotă probabilitatea ca pixelul $i$ să fie pornit pentru clasa $y$. Exact ca înainte putem merge și număra numărul de ori $n_{iy}$ astfel încât un eveniment să aibă loc și să-l împărțim la numărul total de apariții ale lui $y$, i.e., $n_y$. Dar există ceva ușor tulburător: anumiți pixeli s-ar putea să nu fie niciodată negri (e.g., pentru imagini bine decupate pixelii din colț ar putea fi întotdeauna albi). O modalitate convenabilă pentru statisticieni de a se ocupa de această problemă este să adauge pseudo numărători la toate aparițiile. Prin urmare, mai degrabă decât $n_{iy}$ folosim $n_{iy}+1$ și în loc de $n_y$ folosim $n_{y}+2$ (deoarece există două valori posibile pe care pixelul $i$ le poate lua - poate fi fie negru fie alb). Aceasta este numită de asemenea //Netezire Laplace//. Poate părea ad-hoc, totuși poate fi motivată dintr-un punct de vedere Bayesian printr-un model Beta-binomial. #@tab pytorch n_x = torch.zeros((10, 28, 28)) for y in range(10): n_x[y] = torch.tensor(X.numpy()[Y.numpy() == y].sum(axis=0)) P_xy = (n_x + 1) / (n_y + 2).reshape(10, 1, 1) d2l.show_images(P_xy, 2, 5); Vizualizând aceste probabilități de $10\times 28\times 28$ (pentru fiecare pixel pentru fiecare clasă) am putea obține niște cifre cu aspect mediu. Acum putem folosi :eqref:''%%eq_naive_bayes_estimation%%'' pentru a prezice o nouă imagine. Dat fiind $\mathbf x$, următoarele funcții calculează $p(\mathbf x \mid y)p(y)$ pentru fiecare $y$. #@tab pytorch def bayes_pred(x): x = x.unsqueeze(0) # (28, 28) -> (1, 28, 28) p_xy = P_xy * x + (1 - P_xy)*(1 - x) p_xy = p_xy.reshape(10, -1).prod(dim=1) # p(x|y) return p_xy * P_y image, label = mnist_test[0] bayes_pred(image) Acest lucru a mers oribil de prost! Pentru a afla de ce, să ne uităm la probabilitățile per pixel. Ele sunt tipic numere între $0.001$ și $1$. Înmulțim $784$ dintre ele. În acest punct merită menționat că noi calculăm aceste numere pe un computer, prin urmare cu un interval fix pentru exponent. Ceea ce se întâmplă este că experimentăm //underflow numeric//, i.e., înmulțirea tuturor numerelor mici duce la ceva și mai mic până când este rotunjit în jos la zero. Am discutat acest lucru ca o problemă teoretică în , dar vedem fenomenul clar aici în practică. Așa cum s-a discutat în acea secțiune, reparăm asta folosind faptul că $\log a b = \log a + \log b$, i.e., trecem la sumarea logaritmilor. Chiar dacă atât $a$ cât și $b$ sunt numere mici, valorile logaritmice ar trebui să fie într-un interval corespunzător. #@tab pytorch a = 0.1 print('underflow:', a**784) print('logarithm is normal:', 784*math.log(a)) Deoarece logaritmul este o funcție crescătoare, putem rescrie :eqref:''%%eq_naive_bayes_estimation%%'' ca $$ \hat{y} = \mathrm{argmax}_y \ \log P_y[y] + \sum_{i=1}^d \Big[t_i\log P_{xy}[x_i, y] + (1-t_i) \log (1 - P_{xy}[x_i, y]) \Big].$$ Putem implementa următoarea versiune stabilă: #@tab pytorch log_P_xy = torch.log(P_xy) log_P_xy_neg = torch.log(1 - P_xy) log_P_y = torch.log(P_y) def bayes_pred_stable(x): x = x.unsqueeze(0) # (28, 28) -> (1, 28, 28) p_xy = log_P_xy * x + log_P_xy_neg * (1 - x) p_xy = p_xy.reshape(10, -1).sum(axis=1) # p(x|y) return p_xy + log_P_y py = bayes_pred_stable(image) py Putem verifica acum dacă predicția este corectă. #@tab pytorch py.argmax(dim=0) == label Dacă prezicem acum câteva exemple de validare, putem vedea că clasificatorul Bayes funcționează destul de bine. #@tab pytorch def predict(X): return [bayes_pred_stable(x).argmax(dim=0).type(torch.int32).item() for x in X] X = torch.stack([mnist_test[i][0] for i in range(18)], dim=0) y = torch.tensor([mnist_test[i][1] for i in range(18)]) preds = predict(X) d2l.show_images(X, 2, 9, titles=[str(d) for d in preds]); În sfârșit, să calculăm acuratețea generală a clasificatorului. #@tab pytorch X = torch.stack([mnist_test[i][0] for i in range(len(mnist_test))], dim=0) y = torch.tensor([mnist_test[i][1] for i in range(len(mnist_test))]) preds = torch.tensor(predict(X), dtype=torch.int32) float((preds == y).sum()) / len(y) # Validation accuracy Rețelele profunde moderne ating rate de eroare de mai puțin de $0.01$. Performanța relativ slabă se datorează presupunerilor statistice incorecte pe care le-am făcut în modelul nostru: am presupus că fiecare pixel este generat //independent//, depinzând doar de etichetă. Acest lucru nu este clar cum scriu oamenii cifrele, și această presupunere greșită a dus la căderea clasificatorului nostru excesiv de naiv (Bayes). ===== Rezumat ===== * Folosind regula lui Bayes, un clasificator poate fi făcut presupunând că toate caracteristicile observate sunt independente. * Acest clasificator poate fi antrenat pe un set de date numărând numărul de apariții ale combinațiilor de etichete și valori ale pixelilor. * Acest clasificator a fost standardul de aur timp de decenii pentru sarcini precum detectarea spam-ului. ===== Exerciții ===== - Considerați setul de date $[[0,0], [0,1], [1,0], [1,1]]$ cu etichete date de XOR-ul celor două elemente $[0,1,1,0]$. Care sunt probabilitățile pentru un clasificator Naive Bayes construit pe acest set de date. Clasifică cu succes punctele noastre? Dacă nu, ce presupuneri sunt încălcate? - Să presupunem că nu am folosit netezirea Laplace când am estimat probabilitățile și un exemplu de date a sosit la momentul testării care conținea o valoare neobservată niciodată în antrenare. Ce ar afișa modelul? - Clasificatorul Bayes naiv este un exemplu specific de rețea Bayesiană, unde dependența variabilelor aleatoare este codificată cu o structură graf. Deși teoria completă este dincolo de scopul acestei secțiuni (vedeți ((Koller.Friedman.2009)) pentru detalii complete), explicați de ce permiterea dependenței explicite între cele două variabile de intrare în modelul XOR permite crearea unui clasificator de succes. [[https://discuss.d2l.ai/t/1100|Discuții]]