Regolarizzazione di Tichonov

In matematica, la regolarizzazione di Tichonov, così denominata da nome di Andrej Tichonov, è il metodo più comunemente usato di regolarizzazione di problemi mal posti (ill-posed problems). In statistica il metodo è conosciuto come regressione ridge e, ripetutamente ed indipendentemente riscoperto, è anche variamente noto come il metodo di Tichonov-Miller, metodo di Phillips-Twomey, metodo dell'inversione lineare vincolata o anche metodo di regolarizzazione lineare.

Il risultato è collegato all'algoritmo di Levenberg-Marquardt per problemi di minimi quadrati non lineari.

Quando il problema seguente non è ben posto (sia a causa della non esistenza, sia per la non unicità di $x$):

$A\mathbf {x} =\mathbf {b}$

allora l'approccio usuale è noto come metodo dei minimi quadrati lineari e consiste nel minimizzare lo scarto:

$\|A\mathbf {x} -\mathbf {b} \|^{2}$

dove $\left\|\cdot \right\|$ è la norma euclidea. Tuttavia, in generale, il sistema può essere sottodeterminato o sovradeterminato ($A$ può essere mal condizionata o singolare) e la soluzione, sempre che esista, può non essere univoca. Allo scopo di preferire una particolare soluzione con proprietà desiderate, il termine di regolarizzazione viene incluso nella minimizzazione:

$\|A\mathbf {x} -\mathbf {b} \|^{2}+\|\Gamma \mathbf {x} \|^{2}$

per qualche opportuna scelta della matrice di Tichonov, $\Gamma$. In molti casi, la scelta cade sulla matrice identità $\Gamma =I$, preferendo soluzioni con norma più piccola. In altri casi, operatori passa alto (es. un operatore differenza oppure un operatore discreto di Fourier opportunamente pesato) possono essere impiegati per rafforzare il carattere liscio dell'operatore soggiacente quando è creduto essere principalmente continuo.

Questa regolarizzazione migliora il condizionamento del problema, rendendo possibile una soluzione di tipo numerico. Una soluzione esplicita, denotata come ${\hat {x}}$, è data da:

${\hat {x}}=(A^{T}A+\Gamma ^{T}\Gamma )^{-1}A^{T}\mathbf {b}$

L'effetto di regolarizzazione può essere variato scalando la matrice $\Gamma$. Per cui se $\Gamma =\alpha I$, quando $\alpha$ = 0 si ottiene una soluzione che coincide con quella de-regolarizzata fornita dai minimi quadrati, sempre che (A^TA)⁻¹ esista.

Interpretazione bayesiana

Nonostante all'inizio la scelta della soluzione al problema di regolarizzazione possa sembrare artificiosa, e infatti la matrice $\Gamma$ sembra piuttosto arbitraria, il procedimento può essere giustificato da un punto di vista bayesiano. Si noti che per un problema mal condizionato si devono necessariamente introdurre varie assunzioni aggiuntive allo scopo di ottenere una soluzione stabile.

Statisticamente noi possiamo assumere a priori di sapere che $x$ è una variabile casuale con una distribuzione normale multivariata. Per semplicità supponiamo che la media sia nulla e che ogni componente sia indipendente con deviazione standard $\sigma _{x}$. I nostri dati sono soggetti anche ad errori, e noi supponiamo gli errori in $b$ essere statisticamente indipendenti con media nulla e deviazione standard $\sigma _{b}$. Sotto queste assunzioni la soluzione regolarizzata di Tichonov è la soluzione più probabile in termini di stima di probabilità a posteriori massima (maximum a posteriori probability (MAP) estimate) a partire dai dati e dalla distribuzione a priori di $x$, secondo il teorema di Bayes. La matrice di Tikhonov è allora $\Gamma =\alpha I$ con il coefficiente di Tichonov $\alpha =\sigma _{b}/\sigma _{x}$.

Se l'assunzione di normalità è sostituita mediante le assunzioni di omoschedasticità e non correlazione degli errori, e se assumiamo ancora nulla la media, allora il teorema di Gauss-Markov assicura che la soluzione è la minima stima non distorta

Regolarizzazione generalizzata di Tikhonov

Nel caso di distribuzioni normali multivariate generiche per $x$ e per errore sui dati, è possibile applicare una trasformazione alle variabili per ricondursi al caso esposto sopra. Equivalentemente, si può cercare una $x$ in modo da minimizzare

$\|Ax-b\|_{P}^{2}+\|x-x_{0}\|_{Q}^{2}$

dove $\left\|x\right\|_{Q}^{2}$ sta per norma pesata $x^{T}Qx$ (confronta con la distanza di Mahalanobis). Nell'interpretazione bayesiana $P$ è la matrice di covarianza inversa di $b$, $x_{0}$ è il valore di aspettazione di $x$, e $Q$ la matrice di covarianza inversa di $x$. La matrice di Tichonov è allora data come una fattorizzazione della matrice $Q=\Gamma ^{T}\Gamma$ (es. la fattorizzazione di Cholesky), ed è considerata un filtro di casualizzazione bianco.

Questo problema generalizzato può essere risolto esplicitamente usando la formula

$x_{0}+(A^{T}PA+Q)^{-1}A^{T}P(b-Ax_{0}).$

Regolarizzazione nello spazio di Hilbert

Tipicamente i problemi discreti lineari mal condizionati risultano dalla discretizzazione di equazioni integrali, ed è possibile formulare una regolarizzazione di Tichonov nel contesto infinito-dimensionale originale. In quanto visto più sopra, possiamo interpretare $A$ come un operatore compatto su spazi di Hilbert, e $x$ e $b$ come elementi rispettivamente nel dominio e nel range di $A$. L'operatore $A^{*}A+\Gamma ^{T}\Gamma$ è allora un operatore hermitiano autoaggiunto limitato invertibile.

Collegamenti con la decomposizione ai valori singolari e il filtro di Wiener

Con $\Gamma =\alpha I$, questa soluzione basata sui minimi quadrati può essere analizzata in maniera particolare tramite la decomposizione ai valori singolari. Data la decomposizione ai valori singolari di A

$A=U\Sigma V^{T}$

con valori singolari $\sigma _{i}$, la soluzione regolarizzata di Tichonov può essere espressa come

${\hat {x}}=VDU^{T}b$

dove $D$ ha valori diagonali

$D_{ii}={\frac {\sigma _{i}}{\sigma _{i}^{2}+\alpha ^{2}}}$

mentre tutti gli altri valori sono nulli. Questo dimostra l'effetto del parametro di Tichonov sul numero di condizionamento del problema regolarizzato. Per il caso generalizzato una rappresentazione simile può essere derivata usando una decomposizione ai valori singolari generalizzata.

Infine, la soluzione regolarizzata di Tichonov può essere collegata al filtro di Wiener:

${\hat {x}}=\sum _{i=1}^{q}f_{i}{\frac {u_{i}^{T}b}{\sigma _{i}}}v_{i}$

dove i pesi di Wiener sono $f_{i}={\frac {\sigma _{i}^{2}}{\sigma _{i}^{2}+\alpha ^{2}}}$ e $q$ è il rango di $A$.

Determinazione del fattore di Tichonov

Il valore ottimale del parametro di regolarizzazione $\alpha$ è solitamente incognito e spesso nei problemi pratici è determinato ad hoc. Un possibile approccio si basa sull'interpretazione bayesiana descritta sopra. Altri approcci includono il principio di discrepanza, la cross-validazione, il metodo della curva L, la verosimiglianza massima ristretta e lo stimatore di rischio predittivo non distorto (unbiased predictive risk estimator). Grace Wahba dimostrarono che il parametro ottimale, nel senso di validazione incrociata dei dati del tipo uno-escluso (leave-one-out cross-validation) minimizza:

$G={\frac {\operatorname {RSS} }{\tau ^{2}}}={\frac {\left\|X{\hat {\beta }}-y\right\|^{2}}{\left[\operatorname {Tr} \left(I-X(X^{T}X+\alpha ^{2}I)^{-1}X^{T}\right)\right]^{2}}}$

dove $\operatorname {RSS}$ è la somma dei quadrati residui e $\tau$ è l'effettivo numero di gradi di libertà.

Usando la precedente decomposizione a valori singolari, possiamo semplificare l'espressione sopra:

$\operatorname {RSS} =\left\|y-\sum _{i=1}^{q}(u_{i}'b)u_{i}\right\|^{2}+\left\|\sum _{i=1}^{q}{\frac {\alpha ^{2}}{\sigma _{i}^{2}+\alpha ^{2}}}(u_{i}'b)u_{i}\right\|^{2}$

$\operatorname {RSS} =\operatorname {RSS} _{0}+\left\|\sum _{i=1}^{q}{\frac {\alpha ^{2}}{\sigma _{i}^{2}+\alpha ^{2}}}(u_{i}'b)u_{i}\right\|^{2}$

e

$\tau =m-\sum _{i=1}^{q}{\frac {\sigma _{i}^{2}}{\sigma _{i}^{2}+\alpha ^{2}}}=m-q+\sum _{i=1}^{q}{\frac {\alpha ^{2}}{\sigma _{i}^{2}+\alpha ^{2}}}$

Relazione con la formulazione probabilistica

La formulazione probabilistica di un problema inverso introduce (quando tutte le incertezze sono gaussiane) una matrice di covarianza $C_{M}$ rappresentante le incertezze a priori sui parametri del modello, e una matrice di covarianza $C_{D}$ rappresentate le incertezze sui parametri osservati (vedi, per esempio, Tarantola, 2004 [1]). Nel caso particolare quando queste due matrici sono diagonali e isotrope, $C_{M}=\sigma _{M}^{2}I$ e $C_{D}=\sigma _{D}^{2}I$, e, in questo caso, le equazioni della teoria inversa si riducono alle equazioni sopra, con $\alpha ={\sigma _{D}}/{\sigma _{M}}$.

Storia

La regolarizzazione di Tichonov è stata inventata indipendentemente in vari differenti contesti. Divenne largamente famosa grazie alla sua applicazione alle equazioni integrali a partire dal lavoro di Andrej Tichonov e David L. Phillips. Alcuni autori usano il termine regolarizzazione di Tichonov-Phillips. Il caso a dimensione finita fu esposto da Arthur E. Hoerl, il quale intraprese un approccio statistico, e da Manus Foster, il quale interpretò questo metodo come un filtro di Wiener-Kolmogorov. Conseguentemente a Hoerl, esso è noto nella letteratura statistica come ridge-regressione.

Bibliografia

• (RU) Andrey Nikolayevich Tychonoff, Об устойчивости обратных задач [On the stability of inverse problems], in Doklady Akademii Nauk SSSR, vol. 39, n. 5, 1943, pp. 195–198.
• (EN) A.E. Hoerl, R.W. Kennard, Ridge regression: Biased estimation for nonorthogonal problems, in Technometrics, vol. 42, n. 1, 1970, pp. 80–86, JSTOR 1271436.
• (EN) A. N. Tychonoff, О решении некорректно поставленных задач и методе регуляризации [Solution of incorrectly formulated problems and the regularization method], in Doklady Akademii Nauk SSSR, vol. 151, 1963, pp. 501–504.. Tradotto in Soviet Mathematics, vol. 4, pp. 1035–1038.
• (EN) (EN) A. N. Tychonoff e V. Y. Arsenin, Solution of Ill-posed Problems, Washington, Winston & Sons, 1977, ISBN 0-470-99124-0.
• (EN) (EN) WH Press, SA Teukolsky, WT Vetterling e BP Flannery, Section 19.4. Linear Regularization Methods, in Numerical Recipes: The Art of Scientific Computing, 3ª ed., New York, Cambridge University Press, 2007, ISBN 978-0-521-88068-8. URL consultato il 23 febbraio 2012 (archiviato dall'url originale l'11 agosto 2011).
• (EN) Hansen, P.C., 1998, Rank-deficient and Discrete ill-posed problems, SIAM
• (EN) Hoerl AE, 1962, Application of ridge analysis to regression problems, Chemical Engineering Progress, 58, 54-59.
• (EN) Foster M, 1961, An application of the Wiener-Kolmogorov smoothing theory to matrix inversion, J. SIAM, 9, 387-392
• (EN) Phillips DL, 1962, A technique for the numerical solution of certain integral equations of the first kind, J Assoc Comput Mach, 9, 84-97
• (EN) Tarantola A, 2004, Inverse Problem Theory (free PDF version), Society for Industrial and Applied Mathematics, ISBN 0-89871-572-5
• (EN) Wahba, G, 1990, Spline Models for Observational Data, Society for Industrial and Applied Mathematics

Voci correlate

• Problema mal condizionato
• Regolarizzazione (matematica)