Regularizarea Tihonov

În matematică , regularizarea lui Tihonov , numită după Andrei Tihonov , este cea mai frecvent utilizată metodă de regularizare a problemelor prost puse . În statistici , metoda este cunoscută sub numele de regresie a crestei și, redescoperită în mod repetat și independent, este cunoscută și sub denumirea de metoda Tikhonov-Miller , metoda Phillips-Twomey , metoda de inversare liniară constrânsă sau chiar metoda de regularizare liniară .

Rezultatul este legat de algoritmul Levenberg-Marquardt pentru problemeneliniare cu cele mai mici pătrate .

Când următoarea problemă nu este bine pusă (fie din cauza inexistenței, fie din cauza non-unicității $X$ ${\ displaystyle x}$ $X$ ):

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

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

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

atunci abordarea obișnuită este cunoscută ca metoda liniară a celor mai mici pătrate și constă în minimizarea abaterii :

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

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

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

unde este $\left\|\cdot \right\|$ ${\ displaystyle \ left \ | \ cdot \ right \ |}$ ${\ displaystyle \ left \ | \ cdot \ right \ |}$ este norma euclidiană . Cu toate acestea, în general, sistemul poate fi subdeterminat sau supradeterminat ( $LA$ ${\ displaystyle A}$ $LA$ poate fi prost condiționat sau singular ) și soluția, dacă există, poate să nu fie univocă. Pentru a prefera o anumită soluție cu proprietățile dorite, termenul de regularizare este inclus în minimizare:

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

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

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

pentru o alegere oportună a matricei Tihonov , $\Gamma$ ${\ displaystyle \ Gamma}$ $\Gamă$ . În multe cazuri, alegerea se încadrează în matricea identității $\Gamma =I$ ${\ displaystyle \ Gamma = I}$ ${\ displaystyle \ Gamma = I}$ , preferând soluții cu o normă mai mică. În alte cazuri, operatorii de trecere înaltă (de exemplu, un operator de diferență sau un operator Fourier discret ponderat corespunzător) pot fi folosiți pentru a consolida caracterul neted al operatorului de bază atunci când se crede că este în primul rând continuu.

Această regularizare îmbunătățește condiționarea problemei, făcând posibilă o soluție numerică. O soluție explicită, denumită ${\hat {x}}$ ${\ displaystyle {\ hat {x}}}$ ${\ hat {x}}$ , este dat de:

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

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

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

Efectul de netezire poate fi variat prin scalarea matricei $\Gamma$ ${\ displaystyle \ Gamma}$ $\Gamă$ . Astfel, dacă $\Gamma =\alpha I$ ${\ displaystyle \ Gamma = \ alpha I}$ ${\ displaystyle \ Gamma = \ alpha I}$ , cand $\alpha$ ${\ displaystyle \ alpha}$ $\ alfa$ = 0 obținem o soluție care coincide cu soluția de-regularizată oferită de cele mai mici pătrate, cu condiția să existe (A ^T A) ⁻¹ .

Interpretare bayesiană

Deși la început alegerea soluției la problema de regularizare poate părea artificială, și într-adevăr matricea $\Gamma$ ${\ displaystyle \ Gamma}$ $\Gamă$ pare destul de arbitrar, procedura poate fi justificată din punct de vedere bayesian . Rețineți că pentru o problemă slab condiționată trebuie introduse în mod necesar diferite ipoteze suplimentare pentru a obține o soluție stabilă.

Statistic putem presupune a priori că știm asta $X$ ${\ displaystyle x}$ $X$ este o variabilă aleatorie cu o distribuție normală multivariată . Pentru simplitate, presupunem că media este zero și că fiecare componentă este independentă cu deviație standard $\sigma _{x}$ ${\ displaystyle \ sigma _ {x}}$ ${\ displaystyle \ sigma _ {x}}$ . Datele noastre sunt, de asemenea, supuse erorilor și presupunem erori în $b$ ${\ displaystyle b}$ $b$ să fie statistic independenți cu medie zero și deviație standard $\sigma _{b}$ ${\ displaystyle \ sigma _ {b}}$ ${\ displaystyle \ sigma _ {b}}$ . Conform acestor ipoteze, soluția regularizată Tikhonov este cea mai probabilă soluție în ceea ce privește o estimare a probabilității posterioare maxime ( estimarea maximă a posteriori (MAP)) din date și distribuția anterioară a $X$ ${\ displaystyle x}$ $X$ , conform teoremei lui Bayes . Matricea Tihonov este atunci $\Gamma =\alpha I$ ${\ displaystyle \ Gamma = \ alpha I}$ ${\ displaystyle \ Gamma = \ alpha I}$ cu coeficientul Tihonov $\alpha =\sigma _{b}/\sigma _{x}$ ${\ displaystyle \ alpha = \ sigma _ {b} / \ sigma _ {x}}$ ${\ displaystyle \ alpha = \ sigma _ {b} / \ sigma _ {x}}$ .

Dacă presupunerea normalității este înlocuită de ipotezele de homoskedasticitate și necorelare a erorilor și dacă totuși presupunem nimic mediu, atunci teorema Gauss-Markov asigură că soluția este cea mai puțin părtinitoare estimare

Regularizarea generalizată a Tihonov

În cazul distribuțiilor normale multivariate generice pentru $X$ ${\ displaystyle x}$ $X$ și din greșeală asupra datelor, este posibil să se aplice o transformare a variabilelor pentru a reveni la cazul descris mai sus. În mod echivalent, se poate căuta unul $X$ ${\ displaystyle x}$ $X$ pentru a minimiza

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

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

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

unde este $\left\|x\right\|_{Q}^{2}$ ${\ displaystyle \ left \ | x \ right \ | _ {Q} ^ {2}}$ ${\ displaystyle \ left \ | x \ right \ | _ {Q} ^ {2}}$ înseamnă standard ponderat $x^{T}Qx$ ${\ displaystyle x ^ {T} Qx}$ ${\ displaystyle x ^ {T} Qx}$ (comparați cu distanța Mahalanobis ). În interpretarea bayesiană $P.$ ${\ displaystyle P}$ $P.$ este matricea de covarianță inversă a $b$ ${\ displaystyle b}$ $b$ , $x_{0}$ ${\ displaystyle x_ {0}}$ $x_0$ este valoarea de așteptare a $X$ ${\ displaystyle x}$ $X$ , Și $Î$ ${\ displaystyle Q}$ $Î$ matricea de covarianță inversă a $X$ ${\ displaystyle x}$ $X$ . Matricea Tihonov este apoi dată ca factorizare a matricei $Q=\Gamma ^{T}\Gamma$ ${\ displaystyle Q = \ Gamma ^ {T} \ Gamma}$ ${\ displaystyle Q = \ Gamma ^ {T} \ Gamma}$ (de exemplu, factorizarea Cholesky ) și este considerat un filtru de randomizare alb .

Această problemă genealizată poate fi rezolvată în mod explicit folosind formula

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

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

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

Regularizarea în spațiul Hilbert

De obicei, problemele discrete liniare condiționate necorespunzătoare rezultă din discretizarea ecuațiilor integrale și este posibil să se formuleze o regularizare Tihonov în contextul infinit-dimensional original. După cum s-a văzut mai sus, putem interpreta $LA$ ${\ displaystyle A}$ $LA$ ca operator compact pe spațiile Hilbert și $X$ ${\ displaystyle x}$ $X$ Și $b$ ${\ displaystyle b}$ $b$ ca elemente din domeniu și, respectiv, din gama $LA$ ${\ displaystyle A}$ $LA$ . Operatorul $A^{*}A+\Gamma ^{T}\Gamma$ ${\ displaystyle A ^ {*} A + \ Gamma ^ {T} \ Gamma}$ ${\ displaystyle A ^ {*} A + \ Gamma ^ {T} \ Gamma}$ este apoi un operator hermitian auto-adiacent mărginit inversabil.

Legături cu descompunere de valoare singulară și filtrul Wiener

Cu $\Gamma =\alpha I$ ${\ displaystyle \ Gamma = \ alpha I}$ ${\ displaystyle \ Gamma = \ alpha I}$ , această soluție bazată pe cele mai mici pătrate poate fi analizată într-un mod particular prin descompunerea la valori singulare . Având în vedere descompunerea valorii singulare a lui A

A=U\Sigma V^{T}

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

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

cu valori singulare $\sigma _{i}$ ${\ displaystyle \ sigma _ {i}}$ ${\ displaystyle \ sigma _ {i}}$ , Soluția regularizată a lui Tihonov poate fi exprimată ca

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

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

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

unde este $D.$ ${\ displaystyle D}$ $D.$ are valori diagonale

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

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

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

în timp ce toate celelalte valori sunt nule. Aceasta demonstrează efectul parametrului lui Tihonov asupra numărului condiționat al problemei regularizate. Pentru cazul generalizat, o reprezentare similară poate fi derivată folosind o descompunere generală a valorii singular .

În cele din urmă, soluția regularizată Tikhonov poate fi legată de filtrul Wiener :

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

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

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

unde sunt greutățile vieneze $f_{i}={\frac {\sigma _{i}^{2}}{\sigma _{i}^{2}+\alpha ^{2}}}$ ${\ displaystyle f_ {i} = {\ frac {\ sigma _ {i} ^ {2}} {\ sigma _ {i} ^ {2} + \ alpha ^ {2}}}}$ ${\ displaystyle f_ {i} = {\ frac {\ sigma _ {i} ^ {2}} {\ sigma _ {i} ^ {2} + \ alpha ^ {2}}}}$ Și $q$ ${\ displaystyle q}$ $q$ Este rangul de $LA$ ${\ displaystyle A}$ $LA$ .

Determinarea factorului Tihonov

Valoarea optimă a parametrului de regularizare $\alpha$ ${\ displaystyle \ alpha}$ $\ alfa$ este de obicei necunoscut și adesea în probleme practice este determinat ad hoc . O abordare posibilă se bazează pe interpretarea bayesiană descrisă mai sus. Alte abordări includ principiul discrepanței , validarea încrucișată , metoda curbei L , probabilitatea maximă restrânsă și estimatorul predictiv al riscului imparțial (Estimator al riscului predictiv imparțial). Grace Wahba a demonstrat că parametrul optim, în sensul validării încrucișate de tip one-out, minimizează:

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}}}

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

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

unde este $\operatorname {RSS}$ ${\ displaystyle \ operatorname {RSS}}$ ${\ displaystyle \ operatorname {RSS}}$ este suma pătratelor reziduale și $\tau$ ${\ displaystyle \ tau}$ $\ tau$ este numărul efectiv de grade de libertate .

Folosind descompunerea cu valoare singulară de mai sus, putem simplifica expresia de mai sus:

\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}

{\ displaystyle \ 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}}

{\ displaystyle \ 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}

{\ displaystyle \ 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}}

{\ displaystyle \ 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}}

Și

\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}}}

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

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

Relația cu formularea probabilistică

Formularea probabilistică a unei probleme inverse introduce (când toate incertitudinile sunt gaussiene) o matrice de covarianță $C_{M}$ ${\ displaystyle C_ {M}}$ ${\ displaystyle C_ {M}}$ reprezentând incertitudinile a priori asupra parametrilor modelului și o matrice de covarianță $C_{D}$ ${\ displaystyle C_ {D}}$ ${\ displaystyle C_ {D}}$ reprezintă incertitudinile asupra parametrilor observați (a se vedea, de exemplu, Tarantula, 2004 [1] ). În cazul particular când aceste două matrice sunt diagonale și izotrope, $C_{M}=\sigma _{M}^{2}I$ ${\ displaystyle C_ {M} = \ sigma _ {M} ^ {2} I}$ ${\ displaystyle C_ {M} = \ sigma _ {M} ^ {2} I}$ Și $C_{D}=\sigma _{D}^{2}I$ ${\ displaystyle C_ {D} = \ sigma _ {D} ^ {2} I}$ ${\ displaystyle C_ {D} = \ sigma _ {D} ^ {2} I}$ , și, în acest caz, ecuațiile teoriei inverse se rezumă la ecuațiile de mai sus, cu $\alpha ={\sigma _{D}}/{\sigma _{M}}$ ${\ displaystyle \ alpha = {\ sigma _ {D}} / {\ sigma _ {M}}}$ ${\ displaystyle \ alpha = {\ sigma _ {D}} / {\ sigma _ {M}}}$ .

Istorie

Regularizarea lui Tihonov a fost inventată independent în diferite contexte. A devenit cunoscut pe scară largă datorită aplicării sale la ecuațiile integrale începând cu lucrările lui Andrei Tikhonov și David L. Phillips. Unii autori folosesc termenul de regularizare Tikhonov-Phillips . Cazul cu dimensiuni finite a fost prezentat de Arthur E. Hoerl, care a adoptat o abordare statistică, și de Manus Foster, care a interpretat această metodă ca un filtru Wiener - Kolmogorov . În consecință, pentru Hoerl, este cunoscut în literatura statistică ca regresie de creastă .

Bibliografie

( RU ) Andrey Nikolayevich Tychonoff, Об устойчивости обратных задач [ Despre stabilitatea problemelor inverse ], în Doklady Akademii Nauk SSSR , vol. 39, nr. 5, 1943, pp. 195–198.
( EN ) AE Hoerl, RW Kennard, Ridge regression: Biased estimation for nonorthogonal problems , în Technometrics , vol. 42, n. 1, 1970, pp. 80-86 , JSTOR 1271436 .
( EN ) AN Tychonoff, О решении некорректно поставленных задач и методе регуляризации [ Soluția problemelor formulate incorect și metoda de regularizare ], în volumul Doklady Akademii . 151, 1963, pp. 501-504. . Traducere în matematică sovietică , vol. 4, pp. 1035-1038.
(EN) (EN) AN Tychonoff și VY Arsenin, Solution of Ill-Posed Problems, Washington, Winston & Sons, 1977, ISBN 0-470-99124-0 .
(EN) (EN) WH Press, SA Teukolsky, WT Vetterling și BP Flannery, secțiunea 19.4. Linear Regularization Methods , in Numerical Recipes: The Art of Scientific Computing , ediția a 3-a, New York, Cambridge University Press, 2007, ISBN 978-0-521-88068-8 .
( EN ) Hansen, PC, 1998, Rank-deficient and Discrete prost planted problems , SIAM
( EN ) Hoerl AE, 1962, Aplicarea analizei crestei la problemele de regresie , Chemical Engineering Progress, 58, 54-59.
( EN ) Foster M, 1961, O aplicație a teoriei netezirii Wiener-Kolmogorov la inversarea matricei , J. SIAM, 9, 387-392
(EN) DL Phillips, 1962 O tehnică pentru soluția numerică a anumitor ecuații integrale de primul fel, J Comput Assoc Mach, 9, 84-97
( EN ) Tarantola A, 2004, Inverse Problem Theory ( versiune PDF gratuită ), 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

Elemente conexe

Controlul autorității	LCCN (EN) sh85114019 · BNF (FR) cb12345004c (data)

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică