Blog divulgativo sulla matematica applicata

Machine Learning: i postini e gli algoritmi di classificazione.

Probabilmente a scuola vi sarà capitato di sentir dire: "Devi scrivere meglio! Cerca di avere una grafia migliore! non si capisce nulla!''.

La a che somiglia alla o e, perché no, alla c o ad una g uscita male; un 7 che si confonde con un 1 o con uno sbaffo della penna, insomma, chi più ne ha più ne metta.

handwritten_digits

Pensate alla povera maestra che deve decifrare i temi di italiano o gli esercizi di matematica di queste giovani marmotte, rischierebbe di impazzire!

Fortunatamente impara pian piano a capire ogni singolo simbolo di ogni bambino, arrivando persino a pensare che gli alunni non abbiano poi una grafia così malvagia.

Questo piccolo problema "di classe" ci attanaglia ogni giorno anche fuori dagli ambienti scolastici, pensate cosa succede quando inviate una lettera.

Problemi con il codice postale?

Immaginiamo di voler inviare una lettera via posta, il codice di avviamento postale è l'elemento chiave per far sì che il nostro messaggio arrivi a destinazione.
Se la tecnologia fosse ferma all'occhio dell'operatore che smista le lettere in base alla destinazione, probabilmente il nostro messaggio non arriverebbe mai in tempo, e dovremmo sempre aggrapparci alla speranza che il postino comprenda la nostra grafia.

Per fortuna la matematica, quella che gli alunni di prima spesso odiano, viene in nostro soccorso.
In realtà per questo post non dobbiamo ringraziare soltanto lei, ma tante altre discipline come l'informatica, la statistica, la neurobiologia, la teoria dell'informazione ecc. che fondendosi e prendendo idee le une dalle altre "danno vita" al Machine Learning.

Piacere, Machine Learning.

Con Machine Learning, o Apprendimento Automatico, si indica generalmente l'insieme delle teorie e algoritmi che permettono ai dispositivi artificiali di emulare la mente umana, rendendoli di fatto capaci di imparare, scegliere e decidere.

La differenza sostanziale tra il nostro cervello e quello di una macchina è l'incapacità di quest'ultimo di seguire un ragionamento induttivo, ossia di dedurre delle regole partendo da esempi, limitandosi soltanto a quello deduttivo, cioè dedurre gli esempi dalle regole inserite a priori.

ind_ded

In sostanza una macchina non riesce ad imparare dall'esperienza come noi umani, anzi, dopo qualche anno è da buttare!

Citando Tom M. Mitchell:

 "un programma apprende da una certa esperienza E se: nel rispetto di un compito T, con una misura di prestazione P, la prestazione P misurata nello svolgere il compito T è migliorata dall'esperienza E."

Ok, stiamo divagando troppo, torniamo in carreggiata!
Per aiutare gli amici postini o le care maestre introduciamo il problema della classificazione.
Vogliamo fare in modo che il nostro computer, dopo avergli fatto vedere un po' di esempi, sappia leggere nuove cifre scritte a mano. Sporchiamoci un po' le mani!

Problemi di classificazione.

Quella che i nostri occhi vedono come una immagine, per un cervello artificiale non è altro che una griglia di pixel o, più matematicamente, una matrice le cui entrate rappresentano lo stato del pixel corrispondente.

Image_grid

Anche se nella realtà si utilizzano le scale RGB, CMYK, ed altre, per semplicità ipotizziamo di trattare immagini in bianco e nero senza toni di grigio, ogni pixel può essere quindi acceso/bianco o spento/nero (stati corrispondenti rispettivamente ai valori 1 e 0).
Diamo in input al nostro cervello artificiale un insieme, detto training set, di m coppie di esempi (x^{(i)},y^{(i)}): x^{(i)} denota un'immagine (una matrice) e y^{(i)}\in\left\{0,\dots,n\right\} il simbolo rappresentato nell'immagine.
Sottolineamo che in generale i valori del codominio delle y^{(i)} sono soltanto delle etichette per denominare le classi output che possono essere anche di natura non numerica.

Il programma dovrà dunque guardare una nuova matrice di pixel e riconoscere che numero rappresenti.

Un po' di simboli e definizioni.

Per capire qualcosa in più vi presento la funzione sigmoidea,
\begin{equation*}\sigma(x):=\frac 1{1+e^{-x}},\; x\in \mathbb{R},\end{equation*}
di seguito il suo aspetto e qui vi ci potete divertire un po'.

sigmoid3

Supponiamo che le nostre immagini siano piccole e a bassa definizione, ad esempio dei quadrati con 20 pixel per lato.

Lavorare con queste matrici è un po' scomodo, quindi le trasformiamo in vettori mettendo una dopo l'altra le righe, o le colonne, e per questioni tecniche aggiungiamo una componente uguale ad 1 prima di tutte le altre: otteniamo vettori con l=20\times 20+1=401 componenti.

Classificazione binaria.

Riduciamo inizialmente il problema ad una classificazione binaria, il programma deve classificare i nuovi input in due sole categorie, denotate, ad esempio, con le etichette 0 e 1 (gli output saranno y\in\left\{0,1\right\}). Estendere queste idee alla classificazione multipla non è difficile come vedremo tra poco.
Un concetto fondamentale è la funzione ipotesi 

\begin{equation*}h_\theta(x)=P(y=1|x;\theta),\end{equation*}

che rappresenta intuitivamente la probabilità che un nuovo input x produca un output y=1.
Essendo appunto una funzione di probabilità, questa deve essere compresa tra 0 e 1.

E quindi? Ancora un po' di pazienza!

Introduciamo la chiave di tutto il modello, ossia un vettore di parametri \theta=\left(\theta_0,\dots,\theta_l\right) che il programma deve autonomamente calcolare a partire dagli esempi e seguendo una certa logica.
Ricordiamoci la definizione di prodotto scalare \theta \cdot x=\sum_{j=0}^l \theta_jx_j, mischiamolo con la sigmoide e definiamo finalmente

\begin{align*}h_\theta(x)=\sigma(\theta \cdot x)=\frac 1{1+e^{-\theta \cdot x}},\end{align*}

diremo che

\begin{align*}
y =\begin{cases}
1 \; & \text{se } h_\theta(x)\ge0,5 \\
0 \; & \text{se } h_\theta(x)<0,5.
\end{cases}\end{align*}

Sì ok, ma ora che ci facciamo? Resistete un po' e avrete la risposta!
Ricapitolando un attimo, abbiamo

  • un training set con m osservazioni \left\{(x^{(i)},y^{(i)}) ,\dots,(x^{(m)},y^{(m)})\right\}, in cui ogni coppia è composta da vettori x^{(i)}=\left(x^{(i)}_0,x^{(i)}_1,\dots,x^{(i)}_l\right)\in\mathbb{R}^{l+1}, e dagli output associati y^{(i)}\in\left\{0,1\right\};
  • una fantomatica funzione h_\theta.

Funzione Costo.

Il problema principale è  diventato quello di scegliere i parametri \theta_i che minimizzino l'errore delle predizioni di h_\theta sulle coppie del training set, in modo da avere le migliori ipotesi possibili su nuovi input.
La parola "minimo" ai lettori più matematici avrà già suscitato una certa idea: introduciamo infatti una funzione costo J nelle variabili \theta_0,...,\theta_l, il cui minimo fornisce i parametri desiderati:

J(\theta):=\frac 1m \sum_{i=1}^m \mbox{Cost}(h_\theta(x^{(i)}),y^{(i)}) con:

\begin{align*}
Cost (h_\theta(x),y) =\begin{cases}
-\log(h_\theta(x)) \; & \text{se } y = 1 \\
-\log(1-h_\theta(x)) \; & \text{se } y = 0.
\end{cases}\end{align*}

Questa definizione cattura l'intuizione che se il nostro output è y=0 e la funzione ipotesi h_\theta tende correttamente a zero, l'errore tende a zero; se invece la funzione ipotesi tende a uno, il costo cresce penalizzando l'algoritmo. Analogo a parti invertite il caso y=1.

Possiamo quindi riscrivere la funzione costo in maniera compressa:

J(\theta)=-\frac{1}{m}\sum_{i=1}^m[y^{(i)}\log(h_\theta(x^{(i)})+(1-y^{(i)})\log(1-h_\theta(x^{(i)}))]

Alleniamo i parametri.

Calcolare questo minimo analiticamente può essere troppo laborioso, arriviamoci quindi passo dopo passo, come se dovessimo raggiungere una vallata tra due montagne: tra gli algoritmi più conosciuti e semplici che vanno in questa direzione citiamo il gradient descent:

Repeat\lbrace\\ \theta_j \leftarrow\theta_j - \alpha \dfrac{\partial}{\partial \theta_j}J(\theta) \mbox{ per ogni } j=0,\dots,l\\ \rbrace

con il simbolo "\leftarrow'' intendiamo l'operatore di assegnamento mentre \alpha è una costante, detta tasso d'apprendimento, scelta in base alle esigenze specifiche del caso. Se \alpha è troppo piccola la convergenza dell'algoritmo rischia di essere eccessivamente lenta, d'altro canto, se \alpha è troppo grande, l'algoritmo rischia di divergere saltando completamente il punto di minimo.

In realtà ce ne sono anche altri più veloci e sofisticati ma meno intuitivi, come ad esempio il "Gradiente Coniugato'', il "BFGS" o il "L-BFGS".

Perché funziona questo algoritmo?

Per capirlo, intuitivamente, pensiamo ad una semplice parabola sul piano.
Mettiamoci su un punto a caso della parabola (che non sia il minimo, non barate!) e calcoliamo la derivata in quel punto, se è positiva, cioè la parabola cresce, per avvicinarci al minimo dobbiamo andare indietro; se al contrario è negativa, la parabola decresce e quindi dobbiamo andare in avanti.
In sostanza ci spostiamo con passi proporzionali ad \alpha nella direzione opposta a quella che ci dice la derivata, o in generale il gradiente.
Aiutiamoci con un disegno

 GradDescent

Nel punto di partenza A la derivata è positiva, debbo dunque spostarmi all'indietro e finisco in B dove la derivata è negativa, quindi mi sposto in avanti e finisco in C\dots procedendo così arriverò augurabilmente al punto di minimo della parabola.

Abbiamo trovato i parametri ottimali e quindi la funzione ipotesi h_\theta tanto agognata!

Uno contro tutti.

Torniamo ad un dettaglio lasciato in sospeso precedentemente: la classificazione dei dati in più categorie, espandendo cioè il range di valori che l'output può acquisire, y\in\left\{0,\dots,n\right\}.
Dividiamo semplicemente questo nuovo problema in n+1 problemi di classificazione binaria, una classe contro tutte le altre, ognuno dei quali produrrà la funzione ipotesi
\begin{equation*}h_\theta^{(i)}(x):=P(y=i|x;\theta), \mbox{ per ogni } i=0,\dots,n.\end{equation*}
La nostra ipotesi sulla predizione relativa al nuovo input sarà y=j se h_\theta^{(j)} realizza il massimo tra tutte le h_\theta^{(i)}.

La smetto di tediarvi! Non me ne vogliate se sono stato noioso, pesante, prolisso: è il mio primo post!
Critiche, suggerimenti e commenti sono ovviamente i benvenuti, nel frattempo si pensa già al prossimo post... non si sa bene cosa riguarderà, certamente roba più o meno attinente all'apprendimento automatico.
A presto.

P.S.

"Sì vabbè ma cosa me ne importa! Di lettere se ne mandano sempre meno! Si scrive sempre di più al computer! Impegnati a scrivere! Perché devo inventare un cervello artificiale per capirti bla bla bla..."
Alla fine di questo post potreste pensare che approfondire lo studio sulla questione presentata è, come dire, inutile.
In effetti questo presentato è forse l'esempio con il miglior rapporto interesse/semplicità-di-trattazione che mi sia venuto in mente, tuttavia queste tecniche sono alla base del riconoscimento dei volti o di immagini ben più complicate (2D o 3D), delle self-driving car, delle firme digitali e tanto altro ancora...interessante no?

CC BY-NC-SA 4.0
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

Similar posts

Nessun commento ancora

Lascia una risposta

L'indirizzo email non verrà pubblicato. I campi obbligatori sono contrassegnati *

È possibile utilizzare questi tag ed attributi XHTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Partecipa all’indagine “Io e la Matematica”

Clicca sull'immagine sottostante per rispondere al breve e anonimo questionario:

MIA15 - Nomination

Conviditi con i tuoi contatti questo link!

Canale Telegram dedicato alla Matematica

Iscriviti sul nostro canale Telegram

MIA15 - Nomination

Rimani aggiornato sui più interessanti articoli di divulgazione matematica e non solo!

Iscriviti alla nostra newsletter

Resta aggiornato sui nostri post e su quello che facciamo.

Seguici su Twitter

Tag Cloud

Grazie per il sostegno ai #MIA2015

Grazie a tutti per averci votato ai "Macchia Nera Awards 2015" nella categoria "Miglior Sito Tecnico-Divulgativo".

Siamo arrivati in finale grazie al vostro sostegno!

MIA15 - Nomination