Apprendimento trasduttivo

In logica, inferenza statistica e apprendimento supervisionato, l'apprendimento trasduttivo, o mediante trasduzione o inferenza trasduttiva è una forma di ragionamento che va da casi specifici osservati (di addestramento) a casi specifici (di test).[1] Al contrario, con l'induzione, il ragionamento, sulla base di casi osservati (di addestramento), mira a derivare regole (modelli) generali, da applicare poi ai casi di test. La distinzione è particolarmente interessante nei casi in cui le predizioni del modello trasduttivo possano essere ottenute da alcun modello induttivo. Si noti che ciò è causato dal fatto che l'inferenza trasduttiva, se operata su diversi set di test, può produrre conclusioni reciprocamente incoerenti.

La trasduzione è stata introdotta nel contesto dell'informatica da Vladimir Vapnik negli anni '90, motivata dalla sua visione secondo cui essa è preferibile all'induzione poiché, secondo lui, l'induzione richiede la risoluzione di un problema più generale (l'inferenza di una funzione) prima di risolvere un problema più specifico (calcolo degli output per nuovi casi): "Quando si risolve un problema di interesse, non si risolva un problema più generale come passaggio intermedio. Si cerchi di ottenere la risposta di cui si ha davvero bisogno, e non una più generale".[2]

Un esempio di apprendimento non induttivo si riscontra nel caso della classificazione binaria, in cui i dati in input tendono a raggrupparsi in due gruppi. Un insieme di dati di test ampio può aiutare a individuare i cluster, fornendo così informazioni utili riguardo alle etichette delle classi.[3] Non si potrebbero avere le stesse predizioni da un modello che induce una funzione basandosi solo su esempi di addestramento. Questa potrebbe essere considerata come una forma strettamente correlata all'apprendimento semi-supervisionato, sebbene la motivazione di Vapnik sia piuttosto diversa. L'esempio più noto di algoritmo di apprendimento basato su casi è quello del k-vicino più prossimo (k-NN) che è correlato agli algoritmi di apprendimento trasduttivo. Un altro esempio di algoritmo di tale categoria è la Transductive Support Vector Machine (TSVM).[1]

Una terza possibile motivazione per l'inferenza trasduttiva nasce dalla necessità di approssimare. Quando l'inferenza esatta risulta proibitiva dal punto di vista computazionale, si può cercare di assicurare che predizioni ottenute tramite inferenza approssimata siano valide almeno per i dati di test. In tale caso, i dati di test potrebbero provenire da una distribuzione arbitraria (non necessariamente correlata alla distribuzione dei dati di training), il che non sarebbe consentito nell'apprendimento semi-supervisionato. Un esempio di algoritmo che rientra in questa categoria è la Bayesian Committee Machine (BCM).[4]

Contesto storico

La modalità di inferenza da particolari a particolari, che Vapnik volle chiamare trasduzione, era già distinta dalla modalità di inferenza da particolari a generalizzazioni nella terza parte del manuale Logic del filosofo e logico di Cambridge W.E. Johnson [5]. Nell'opera di Johnson, la prima modalità era chiamata "eduzione" e la seconda "induzione". Bruno de Finetti sviluppò una forma puramente soggettiva di approccio bayesiano in cui le affermazioni sulle probabilità oggettive potevano essere tradotte in affermazioni empiricamente valide sulle credenze soggettive rispetto agli osservabili attraverso proprietà di scambiabilità. Una prima affermazione di questa visione si può trovare nel suo libro del 1937 "La Prévision: ses Lois Logiques, ses Sources Subjectives"[6] e un'affermazione matura nella sua "Theory of Probability " del 1970 [7]. All'interno del quadro bayesiano soggettivo di de Finetti, ogni inferenza induttiva è in ultima analisi un'inferenza da particolari a particolari.

Problema esemplificativo

Il seguente problema di esempio mette a confronto alcune delle proprietà peculiari della trasduzione rispetto all'induzione.

Sia dato un insieme di punti, tale che alcuni siano etichettati (con A, B o C), ma la maggior parte dei punti non abbia etichetta (?). L'obiettivo è predire le etichette appropriate per tutti i punti non etichettati.

L'approccio induttivo per risolvere questo problema consiste nell'utilizzare i punti etichettati per addestrare un algoritmo di apprendimento supervisionato, e poi fargli predire le etichette per tutti i punti non etichettati. Con questo problema, tuttavia, l'algoritmo di apprendimento supervisionato avrà solo cinque punti etichettati da utilizzare come base per costruire un modello predittivo. Avrà sicuramente difficoltà a costruire un modello che catturi la struttura di questi dati. Ad esempio, se si utilizza un algoritmo del vicino più prossimo, i punti vicini al centro saranno etichettati come "A" o "C", anche se è evidente che appartengono allo stesso cluster del punto etichettato con "B", a differenza di quanto accadrebbe nell'apprendimento semi-supervisionato.

La trasduzione ha il vantaggio di poter considerare tutti i punti, non solo quelli etichettati, durante l'etichettatura. In questo caso, gli algoritmi trasduttivi etichetterebbero i punti non etichettati in base ai cluster a cui appartengono naturalmente. I punti al centro, quindi, sarebbero molto probabilmente etichettati con "B", perché sono molto vicini a quel cluster.

Un vantaggio della trasduzione è che può essere in grado di fare predizioni migliori con un minor numero di punti etichettati disponibili, poiché utilizza le separazioni naturali presenti nei punti non etichettati. Uno svantaggio della trasduzione è che non costruisce alcun modello predittivo. Se si aggiunge un punto precedentemente sconosciuto all'insieme, l'intero algoritmo di trasduzione dovrebbe essere ripetuto con tutti i punti per predire un'etichetta. Questo può essere computazionalmente costoso se i dati vengono acquisiti in modo incrementale in un flusso. Inoltre, ciò potrebbe causare la modifica delle predizioni di alcuni dei vecchi punti (il che può essere positivo o negativo, a seconda dell'applicazione). Un algoritmo di apprendimento supervisionato, d'altra parte, può etichettare nuovi punti istantaneamente, con un costo computazionale molto basso.

Algoritmi di trasduzione

Gli algoritmi di trasduzione possono essere suddivisi in due categorie: quelli che cercano di assegnare etichette discrete a punti non etichettati e quelli che cercano di ricavare etichette continue per punti non etichettati. Gli algoritmi che cercano di predire etichette discrete tendono a essere derivati aggiungendo una supervisione parziale a un algoritmo di clustering. Possono essere utilizzate due classi di algoritmi: clustering piatto o gerarchico. Quest'ultimo può essere ulteriormente suddiviso in due categorie: quelli che clusterizzano per partizionamento e quelli che clusterizzano per agglomerazione. Gli algoritmi che cercano di predire etichette continue tendono a essere derivati aggiungendo una supervisione parziale a un algoritmo di apprendimento su manifold.

Trasduzione per partizionamento

La trasduzione tramite partizionamento può essere considerata una forma di trasduzione top-down. Si tratta di un'estensione semi-supervisionata del clustering basato su partizionamento. Tipicamente si procede secondo lo schema seguente:

Si considera l'insieme di tutti i punti come una grande partizione.
Mentre ogni partizione P contiene due punti con etichette in conflitto:
 Suddividere P in partizioni più piccole.
Per ogni partizione P:
 Assegnare la stessa etichetta a tutti i punti in P.

Naturalmente con questo algoritmo si può utilizzare qualsiasi tecnica di partizionamento utile allo scopo. Ad esempio, sono molto comuni gli schemi di partizionamento Max Flow Min Cut.

Trasduzione agglomerativa

La trasduzione agglomerativa può essere considerata una forma di trasduzione bottom-up. Si tratta di un'estensione semi-supervisionata del clustering agglomerativo. Viene tipicamente eseguita come segue:

Si calcolano le distanze a coppie, D, tra tutti i punti.
Si ordina D in ordine crescente.
Si considera ogni punto come un cluster di dimensione 1.
Per ogni coppia di punti {a,b} in D:
 Se (a non è etichettato) o (b non è etichettato) o (a e b hanno la stessa etichetta)
  Unire i due cluster che contengono a e b.
  Etichettare tutti i punti del cluster unito con la stessa etichetta.

Trasduzione con etichette continue

Questi metodi mirano a ricavare etichette in domini continui, spesso tramite tecniche di riduzione non lineare della dimensionalità (manifold learning). L'idea è quella di apprendere una rappresentazione a bassa dimensionalità dei dati e di dedurre i valori in modo fluido lungo la manifold.

Applicazioni e nozioni correlate

La trasduzione è strettamente correlata a:

  • Apprendimento semi-supervisionato: utilizza dati sia etichettati che non etichettati, ma in genere induce un modello.
  • Ragionamento basato sui casi, come l'algoritmo k-nearest neighbor (k-NN), spesso considerato un metodo trasduttivo.
  • Macchine a vettori di supporto trasduttivi (TSVM) : estendono le SVM standard per incorporare dati di test non etichettati durante l'addestramento.
  • Bayesian Committee Machine (BCM): un metodo di approssimazione che effettua predizioni trasduttive quando l'inferenza esatta è troppo costosa.

Note

  1. 1 2 (EN) Vladimir N. Vapnik, Statistical learning theory, Wiley, 1998, ISBN 978-0-471-03003-4.
  2. ↑ (EN) Vapnik, Estimation of Dependences Based on Empirical Data, in Information Science and Statistics, 2006, pp. 477, DOI:10.1007/0-387-34239-7, ISBN 978-0-387-30865-4, ISSN 1613-9011.
  3. ↑ (EN) Avrim Blum e Tom Mitchell, Combining labeled and unlabeled data with co-training, in Proceedings of the eleventh annual conference on Computational learning theory, Association for Computing Machinery, 24 luglio 1998, pp. 92–100, DOI:10.1145/279943.279962. URL consultato il 30 agosto 2025.
  4. ↑ (EN) Volker Tresp, A Bayesian Committee Machine, in Neural Computation, vol. 12, n. 11, 1º novembre 2000, pp. 2719–2741, DOI:10.1162/089976600300014908.
  5. ↑ (EN) W. E. Johnson, Logic, CUP Archive, 1924, Part III.
  6. ↑ (FR) Bruno de Finetti, La prévision: ses lois logiques, ses sources subjectives (PDF), collana Annales de l'I. H. P., 7 (1), 1937.
  7. ↑ (EN) Bruno De Finetti, Antonio Machì e Adrian F. M. Smith, Theory of probability: a critical introductory treatment, John Wiley & Sons, 2017, ISBN 978-1-119-28634-9.

Voci correlate

Collegamenti esterni

  • A Gammerman, V. Vovk, V. Vapnik (1998). "Learning by Transduction." An early explanation of transductive learning.
  • "http://www.kyb.mpg.de/ssl-book/discussion.pdf", Capitolo 25 di Semi-Supervised Learning, Olivier Chapelle, Bernhard Schölkopf and Alexander Zien (curatori), (2006). MIT Press. Discussione della differenza fra SSL e trasduzione.
  • Waffles - libreria C++ open source di algoritmi di apprendimento, che include algo. trasduttivi fra cui Waffles.
  • SVMlight - pacchetto general purpose per le SVM che include le TSVM.
Questa voce è stata pubblicata da Wikipedia. Il testo è rilasciato in base alla licenza Creative Commons Attribution-Share Alike 4.0, salvo diversa indicazione. Potrebbero essere applicate clausole aggiuntive per i file multimediali.