Two Dimensions Govern Agnostic Multiclass Transductive Learning

Nel mondo dell'apprendimento automatico, i computer imparano a fare previsioni studiando degli esempi. Immaginate uno studente che cerca di indovinare la risposta a una domanda di un test. Nel modo standard di apprendere, chiamato "apprendimento PAC", lo studente si esercita su un insieme di flashcard, per poi sostenere un test su nuove carte mai viste prima. L'obiettivo è performare bene in media su molti test possibili. Ma esiste un altro modo di apprendere, più specifico, chiamato "apprendimento trasduttivo". Qui, allo studente viene consegnato in anticipo l'intero foglio del test, incluse tutte le domande, ma la risposta a una sola domanda specifica è nascosta. Lo studente vede tutte le altre risposte e deve prevedere l'unica etichetta mancante. Questa configurazione è più rigorosa perché lo studente non può fare affidamento sulla prestazione media; deve essere esatto per quel set specifico e fisso di domande.

Per problemi semplici con solo due possibili risposte, come "sì" o "no", i ricercatori sanno da tempo che questi due modi di apprendere sono essenzialmente gli stessi in termini di quanto dato sia necessario per avere successo. Tuttavia, quando le risposte possono essere una tra molte possibilità — come identificare migliaia di diverse specie di uccelli o diagnosticare centinaia di malattie — le regole cambiano. In queste situazioni complesse, "multiclasse", la difficoltà di apprendere dipende da due diverse misure matematiche di complessità. Una misura, spesso chiamata dimensione DS, riguarda quanto bene il discente possa gestire situazioni in cui esiste una risposta perfetta. L'altra, la dimensione di Natarajan, riguarda quanta incertezza rimane quando non è disponibile una risposta perfetta. Per anni, è stato un quesito aperto se le regole più rigide dell'apprendimento "trasduttivo" costringerebbero il discente ad aver bisogno di più dati rispetto alle regole "PAC" standard, specialmente quando il numero di possibili risposte è enorme o addirittura infinito.

Un ricercatore della Johns Hopkins University ha ora risolto questa questione, dimostrando che per i problemi multiclasse, le rigide regole trasduttive non richiedono effettivamente più dati rispetto alle regole standard, salvo piccolissimi aggiustamenti. Ha dimostrato che la quantità di informazione necessaria per apprendere in questo contesto rigoroso è governata dalle stesse due misure di complessità che controllano l'impostazione standard. Il suo lavoro dimostra che anche quando il discente deve prevedere un'unica etichetta nascosta da un gruppo fisso di esempi, può raggiungere lo stesso livello di accuratezza come se stesse imparando da un flusso casuale di dati. Questa scoperta è significativa perché unifica due diversi modelli di apprendimento, confermando che i limiti fondamentali dell'apprendimento sono determinati dalla natura del problema stesso, non dal modo specifico in cui i dati vengono presentati.

Per raggiungere questa conclusione, il ricercatore ha dovuto superare un ostacolo importante. Nell'impostazione trasduttiva rigorosa, un discente non può semplicemente guardare tutte le risposte visibili e scegliere la regola migliore, perché ciò può portare a una sorta di instabilità. Se un discente cerca di adattarsi perfettamente ai dati visibili, potrebbe accidentalmente creare una regola che funziona per ogni esempio visibile ma fallisce completamente sul caso nascosto. Questo è simile a uno studente che memorizza le risposte a ogni domanda di pratica ma fallisce il test perché non ha compreso il modello sottostante. Il ricercatore ha scoperto che, per evitare questa trappola, il discente deve deliberatamente ignorare una parte dei dati visibili.

La soluzione che ha ideato prevede una strategia di "riserva casuale". Invece di usare tutti gli esempi visibili per costruire una previsione, il discente mette da parte casualmente un grosso blocco dei dati visibili, trattandoli come se fossero il punto di test nascosto. Ignorando queste etichette riservate, il discente crea un grande blocco di dati non visti che è statisticamente indipendente dalla regola che costruisce. Ciò gli consente di utilizzare potenti strumenti matematici che si basano sull'idea di generalizzazione: prevedere bene su dati che non sono stati utilizzati per costruire il modello. Il discente utilizza quindi un processo in tre fasi per perfezionare la sua previsione. Primo, utilizza un piccolo campione dei dati visibili per creare un elenco finito di possibili regole di previsione. Secondo, utilizza un sistema di voto ponderato per restringere l'elenco delle possibili risposte per ogni domanda, riducendo efficacemente la complessità del problema. Infine, utilizza i restanti dati visibili per selezionare la migliore regola da questo elenco ristretto.

Questo approccio si basa su una nuova intuizione matematica su come gestire i dati che vengono campionati senza reinserimento. In molti scenari di apprendimento, si assume che i punti dati siano indipendenti, come estrarre una carta da un mazzo e rimetterla dentro. Ma nell'impostazione trasduttiva, una volta visto un punto dato, non può essere visto di nuovo. Il ricercatore ha dimostrato che, anche con questa restrizione, un tipo specifico di sistema di voto ponderato funziona ancora efficacemente. Ha dimostrato che gli "esperti" o le regole nel loro sistema ottengono una quantità prevedibile di "ricompense" in base a quanto bene coprono le parti non viste dei dati. Ciò assicura che il discente non perda accuratezza passando dai dati visibili alla previsione nascosta.

Il ricercatore ha anche dimostrato che il suo risultato è il migliore possibile costruendo esempi specifici in cui l'apprendimento diventa difficile. Ha mostrato che se un problema ha un alto livello di complessità nel senso della "risposta perfetta", il tasso di errore sarà proporzionale a tale complessità divisa per il numero di esempi. Se il problema ha un alto livello di incertezza nel senso del "nessuna risposta perfetta", il tasso di errore sarà proporzionale alla radice quadrata di tale complessità divisa per il numero di esempi. Entrambi i fattori sono necessari; rimuoverne anche solo uno renderebbe il compito di apprendimento impossibile in certi casi. Ciò conferma che le due dimensioni di complessità identificate nell'apprendimento standard sono effettivamente le misure corrette anche per l'impostazione trasduttiva rigorosa.

Le implicazioni di questo lavoro sono che il divario tra i due modelli di apprendimento è stato colmato. Per chiunque progetti algoritmi di apprendimento per problemi multiclasse complessi, significa che gli stessi limiti teorici si applicano sia che i dati siano presentati come un flusso casuale, sia come un insieme fisso con un'unica risposta nascosta. Il ricercatore non ha fornito un algoritmo specifico che sia garantito essere veloce su un computer, poiché la sua prova si basa sulla teoria dell'informazione piuttosto che sull'efficienza computazionale. Tuttavia, ha stabilito che la barriera fondamentale all'apprendimento è la stessa in entrambi i mondi. Mostrando che un approccio strutturato utilizzando la riserva casuale e la compressione può trasferire il successo dell'apprendimento standard all'impostazione trasduttiva rigorosa, ha fornito una chiara tabella di marcia per comprendere i limiti della previsione in ambienti complessi.

Questo lavoro chiarisce anche il ruolo dei diversi tipi di complessità nell'apprendimento. Dimostra che la capacità di apprendere una regola perfetta e la capacità di apprendere una buona regola in presenza di rumore sono sfide distinte, ognuna delle quali richiede una diversa quantità di dati. Il ricercatore ha dimostrato che queste sfide non si sommano in modo da rendere l'impostazione trasduttiva più difficile di quella standard. Invece, il discente può navigare nella popolazione fissa di dati ignorando strategicamente parti di essa, trasformando così un problema difficile e instabile in uno gestibile. Il risultato regge anche quando il numero di possibili risposte è infinito, uno scenario in cui i metodi precedenti spesso fallivano.

In definitiva, lo studio conferma che le leggi che governano il modo in cui le macchine apprendono sono robuste. Che il discente stia praticando su un insieme casuale di esempi o risolvendo un puzzle specifico con un pezzo mancante, la quantità di informazione necessaria per avere successo è determinata dalla stessa struttura sottostante del problema. Il ricercatore ha dimostrato che, gestendo attentamente come i dati vengono utilizzati e comprendendo le specifiche dimensioni di complessità coinvolte, è possibile ottenere prestazioni ottimali negli ambienti di apprendimento più rigorosi. Ciò fornisce una solida base teorica per i futuri sviluppi nell'apprendimento automatico, assicurando che, man mano che gli algoritmi diventano più sofisticati, rimangano radicati in una chiara comprensione di ciò che è possibile.