Valutazione delle prestazioni degli algoritmi

Metodi di linkage

Average linkage calcola la distanza media tra tutte le coppie di istanze provenienti da cluster diversi. Fonde i cluster con la più piccola distanza media. Fornisce un equilibrio tra il collegamento singolo e il collegamento completo.

Centroid linkage calcola i centroidi, punti medi dei cluster, e fonde i cluster con i centroidi più vicini. Cerca di creare cluster con dimensioni e varianze simili.

Metodo di Ward fonde i cluster che comportano il minor aumento della varianza all'interno del cluster e il maggior aumento della varianza tra i cluster. Cerca di minimizzare la varianza all'interno di ciascun cluster e massimizzare la separazione tra i cluster.

Capitolo 5: valutazione delle prestazioni degli algoritmi

Dopo aver addestrato il sistema in modo che esso sia capace di generalizzare, dobbiamo trovare metodologie che ci permettano di valutare le prestazioni in maniera opportuna. Per i problemi di classificazione è l'error rate, ovvero la proporzione tra errori fatti rispetto al totale delle istanze del dataset. L'accuracy è definita come 1 - error rate e si parla di successo se l'istanza predetta è corretta, di errore in caso contrario.

L'error rate su training è tuttavia una misura ottimistica: classificherebbe correttamente la maggior parte delle classi a causa del fatto che il modello ha già visto i dati. Questo errore è detto resubstitution error e potrebbe accadere che sia di errore sui dati di training lo 0%, il che chiaramente non è una valutazione efficiente.

Per valutare gli errori servono nuovi gruppi di dati che il classificatore non ha mai visto: suddivido quindi il dataset in training e test, e vado a valutare le prestazioni su questo test set, che deve essere un insieme di istanze totalmente indipendenti che non hanno giocato nessun ruolo nell'apprendimento. Quindi questo test set lo uso una e una sola volta, solo quando ho terminato tutto il processo di apprendimento e quando abbiamo fissato tutti i parametri del nostro dataset.

Training e test sono separati. La prima assunzione che facciamo è che, anche se essi appartengono alla stessa distribuzione e sono rappresentativi del problema che stiamo cercando di risolvere. Tipicamente il classificatore non sarà in grado di classificare correttamente campioni che sono totalmente diversi da quelli visti in fase di training, ovvero che non appartengono alla stessa distribuzione.

Riassunti Machine Learning 31

È fondamentale, come detto, che i dati di test non siano usati in nessun modo per la creazione del classificatore né per il tuning dei parametri.

Spesso suddividiamo i dati in tre gruppi: training, test e validation. I dati di validazione sono utilizzati dal modello per scegliere gli iperparametri ed ottimizzarli in maniera opportuna. Stimati correttamente tutti i parametri, è necessario usare tutti i dati per costruire il classificatore finale. Quindi facciamo un nuovo addestramento con i valori dei parametri fissati.

Metodo hold out

Il metodo dell'hold out prende i dati e li divide in training e test. Il problema è che entrambi questi insiemi dovrebbero essere molto grandi, quindi questo metodo va bene se ho molti dati a disposizione. Infatti, più grande è il training set e migliore sarà il classificatore; più grande è il test set e migliore sarà la stima dell'errore.

Non c'è un numero magico che sia indicativo del buon funzionamento o meno di questo metodo. A noi non interessa ottenere solo una stima dell'errore, ma anche individuare quanto quella stima è vicina all'errore reale, ottenendo quelli che sono gli intervalli di confidenza. In genere poi consideriamo ogni classificazione come un evento a sé stante, indipendente dalle altre.

Intervalli di confidenza

Supponiamo che un classificatore sui dati di test ha il 25% di error rate, quindi il 75% di accuracy. Bisogna capire come cambia questa stima rispetto al numero di campioni utilizzati nel test. In statistica una successione di eventi indipendenti è chiamata processo di Bernoulli.

Questo concetto si basa su una successione di eventi indipendenti che possono avere successo o fallire, come ad esempio il lancio di una moneta. In questo caso, si considera ogni lancio della moneta come un evento indipendente che può avere successo (testa) o fallimento (croce). Se la moneta è truccata e non conosciamo la probabilità di successo (testa), possiamo stimare la probabilità di successo effettuando un certo numero di lanci.

Ad esempio, se lanciamo la moneta 100 volte e 75 volte otteniamo testa, possiamo dire che la percentuale di successo stimata è del 75%. Tuttavia, ci si chiede quanto siamo sicuri che la percentuale di successo sulla popolazione di riferimento sia effettivamente del 75%. Per rispondere a questa domanda si può utilizzare un intervallo di confidenza.

L'intervallo di confidenza indica l'intervallo di valori entro cui ci aspettiamo che si trovi il valore effettivo della percentuale di successo sulla popolazione di riferimento con una certa probabilità. Ad esempio, se abbiamo 750 successi su 1000 lanci della moneta, l'intervallo di confidenza dell'80% indica che la percentuale di successo effettiva sulla popolazione di riferimento dovrebbe essere compresa tra il 73,2% e il 76,7%.

Riassunti Machine Learning 32

In altre parole, abbiamo una probabilità dell'80% che la percentuale di successo sulla popolazione di riferimento si trovi in questo intervallo. Tuttavia, se abbiamo solo 75 successi su 100 lanci della moneta, l'intervallo di confidenza dell'80% è più ampio e va dal 69,1% all'80,1%. Questo è dovuto al fatto che la stima della percentuale di successo sulla popolazione di riferimento diventa meno accurata quando abbiamo meno dati a disposizione.

In generale possiamo dire che la stima della percentuale di successo su un insieme di test ci fornisce solo un'indicazione approssimativa della percentuale di successo sulla popolazione di riferimento. Per avere una stima più accurata, dobbiamo considerare la dimensione dell'insieme di test e utilizzare un intervallo di confidenza per stimare la probabilità effettiva di successo sulla popolazione di riferimento.

La media di un processo di Bernoulli è p, mentre la varianza è p(1-p). L'accuracy attesa di f è S/N, dove S è l'insieme di istanze classificate correttamente e N il numero di elementi dell'insieme. La media di f è sempre p, mentre la varianza è p(1-p)/N. Per valori elevati di N, N 100, la distribuzione di questa variabile casuale tende a una distribuzione normale.

Quindi, in questo caso l'intervallo di confidenza percentuale per la variabile aleatoria casuale x viene calcolato come:

Il vantaggio è che posso usare dei valori tabellati che mi dicono qual è la probabilità di avere X ≥ z per un determinato z. Queste tabelle fanno riferimento solo a una delle due code della distribuzione, quindi devo duplicare il valore.

Quindi Pr[X ≥ 1.65] = 5% implica che c'è il 5% di probabilità che X si trovi oltre 1.65. Per quanto detto prima poi, poiché la distribuzione è simmetrica, la probabilità che X si trovi oltre 1.65 oppure in maniera equivalente è del 10%.

Bisogna ora ridurre la variabile f ad avere media nulla e varianza unitaria, sottraendo la media p e dividendo per la deviazione standard:

Riassunti Machine Learning 33

Dato un certo intervallo di confidenza c si trova z dalle tabelle. Per utilizzare la tabella si sottrae c da 1 e così otteniamo il risultato: ad esempio, se c = 90% si utilizza nella tabella quella al 5%. Risolvendo l'equazione rispetto a p, che rappresenta proprio l'intervallo di confidenza:

con:

nel primo caso ci dà una probabilità [0.732,0.767], nel secondo [0.691,0.801].

Cross validation

Come visto, dato un singolo dataset, lo divide in una parte di test e una parte di training dopo una fase di shuffling. Generalmente non si divide il dataset in due parti uguali, ma si riserva 1/3 per il testing e i 2/3 per il training. Questo perché il 50% per il training potrebbe essere troppo poco.

Un problema che potremmo avere, soprattutto nel caso in cui abbiamo molteplici classi, è che una classe non è presente nei dati di training. Per evitare sbilanciamenti, cioè per evitare che il numero di campioni che appartengono alle varie classi nel training sia diverso dalla loro distribu