INTEGRAZIONI DIDATTICHE
I collegamenti che completano il quadro.
Questi approfondimenti sono aggiunti rispetto ai manoscritti. Ogni esempio mette a fuoco una domanda, le ipotesi e un controllo concreto.
Floating point: il computer approssima i numeri
Binary64 rappresenta numeri con una precisione finita: molti decimali non hanno una codifica binaria esatta. Il modello \(\operatorname{fl}(a\circ b)=(a\circ b)(1+\delta)\), con \(|\delta|\le u\), descrive un'operazione arrotondata in condizioni regolari, senza overflow o underflow. Con arrotondamento al più vicino, \(u=2^{-53}\); la distanza fra 1 e il successivo numero rappresentabile è invece \(2^{-52}\).
Sottrarre quantità quasi uguali può rendere visibili gli errori già presenti. Per \(h=10^{-16}\), la formula \(\sqrt{1+h}-1\) può restituire zero in binary64. La forma equivalente \(h/(\sqrt{1+h}+1)\) conserva un valore vicino a \(5\cdot10^{-17}\). Il problema matematico e la formula usata per calcolarlo vanno analizzati separatamente. Goldberg, trattazione originale ripubblicata da Oracle.
Verifica: un risultato con residuo piccolo è sempre accurato?
No. In un problema mal condizionato, un residuo piccolo può accompagnare un errore significativo nella soluzione. Servono scala, norma e condizionamento del problema.
Power method: le moltiplicazioni fanno emergere una direzione
Considera una matrice diagonalizzabile con \(|\lambda_1|>|\lambda_2|\) e un vettore iniziale che contenga la direzione dominante. Ripeti \(y_k=Ax_k\), poi \(x_{k+1}=y_k/\|y_k\|_2\). Nella decomposizione in autovettori, i contributi non dominanti vengono moltiplicati relativamente per potenze di \(\lambda_i/\lambda_1\). Con autovalore dominante negativo può alternarsi il segno: converge la direzione.
Per \(A=\operatorname{diag}(2,1)\) e partenza \((1,1)^T\), prima della normalizzazione il vettore dopo k prodotti è \((2^k,1)^T\). Il rapporto fra seconda e prima componente vale \(2^{-k}\). Se parti da \((0,1)^T\), la componente dominante manca e il metodo rimane nella direzione sbagliata. Controlla anche il residuo \(Ax-\rho x\), con quoziente di Rayleigh \(\rho=x^TAx/(x^Tx)\). Netlib, Power Method.
Verifica: due autovalori con lo stesso modulo dominante garantiscono convergenza?
No. L'ipotesi di separazione in modulo manca. Possono comparire oscillazioni o assenza di una direzione dominante unica.
PageRank: un autovettore che descrive una distribuzione
Usiamo vettori probabilità colonna. La matrice S ha colonne con somma 1; eventuali pagine senza uscite richiedono una distribuzione sostitutiva. Il modello con teletrasporto è \(p_{k+1}=\alpha Sp_k+(1-\alpha)v\), dove \(0<\alpha<1\), \(v\ge0\) e \(\mathbf1^Tv=1\). Con v strettamente positivo il teletrasporto rende unica la distribuzione stazionaria e rimuove i cicli puri del percorso sui link.
Per due pagine che si rimandano a vicenda, \(S=\begin{bmatrix}0&1\\1&0\end{bmatrix}\). Con \(v=(1/2,1/2)^T\), \(\alpha=0.85\) e \(p_0=(1,0)^T\), il primo passo dà \((0.075,0.925)^T\). Il punto fisso è uniforme. Per due distribuzioni la distanza in norma 1 dopo un passo è al più α volte quella precedente: S non espande quella norma. Questa è una ragione concreta della convergenza. Brin e Page, articolo originale.
Verifica: PageRank usa la stessa convenzione righe/colonne in ogni testo?
No. Alcuni usano distribuzioni riga e matrici stocastiche per righe. La formula va trasposta coerentemente; non si possono mescolare le due convenzioni.
SVM: scegliere un separatore con margine grande
Per etichette \(y_i\in\{-1,1\}\), il classificatore lineare usa il segno di \(w^Tx+b\). Nei dati separabili, fissare \(y_i(w^Tx_i+b)\ge1\) elimina l'ambiguità della scala. Il margine fra i due iperpiani di supporto misura \(2/\|w\|_2\). Massimizzarlo equivale a minimizzare \(\tfrac12\|w\|_2^2\) sotto quei vincoli.
In una dimensione, i punti −2 e −1 negativi e 1 e 2 positivi ammettono \(w=1,b=0\). I support vectors sono −1 e 1; il margine totale è 2. Nei dati non separabili si introducono slack non negativi e una penalità: \(\min\tfrac12\|w\|^2+C\sum_i\xi_i\), con \(y_i(w^Tx_i+b)\ge1-\xi_i\). Si assume C > 0. C regola il compromesso fra ampiezza del margine e violazioni; non garantisce da solo buone previsioni. Stanford CS229, note sulle SVM.
Verifica: moltiplicare w e b per 10 cambia il classificatore?
Non cambia il segno, ma cambia il margine funzionale. La normalizzazione dei vincoli permette di confrontare il margine geometrico fra separatori.
Spectral clustering: dai legami a coordinate per i gruppi
Con un grafo non orientato a pesi non negativi, \(W=W^T\), poni \(D_{ii}=\sum_jW_{ij}\) e \(L=D-W\). Vale \(z^TLz=\tfrac12\sum_{ij}W_{ij}(z_i-z_j)^2\): nodi fortemente collegati penalizzano coordinate molto diverse. Gli autovettori associati agli autovalori piccoli descrivono variazioni lente sul grafo.
Due coppie di nodi collegate internamente, senza archi fra coppie, danno due componenti connesse e due autovalori nulli. I vettori indicatore delle componenti appartengono a null(L). Quando i legami fra gruppi sono deboli, un embedding spettrale rende visibile quella struttura. L'algoritmo normalizzato usa \(L_{sym}=I-D^{-1/2}WD^{-1/2}\), con gradi positivi, e specifiche fasi di normalizzazione delle righe prima del clustering. La scelta di W e del Laplaciano conta. von Luxburg, tutorial e derivazioni.
Verifica: per due componenti connesse quanti zeri ha lo spettro del Laplaciano non normalizzato?
Due, contati con molteplicità. Ogni componente consente una costante indipendente senza variazione lungo gli archi.
Core-nilpotente: separare ciò che persiste da ciò che si annulla
Per una matrice quadrata, sia k il primo indice con \(\operatorname{rank}(A^k)=\operatorname{rank}(A^{k+1})\). I sottospazi \(\operatorname{range}(A^k)\) e \(\operatorname{null}(A^k)\) sono complementari e invarianti. In una base adattata, \(Q^{-1}AQ=\operatorname{diag}(C,N)\): C è non singolare e N è nilpotente. La dimensione di C è il rango stabilizzato di Aᵏ, che può differire dal rango di A.
Per \(A=\begin{bmatrix}2&0&0\\0&0&1\\0&0&0\end{bmatrix}\), il rango passa da 2 a 1 fra A e A², poi resta 1. Il blocco C è [2]; il blocco N è \(\begin{bmatrix}0&1\\0&0\end{bmatrix}\), con N²=0. Le potenze separano la direzione che rimane attiva da quelle che vengono annullate. Questa similarità non richiede che A sia diagonalizzabile. Wolfram, definizione e ricostruzione.
Verifica: nell'esempio la dimensione di C è rank(A)=2?
No: è rank(A²)=1, il rango dopo la stabilizzazione. Confondere i due ranghi produce dimensioni sbagliate.
Eigenfaces: la PCA applicata a immagini allineate
Questa è un'applicazione aggiunta: il nome del file Lecture29 la menziona, ma le sue pagine utili trattano soprattutto text mining. Allinea e ridimensiona le immagini, trasformale in vettori e disponi le osservazioni per righe di X. Sottrai l'immagine media μ a ogni riga. Nella SVD di X centrata, le prime colonne di V sono direzioni nello spazio dei pixel: possono essere rimodellate come immagini, le eigenfaces.
Per una nuova immagine q, usa gli stessi passaggi e calcola \(z=V_k^T(q-\mu)\). La ricostruzione è \(\mu+V_kz\). Confrontare coordinate ridotte costituisce una semplice regola di riconoscimento; l'errore di ricostruzione misura invece quanto l'immagine appartiene al sottospazio appreso. Un errore piccolo non dimostra l'identità di una persona. Illuminazione, allineamento e dati di training influenzano il risultato. Turk e Pentland, Eigenfaces for Recognition.
Verifica: con osservazioni per righe le eigenfaces sono colonne di U o di V?
Di V: ogni direzione ha una componente per pixel. U descrive invece le osservazioni nella fattorizzazione.
AdaGrad e Adam: il passo dipende dalla storia dei gradienti
SGD usa una stima del gradiente da un campione o mini-batch. AdaGrad accumula per coordinata i quadrati dei gradienti, \(G_{t,j}=\sum_{s=1}^tg_{s,j}^2\), e, con passo base positivo ed ε > 0, usa un passo proporzionale a \(1/(\sqrt{G_{t,j}}+\epsilon)\). Direzioni spesso attive ricevono passi più piccoli. L'accumulo può però far diventare i passi molto piccoli. Duchi, Hazan e Singer, articolo AdaGrad.
Adam aggiorna medie mobili di gradiente e quadrato del gradiente: \(m_t=\beta_1m_{t-1}+(1-\beta_1)g_t\), \(v_t=\beta_2v_{t-1}+(1-\beta_2)g_t^2\). Le correzioni \(\hat m_t=m_t/(1-\beta_1^t)\) e \(\hat v_t=v_t/(1-\beta_2^t)\) compensano l'inizializzazione a zero. Il passo è \(-\eta\hat m_t/(\sqrt{\hat v_t}+\epsilon)\), componente per componente, con η > 0, ε > 0 e 0 ≤ β₁, β₂ < 1. Questi meccanismi adattano la scala; non garantiscono un minimo globale per una funzione non convessa. Kingma e Ba, articolo Adam.
Verifica: vₜ in Adam è semplicemente il quadrato di mₜ?
No. È una media mobile dei quadrati dei gradienti; media del quadrato e quadrato della media sono operazioni diverse.