Tikhonov-Regularisierung - Tikhonov regularization

Teil einer Serie über
Regressionsanalyse
Modelle
Lineare Regression Einfache Regression Polynomialregression Allgemeines lineares Modell
Verallgemeinertes lineares Modell Diskrete Wahl Binomiale Regression Binäre Regression Logistische Regression Multinomiale logistische Regression Gemischte Logit Probit Multinomiales Probit Logit bestellt Bestelltes Probit Poisson
Mehrstufiges Modell Feste Effekte Zufällige Effekte Lineares Mixed-Effects-Modell Nichtlineares Mixed-Effects-Modell
Nichtlineare Regression Nichtparametrisch Semiparametrisch Robust Quantil Isotonisch Hauptkomponenten Kleinster Winkel Lokal Segmentiert
Fehler-in-Variablen
Einschätzung
Kleinsten Quadrate Linear Nichtlinear
Normal Gewichtet Verallgemeinert
Teilweise Gesamt Nicht negativ Ridge-Regression Regularisiert
Geringste absolute Abweichungen Iterativ neu gewichtet Bayesian Bayes-Multivariat
Hintergrund
Regressionsvalidierung Mittlere und vorhergesagte Reaktion Fehler und Residuen Güte der Anpassung Studentisiertes Residuum Satz von Gauss-Markov
Mathematikportal
v T e

Die Tikhonov-Regularisierung , benannt nach Andrey Tikhonov , ist eine Methode zur Regularisierung von schlecht gestellten Problemen . Auch bekannt als Ridge-Regression , ist es besonders nützlich, das Problem der Multikollinearität bei der linearen Regression zu mildern , das häufig bei Modellen mit einer großen Anzahl von Parametern auftritt. Im Allgemeinen bietet die Methode eine verbesserte Effizienz bei Parameterschätzungsproblemen im Austausch für ein tolerierbares Maß an Bias (siehe Bias-Varianz-Tradeoff ).

Im einfachsten Fall wird das Problem einer nahezu singulären Momentenmatrix dadurch gemildert, dass den Diagonalen positive Elemente hinzugefügt werden , wodurch deren Zustandszahl verringert wird . Analog zum gewöhnlichen Kleinste-Quadrate- Schätzer ist der einfache Ridge-Schätzer dann gegeben durch ${\displaystyle (\mathbf {X} ^{\mathsf {T}}\mathbf {X} )}$

${\displaystyle {\hat{\beta}}_{R}=(\mathbf{X}^{\mathsf{T}}\mathbf{X} +\lambda\mathbf{I})^{-1}\ mathbf {X} ^{\mathsf {T}}\mathbf {y} }$

wobei ist der Regressand , ist die Entwurfsmatrix , ist die Identitätsmatrix und der Ridge-Parameter dient als die Konstante, die die Diagonalen der Momentenmatrix verschiebt. Es kann gezeigt werden, dass dieser Schätzer die Lösung des Problems der kleinsten Quadrate unter der Bedingung ist , die als Lagrange-Operator ausgedrückt werden kann: ${\displaystyle \mathbf{y}}$${\displaystyle\mathbf{X}}$${\displaystyle\mathbf{I}}$${\displaystyle \lambda\geq 0}$ ${\displaystyle \beta^{\mathsf {T}}\beta =c}$

${\displaystyle \min_{\beta}\,(\mathbf {y} -\mathbf {X} \beta )^{\mathsf {T}}(\mathbf {y} -\mathbf {X} \beta ) +\lambda (\beta^{\mathsf{T}}\beta -c)}$

was zeigt, dass dies nichts anderes ist als der Lagrange-Multiplikator der Einschränkung. Im Fall von , in dem die Einschränkung nicht verbindlich ist , reduziert sich der Gratschätzer auf gewöhnliche kleinste Quadrate . Ein allgemeinerer Ansatz zur Tikhonov-Regularisierung wird unten diskutiert. ${\displaystyle \lambda}$${\displaystyle \lambda =0}$

Geschichte

Die Tikhonov-Regularisierung wurde unabhängig in vielen verschiedenen Kontexten erfunden. Es wurde weithin bekannt durch seine Anwendung auf Integralgleichungen aus der Arbeit von Andrey Tikhonov und David L. Phillips. Einige Autoren verwenden den Begriff Tikhonov-Phillips-Regularisierung . Der endlichdimensionale Fall wurde von Arthur E. Hoerl , der einen statistischen Ansatz verfolgte, und von Manus Foster erläutert , der diese Methode als Wiener-Kolmogorov (Kriging) -Filter interpretierte . In Anlehnung an Hörl wird sie in der statistischen Literatur als Ridge-Regression bezeichnet.

Tikhonov-Regularisierung

Angenommen , wir möchten für eine bekannte Matrix und einen bekannten Vektor einen Vektor finden, so dass ${\displaystyle A}$${\displaystyle\mathbf{b}}$${\displaystyle\mathbf{x}}$

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

Der Standardansatz ist die gewöhnliche lineare Regression der kleinsten Quadrate . Erfüllt jedoch keine die Gleichung oder mehr als eine – das heißt, die Lösung ist nicht eindeutig – wird das Problem als schlecht gestellt bezeichnet . In solchen Fällen führt die gewöhnliche Kleinste-Quadrate-Schätzung zu einem überbestimmten oder häufiger einem unterbestimmten Gleichungssystem. Die meisten realen Phänomene haben die Wirkung von Tiefpassfilter in der Vorwärtsrichtung , wo Karten zu . Daher arbeitet bei der Lösung des inversen Problems die inverse Abbildung als Hochpassfilter , der die unerwünschte Tendenz hat, Rauschen zu verstärken ( Eigenwerte /Singulärwerte sind bei der Rückwärtsabbildung am größten, wo sie bei der Vorwärtsabbildung am kleinsten waren). Darüber hinaus annulliert gewöhnliche kleinste Quadrate implizit jedes Element der rekonstruierten Version davon , das sich im Nullraum von befindet , anstatt zuzulassen, dass ein Modell als Prior für verwendet wird . Gewöhnliche kleinste Quadrate versucht die Summe der quadrierten Residuen zu minimieren , die kompakt geschrieben werden kann als ${\displaystyle\mathbf{x}}$${\displaystyle\mathbf{x}}$${\displaystyle A}$${\displaystyle\mathbf{x}}$${\displaystyle\mathbf{b}}$${\displaystyle\mathbf{x}}$${\displaystyle A}$${\displaystyle\mathbf{x}}$

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

wo ist die euklidische Norm . ${\displaystyle \|\cdot \|_{2}}$

Um einer bestimmten Lösung mit wünschenswerten Eigenschaften den Vorzug zu geben, kann in diese Minimierung ein Regularisierungsterm eingefügt werden:

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

für eine geeignet gewählte Tikhonov-Matrix . In vielen Fällen wird diese Matrix als Vielfaches der Identitätsmatrix ( ) gewählt, wobei Lösungen mit kleineren Normen bevorzugt werden ; dies wird als L ₂ -Regularisierung bezeichnet . In anderen Fällen können Hochpassoperatoren (z. B. ein Differenzoperator oder ein gewichteter Fourieroperator ) verwendet werden, um die Glätte zu erzwingen, wenn angenommen wird, dass der zugrunde liegende Vektor größtenteils kontinuierlich ist. Diese Regularisierung verbessert die Konditionierung des Problems und ermöglicht so eine direkte numerische Lösung. Eine explizite Lösung, bezeichnet mit , ist gegeben durch ${\displaystyle \Gamma}$${\displaystyle \Gamma =\alpha I}$${\displaystyle {\hat {x}}}$

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

Die Wirkung der Regularisierung kann durch den Maßstab der Matrix variiert werden . Denn dies reduziert sich auf die unregularisierte Lösung der kleinsten Quadrate, sofern (A ^T A) ⁻¹ existiert. ${\displaystyle \Gamma}$${\displaystyle \Gamma =0}$

Die L ₂ -Regularisierung wird in vielen Kontexten neben der linearen Regression verwendet, wie z. B. der Klassifikation mit logistischer Regression oder Support-Vektor-Maschinen und der Matrixfaktorisierung.

Generalisierte Tikhonov-Regularisierung

Für allgemeine multivariate Normalverteilungen für und den Datenfehler kann man eine Transformation der Variablen anwenden, um sie auf den obigen Fall zu reduzieren. Äquivalent kann man nach einem suchen, um zu minimieren ${\displaystyle x}$${\displaystyle x}$

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

wobei wir früher für die gewichtete Norm zum Quadrat standen (vergleiche mit der Mahalanobis-Distanz ). In der Bayes'schen Interpretation ist die inverse Kovarianzmatrix von , ist der Erwartungswert von und ist die inverse Kovarianzmatrix von . Die Tikhonov-Matrix wird dann als Faktorisierung der Matrix (zB die Cholesky-Faktorisierung ) angegeben und gilt als Aufhellungsfilter . ${\displaystyle \|x\|_{Q}^{2}}$${\displaystyle x^{\top }Qx}$${\displaystyle P}$${\displaystyle b}$${\displaystyle x_{0}}$${\displaystyle x}$${\displaystyle Q}$${\displaystyle x}$${\displaystyle Q=\Gamma^{\top}\Gamma}$

Dieses verallgemeinerte Problem hat eine optimale Lösung , die explizit mit der Formel geschrieben werden kann ${\displaystyle x^{*}}$

${\displaystyle x^{*}=(A^{\top }PA+Q)^{-1}(A^{\top}Pb+Qx_{0}),}$

oder gleichwertig

${\displaystyle x^{*}=x_{0}+(A^{\top }PA+Q)^{-1}(A^{\top }P(b-Ax_{0})).}$

Lawrentjew-Regularisierung

In einigen Situationen kann man die Transponierung vermeiden , wie von Michail Lawrentjew vorgeschlagen . Wenn zum Beispiel symmetrisch positiv definit ist, also auch seine Umkehrung , die somit verwendet werden kann, um die gewichtete Norm quadriert in der verallgemeinerten Tikhonov-Regularisierung aufzustellen , was zu Minimierung führt ${\displaystyle A^{\top }}$${\displaystyle A}$${\displaystyle A=A^{\top }>0}$${\displaystyle A^{-1}}$${\displaystyle \|x\|_{P}^{2}=x^{\top }A^{-1}x}$

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

oder, äquivalent bis zu einem konstanten Term,

${\displaystyle x^{\top}(A+Q)x-2x^{\top}(b+Qx)}$.

Dieses Minimierungsproblem hat eine optimale Lösung , die explizit mit der Formel geschrieben werden kann ${\displaystyle x^{*}}$

${\displaystyle x^{*}=(A+Q)^{-1}(b+Qx_{0})}$,

was nichts anderes als die Lösung des verallgemeinerten Tikhonov-Problems ist, wobei ${\displaystyle A=A^{\top}=P^{-1}.}$

Die Lavrentyev-Regularisierung, falls zutreffend, ist gegenüber der ursprünglichen Tikhonov-Regularisierung vorteilhaft, da die Lavrentyev-Matrix besser konditioniert werden kann, dh eine kleinere Bedingungszahl hat als die Tikhonov-Matrix${\displaystyle A+Q}$${\displaystyle A^{\top }A+\Gamma^{\top}\Gamma.}$

Regularisierung im Hilbertraum

Typischerweise resultieren diskrete lineare schlecht konditionierte Probleme aus der Diskretisierung von Integralgleichungen , und man kann eine Tikhonov-Regularisierung im ursprünglichen unendlich-dimensionalen Kontext formulieren. In der oben können wir interpretieren als kompakten Operator auf Hilbert - Räumen , und und als Elemente in der Domäne und die Reichweite . Der Operator ist dann ein selbstadjungierter beschränkter invertierbarer Operator. ${\displaystyle A}$${\displaystyle x}$${\displaystyle b}$${\displaystyle A}$${\displaystyle A^{*}A+\Gamma^{\top}\Gamma}$

Beziehung zur Singulärwertzerlegung und Wiener Filter

Mit kann diese Kleinste-Quadrate-Lösung in besonderer Weise mit der Singulärwertzerlegung analysiert werden . Gegeben sei die Singulärwertzerlegung ${\displaystyle \Gamma =\alpha I}$

${\displaystyle A=U\Sigma V^{\top }}$

mit singulären Werten kann die regularisierte Tikhonov-Lösung ausgedrückt werden als ${\displaystyle \sigma_{i}}$

${\displaystyle {\hat{x}}=Bildschirm^{\top}b,}$

wo hat Diagonalwerte ${\displaystyle D}$

${\displaystyle D_{ii}={\frac {\sigma_{i}}{\sigma_{i}^{2}+\alpha^{2}}}}$

und ist an anderer Stelle null. Dies demonstriert die Wirkung des Tikhonov-Parameters auf die Bedingungszahl des regularisierten Problems. Für den verallgemeinerten Fall kann eine ähnliche Darstellung unter Verwendung einer verallgemeinerten Singulärwertzerlegung abgeleitet werden .

Schließlich hängt es mit dem Wiener-Filter zusammen :

${\displaystyle {\hat{x}}=\sum_{i=1}^{q}f_{i}{\frac {u_{i}^{\top}b}{\sigma_{i}} }v_{i},}$

wobei die Wiener-Gewichte sind und der Rang von ist . ${\displaystyle f_{i}={\frac {\sigma_{i}^{2}}{\sigma_{i}^{2}+\alpha^{2}}}}$${\displaystyle q}$${\displaystyle A}$

Bestimmung des Tikhonov-Faktors

Der optimale Regularisierungsparameter ist normalerweise unbekannt und wird bei praktischen Problemen oft durch ein Ad-hoc- Verfahren bestimmt. Ein möglicher Ansatz beruht auf der unten beschriebenen Bayes'schen Interpretation. Andere Ansätze umfassen das Diskrepanzprinzip , Kreuzvalidierung , L-Kurven-Methode , eingeschränkte maximale Wahrscheinlichkeit und unverzerrter prädiktiver Risikoschätzer . Grace Wahba hat bewiesen, dass der optimale Parameter im Sinne einer Leave-One-Out-Kreuzvalidierung minimiert ${\displaystyle\alpha}$

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

Dabei ist die Restsumme der Quadrate und die effektive Anzahl der Freiheitsgrade . ${\displaystyle \operatorname {RSS} }$${\displaystyle \tau}$

Mit der vorherigen SVD-Zerlegung können wir den obigen Ausdruck vereinfachen:

${\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} =\operatorname {RSS} _{0}+\left\|\sum _{i=1}^{q}{\frac {\alpha ^{2}}{\sigma _ {i}^{2}+\alpha^{2}}}(u_{i}'b)u_{i}\right\|^{2},}$

und

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

Bezug zur probabilistischen Formulierung

Die probabilistische Formulierung eines inversen Problems führt (wenn alle Unsicherheiten gaußförmig sind) eine Kovarianzmatrix ein, die die a-priori- Unsicherheiten der Modellparameter darstellt, und eine Kovarianzmatrix, die die Unsicherheiten der beobachteten Parameter darstellt. In dem speziellen Fall , wenn diese beiden Matrizen sind diagonal und isotrop ist , und , und, in diesem Fall reduzieren sich die Gleichungen der inversen Theorie den Gleichungen oben, mit . ${\displaystyle C_{M}}$${\displaystyle C_{D}}$${\displaystyle C_{M}=\sigma_{M}^{2}I}$${\displaystyle C_{D}=\sigma_{D}^{2}I}$${\displaystyle \alpha ={\sigma_{D}}/{\sigma_{M}}}$

Bayessche Interpretation

Obwohl die Wahl der Lösung dieses regularisierten Problems auf den ersten Blick künstlich erscheinen mag und die Matrix tatsächlich ziemlich willkürlich erscheint, lässt sich der Prozess aus bayesianischer Sicht rechtfertigen . Beachten Sie, dass für ein schlecht gestelltes Problem notwendigerweise einige zusätzliche Annahmen eingeführt werden müssen, um eine eindeutige Lösung zu erhalten. Statistisch wird die A- priori-Wahrscheinlichkeitsverteilung von manchmal als multivariate Normalverteilung angesehen . Der Einfachheit halber werden hier die folgenden Annahmen gemacht: die Mittelwerte sind null; ihre Komponenten sind unabhängig; die Komponenten haben die gleiche Standardabweichung . Die Daten sind auch fehlerbehaftet, und die Fehler in werden ebenfalls als unabhängig mit Nullmittelwert und Standardabweichung angenommen . Unter diesen Annahmen ist die Tikhonov-regularisierte Lösung die wahrscheinlichste Lösung, wenn die Daten und die a-priori- Verteilung von nach dem Satz von Bayes gegeben sind . ${\displaystyle \Gamma}$${\displaystyle x}$ ${\displaystyle \sigma_{x}}$${\displaystyle b}$${\displaystyle \sigma_{b}}$${\displaystyle x}$

Wenn die Annahme der Normalität durch Annahmen der Homoskedastizität und der Unkorreliertheit der Fehler ersetzt wird und man immer noch einen Mittelwert von Null annimmt, dann folgt dem Gauß-Markov-Theorem , dass die Lösung der minimale unverzerrte lineare Schätzer ist .

Siehe auch

• Der LASSO-Schätzer ist eine weitere Regularisierungsmethode in der Statistik.
• Elastische Netzregularisierung
• Matrix-Regularisierung

Anmerkungen

Verweise

Weiterlesen

• Gruber, Marvin (1998). Verbesserung der Effizienz durch Schrumpfung: Die Regressionsschätzer nach James-Stein und Ridge . Boca Raton: CRC-Presse. ISBN 0-8247-0156-9.
• Kress, Rainer (1998). "Tikhonov-Regularisierung" . Numerische Analyse . New York: Springer. S. 86–90. ISBN 0-387-98408-9.
• Drücken Sie, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Abschnitt 19.5. Lineare Regularisierungsmethoden" . Numerische Rezepte: Die Kunst des wissenschaftlichen Rechnens (3. Aufl.). New York: Cambridge University Press. ISBN 978-0-521-88068-8.
• Saleh, AK Md. Ehsanes; Arashi, Mohammed; Kibria, BM Golam (2019). Theorie der Ridge-Regressionsschätzung mit Anwendungen . New York: John Wiley & Söhne. ISBN 978-1-118-64461-4.
• Taddy, Matt (2019). "Regularisierung" . Business Data Science: Kombination von maschinellem Lernen und Wirtschaftswissenschaften zur Optimierung, Automatisierung und Beschleunigung von Geschäftsentscheidungen . New York: McGraw-Hill. S. 69–104. ISBN 978-1-260-45277-8.