Regolarizzazione di Tichonov

Da Wikipedia, l'enciclopedia libera.

In matematica, la regolarizzazione di Tichonov, così denominata da nome di Andrey Tichonov, è il metodo più comunemente usato di regolarizzazione di problemi mal condizionati (ill-posed problems).

In statistica, il metodo è noto come regressione ridge, e, ripetutamente ed indipendentemente riscoperto, è anche variamente noto come il metodo di Tichonov-Miller, il metodo di Phillips-Twomey, il metodo dell'inversione lineare vincolata, e il metodo di regolarizzazione lineare.

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

Quando il problema seguente non è ben condizionato (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 (ATA)−1 esista.

Interpretazione bayesiana[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

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 Q x (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 genealizzato 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[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

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} = V D U^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[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

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 Andrey 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.

Riferimenti[modifica | modifica wikitesto]

  • Andrey Nikolayevich Tychonoff, Об устойчивости обратных задач [On the stability of inverse problems] in Doklady Akademii Nauk SSSR, vol. 39, nº 5, 1943, pp. 195–198.
  • 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) A. N. Tychonoff e V. Y. Arsenin, Solution of Ill-posed Problems, Washington, Winston & Sons, 1977, ISBN 0-470-99124-0.
  • Hansen, P.C., 1998, Rank-deficient and Discrete ill-posed problems, SIAM
  • Hoerl AE, 1962, Application of ridge analysis to regression problems, Chemical Engineering Progress, 58, 54-59.
  • 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.
  • Foster M, 1961, An application of the Wiener-Kolmogorov smoothing theory to matrix inversion, J. SIAM, 9, 387-392
  • 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) 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.
  • Tarantola A, 2004, Inverse Problem Theory (free PDF version), Society for Industrial and Applied Mathematics, ISBN 0-89871-572-5
  • Wahba, G, 1990, Spline Models for Observational Data, Society for Industrial and Applied Mathematics

Voci correlate[modifica | modifica wikitesto]

matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica