Passa ai contenuti principali

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.

Commenti

Popular Posts

"Ingegneria deve essere difficile"

Il ritaglio di giornale qui sotto ricorda uno degli eventi più non-trovo-un-aggettivo-appropriato del mio periodo di studente di Ingegneria a Pisa. Ricordo che una mattina iniziò a spargersi la voce "hanno murato la porta del dipartimento!".  Andammo subito a vedere ed arrivammo un pò prima dei giornalisti che scattarono questa foto. La porta era murata, intonacata, pitturata di bianco e sovrastata da una scritta "INGEGNERIA DEVE ESSERE DIFFICILE". Le "E" di "INGEGNERIA" erano scritte al contrario perché era una sorta di "marchio di fabbrica" della facoltà di Ingegneria di Pisa. L'aula più grande, quella in cui pressoché tutti gli studenti seguivano i corsi dei primi anni, aveva infatti alcuni bellissimi "affreschi scherzosi" che furono fatti nel corso delle proteste studentesche di qualche anno prima ed in cui la parola "Ingegneria" era appuntoi scritta in quel modo. Si era anche già sparsa la voce di cosa era

Il patch che non era un patch

Quanto segue è un patetico quanto inutile tentativo di distrarmi e non pensare alla pessima prestazione calcistica di ieri sera, decisamente non all'altezza dell'evento e dei nostri gloriosi colori. Nella lezione di "Computer Networks and Principles of Cybersecurity" di ieri, mi è stata posta la domanda " E' possibile che un patch introduca nuove vulnerabilità? ". La mia risposta è stata affermativa, ho evidenziato che un patch è un software, quindi può introdurre errori, vulnerabilità, può fare riemergere errori o vulnerabilità presenti e risolti in versioni precedenti, può correggere la specifica vulnerabilità presumibilmente risolta da quel patch solo in parte. Non è frequente, ma può accadere ed è quindi una possibilità da tenere presente. Uno dei numerosi motivi che rendono così complessa la gestione delle vulnerabilità è anche questo. Stamattina ho letto un esempio molto interessante di quanto abbiamo detto. Pochissime settimane fa Microsoft ha ril

Perché studiare Analisi Matematica???

Un mio caro amico mi ha scritto: ...sono con mia figlia che studia Analisi 1...A cosa serve, al giorno d'oggi, studiare Analisi (a parte sfoltire i ranghi degli aspiranti ingegneri)? Riporto la mia risposta di seguito, forse può "motivare" qualche altro studente. ... Per un ingegnere la matematica è fondamentale perché è un linguaggio ; ed è il linguaggio essenziale per trattare gli argomenti che dovrà affrontare come ingegnere; non sono importanti i contenuti specifici; è importante, anzi fondamentale, che riesca a capirli, ricostruirli etc. ad esempio, chi deve usare l'inglese, lo usa perché in un modo o nell'altro lo conosce; nessuno di noi ha usato esattamente le frasi o i dialoghi o le regole che ha incontrato negli esercizi di inglese o di tedesco; nella matematica è lo stesso; non sono importanti i limiti, le serie, i teoremi di cauchy o che so io; ma se uno non è in grado di capire quel linguaggio allora non sarà in grado di capire davvero quas

40 anni di Internet: Cosa non ha funzionato e perché

Leggo molti documenti tecnico-scientifici per lavoro e, in parte, per "piacere". Molti sono interessanti, alcuni molto interessanti. E' raro che trovi un documento che mi appare illuminante. Questo indicato sotto è uno dei pochi documenti in questa categoria. Sembra banale, in quanto è molto discorsivo e parla di molte cose note: IP, DNS, NAT.... In realtà è profondissimo. Una miniera di riflessioni profonde, sintetiche, focalizzate ed, appunto, illuminanti. A mio parere imperdibile per chiunque abbia un qualche interesse negli aspetti tecnici di Internet. Chi non ha la pazienza di leggerlo per intero, legga almeno gli ultimi due paragrafi. Failed Expectations (l'autore, Geoff Houston , fa parte della Internet Hall of Fame )

ChatGPT: supererebbe il mio esame di Reti di Calcolatori?

Molto probabilmente chi ha a che fare con i corsi di laurea scientifici e tecnologici, come me, ha preso atto della notizia che ChatGPT ha superato esami universitari in giurisprudenza ed economia con un pò, diciamo così, di sufficienza. Pensando "da noi non potrebbe mai succedere; figuriamoci". E' quello che ho pensato io. Poi però ho fatto a ChatGPT qualche domanda di Reti di Calcolatori. Ho quasi cambiato idea. "Quasi" perché nello scritto di Reti di Calcolatori faccio sempre esercizi. Pur non avendoli sottoposti a ChatGPT sono certo che questi esercizi non li sa risolvere. Ma alle "domande tipiche da orale" ha fornito risposte che mi hanno davvero stupefatto. Riporto qui sotto solo un esempio di "dialogo", relativo a validazione di firma digitale e certificati auto-firmati. Risposte sostanzialmente corrette e pertinenti, molto più sintetiche e focalizzate di quelle che ricevo normalmente. E più rapide. Alla fine ha riconosciuto di esser