Macchine che imparano #2: l'importanza dei vicini

Ricordate il problema della determinazione del genere di un autore? Ne avevo parlato nel primo post di questa serie dedicata alle tecniche di apprendimento automatico (in inglese, machine learning), interrotta sul nascere per molti mesi, che da oggi riprenderà tuttavia a camminare con maggiore regolarità.

Qualche volta vi sarà forse capitato di leggere un articolo, un racconto, o un qualsiasi testo, e non conoscendo nome e cognome dell'autore, vi sarete chiesti perlomeno se si tratti di un uomo o di una donna. Certo, questa attribuzione può diventare banale qualora il testo contenga indicazioni autoreferenziali: se a un certo punto si legge qualcosa come "il tale giorno mi sono recata nella tale città" è evidente che a scrivere è una donna e non un uomo. Ma in molti altri casi è molto più difficile determinare il sesso dell'autore, e per farlo ci si deve basare su elementi poco oggettivi e di dubbia interpretazione, come lo stile, la frequenza di certe parole, l’utilizzo di costrutti sintattici.

Può sembrare strano, ma c’è chi si è occupato in modo scientifico di questo tipo di determinazioni. Da alcuni studi, condotti su diverse lingue (non soltanto l'inglese ma, per esempio, anche lo spagnolo), risulta per esempio che gli uomini utilizzano le preposizioni in misura maggiore rispetto alle donne. Una spiegazione psicologica che viene fornita a supporto di questo dato è che gli uomini hanno più bisogno di categorizzare gerarchicamente gli oggetti all'interno dell'ambiente. Viceversa, le donne sembrano adoperare più interiezioni, più pronomi, più determinanti (cioè articoli, pronomi dimostrativi e in certe lingue come l'inglese e il francese anche i possessivi) rispetto agli uomini, probabilmente perché sono più interessate alle relazioni sociali.

Alcune ricerche suggeriscono che le donne si esprimono mediante un linguaggio più emotivamente connotato, e per questo impiegano più aggettivi e più avverbi degli uomini. Inoltre sembra che gli uomini commettano più errori grammaticali delle donne e si servano più spesso di quantificatori. Un paio di articoli su questa area della ricerca sono questo e questo.

Mi piace l’idea di utilizzare il curioso problema della determinazione del genere di un autore come esempio di applicazione delle tecniche di apprendimento automatico. Supponiamo di avere una raccolta di 50 racconti: dei primi 49 conosciamo con certezza il genere dell’autore, ma per il cinquantesimo no. Come possiamo affrontare il problema? Potremmo provare a concentrarci su un insieme ristretto di indicatori che riteniamo significativi per il nostro compito di attribuire un genere all’autore misterioso. Immaginiamo di considerarne soltanto due, per esempio il numero di aggettivi e il numero di determinanti ogni 1000 parole.

A ognuno dei 49 racconti già classificati possiamo assegnare una coppia di numeri, corrispondenti agli indicatori che abbiamo scelto. Per esempio, il primo racconto potrebbe essere costituito complessivamente da 5450 parole, e contenere 409 aggettivi e 703 determinanti. Ciò significa che, mediamente, questo testo contiene circa 75 aggettivi e 129 determinanti ogni 1000 parole. La coppia di numeri da attribuire al primo racconto è quindi (75, 129). 

Potrebbe venire quasi spontaneo, a questo punto, pensare di rappresentare ciascuno dei racconti come un punto sul piano cartesiano, le cui coordinate (x, y) corrispondono ai due numeri caratterizzanti. Il risultato sarà un diagramma costellato di 49 punti, uno per ogni racconto già classificato. Potremmo pensare di rappresentare gli autori maschili come pallini gialli e le scrittrici come pallini viola. A questo punto analizziamo il cinquantesimo racconto, quello scritto dall'autore senza volto, e determiniamo i due indicatori. Il punto che disegneremo sul piano cartesiano avrà una collocazione ben precisa, ma non possiamo sapere se sia un pallino giallo o un pallino viola: il nostro obiettivo è proprio decidere il colore di questo cinquantesimo pallino.

Sgombriamo il campo da un dubbio: la tecnica che descriverò può sperare di risolvere il problema della determinazione del genere, ma è soggetta all'errore. Non c'è alcuna certezza nel successo di questo algoritmo, perché si tratta di una metodologia di predizione incerta per definizione.

L'idea è la seguente: si traccia una circonferenza attorno al pallino senza colore, in modo da comprendere al suo interno un numero prestabilito k di pallini colorati, ovvero di racconti di autore noto. La nostra predizione deve basarsi sul genere prevalente presente tra i k pallini racchiusi dalla circonferenza.

Per esempio, considerando la figura a fianco, con k = 3, abbiamo due pallini viola e un pallino giallo, cioè prevalgono le autrici. In base alla tecnica descritta, dobbiamo prevedere che l'autore del cinquantesimo racconto sia una donna. Che l'algoritmo sia per definizione incerto è dimostrato dal fatto che scegliendo, in alternativa, k = 6, i pallini considerati diventano 4 gialli e 2 viola: elementi che ci guiderebbero ad azzardare una predizione maschile per il cinquantesimo racconto.
Dove sta l'apprendimento automatico in questa procedura? Nella fase di acquisizione delle informazioni relative ai 49 punti associati ai racconti di autore noto: l'algoritmo, infatti, apprende, per ciascuno di questi punti, il genere dell'autore, e questi dati divengono la base di conoscenza su cui si basa la predizione relativa al cinquantesimo racconto. Si dice anche che questi 49 punti sono esempi noti che l'algoritmo utilizza per addestrarsi, in modo da costruire una sua descrizione interna (cioè un modello) del fenomeno, e quindi formulare predizioni.

L'esempio mostrato in figura ci fa osservare che lo stesso algoritmo può portare a predizioni diverse a seconda del valore scelto di k. Variando di poco il valore di k, infatti, cambia totalmente la predizione. Tale fenomeno si verifica perché sono stati scelti, per semplicità, valori molto bassi di k, mentre è evidente che, nella maggior parte dei casi, valori più alti di questo parametro possono garantire accuratezze migliori.

Inoltre, il problema scelto è un problema di classificazione binaria, perché la predizione può consistere esclusivamente in due opzioni: autore maschio o autore femmina. In problemi di tal genere, quando la predizione cambia, cambia di brutto (nel nostro esempio, da maschio a femmina, o viceversa), mentre in problemi di classificazione a più valori i cambiamenti possono essere meno radicali.

Altri due elementi molto importanti per il successo dell'algoritmo sono il numero di indicatori utilizzati e la quantità di dati di esempio impiegati per la fase di addestramento.

Utilizzando più di due indicatori, o, come si dice nel gergo tecnico, features, si può sperare di ottenere predizioni più accurate. Questo non è assicurato, tuttavia, perché se si includono nel modello features non significative, cioè grandezze che non influenzano il valore che si vuole predire, allora l'aumento del numero di features non aumenta la qualità delle predizioni. Aumentare il numero di features significa muoversi non più sul piano cartesiano, ma su un iperspazio a n dimensioni, dove n è il numero delle features selezionate.

Poter disporre di un numero il più alto possibile di esempi già classificati da cui apprendere, invece, è quasi sempre buona cosa. Non a caso il mondo dell'apprendimento automatico è strettamente imparentato con quello dei cosiddetti big data: questo non significa che avere grandi moli di dati sia di per sè sufficiente per costruire modelli vincenti grazie agli algoritmi di machine learning, ma che, al contrario, quasi mai si riesce a predire con buona precisione quando i dati a disposizione sono pochi.

Per inciso, l'algorimo che ho descritto si chiama "k-Nearest Neighbors" (kNN), ed è uno dei più famosi nel campo delle tecniche di classificazione basate sull'apprendimento automatico. Nel prossimo articolo della serie scopriremo un altro algoritmo che può essere impiegato per risolvere problemi simili.

Macchine che imparano #1: autori e autrici

Qualche anno fa frequentai un corso di scrittura creativa. Ad ogni appuntamento il docente, che tra l'altro era uno scrittore e poeta piuttosto noto, ci assegnava, come compito per la lezione successiva, la stesura di un racconto su un tema fissato.
Una volta uno di noi gli domandò se fosse in grado di capire, leggendo un racconto anonimo, di determinare il genere dell'autore (cioè se fosse uomo o donna). Il docente rispose che sì, con un po' di esercizio e di intuito si riesce abbastanza facilmente. Non fummo abbastanza cattivi da metterlo alla prova con alcuni nostri racconti privati dell'indicazione dell'autore.
 Ora, un compito di questo tipo sembra richiedere una tale dose di intuizione e di sensibilità, doti squisitamente umane, che difficilmente potremmo pensare di affidarlo a una macchina.
Eppure qualcuno ci ha pensato, e in rete si trova persino una pagina in cui potete verificare l'abilità del computer in questo difficile esercizio.

L'identificazione del genere dell'autore di un testo è infatti uno degli innumerevoli campi in cui sono state applicate le tecniche di apprendimento automatico (in inglese "machine learning").

A partire da questo post comincerò a esplorare questo vastissimo ambito dell'intelligenza artificiale di cui oggi si sente parlare sempre di più e sul quale università e aziende stanno investendo in misura sempre maggiore.

L'idea alla base dell'apprendimento automatico è molto semplice: affinché un computer riesca a risolvere un tipo di problema particolarmente difficile, come quello descritto sopra, la strategia migliore è la stessa che gli insegnanti utilizzano spesso con i propri studenti: mostrare alcuni esercizi svolti, e poi verificare se gli alunni sono in grado di risolvere da soli altri problemi dello stesso tipo.

Nel panorama odierno dell'intelligenza artificiale il machine learning è la tendenza di gran lunga dominante. Sono da un bel po' considerati old-style gli approcci utilizzati da metodologie come i sistemi di produzione o i sistemi esperti: programmi la cui ambizione era possedere fin dall'inizio l'intera base di conoscenza relativa a un dato argomento, ed essere così capaci di risolvere ogni problema di un certo tipo in maniera diretta, sulla base di deduzioni logiche.
La debolezza dei sistemi esperti era la loro incapacità di imparare dall'esperienza.
Negli anni Settanta e Ottanta, per esempio, si realizzarono sistemi esperti il cui compito era effettuare diagnosi di malattie in funzione dei sintomi segnalati dai pazienti. Anche ammettendo di poter introdurre in un simile sistema tutte le conoscenze dei migliori luminari del pianeta, il programma, una volta confezionato, poteva iniziare a formulare diagnosi, magari anche azzeccate, ma era destinato a restare un medico artificiale sempre uguale a se stesso: in altre parole, non era in grado di imparare dalla propria esperienza, cioè dai propri successi e dai propri errori.

Tratto da http://eecs.wsu.edu/~cook/ml

Una persona, prima di iniziare a lavorare, deve andare a scuola per un po' di anni: analogamente, un algorimo di apprendimento automatico, prima di cominciare a emettere le sue risposte, deve essere addestrato, cioè deve analizzare un grande numero di problemi dello stesso tipo, ciascuno completo di soluzione preconfezionata. Il programma, sulla base di questi esempi, impara, cioè costruisce e via via perfeziona un proprio "modello" interno del problema, che viene poi adoperato quando sarà il momento di lavorare davvero senza conoscere in anticipo la risposta.

Questo approccio si è rivelato ottimale per un insieme innumerevole di problemi, soprattutto quelli molto complessi per i quali non esiste una formula esatta per determinare a colpo sicuro le risposte e le predizioni desiderate.
In altre parole, a causa della complessità di questi problemi, non possiamo più ambire alla perfezione assoluta, ma dobbiamo anzi accettare una percentuale di errore (comunque limitata).
Le tecniche di un tempo, fondate su schemi rigidi di deduzione, cercherebbero di risolvere questi problemi in modo esatto, ma impiegherebbero tempi biblici prima di produrre qualcosa, il che francamente non è quello che desideriamo.

Uno dei modi per superare questa empasse è il machine learning. Un altro filone algoritmico di cui ho già parlato in passato (ad esempio qui e qui), è costituito dai metodi euristici: anche questi, seppure attraverso un percorso un po' diverso, soddisfano il bisogno di meccanismi meno rigidi, che accettano l'approssimazione e che si avvicinano alla soluzione del problema attraverso una ricerca graduale.
I due mondi, apprendimento automatico e tecniche euristiche, non sono tra di loro separati in modo netto, ma si intersecano reciprocamente in molti casi.

La necessità di ricorrere a metodologie "soft", non rigide ma basate su paradigmi "moderni" (euristici, evolutivi, di apprendimento, e così via) è resa ancora più stringente dal fatto che i dati da elaborare arrivano spesso in quantità molto grandi, a grande velocità, e con formati molto eterogenei (i famosi "big data").
Da queste confuse e furiose basi di conoscenza si vorrebbe poter estrarre informazioni pregiate, che purtroppo se ne stanno solitamente ben nascoste come minuscoli aghi d'oro nello sterminato pagliaio informativo. Le numerose tecniche basate sull'idea dell'apprendimento automatico escono spesso vincitrici in questo genere di sfida, a condizione che i dati vengano inizialmente "puliti" e resi omogenei, che venga scelto l'algoritmo più appropriato per il problema da risolvere, e che il programma sia ben addestrato nella fase iniziale.

L'esempio con cui ho aperto questo post è emblematico. Per poter sviluppare un programma capace di riconoscere se un racconto è stato scritto da uno scrittore o da una scrittrice, possiamo certamente pensare ad un approccio di tipo "machine learning". Certo, occorre prendere oculatamente alcune decisioni importanti, per esempio scegliere  un algoritmo di apprendimento che si presti a questo ingrato compito. Nella prossima puntata di questa serie entreremo nel merito matematico di una di queste tecniche di apprendimento, e vedremo di applicarla al problema dell'identificazione del genere dell'autore. 

Buon compleanno, Alan

Oggi Alan Turing compirebbe 100 anni. Peccato sia morto, appena quarantaduenne, nel lontano 1954, e in circostanze tra l'altro alquanto incresciose (non per lui, ovviamente, ma per il governo inglese che troppo tardi e goffamente ha riconosciuto le proprie responsabilità).
Ma ve lo immaginate Turing oggi?
Sarebbe più giovane di Rita Levi Montalcini, di ben tre anni.
Ve lo immaginate, il fondatore dell'informatica teorica e dell'intelligenza artificiale, nell'epoca degli iPad e degli smartphone, dei computer quantistici e dei computer a DNA?
E ve lo immaginate, il crittoanalista che durante la seconda guerra mondiale decifrò il codice Enigma usato dai nazisti, alle prese con le problematiche di sicurezza della rete?
Buon compleanno, Alan.  L'informatica continuerà ad evolvere continuamente e rapidamente dal punto di vista tecnologico, come ha sempre fatto finora; nuovi framewok, linguaggi, sistemi operativi compariranno e sostituiranno i precedenti. Ma la base teorica di tutto questo, che conta molto più dei dettagli tecnologici, attingerà, anche fra mille anni, alle ricerche fondamentali di quell'uomo che, come nella favola di Biancaneve, si spense addentando una mela avvelenata.

John McCarthy e l'attrazione fatale del 91

Dopo Steve Jobs e Dennis Ritchie, il fatidico mese di ottobre 2011 ci ha portato via un altro grande informatico: l'americano John McCarthy, uno dei padri dell'intelligenza artificiale, inventore del linguaggio di programmazione LISP, nonché premio Turing nel 1971.
Con McCarthy scompare uno dei giganti della ricerca teorica informatica, uno di quelli che hanno fatto davvero la storia della computazione.

Oltre alle sue ricerche pionieristiche sull'intelligenza artificiale (fu lui, nel lontano 1955, il primo ad adoperare la fortunatissima espressione "intelligenza artificiale"), a McCarthy dobbiamo l'invenzione di alcuni concetti oggi fondamentali dell'ambito della programmazione e delle tecnologie informatiche in genere: ad esempio il meccanismo del "garbage collection", ben noto a chiunque abbia scritto programmi per computer, e l'idea di rendere disponibile come servizio la potenza dei calcolatori, un po' come avviene per l'elettricità o l'acqua. Quest'ultimo concetto, proposto da McCarthy già all'inizio degli anni Sessanta, è stato recentemente rivalutato, e si è imposto con successo sotto forma di tecnologie con nomi diversi ("Software as a service", "Cloud computing", ecc.).

Vorrei qui ricordare McCarthy accennando ad una sua curiosa creazione matematica: la cosiddetta "funzione 91" di McCarthy.
La funzione 91 è definita come segue:







Come si può notare, la funzione è ricorsiva: per i valori minori o uguali a 100 la funzione è definita in termini di se stessa (addirittura con una doppia ricorsione).

La particolare definizione ricorsiva ha delle conseguenze molto interessanti. Provate a calcolare il valore della funzione per un qualsiasi n ≤ 101: ebbene, otterrete sempre e comunque 91!

Proviamo con n=100:

Con n=87:

Se proviamo a disegnare il grafico della funzione 91 di McCarthy, otteniamo qualcosa del genere:

E' evidente, nel primo tratto della funzione, corrispondente ai valori di n ≤ 101, che la funzione rimane fissa sul valore 91.
Lo strano comportamento della funzione, che "precipita" sempre sul numero 91 per tutti gli n ≤ 101, è dimostrabile in modo abbastanza semplice, utilizzando il metodo di induzione. Non riporto qui i passi della dimostrazione, che possono essere trovati ad esempio sulla voce di Wikipedia dedicata alla funzione 91.