Appunti Machine Learning

CLASSIFICAZZIONE BINARIA

( )

Qui abbiamo e

= ⁽ᴰ⁾ = ( ᴰ )

Poiché, per le proprietà della funzione logistica,

Risulta

CLASSIFICAZIONE K-CLASSE

Qui abbiamo

E

Poiché

Risulta

BACKPROPAGATION

Algoritmo applicato per valutare le derivate dell’errore rispetto a tutti i pesi. Può essere interpretato come una

propagazione all’indietro del calcolo nella rete, dall’output verso le unità di input. Fornisce un metodo

efficiente per valutare le derivate rispetto ai pesi. Può essere applicato anche per calcolare le derivate

dell’output rispetto alle variabili di input, al fine di ottenere valutazioni delle matrici Jacobiana e Hessiana in

un punto dato.

Mostriamo ora che, per qualsiasi strato, conoscendo:

()

• i pesi correnti

() ()

• i valori ottenuti sottoponendo l’elemento corrente alla rete

,

la conoscenza delle derivate

rende possibile calcolare:

da usare per la discesa del gradiente

dove è il numero di unità nello strato

.

BACKPROPAGATION AL LAYER r

Qui

A, come conseguenza,

Inoltre, poiché

Risulta () ()

E poiché allora

= ℎ( ),

e

Riassumendo risulta

E per ogni layer = , … ,2

Per il primo layer,

BACKPROPAGATION E FUNZIONI DI ATTIVAZIONE

Nel caso di una funzione di attivazione sigmoide si ottiene, in particolare:

ℎ() = (),

Mentre, se si applica una funzione di attivazione ReLU, si ha:

BACKPROPAGATION

Iterare i passaggi precedenti su tutti gli elementi del batch. Infatti, poiché:

si ha: ̅ ̅

Questo fornisce una valutazione del gradiente nel punto corrente .

( )

̅

Una volta noto si può eseguire un singolo passo di discesa del gradiente:

( ),

dove η è il tasso di apprendimento.

EFFICIENZA COMPUTAZIONALE DEL BACKPROPAGATION ̅

Una singola valutazione delle derivate della funzione di errore richiede operazioni,

(| |)

Approccio alternativo: differenze finite. Un’alternativa consiste nel perturbare ciascun peso singolarmente

e approssimare la derivata come segue:

̅ ̅ 2

Questo approccio richiede operazioni per ogni peso, quindi complessive.

(| |) (| | )operazioni

PPT 13

DECISION TREE

Un albero decisionale è un classificatore espresso come una partizione ricorsiva dello spazio delle istanze.

• È composto da nodi che formano un albero radicato

• Ogni nodo interno suddivide lo spazio delle istanze in due o più sottospazi, secondo una funzione

discreta definita sui valori degli attributi

• Di solito, ogni nodo è associato a una partizione rispetto a un singolo attributo

• Ogni foglia è associata a un sottospazio e:

o a una classe, che rappresenta la previsione più appropriata per tutti i punti nel sottospazio

o oppure a un vettore di probabilità di classe

o

ALBERO DECISIONALE: CLASSIFICAZIONE

• Dato un elemento , l’albero decisionale viene percorso a partire dalla radice.

( )

= , … ,

1

• A ogni nodo attraversato, associato a una caratteristica e a una funzione , si calcola il valore

( )

per decidere quale nodo figlio considerare. Questo equivale a considerare sotto-regioni sempre più

piccole dello spazio dei dati.

Un caso importante è quando viene definita una soglia e si effettua un confronto tra e

o

per decidere quale dei due nodi figli considerare.

• La procedura si interrompe quando si raggiunge una foglia. La predizione restituita è data dalla classe

corrispondente, oppure derivata dal vettore di probabilità delle classi.

ALBERO DECISIONALE: COSTRUZIONE

Lo spazio dei dati viene partizionato ricorsivamente costruendo l’albero decisionale dalla radice alle foglie.

Ad ogni nodo, ci si pone due domande fondamentali:

1. Come effettuare la partizione della regione corrispondente? → Bisogna scegliere quale attributo

considerare e quale funzione di partizione applicare.

2. Quando interrompere la partizione? → Bisogna decidere quando fermarsi e come assegnare

l’informazione alle foglie.

ALBERO DECISIONALE: PARTIZIONAMENTO AD OGNI NODO

Si seleziona l’attributo e la funzione/soglia in modo tale che una data misura venga massimizzata all’interno

delle intersezioni del training set con ciascuna sotto-regione. Le misure di impurità di classe all’interno di un

insieme devono essere minimizzate.

MISURA DI IMPURITÀ

Data una variabile casuale con dominio discreto e corrispondenti probabilità

{ , . . . , } = ( , . . . , ),

1 1

una misura di impurità possiede le seguenti proprietà:

: →

• per ogni possibile vettore di probabilità pp

() ≥ 0

• è minima se esiste un indice ii, con 1≤i≤k1 \leq i \leq k, tale che pi=1p_i = 1

()

• è massima se pi=1/kp_i = 1/k per ogni ii

()

• per ogni p′p' ottenuto da una permutazione di pp

() = (′)

• è differenziabile ovunque

()

BONTÀ DELLA SUDDIVISIONE (GOODNESS OF SPLIT)

Nel nostro caso, si considera la classe di ciascun elemento in un insieme .

• Per qualsiasi insieme di elementi, il vettore di probabilità associato a può essere definito come:

dove è l’insieme degli elementi di appartenenti alla classe

⊆ .

ℎ

• Data una funzione si definisce cioè se e solo se

: → {1, . . . , }, = { ∈ ∣ () = }, ∈

() = .

• La bontà della suddivisione di rispetto a è data da:

cioè dalla differenza tra l’impurità di e la media delle impurità dei sottoinsiemi risultanti

dall’applicazione di

BONTÀ DELLA SUDDIVISIONE (GOODNESS OF SPLIT)

Nella pratica, la funzione viene solitamente definita considerando un singolo attributo e:

• Se l’attributo è discreto, si induce una partizione del codominio in sottoinsiemi → Un caso

particolare è la partizione tra gli elementi che hanno lo stesso valore per l’attributo considerato

• Se l’attributo è continuo, si induce una partizione del codominio in intervalli, definiti da soglie → Un

caso particolare è quando viene data una singola soglia, e ff esegue una partizione binaria degli

elementi in S

ENTROPIA E INFORMATION GAIN

• Per qualsiasi insieme S di elementi, si definisce l’entropia come:

dove è il sottoinsieme di appartenente alla classe

.

• L’entropia è:

minima (uguale a 0) se tutti gli elementi di appartengono alla stessa classe

o massima (uguale a se tutte le classi sono rappresentate in modo uniforme in

log )

o 2

• Utilizzando l’entropia come misura di impurità, la bontà della suddivisione è data dal guadagno

informativo (information gain), definito come:

cioè la diminuzione dell’entropia da alla media pesata delle entropie dei sottoinsiemi risultanti

dalla partizione indotta dalla funzione .

Indice di Gini

L’indice di Gini è spesso utilizzato come strumento per misurare la divergenza dall’uguaglianza. È definito

come:

dove è il sottoinsieme di appartenente alla classe

.

• Il guadagno di Gini rispetto a una funzione di partizione è la diminuzione dell’indice di Gini da

alla somma pesata degli indici di Gini dei sottoinsiemi :

ALTRE MISURE DI BONTÀ DELLA SUDDIVISIONE

• DKM è una misura di impurità definita per la classificazione binaria. È calcolata come:

Il guadagno DKM rispetto a una funzione di partizione è la diminuzione della misura DKM da alla

somma pesata delle DKM dei sottoinsiemi :

• Il Gain Ratio è una versione normalizzata del guadagno informativo, rispetto all’entropia originale:

ALBERO DECISIONALE: FOGLIE

Spesso, le condizioni per decidere quando interrompere la partizione sono predefinite, come:

• profondità massima dell’albero

• numero massimo di foglie

• numero minimo di elementi in una sotto-regione

Quando si raggiunge una foglia, la classe corrispondente può essere definita come la classe maggioritaria

nell’intersezione tra la sotto-regione e il training set.

POTATURA (PRUNING)

• Un arresto anticipato tende a generare alberi decisionali piccoli e sotto-adattati (underfitted)

• Uno stop troppo permissivo tende a generare alberi grandi e sovra-adattati (overfitted)

Per affrontare questo problema, si possono applicare metodi di potatura:

1. Si utilizza un criterio di arresto permissivo, lasciando che l’albero decisionale overfitti

2. L’albero sovra-adattato viene ridotto in un albero più piccolo, rimuovendo opportunamente i rami che

sembrano non contribuire all’accuratezza di generalizzazione → Diversi sottoalberi vengono fusi in

singoli nodi, riducendo così la dimensione dell’albero

PPT 14

METODI ENSEMBLE

I metodi ensemble cercano di migliorare le prestazioni combinando più modelli, in qualche modo, invece di

utilizzare un singolo modello.

• Si addestra un comitato di L modelli differenti e si effettuano le predizioni mediando le previsioni fatte

da ciascun modello su campioni del dataset (bagging)

• Si addestrano modelli diversi in sequenza: la funzione di errore utilizzata per addestrare un modello

dipende dalle prestazioni dei modelli precedenti (boosting)

BOOTSTRAP

Il bootstrap è uno strumento fondamentale di ricampionamento in statistica. L'idea di base è stimare la vera

̂

distribuzione dei dati tramite la cosiddetta distribuzione empirica .

̂

Dato un insieme di dati di addestramento con la distribuzione empirica è definita come:

( ),

, = 1, … , ,

1

Questa è semplicemente una distribuzione di probabilità discreta, che assegna peso uguale a ciascun punto

osservato nel dataset.

Un campione bootstrap di dimensione m è: ∗ ∗

( )

, = 1