Appunti del corso di Machine Learning

CONSIDERAZIONI FINALI

Alla fine, possiamo dire che: (Θ)

() (+1)

=

( )

Θ ji

()

.

Dove è l’errore del nodo nello strato

ALGORITMO DI BACKPROPAGATION

L’ algoritmo di backpropagation è uno dei meccanismi più usati per allenare le reti neurali. Infatti,

permette di calcolare il gradiente degli errori rispetto ai pesi della rete, in modo da aggiornare il

loro valore e cercare di minimizzare l’errore complessivo della rete.

(1) (1) () ()

{( , ), … , ( , )},

Dato un training set dobbiamo seguire le seguenti fasi:

()

∆ = 0 , , ;

1. Sia per tutti le

2. Eseguire le seguenti operazioni:

(1)

➢ =

Fissare ()

➢ = 2, … ,

Forward propagation per calcolare tutte le , dove

() () () (−1) (2)

➢ = − , … ,

Calcolare , e tutti gli altri

() () () (+1)

➢ ∆ ≔ ∆ +

Calcolare

3. Alla fine, definiamo: 1 1

() () ( ) () ()

= ∆ + = ∆

Θ ≠ 0 = 0

ji

INIZIALIZZAZIONE

Per la prima iterazione dell'algoritmo dovremmo impostare i pesi Θ. Se li impostiamo tutti a 0, tutti

(Θ) (Θ)

(2) (2) (2) (2) (1) (1)

= = = Θ = Θ

i parametri saranno uguali: , , and .

⁄ ⁄

(1) (1)

1 2 1 2 01 02

Θ Θ

01 02

Quindi, ogni aggiornamento comporterà lo stesso parametro. Per risolvere il problema

() [−, ]

Θ ∈ +

dell'inizializzazione a zero, impostiamo i pesi all'interno di un piccolo intervallo .

ji

Questo metodo è chiamato inizializzazione casuale. Per evitare che i gradienti delle attivazioni

della rete svaniscano o esplodano, ci atterremo alle seguenti regole:

• La media delle attivazioni deve essere zero.

• La varianza delle attivazioni dovrebbe rimanere la stessa in ogni livello.

Una possibile soluzione può essere quella di selezionare i valori rispetto a una distribuzione di

probabilità, come normale standard, uniforme o Xavier.

FUNZIONI DI ATTIVAZIONE ALBERI

ALBERI DI REGRESSIONE

Gli alberi di regressione sono un tipo di algoritmo di machine learning che non si limitano alle

relazioni lineari, perché segmentano i dati in sottoinsiemi distinti e ne calcolano un valore medio.

Questo permette agli alberi di catturare relazioni complesse tra le variabili in modo non lineare,

rendendoli ideali per situazioni in cui la relazione input-output è complessa o non facilmente

modellabile con una linea retta. Inoltre, gli alberi di regressione: sono intuitivi e facilmente

interpretabili, non necessitano di normalizzazione, ma sono sensibili a piccole variazioni nei dati.

RESIDUAL SUM OF SQUARES (RSS o SSR)

Per capire quanto bene l'albero si adatta ai dati, si usa una misura chiamata Residual Sum of

Squares (RSS), ovvero la somma dei quadrati delle differenze tra i valori reali e quelli predetti. È

2

=1 () ()

∑

= (ℎ( ) − )

definito dalla formula: . Più piccolo è l'RSS, migliore è l'adattamento

dell'albero di regressione ai dati.

COSTRUZIONE DELL’ALBERO

Per costruire un albero di regressione, si seguono i seguenti passaggi:

1. Identificazione del miglior split: per ogni feature, bisogna scegliere

come dividere il dataset in sottoinsiemi. Bisogna evitare divisioni

troppo piccole, per evitare overfitting.

2. Prima divisione del dataset: si separa il dataset in due sottoinsiemi in

base allo split ottimale trovato. Si calcola il RSS composto dalla

somma dei quadrati dei residui della parte di sinistra e di destra.

3. Calcolo del RSS e ripetizione della divisione: si ripete

l’operazione precedente, ma eseguendo una divisione che

aumenta il numero di sample di uno, nella parte di sinistra.

4. Creazione del grafico di RSS: di volta in volta, registriamo il

valore di RSS in un grafico e quello con il valore minimo,

diventa il nodo radice dell’albero

5. Interruzione del processo: si smette di dividere quando si raggiunge un certo criterio di stop,

come un numero minimo di osservazioni per nodo foglia o una soglia minima di RSS. RSS.

In caso di più feature, l'albero si ottiene organizzando le feature in ordine decrescente di

POTATURA

La potatura (pruning) è una tecnica applicata agli alberi di regressione per ridurne la complessità e

migliorare la capacità di generalizzazione sui dati nuovi. Interviene eliminando i rami meno

significativi per ottenere un albero più semplice e robusto. Solitamente si effettua la potatura del

nodo più debole, in cui si calcola il punteggio di ogni tipo di albero (dal più complesso al più

semplice) in base al compromesso tra errore di previsione (SSR) e penalizzazione della

= +

complessità. In tal caso, si sceglierà quello con più basso, dove è la

).

dimensione dell’albero e è un parametro di penalizzazione (“simile” a

ALBERI DI CLASSIFICAZIONE

Gli alberi di classificazione sono algoritmi utilizzati per classificare i dati in categorie discrete. A

differenza di quelli di regressione, dividono il dataset in modo da assegnare ogni elemento a una

classe specifica. La complessità di un albero di classificazione dipende dal numero di attributi (o

feature) disponibili nel dataset. Infatti, il numero di alberi possibili cresce con il numero di attributi,

poiché per ogni attributo si possono generare combinazioni diverse (spazio delle ipotesi).

L’ENTROPIA

L’entropia è una misura dell'incertezza associata alla variabilità delle classi in un nodo. Attraverso la

sua valutazione, è possibile capire quanto è informativo un valore. Dati eventi, avremo bisogno di

log = − log 1/ 1/

bit per rappresentarli. Osserviamo che è la probabilità dell’evento in caso

2 2

di distribuzione uniforme. Quindi, in generale, l’entropia è definita come:

1 1 1

− log = − ∑ log = − ∑ log

2 2 2

Nel caso in cui abbiamo bassa entropia, avremo un nodo con classi omogenee (nodo puro);

altrimenti avremo una maggiore eterogeneità e quindi maggiore incertezza.

INFORMATION GAIN

Il guadagno d'informazione misura la riduzione di entropia ottenuta scegliendo un particolare

attributo per dividere il dataset. La formula generale per calcolare il guadagno di informazione è:

+

() = ( , ) − () = ( , )−∑ ( , )

+ + + + + + +

COSTRUZIONE DELL’ALBERO DECISIONALE

Per costruire un albero di classificazione, si seguono questi passaggi:

1. Scelta del nodo radice in base a quanto le feature sono informative. In altre parole, si sceglie

quello con information gain maggiore. Per esempio, in questo caso, Patrons è migliore di Type.

2. Dividere in base a ogni attributo: si calcola l’entropia delle sotto-partizioni e si prende quello

con information gain maggiore. Sulla sotto-partizione scelta, si posizione il nodo decisionale.

3. Eseguire i primi due punti in modo iterativo per ottenere i successivi nodi decisionali.

VALORI CATEGORICI E NUMERICI

Nel caso in cui abbiamo sia valori categorici che numerici, dobbiamo seguire i seguenti passi:

1. Ordinare le righe in ordine crescente

2. Calcola la media tra tutte le righe adiacenti

3. Calcola il guadagno di informazioni per tutte le possibili opzioni binarie e considera quello con il

massimo guadagno come rappresentativo delle feature

4. Confronta il guadagno di informazioni per tutte le feature e seleziona quella con il valore più

alto.

5. Continua fino a quando non costruisci l'intero albero.

VALORI MANCANTI

VALORI CATEGORICI VALORI CONTINUI

1. Aggiungi il valore più frequente Possiamo usare un altro valore continuo e

2. Trova una funzione correlata e usala come calcolare una regressione lineare per trovare il

linea guida valore

RANDOM FOREST

Le random forest sono una "contromisura" per l'imprecisione generata dagli alberi decisionali

poiché funzionano bene sui dati che li generano. L'idea delle random forest è quella di combinare

la semplicità degli alberi decisionali aggiungendo flessibilità al modello con conseguente

miglioramento della precisione.

COSTRUZIONE DELLE RANDOM FOREST

1. Generare un set di dati bootstrap:

supponiamo di partire da un set di dati di

una data dimensione, per creare la

versione bootstrap del nostro set di dati

selezioniamo casualmente campioni

(sample) dal set di dati originale

permettendo di prelevare lo stesso

campione più volte

2. Creare un albero decisionale basato sul set

di dati bootstrap: utilizzeremo un

sottoinsieme casuale di variabili (colonne)

ad ogni passaggio. Per continuare questo

albero, selezioniamo casualmente altre

due colonne

3. Continua a costruire l'albero con la

stessa idea di selezione casuale delle

caratteristiche

4. Torna al primo passaggio e genera nuovi

alberi

Il numero di alberi che possiamo generare varia a seconda dello scenario (dimensione del set di

dati, ecc.) ma, in generale, questo processo viene eseguito centinaia di volte.

CLASSIFICARE UN NUOVO CAMPIONE Definiamo il bagging come l'azione di

bootstrap dei dati e di aggregazione tra

loro per prendere una decisione. Una

random forest è utile per classificare un

nuovo campione. Questo avviene, eseguendo il campione in ogni albero decisionale della random

forest e, dopo aver ottenuto i dati, si prende l'output più comune.

VALUTAZIONE DELL'ACCURATEZZA

I campioni non considerati creano il set di dati out-of-bag. Poiché i

campioni all'interno di questo set non sono stati considerati

durante l'addestramento, possono essere utilizzati per valutare

l'errore. Quindi, per ogni albero, si può valutare l'errore di

classificazione e restituire la percentuale di campioni classificati in

modo errato nei set di dati out-of-bag.

VALORI MANCANTI SUL DATASET ORIGINALE

In caso di valori mancanti nel dataset originale, bisogna seguire alcuni passi:

• Stima iniziale dei v