Come generare programmi automaticamente

Nell'ultima lezione di Reti ho accennato al Machine Learning come tecnica per costruire i filtri anti-spam. Il Machine Learning è un insieme di tecniche che permettono di fare una cosa fantastica:

1. ho un problema che non ho la minima idea di come risolvere;
2. ho tanti esempi risolti di quel problema, cioè tante coppie "dati del problema", "risultato desiderato".

Grazie a queste tecniche, si può generare automaticamente un algoritmo che risolve il problema.

Descritta in questi termini la faccenda è fantastica: come generare un algoritmo in grado di cucinare piatti buonissimi ? basta fornire un grande elenco di ricette di piatti buoni, un altro grande elenco di piatti pessimi, e voilà. Come generare un algoritmo in grado di sintetizzare canzoni di successo ? idem, un elenco di successi ed un elenco di canzoni schifose e siamo a posto. Ovviamente le cose non sono così semplici e queste tecniche, pur applicabili in moltissimi campi, non si possono applicare "sempre". In questi due casi non funzionano (almeno sinora), ma in molti altri casi funzionano benissimo ed hanno permesso di risolvere problemi che nessuno sapeva come risolvere, oppure di trovare soluzioni alternative e più efficienti di quelle usate di solito.

Nel nostro laboratorio ci occupiamo anche noi di queste cose e proprio ieri abbiamo ottenuto un risultato interessante, che sarà presentato ad una top conference nei prossimi mesi.

Su Internet nascono ogni tanto delle competizioni di programmazione ("code golf") in cui i programmatori competono per scrivere il programma più corto che risolve un dato problema. Nei mesi scorsi hanno iniziato a diffondersi delle competizioni simili in cui il programma da scrivere è una espressione regolare ("regex golf"). Una espressione regolare è un modo molto compatto per descrivere sequenze di caratteri---una sorta di linguaggio specializzato per la descrizione di pattern. Ad esempio "\b\d{1,3}\.\d{1,3}\.\d{1,3}\.\d{1,3}\b" è un'espressione regolare che descrive gli indirizzi IP (con qualche approssimazione che non approfondisco). Le espressioni regolari sono usate in moltissimi contesti pratici e sono, come si intuisce, complicate da scrivere.

Le competizioni "regex golf" sono sfide di questo genere: dato un elenco di stringhe da riconoscere ed un elenco di stringhe da non riconoscere, generare la più corta espressione regolare che riconosce tutte le stringhe nel primo elenco e non riconosce nessuna nel secondo elenco. Un esempio di regex golf è riconoscere tutti i cognomi dei presidenti degli Stati Uniti e non riconoscere nessun cognome degli sfidanti sconfitti alle elezioni.

E' facile rendersi conto che problemi di questo genere sono, in linea di principio, adatti per le tecniche di Machine Learning. In linea di principio. Nessuno era ancora riuscito a farlo.

Noi siamo riusciti a generare un regex golf player competitivo con i player umani.

We considered a popular regex golf challenge proposed recently and compared the performance of our player to the best results produced by humans and to the only existing algorithm for playing automatically---an algorithm developed by Peter Norvig, Director of Google Research (!).

We rank in the top ten list worldwide, 6-th and 7-th place, beaten only by a few humans. (full post here)

E' interessante anche la particolare tecnica di Machine Learning che abbiamo usato: il Genetic Programming, una tecnica ispirata all'evoluzione biologica. Abbiamo creato una popolazione composta da centinaia di soluzioni generate (quasi) a caso. Abbiamo fatto evolvere questa popolazione, incrociando tra loro (a caso) alcune soluzioni e modificando (a caso) altre soluzioni. Nell'evoluzione abbiamo privilegiato la sopravvivenza delle soluzioni migliori. Abbiamo fatto proseguire l'evoluzione per centinaia di generazioni ed alla fine...voilà, tante soluzioni con ottime prestazioni !

Abbiamo sempre varie proposte per tesi e tirocini, triennali e magistrali, su tematiche di Machine Learning. So che gli studenti tendono a preferire lo sviluppo dei soliti programmi con le solite finestre con i soliti bottoncini colorati semplicemente installando, configurando ed usando una delle N tecnologie di moda del momento...ma ogni tanto c'è qualcuno che preferisce qualcosa di più challenging.