Non tutto è dimostrabile nel machine learning

Esiste un modo per dimostrare che un certo concetto, che al momento non è classificato in modo soddisfacente, un giorno sarà alla portata di un algoritmo di apprendimento? E al contrario: esistono concetti impossibili da apprendere meccanicamente? Con questa domanda, formulata nella rubrica Il Pollo di Trilussa (che in questo numero si prende una pausa), ci eravamo lasciati lo scorso mese.

A un quesito simile ha risposto Alan Turing nel 1936, portando al culmine una serie di risultati  passati alla storia della logica con il nome collettivo di Teoremi Limitativi. Tutto era partito da una domanda apparentemente fine a se stessa: “Di quanti punti è fatta la retta del piano euclideo?”. A prima vista sembrano ambiti molto diversi. Il machine learning fa riferimento a una delle aree di maggiore penetrazione tecnologica e sociale della scienza contemporanea: l’intelligenza artificiale di nuova generazione, quella che sa mettere a profitto (notevole, in alcuni casi) i “big data”. Dall’altra parte, invece, abbiamo una delle domande centrali di quella teoria degli insiemi che è stata inventata da Georg Cantor per fornire alla comunità matematica uno strumento per ragionare rigorosamente di quantità infinite.

L’apparenza inganna. È stato da poco dimostrato, da una collaborazione internazionale tra informatici, matematici e statistici, che le domande sono strettamente legate. O meglio, lo sono le risposte nella misura in cui queste sono impossibili da ottenere con gli strumenti standard della matematica. Formulando infatti il problema generale dell’apprendimento automatico in termini di classificazione, il risultato pubblicato a gennaio su Nature Machine Intelligence dimostra che una classe rilevante di problemi di apprendimento è indecidibile, nel senso che gli strumenti standard della matematica non permettono di dimostrare né che un certo concetto sarà apprendibile, né che non lo sarà. Nella prima giornata dei Discorsi e dimostrazioni matematiche intorno a due nuove scienze, Galileo enunciava il fatto, certamente sorprendente, che si potessero contare tanti numeri quanti quadrati e in entrambi i casi, infinitamente molti. La sorpresa, ovviamente, veniva dal fatto che non tutti i numeri sono quadrati. La conclusione è prudente: meglio limitare i confronti di numerosità alle quantità finite.

Ma si trattava di un problema troppo interessante per rimanere inattaccato. Come risultato accessorio alla dimostrazione dell’esistenza di numeri trascendenti – l’ultima parola, negativa, sulla quadratura del cerchio – Cantor mostra nel 1874 come mettere in corrispondenza biunivoca i numeri algebrici, cioè i numeri che sono soluzioni di equazioni polinomiali a coefficienti interi, e i naturali. Nella terminologia attuale, dimostra cioè che l’insieme dei numeri algebrici è numerabile, osservando poi che una tale corrispondenza con l’insieme dei numeri reali non è costruibile.

Una dimostrazione più generale arriverà quattro anni dopo: è impossibile mettere in corrispondenza biunivoca un insieme qualsiasi con l’insieme dei suoi sottoinsiemi da cui segue, in particolare, che l’insieme dei punti della retta è più che numerabile. Nasce così la congettura passata alla storia come Ipotesi del Continuo per cui non esiste alcun tipo “intermedio” di infinito tra quello dei naturali e quello dei reali.

Nella Conferenza di Parigi del 1900 David Hilbert pose questo in cima alla lista di problemi più famosi della matematica. Né Cantor, né Hilbert né altri riuscirono a risolvere la questione e per un buon motivo: nel 1963 Paul Coen si è guadagnato la medaglia Fields mostrando la futilità della ricerca di una dimostrazione perché la negazione dell’ipotesi è coerente, così come Kurt Gödel aveva dimostrato per l’ipotesi stessa. Dunque la congettura di Cantor è indipendente dagli assiomi standard della teoria degli insiemi.

Torniamo ai Teoremi Limitativi. Verso la fine dell’Ottocento i progressi speditissimi della matematica si confrontavano con (vecchi) paradossi che ne mettevano l’affidabilità in discussione. Uno su tutti, il paradosso di Russell, diventato celebre nella sua versione da barbiere: Bertrand è un barbiere che rade tutti gli uomini del suo paese che non si radono da soli. Bertrand si rade da solo? Se Bertrand non si rade da solo, allora è lui a radersi. Ma se si rade da solo, allora non è lui a radersi.

Casi di questo tipo portarono Hilbert a includere, tra i 23 problemi di Parigi, quello della non-contraddittorietà della matematica, che avrebbe rassicurato sulla natura patologica, e quindi trascurabile, del paradosso di Russell e di situazioni analoghe. Ma le cose non sono andate così.

Nel 1931 Gödel dimostrò l’indecidibilità di questo problema: a meno che non sia 0=1 (da cui si potrebbe dimostrare tutto, non solo quello che voleva Hilbert), l’asserzione che esprime la coerenza della matematica non è dimostrabile né refutabile con gli strumenti standard della matematica.

Usando la tecnica di Gödel, che elaborava quella di Cantor, Turing dimostrò infine l’indecidibilità del cosiddetto Problema della Fermata: la domanda “esiste una soluzione algoritmica a un problema qualsiasi?” non ha risposta algoritmica. Torniamo all’apprendimento meccanico.

Nell’articolo pubblicato su Nature Machine Intelligence, si dimostra che gli strumenti matematici standard non permettono di dimostrare né che un certo concetto verrà appreso, né che non verrà mai appreso. Il risultato si ottiene riducendo una certa formulazione generale del problema dell’apprendibilità meccanica proprio all’Ipotesi del Continuo.

Si tratta della fine del machine learning? Tutt’altro! Il periodo d’oro della logica matematica è iniziato esattamente nel momento in cui Gödel, Tarski, Church e Turing hanno dimostrato i limiti intrinseci dei loro strumenti: dimostrabilità, verità, computabilità.