Regularisierung und Projektion auf die

8

Ich versuche zu verstehen , wie Regularisierung in der Bezeichnung der Projektionen auf ein Werk l Kugel und euklidische Projektion auf die simplex.

Ich bin mir nicht sicher, ob ich verstehe, was wir meinen, wenn wir den Gewichtsvektor auf die l1 oder l2 Bälle projizieren .

Ich kann das Konzept der l1 Regularisierungsprogrammatik verstehen , indem wir jedes Element im Gewichtsvektor durchgehen und signum(w) * max(0.0, abs(w) - shrinkageValue)wo anwenden shrinkageValue = regularizationParameter * eta, wodurch kleine Gewichte auf 0 getrieben werden.

Ich vermisse hier wohl etwas Mathematik, also ist meine Frage, wie wir die Projektion des Vektors in das Programm übersetzen, das ich gerade beschrieben habe. Wie hängen Regularisierung und Vektorprojektionen zusammen?

Bearbeiten: Ich versuche, dieses Papier Effiziente Projektionen auf den l1 -Ball zum Lernen in hohen Dimensionen durchzugehen

Bar
quelle

Antworten:

11

Regularisierung und Vektorprojektionen sind durch die Idee der eingeschränkten Optimierung und die Karush-Kuhn-Tucker-Bedingungen (keine Beziehung) verbunden .

Was sind die KKT-Bedingungen?

Kurz gesagt, diese besagen, dass, wenn eine Lösung für das Problem "Minimieren von f ( x ) unter Berücksichtigung von g ( x ) 0 " ist, x auch eine Lösung für das Problem f ( x ) = λ g ( x ist ) für einen Skalar λ . Aber dies ist äquivalent zu der Aussage f ( x ) - & lgr; g ( x ) = 0 , was bedeutet , dass xxf(x)g(x)0xf(x)=λg(x)λf(x)λg(x)=0xminimiert das uneingeschränkte Optimierungsproblem "minimiere ".f(x)λg(x)

Die Intuition ist, dass entweder:

  • . In diesem Fall ist x eine "innere Lösung", daher muss der Gradient von f an diesem Punkt Null sein. (Wenn es nicht Null wäre, könnten wir uns von x aus ein wenig in diese Richtung bewegen, während g ( x ) < 0 bleibt , und einen höheren Wert für f ( x ) haben . Dann setzen wir λ = 0 und wir sind erledigt.g(x)<0xfxg(x)<0f(x)λ=0

  • Oder . In diesem Fall befindet sich x am Rand des möglichen Lösungsraums. Lokal sieht diese Kante wie eine Hyperebene aus, die orthogonal zum Gradienten g ( x ) ist , da die Art und Weise, wie Sie die Einschränkung g ( x ) = 0 beibehalten , darin besteht, den Gradienten überhaupt nicht nach oben oder unten zu bewegen. Dies bedeutet jedoch, dass die einzige Richtung, in die der Gradient f möglicherweise zeigen könnte, genau dieselbe Richtung wie g ist - wenn er eine Komponente hätte, die orthogonal zu g war , könnten wir x bewegeng(x)=0xg(x)g(x)=0fggxein wenig in diese Richtung, bleibe auf der orthogonalen Hyperebene und erhöhe f ( x ) .g(x)=0f(x)

Wie die KKT-Bedingungen die Beziehung zwischen eingeschränkter Minimierung und Regularisierung erklären

g(x)=|x|ccg(x)0xcλg(x)λ|x|+λcλc

Menschen nutzen oft diese "Dualität" zwischen uneingeschränkter und eingeschränkter Optimierung. Ein Beispiel, das ich durch Googeln schnell finden konnte, finden Sie unter Auf dem LASSO und seinem Dual .

Warum sind Projektionen hier wichtig?

OK, warum schreibt jemand eine Arbeit über schnelle Projektionen?

f(x)xX

  • f(x)
  • x0
  • x0step(x0)
  • Xx1PX(x0)
  • Und bis zur Konvergenz wiederholen.

PX

Alles zusammenfügen

argminβ(yβX)2+λ||β||1

Das ist die uneingeschränkte Version. Unter den KKT-Bedingungen entspricht das Hinzufügen des Regularisierungsterms der Einschränkung, dass die Lösung für eine Konstante in . Aber das ist nur der Ball mit Radius !c 1 c||β||1cc1c

Sie können sich also vorstellen, dies mit einem projizierten (Sub-) Gradientenabstieg zu lösen. * Wenn Sie dies tun würden, wäre Ihre Funktion eine Projektion auf den Einheitskugel, und Sie möchten dies schnell machen.PX

* Ich glaube nicht, dass die Leute dies tatsächlich tun, weil es effizientere Wege gibt. Diese könnten aber auch Projektionen verwenden. BEARBEITEN: Wie @Dougal hervorhebt, war eine komplexere Variante des projizierten Abstiegs unter dem Gefälle gut genug, um 2008 eine Arbeit darüber zu schreiben.

Ben Kuhn
quelle
1
Der ISTA / FISTA- Algorithmus ist im Grunde genommen ein (beschleunigter) projizierter subgradienter Abstieg, der vielleicht nicht der beliebteste LASSO-Algorithmus ist, aber ziemlich gut (und ich denke, er war um 2008, als dieser Artikel veröffentlicht wurde, Stand der Technik).
Dougal
@ Dougal: Danke für den Hinweis! Ich habe es in bearbeitet.
Ben Kuhn