Ich implementiere Ridge Regression in einem Python / C-Modul und bin auf dieses "kleine" Problem gestoßen. Die Idee ist, dass ich die effektiven Freiheitsgrade mehr oder weniger gleichmäßig verteilt abtasten möchte (wie die grafische Darstellung auf Seite 65 unter "Elemente des statistischen Lernens" ), dh Beispiel: wobei die Eigenwerte der Matrix aus bis \ mathrm {df} (\ lambda _ {\ min}) = p . Eine einfache Möglichkeit, die erste Grenze festzulegen, besteht darin, \ lambda _ {\ max} = \ sum_i ^ p d_i ^ 2 / c (unter der Annahme von \ lambda _ {\ max} \ gg d_i ^ 2 ) zu lassen, wobei c
Wie aus dem Titel hervorgeht, muss ich von bis in einer gewissen Skala abtasten, sodass (ungefähr) abgetastet wird, z Intervalle von bis ... gibt es eine einfache Möglichkeit, dies zu tun? Ich dachte, die Gleichung für jedes mit einer Newton-Raphson-Methode zu lösen , aber dies fügt zu viele Iterationen hinzu, insbesondere wenn groß ist. Irgendwelche Vorschläge?
quelle
Antworten:
Das ist eine lange Antwort . Lassen Sie uns hier eine Kurzgeschichtenversion davon geben.
R
Code ohne Optimierungsversuche kann in wenigen Sekunden ein Raster der Größe 100 mit 100.000 berechnen . Sorgfältig geschriebener Code würde dies um mindestens 2–3 Größenordnungen reduzieren.C
Im Folgenden werden zwei Schemata angegeben, um eine monotone Konvergenz zu gewährleisten. Man verwendet die unten gezeigten Grenzen, die gelegentlich helfen, ein oder zwei Newton-Schritte zu sparen.
Beispiel : und ein einheitliches Gitter für die Freiheitsgrade der Größe 100. Die Eigenwerte sind paretoverteilt und daher stark verzerrt. Unten finden Sie Tabellen mit der Anzahl der Newton-Schritte, um die einzelnen Wurzeln zu finden.p=100000
Es wird im Allgemeinen keine geschlossene Lösung dafür geben , aber es ist eine Menge Struktur vorhanden, die verwendet werden kann, um sehr effektive und sichere Lösungen unter Verwendung von Standardmethoden zum Auffinden von Wurzeln zu erzeugen.
Bevor wir uns zu sehr mit Dingen , wollen wir einige Eigenschaften und Konsequenzen der Funktion
Eigenschaft 0 : ist eine rationale Funktion von . (Dies geht aus der Definition hervor.) Konsequenz 0 : Es gibt keine allgemeine algebraische Lösung zum Finden der Wurzel . Dies liegt daran, dass es ein äquivalentes Polynomwurzelfindungsproblem des Grades Wenn also nicht extrem klein ist (dh weniger als fünf), gibt es keine allgemeine Lösung. Wir brauchen also eine numerische Methode. λ d f ( λ ) - y = 0 p pdf λ
df(λ)−y=0 p p
Eigenschaft 1 : Die Funktion ist konvex und nimmt bei . (Nehmen Sie Derivate.) Konsequenz 1 (a) : Newtons Algorithmus zum Auffinden von Wurzeln wird sich in dieser Situation sehr gut verhalten . Sei die gewünschten Freiheitsgrade und die entsprechende Wurzel, dh . Insbesondere wenn wir mit einem Anfangswert (also ) beginnen, konvergiert die Folge von Newton-Schritt-Iterationen monoton gegen einzigartige Lösung λ ≥ 0 y λ 0 y = d f ( λ 0 ) λ 1 < λ 0 d f ( λ 1 ) > y λ 1 , λ 2 , … λ 0 λ 1 > λ 0 λ 2 ≤ λ 0 d f d f λ d f y 1 y 2 < ydf λ≥0
y λ0 y=df(λ0) λ1<λ0 df(λ1)>y λ1,λ2,… λ0 .
λ1>λ0 λ2≤λ0 df df λ Dies ist ein wichtiger Grund, lieber links von der gewünschten Wurzel zu beginnen. Andernfalls müssen wir noch einmal überprüfen, ob der Newton-Schritt zu keinem negativen Wert für die geschätzte Wurzel geführt hat, was dazu führen kann, dass wir uns irgendwo in einem nicht konvexen Teil von .
Konsequenz 1 (c) : Sobald wir die Wurzel für ein und dann von einem nach der Wurzel suchen , verwenden wir so dass unsere anfängliche Vermutung ist das links von der zweiten Wurzel. Somit ist unsere Konvergenz von dort aus garantiert monoton.df
y1 λ 1 d f ( λ 1 ) = y 1y2<y1 λ1 df(λ1)=y1
Konsequenz 1 (b) : Wenn wir mit , würde der erste Schritt , von wo aus er sich durch die vorherige Konsequenz monoton zur Lösung erhöht (siehe Warnung) unten). Intuitiv folgt diese letzte Tatsache, denn wenn wir rechts von der Wurzel beginnen, ist die Ableitung aufgrund der Konvexität von "zu" flach, und so führt uns der erste Newton-Schritt irgendwo links von der Wurzel. NB Da ist nicht im allgemeinen konvexen für negative
Eigenschaft 2 : Es gibt vernünftige Grenzen, um "sichere" Startpunkte zu geben. Unter Verwendung von Konvexitätsargumenten und Jensens Ungleichung ergeben sich folgende Grenzen: Consequence 2 : Dies sagt uns , dass die Wurzel erfüllt gehorcht Wir haben also bis auf eine gemeinsame Konstante die Wurzel zwischen dem harmonischen und dem arithmetischen Mittel von eingeklemmt .λ 0 d f ( λ 0 ) = y 1
Dies setzt voraus, dass für alle . Ist dies nicht der Fall, so gilt dieselbe Schranke, indem nur das positive und durch die Anzahl des positiven . Anmerkung : Da Annahme von , ist , von wo aus die Grenzen immer nichttrivial sind (z. B. ist die untere Grenze immer nichtnegativ).i d i p d i d f ( 0 ) = p d i > 0 y ∈ ( 0 , p ]di>0 i di p di df(0)=p di>0 y∈(0,p]
Hier ist eine Darstellung eines "typischen" Beispiels für mit . Für die Freiheitsgrade haben wir ein Raster der Größe 10 eingeblendet. Dies sind die horizontalen Linien im Plot. Die vertikalen grünen Linien entsprechen der unteren Grenze in .p = 400 ( ⋆ )df(λ) p=400 (⋆)
Ein Algorithmus und ein Beispiel für einen R-Code
Ein sehr effizienter Algorithmus, der ein Gitter gewünschter Freiheitsgrade in besteht darin, sie in absteigender Reihenfolge zu sortieren und dann nacheinander die Wurzel von jedem zu finden, wobei die vorherige Wurzel als Ausgangspunkt für die folgenden verwendet wird Wir können dies weiter verfeinern, indem wir prüfen, ob jede Wurzel größer als die Untergrenze für die nächste Wurzel ist, und wenn nicht, können wir die nächste Iteration stattdessen an der Untergrenze beginnen. ( 0 , p ]y1,…yn (0,p]
Hier ist ein Beispielcode, in dem
R
keine Optimierungsversuche unternommen wurden. Wie unten zu sehen, ist es immer noch ziemlich schnell, obwohlR
es - höflich ausgedrückt - entsetzlich, schrecklich, schrecklich langsam in Schleifen ist.Unten ist der endgültige vollständige Algorithmus, der ein Gitter von Punkten und einen Vektor von ( nicht !) .d 2 idi d2i
Beispiel Funktionsaufruf
quelle
Darüber hinaus gibt es eine Reihe von Methoden, mit denen der vollständige Regularisierungspfad effizient berechnet werden kann:
Die obigen sind alle R-Pakete, da Sie Python verwenden, enthält scikit-learn Implementierungen für Ridge, Lasso und Elastic Net.
quelle
ols
Funktion in dem R-rms
Paket kann die numerische Optimierung verwenden, um die optimale Strafe unter Verwendung eines effektiven AIC zu finden. Aber Sie müssen die maximale Strafe bereitstellen, die nicht immer einfach ist.Eine mögliche Alternative nach der folgenden Quelle scheint zu sein:
Die Lösung in geschlossener Form:df(λ)=tr(X(X⊤X+λIp)−1X⊤)
Wenn Sie die normale Gleichung als Löser verwenden oder die Varianz-Kovarianz-Schätzung berechnen, sollten Sie bereits berechnet haben . Dieser Ansatz funktioniert am besten, wenn Sie die Koeffizienten bei den verschiedenen schätzen . λ(X⊤X+λIp)−1 λ
Quelle: https://onlinecourses.science.psu.edu/stat857/node/155
quelle