Advanced Machine Learning: apprendimento supervisionato e non supervisionato

Advanced Machine Learning

Lisa Giacobazzi 11

Machine Learning

Obiettivo del Machine Learning

OBIETTIVO: Un sistema deve migliorare la sua performance P in una data Task T attraverso l'esperienza E. Vogliamo che i sistemi siano adattivi, robusti e fault tolerant.

Fasi del Machine Learning

1. Ottenere degli esempi di quello che vogliamo
2. Raccogliere dati
3. Stimare una funzione che da un input trovi l'output ‹ Supervised Learning
4. Trovare dei pattern all'interno dei dati ‹ Unsupervised Learning

Supervised Learning

Nel supervised Learning l'algoritmo impara da degli esempi labeled (xi, yi) e stima una funzione che predice y su dei dati non labeled. Possiamo fare Binary Classification, Multiclass Classification e Regressione Queste si distinguono perchè hanno rispettivamente:

• 2 opzioni di output (es. spam / non spam)
• n opzioni finite (es. classificazione di animali)
• output continuo (es. prezzo di una casa)

Esempi pratici di Supervised Learning

• Binary classification: "Questa email è spam?"
• Multiclass classification: "Qual è la specie di questo fiore?"
• Regressione: "Quanto costerà questa casa in base ai metri quadri?"

Unsupervised Learning

Analizza dei dati non labeled e identifica dei pattern nascosti. L'output è la struttura latente che emerge dai dati (es. clustering, riduzione di dimensionalità).

Esempi pratici di Unsupervised Learning

• Clustering: segmentazione di clienti in gruppi simili
• PCA (Principal Component Analysis): riduzione del numero di variabili in un dataset

How to deal with data

1. Osservare i dati: Prima di tutto, raccogliamo dati sul fenomeno che vogliamo studiare o modellare.
2. Riassumere la loro incertezza: I dati non sono mai perfetti: c'è rumore, mancano valori, ci possono essere errori. Quindi si cerca di modellare l'incertezza, ad esempio stimando probabilità, intervalli di confidenza, distribuzioni.
3. Cercare dei constraint e invariances (Prior Knowledge): In questa fase si cerca di trovare regolarità nei dati cercando anche di integrare conoscenza che già abbiamo
4. Trovare un modello che li spieghi: Identificare quale conoscenza abbiamo sul mondo e usarla per costruire il modello, cer- chiamo di costruire un modello matematico o computazionale che spieghi i dati, tenendo conto dell'incertezza e dei vincoli trovati prima.

25. Rappresentare i dati: Rappresentare le feature e modello di classificazione - posso decidere ad esempio se diminuire il numero di features tramite la dimensionality reduction

1. Sfruttare il calcolo: trovare una soluzione tramite tecniche di ottimizzazione e calcolo numerico.
2. Evitare il data bias: garantire che i dati siano rappresentativi e privi di distorsioni sistematiche.

Discriminative VS Generative Learning

L'apprendimento supervisionato stima la relazione tra input e output. I due modelli sono quello discriminativo e quello generativo.

• Discriminativo: Stima P(Y|X), ossia predice direttamente l'etichetta Esempi: Logistic Regression, SVM
• Generativo: Stima P(X, Y), il joint model di X e Y e ne ricava P(Y|X) tramite Bayes Esempio: Naive Bayes

Esempio di Discriminative e Generative Learning

• Discriminativo: un classificatore che distingue email spam da non-spam osservando solo le probabilità condizionate.
• Generativo: un modello che prova a capire come sono fatte le email spam e le email normali (modella tutto).

Estimator

Un estimator è una funzione o metodo che stima un parametro sconosciuto a partire da dati osservati. Hai dei dati, ma non conosci alcuni parametri del fenomeno che li ha generati (es. la media vera, la relazione tra variabili, ecc), un estimator prova a indovinare questi valori a partire dai dati.

• In statistica: stima media, varianza, ecc.
• In ML: è un modello che può essere addestrato su dei dati e che vi fa previsioni (es. regressione lineare).

La linear regression è uno stimatore in quanto trova la linea retta che "riassume" una nuvola di punti.

Bias e Varianza di uno stimatore

• Bias: differenza tra il valore atteso dello stimatore e il valore vero. Il bias misura quanto in media lo stimatore sbaglia rispetto al valore vero che dovrebbe sti- mare. E' la differenza tra l'average estimate e il valore vero. L'aspettativa dello stimatore è la media teorica dello stimatore su infiniti campioni. Estimator of Bernoulli mean: unbiased Estimator of Gaussian Mean: unbiased Estimator of Gaussian variance: biased! Perchè usa la stima della media invece della media vera, perdendo quindi un grado di liberta! Dobbiamo quindi dividere per n-1 invece che per n 1 E(Xi-X)2) n-1
• Varianza: quanto lo stimatore cambia al variare dei dati. 3La varianza misura quanto lo stimatore oscilla da un campione all'altro. L'estimator ideale è unbiased e con una varianza piccola.
• Standard Error: radice della varianza; indica quanto ci si aspetta che la stima fluttui tra i campioni.

Mean Squared Error (MSE)

MSE = Bias2 + Varianza Il Mean Squared Error è uno dei metodi più efficaci per valutare la qualità di uno stimatore in quanto combina il bias e la varianza in un'unica metrica. Misura quanto lo stimatore si discosta dal valore vero, in media, al quadrato. Al quadrato perchè penalizza di più gli errori grandi e mantiene tutto positivo Anche se uno stimatore è biasato, può avere MSE più basso di uno non biasato, se ha varianza molto più piccola.

Bias-Variance Decomposition

È un modo per scomporre l'errore totale di un modello in tre parti:

1. Bias quadrato: È l'errore sistematico, quanto la media delle previsioni del modello si discosta dalla verità. Succede quando il modello è troppo semplice per rappresentare il fenomeno. Esempio: usare una retta per approssimare un fenomeno curvo.
2. Varianza: È l'errore dovuto a quanto il modello cambia se gli dai dati leggermente diversi. Modelli troppo complessi tendono a variare molto, cioè a "overfittare". Esempio: un modello che segue troppo i punti del training set e generalizza male.
3. Rumore: È l'errore intrinseco nei dati, che non può essere eliminato da nessun modello.

Aumentare la complessità del modello tende a ridurre il bias ma aumentare la varianza, e viceversa.

Deep Learning e Funzionamento Generale

Cose principali nell'apprendimento supervisionato (valide anche per deep learning):

1. Training Data: insieme di esempi etichettati (x, y) E X x Y
2. Build a Model: si costruisce una funzione h : X -> Y che cerca di cogliere la relazione tra input e output. Il modello impara.
3. Make Predictions: si usa h per predire l'etichetta di nuovi input

Differenze tra ML e DL

Ma cosa differenzia ML e DL?

1. Nel Deep Learning avremo un Feature Learning automatico invece del feature engi- neering
2. Modelli diversi: reti neurali invece che decision trees, per esempio
3. I dati non dovranno più essere necessariamente numerici o ben strutturati, ma si potranno usare anche immagini, audio e testi grezzi

Loss e True Risk

42.1 Loss e True Risk La loss misura l'errore tra la predizione h(x)e la vera etichetta y = f(x). La loss è la funzione obiettivo che si minimizza durante l'addestramento. E' una funzione che misura l'errore tra la predizione assegnata (fatta dal modello) e la correct labeling function, che è una funzione ideale che simuliamo con le etichette nei dati di input. Si calcola durante la fase di training per aggiornare i pesi (Il bias invece si calcola dopo) Esempio di loss 0-1: L(h(x), y) = < 1 0 se h(x) +y se h(x) = y La loss è una misura empirica. Il true risk rappresenta l'errore medio del modello su tutta la distribuzione D dei dati. E' la probabilità che NON venga predetta la label corretta in un data point random di D RD(h) := P[h(X)= f(X)] = [h(X) +Y] Il true risk di un learner h è quindi il valore atteso della loss, misura la capacità del modello di generalizzare In pratica: quanto spesso sbaglia il modello nel mondo reale.

Empirical Risk

L'empirical risk diventa una stima necessaria quando la distribuzione D è ignota. Se conosces- simo D potremmo calcolare direttamente il true risk del modello h, ma nella pratica non conos- ciamo mai veramente D. Quando non conosciamo la distribuzione, usiamo i dati di training - che sono stati campionati da D - per stimare il rischio empirico, ossia l'errore sul dataset di training: Rs(h) = rischio empirico: ci dice quanto bene il modello ha imparato dai dati di training. L'empirical risk è la miglior proxy che abbiamo del true risk quando non possiamo accedere a tutta la distribuzione dei dati reali, cosa che succede praticamente sempre. Non garantisce che generalizzi bene su dati nuovi. Il rischio empirico è la media della loss sul training set.

Bayes Classifier e Bayes Risk

Il Bayes Classifier opera con l'assunzione che l'input space sia discreto. Il suo obiettivo è trovare una funzione che minimizzi la probabilità di misclassificazione, ossia il true risk. Vuole quindi minimizzare P[h(X) + Y], che può essere espressa come la sommatoria su tutti gli input x del prodotto P(h(X) +Y|X = x)P(X = x) Per ogni specifica x settiamo h(x) in modo che minimizzi la probabilità condizionata P(h(X) + Y|X = x), cosa che corrisponde a massimizzare la probabilità P(h(X) = Y|X = x) Il Bayes Classifier h*(x) è ottimale, in quanto assegna ad ogni x l'etichetta y che massimizza la probabilità a posteriori: 5h*(x) = arg max P[Y = y | X = x] yEY Il Bayes Risk RD(h*) è l'errore minimo teoricamente raggiungibile sotto la distribuzione D. E' il true risk più basso ottenibile. Nessun algoritmo può andare meglio del Bayes Risk. È il limite inferiore dell'errore.

PAC Learning (Probably Approximately Correct)

No Free Lunch Theorem

Senza fare assunzioni sul problema o sulla distribuzione dei dati, nessun algoritmo può garantire di apprendere bene in generale. Implicazione: ogni algoritmo può funzionare bene solo su alcune classi di problemi - non su tutti. Nella teoria dell'apprendimento, si vorrebbe idealmente che l'algoritmo trovi sempre una funzione esattamente corretta, su tutti i dati. Nella pratica questo è irrealizzabile. Quindi si fa una relaxation (rilassamento della garanzia):

In apprendimento automatico esistono quindi diversi livelli di garanzie. Alcuni algoritmi sono solo approximately correct (errore basso, ma senza garanzie probabilistiche). Altri sono only probably correct (corretti solo con alta probabilità, ma magari con errore alto). Gli algoritmi più solidi sono PAC: garantiscono errore basso con alta probabilità. Infine, molti algoritmi moderni funzionano bene in pratica, ma non offrono nessuna garanzia teorica PAC combina entrambe le garanzie: Probably (con confidenza 1 - 8) approximately (er- rore ≤ &) correct. Non possiamo imparare perfettamente in generale, ma possiamo imparare con alta prob- abilità (probably) una funzione quasi corretta (approximately correct). Nel PAC learning il learner opera senza avere una prior knowledge sulla distribuzione D o sul classificatore Bayesiano, ma deve avere:

• La classe di ipotesi ha capacità limitata,
• I dati sono i.i.d. da una distribuzione fissa,
• L'algoritmo ha errore empirico basso.

Il leaner avrà due parametri key

• ¿ (accuracy parameter): tolleranza massima sull'errore
• 8 (confidence parameter): probabilità massima di fallimento del learner

Il learner può avere un dataset di training con m(€, 8) samples, la grandezza di questo dataset dipende quindi dai requisiti di accuratezza e confidenza. L'obbiettivo è di produrre una ipotesi h tale che 6