Wie kann die Gratregressionslösung abgeleitet werden?

40

Ich habe einige Probleme mit der Herleitung der Lösung für die Gratregression.

Ich kenne die Regressionslösung ohne den Regularisierungsbegriff:

β = (X^{T} X)^{- 1} X^{T} y .

$\beta = (X^TX)^{-1}X^Ty.$

$\lambda\|\beta\|_2^2$

β = (X^{T} X + λ I)^{- 1} X^{T} y .

$\beta = (X^TX + \lambda I)^{-1}X^Ty.$

regression least-squares regularization ridge-regression user34790
quelle

23

Es reicht aus, die Verlustfunktion durch Hinzufügen der Strafe zu ändern. In Matrixbegriffen wird die anfängliche quadratische Verlustfunktion Die Herleitung bezüglich führt zu der normalen Gleichung die zum Ridge-Schätzer führt.

(Y - X β)^{T} (Y - X β) + λ β^{T} β .

$(Y - X\beta)^{T}(Y-X\beta) + \lambda \beta^T\beta.$

β

$\beta$

X^{T} Y = (X^{T} X + λ I) β

$X^{T}Y = \left(X^{T}X + \lambda I\right)\beta$

Johnny
quelle

1

Wie kommt es, dass die Ableitung von gleich

λ β^{T} β

$\lambda \beta^T \beta$

λ I β

$\lambda I \beta$

user34790

4

@ user34790 Ist es nicht. Es ist gleich . Aber die 2 annulliert mit ähnlichen 2s auf den anderen Ausdrücken. Natürlich ist der Faktor wie der Faktor 1 in der "regulären" Algebra. Sie können ihn beliebig multiplizieren, ohne etwas zu ändern.

2 λ β

$2\lambda\beta$

I

$I$

Bill

4

@bill: hier brauchst du das , um eine Matrix der richtigen Dimension zu erhalten, damit die Addition mit funktioniert : ist nur ein Skalar

I

$I$

X^{T} X

$X^TX$

λ

$\lambda$

Henry

47

Bauen wir auf dem, was wir wissen : Immer wenn die Modellmatrix , ist die Antwort -vector und der Parameter -vector ist , die Zielfunktion $n\times p$ $X$ $n$ $y$ $p$ $\beta$

f (β) = (y - X β)^{'} (y - X β)

$f(\beta) = (y - X\beta)^\prime(y - X\beta)$

(das ist die Summe der Quadrate der Residuen) wird minimiert, wenn die Normalgleichungen löst $\beta$

(X^{'} X) β = X^{'} y .

$(X^\prime X)\beta = X^\prime y.$

Die Ridge-Regression fügt der Zielfunktion einen weiteren Begriff hinzu (normalerweise nachdem alle Variablen standardisiert wurden, um sie auf eine gemeinsame Basis zu stellen) und fordert zum Minimieren auf

(y - X β)^{'} (y - X β) + λ β^{'} β

$(y - X\beta)^\prime(y - X\beta) + \lambda \beta^\prime \beta$

für eine nicht negative Konstante . Es ist die Summe der Quadrate der Residuen plus ein Vielfaches der Summe der Quadrate der Koeffizienten selbst (was deutlich macht, dass es ein globales Minimum gibt). Da , hat es eine positive Quadratwurzel . $\lambda$ $\lambda\ge 0$ $\nu^2 = \lambda$

Betrachten Sie die Matrix die mit Zeilen erweitert ist, die dem fachen der Identitätsmatrix : $X$ $\nu$ $p\times p$ $I$

X_{*} = (\begin{matrix} X \\ ν I \end{matrix})

$X_{*} = \pmatrix{X \\ \nu I}$

Wenn der Vektor am Ende von ähnliche Weise mit Nullen erweitert wird, fügt das Matrixprodukt in der Zielfunktion zusätzliche Terme der Form zum ursprünglichen Ziel. Deshalb $y$ $p$ $y_{*}$ $p$ $(0 - \nu \beta_i)^2 = \lambda \beta_i^2$

(y_{*} - X_{*} β)^{'} (y_{*} - X_{*} β) = (y - X β)^{'} (y - X β) + λ β^{'} β .

$(y_{*} - X_{*}\beta)^\prime(y_{*} - X_{*}\beta) = (y - X\beta)^\prime(y - X\beta) + \lambda \beta^\prime \beta.$

Aus der Form des Ausdrucks für die linke Hand ergibt sich unmittelbar, dass die Normalgleichungen sind

(X_{*}^{'} X_{*}) β = X_{*}^{'} y_{*} .

$(X_{*}^\prime X_{*})\beta = X_{*}^\prime y_{*}.$

Da wir an das Ende von Nullen , ist die rechte Seite dieselbe wie . Auf der linken Seite wird zum ursprünglichen addiert . Daher vereinfachen sich die neuen Normalgleichungen zu $y$ $X^\prime y$ $\nu^2 I=\lambda I$ $X^\prime X$

(X^{'} X + λ I) β = X^{'} y .

$(X^\prime X + \lambda I)\beta = X^\prime y.$

Abgesehen davon, dass es konzeptionell wirtschaftlich ist - es sind keine neuen Manipulationen erforderlich, um dieses Ergebnis abzuleiten -, ist es auch rechnerisch wirtschaftlich: Ihre Software für gewöhnliche kleinste Fehlerquadrate führt auch eine Kammregression ohne jegliche Änderung durch. (Trotzdem kann es bei großen Problemen hilfreich sein, für diesen Zweck entwickelte Software zu verwenden, da die spezielle Struktur von ausgenutzt wird , um Ergebnisse für ein dichtes Intervall von effizient zu erhalten , sodass Sie untersuchen können, wie die Antworten variieren mit .) $X_{*}$ $\lambda$ $\lambda$

Eine weitere Schönheit dieser Betrachtungsweise ist, wie sie uns helfen kann, die Regression der Grate zu verstehen. Wenn wir die Regression wirklich verstehen wollen, hilft es fast immer, sie geometrisch zu denken: Die Spalten von bilden Vektoren in einem realen Vektorraum der Dimension . Durch anschließende bis , dadurch verlängert sie von -Vektoren zu -Vektoren wir Einbettungs in einem größeren Raum , indem "imaginäre", zueinander orthogonale Richtungen. Die erste Spalte von $X$ $p$ $n$ $\nu I$ $X$ $n$ $n+p$ $\mathbb{R}^n$ $\mathbb{R}^{n+p}$ $p$ $X$ erhält eine kleine imaginäre Komponente der Größe , wodurch sie verlängert und aus dem von den ursprünglichen Spalten erzeugten Raum verschoben wird . Die zweite, dritte, ..., -Spalte wird ebenfalls verlängert und um den gleichen Betrag aus dem ursprünglichen Raum verschoben - aber alle in unterschiedliche neue Richtungen. Folglich wird jede Kollinearität, die in den ursprünglichen Spalten vorhanden ist, sofort aufgelöst. Außerdem nähern sich diese neuen Vektoren umso mehr dem Individuum , je größer wird $\nu$ $p$ $p^\text{th}$ $\nu$ $\nu$ $p$ imaginäre Richtungen: Sie werden immer orthonormaler. Folglich wird die Lösung der Normalgleichungen sofort möglich und wird schnell numerisch stabil, wenn von zunimmt . $\nu$ $0$

Diese Beschreibung des Prozesses schlägt einige neuartige und kreative Ansätze zur Lösung der Probleme vor, für die Ridge Regression entwickelt wurde. Beispielsweise können Sie mit beliebigen Mitteln (wie etwa der Varianzzerlegung, die von Belsley, Kuh und Welsch in ihrem Buch über Regressionsdiagnostik von 1980 , Kapitel 3, beschrieben wurde) Untergruppen von nahezu kollinearen Spalten von identifizieren , in denen jede Untergruppe vorhanden ist ist fast orthogonal zu jedem anderen. Sie angrenzen so viele Zeilen zu müssen (und Nullen ) , da es Elemente in der größten Gruppe, von seinen Geschwistern eine neue „imaginäre“ Dimension zu widmen für jedes Element einer Gruppe zu verschieben weg: Sie brauchen keine imaginäre Dimensionen, um dies zu tun. $X$ $X$ $y$ $p$

whuber
quelle

2

Der letzte Autor des Buches ist Welsch, nicht Waliser.

Mark L. Stone

1

Das hat mich einfach umgehauen. Gibt es eine Diskussion darüber, was passiert, wenn dies außerhalb linearer Modelle verallgemeinert wird, dh auf glms? Die Strafe sollte nicht mit der Gratregression identisch sein ... aber diese Interpretation impliziert, dass sie immer noch ein potenzieller nützlicher Schätzer wäre!

Cliff AB

2

@Cliff Das ist ein sehr interessanter Vorschlag. Da GLM-Schätzungen jedoch komplizierter von abhängen und ihre Schätzer normalerweise nicht in der Form berücksichtigt werden können, wie sie es für OLS sind (wobei und ) kann es schwierig sein, eine nützliche Beziehung zwischen dem Auferlegen einer Straffunktion und dem Modifizieren der Spalten von herzustellen . Insbesondere ist unklar, wie die Werte in erhöht werden müssten, damit dies funktioniert.

X

$X$

\hat{β} = g (X) \cdot h (y)

$\hat\beta = g(X)\cdot h(y)$

g (X) = (X^{'} X)^{- 1} X^{'}

$g(X)=(X^\prime X)^{-1}X^\prime$

h (y) = y

$h(y)=y$

X

$X$

y

$y$

whuber

1

Ja, es würde einige Überlegungen erfordern, um herauszufinden, was die Strafe ist, aber ich bin nicht so besorgt darüber. Die Idee von dem, was

zu verwenden ist im Allgemeinen nicht leicht entweder ... außer vielleicht im Fall der logistischen Regression, wo wir hinzufügen könnten zwei

‚s; eine der Nullen und eine der Einsen. Diese Erweiterung wäre dann eine allgemeinere Version des "+2 Binomialschätzers" (es gibt einen genaueren Namen für diesen Schätzer, den ich ausblenden möchte, wenn Sie

aus einer Binomialverteilung unter Verwendung des posterioren Mittels als schätzen die Schätzung mit einheitlichem Vorrang auf

).

y_{*}

$y_*$

y_{*}

$y_*$

p

$p$

p

$p$

Cliff AB

@Mark Danke für die Korrektur. Sie können sagen, ich war aus dem Gedächtnis ... :-).

whuber

20

min_{β} (Y - β^{T} X)^{T} (Y - β^{T} X) + λ β^{T} β

$\begin{equation} \min_\beta (Y-\beta^T X)^T(Y-\beta^T X)+\lambda \beta^T \beta \end{equation}$

Nun beachte, dass und Gemeinsam gelangen wir zur Bedingung erster Ordnung Isolieren von ergibt die Lösung:

\frac{\partial (Y - β^{T} X)^{T} (Y - β^{T} X)}{\partial β} = - 2 X^{T} (Y - β^{T} X)

$\begin{equation} \frac{\partial (Y-\beta^T X)^T (Y-\beta^T X)}{\partial \beta}=-2X^T(Y-\beta^T X) \end{equation}$

\frac{\partial λ β^{T} β}{\partial β} = 2 λ β .

$\begin{equation} \frac{\partial \lambda \beta^T \beta}{\partial \beta}=2\lambda\beta. \end{equation}$

X^{T} Y = X^{T} X β + λ β .

$\begin{equation} X^TY = X^TX\beta + \lambda\beta. \end{equation}$

β

$\beta$

β = (X^{T} X + λ I)^{- 1} X^{T} Y .

$\begin{equation} \beta = (X^TX+ \lambda I )^{-1}X^T Y. \end{equation}$

pthesling
quelle

9

Ich bin kürzlich im Zusammenhang mit P-Splines auf dieselbe Frage gestoßen, und da das Konzept dasselbe ist, möchte ich eine detailliertere Antwort auf die Herleitung des Gratschätzers geben.

Wir beginnen mit einer bestraften Kriteriumsfunktion, die sich von der klassischen OLS-Kriteriumsfunktion durch ihren Bestrafungsbegriff im letzten Summand unterscheidet:

$Criterion_{Ridge} = \sum_{i=1}^{n}(y_i-x_i^T\beta)^2 + \lambda \sum_{j=1}^p\beta_j^2$

wo

$p=$ Anzahl der im Modell verwendeten Kovariablen
$x_i^T\beta =$ Ihr standardmäßiger linearer Prädiktor
Der erste Summand stellt den MSE dar (Quadratische Abweichung der Vorhersage vom tatsächlichen Wert), den wir wie gewohnt minimieren möchten
Der zweite Summand stellt die Bestrafung dar, die wir auf die Koeffizienten anwenden. Hier befinden wir uns im Ridge-Kontext, der ein euklidisches Distanzmaß und damit den Grad 2 im Strafbegriff impliziert. Im Falle einer Lasso-Bestrafung würden wir einen Grad von 1 anwenden und einen völlig anderen Schätzer ergeben.

Wir können dieses Kriterium in Matrixnotation umschreiben und weiter aufschlüsseln:

$Criterion_{Ridge} = (y-X\beta)^T(y-X\beta) + \lambda\beta^T\beta$

$= y^Ty - \beta^TX^Ty - y^TX\beta+ \beta^Tx^TX\beta + \lambda\beta^T\beta$

$= y^Ty - \beta^TX^Ty - \beta^TX^Ty + \beta^TX^TX\beta + \beta^T\lambda I\beta$ wobei die Identitätsmatrix ist $I$

$= y^Ty - 2\beta^TX^Ty + \beta^T(X^TX + \lambda I)\beta$

Jetzt suchen wir nach der , die unser Kriterium minimiert. Unter anderem verwenden wir die Matrixdifferenzierungsregel die wir können gelten hier als : $\beta$ $\frac{\partial x^TAx}{\partial x} = (A+A^T)x \overset{\text{A symmetric}}{=} 2Ax$ $(X^TX + \lambda I) \in \mathbb{R}^{n \times n}$

$\frac{\partial Criterion_{Ridge} }{\partial\beta} = -2X^Ty + 2(X^TX + \lambda I)\beta \overset{!}{=}0$

$(X^TX + \lambda I)\beta = X^Ty$

$\overset{\text{et voilà}}{\Rightarrow} \hat\beta = (X^TX + \lambda I)^{-1} X^Ty$

Jann Goschenhofer
quelle

@Jahn, können Sie bitte erklären , wie wurde ? Ich denke, Sie haben gerade die Transponierung angewendet, richtig. Sie können die Transponierung jedoch nicht nur auf einen Term anwenden, ohne sie auf alle Gleichungen anzuwenden. Was vermisse ich hier?

y^{T} X β

$y^TX\beta$

β^{T} X^{T} y

$\beta ^TX^Ty$

Theateist

1

@theateist Ein transponierter Skalar ist der gleiche Skalar.

Konstantin

2

Es gibt ein paar wichtige Dinge, die in den gegebenen Antworten fehlen.

Die Lösung für ergibt sich aus der notwendigen Bedingung erster Ordnung: $\beta$ $\frac{\partial f_{ridge}(\beta, \lambda)}{\partial \beta} = 0$ $\beta = (X^TX+ \lambda I )^{-1}X^T Y$ $f_{ridge}(\beta, \lambda)$
$f_{ridge}(\beta, \lambda)$ $f_{OLS}(\beta) = (Y-\beta^T X)^T(Y-\beta^T X)$ $||\beta||^2_2 \leq t$ $f_{ridge}(\beta, \lambda)$ $f_{OLS}(\beta)$ $||\beta||^2_2$

$\beta$

Davor Josipovic
quelle

Wie kann die Gratregressionslösung abgeleitet werden?

Antworten: