MACHINE LEARNING PDF

STATISTICA TRADIZIONALE: interpreta i dati con un modello dotato di una variabile target, che è spiegata da variabili esplicative, le quali hanno dei coefficienti che ne valutano l’impatto. Il suo limito sta nel fatto che è verification-driven, cioè l’utente formula ipotesi da verificare con il mode...

STATISTICA TRADIZIONALE: interpreta i dati con un modello dotato di una variabile target, che è spiegata da variabili esplicative, le quali hanno dei coefficienti che ne valutano l’impatto. Il suo limito sta nel fatto che è verification-driven, cioè l’utente formula ipotesi da verificare con il modello, dove y è in funzione di f(x)+ε. DM e ML sono discipline computerizzate capaci di ottimizzare la fase di analisi esplorativa dei dati (DM) e di trovare informazioni utili (ML) da grandi quantità di dati, al fine di migliorare i processi decisionali. I database sono sempre più grandi e la maggior parte dei dati finisce per non essere mai analizzata. (confronto tra DM e ML). MACHINE LEARNING: discovery-driven, cioè usa metodi computazionali per apprendere le informazioni dai dati senza basarsi su un’equazione predeterminata come modello. i modelli di ML possono migliorare in modo adattivo le loro prestazioni, man mano che aumenta il numero di campioni disponibili. Definizioni del prof: il processo che impiega una o più tecniche di apprendimento computerizzate per analizzare automaticamente ed estrarre le conoscenze dai dati contenuti in un database; processo di esplorazione e analisi, automatico o semiautomatico, di un’ampia mole di dati al fine di scoprire regole e modelli significativi; processo che, a partire dai dati forniti dal Data Warehouse (archivio centrale di dati), produce informazioni potenzialmente utili utilizzando tecniche avanzate di esplorazione e modellazione (definizione più ingegneristica) si distinguono nel ML due tipi di apprendimento: - NON SUPERVISIONATO (clustering): cioè raggruppa e interpreta i dati basandosi solo su dati di input - SUPERVISIONATO (classificazione per qualitativi, e regressione per quantitativi): sviluppa modelli predittivi basandosi sia su dati di input che di output. Data mining e machine learning ricoprono un ruolo fondamentale nella KDD, cioè Knowledge Discovery in Database=processo non banale di identificazione di pattern nei dati che siano validi nel tempo, nuovi (cioè non devono essere precedentemente noti), potenzialmente utili e comprensibili per l’uomo. Il KDD è un processo iterativo in cui le misure di valutazione possono essere migliorate, l'estrazione può essere raffinata, nuovi dati possono essere integrati e trasformati per ottenere risultati diversi e più appropriati. 1. Data cleaning: pulizia dei dati rumorosi e irrilevanti dalla raccolta e di dati mancanti con strumenti di rilevamento delle discrepanze e di trasformazione dei dati. 2. Data Integration: L'integrazione dei dati è definita come la combinazione di dati eterogenei provenienti da più fonti in una fonte comune (DataWarehouse). Può essere fatta mediante strumenti di migrazione o di sincronizzazione dei dati o mediante il processo ETL (Extract-Load-Transformation). 3. Data Selection: processo in cui si decidono ed estraggono dal Data Warehouse i dati rilevanti per l'analisi e si riduce la dimensionalità dei dati. La si può fare con dei modelli. 4. Data Transformation: processo di trasformazione dei dati nella forma appropriata richiesta dalla procedura di estrazione. È un processo in due fasi: - Mappatura dei dati: Assegnazione di elementi dalla base di origine alla destinazione per catturare le trasformazioni. - Generazione del codice: Creazione del programma di trasformazione vero e proprio. 5. Data Mining: tecniche intelligenti applicate per estrarre modelli potenzialmente utili. - Trasforma i dati rilevanti per l'attività in modelli/patterns. 1  - Decide lo scopo del modello utilizzando la classificazione o la caratterizzazione. 6. Valutazione dei modelli/pattern: l'identificazione di modelli strettamente crescenti che rappresentano la conoscenza in base a misure date. Utilizza la sintesi (rimozione di pattern ridondanti) e la visualizzazione per rendere i dati comprensibili all'utente. 7. Rappresentazione della conoscenza: tecnica che utilizza strumenti di visualizzazione per rappresentare i risultati del data mining. Genera reports, tabelle, regole discriminanti, regole di classificazione, regole di caratterizzazione, ecc. Finalità dei metodi di apprendimento statistici e dei modelli - Previsione: se si parla di un evento futuro o di qualcosa che può essere verificato esplicitamente nel "corso naturale delle cose” - Inferenza: teoria formata da un'analisi implicita basata su prove e indizi Step machine learning: 1. Costruzione di modelli. È fondamentale controllare se il dataset è rappresentativo del contesto in esame e fare eventuali aggiustamenti. 2. Assesment: scegliere la complessità ottimale e confrontare le prestazioni classificatorie dei modelli, ad esempio l’overfitting con la cross validation. Esempio di modello lineare, dove i valori usati per la regolazione/training sono m e b. Si decide che M è il modello vincente se, usando metriche di validazione di modelli, si stabilisce che il suo adattamento/errore è soddisfacente. 3. Validazione: Valutare le prestazioni classificative del modello M, testando il nostro modello con dati che non sono mai stati utilizzati per l'addestramento ma che fanno parte del dataset. I risultati sono rappresentativo di come il modello potrebbe funzionare nel mondo reale. Le considerazioni da fare in questa fase dell'addestramento sono molte ed è importante definire cosa rende un modello "sufficientemente buono"; se si vuole migliorare il modello si può tornare indietro e regolare i parametri. La regolazione è un processo sperimentale che dipende fortemente dal dataset e dal modello. 4. Previsione/Score: si utilizza il modello M trovato sul training per effettuare lo score di nuovi casi (classificazione/ previsione), su altri dati mai visti, ovvero il dataset di score. 1 TEORIA DEI MODELLI CLASSIFICATIVI, FOCUS SU OGNI TIPO DI MODELLO. Come si fa a capire la reale distribuzione dei dati? Possiamo dire che il vero modello è f(X); il target Y deve cercare di avvicinarvisi il più possibile e per questo si assume che y sia generato da f(X)+ε, 2 dove X è in input e ε, errore stocastico indipendente da X, deve essere minore possibile. Tuttavia il vero modello f(X) rimane sconosciuto e bisogna quindi stimarlo: lo si fa attraverso 𝑓̂(𝑋) che sarà uguale a 𝑌̂, previsione di Y, cercando ovviamente di minimizzare l’errore. Occorre un modo per misurare quanto bene le previsioni di un modello siano accurate: per farlo bisogna valutare quanto i dati di un metodo di apprendimento statistico corrispondano effettivamente ai dati osservati (di training). Nel campo della regressione la misura più usata è 𝟏 𝟐 l’MSE: 𝑴𝑺𝑬 = ∑𝒏𝒊=𝟏(𝒚𝒊 − 𝒇̂(𝒙𝒊 )) = 𝒃𝒊𝒂𝒔𝟐 + 𝝈𝟐 che deve tendere a 0. 𝒏 Supponiamo di voler adattare il nostro modello sulle osservazioni di training {(x1, y1),…,(xn, yn)} per poi ottenere la stima di 𝑓̂. Possiamo calcolare 𝑓̂(𝑥1 ), … , 𝑓̂(𝑥𝑛 ): se sono quasi uguali a y1, yn allora l’MSE di training è piccolo. Tuttavia non ci interessa che 𝑓̂(𝑥𝑖 ) ≈ 𝑦𝑖 , ma vogliamo che 𝑓̂(𝑥0 ) ≈ 𝑦0 , dove (x0, y0) è una osservazione di test non vista precedentemente né usata nel training. Infatti, nel primo caso il modello si concentrerebbe troppo nel cercare patterns tra i dati di training e potrebbe trovarne alcuni causati dal caso, e non da vere proprietà della funzione sconosciuta f: così si ha overfitting. Bisogna anche tenere in considerazione che l’errore stocastico deve essere minore possibile, poiché se aumenta allora aumenta anche la parte non spiegata di un modello. L’obiettivo sarà minimizzare l’errore medio di previsione su tutto il dataset di test (e non di training), cioè Expected Prediction Error: differenza tra il valore atteso del modello su tutto il dataset. Assumiamo di costruire un predittore/modello 𝑓̂(x) per stimare f(x) dove y=f(x)+ε. 2 2 𝐸𝑃𝐸(𝑥) = 𝐸(𝑦 − 𝑦̂)2 = 𝐸[𝑓(𝑥) + 𝜀 − 𝑓̂(𝑥)] = [𝑓(𝑥) − 𝑓̂(𝑥)] + 𝑉𝑎𝑟(𝜀) 2 Formula del prof: 𝐸𝑃𝐸(𝑥) = 𝐸(𝑦 − 𝑔̂(𝑥)) = 𝐸[𝑓(𝑥) + 𝜀 − 𝑔̂(𝑥)]2 ± 𝐸(𝑔̂(𝑥)) Decomposizione e compromesso di bias-varianza di un classificatore/modello. Con 𝐸(𝑔̂(𝑥)) media delle previsioni su tutto il dataset, l’EPE si decompone in tre parti Errore irriducibile=noise (varianza degli errori), sconosciuta. Fornirà sempre un limite superiore all'accuratezza della nostra previsione per Y. Errore riducibile: bias2+varianza, da minimizzare o Bias del modello: descrive quanto il modello medio fittato su tutto il dataset 𝐸(𝑔̂(𝑥)) si discosta dal valore della funzione vera f(x), cioè è la media dell’errore, e quindi Bias2 = errori al quadrato. o Varianza del modello: misura quanto un singolo modello 𝑔̂𝑗 (𝑥) si discosta dal modello medio sui dataset 𝐸(𝑔̂(𝑥)) (in teoria possiamo avere infiniti dataset). Il grado di variabilità è dato da quanto sono sovrapposte le curve verdi. Quella bold è il valore atteso di g^. Le distanze da curva nera e verde bold sono rappresentate dalla tratteggiata, cioè MSE (schematicamente sembra poco variabile molto vicina allo zero). La varianza e il bias del modello in questa figura sono piuttosto basse: è il modello auspicabile. Il modello migliore avrà sia un basso bias che una bassa varianza. 3 All'aumentare della complessità il bias diminuisce, la variabilità (blu) aumenta, se sommiamo verticalmente blu e rossa esce l'EPE cioè una misura che non è inversamente proporzionale alla complessità. L’EPE qui è visibile solo dal punto di vista teorico, non è stimabile perché dipende dalla varianza di ε non nota e quindi dobbiamo ricorrere a un suo stimatore. Esiste un compromesso tra bias e varianza che deriva dalla complessità del modello: i modelli troppo complessi avranno un'alta varianza e un basso bias; i modelli troppo semplici avranno un alto bias e una bassa varianza. Essendo f(x) sconosciuto e ESE non stimabile, dobbiamo ricorrere allo stimatore dell’ESE, cioè Average Standard Error=ASE. Notiamo che l’EPE è il valore atteso su tutto il dataset D, l’ASE il valore atteso sulle osservazioni del mio dataset (media dei residui al quadrato) ∑𝑖(𝑦𝑖 − 𝑦̂𝑖 )2 2 𝐴𝑆𝐸 = 𝐸[𝑦 − 𝑔̂(𝑥))] = 𝑛 ∑𝑛𝑖=1(𝑦𝑖 − 𝑝̂ 𝑖 )2 𝐴𝑆𝐸 𝑝𝑒𝑟 𝑡𝑎𝑟𝑔𝑒𝑡 𝑏𝑖𝑛𝑎𝑟𝑖𝑜 = 𝑛 Per evitare l’overfitting si opta per il modello con ASE (o error rate) più bassi, ricordando che i modelli più complessi hanno errore più basso e sono quelli che rischiano di più l’overfitting. Distinguiamo due categorie di apprendimento in base alla eventuale presenza di parametri. Metodi parametrici: 1 si assume la forma finale della funzione/selezione del modello 2 si trova una procedura per fittare o allenare il modello sui dati di training. Ad esempio nei modelli lineari si trovano i parametri β con il metodo dei minimi quadrati. Metodi non parametrici: non fanno assunzioni esplicite sulla forma funzionale ma cercano una stima di f che si avvicini il più possibile alle osservazioni, senza essere troppo spezzata o lineare. Rispetto ai metodi parametrici, hanno il vantaggio di avere fit più accurato perché non fa assunzioni iniziali che potrebbero non essere giuste; tuttavia necessitano di molte osservazioni per essere accurati. Tendiamo a riferirci ai problemi con una risposta quantitativa come problemi di regressione, mentre quelli che coinvolgono una risposta qualitativa sono spesso indicati come problemi di classificazione. Alcuni metodi possono essere usati per entrambe le tipologie di target e inoltre è meno importante che tipo di dato sia x. A prescindere dal tipo di target è fondamentale verificare che il dataset sia bilanciato, cioè tutte le classi o le variabili di interesse sono rappresentate in modo equilibrato. In altre parole, ogni classe o variabile ha lo stesso numero di esempi o una proporzione bilanciata rispetto alle altre classi o variabili. Va anche verificato che il dataset sia rappresentativo, cioè che riflette in modo accurato la popolazione di provenienza. TARGET QUALITATIVO 4  1. Caratteristiche dei classificatori. Teorema di Bayes, approccio Bayesiano nella classificazione, decision boundary, classificatori Bayesiani (tra cui le funzioni discriminanti, naive bayes, k-NN). 2. Teoria della decisione: eventi rari e priors, costi e profitti. 3. Misure di bontà classificativa (step 3) 1 CLASSIFICATORI. Tipologia di algoritmo (o funzione matematica che lo implementa) capace di assegnare un elemento in entrata non etichettato a una categoria già nota, in base a determinate caratteristiche. Il suo compito è quindi quello di suddividere lo spazio delle caratteristiche o covariate in regioni decisionali etichettate come classi. I confini tra le regioni di decisione sono chiamati soglie. I classificatori si costruiscono mediante metodologie diverse, parametri che riflettono la loro complessità e limiti decisionali associati. Questo fa sì che ci siano diverse strategie di pre-processing per la selezione della covariate o feature, trasformazione, dati mancanti ecc. Un buon classificatore è quello per cui l’errore di test 𝐴𝑣𝑒(𝐼(𝑦0 ≠ 𝑦̂0 )) è minimo. Error rate: metrica che valuta il modello attraverso la proporzione di osservazioni classificate erroneamente. Accuracy: metrica che valuta il modello attraverso la proporzione di osservazioni classificate correttamente. CLASSIFICATORE BAYESIANO: l’errore di test è minimizzato dal classificatore bayesiano, il quale assegna ogni osservazione xi alla classe più probabile j, dati i valori dei predittori. In altre parole, l'errore di classificazione di Bayes è l'errore minimo che può commettere un classificatore ideale. Il classificatore bayesiano richiede la conoscenza delle probabilità a priori e condizionate relative al problema, quantità che in generale non sono note ma sono tipicamente stimabili anche grazie al teorema di Bayes. TEOREMA DI BAYES: 𝐏(𝐱|𝐲 = 𝐣) 𝐏(𝐲=𝐣) Probabilità=x categoriale: 𝑷(𝐲 = 𝐣|𝐱) = 𝐏(𝐱) 𝐏(𝐱|𝐲 = 𝐣)𝛑𝐣 𝐏(𝐱|𝐲 = 𝐣)𝛑𝐣 Densità= x continua: 𝑷(𝒚 = 𝒋|𝒙) = = 𝐏(𝐱) ∑𝐉𝐣=𝟏 𝐏(𝐱|𝐲 = 𝐣)𝛑𝐣 - P(x|y=j): probabilità o densità congiunta dei livelli dell’input x entro il livello j del target, cioè sapendo che proviene dalla classe j (verosimiglianza) - P(y=j)=πj: probabilità a priori di provenire dalla classe j - P(x): distribuzione dell’input x nella popolazione - P(y=j|x): probabilità a posteriori di assegnare y al target j data una certa x Criterio MAP (Maximum A Posteriori): Il classificatore di Bayes assegna l'individuo xi alla classe j* con la maggiore probabilità a posteriori, dove il target previsto è j* tale che 𝐌𝐚𝐱 𝑷(𝝎𝒊 = 𝒋 ∗ |𝒙𝒊 ). 𝒋 5 La stima del MAP può essere usata per ottenere una stima puntuale di una quantità non osservata con i dati empirici. Il classificatore di Bayes sceglie la classe per cui la probabilità è più alta e allora il tasso di errore di classificazione Bayesiano, per X=x0, è: 𝟏 − 𝐦𝐚𝐱 𝑷(𝒀 = 𝒋|𝑿 = 𝒙𝟎 ); mentre 𝒋 quello complessivo è 𝟏 − 𝑬(𝐦𝐚𝐱 𝑷(𝒀 = 𝒋|𝑿)). Ci interessa minimizzarli: 𝒋 Esempio con target binario: per probabilità a priori 𝑃[𝜔𝑖 ] = 1⁄2 e funzione di perdita 0/1 il likelihood-ratio test diventa ML, e si pone l’obiettivo di massimizzare 𝑃(𝑥|𝜔𝑖 ) Esempio di classificazione di 2 classi: La probabilità di appartenere a una delle classi è 𝑃(𝑌 = 1|𝑋 = 𝑥0 ) >< 0.5. Se è =0.5 allora ci si trova sulla linea porpora tratteggiata chiamata Bayes decision boundary. La linea di confine o soglia di Bayes determina quindi la previsione del classificatore. Esempio: target binario ω1, ω2, con x con distribuzione normale da classificare come ω1 o ω2: Probabilità=densità perché x è continua probabilità che x 𝑃(𝑥 ∈ 𝑅2 ∩ 𝜔1 ) = 𝑃(𝑥 ∈ 𝑅2 )𝑃(𝜔1 ) = ∫ 𝑓1 (𝑥)𝑑𝑥 𝜋1 = 𝑒(2⁄1)𝜋1 venga misclassificato 𝑅2 come ω2 ma provenga da ω1 probabilità che x 𝑃(𝑥 ∈ 𝑅1 ∩ 𝜔2 ) = 𝑃(𝑥 ∈ 𝑅1 )𝑃(𝜔2 ) = ∫ 𝑓2 (𝑥)𝑑𝑥 𝜋2 = 𝑒(1⁄2)𝜋2 venga misclassificato 𝑅1 come ω1 ma provenga da ω2 Expected classification error rate Minimizzare p 6 TEOREMA DI BAYES y con j=1…J categorie: stima per il soggetto i la probabilità a posteriori di ogni categoria j del target condizionatamente ai valori xi 𝑷(𝑭|𝒄𝒉𝒖𝒓𝒏)𝑷(𝒄𝒉𝒖𝒓𝒏) 𝑷(𝒄𝒉𝒖𝒓𝒏|𝑭) = 𝑷(𝑭|𝑪𝒉𝒖𝒓𝒏)𝑷(𝑪𝒉𝒖𝒓𝒏) + 𝑷(𝑭|𝒏𝒐𝑪𝒉𝒖𝒓𝒏)𝑷(𝒏𝒐𝑪𝒉𝒖𝒓𝒏) P(yi = 1|xi)…..P(yi = j |xi) …. P(yi = J|xi) e assegna al soggetto i il target j sulla base della massima P(yi = j |xi). NB: Con K covariate di input si ha il caso multidimensionale, xi = (xi1,….,xiK) è vettore. 𝑃(𝜔𝑖 =𝑗∩𝑥𝑖 ) 𝑃(𝑥𝑖 |𝜔𝑖 = 𝑗)𝜋𝑗 x categoriali: 𝑃(𝜔𝑖 = 𝑗|𝑥𝑖 ) = 𝑃(𝑥 ) = x continue: 𝑃(𝜔𝑖 = 𝑗|𝑥𝑖 ) = 𝑖 𝑖 𝑃(𝑥 ) 𝑃(𝜔𝑖 =𝑗∩𝑥𝑖 ) 𝑓𝑗 (𝑥𝑖 )𝜋𝑗 = 𝑃(𝑥𝑖 ) 𝑓(𝑥𝑖 ) Regressione logistica e Bayes: nel caso in cui la variabile risposta abbia due classi si può ricorrere alla regressione logistica. Come si modella la relazione tra p(X)=P(Y=1|X) e X? Per convenienza usiamo 0/1 per la risposta. Ricordiamo che i parametri della regressione logistica vengono stimati con la massima verosimiglianza. Quando si assume che la distribuzione di X all'interno di ciascuna classe sia normale, si scopre che il modello è molto simile nella forma alla regressione logistica. Target binario j=1 evasore di tasse, j=0 non evasore. Un input binario: x ha una ferrari (classe x=1); un input continuo: reddito dichiarato di x. La probabilità a posteriori di yi di provenire dalla j-esima classe è 𝑒 𝛽0 +𝛽1 𝑋 Regressione logistica: 𝑃(𝑦𝑖 = 𝑗|𝑥𝑖 ) = 1+𝑒 𝛽0+𝛽1 𝑋 𝑃(𝑥𝑖 |𝑗)𝜋𝑗 Classificatore bayesiano: 𝑃(𝑦𝑖 = 𝑗|𝑥𝑖 ) = 𝑃(𝑥 ) con x=ferrari 𝑖 Regola comune: se 𝑃(𝑦𝑖 = 1|𝑥𝑖 ) > 𝑃(𝑦𝑖 = 0|𝑥𝑖 ) allora i=1, altrimenti i=0; ma Bayes utilizza: 𝑃(𝑥𝑖 |1)𝜋1 𝑃(𝑥𝑖 |0)𝜋0 𝑃(𝑦𝑖 = 1|𝑥𝑖 ) = 𝑃(𝑥 ) 𝑃(𝑦𝑖 = 0|𝑥𝑖 ) = 𝑃(𝑥 ) 𝑖 𝑖 - 𝑃(𝑥𝑖 |1)=probabilità che un evasore di tasse abbia una ferrari - 𝑃(𝑥𝑖 |0)=probabilità che un non evasore abbia una ferrari - 𝜋1 =probabilità a priori di essere un evasore nella popolazione - 𝜋0 =probabilità a priori di non essere un evasore nella popolazione Il classificatore di Bayes diventa quindi, con x=reddito 𝑓𝑗 (𝑥𝑖 )𝜋𝑗 𝑃(𝑦𝑖 = 𝑗|𝑥𝑖 ) = 𝐽 ∑𝑗=1 𝑓𝑗 (𝑥𝑖 )𝜋𝑗 - 𝑓1 (𝑥𝑖 ) funzione di densità del reddito per gli evasori fiscali - 𝑓0 (𝑥𝑖 ) funzione di densità del reddito per i non evasori Regole di classificazione equivalenti del classificatore di Bayes per classificare una nuova x come ω1 se: Regola come funzione di 1 rapporto a posteriori MAP 𝑃(𝜔1|𝑥) > 𝑃(𝜔2 |𝑥) posteriori regola come funzione di 𝜋1 𝑃(𝑥|𝜔1 ) > 𝜋2 𝑃(𝑥|𝜔2 ) verosimiglianza e priori 𝜋1 𝑓1 (𝑥) > 𝜋2 𝑓2 (𝑥) 2 Densità/rapporto di 𝑓1 (𝑥) 𝜋2 > =𝑘 verosimiglianza vs ratio a 𝑓2(𝑥) 𝜋1 priori LRT Quando i priori sono uguali 3 Densità/rapporto di 𝑓1 (𝑥) >1=𝑘 (probabilità a priori uniforme), verosimiglianza ML 𝑓2(𝑥) MAP=ML La regressione logistica però non è sempre il metodo migliore se si hanno i seguenti casi 7  - Quando c'è una sostanziale separazione tra le due classi, le stime dei parametri del modello di regressione logistica sono sorprendentemente instabili. I metodi che consideriamo in questa sezione non soffrono di questo problema. - Se la distribuzione dei predittori X è approssimativamente normale in ogni classe e la dimensione del campione è piccola, la regressione logistica non restituirà una previsione precisa e si dovrà ricorrere a un’altra classe di stimatori - Non è molto comoda nel caso in cui ci siano più di due classi nella variabile risposta, anche se si può ricorrere alla regressione logistica multinomiale. INAPPLICABILITA’ DEL TEOREMA DI BAYES: 1. Non conosciamo la distribuzione condizionata Y|X. In teoria, vorremmo sempre prevedere le risposte qualitative utilizzando il classificatore di Bayes. Ma per i dati reali non conosciamo la distribuzione condizionata di Y data X e quindi calcolare il classificatore di Bayes è impossibile. Pertanto, il classificatore di Bayes serve come gold standard irraggiungibile con cui confrontare altri metodi. Molti approcci cercano di stimare la distribuzione condizionata di Y data X, e quindi di classificare una data osservazione nella classe osservazione alla classe con la più alta probabilità stimata. Uno di questi metodi è il classificatore K-NN. 2. Probabilità a priori differenti x classificato come ω1 se 𝜋1 𝑓1 (𝑥) > 𝜋2 𝑓2 (𝑥) 𝜋1 𝑃(𝑥|𝜔1) > 𝜋2 𝑃(𝑥|𝜔2) La classificazione di Bayes si basa sul massimizzare la probabilità di appartenenza a una determinata classe. Tuttavia, se le probabilità a priori sono differenti, la linea di soglia si sposta e la conseguenza è l’aumento della probabilità a posteriori (nella figura quella rosa; si può dire che si danno pesi diversi). L’errore di classificazione di Bayes sarà sconosciuto 3. Caso di x multivariato. Il problema di ottimizzazione diventa troppo complesso per applicare Bayes. Si ricorre quindi all’analisi discriminante di Fisher, analisi discriminante lineare LDA, analisi discriminante quadratica, analisi discriminante regolarizzata RDA. Nonostante l’inapplicabilità in certi casi, l'approccio di Bayes ha ispirato le famiglie di classificatori: indiretti o generativi e diretti o discriminativi. Modelli di classificazione diretti o discriminativi (regressione logistica, albero decisionale, reti neurali): Modellano e identificano il confine decisionale tra le classi del dataset e l’obiettivo è rispondere alla domanda: “In quale lato del confine decisionale si trova questa istanza?”, così da applicare etichette di classe affidabili alle istanze di dati. I modelli discriminativi separano le classi nel set di dati utilizzando la probabilità condizionata, senza fare ipotesi sui singoli punti dati: stimano direttamente le probabilità posteriori P(𝜔i=j | x) Modelli di classificazione indiretti o generativi (metodi basati su densità, nearest neighbor, naïve bayes, metodi di smoothing, AM e analisi discriminante): modellano il modo in cui i dati sono 8 stati generati, (cioè apprendono la distribuzione del dataset) rispondendo alla domanda: “Qual è la probabilità che questa o un’altra classe abbia generato questo punto/dato/istanza?”. Prevedono così la distribuzione di probabilità congiunta P(X,Y) su una variabile osservata X e una variabile target Y mediante il teorema di Bayes. Si calcolano separatamente la stima della probabilità a priori πj che una osservazione a caso provenga dalla j-esima classe, e poi la funzione di densità di X per una osservazione proveniente dalla j-esima classe P(x|𝜔i=j). Fatto ciò, si applica il teorema di Bayes per ottenere la probabilità a posteriori P(𝜔i=j|x). L’obiettivo di questi classificatori è fare una stima della densità P(x|𝜔i=j), così poi da poter approssimare il classificatore di Bayes. I due tipi di modelli utilizzano tipi algoritmi diversi che vanno utilizzati a seconda delle esigenze. Possono essere distinti in due metodi di apprendimento lazy learning: KNN (utile per dataset eager learning: alberi decisionali, naive continuamente aggiornati) bayes, reti neurali 1. Memorizza l'insieme dei dati senza fare 1. inizia la classificazione quando riceve calcoli su di essi un dataset: di solito ha algoritmo 2. Inizia a classificare i dati quando riceve precalcolato i nuovi dati di test 2. non aspetta i dati di test per il training 3. impiega meno tempo per e classificazione l'apprendimento e più tempo per la 3. impiega molto tempo per classificazione dei dati/previsione. l'apprendimento e meno tempo per la va bene se il dataset è piccolo o classificazione dei dati. l’apprendimento ha un grande costo è usato soprattutto per piccoli dataset o per computazionale fasi di training veloci +Instance-based: riduce il numero di dati da + deve trovare una singola ipotesi che copra processare e questo salva tempo e risorse e tutte le istanze, cioè si ha un risultato globale. rende il processo di apprendimento più Dà predizioni il più velocemente possibile accurato +previene overfitting perché il modello è +più accurati degli algoritmi lazy learning allenato solo su dati rilevanti +utilissimi per dataset i cui dati diventano +necessario poco spazio: la funzione target è presto obsoleti: dati calcolati periodicamente approssimata globalmente durante il training in previsione di interrogazioni future e le risposte vengono memorizzate -alto costo computazionale: grandi dataset di -alto costo computazionale: considera training moltissimi dati per mappare tutto - È lento perché calcola le previsioni in base ai - non fornisce buone approssimazioni locali dati correnti della funzione di target -dati di training rumorosi quindi ci sono molti -spesso porta all’overfitting perché mappa più casi da considerare (inutilmente) troppo bene da input all’output e non si riesce a generalizzare nuovi dati Dai punteggi discriminanti alle quasi previsioni/posteriors. Diversi modelli di classificazione generano un punteggio di classificazione o un punteggio discriminante per ogni classe nei dati originali, che non necessariamente sono tutti positivi e sommano a uno (PLS, LDA e reti neurali). Le previsioni sono invece probabilità e DEVONO essere tutte comprese tra 0 e 1 e sommare a uno per ogni osservazione. Funzione softmax: Siano 𝑔𝑗 (𝑥𝑖 ) = 𝑔𝑖𝑗 i punteggi discriminanti della i-esima osservazione nel target j (j=1, J). La softmax li trasforma in valori quasi-probabilistici, cioè compresi in [0, 1] la cui 9 somma totale è 1, che possono essere interpretati come probabilità che l’i-esima osservazione 𝒈 𝒆 𝒊𝒋 nella classe j sia 𝑺𝒐𝒇𝒕𝒎𝒂𝒙 𝒑𝒊𝒋 = 𝒈. ∑𝑱𝒋=𝟏 𝒆 𝒊𝒋 Esempio: da probabilità logistica a softmax. La regola decisionale è “assegnare xi alla classe ωj se 𝑔𝑗 (𝑥𝑖 ) > 𝑔𝑡 (𝑥𝑖 ) ∀𝑗 ≠ 𝑡, con gj(xi) punteggi discriminanti, che nel caso binario sono: 𝑔1 (𝑥𝑖 ) = exp(𝑤 +𝑤 𝑇 𝑥𝑖 ) 𝑤 𝑇 𝑥𝑖 + 𝑤0 ; 𝑔0 (𝑥𝑖 ) = 0. Le probabilità a posteriori sono invece 𝑃(𝑦𝑖 = 𝑗|𝑥𝑖 ) = 1+exp(𝑤0 𝑇𝑥. La 0 +𝑤 𝑖) combinazione lineare dei dati pesati per i parametri è 𝑦𝑖 = 𝑗 𝑠𝑒 𝑔𝑗 (𝒙𝒊 ) = 𝒘𝑇 𝒙𝒊 + 𝑤0 ≥ 0. Abbiamo quindi che exp(𝑔1 (𝑥𝑖 )) = exp(𝑤 𝑇 𝑥𝑖 + 𝑤0 ) ; exp(𝑔0 (𝑥𝑖 )) = 1. Dall’equazione delle posteriors segue che esse non sono altro che le softmax di gj(xi). Prima di concentrarsi su ogni tipo di modello bisogna fare un piccolo excursus sullo step 3, per illustrare meglio il procedimento di addestramento di un modello: nell’elaborato si farà validazione esterna, e il modello sarà allenato sul dataset di training con la cross-validation. 3 TECNICHE DI VALIDAZIONE DEL MODELLO. sono tecniche robuste in grado di valutare l’errore del modello stimato sul dataset (misura distorta e sovraottimistica) e capaci di confrontarlo con l’errore dello stesso modello stimato su nuovi dati di validazione o test. Overfitting: l’errore (es. varianza residua, ASE) di un modello o algoritmo continua a diminuire drasticamente al crescere della complessità. Un modello overfitted è solitamente troppo complesso, cioè contiene più parametri di quanti possano essere giustificati dai dati, e nella sua costruzione si è estratta parte del rumore (varianza residua) come se fosse rappresentativa. Ne consegue ❑ Poca accuratezza (basso fit) per altri campioni: non c’è replicabilità su nuovi casi ❑ Non è attendibile nessuna previsione o stima di previsione: se il modello stimato non si generalizza nemmeno sul dataset di lavoro non ha senso ed è pericoloso fare lo score su nuovi dati ❑ Distorsione degli indici R2 e di tutte le misure di errore del modello (RSS; ASE, RASE) In sostanza, la scelta del modello di previsione/classificazione ricade su un modello che rispetti 1 criterio di importanza: robusto su nuovi dati 2 criterio di importanza: fitta/classifica bene La statistica tradizionale aveva solo il 2 criterio, non il 1. Esempio in regressione lineare: La previsione jackknife è più distante da y rispetto alla previsione del modello one shot che fornirà infatti un errore (ASE) troppo ottimistico di quello jacknife (ASECV1) Tecniche per aggiustare l’overfitting: VALIDAZIONE ESTERNA: valida il modello su un dataset totalmente nuovo e molto grande; è un set di validazione indipendente (usa infatti nuovi dati) ed è chiamato anche metodo Holdout. Consiste nel dividere il dataset in due differenti insiemi: Il dataset di training (60-70%): serve per la costruzione del modello e stima dei parametri Il dataset di validazione (40-30%): serve per la stima della performance del modello. - Vantaggi: stimo 𝑝̂ e target previsto o 𝑦̂ sul dataset di validazione: le previsioni non sono distorte e le metriche di fit e di errore sono robuste 10  - Svantaggi: parte dei dati vengono sacrificati per la fase di validazione Per ogni modello posso valutare l’overfitting al variare di j (cioè della complessità). Scelta la dimensione del modello, se l'errore di validazione è elevato rispetto ai dati di training significa che siamo in presenza di un possibile caso di overfitting: il modello non è robusto, ovvero si specializza sui dati. Scelgo j in modo da non avere overfitting (FIT TRAIN=FIT VALIDATION). Nella figura si fa validazione di un campione diverso usando la stessa funzione: l’errore di training tende a 0 all’aumentare della complessità, mentre l’errore di validazione aumenta con j. il modello migliore ha j=3 (j valuta complessità), perché l’ASE di validazione è minimo e il modello non overfitta. VALIDAZIONE INTERNA/CROSS VALIDATION: addestra il modello su una porzione (n10% dell’errore del training overfitta e quindi viene scartato: non passa il primo step: va reso meno complesso. Non ci interessa R2 alto su dati di training ma che quello di validation sia simile a quello di training. STRATIFIED SAMPLING: una tecnica di validazione che garantisce che la proporzione delle classi target nel set di training e nel set di validazione sia simile a quella del set di dati originale. Stratificazione: combina le stime di modellazione statistica per segmentazione di gruppo del set di dati di addestramento (modelli separati per ogni livello di SESSO). PRO: Tecnica vantaggiosa se c’è alta variabilità tra i gruppi (rispetto alla variabilità complessiva dei valori target, si controlla per costruzione). Si possono così ottenere stime da ciascun gruppo separatamente e poi si combinano quelle di ciascun gruppo in un’unica stima complessiva. 13 CONTRO: Metodo svantaggioso se all'interno di alcuni gruppi non ci sono abbastanza osservazioni, si ha poi bassa potenza statistica, stime instabili e cattiva generalizzazione. K-NEAREST NEIGHBOR: algoritmo che riconosce pattern per la classificazione di oggetti basandosi sulle caratteristiche degli oggetti vicini a quello considerato ed è così una forma di clustering. Il modello che ne deriva può essere classificato come generativo o discriminativo. Nella classificazione k-NN, l'output è un'appartenenza a una classe. 1. Lo spazio viene diviso in regioni in base alle posizioni e caratteristiche degli oggetti 2. Si calcola la distanza tra gli oggetti (tipicamente euclidea), ma ha alto costo computazionale 3. Classificazione: un oggetto xi è classificato dal voto di maggioranza dei suoi vicini, cioè xi assegnato alla classe più frequente tra i suoi k vicini più vicini (k è un numero intero positivo, tipicamente piccolo, che dipende dai dati). I vicini sono presi da un insieme di oggetti per cui è nota la classificazione corretta. Considerando solo i voti dei k oggetti vicini c'è l'inconveniente dovuto alla predominanza delle classi con più oggetti. In questo caso può risultare utile pesare i contributi dei vicini in modo da dare, nel calcolo della media, maggior importanza in base alla distanza dall'oggetto considerato. Probabilità che xi appartenga alla classe j del target P(yi= j/x)= % dei vicini più prossimi con la classe j. In questo caso, non esiste un modello, ma solo una regola decisionale. 𝑃(𝑥 |𝜔𝑗 )𝜋𝑗 K Nearest Neighbor è un modello generativo. 𝑃(𝑦𝑖 = 𝑗|𝑥) = 𝑃(𝜔𝑗 |𝑥) = 𝑃(𝑥). Modella la probabilità condizionata di un campione (o oggetto) di appartenere a una classe. Si stimano separatamente 𝜋𝑗 e 𝑃(𝑥|𝜔𝑗 ), poi si applica il teorema di Bayes per ottenere 𝑃(𝜔𝑗 |𝑥). K-NN è uno stimatore di densità di Kernel: definiamo prima la stima kernel di densità: metodo non parametrico utilizzato per il riconoscimento di pattern e per la classificazione attraverso una stima di densità nello spazio delle feature. Per ogni x all'interno dello spazio delle feature, l'algoritmo permette di calcolare la probabilità di appartenere ad una classe C, considerando la densità di C in un intorno k del punto x. Il metodo si basa su un intorno di dimensione fissa calcolata in funzione al numero di osservazione N. Rischia facilmente overfitting se la finestra è molto piccola, ma se è troppo grande si hanno più errori nelle zone più addensate. L’algoritmo k- NN ha tutte queste caratteristiche ed è perciò uno speciale tipo di stima di densità kernel, che però migliora questa stima perché viene impiegata una finestra dinamica scelta localmente. Con N punti in due dimensioni vogliamo la densità 𝑃(𝑥|𝜔𝑗 ) = 𝑃(𝑥1 , 𝑥2 |𝜔𝑗 ), xcerchio VR2 la cui area si allarga finché non troviamo k neighbours (kj di classe j). La stima di densità non parametrica in 𝑉 = 𝑎𝑟𝑒𝑎 𝑐𝑖𝑟𝑐𝑜𝑠𝑡𝑎𝑛𝑡𝑒 𝑎 𝑥 𝑘𝑗 𝑃(𝑥|𝜔𝑗 ) è: 𝑃(𝑥|𝜔𝑗 ) = 𝑉 𝑁 𝑑𝑜𝑣𝑒 {𝑁𝑗 𝑝𝑢𝑛𝑡𝑖 𝑑𝑖 𝑐𝑙𝑎𝑠𝑠𝑒 𝑗 𝑛𝑒𝑙 𝑑𝑎𝑡𝑎𝑠𝑒𝑡 𝑗 𝑘𝑗 𝑝𝑢𝑛𝑡𝑖 𝑣𝑖𝑐𝑖𝑛𝑖 𝑑𝑖 𝑐𝑙𝑎𝑠𝑠𝑒 𝑗 La stima si può calcolare con due metodi: o k-nearest-neighbors (kNN): fissare 𝑘 e determinare il minimo 𝑉 che comprende 𝑘 punti intorno a x. La posteriorità utilizzando il classificatore di Bayes diventa o kernel density estimation: si fissa 𝑉 e si determina il numero 𝑘 di punti dati all'interno di 𝑉 14 Come si fa a scegliere k ottimale? Considero vantaggi e svantaggi di k grande + Rende più omogenee le regioni di decisione + Fornisce informazioni probabilistiche, ossia il rapporto di esempi per ciascuna classe fornisce informazioni sull'ambiguità della decisione. + Riduce l’effetto del noise sulla classificazione - Distrugge la località della stima, poiché vengono presi in considerazione esempi più lontani. - rende meno distinti i confini tra le classi - Aumenta il costo computazionale confronto tra confini decisionali KNN per K=1 e K=100 Il tasso di errore di addestramento KNN (blu, 200 osservazioni) e il tasso di errore di prova (arancione, 5.000 osservazioni) sui dati della figura, all'aumentare del livello di flessibilità (valutato con 1/K sulla scala dei log) aumenta, o equivalentemente al diminuire del numero di vicini K. La linea nera tratteggiata indica il tasso di errore di Bayes. La saltuarietà delle curve è dovuta alle ridotte dimensioni dell'insieme di dati di addestramento. Vantaggi e svantaggi KNN: +essendo non parametrico è utilissimo quando il confine decisionale non è per niente lineare +tende a ridurre il bias -richiede numero di osservazioni n molto elevato -n>>>>p predittori -incorre in forte varianza, cioè rischio di overfitting -non dice quali predittori sono importanti, a differenza della regressione logistica -sono instabili: piccolo cambiamento nei dati può portare a grandi cambiamenti nei confini decisionali e performance - non funziona bene nel caso di molti attributi di rumore ANALISI DISCRIMINANTE LINEARE. Si parte in generale dalla Analisi Discriminante di Fisher FDA: utilizza un criterio di classificazione del segnale: trova una rappresentazione che massimizzi l'informazione discriminante per la classe nello spazio a più bassa dimensionalità. LDA con un solo predittore. LDA produce la migliore discriminazione possibile in termini di separazione tra i gruppi, supponendo che le u.s. siano separate a priori nei gruppi. Se l’obiettivo è predittivo allora si assegna una nuova u.s. di cui non si conosce la popolazione di provenienza a una delle Pg commettendo il minimo errore possibile di misclassificazione. Assunzioni da fare: - indipendenza: si presume che il campione sia casuale - omoschedasticità: le matrici di var-cov dei gruppi sono uguali tra loro - normalità multivariata: le variabili indipendenti sono normali La funzione discriminante lineare produce la migliore discriminazione possibile tra i gruppi, e i gruppi sono massimamente separati con le loro medie. Si vuole ottenere la stima della densità fk(x) così da poter stimare la probabilità a posteriori e poi poter classificare le osservazioni per la classe con maggiore probabilità. 15 Esempio: LDA con un input e target binario. Priors uguali: π1=π2=0.5. Nel grafico a sinistra sono rappresentate funzioni di densità normali unidimensionali; la soglia Bayesiana, indicata con la linea tratteggiata, è il valore 𝜇 +𝜇 delle due medie campionarie 1 2 2 = 0. Ad esempio se un nuovo punto x=0,73 classificare come 2: 1. ha la massima densità/verosimiglianza di appartenere a classe 2 (posteriors fj(x)j = fj(x)) 2. è più vicino al centroide della classe 2 (approccio delle funzioni discriminanti): 2𝑥(𝜇1 − 𝜇2 ) < 𝜇12 − 𝜇22 A destra: 20 osservazioni sono state estratte da ciascuna delle due classi e sono mostrate come istogrammi; la linea verticale tratteggiata rappresenta la soglia di Bayes, la linea verticale continua la soglia LDA stimata dai dati di training. In questo caso possiamo calcolare il classificatore di Bayes perché sappiamo che X è estratto da una distribuzione gaussiana all'interno di ogni classe e conosciamo tutti i parametri coinvolti. In una situazione reale, non siamo in grado di calcolare il classificatore di Bayes. Priors differenti. 𝜋1 = 0.3 < 𝜋2 = 0.7. in generale sappiamo che x è classificato come ω1 se 𝜋1 𝑓1 (𝑥) > 𝜋2 𝑓2 (𝑥) → 𝜋1 𝑃(𝑥|𝜔1) > 𝜋2 𝑃(𝑥|𝜔2 ). In questo caso, però, la posterior rosa è aumentata e di conseguenza la soglia si è spostata verso sinistra. Relazione tra LDA e k-NN: la soglia di k-NN converge con quella della LDA per 𝑘 → ∞. LDA con più di un predittore. Si assume che X=(X1, …, Xp) è una Gaussiana multivariata. Esempio: in questo caso la variabile è di tipo qualitativo, quindi l’assunzione di normalità è violata. Tuttavia LDA è spesso robusta rispetto a queste violazioni, come in questo esempio. Qui non c’è problema di overfitting perché p=2 e n=10000. La matrice di confusione mostra che in un target binario si possono fare due tipi di errore: i “no” assegnati a “yes” e viceversa. L’errore di training è 2.75%, che sembra piccolo, ma l’errore di training è quasi sempre più piccolo dell’errore di test. Inoltre in questo contesto va notato che il tasso di errore per gli “yes” quindi chi va davvero in default è 252/333=75.7%, che è troppo. LDA ha bassa sensibilità. ANALISI DISCRIMINANTE QUADRATICA. Come LDA assume che le osservazioni di ciascuna classe sono tratte da una distribuzione gaussiana e inserendo le stime dei parametri nel teorema di Bayes per eseguire la previsione. QDA però non presuppone che le covarianze di ogni classe siano uguali ed è utile nel caso in cui la soglia tra le classi non è lineare. Assegna un’osservazione x alla classe per cui è più piccolo il punteggio discriminante, avendo relazione quadratica tra x e la f.d. Differenze tra LDA e QDA: LDA QDA Funzione discriminante: Funzione discriminante: 1 𝑇 1 𝑇 −1 𝑔𝑗 (𝑥) = − (𝑥 − 𝜇𝑗 ) Σ −1 (𝑥 − 𝜇𝑗 ) + 𝑙𝑜𝑔𝜋𝑗 𝑔𝑗 (𝑥) = − 2 (𝑥 − 𝜇𝑗 ) Σj (𝑥 − 𝜇𝑗 ) + 𝑙𝑜𝑔𝜋𝑗 2 Interpretazione: assegnare il nuovo caso 𝑥 Interpretazione: assegnare il nuovo caso 𝑥 alla classe j più vicina al suo centroide μj alla classe j più vicina al suo centroide μj (metrica di Mahalanobis) (metrica di Mahalanobis pesata dalle diverse matrici Σj) matrice di covarianza comune matrice di covarianza per ogni classe k 16  numero di parametri con p predittori: numero di parametri con p predittori: p(p+1)/2 Kp(p+1)/2 LDA meno flessibile QDA varianza inferiore preferibile se le osservazioni di training sono preferibile se l'insieme di training è grande, poche e quindi bisogna ridurre la varianza quindi la varianza del classificatore non è molto importante o se non si può avere una matrice di covarianza comune per le K classi densità stimate: densità stimate: confini decisionali:  ha curve di forma confini decisionali: j ha curve di forma simile tra le classi diverse tra le classi Analisi discriminante: vantaggi e svantaggi (stessi svantaggi di NN) +analiticamente trattabile -variabili di input continue e normali + implementazione semplice -richiedono model selection + solitamente basso overfitting -non ci dicono quali predittori sono importanti + veloce (non i coefficienti) -soffre la collinearità e dati mancanti Nelle caso in cui la soglia è non lineare ma n è piccolo oppure c’è un numero non molto piccolo di predittori p, allora QDA può essere preferito a KNN. Questo perché QDA è in grado di fornire una soglia non lineare e allo stesso tempo sfruttare una forma parametrica, il che significa che richiede una dimensione del campione più piccola per una classificazione accurata, rispetto a KNN. NAIVE BAYES. versione semplificata e applicabile del classificatore di Bayes, usata perché la probabilità P(xi|ωj) è difficile da stimare, soprattutto nel caso multidimensionale con xi=(xi1,xik, xiK) 𝑷(𝒙𝒊 |𝝎𝒋 )𝝅𝒋 con K covariate. L’equazione di partenza è 𝑷(𝝎𝒋 |𝒙𝒊 ) = 𝑷(𝒚𝒊 = 𝒋|𝒙𝒊 ) = 𝑷(𝒙 ) 𝒊 data una classe j, le xi1, xik, xiK sono indipendenti tra loro. È quindi un’applicazione del teorema di Bayes con forti assunzioni di indipendenza (naive) tra le features (non ne assume la forma): all’interno della k-esima classe, i p predittori sono indipendenti tra loro e assegna l'individuo i alla classe j con la maggiore probabilità a posteriori di appartenenza P(ω j|xi). Ne consegue che la probabilità condizionata di xi multidimensionale è: 𝑃(𝑥𝑖 |𝜔𝑗 ) = 𝑃(𝑥𝑖1 |𝜔𝑗 ) × … × 𝑃(𝑥𝑖𝐾 |𝜔𝑗 ): è un prodotto di K probabilità unidimensionali (facilmente stimabili dai dati). Quindi per k=1,…,K: Xj quantitative: 17  2 - Si può assumere che 𝑋𝑗 |𝑌 = 𝑘~𝑁(𝜇𝑗𝑘 , 𝜎𝑗𝑘 ), cioè che all’interno di ogni classe il j-esimo predittore sia generato da una distribuzione normale univariata. Differisce dall’LDA perché si assume l’indipendenza. - Si può usare una stima non parametrica per fkj, usando un istogramma per le osservazioni del j-esimo predittore all’interno di ciascuna classe e poi stimare fkj(xj) come frazione. Xj qualitative: le P(xk|𝜔j) sono facilmente stimate utilizzando le percentuali di riga nelle tabelle di contingenza date dall'incrocio dei target y e xk. Ne deriverà una produttoria. Il classificatore è quindi 𝑷(𝒙𝒊𝒌 |𝝎𝒋 )𝝅𝒋 𝑷(𝝎𝒋 |𝒙𝒊 ) = ∏ ∝ ∏ 𝑷(𝒙𝒊𝒌 |𝝎𝒋 )𝝅𝒋 𝑷(𝒙𝒊 ) 𝒌 𝒌 Esempio: matrice di confusione con Naïve Bayes. Prevediamo il default per ogni osservazione per cui (Y=deafult|X=x)>0.2. Il tasso di errore è più alto rispetto a quello dell’LDA, ma prevede correttamente circa 2/3 dei veri default. Naive Bayes e pre processing Gestire il problema della frequenza zero: aggiungere n dati artificiali (chiamati correzione di Laplace/smoothing) per ogni cella della tabella di frequenza dell'input*target per stimare P(xk/𝜔j), quando un input ha un conteggio pari a 0, in modo da eliminare il problema. Dati mancanti: bene per inputs=x categoriali. I valori mancanti per gli input categorici (x) sono gestiti in modo appropriato da NB: Nella fase di fit del modello di training, l'osservazione i con valori mancanti sugli input xk non viene inclusa nel conteggio delle frequenze per il calcolo di P(xki/𝜔j). In pratica, la P(xki/𝜔j) per l'osservazione i viene trovata utilizzando altre n-1 osservazioni non mancanti della tabella di contingenza che incrocia xk e y. Nella fase di classificazione dei nuovi dati: l'input mancante xki (x2 sotto) sarà omesso dal calcolo del posterior P(𝜔j /xi) per un'osservazione i, ma la formula mantiene altri fattori del prodotto: 𝑃(𝜔𝑗 |𝑥𝑖 ) ∝ 𝑃(𝑥1𝑖 |𝜔𝑗 ) ∗ 𝑃(𝑥2𝑖 |𝜔𝑗 ) ∗ 𝑃(𝑥3𝑖 |𝜔𝑗 )𝜋𝑗 Non gestire il problema dei dati mancanti per x continui. +Facile da implementare - Influenzato da input collineari + Buoni risultati ottenuti nella maggior parte - Gestire il problema della frequenza zero: dei casi aggiungere dati artificiali per ogni + Nonostante la sua semplicità, il Naïve Bayes combinazione attributo-valore-classe con ha dimostrato di avere prestazioni conteggio 0 (correzione di Laplace) paragonabili alle reti neurali artificiali e a - Metodo di stima per le densità (input strumenti più complicati in alcuni domini continui) (testi) - Presupposti forti indipendenza condizionale, + Non è influenzato da input irrilevanti: gli esistono dipendenze tra le variabili (vedi Reti attributi distintivi hanno un potere Bayesiane), possibile perdita di accuratezza. discriminante migliore degli attributi di rumore Nel caso, è meglio usare la KNN. + Piccolo sforzo di pre-elaborazione 18 Le metodologie elencate non hanno un ruolo univoco e possono essere riutilizzate in diversi step, accompagnate da metodi di ricampionamento (cross-validation, bootstrap) e metodi di selezione del modello (regolarizzazione, riduzione della dimensionalità). Poiché i metodi di ricampionamento possono essere particolarmente dispendiosi dal punto di vista computazionale, è più conveniente fare prima model selection. Tre strategie per gestire molte covariate: model selection, shrinkage, riduzione dimensionalità. Model selection: Identificazione di un sottoinsieme M di tutti i predittori X che si ritiene siano correlati alla risposta y, e quindi adattamento del modello utilizzando questo sottoinsieme. In genere si basa sulla significatività (p-value) di qualche strategia (backward, forward, stepwise). Nel nostro corso di ML proporremo diversi modi per fare la selezione del modello, utilizzando algoritmi (che sono di per sé classificatori) di ML che fanno naturalmente la selezione del modello (albero decisionale, foresta casuale). Ovviamente è anche possibile farlo manualmente ispezionando i grafici (osservando quali covariate separano le classi di riferimento). Per valutare la significatività delle x si può anche usare una regressione logistica; le reti neurali non fanno model selection poiché ne hanno bisogno nel pre-processing. Shrinkage/regolarizzazione: La regolarizzazione risolve un problema mal condizionato (soluzioni sono molto sensibili a piccole perturbazioni dei dati iniziali) o previene l’overfitting. Alcuni dei coefficienti possono ridursi esattamente a zero e quindi i metodi di contrazione possono anche effettuare una selezione delle variabili, tra cui, ad esempio, la regressione Ridge e il LASSO. Perché regolarizzare i parametri? Se abbiamo il caso in immagine, per j=9 il polinomio passa esattamente ogni punto dei dati, ma tra un punto e l'altro (in particolare vicino agli estremi dell'intervallo) la funzione presenta grandi oscillazioni: l'ampiezza dell’intervallo dei coefficienti è sintomo di instabilità del modello. Sia la linea verde sia quella rossa hanno errore nullo sui dati blu. Tuttavia, un modello addestrato può essere indotto a preferire la linea verde, in quanto più stabile, tramite una modifica del peso del termine regolarizzatore. 19 Regolarizzazione: REGRESSIONE DI RIDGE. La RR tende a “spingere verso lo zero” coefficienti stimati e non penalizza il termine di intercetta. Quando ci si trova di fronte a problemi di minimi quadrati non lineari oppure si hanno molti predittori, con alcuni di loro multicollineari, allora le stime possono diventare instabili e meno attendibili. Un metodo per risolvere questo problema è quello di adattare un modello contenente tutti i predittori usando una tecnica che “vincola” o “regolarizza” le stime dei coefficienti, o equivalentemente, che “stringe” (“shrink”) le stime dei coefficienti verso zero. Restringere le stime dei coefficienti ha l’effetto di ridurre significativamente la varianza dei coefficienti. Nella RR i coefficienti sono stimati minimizzando una quantità leggermente differente rispetto ai minimi quadrati. In particolare, la funzione obiettivo nella RR è una versione “penalizzata” della somma dei quadrati delle deviazioni usata nei minimi quadrati. La penalizzazione (chiamata “shrinkage penalty”), è piccola quando i coefficienti sono prossimi a zero, e quindi ha l’effetto di costringere le stime verso lo zero. Nella funzione obiettivo troviamo anche un parametro di tuning che regola l’ammontare dello “shrinkage”. La regressione ridge produce stime dei coefficienti meno variabili e meno correlate al costo di un leggero aumento nella distorsione della stima. La penalizzazione non avviene liberamente, infatti la somma dei coefficienti deve essere al di sotto del massimo budget ed è stima vincolata, calcolabile mediante i moltiplicatori di Lagrange con parametro λ. La regolarizzazione avviene ponendo una qualche funzione della somma dei coefficienti come penalità nella loss function per stimare i parametri. 𝜆 ≥ 0 è il parametro di regolarizzazione che bilancia il fit dei minimi quadrati/OLS, in altre parole regola la complessità della funzione; la selezione di un buon valore di λ è critica ed è fatta tipicamente tramite cross- validation. 𝛌 → 𝟎, 𝛃 ̂ 𝐫𝐢𝐝𝐠𝐞 → 𝛃̂ 𝐎𝐋𝐒. 𝛌 Il termine di penalizzazione non ha alcun effetto sui coefficienti e la regressione Ridge produrrà OLS, avendo la stessa funzione di perdita, tornando ai problemi di OLS e massima verosimiglianza. Quindi, quando λ è troppo piccolo possiamo tunare i dati e ottenere modelli che hanno un basso bias e alta varianza. Le stime 𝛽̂ 𝑂𝐿𝑆 sono uniche 20  𝒓𝒊𝒅𝒈𝒆 𝝀 → ∞, ̂ 𝜷𝝀 → 𝟎. 𝑟𝑖𝑑𝑔𝑒 Ridge fornisce le stime 𝛽̂𝜆 per ogni λ. Se λ è grande si dà grande peso alla penalizzazione e va tenuto sotto controllo. I coefficienti saranno sempre più piccoli (tendenti a 0) e la conseguenza sarà avere modelli troppo semplicistici e distorti, fino ad arrivare al caso limite dove l’unico modello sarà costituito dall’intercetta: alto bias e bassa varianza. ridge TEOREMA DI ESISTENZA: Esiste sempre un λ tale che l’errore quadratico medio MSE di β̂λ è minore dell’MSE di β̂OLS. In generale, l'errore quadratico medio di uno stimatore 𝜃̂ rispetto al 2 parametro stimato θ è definito come 𝑀𝑆𝐸(𝜃̂) = 𝐸[(𝜃̂ − 𝜃) ]: l’MSE ci dà una misura per giudicare la qualità di uno stimatore in termini della sua variazione e della sua distorsione. 2 Dimostrazione. Essendo 𝐸(𝜃 2 ) = 𝑉𝑎𝑟(𝑋) + (𝐸(𝑋)) , possiamo dire che Si tratta di un risultato piuttosto sorprendente con implicazioni radicali: anche se il modello che fittiamo con OLS è esattamente corretto e i residui seguono l'esatta distribuzione da noi specificata, possiamo sempre ottenere un migliore (in metrica MSE) stimatore Ridge restringendo verso lo zero i coefficienti. Gli OLS sono unici, Ridge dà una stima per ogni λ, è distorto ma è più efficiente: MSE ridge è inferiore dell’MSE di OLS. Vantaggi computazionali della regressione di Ridge: - Se p è grande, la Regressione di Ridge è un metodo adatto. λ è un parametro di regolazione che di solito viene individuato come il valore che minimizza l’ASE - Con la RR è sufficiente adattare un solo modello e i calcoli risultano molto semplici. - La Regressione di Ridge può essere utilizzata anche quando p > N, una situazione in cui OLS, regressione logistica e molti altri modelli falliscono completamente - La Regressione di Ridge non funziona come selettore di modelli, ma aumenta la stabilità del modello completo. Regolarizzazione: REGRESSIONE LASSO=Least Absolute Shrinkage and Selection Operator. Simile al metodo dei minimi quadrati OLS, è un metodo di analisi di regressione che esegue sia la selezione delle variabili sia la regolarizzazione, in modo da migliorare l’accuratezza della previsione e l’interpretabilità del modello statistico finale. LASSO minimizza la devianza residua o RSS ma pone il vincolo che la somma dei valori assoluti del coefficiente sia inferiore a una costante. Questo vincolo aggiuntivo è inoltre simile a quello introdotto nella regressione di Ridge, dove il vincolo riguarda la somma dei valori al quadrato dei coefficienti. Questa semplice modifica fa sì che alcuni coefficienti possano essere ridotti esattamente a 0, essendo non negativi. Offre gli stessi vantaggi della Ridge, cioè alto bias e bassa varianza rispetto all’OLS con N1 i coefficienti di regressione si restringono fino a essere ridotti a 0, e per λ→∞ tutti i coefficienti vengono eliminati. Ad esempio, per s vicino a 0,4 (linea rossa tratteggiata), vengono selezionate solo 3 variabili. Se λ=0 nessun parametro viene eliminato; se decresce aumenta la varianza. Regolarizzazione: funzione di perdita per un target binario. - Tipica funzione di perdita: massima verosimiglianza. 𝑁 1 𝑇 max ∑ [𝑦𝑖 (𝑥𝑖𝑇 𝛽 + 𝛽0 ) − log (1 + 𝑒 𝑥𝑖 𝛽+𝛽0 )] 𝛽,𝛽0 𝑁 𝑖=1 22  - Nuova funzione di perdita: massima verosimiglianza penalizzata. 1 𝑇 2 Logistica Ridge: max ∑𝑁 𝑇 𝑖=1 [𝑦𝑖 (𝑥𝑖 𝛽 + 𝛽0 ) − log (1 + 𝑒 𝑥𝑖 𝛽+𝛽0 )] − 𝜆||𝛽|| 𝛽,𝛽0 𝑁 2 1 𝑥𝑖𝑇𝛽+𝛽0 Logistica Lasso: max ∑𝑁 𝑇 𝑖=1 [𝑦𝑖 (𝑥𝑖 𝛽 + 𝛽0 ) − log (1 + 𝑒 )] − 𝜆||𝛽||1 𝛽,𝛽0 𝑁 Riduzione della dimensionalità. Consiste nel proiettare tutti i p predittori in uno spazio di M dimensioni, dove M 1 è generalmente usata per la selezione di variabili poiché la media di 𝑉𝐼𝑃𝑗2 = 1. Vantaggi e svantaggi di PCR-PLS: + Regressione e riduzione delle dimensioni simultanea -Similmente alle PCA: o Le direzioni del PLS saranno tracciate verso le variabili indipendenti con la maggiore variabilità (anche se questo sarà mitigato dalla scala x) o Gli outlier possono avere un'influenza significativa sulle direzioni, sui punteggi risultanti e sulla relazione con la risposta. o PCR-PLS fornisce punteggi discriminanti e non posteriorità. Per determinare il numero di componenti PLS da calcolare si ottimizza una statistica di adattamento (o fit) del modello (ASE o PRESS). Uso di PCR-PLS: come nuovi input, o/e come nuovi classificatori Se la selezione del modello è troppo accurata si potrebbe incorrere nell’overfitting. 24 ALBERO DECISIONALE: tecnica di ml non parametrica per risolvere problemi di classificazione e previsione, capace di analizzare il ruolo delle covariate e dei rispettivi livelli nella discriminazione rispetto al target dei soggetti del dataset in gruppi finali. Sono molto versatili in quanto possono trattare molti tipi di dati, hanno buone performance e sono comprensibili ai non statistici. Per quanto riguarda la sua struttura, ha come punto di partenza il nodo padre o radice, cioè il dataset completo, che si divide in nodi figli o foglie rispetto ai livelli mutuamente esclusivi di una covariata. La divisone in foglie farà sì che si rispetti il criterio di massima eterogeneità tra le foglie finali, che devono anche essere massimamente omogenee al loro interno. In ogni nodo finale si assegnano soggetti al target previsto in base alla modalità del target più frequente. INTERPRETAZIONE. Esempio: studiare i fattori che influenzano la decisione di iscriversi a un giornale.Nodo finale 1: soggetti in questo nodo hanno 0.906 probabilità di iscriversi al giornale: valore previsto =yes. Nodo finale 2: soggetti in questo nodo hanno 0.44 probabilità di iscriversi al giornale: valore previsto =No. Nodo finale 3 analogamente COSTRUZIONE: quale è la variabile che determina il primo split e perché; perché il primo split si ottiene a un determinato livello. 1. Divisioni/split ammissibili: stabilire, per ciascun nodo, l’insieme delle divisioni ammissibili Split binari (preferibili): 2 nodi figli o split multilivello: >2 nodi figli. Partizioni binarie: Natura del predittore Numero di modalità Numero di split (binari) variabile continua N N-1 variabile binaria 2 1 variabile ordinale m m-1 variabile nominale m 2𝑚−1 − 1 2. Definire criterio di split per selezionare la migliore divisione di un nodo. Esempi: - Rispetto al target: L’insieme iniziale (nodo padre) deve essere suddiviso in 2 gruppi (NODI FIGLI) che siano più possibilmente omogenei al loro interno ed il più possibile eterogenei tra loro rispetto al target - Un criterio di split deve basarsi su un indice statistico che consente di selezionare la partizione migliore fra tutte le possibili partizioni binarie di una covariata (cutoff covariata (x)) e tra tutte le possibili covariate. In un target categoriale con k livelli a ciascun nodo t, t1, t2 è legato una misura di impurità. Massima impurità: classi del 25  target equidistribuite al suo interno; minima impurità: nodo contiene individui appartenenti solo ad una classe del target. Esempio: se in t abbiamo N soggetti, 50% di abbonati ad una rivista, e riusciamo a trovare una covariata (sex) tale che in t1 (maschi) il 100% è abbonato e in t2 (femmine) il 100% non è abbonato, i due nodi figli hanno minima impurità da un nodo padre che ha max impurità. 1. valutare la misura di impurità di un nodo, a prescindere se è nodo padre o figlio. Indice di eterogeneità di Gini. 𝑮𝒊𝒏𝒊(𝒕) = 𝟏 − ∑𝒋 𝒇𝟐𝒋 (𝒕). Minima impurità=minimo Gini=0. Massima impurità=Massimo Gini=(J-1)/J Impurità media dei figli dello split s dal nodo padre t: 𝐺𝐼𝑁𝐼𝑠𝑝𝑙𝑖𝑡 (𝑠, 𝑡) = 𝑝1 𝐺𝐼𝑁𝐼(𝑡1 ) + 𝑝2 𝐺𝐼𝑁𝐼(𝑡2 ) Decremento di impurità dello split s dal nodo padre t: ∆𝐺𝐼𝑁𝐼(𝑠, 𝑡) = 𝐺𝐼𝑁𝐼(𝑡) − 𝑝1 𝐺𝐼𝑁𝐼(𝑡1 ) − 𝑝2 𝐺𝐼𝑁𝐼(𝑡2 ) o Target quantitativo y: misura di impurità di un nodo t=varianza di y nel nodo t. Impurità del padre t: 𝑉𝑎𝑟(𝑡) = 𝑠 2. Impurità dei figli tj: 𝑉𝑎𝑟(𝑡𝑗 ) = 𝑠𝑗2 Impurità media dei figli dello split j dal nodo t: 𝑣𝑎𝑟(𝑗, 𝑡) = 𝑝1 𝑠12 + 𝑝2 𝑠22 L’impurità complessiva è uguale alla varianza del target y in ogni nodo tj. - Chi quadro associato a ogni split s da t. Χ2 grande: grande associazione tra target e divisione binaria di x → p-value piccolo perché c’è una forte associazione tra gli split e le classi del target, quindi lo split è otimale. Trovare lo split s* con il più piccolo p-value del test Chi-quadro. - Tasso di misclassificazione: Ad ogni possibile split s da t è associato un tasso di errore che attraversa il target e che è previsto dallo split. Trovare lo split s* con il più piccolo tasso di errore. Questa regola è usata in R si usa il codice rpart per controllare la dimensionalità dell’albero nella fase di pruning Target continui: Indichiamo var(totale)=s2 (varianza del target nel dataset di validazione); var(nei nodi)=var(j*,t) (media pesata per le numerosità dei nodi delle varianze del target nei nodi finali della validazione). Per valutare eventuale overfitting si ricorre alle seguenti metriche: o Average square error 𝐀𝐒𝐄 = 𝐧−𝟏 ∑𝒊(𝒚𝒊 − 𝒚 ̂𝒊 )𝟐 con yi=valore osservato per osservazione i del target; y^i=valore previsto per osservazione i (media del target del nodo t dove si trova l’osservazione i) [𝑠2 −𝑣𝑎𝑟(𝑗 ∗ ,𝑡)] o R2 di un albero=varianza spiegata/totale: 𝑅 2 = 𝑠2 o Correlazione tra yi e y^i 3. Una regola di arresto per dichiarare un nodo come finale o intermedio. La ripartizione binaria di un insieme di unità statistiche si arresta naturalmente nella situazione ideale che i nodi terminali contengono solo individui appartenenti ad una sola classe della variabile dipendente. L’albero completo potrebbe avere tanti nodi finali quante sono le unità statistiche, fornendo un albero potenzialmente con migliaia di nodi (in qusto caso, però, si andrebbe incontro all’overfitting). La regola di arresto serve per arrestare l’albero in un punto efficace (alto potere discriminatorio). Di fatto vanno definite regole di potatura (pruning) per controllare la dimensione dell’albero (numero nodi finali). Esistono due possibilità: PRE pruning e POST pruning 26  - PRE-PRUNING: prima di ricavare l’albero si può definire la dimensione della foglia=numerosità minima dei nodi finali, il numero minimo di osservazioni in un nodo necessarie per avere uno split (K, multiplo di n), la massima profondità dell’albero - POST-PRUNING: Consentono all'albero decisionale di crescere in profondità sfoltendo i rami che non generano ulteriore discriminazione sul validation secondo vari criteri: misclassification, profit & loss, ASE 4. valutazione della qualità della regola di decisione: stimare il rischio di errore di classificazione o di previsione associato Useremo approccio CART=Classification And Regression Trees, il quale utilizza come criterio di split le partizioni binarie. Alberi di classificazione: Individuare gruppi di soggetti che siano internamente omogenei ed esternamente eterogenei rispetto ad una variabile risposta qualitativa con J livelli (classificazione/segmentazione) Alberi di regressione: Individuare gruppi di soggetti che siano internamente omogenei ed esternamente eterogenei rispetto ad una variabile risposta quantitativa (previsione) 1. Mediante una successione di divisioni binarie usando covariate di ogni tipo (nominali, dummy, ordinali) si raggiungerà l’obiettivo decisionale che consiste nello sfruttare la regola di classificazione/previsione ottenuta per classificare nuovi casi. 2. l criterio di split utilizzato dal CART è lo split s* che ha massimo decremento di impurità e l’obiettivo è generare nodi figli più puri del nodo padre t: ∆𝐺𝐼𝑁𝐼(𝑠 ∗ , 𝑡) = 𝑚𝑎𝑥. Deve essere raggiunto con i dati disponibili (c’è lo split ideale che non rispecchia mai i dati). Una volta creato il primo split, dai due nodi figli creati CART si riparte daccapo, considerando ciascun nodo figlio come un nuovo nodo padre e riavvia la ricerca del miglior split separatamente per i due nodi figli. o Target quantitativo: impurità del padre=varianza del target nel dataset. Impurità dello split j dal nodo t=varianza media del target dei figli, cioè varianza nei gruppi/residua: 𝑣𝑎𝑟(𝑗, 𝑡) = 𝑝1 𝑠12 + 𝑝2 𝑠22. Cart cerca da nodo t il miglior split j* che minimizza la varianza nei gruppi/residua 𝑀𝑖𝑛[𝑣𝑎𝑟(𝑗 ∗ , 𝑡)] o, equivalentemente, massimizza la varianza tra i gruppi/spiegata 𝑀𝑎𝑥[𝑠 2 − 𝑣𝑎𝑟(𝑗 ∗ , 𝑡)]. Vantaggi e svantaggi +al contrario della regressione non richiedono -tende a selezionare troppi pochi input per i l’imputazione e trasformazione di X né modelli successivi: per questo motivo si selezione del modello, anzi può servire proprio sconsiglia di fare pruning. Aumentare il ad altri modelli che lo richiedono: non c’è numero di input surrogati (gli input surrogati bisogno di scalare i dati e quindi il sono input che non compaiono nell'albero preprocessing è più facile con gli alberi poiché riprodurranno quasi allo stesso modo decisionali l'impurità dei nodi figli degli input selezionati +gli alberi sono robusti ai valori mancanti di xj: nell'albero, una sorta di correlazione tra split). le osservazioni con xj mancanti vengono L'albero può quindi omettere predittori spostate nel nodo figlio più popolato da un importanti solo perché sono input surrogati. nodo padre, o in una nuova categoria "mancante" +robusti all’imputazione dei dati mancanti xj per altri modelli predittivi, usando il target 27  previsto xj dell’albero dove le altre x1, xj-1, xj+1, xp sono input. +Gli alberi decisionali possono essere utilizzati come selettori di modelli flessibili per altri modelli predittivi, poiché le relazioni tra gli input e l'obiettivo sono non lineari o non additive. Il vantaggio di includere i surrogati nella selezione delle variabili è quello di consentire l'inclusione di input che possono essere importanti predittori dell'obiettivo. Vantaggi e svantaggi della segmentazione binaria e del CART +facile leggibilità della regola di classificazione -Sono modelli instabili: piccoli cambiamenti nei +funge da model selection con criteri non dati possono cambiare radicalmente gli split e parametrici per variabili maggiormente di conseguenza anche i confini decisionali e le discriminanti performance. I risultati avranno alta varianza. + non sono sensibili alle differenze di scala, né -Possibilità di cadere in regole di classificazione ai valori fuori scala (outliers) degli input, e semplicistiche neppure alle distribuzioni asimmetriche (per questo non serve preprocessing) +Facile leggibilità della regola di classificazione + Uno dei pochi strumenti robusto ai dati mancanti (oltre alle due regole precedenti citate, un albero assegna un soggetto i con dato mancante a un nodo figlio sulla base di un “surrogate split” (split di variabili surrogate per le quali il dato di i non è mancante) + Fornisce un modo di riclassificare in modo binario gli input continui (o aggregati in due classi quelli categorici) per essere utilizzati in modelli parametrici successivi + Molto veloci nella fase di training e validation (eager, not lazy) Perturb and Combine (P&C): metodi che sfruttano l'instabilità degli alberi e creano modelli più potenti: generano modelli multipli manipolando la distribuzione dei dati o alterando il metodo di costruzione dei risultati (Breiman 1998). Di seguito sono riportati alcuni metodi di perturbazione: ricampionamento; sottocampionamento; aggiunta di rumore; riponderazione adattiva; scelta casuale tra le suddivisioni concorrenti METODI ENSEMBLE DI ALBERI: Gli alberi utilizzati per la regressione e gli alberi utilizzati per la classificazione presentano alcune somiglianze, ma anche alcune differenze, come la procedura utilizzata per determinare dove dividere. Gli ensemble di alberi forniscono modelli con previsioni più accurate dei singoli alberi e sono meno variabili di questi ultimi, cioè sono capaci di ridurre bias e varianza. La classificazione finale dell'ensamble viene effettuata facendo la media (AVE) delle classificazioni dei singoli alberi. Ci sono tre modi diversi per combinare i modelli: Combined model: si calcolano le stime medie basate sui valori previsti provenienti da un certo numero di diversi modelli predittivi, fittando gli M modelli allo stesso dataset di training. Una 28 buona alternativa è lo stacking. L’idea generale è prevedere l’osservazione i usando m=1,…,M modelli Questo metodo è utile anche per migliorare l’accuratezza. Supponiamo di avere i=1,…,25 classificatori di base, ognuno con tasso di errore ε=0.35. Assumendo che sono indipendenti, la probabilità che il classificatore ensemble sbagli una classificazione è la probabilità che più del 50% 25 dei classificatori (13 su 25) faccia una classificazione errata (ε=0.35). ∑25 𝑖 𝑖=13( 𝑖 ) 0.35 (1 − 0.35)25−𝑖 = 0.06. In sostanza, gli ensemble performano meglio di un classificatore di base se il tasso di errore dell’ultimo è 𝑤 𝜏 𝜕𝑤 𝜕𝐽(𝑊) b) il gradiente in 𝑤 𝜏 è positivo > 0 → 𝑤 𝜏+1 < 𝑤 𝜏 𝜕𝑤 Allora la regola del gradiente ci dice di aggiornare i parametri nell'iterazione τ+1 nella direzione 𝝏𝑱(𝑾) opposta del gradiente valutato alla pesa stimata w nell'iterazione τ: 𝒘𝝉+𝟏 = 𝒘𝝉 − = 𝒘𝝉 + 𝝏𝒘𝝉 𝒙′𝒊 𝒆𝝉𝒊 , dove −𝑥𝑖′ 𝑒𝑖𝜏 è il contributo dell’osservazione i al gradiente. La formula è la regola di aggiornamento dei parametri su tutte le osservazioni. Teoricamente bisogna distinguere tra τ e i, ma nel calcolo online di GB i=τ. - Nell'iterazione τ+1 aggiornare i parametri in direzione opposta al gradiente di J(W): se i residui 𝑒𝑖𝜏 > 0, il gradiente J(W) è negativo, i parametri 𝒘𝝉+𝟏 devono aumentare 𝝉 (poiché 𝑥𝑖′𝒘 < 𝒚𝒊 ), e viceversa. - La minimizzazione di J(W) si ha quando il gradiente è nullo, rendendo quindi nullo 𝑥𝑖 𝑒𝑖𝜏 lavorando sui residui 𝑒𝑖𝜏 nella prossima iterazione τ+1 come nuova variabile dipendente. In conclusione, fittando un albero allo step m+1 sui residui dello step m, poiché i residui all'iterazione m 𝑟𝑚,𝑖 sono il gradiente negativo all'iterazione m, ciò equivale a minimizzare iterativamente il gradiente 𝐽(𝛾), la somma dei quadrati residui (RSS), su M iterazioni. Non sfrutta a pieno la regola del gradiente come fanno invece le reti neurali: esse usano il fatto che il gradiente ha segno negativo. Gli svantaggi del gradient boosting è che sono black box quindi non vanno bene in ambito assicurativo ma vanno bene in ambito testuale, di immagini, frodi. Nel bagging i dati cambiano ma il modello resta lo stesso ma in ogni campione bootstrap cambia l’albero, nel boosting non cambia il dataset perché non li campioniamo: non generiamo rumore nelle righe e nelle colonne. Anche la rf genera rumore. GD per target binario: la funzione di perdita, in funzione del target y e della probabilità stimata dell'evento p per l'osservazione i (𝑝 = 𝑦̂) è 𝐽(𝑝) = 𝐿(𝑝𝑖 , 𝑦𝑖 ) = 𝐿𝑖 = − log(𝑙𝑖𝑘𝑒𝑙𝑖ℎ𝑜𝑜𝑑). Quindi, fittare un albero al passo/osservazione i+1 sui residui ei equivale a minimizzare iterativamente il gradiente (L = -log likelihood). Tuning e importanza delle variabili in GB. 1. Profondità di interazione. Qual è J il numero di nodi terminali in un albero per GB? Con J=2 (nodi decisionali), non è consentita alcuna interazione tra le variabili. Con J=3 il modello può includere gli effetti dell'interazione tra un massimo di due variabili, e così via. Hastie et al. commentano che J[4-8] in genere funziona bene e i risultati sono abbastanza insensibili alla scelta di questo intervallo, J=2 è insufficiente per molte applicazioni e J>10 è improbabile che sia necessario. 2. Regolarizzazione: aggiungere una penalità λ alla nuova iterazione, purché λ sia un piccolo multiplo di λ dell’m-esimo albero. 𝑓𝐺𝐵𝑚 (𝑥) = 𝑎𝑚−1 𝑓𝑚−1 (𝑥) + 𝜆𝑎𝑚 𝑓𝑚 , dove il parametro 𝜆 è chiamato "tasso di apprendimento" e indica la velocità dell'iterazione m (simile a lambda nella regressione penalizzata). Empiricamente è stato riscontrato che l'utilizzo di tassi di apprendimento piccoli (come 𝜆0,1) produce miglioramenti drastici nella capacità di generalizzazione del modello rispetto al gradient boosting senza contrazione (𝜆 =1). Tuttavia, ciò avviene al prezzo di un aumento del tempo computazionale sia durante 35  l'addestramento sia durante l'interrogazione: un tasso di apprendimento più basso richiede un maggior numero di iterazioni. 3. Importanza della variabile nel boosting: (media dell'importanza quadratica su tutti gli M alberi fittati). La variabile più importante è stata scalata a 100. GB vs ADA: AdaBoost diminuisce l'errore di classificazione poiché in ogni iterazione lavora su dati di training diversi: ogni iterazione vede "più spesso" i dati erroneamente classificati e poi combina le classificazioni delle varie iterazioni. GB diminuisce la misclassificazione poiché in ogni iterazione lavora sui residui (lavora sugli STESSI dati del training), poi combina le classificazioni delle varie iterazioni. Vantaggi e svantaggi di modellare con tecnica ensemble +accuratezza delle previsioni: Il calcolo della media ponderata dei valori previsti combinando le stime dei modelli è di solito più accurato dei singoli modelli (soprattutto per il boosting). +generalizzazione dei risultati (più stabili): Il motivo è che la media delle stime di previsione di vari modelli o la media delle stime di previsione basate su adattamenti successivi dello stesso modello predittivo con il set di dati è campionata casualmente un numero qualsiasi di volte. Inoltre, viene inserito più rumore nella stima (bootstrap, campionamento casuale degli input), viene fornita una maggiore generalizzazione (soprattutto per Bagging, RF). - modelli molto complicati perché non sono più semplici alberi di decisione. -se sono più complicati sono più difficili da interpretare ed è più difficile interpretare la relazione tra le variabili. Importanza della variabile non molto interpretabile, sembrano artefatti! RETE NEURALE: Le reti neurali cercano di riprodurre il processo di apprendimento del cervello umano, applicando un modello su dati storici per poter ricavare classificazioni o previsioni, e sono caratterizzate da strati di neuroni. Tutti i neuroni di uno strato sono collegati ad ogni neurone dello strato successivo mediante connessioni più o meno spesse. Lo strato di input associa i neuroni alle variabili attive dell’analisi, lo strato di output associa uno o più neuroni alla variabile target (in base alla sua natura). Tra questi due strati possono esserci un certo numero di strati nascosti. Una rete neurale prende in input p variabili X=(X1,…, Xp) e costruisce una funzione non lineare f(X) per prevedere la variabile risposta Y. Abbiamo già costruito modelli previsivi non lineari (alberi, boosting), ma la rete neurale si distingue per la struttura. Le reti neurali sono fondamentali nel deep learning, area di ricerca del ml. Architettura della rete neurale: una rete neurale è costituita dallo strato (layer) di input, cioè l’insieme delle features (4 nell’immagine). Le frecce indicano che ciascuno degli ingressi dallo strato di input alimenta ciascuna delle K unità dello strato di input nascosto (possiamo scegliere K; qui abbiamo scelto 5). Queste K attivazioni dallo strato nascosto confluiscono poi nello strato di uscita (output) f(X). Classificazione delle architetture: Reti feedforward (acicliche): i dati entrano nei nodi di input ed escono dai nodi di output senza cicli: direzione sempre in avanti. Ci sono anche le reti di funzioni base radiali RBF. 36 Il modello rete neurale ha forma PERCETTRONE (NN a strato singolo): rete più semplice. L’input x0 è una colonna di uno (vettore 𝟏) e il parametro w0 è chiamato bias (intercetta). Nel percettrone i p segnali di ingresso/covariate (xi) agiscono insieme attraverso uno specifico peso (wi). In genere, i valori delle variabili di input entrano nel layer di input solo dopo essere stati sottoposti a una trasformazione (standardizzazione/trasformazione). Step di una rete: 1. La rete elabora la somma dei p segnali in ingresso (input), spesso aggiungendo una distorsione (w0) o intercetta: i pesi di input vengono elaborati secondo una combinazione H (i pesi di collegamento in genere sono una combinazione lineare, come in questo caso). 𝑝 𝐻𝑖 = ∑𝑗=1 𝑤𝑗 𝑥𝑖𝑗 + 𝑤0 = 𝑤 𝑇 𝑥𝑖 2. Si trasforma H attraverso una funzione di attivazione non lineare F, il cui risultato è l’output della rete 𝑦̂𝑖 = 𝐹(𝐻𝑖 ) per il soggetto i. nella prima immagine ci sono 5 attivazioni e bisognerà poi stimare tutti i parametri. 𝑝 𝑝 𝑦̂𝑖 = 𝐹 [∑ 𝑤𝑗 𝑥𝑖𝑗 + 𝑤0 ] = 𝐹 [∑ 𝑤𝑗 𝑥𝑖𝑗 ] = 𝐹[𝑤 𝑡 𝑥𝑖 ] 𝑗=1 𝑗=0 3. Se y è continua, dal punto di vista statistico con F fisso devo stimare w minimizzando 𝐸 = ∑𝑖[𝑦𝑖 − 𝐹(𝑤 𝑇 𝑥𝑖 )]2 e quindi il percettrone può essere visto come regressione non lineare. Funzioni di attivazione: F ha il compito di restituire da parte della rete un output che ha un range coerente con quello della variabile target da spiegare (continua, binaria…). Lo strato nascosto calcola le attivazioni che sono trasformazioni non lineari di combinazioni lineari di ingressi X1,..., Xp. Pertanto non vengono osservate direttamente. Le funzioni di attivazione non sono fissate in anticipo, ma vengono apprese durante l'addestramento della rete. Lo strato di uscita è un modello lineare che utilizza queste attivazioni come input, ottenendo una funzione f(X) che sarà utile a dare forma al target. La funzione di attivazione di un percettrone si comporta similmente all’inverso della link function g(.) di un modello lineare generalizzato: GLM 𝑔(𝑦) = 𝑤0 + 𝑤1 𝑥1 → 𝑦 = 𝑔−1 (𝑤0 + 𝑤1 𝑥1 ) 𝐹 = 𝑔−1 = 𝑙𝑜𝑔𝑖𝑡 REG 𝑔(𝑦) = 𝑤0 + 𝑤1 𝑥1 → 𝑦 = 𝑔 (𝑤0 + 𝑤1 𝑥1 ) 𝐹 = 𝑔−1 = 𝑙𝑖𝑛𝑒𝑎𝑟/𝑖𝑑𝑒𝑛𝑡𝑖𝑡𝑦 −1 37  F lineare. La regressione lineare multipla è un percettrone che presuppone essenzialmente l'applicazione ad H di una funzione di attivazione lineare F. La differenza è che la rete stima i pesi w in modo diverso dall'OLS. 𝐻 = ∑𝑗 𝑤𝑗 𝑥𝑗 = 𝑤 ′ 𝑥 = 𝑤0 + 𝑤 𝑇 𝑥 Funzione di attivazione lineare F: 𝑦̂ = 𝐹(𝐻) = 𝐻 = 𝑤′𝑥 F sigmoide/logistica. 𝐻 = ∑𝑗 𝑤𝑗 𝑥𝑗 = 𝑤′𝑥 1 𝑦̂ = 𝐹(𝐻) = 1+𝑒 −𝐻 = [1 + 𝑒 −𝐻 ]−1 𝑒𝑥𝑝(𝑤 ′ 𝑥) La regressione logistica dà 𝑝(𝑥) = [1+𝑒𝑥𝑝(𝑤′𝑥)] come output: exp(𝑤 ′ 𝑥) 𝑦̂ = 𝑝̂ = ′ = [exp(−𝑤 ′ 𝑥) + 1]−1 = [1 + exp(−𝐻)]−1 [1 + exp(𝑤 𝑥)] La regressione logistica è quindi un semplice percettrone con funzione di attivazione F sigmoide. La differenza è che la rete stima i pesi w in modo diverso dalla massima verosimiglianza. Target binario. Viene codificato con (+1, -1) ed è 𝐻 = 𝑤0 + 𝑤 𝑇 𝑥 → 𝐹(𝐻) = 𝑦̂ → 𝑦; F è la funzione segno, che in pratica elabora la combinazione H e in base al segno ricava il valore dell’output (il valore previsto  1). In uscita non fornisce probabilità, ma solo target previsto. Soglia decisionale g(x) della logistica vs percettrone. I due modelli stimano i pesi (w vettore+intercetta) nelle funzioni discriminanti g(x) in modo diverso. Strategie di fitting di una rete neurale per stimare il percettrone. Si ricorre allo slow learning, dove il modello si fitta in modo iterativo usando la discesa del gradiente per minimizzare la 𝒎𝒊𝒏 𝑱(𝑾) funzione a più variabili 𝐽(W); il processo è interrotto se si trova overfitting. { 𝑾 ∈ ℝ𝒏 38 Il metodo del gradiente è un metodo di risoluzione per problemi di ottimizzazione non vincolati ad ogni iterazione τ, supponendo il gradiente diverso da zero (cioè derivata di 𝐽(W) a w). La direzione di ricerca è quella dell’anti- gradiente, cioè 𝑑𝜏 = −∇𝐽(𝑤 𝜏 ), ovvero la direzione che minimizza (massimizza in modulo) il valore della derivata della funzione J nel punto scelto (di solito casualmente). Con η parametro di regolarizzazione/lunghezza del passo di discesa, la regola per aggiornare i parametri 𝒅𝐉(𝐖) è: 𝒘𝝉+𝟏 = 𝒘𝝉 − 𝜼. Illustrazione della discesa del gradiente per θ unidimensionale. La 𝒅𝒘𝝉 funzione obiettivo R(θ) non è convessa e ha due minimi. θ0 è scelto casualmente e si scende a ogni step finché non si raggiunge un minimo globale. Stima del percettrone in un target binario: Per comodità, assorbiremo l'intercetta 𝑤0 aumentando il vettore di caratteristiche 𝑥 con un'ulteriore costante. 1 𝑤 𝑇 𝑥 + 𝑤0 = [𝑤0 𝑤 𝑇 ] [ ] = 𝒂𝑇 𝑥 𝑥 Il nostro obiettivo è trovare un vettore a avendo la seguente regola decisionale con soglia > 0 𝑎𝑙𝑙𝑜𝑟𝑎 𝑦 = +1 → 𝑐𝑙𝑎𝑠𝑠𝑒 1 𝑔(𝑥) = 𝒂?