Regressione Lineare. Corso di Intelligenza Artificiale, a.a Prof. Francesco Trovò 27/04/2020

Prof. Francesco Trovò

Corso di Intelligenza Artificiale, a.a. 2019-2020

Regressione Lineare

27/04/2020

Regressione Lineare

Deifnizione di Supervised Learning Regressione Lineare

Tecniche di Regolarizzazione

Supervised Learning: Recap

È il sottocampo del ML più vasto e più analizzato

Dati: un training set composto di coppie 𝐷 = {(𝑥, 𝑡)} estratti da una qualche funzione 𝑓 𝑥 = 𝑡

Trovare: un’approssimazione della funzione 𝑓(⋅) che sia in grado di generalizzare su input non visti nel training set

• I vettori 𝑥 sono anche detti input, predittori, attributi, covariate

• I valori 𝑡 sono anchedetti target, risposte, etichette (labels)

• se il target è ordinale → problema di regressione

• se il target è categorico → problema di classificazione

• se il target è una distribuzione → probability estimation

Interpretazione del Supervised Learning

Vorremmo approssimare la funzione 𝑓 appartenente ad uno spazio ℱ

utilizzando i dati appartenenti al training set 𝐷

Dobbiamo scegliere

• Una loss 𝑙( መ𝑓)

• Un hypothesis space ℋ

• Un metodo di ottimizzazione Potremmo scegliere un hypothesis space più grande → arriveremmo ad approssimare la funzione vera

ℱ

𝑓

𝑓መ

ℋ₁ ℋ₂

Problemi

ℱ

𝑓

ℋ₁ ℋ₂

ℱ

𝑓

𝑓෡₁

ℋ₁ ℋ₂

Loss non appropriata (e.g., per mancanza di dati)

Metodo di ottimizzazione approssimato

𝑓෡₂ 𝑓෡₂

𝑓෡₁

Elementi Fondamentali per un Algoritmo di ML

Esperienza: set di dati che assumiamo essere disponibili per la fase di apprendimento

Es: coppie input/output in un problema di supervised learning

Rappresentazione: spazio in cui vengono ricercate le funzioni approssimanti Es: spazio di tutte le funzioni lineari tra input e target Ƹ𝑡 = 𝑎 𝑥 + 𝑏

Valutazione (loss function): come valuto la bontà di una delle funzioni che appartiene allo spazio

Es: errore assoluto tra target vero e target stimato |𝑡 − Ƹ𝑡|

Ottimizzazione: metodo per trovare la funzione ottima all’interno dello spazio scelto

Es: hill climbing

Dicotomie del ML

• Parametrico vs Nonparametrico

Parametrico: il numero dei parametri da apprendere è fisso e finito Nonparametrico: il numero dei parametri dipende dal training set

• Frequentista vs Bayesiano

Frequentist: usa delle probabilità per modellizzare la distribuzione dei sample

Bayesian: usa la probabilità per modellizzare l’incertezza sulla stima dei paramteri

• Generativo vs Discriminativo

Generative: apprende la distribuzione congiunta 𝑝(𝑥, 𝑡) Discriminative: apprende la probabilità condizionata 𝑝(𝑡|𝑥)

• Empirical Risk Minimization vs Structural Risk Minimization Empirical Risk: errore del modello sul training set

Structural Risk: bilancia errore con la complessità del modello

Scelta del Modello da Utilizzare

Deep NN

Regressione

Vogliamo apprendere una relazione tra un input 𝑥 e un output (target) 𝑡 che assumiamo essere continuo ed ordinato

Esempi:

• Predizione dell’andamento di un’azione

• Predizione dell’età di un utente

• Predire l’effetto di un’azione di un robot

• Predire il valore di una casa

In assenza di componenti stocastiche potrei usare tecniche di interpolazione

Differenti Approcci Risolutivi

• Approccio generativo: modellizzo direttamente la probabilità congiunta di input e target 𝑝(𝑥, 𝑡), poi per decidere il target da dare come predizione calcolo 𝑝 𝑡 𝑥 = ^{𝑝(𝑥,𝑡)}

𝑝(𝑥) e trovo il miglior target medio 𝔼 𝑡 𝑥 =

׬ 𝑡 𝑝 𝑡 𝑥 𝑑𝑡

• Approccio discriminativo: calcolo direttamente la probabilità dei target condizionata 𝑝 𝑡 𝑥 e marginalizzo 𝔼 𝑡 𝑥 = ׬ 𝑡 𝑝 𝑡 𝑥 𝑑𝑡

• Approccio diretto: apprendo direttamente una regola 𝑡(𝑥) che predica l’output dai dati

Una Soluzione: Regressione Lineare

Tutti i processi reali possono essere approssimati tramite funzioni lineari

Non necessariamente essa è la soluzione definitiva ad un problema di regressione

Viene usata normalmente come modulo base di sistemi più complessi o come baseline

Pros:

• Ha una soluzione analitica

• È utile per descrivere concetti che ricorrono nel campo del ML

• Può supportare anche relazioni nonlineari

Rappresentazione: Funzioni Lineari

Approssimimamo la funzione di input/output 𝑓 con una funzione lineare rispetto ad un vettore di parametri 𝒘:

Possiamo anche utilizzare delle funzioni di base per rendere più espressivo lo spazio degli input

Offset

Esempio: Base Quadratica

Valutazione: Loss su Tutto lo Spazio

Come possibile funzione di loss possiamo considerare la loss media rispetto agli input e agli output

Una scelta usuale è la loss quadratica (𝑞 = 2)

Purtroppo non conosciamo la forma della distribuzione congiunta delle coppie input/output

???

Minimizzazione della Loss sul Training Set

Quello che posso fare è minimizzare la loss sui dati che ho a disposizione (essi sono sample della distribuzione congiunta 𝑝(𝑥, 𝑦))

É anche (metà del) la somma dei residui, ovvero di quanto errore faccio sulle predizioni

Ottimizzazione: Differenti Soluzioni

• Ordinary least square

• Stochastic gradient descent

• Maximum likelihood estimation

• Bayesian linear regression

Soluzione Analitica: OLS

Voglio minimizzare la somma dei residui

dove ho

Controllo che esista un punto di minimo

Lo trovo

Ottimizzazione Tramite Gradiente

La soluzione analitica non può essere applicata nel caso in cui abbiamo un numero elevato di parametri (l’inversione della matrice è costosa)

Possiamo usare stochastic gradient descent

ovvero aggiorno il vettore dei pesi rispetto al gradiente della funzione di loss Il metodo di ottimizzazione converge se:

Maximum Likelihood

Un’altra modellizzazione che possiamo adottare è che la funzione sia deterministica e che esista un errore 𝜖 (noise) che modifichi il target

con

La funzione di likelihood di un modello lineare 𝑦 𝑥_𝑛, 𝒘 , dato un training set è data da:

Soluzione della Massimizzazione della Likelihood

Se i dati sono i.i.d. (indipendenti e identicamente distribuiti) considerando la log-likelihood:

Il cui massimo può essere trovato annullando il gradiente

Vantaggi dell’Interpretazione come Massimizzazione della Likelihood

Abbiamo una stima della matrice di covarianza dei parametri:

Dove la stima della varianza del rumore è

Da qui abbiamo una connotazione probabilistica dei parametri

Vantaggi e Svantaggi delle Differenti Soluzioni

• Ordinary least square

• Pro: ho una soluzione analitica

• Contro: devo invertire una matrice potenzialmente grossa

• Stochastic gradient descent

• Pro: posso risolvere problemi anche di grandi dimensioni

• Cons: la velocità di convergenza dipende dal parametro 𝛼

• Maximum likelihood estimation

• Pro: ho una distribuzione esplicita dei parametri stimati

• Contro: stessi dell’OLS

Quante Feature Usare

Se vogliamo usare delle basi allora il modello è:

Sta a noi scegliere le basi giuste

Nessuna base: posso usare OLS o Maximum Likelihood e invertire senza problemi la matrice, ma il modello è poco espressivo

Basi molto complesse: uso gradient descent e il modello è molto espressivo

Scelta del Modello

Underfitting e Overfitting

Modelli troppo semplici non sono in grado di cogliere la complessità del fenomeno → underfitting

Modelli troppo complessi riescono a spiegare in maniera molto accurata i dati che abbiamo ma non sono una buona rappresentazione della funzione

originale → overfitting

Il nostro scopo è avere buoni risultati su dati mai visti: buone capacità di generalizzazione del modello

Idea: valuto il modello su un nuovo dataset (indipendente dai dati su cui lo addestro, detto training set) e vedo come performa per sapere se vi è

overfitting o underfitting

Errore su un Nuovo Dataset

Valuto:

𝐸_𝑅𝑀𝑆 = 2𝑅𝑆𝑆(𝒘^∗) 𝑁

Il modello generalizza in maniera diversa per differenti basi scelte

Voglio progettare un metodo per evitare problemi di overfitting e allo stesso tempo avere un modello abbastanza espressivo

Aumentare le Dimensioni del Training Set

Il fenomeno dell’overfitting diminuisce

La «rule of thumb» è che si i dati dovrebbero essere circa 5-10 volte il numero dei parametri

Di solito i dati sono dati (non ne posso aggiungere altri)

Valori dei Parametri dei Modelli

Idea: voglio contenere il valore assoluto dei parametri ottimi

Includo un nuovo termine nella funzione di loss considerata:

Ad esempio penalizzo le soluzioni con norma || ⋅ ||₂ dei parametri troppo alta

Molto comoda perchè ho ancora una soluzione analitica (ridge regression)

Tecniche di Regolarizzazione

Il Problema è Quasi Risolto

Devo trovare un modo per scegliere il valore del parametro 𝜆

Un’altra Regolarizzazione: LASSO

Possiamo utilizzare differenti metodi per scegliere il termine di regolarizzazione: LASSO regularization

Purtroppo per questa funzione di loss non abbiamo una forma chiusa per la sua risoluzione (problema di ottimizzazione quadratico)

Vantaggio: implicitamente cerca le soluzioni con più parametri possibili con valore zero, ovvero cerca una soluzione sparsa

Meno parametri significa meno variabili da includere nel modello e una maggiore interpretabilità di quelli rimanenti

Interpretazione Grafica della Regolarizzazione

Ridge LASSO