Visualizza wikitesto di Regolarizzazione di Tichonov

In [[matematica]], la '''regolarizzazione di Tichonov''', che prende nome da [[Andrej Nikolaevič Tichonov|Andrej Tichonov]], è il metodo più comunemente usato di [[Regolarizzazione (matematica)|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#Caso_non_lineare|minimi quadrati non lineari]].

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

: <math>A\mathbf{x}=\mathbf{b}</math>

allora l'approccio usuale è noto come metodo dei [[Minimi Quadrati|minimi quadrati lineari]] e consiste nel minimizzare lo [[Scarto quadratico|scarto]]:

: <math>\|A\mathbf{x}-\mathbf{b}\|^2 </math>

dove <math>\left \| \cdot \right \|</math> è la [[Norma_euclidea#Struttura_euclidea|norma euclidea]]. Tuttavia, in generale, il sistema può essere sottodeterminato o sovradeterminato (<math>A</math> 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:

: <math>\|A\mathbf{x}-\mathbf{b}\|^2+ \|\Gamma \mathbf{x}\|^2</math>

per qualche opportuna scelta della ''matrice di Tichonov'', <math>\Gamma </math>. In molti casi, la scelta cade sulla [[matrice identità]] <math>\Gamma= I </math>, preferendo soluzioni con [[Norma (matematica)|norma]] più piccola. In altri casi,  operatori ''[[Filtro passa alto|passa alto]]'' (es. un [[Differenza finita|operatore differenza]] oppure un [[Trasformata discreta di Fourier|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 <math>\hat{x}</math>, è data da:
: <math>\hat{x} = (A^{T}A+ \Gamma^{T} \Gamma )^{-1}A^{T}\mathbf{b}</math>
L'effetto di regolarizzazione può essere variato scalando la matrice <math>\Gamma</math>. Per cui se <math>\Gamma = \alpha I</math>, quando <math>\alpha </math> = 0 si ottiene una soluzione che coincide con quella de-regolarizzata fornita dai minimi quadrati, sempre che (A<sup>T</sup>A)<sup>−1</sup> esista.

==Interpretazione bayesiana==
Nonostante all'inizio la scelta della soluzione al problema di regolarizzazione possa sembrare artificiosa, e infatti la matrice <math>\Gamma</math> sembra piuttosto arbitraria, il procedimento può essere giustificato da un [[Inferenza bayesiana|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 <math>x</math> è una [[variabile casuale]] con una [[Distribuzione multivariata|distribuzione normale multivariata]]. Per semplicità supponiamo che la media sia nulla e che ogni componente sia indipendente con [[deviazione standard]] <math>\sigma _x</math>. I nostri dati sono soggetti anche ad errori, e noi supponiamo gli errori in <math>b</math> essere [[statisticamente indipendenti]] con media nulla e deviazione standard <math>\sigma _b</math>. 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  <math>x</math>, secondo il [[teorema di Bayes]]. La matrice di Tikhonov è allora  <math>\Gamma = \alpha I </math> con il coefficiente di Tichonov <math>\alpha = \sigma _b / \sigma _x</math>.

Se l'assunzione di [[distribuzione normale|normalità]] è sostituita mediante le assunzioni di [[omoschedasticità]] e non correlazione degli [[Errore statistico|errori]], e se assumiamo ancora nulla la media, allora il [[teorema di Gauss-Markov]] assicura che la soluzione è la minima [[Bias (statistica)|stima non distorta]]

==Regolarizzazione generalizzata di Tikhonov==
Nel caso di distribuzioni normali multivariate generiche per <math>x</math> e per errore sui dati, è possibile applicare una trasformazione alle variabili per ricondursi al caso esposto sopra. Equivalentemente, si può cercare una <math>x</math> in modo da minimizzare

:<math>\|Ax-b\|_P^2 + \|x-x_0\|_Q^2</math>

dove <math>\left \| x  \right \|_Q^2</math> sta per norma pesata <math>x^T Q x</math> (confronta con la [[distanza di Mahalanobis]]). Nell'interpretazione bayesiana <math>P</math> è la [[Matrice delle covarianze|matrice di covarianza]] inversa di <math>b</math>, <math>x_0</math> è il [[valore di aspettazione]] di <math>x</math>, e <math>Q</math> la matrice di covarianza inversa di <math>x</math>. La matrice di Tichonov è allora data come una fattorizzazione della matrice <math> Q = \Gamma^T \Gamma </math> (es. la [[fattorizzazione di Cholesky]]), ed è considerata un [[Rumore bianco|filtro di casualizzazione bianco]].

Questo problema generalizzato può essere risolto esplicitamente usando la formula

: <math>x_0 + (A^T PA + Q)^{-1} A^T P(b-Ax_0).</math>

==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 <math>A</math> come un [[operatore compatto]] su [[spazio di Hilbert|spazi di Hilbert]], e <math>x</math> e <math>b</math> come elementi rispettivamente nel dominio e nel range di <math>A</math>. L'operatore <math>A^* A + \Gamma^T \Gamma </math> è allora un [[Operatore aggiunto|operatore hermitiano autoaggiunto]] limitato invertibile.

==Collegamenti con la decomposizione ai valori singolari e il filtro di Wiener==
Con <math>\Gamma = \alpha I </math>, 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

:<math>A = U \Sigma V^T</math><!-- Non cancellare "\,": migliora la visualizzazione della formula in certi browsers --->

con valori singolari <math>\sigma _i</math>, la soluzione regolarizzata di Tichonov può essere espressa come

:<math>\hat{x} = V D U^T b</math>

dove <math>D</math> ha valori diagonali

:<math>D_{ii} = \frac{\sigma _i}{\sigma _i ^2 + \alpha ^2}</math>

mentre tutti gli altri valori sono nulli. Questo dimostra l'effetto del parametro di Tichonov sul numero di [[Condizionamento (matematica)|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]]:

:<math>\hat{x} = \sum _{i=1} ^q f_i \frac{u_i ^T b}{\sigma _i} v_i</math>

dove i pesi di Wiener sono <math>f_i = \frac{\sigma _i ^2}{\sigma _i ^2 + \alpha ^2}</math> e <math>q</math> è il [[Rango (algebra lineare)|rango]] di <math>A</math>.

==Determinazione del fattore di Tichonov==
Il valore ottimale del parametro di regolarizzazione <math>\alpha</math> è 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: 

:<math>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}</math>

dove <math>\operatorname{RSS}</math> è la [[somma dei quadrati residui]] e <math>\tau</math> è l'effettivo numero di [[Grado di libertà (statistica)|gradi di libertà]].

Usando la precedente decomposizione a valori singolari, possiamo semplificare l'espressione sopra:
:<math>\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</math>

:<math>\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</math>

e

:<math>\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}</math>

==Relazione con la formulazione probabilistica==
La formulazione probabilistica di un [[problema inverso]] introduce (quando tutte le incertezze sono gaussiane) una matrice di covarianza <math> C_M</math> rappresentante le incertezze ''a priori'' sui parametri del modello, e una matrice di covarianza  <math> C_D</math> rappresentate le incertezze sui parametri osservati (vedi, per esempio, Tarantola, 2004 [http://www.ipgp.jussieu.fr/~tarantola/Files/Professional/SIAM/index.html]). Nel caso particolare quando queste due matrici sono diagonali e isotrope, <math> C_M = \sigma_M^2 I </math> e <math> C_D = \sigma_D^2 I </math>, e, in questo caso, le equazioni della teoria inversa si riducono alle equazioni sopra, con <math> \alpha = {\sigma_D}/{\sigma_M} </math>.

==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 Nikolaevič Tichonov|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 [[Norbert Wiener|Wiener]]-[[Andrej Nikolaevič Kolmogorov|Kolmogorov]]. Conseguentemente a Hoerl, esso è noto nella letteratura statistica come ''ridge-regressione''.

==Bibliografia==
* {{ru}}{{Cita pubblicazione| cognome=Tychonoff | nome=Andrey Nikolayevich | anno=1943 | titolo=Об устойчивости обратных задач |titolotradotto=On the stability of inverse problems | rivista=Doklady Akademii Nauk SSSR | volume=39 | numero=5 | pagine=195–198}}
* {{en}}{{Cita pubblicazione | cognome = Hoerl | nome = A.E. | coautori = R.W. Kennard | anno = 1970 | titolo=Ridge regression: Biased estimation for nonorthogonal problems | rivista=Technometrics | volume=42 | jstor=1271436 | numero=1 | pagine = 80–86}}
* {{en}}{{Cita pubblicazione| cognome=Tychonoff | nome=A. N. | anno=1963 | titolo=О решении некорректно поставленных задач и методе регуляризации |titolotradotto=Solution of incorrectly formulated problems and the regularization method | rivista=Doklady Akademii Nauk SSSR | volume=151 | pagine=501–504}}. Tradotto in {{Cita pubblicazione| rivista=Soviet Mathematics | volume=4 | pagine=1035–1038}}
* {{en}}{{Cita libro| cognome=Tychonoff | nome=A. N. | nome2=V. Y. | cognome2=Arsenin | anno=1977 | titolo=Solution of Ill-posed Problems | url=https://archive.org/details/solutionsofillpo0000tikh | editore=Winston & Sons | città=Washington | isbn=0-470-99124-0 | lingua=en}}
* {{en}}{{Cita libro | cognome=Press | nome=WH | cognome2=Teukolsky | nome2=SA | cognome3=Vetterling | nome3=WT | cognome4=Flannery | nome4=BP | anno=2007 | titolo=Numerical Recipes: The Art of Scientific Computing | edizione=3 | editore=Cambridge University Press | città=New York | capitolo=Section 19.4. Linear Regularization Methods | url=http://apps.nrbook.com/empanel/index.html#pg=1006 | isbn=978-0-521-88068-8 | lingua=en | accesso=23 febbraio 2012 | dataarchivio=11 agosto 2011 | urlarchivio=https://web.archive.org/web/20110811154417/http://apps.nrbook.com/empanel/index.html#pg=1006 | urlmorto=sì }}
* {{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'' ([http://www.ipgp.jussieu.fr/~tarantola/Files/Professional/SIAM/index.html 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)]]

{{Controllo di autorità}}
{{portale|matematica}}

[[Categoria:Teoria degli operatori]]
[[Categoria:decomposizione matriciale]]