Esercitazione: Approssimazione di dati e Ottimizzazione

Esercitazione: Approssimazione di dati e Ottimizzazione#

Warning

Lo svolgimento di questa esercitazione è obbligatoria per sostenere l’esame. L’esercitazione può essere consegnata in qualiasi momento e NON è richiesto di consegnarla entro una specifica data. L’unico vincolo è che dovrà essere consegnata su Virtuale prima del proprio esame scritto, poiché i risultati di tale esercitazione saranno discussi durante l’esame orale.

L’esercitazione dovrà essere svolta eseguendo tutte le prove richieste, e i risultati dovranno essere collezionati e brevemente commentati tramite una delle due seguenti modalità:

  • Un documento PDF (o Word) contenente uno screenshot dello snippet di codice, i risultati associati a tale snippet, e un commento a tali risultati.

  • Un Notebook di Python come quelli utilizzati a lezione, con celle di codice contenenti le soluzioni agli esercizi, alternate ad un breve commento degli esercizi stessi. Tuttavia, i codici NON devono essere lanciati durante l’esame, ma lo studente deve presentarsi all’esame con il programma già eseguito e con l’output delle celle ancora visibile.

Presentarsi all’esame con codice completo ma ancora da eseguire o senza una versione PDF con risultati già presenti, può compromettere la riuscita dell’esame orale.

Approssimazione di dati#

Scaricare tramite Virtuale il file data_hw.csv, inserirlo nella cartella del progetto (per esempio, supponiamo di inserirlo nel path relativo ./data/data_hw.csv), e caricarlo su Python (utilizzando pandas). Fatto ciò, il dataset si presenterà come un’array composto da 50 righe e 2 colonne. Le due colonne (chiamate x e y), indicano i valori in x e in y di una serie di dati (rumorosi) che si vuole analizzare. Sono note due informazioni sui dati in questione:

  • La funzione che lega y ad x è un polinomio di un certo grado d_true, il cui valore non è noto.

  • I dati in y sono corrotti da del rumore Gaussiano con una certa intensità sigma, anch’essa ignota.

In questo esercizione si vuole approssimare y il meglio possibile, utilizzando le tecniche di approssimazione dati viste a lezione. Tenendo a mente quanto fatto nella rispettiva lezione,

  • Visualizzare (tramite un plot) i dati. Stimare (tramite ragionamento) il possibile grado del polinomio che ha generato i dati.

  • Scelta una stima d per il grado del polinomio, impostare il problema ai minimi quadrati

    \[ \min_{\alpha \in \mathbb{R}^{d+1}} || X \alpha - y ||_2^2, \]

    dove \(\alpha \in \mathbb{R}^{d+1}\) rappresenterà (una volta risolto) il vettore dei coefficienti del polinomio, mentre \(X \in \mathbb{R}^{n \times d+1}\) è la matrice di Vandermonde associata ad \(x\).

  • Risolvere il problema ai minimi quadrati tramite metodo delle Equazioni Normali, utilizzando:

    • Il metodo di Cholesky (dopo aver controllato che la matrice ne soddisfa le ipotesi di applicabilità),

    • Soluzione tramite decomposizione SVD,

    • Algoritmo dei Gradienti Coniugati (CGLS). Confrontare i tre metodi misurando sia il tempo impiegato, che plottando (sullo stesso plot) i polinomi descritti dalla soluzione dei tre metodi, commentando su quale (a occhio) approssima meglio i dati.

  • Ripetere l’esperimento sopra variando il grado d del polinomio approssimante in \(\{ 0, 1, 2, 3, \dots, 8 \}\). Per quale scelta di d il polinomio approssimante meglio approssima i dati?

  • Per d = 6, impostare il problema ai minimi quadrati regolarizzato con Tikhonov,

    \[ \min_{\alpha \in \mathbb{R}^{d+1}} \frac{1}{2}|| X \alpha - y ||_2^2 + \frac{\lambda}{2} || Lx ||_2^2, \]

    con \(L\) matrice identità, e \(\lambda > 0\) parametro di regolarizzazione.

  • Risolvere il problema ai minimi quadrati regolarizzato con Tikhonov utilizzando:

    • Il metodo di Cholesky (dopo aver controllato che la matrice ne soddisfa le ipotesi di applicabilità),

    • Soluzione tramite decomposizione SVD,

    • Algoritmo dei Gradienti Coniugati (CGLS). Visualizzare le soluzioni ottenute sul grafico al variare della scelta del parametro \(\lambda > 0\). Per quale valore di \(\lambda\) il polinomio approssimante meglio approssima i dati?

  • Ripetere l’esperimento sopra variando il grado d del polinomio approssimante.

  • Ripetere l’esperimento sopra utilizzando come matrice di Tikhonov \(L\) la matrice:

    \[\begin{split} L = \begin{bmatrix} 1 & -1 & 0 & 0 & \dots & 0 \\ 0 & 1 & -1 & 0 & \dots & 0 \\ 0 & 0 & 1 & -1 & \dots & 0 \\ 0 & 0 & 0 & 1 & \dots & 0 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ 0 & 0 & 0 & 0 & \dots & -1 \\ 0 & 0 & 0 & 0 & \dots & 1 \\ \end{bmatrix}, \end{split}\]

    ovvero la matrice (di dimensione \(n \times n\), dove \(n\) è uguale al numero di elementi di \(x\)), che ha tutti valori \(1\) sulla diagonale, e valori \(-1\) sulla sovra-diagonale. Come cambiano i risultati precedenti per questa scelta di \(L\)?

  • Sapendo ora che d_true = 4 e alpha_true = np.array([0, 0, 4, 0, -3]), misurare (per alcuni degli esperimenti fatti sopra (i più promettenti)) l’errore relativo tra il valore di alpha calcolato e alpha_true, e confrontare visivamente su grafico i polinomi approssimanti rispetto al polinomio reale (senza rumore) ottenuto tramite alpha_true. Commentare i risultati ottenuti.

Warning

L’errore relativo tra alpha e alpha_true può ovviamente essere calcolato solo nel caso in cui il grado d del polinomio approssimante sia uguale a 4. In tutti gli altri casi, limitarsi ad un confronto visivo sul grafico.

Ottimizzazione con Discesa Gradiente#

Utilizzando il metodo di Discesa del Gradiente (GD) visto a lezione, risolvere il problema di minimo:

\[ \min_{x \in \mathbb{R}^n} f(x), \]

per le seguenti funzioni \(f(x)\):

  1. \(f: \mathbb{R}^2 \to \mathbb{R}\) tale che:

    \[ f(x_1, x_2) = (x_1 - 3)^2 + (x_2 - 1)^2, \]

    con soluzione esatta \(x_{true} = (3, 1)\).

  2. \(f: \mathbb{R}^2 \to \mathbb{R}\) tale che:

    \[ f(x_1, x_2) = 10(x_1 - 1)^2 + (x_2 - 2)^2, \]

    con soluzione esatta \(x_{true} = (1, 2)\).

  3. \(f: \mathbb{R} \to \mathbb{R}\) tale che:

    \[ f(x) = x^4 + x^3 - 2x^2 - 2x, \]

    con soluzione esatta \(x_{true} = 0.92222\).

  • Per ognuna delle funzioni sopra, utilizzare sia il metodo GD con passo fisso sia utilizzando backtracking, provando vari valori del passo \(\alpha > 0\) nel caso in cui non si utilizzi backtracking. Utilizza maxit = 100, tolf = tolx = 1e-6. Per le funzioni 1. e 2., scegliere x0 come vettore di zeri. Confrontare le soluzioni ottenute con e senza backtracking in termini di tempo di esecuzione e velocità di convergenza (misurata in termini di numero di iterazioni richieste per convergere).

  • Visualizzare su un grafico il valore di \(|| \nabla f(x_k) ||_2\) sia per la soluzione con backtracking sia per alcuni valori di \(\alpha\), e commenta su quale metodo performa meglio e perché. La soluzione con backtracking è sempre più veloce di quella con passo fisso?

  • Visualizzare su un grafico il valore dell’errore relativo \(RE(x_{true}, x_k)\) sia per la soluzione con backtracking sia per alcuni valori di \(\alpha\), e commenta i risultati ottenuti.

  • Fare un plot della funzione 3. nell’intervallo \([-3, 3]\), cosa osservi? Provare ad eseguire il metodo GD con e senza backtracking variando il valore di x0. Cosa osservi?

  • Opzionale (Diffile): Fare un contour plot delle funzioni 1. e 2. (vedi documentazione per plt.contour) e visualizza, sullo stesso grafico, il percorso generato dall’algoritmo GD. In particolare, rappresentare sul grafico bi-dimensionale la posizione di tutti gli iterati \(x_k\) dell’algoritmo GD, collegati da un segmento, così da controllare il diverso comportamento di GD quando si utilizza o meno il backtracking.

Contents