Appunti esame Machine Learning – Semi-Supervised Learning, Multi-Instance Learning ed Ensemble

Probabilità congiunta e regola di Bayes

La probabilità congiunta di n attributi Ai=1…m può essere decomposta nel seguente prodotto:

Regola di Bayes:

Supponiamo di avere i modelli per P(A|B) e P(B) e che osserviamo l’evento A=a.

Vogliamo calcolare P(B|A=a). P(A=a|B) è detta verosimiglianza, P(B) è la probabilità a priori di B e P(B|A=a) è la probabilità a posteriori. P(A=a) si ottiene dalla regola della somma:

La massima verosimiglianza

Consideriamo il problema di stimare un insieme di parametri θ di un modello probabilistico, dato un insieme di osservazioni x1,x2,…,xn. Assumiamo che le osservazioni siano continue ma il ragionamento si estende anche a quelle discrete. Le tecniche a massima verosimiglianza assumono che le istanze non hanno dipendenze l’una dall’altra e quindi l’occorrenza di una non ha effetti sull’occorrenza delle altre. Le istanze possono essere modellate tutte allo stesso modo.

Queste assunzioni spesso si riassumono dicendo che gli eventi sono I.I.D. (Indipendenti e Identicamente Distribuiti). L’assunzione di I.I.D. corrisponde all’utilizzo di una funzione di densità di probabilità congiunta per tutte le osservazioni che consiste nel prodotto dello stesso modello di probabilità p(xi, θ) applicato a ogni osservazione in maniera indipendente.

//Vedere appunti Mario cap. 9

Capitolo 11 oltre l’apprendimento supervisionato e non supervisionato

Riassunti Machine Learning 105

L’approccio semi-supervisionato si usa quando abbiamo una grossa mole di dati e solo una parte di essi sono etichettati. Molte situazioni presentano grandi volumi di dati grezzi, ma l'assegnazione delle classi è costosa perché richiede l’intervento umano.

Clustering per la classificazione

Un primo approccio è quello che prevede di combinare un approccio EM con un classificatore.

Supponiamo di avere un insieme relativamente piccolo di dati etichettati e un significativo insieme di dati non etichettati. Come prima cosa costruiamo un modello usando un classificatore Naïve Bayes sui dati etichettati e successivamente estenderlo a un ampio insieme di dati non etichettati utilizzando l'algoritmo di clustering iterativo EM (expectation-maximization).

La procedura è la seguente:

• Prima, si addestra un classificatore utilizzando i dati etichettati.
• Seconda, si applica il classificatore ai dati non etichettati per etichettarli con le probabilità delle classi (fase di "expectation").
• Terza, si addestra un nuovo classificatore utilizzando le etichette di tutti i dati (fase di "maximization").
• Quarta, si itera fino alla convergenza.

Questo può essere visto come un processo di clustering iterativo, in cui i punti di partenza e le etichette dei cluster vengono tratti dai dati etichettati. La procedura EM garantisce di trovare i parametri del modello che hanno probabilità uguali o maggiori ad ogni iterazione.

Ci sono due possibili modifiche a questo approccio:

Una prima modifica può essere quella di pesare opportunamente i campioni.

Fra i dati etichettati e quelli non inizialmente etichettati c’è una significativa differenza: il primo insieme ha etichette certe, il secondo etichette fornite in maniera probabilista. Quindi si può fare in modo di dare un peso minore ai dati non inizialmente etichettati per conferire loro minore credibilità.

Altra modifica è quella che permette di avere più cluster per ogni classe (mentre l’approccio EM classico costruisce un cluster per ogni classe). Per fare ciò si estende il modello delle misture in modo da avere componenti multiple per ogni classe e poi nello step di maximization non bisogna solo etichettare in maniera probabilistica ogni istanza ma bisogna anche assegnare in maniera probabilistica quell’istanza alle diverse componenti (i diversi cluster) associate a quella classe.

Co-Training

Riassunti Machine Learning 106

Un’altra situazione in cui dati non etichettati possono migliorare le prestazioni della classificazione è quando ci sono due viste diverse e indipendenti sull’attività di classificazione. Un classico esempio è quello delle pagine web, in cui le due viste sono quella del contenuto della pagina web e quella dei link da altre pagine. Entrambe le viste sono utili e differenti.

L’idea alla base del co-training è quella in cui date poche istanze labellate, si apprende un modello differente per ogni vista, ad esempio un modello per la pagina web ed una per i link. Si usa poi ciascun modello per etichettare le istanze ancora non etichettate. Gli esempi etichettati con maggiore confidenza da ciascun classificatore, sia positivi che negativi, vengono selezionati e aggiunti al dataset etichettato. Questo processo viene ripetuto in modo iterativo, addestrando i classificatori sul dataset etichettato espanso ed etichettando ulteriori dati non etichettati, fino a esaurire l'insieme di dati non etichettati o a raggiungere un criterio di arresto.

Si parla di co-training perché ogni classificatore lavora con le istanze etichettate dall’altro classificatore. L'assunzione alla base è che i due classificatori, sebbene addestrati su prospettive diverse, forniscono informazioni complementari sugli esempi. Incorporando punti di vista diversi, il co-training mira a catturare aspetti diversi dei dati che potrebbero non essere catturati da un singolo classificatore. Il successo del co-training si basa su due condizioni chiave. In primo luogo, le due prospettive devono essere indipendenti ma fornire informazioni ridondanti. Ciò significa che i due classificatori non devono fare affidamento sulle stesse caratteristiche o mostrare forti correlazioni nelle loro predizioni. In secondo luogo, ciascuna prospettiva dovrebbe avere un'adeguata capacità predittiva da sola. Se una prospettiva supera costantemente l'altra, il co-training potrebbe non fornire miglioramenti significativi.

Co-EM

È possibile fondere gli approcci di EM e co-training per incrementare le prestazioni.

Nell'approccio di co-training tradizionale, vengono addestrati due classificatori indipendenti utilizzando diverse prospettive dei dati. Tuttavia, l'etichettatura dei dati non etichettati viene effettuata in modo deterministico utilizzando le predizioni dei due classificatori. Invece, l'uso dell'algoritmo EM nella procedura di co-training introduce un'etichettatura probabilistica dei dati non etichettati, consentendo una maggiore flessibilità nell'incorporare tali dati nel processo di apprendimento.

Riassunti Machine Learning 107

Co-EM dall’altro lato, addestra il classificatore A su dati etichettati e li usa per etichettare in maniera probabilistica tutti i dati non etichettati. Successivamente viene addestrato il classificatore B sia su dati etichettati che non etichettati con le etichette di tentativo del classificatore A e quindi si rietichettano in maniera probabilistica tutti i dati per poi essere usati dal classificatore A. Il processo viene iterato finché non si raggiunge la convergenza. Questo approccio sembra funzionare meglio del co-training perché non si affida alle etichette delle classi generate dal classificatore A o B ma le stima in maniera probabilistica a ogni iterazione. L'iterazione continua fino a quando il processo converge o soddisfa un criterio di arresto predefinito.

Il requisito di applicabilità di questo approccio è ancora una volta l’indipendenza delle viste multiple. Ci sono però prove che questo approccio funziona bene anche quando le viste sono scelte in maniera casuale, questo perché un classificatore co-trained è generalmente abbastanza robusto.

Il classificatore base inoltre non deve essere necessariamente quello Naïve Bayes. Il metodo co-EM viene spesso usato anche con le SVM. Affinché l’iterazione EM funzioni, è necessario che il classificatore etichetti i dati in maniera probabilistica e deve essere anche in grado di usare in maniera probabilistica le istanze pesate di training. Un modo di ottenere le stime di probabilità dalle SVM è eseguire una logistic regression. Per gestire i pesi si può invece usare l’approccio usato nella Locally Weighted Linear Regression. Nel caso delle SVM, la distanza dall’iperpiano separatore può essere vista come la probabilità di appartenenza a una classe piuttosto che a un’altra: se un punto è molto distante dall’iperpiano, allora quel campione è classificato con una forte confidenza.

Multi-instance Learning

Il multi-instance learning (apprendimento da istanze multiple) è un paradigma di apprendimento automatico in cui un'istanza è rappresentata da un insieme di sotto-istanze chiamate "bags" (sacche). A differenza dell'apprendimento tradizionale, in cui ogni istanza è etichettata individualmente, nel multi-instance learning l'etichetta è assegnata all'intera bag anziché alle singole sotto-istanze al suo interno. Può essere considerato quindi come una forma debole dell’apprendimento supervisionato.

Un primo approccio per gestire le bags è quello di passare da un problema multiistanza ad uno a singola istanza o aggregando l’input (tramite operatori di media, min, max etc.) o aggregando l’output (si propaga l’output del bag a tutte le istanze). Questo comporterà una grande perdita di informazioni poiché gli attributi vengono condensati in statistiche di riepilogo individualmente e indipendentemente. È

Riassunti