Appunti esame Machine Learning – Modelli Instance-Based, SVM e Kernel

Backtracking e pruning

Backtracking e viene scelto il nodo 5 per l’espansione. Raggiunto il passo c, si vede che il nodo 5 ha tutti i figli espansi in foglie e questo avvia il pruning. Viene quindi valutato e accettato il rimpiazzamento del sottoalbero per il nodo 5 giungendo al passo d. Si considera quindi il nodo 3 per il rimpiazzamento e anche questa operazione viene accettata. Si continua con il backtracking e il nodo 4, che ha entropia più bassa del nodo 2, viene espanso nelle sue due foglie. Viene considerato il rimpiazzamento del sottoalbero per il nodo 4 ma supponiamo che esso non venga rimpiazzato. A questo punto il processo termina con l’albero parziale con tre foglie mostrato in figura e.

Quindi PART trasforma in regole le foglie che hanno la massima coverage. Tratta i valori mancanti come C4.5 splittando le istanze con valori mancanti in pezzi.

Tempo per generare una regola

• Nel caso peggiore, il tempo è lo stesso di quello impiegato per costruire un albero C4.5 potato e si verifica quando i dati sono rumorosi e si fa molto pruning.
• Nel caso migliore, il tempo è lo stesso di quello impiegato per costruire una singola regola if-then usando la strategia usata da PRISM. Si verifica quando i dati non sono rumorosi e non c’è bisogno di fare pruning.

Capitolo 7 - Estensione dei modelli lineari

L’apprendimento instance based ha una serie di problemi. In primo luogo risultano molto lenti per dati di training grossi poiché per calcolare le funzioni distanza si deve cercare in tutto il dataset. In secondo luogo è molto sensibile ai dati rumorosi: se in una zona in cui ci sono tutti campioni di una classe ho un’istanza singola di un’altra classe potrei avere una classificazione localmente non corretta.

Un possibile rimedio è usare invece di un solo vicino, k vicini (K-Nearest-Neighbor) oppure rimuovere le istanze rumorose. Terzo, tutti gli attributi nel calcolo della distanza assumono la stessa importanza nella formula. Infine non fornisce una esplicita generalizzazione, si memorizzano semplicemente tutti i campioni del set.

Per velocizzare la classificazione e combattere il rumore sono stati proposti una serie di classificatori che risolvono attraverso varie versioni i problemi precedenti. In primo luogo si può pensare che non è necessario memorizzare tutte le istanze del classificatore per classificare le nuove istanze.

IB2

La variante che utilizza IB2 è quella in cui si memorizzano solamente le istanze erroneamente, eliminando quelle classificate correttamente per ridurre il numero di esempi ridondanti. Per ogni regione così dello spazio dell’istanza conservo quelle che non vengono classificate correttamente, le aggiungo al reference set e quindi vado a coprire una zona di spazio che non era coperta in precedenza.

Questo metodo funziona bene se non ci sono esempi rumorosi, altrimenti gli esempi meno utili vengono accumulati nel set di esempi salvati. Tuttavia, questo metodo rappresenta solo un passo intermedio verso algoritmi di apprendimento più efficaci basati sugli esempi.

IB3

I dati rumorosi quindi abbassano inevitabilmente le performance del classificatore, IB3 propone una soluzione che si basa sulle performance delle singole istanze che verranno conservate oppure scartate a seconda del comportamento. Questo viene effettuato tenendo traccia del numero di classificazioni corrette o errate di ogni esempio.

Innanzitutto si analizza il success rate della singola istanza settando sue soglie, quando il SR scende troppo si elimina l’istanza mentre se sale oltre il limite massimo entra a far parte dei riferimenti per classificare le nuove istanze.

Se le sue prestazioni si trovano tra i due limiti, non viene utilizzato per la previsione ma, ogni volta che è il vicino più vicino alla nuova istanza, e quindi sarebbe stato utilizzato per la previsione se il suo record di prestazioni fosse stato abbastanza buono, le sue statistiche di successo vengono aggiornate come se fosse stato utilizzato per classificare quella nuova istanza.

Per attuare questo, vengono utilizzati i limiti di confidenza sulla probabilità di successo di un processo di Bernoulli, considerando Si successi sul numero di istanze totali N si calcola il success rate p. Se diamo un livello di confidenza del 5% ad esempio possiamo calcolare i limiti inferiore e superiore sapendo che al 95% p appartenga all’intervallo. Per l’algoritmo IB3 il livello di confidenza è il 5% per l’accettazione dell’istanza ed il 12% per il rifiuto.

IB4

L’ultimo problema è che gli attributi hanno lo stesso peso, per questo motivo IB4 utilizza un sistema di pesi modificandoli dinamicamente nel calcolo della funzione distanza. I pesi possono essere o generali per il problema o specifici per ogni classe. Di solito si utilizza la funzione di distanza euclidea pesata:

Dove xi è l’istanza del training set che sto considerando, yi è il campione da classificare e wi sono i pesi. Per scegliere i pesi ragiono nel seguente modo: se la classificazione è corretta incremento il peso, se non è corretta decremento il peso. Il valore dell’incremento o del decremento è proporzionale per l’iesimo attributo alla differenza |xi-yi|.

Generalizzazione con iper-rettangoli

Rimuovendo le istanze rumorose e ridondanti permette di fare capire meglio al modello la struttura dei dati. Per migliorare l’interpretazione c’è bisogno di aumentare la generalizzazione. Per generalizzare il comportamento di un classificatore nearest-neighbor è utilizzare un approccio rule-based che va a considerare un insieme di iper-rettangoli, quando una nuova istanza viene classificata correttamente, viene generalizzata unendola con quelle più vicine nello stesso iper-rettangolo della stessa classe.

L'iper-rettangolo più vicino può essere una singola istanza o un iper-rettangolo. Nel primo caso, viene creato un nuovo iper-rettangolo che copre l'istanza vecchia e quella nuova. Nel secondo caso, l'iper-rettangolo viene ingrandito per comprendere la nuova istanza. Infine, se la previsione è errata e l'iper-rettangolo è responsabile della previsione errata, i confini dell'iper-rettangolo vengono modificati in modo che eviti la nuova istanza.

Si può decidere a priori di evitare la sovregeneralizzazione impedendo la sovrapposizione degli iper-rettangoli. Inoltre, si vede che gli iper-rettangoli sovrapposti sono esattamente analoghi alle situazioni in cui lo stesso esempio è coperto da due o più regole in un insieme di regole.

Con il metodo degli iper-rettangoli si necessita che un cambiamento concettuale del calcolo della distanza. La distanza tra un’istanza e un iper-rettangolo è pari a zero se il punto che rappresenta l’istanza si trova all’interno dell’iper-rettangolo. Per calcolare la distanza tra un punto esterno all’iper-rettangolo e l’iper-rettangolo stesso si potrebbe scegliere l’istanza più vicina all’interno dell’iper-rettangolo e misurare la distanza tra il punto esterno e questo punto. Sarebbe tuttavia meglio considerare la distanza tra il punto esterno e il lato più vicino dell’iper-rettangolo per evitare dipendenze da alcune singole istanze.

In figura sono mostrati i confini impliciti che sono formati tra due classi rettangolari nel caso in cui come metrica di distanza si utilizzi proprio la distanza tra un’istanza ed il punto più vicino di un lato del rettangolo.

Vediamo che sono state create delle zone: ad esempio la zona 1 comprende quei punti che non incontrano i prolungamenti di entrambi i rettangoli, mentre la zona 2 comprende i punti che incontrano i prolungamenti del primo rettangolo e non del secondo, la zona 3 invece comprende i punti che incontrano i prolungamenti inferiori del primo rettangolo e del lato sinistro del secondo rettangolo; la zona 4 comprende i punti che incontrano il prolungamento sinistro del secondo rettangolo, ma non incontrano i prolungamenti del primo etc. etc.

Per verificare se un nuovo punto appartiene alla prima o alla seconda classe devo considerare la distanza dai rettangoli, ovviamente vado a considerare la distanza dai lati più vicini. Ad esempio, se considero un punto della zona 3, devo confrontare la distanza con il lato inferiore del primo rettangolo e la distanza con il lato sinistro del secondo. Come si nota, calcolando una distanza tra oggetti, rettangoli in questo caso, la forma della regione di decisione non è più semplicemente una spezzata ma viene generalizzata e può essere anche parabolica.

Un altro problema da considerare si ha quando dobbiamo misurare la distanza nel caso di iper-rettangoli che sono sovrapposti o innestati: in questo caso un’istanza può appartenere a più classi. Si preferisce una euristica: si considera per quella istanza l’iper-rettangolo più specifico che la contiene, ad esempio quello che copre area minore.

K* similarity

Una soluzione per generalizzarla è quella di considerare la trasformazione di una istanza in un'altra attraverso una serie di operazioni elementari predefinite e di calcolare la probabilità di occorrenza della sequenza usata, nel caso in cui le operazioni che la costituiscono siano scelte in modo casuale. La robustezza viene migliorata se vengono considerati tutti i possibili percorsi di trasformazione, ponderati dalle loro probabilità.

In questo modo, il metodo generalizza naturalmente al problema di calcolare la distanza tra un'istanza e un insieme di altre istanze, considerando le trasformazioni a tutte le istanze dell'insieme. Si definisce quindi la K* similarity, la probabilità di trasformare un’istanza A nell’istanza B. Il criterio è sempre lo stesso: si calcola la distanza di un’istanza da un set di istanze, mediante le trasformazioni, e si sceglie la classe dell’istanza più vicina che corrisponde a quella in cui l’istanza nuova viene trasformata con maggior probabilità. In questo modo possiamo gestire sia attributi numerici che nominali.

Estensione dei modelli lineari - SVM

I modelli lineari semplici mostrano grandi problemi quando i limiti delle classi da rappresentare sono non lineari, per risolvere questo si può ricorrere alle Support Vector Machine.

Nel caso di dati linearmente separabili, una SVM si comporta come un classificatore lineare ottimizzato che tende a massimizzare la capacità di generalizzazione della rete stessa. Questo viene ottenuto attraverso un processo di massimizzazione del margine che prevede di riformulare il problema dell’apprendimento come un problema di ottimizzazione vincolata. Trovo quindi la soluzione ottima che è quella che massimizza questo margine e ottengo quindi la migliore capacità di generalizzazione.

L’idea di base è quella di spostare il problema non lineare non risolubile in uno spazio, in un altro spazio a più dimensioni. Applicandolo ad un modello lineare semplice possiamo sempre trasformare uno spazio a due dimensioni in uno a più dimensioni utilizzando ad esempio il prodotto di n fattori che può essere costruito da questi attributi. Il modello lineare si traduce in:

In questo caso abbiamo ottenuto 4 differenti attributi di cui dobbiamo trovarne i relativi pesi. Il problema di questo approccio sorge quando si ha un grande numero di coefficienti poiché nella trasformazione il numero di attributi cresce esponenzialmente. Questo inoltre aumenta l’overfitting.

Le support vector machine riescono a gestire entrambi i problemi. Queste sono basate su un algoritmo che trova un particolare tipo di modello lineare: l’iperpiano a massimo margine. Consideriamo un problema linearmente separabile, esiste sempre un iperpiano che permette di dividere le classi e classificare le istanze correttamente.

Le SVM tra tutte le possibili soluzioni del problema, scelgono quella che massimizza il margine, ovvero la distanza minima tra i punti delle due classi nel training set dall’iperpiano individuato. In altre parole, cerchiamo una soluzione in cui l’iperpiano si trovi alla stessa distanza rispetto ai campioni più vicini delle due classi e questa distanza deve essere la massima possibile.

Le istanze più vicine all’iperpiano si dicono support vector. La classificazione dipende solo dalla posizione di questi campioni. Tutte le altre istanze sono irrilevanti perché, definito il margine e le istanze più vicine a esso, mi basta solo la posizione dei support vector per definire l’equazione del piano. Quindi posso trascurare anche nuovi campioni aggiunti al training set che non sono più vicini al margine rispetto ai support vector.

Scegliendo l’iperpiano con massimo margine non stiamo facendo altro che massimizzare la capacità di generalizzazione della rete perché il piano si pone esattamente alla stessa distanza tra le istanze più vicine delle due classi e quindi sono abbastanza robusto rispetto a punti che potrebbero essere distribuiti in maniera più anomala rispetto agli altri e che quindi con un altro tipo di iperpiano potrebbero essere misclassificati.

Consideriamo un problema di classificazione binaria, l’equazione di base dell’iperpiano è: Con a1 ed a2 gli attributi e wi i pesi da imparare. L’equazione dell’iperpiano può essere scritta in un altro modo, attraverso i vettori di supporto. Il valore della classe y può essere 1 o -1 a seconda se l’istanza appartiene alla classe.

L’iperpiano a massimo margine si scrive: yi è il valore della classe dell’istanza di training a(i), b ed ai sono dei parametri numerici determinati dall’algoritmo, a invece è l’istanza di test da classificare. a ed a(i) sono due vettori, il vettore a è quello dell’istanza con a1 ed a2 mentre a(i) sono i vettori di supporto. Il prodotto tra i due vettori è un prodotto vettoriale quindi la somma dei prodotti delle componenti. Infine a e b sono dei semplici parametri come i pesi del modello lineare. Nel caso lineare r