Machine learning porta i matematici al problema “irrisolvibile”
Un semplice problema di intelligenza artificiale mette i ricercatori di fronte a un paradosso logico scoperto dal famoso matematico Kurt Gödel.
Un gruppo di ricercatori è incappato in una domanda che è matematicamente senza risposta perché è legata ai paradossi logici scoperti dal matematico austriaco Kurt Gödel negli anni ’30 che non possono essere risolti usando la matematica standard. I matematici, che stavano lavorando su un problema di apprendimento automatico, mostrano che la questione dell “apprendimento” – se un algoritmo può estrarre un modello da dati limitati – è legata a un paradosso noto come continuum hypothesis“ipotesi del continuo”. Gödel ha dimostrato che l’affermazione non può essere dimostrata né vera né falsa usando il linguaggio matematico standard. L’ultimo risultato è apparso il 7 gennaio su Nature Machine Intelligence. “Per noi è stata una sorpresa”, dice Amir Yehudayoff al Technion-Israel Institute of Technology di Haifa, che è un co-autore. Dice che sebbene ci siano un certo numero di domande di matematica tecnica che sono notoriamente “indecidibili”, non si aspettava che questo fenomeno si manifestasse in un problema relativamente semplice nel machine learning. John Tucker, scienziato informatico presso la Swansea University, nel Regno Unito, afferma che il documento è “un risultato pesante ai limiti delle nostre conoscenze”, con implicazioni fondazionali sia per la matematica che per l’apprendimento automatico.
Non tutti gli insiemi sono uguali
I ricercatori spesso definiscono l’apprendimento in termini di capacità di un algoritmo di generalizzare le proprie conoscenze. All’algoritmo viene data la risposta a una domanda “sì o no” – come “Questa immagine mostra un gatto?” – per un numero limitato di oggetti, e quindi deve indovinare la risposta per nuovi oggetti. Yehudayoff e i suoi collaboratori sono arrivati al loro risultato mentre studiavano la connessione tra l’apprendimento e la “compressione”, che implica la ricerca di un modo per riassumere le caratteristiche salienti di un grande insieme di dati in un insieme più piccolo di dati. Gli autori hanno scoperto che la capacità delle informazioni di essere compresso efficientemente si riduce a una domanda nella teoria degli insiemi – collezioni matematiche di oggetti come gli insiemi nei diagrammi di Venn. In particolare, si riferisce alle diverse dimensioni di set contenenti infinitamente molti oggetti. Georg Cantor, il fondatore della teoria degli insiemi, dimostrò nel 1870 che non tutti gli insiemi infiniti sono creati uguali: in particolare, l’insieme dei numeri interi è “più piccolo” dell’insieme di tutti i numeri reali, noto anche come continuum. (I numeri reali includono i numeri irrazionali, così come i razionali e gli interi.) Cantor ha anche suggerito che non ci possono essere insiemi di dimensioni intermedie – cioè, più grandi degli interi ma più piccoli del continuum. Ma non era in grado di dimostrare questa ipotesi di continuum, e nemmeno molti matematici e logici che lo seguivano. I loro sforzi furono vani. Un risultato del 1940 di Gödel (che fu completato negli anni ’60 dal matematico statunitense Paul Cohen) mostrò che l’ipotesi del continuo non può essere dimostrata né vera né falsa a partire dagli assiomi standard – le affermazioni considerate vere – della teoria degli insiemi, che sono comunemente presi come base per tutta la matematica. Il lavoro di Gödel e Cohen sull’ipotesi del continuum implica che possano esistere universi matematici paralleli che sono entrambi compatibili con la matematica standard – uno in cui l’ipotesi del continuo viene aggiunta agli assiomi standard e quindi dichiarata vera, e un’altra in cui è dichiarata falsa.
Limite di apprendimento
Nell’ultimo articolo, Yehudayoff ed i suoi collaboratori definiscono la learnability “apprendibilità” come la capacità di fare previsioni su un grande set di dati campionando un piccolo numero di punti dati. Il collegamento con il problema di Cantor è che ci sono infiniti modi di scegliere l’insieme più piccolo, ma la dimensione di quell’infinito è sconosciuta. Gli autori continuano a dimostrare che se l’ipotesi del continuo è vera, un piccolo campione è sufficiente per effettuare l’estrapolazione. Ma se è falso, nessun campione finito può mai essere sufficiente. In questo modo mostrano che il problema dell’apprendimento è equivalente all’ipotesi del continuo. Pertanto, anche il problema di apprendimento è in uno stato di limbo che può essere risolto solo scegliendo l’universo assiomatico. Il risultato aiuta anche a dare una più ampia comprensione dell’apprendimento, dice Yehudayoff. “Questa connessione tra compressione e generalizzazione è davvero fondamentale se vuoi capire l’apprendimento.” I ricercatori hanno scoperto una serie di problemi “indecidibili” allo stesso modo, afferma Peter O’Hearn, scienziato informatico presso l’University College di Londra. In particolare, dopo il lavoro di Gödel, Alan Turing – che ha co-fondato la teoria degli algoritmi – ha trovato una classe di domande a cui nessun programma per computer può essere garantito per rispondere in un numero finito di passaggi. Ma l’indecidibilità degli ultimi risultati è “di un tipo raro”, e molto più sorprendente, aggiunge O’Hearn: indica ciò che Gödel ha scoperto essere un’intrinseca incompletezza in qualsiasi linguaggio matematico. I risultati saranno probabilmente importanti per la teoria del machine learning, aggiunge, anche se “non è sicuro che avrà un grande impatto sulla pratica”.
