Anwenden der Gratregression für ein unterbestimmtes Gleichungssystem?

9

Wenn , kann das Problem der kleinsten Quadrate, das dem Wert von eine sphärische Beschränkung auferlegt , als für ein überbestimmtes System. \ | \ cdot \ | _2 ist die euklidische Norm eines Vektors.y=Xβ+eδβ

min yXβ22s.t.  β22δ2
2

Die entsprechende Lösung für β ist gegeben durch

β^=(XTX+λI)1XTy ,
Dies kann aus der Methode der Lagrange-Multiplikatoren abgeleitet werden ( λ ist der Multiplikator):
L(β,λ)=yXβ22+λ(β22δ2)

Ich verstehe, dass es eine Eigenschaft gibt, die

(XTX+λI)1XT=XT(XXT+λI)1 .
Die rechte Seite ähnelt der Pseudo-Inversen der Regressormatrix X im unbestimmten Fall (mit dem hinzugefügten Regularisierungsparameter λ ). Bedeutet dies, dass derselbe Ausdruck verwendet werden kann, um β für den unbestimmten Fall zu approximieren ? Gibt es im unbestimmten Fall eine separate Ableitung für den entsprechenden Ausdruck, da die sphärische Beschränkungsbeschränkung mit der Zielfunktion redundant ist (Mindestnorm von β ):

min. β2s.t. Xβ=y .
hatmatrix
quelle

Antworten:

12

Beginnend mit der Formulierung des Gratregressionsproblems als

minXβy22+λx22

Sie können das Problem als schreiben

minAβb22

wo

A=[XλI]

und

b=[y0].

Die Matrix hat aufgrund des Teils vollen Spaltenrang . Somit ist das Problem der kleinsten Quadrate eine einzigartige LösungAλI

β^=(ATA)1ATb

Wenn wir dies in und ausschreiben und viele Nullen vereinfachen, erhalten wiryXy

β^=(XTX+λI)1XTy

Nichts in dieser Ableitung hängt davon ab, ob mehr Zeilen oder Spalten hat oder ob den vollen Rang hat. Diese Formel ist somit auf den unbestimmten Fall anwendbar. X.XX

Es ist eine algebraische Tatsache, dass für ,λ>0

(XTX+λI)1XT=XT(XXT+λI)1

Somit haben wir auch die Möglichkeit zu verwenden

β^=XT(XXT+λI)1y .

So beantworten Sie Ihre spezifischen Fragen:

  1. Ja, beide Formeln funktionieren sowohl für den unbestimmten Fall als auch für den überbestimmten Fall. Sie funktionieren auch, wenn kleiner als das Minimum der Anzahl der Zeilen und Spalten von . Die zweite Version kann für unbestimmte Probleme effizienter sein, da in diesem Fall kleiner als ist. X X X T X T X.rank(X)XXXTXTX

  2. Mir ist keine Ableitung der alternativen Version der Formel bekannt, die mit einem anderen Problem mit gedämpften kleinsten Quadraten beginnt und die normalen Gleichungen verwendet. In jedem Fall können Sie es mit etwas Algebra auf einfache Weise ableiten.

Es ist möglich, dass Sie in der Form an das Problem der Gratregression denken

minβ22

vorbehaltlich

Xβy22ϵ.

Diese Version des Ridge-Regressionsproblems führt jedoch einfach zu demselben Problem mit gedämpften kleinsten Quadraten .minXβy22+λβ22

Brian Borchers
quelle
2
Es ist erwähnenswert, was im Limit passiert, wenn auf 0 geht, wenn den vollen Zeilen- oder Spaltenrang hat. Wenn den vollen Spaltenrang hat, erhalten Sie im Limit die Pseudoinverse . Wenn den vollen Zeilenrang hat, erhalten Sie in der Grenze das pseudoinverse . Das funktioniert also wie erwartet. X X ( X T X ) - 1 X T X X T ( X X T ) - 1λXX(XTX)1XTXXT(XXT)1
Brian Borchers
Dies ist eine phänomenal umfassende Antwort und die Ableitung von den erweiterten Arrays (plus Algebra, die ich verpasst habe) ist sehr zufriedenstellend. Ich habe nicht an das Problem der Gratregression in der Form gedacht, die Sie am Ende vorgestellt haben, aber es ist interessant zu sehen, dass es zu derselben Zielfunktion führt. Ein großes Dankeschön!
Hatmatrix
1
Vielen Dank. Ich werde hier einen schamlosen Stecker einfügen. Sie finden diesen (und viele verwandte Materialien) im Lehrbuch über Parameterschätzung und inverse Probleme, die ich gemeinsam mit Rick Aster und Cliff Thurber verfasst habe.
Brian Borchers
1
Lassen Sie mich auch hinzufügen, dass die tatsächliche Berechnung dieser inversen Matrix normalerweise nicht der beste Weg ist, diese Formel zu verwenden. Abhängig von der Größe und der möglichen Sparsamkeit von es möglicherweise viel besser, ein iteratives Schema oder einfach die Cholesky-Faktorisierung der Matrix . X T X + λ I.XXTX+λI
Brian Borchers
Vielen Dank für Ihre Vorschläge! Ich schätze den Verweis auf Ihr Buch, da ich Probleme hatte, ein Texbook zu diesem Material zu finden. Unsere Datengröße ist tatsächlich nicht sehr groß (nur, dass wir dies möglicherweise viele Male auf separate Datensätze anwenden müssen), kann also für die direkte Umkehrung zugänglich sein, aber danke für die zusätzlichen Zeiger!
Hatmatrix