Bei der komprimierten Abtastung gibt es einen Satz, der garantiert, dass

Gibt es einen ähnlichen Satz für Lasso? Wenn es einen solchen Satz gibt, garantiert er nicht nur die Stabilität des Lassos, sondern bietet dem Lasso auch eine aussagekräftigere Interpretation:

Lasso kann den spärlichen Regressionskoeffizientenvektor aufdecken, der $c$verwendet wird, um die Antwort $y$ durch zu erzeugen .$y = Xc$

Es gibt zwei Gründe, warum ich diese Frage stelle:

1. Ich denke, "Lasso bevorzugt eine spärliche Lösung" ist keine Antwort darauf, warum Lasso für die Funktionsauswahl verwendet wird, da wir nicht einmal sagen können, welchen Vorteil die von uns ausgewählten Funktionen haben.

2. Ich habe gelernt, dass Lasso dafür berüchtigt ist, bei der Auswahl von Features instabil zu sein. In der Praxis müssen wir Bootstrap-Beispiele ausführen, um die Stabilität zu bewerten. Was ist der wichtigste Grund für diese Instabilität?

Blinddarm:

Gegeben ist $X_{N \times M} = (x_1, \cdots, x_M)$ . $c$ ist ein $\Omega$ sparsamer Vektor ( $\Omega \leqslant M$ ). Der Prozess erzeugt die Antwort . Wenn den NSP (Nullraum-Eigenschaft) der Ordnung und die Kovarianzmatrix von keinen Eigenwert nahe Null hat, gibt es eine eindeutige Lösung für was genau das , das ergibt$y = Xc$$y$$X$$\Omega$$X$

Was dieser Satz auch sagt, ist auch, wenn nicht den NSP der Ordnung , ist es einfach hoffnungslos, .Ω argmin c : y = X c ‖ c ‖ $X$$\Omega$$\text{argmin}_{c: y = Xc} \Vert c \Vert_1$

BEARBEITEN:

Nachdem ich diese großartigen Antworten erhalten hatte, stellte ich fest, dass ich verwirrt war, als ich diese Frage stellte.

Warum diese Frage verwirrend ist:

Ich habe eine Forschungsarbeit gelesen , in der wir entscheiden müssen, wie viele Merkmale (Spalten) die Entwurfsmatrix $X_{N \times M}$ haben wird (Hilfsmerkmale werden aus primären Merkmalen erstellt). Da es sich um ein typisches $n < p$ Problem handelt, wird erwartet, dass $D$ gut konstruiert ist, so dass die Lösung für Lasso eine gute Annäherung an die real spärliche Lösung sein kann.

Die Argumentation ergibt sich aus dem Satz, den ich im Anhang erwähnt habe: Wenn wir eine sparsame Lösung c finden wollen , hat X besser den NSP der Ordnung Ω .$\Omega$$c$$X$$\Omega$

Wenn für eine allgemeine Matrix N > C Ω ln M verletzt wird, dann$N \times M$$N > C \Omega \ln M$

Eine stabile und robuste Gewinnung von aus D und P ist nicht möglich$c$$D$$P$

entspricht X , P entspricht$D$$X$$P$$y$

... wie aus der Beziehung erwartet , wird die Auswahl des Deskriptors instabiler, dh für verschiedene Trainingssätze unterscheidet sich der ausgewählte Deskriptor häufig ...$N = C \Omega \ln M$

Das zweite Zitat ist der Teil, der mich verwirrt. Es scheint mir, wenn die Ungleichung verletzt wird, ist es nicht nur die Lösung, die möglicherweise nicht eindeutig ist (nicht erwähnt), sondern der Deskriptor wird auch instabiler.

AKTUALISIEREN

In diesem zweiten Beitrag finden Sie McDonalds Feedback zu meiner Antwort, in der der Begriff der Risikokonsistenz mit der Stabilität zusammenhängt.

1) Einzigartigkeit gegen Stabilität

Ihre Frage ist schwer zu beantworten, da sie zwei sehr unterschiedliche Themen erwähnt: Einzigartigkeit und Stabilität .

• Intuitiv ist eine Lösung eindeutig, wenn bei einem festen Datensatz der Algorithmus immer die gleichen Ergebnisse liefert. Martins Antwort-Cover behandelt diesen Punkt sehr detailliert.

• Stabilität hingegen kann intuitiv als eine verstanden werden, bei der sich die Vorhersage nicht wesentlich ändert, wenn die Trainingsdaten geringfügig geändert werden.

Die Stabilität gilt für Ihre Frage, da die Auswahl der Lasso-Funktionen (häufig) über die Kreuzvalidierung erfolgt. Daher wird der Lasso-Algorithmus für verschiedene Datenfalten ausgeführt und kann jedes Mal zu unterschiedlichen Ergebnissen führen.

Stabilität und das No Free Lunch Theorem

Verwenden Sie die Definition von hier, wenn wir die einheitliche Stabilität definieren als:

Ein Algorithmus hat eine gleichmäßige Stabilität in Bezug auf die Verlustfunktion V, wenn Folgendes gilt:$\beta$$V$

$$\forall S \in Z^m \ \ \forall i \in \{ 1,...,m\}, \ \ \sup | > V(f_s,z) - V(f_{S^{|i},z}) |\ \ \leq \beta$$

Als Funktion von , kann der Term β als β m geschrieben werden . Wir sagen, der Algorithmus ist stabil, wenn β m als 1 abnimmt $m$$\beta$$\beta_m$$\beta_m$ .$\frac{1}{m}$

dann der "No Free Lunch Satz, Xu und Caramis (2012)" besagt , dass

Wenn ein Algorithmus in dem Sinne spärlich ist , dass er redundante Merkmale identifiziert, ist dieser Algorithmus nicht stabil (und die einheitliche Stabilitätsgrenze geht nicht auf Null). [...] Wenn ein Algorithmus stabil ist, besteht keine Hoffnung, dass er spärlich ist. (Seiten 3 und 4)$\beta$

Beispielsweise ist die regulierte -Regression stabil und identifiziert keine redundanten Merkmale, während die regulierte L 1 -Regression (Lasso) instabil ist. $L_2$$L_1$

Ein Versuch, Ihre Frage zu beantworten

Ich denke, "Lasso bevorzugt eine spärliche Lösung" ist keine Antwort darauf, warum Lasso für die Funktionsauswahl verwendet wird

• Ich bin anderer Meinung, der Grund, warum Lasso für die Merkmalsauswahl verwendet wird, ist, dass es eine spärliche Lösung ergibt und gezeigt werden kann, dass es die IRF-Eigenschaft hat, dh redundante Merkmale identifiziert.

Was ist der wichtigste Grund für diese Instabilität?

• Das No Free Lunch Theorem

Weitergehen

Dies bedeutet nicht, dass die Kombination aus Kreuzvalidierung und Lasso nicht funktioniert. Tatsächlich wurde experimentell (und mit viel unterstützender Theorie) gezeigt, dass sie unter verschiedenen Bedingungen sehr gut funktioniert. Die Hauptschlüsselwörter hier sind Konsistenz , Risiko, Orakel-Ungleichungen usw.

Die folgenden Folien und Artikel von McDonald und Homrighausen (2013) beschreiben einige Bedingungen, unter denen die Auswahl von Lasso-Merkmalen gut funktioniert: Folien und Papier: "Das Lasso, die Persistenz und die Kreuzvalidierung, McDonald und Homrighausen (2013)" . Tibshirani sich auch eine große Reihe von Notizen über entsandte sparcity , lineare Regression

Die verschiedenen Bedingungen für Konsistenz und ihre Auswirkungen auf Lasso sind ein aktives Forschungsthema und definitiv keine triviale Frage. Ich kann Sie auf einige relevante Forschungsarbeiten hinweisen:

• Videovorträge zum No-No-Lunch-Theorem von Xu
• HM Bøvelstad et al., Ein Vergleich von Merkmalsauswahlansätzen für die Genselektion, (2007)
• Das Lasso, die Persistenz und die Kreuzvalidierung, McDonald und Homrighausen (2013)
• Huang und Bowick, Zusammenfassung und Diskussion von: "Stabilitätsauswahl"
• Lim und Yu, Schätzungsstabilität mit Kreuzvalidierung, (2015)
• Ein Vortrag von Peter Buhlmann: Stabilität Auswahl für hochdimensionalen Daten, (2008) und das Begleitpapier
• Wang, Nan et al., Random Lasso, (2011)
• Stapelaustauschpfosten: Modellstabilität bei großen , kleinen n Problemen$p$$n$
• Roberts, Nowakm Stabilisierung des Lassos gegen Variabilität der Kreuzvalidierung (2014), in der argumentiert wird, dass "Perzentil-Lasso im Vergleich zum Lasso zu einer starken Verringerung sowohl der Instabilität der Modellauswahl als auch des Modellauswahlfehlers führen kann".
• Ein großartiger Satz von Notizen von Tibshirani und Wasserman über spärliche , lineare Regression

Kommentare von Daniel J. McDonald

Assistenzprofessor an der Indiana University Bloomington, Autor der beiden in der ursprünglichen Antwort von Xavier Bourret Sicotte erwähnten Artikel .

Ihre Erklärung ist im Allgemeinen ganz richtig. Ein paar Dinge, auf die ich hinweisen möchte:

1. Unser Ziel in der Reihe von Artikeln über CV und Lasso war es zu beweisen, dass "Lasso + Cross Validation (CV)" genauso gut funktioniert wie "Lasso + optimales "$\lambda$ . Insbesondere wollten wir zeigen, dass die Vorhersagen auch funktionieren (modellfrei). Um Aussagen über die korrekte Wiederherstellung von Koeffizienten zu treffen (die richtigen nicht spärlichen zu finden), muss man eine spärliche Wahrheit annehmen, was wir nicht wollten.

2. Algorithmische Stabilität impliziert Risikokonsistenz (zuerst von Bousquet und Elisseeff bewiesen, glaube ich). Mit Risikokonsistenz meine ich, dass die geht auf Null, wobei f entweder E [ Y | ist X ] oder der beste Prädiktor innerhalb einer Klasse, wenn die Klasse falsch angegeben ist. Dies ist jedoch nur eine ausreichende Bedingung. Es wird auf den Folien, auf die Sie verlinkt haben, im Wesentlichen als „mögliche Proof-Technik, die nicht funktioniert, da Lasso nicht stabil ist“ erwähnt.$||\hat{f}(X) - f(X)||$$E[Y|X]$

3. $\lambda$$p>n$

4. $Y$$X_i$

$\rightarrow$

Das Lasso hat im Gegensatz zur Ridge-Regression (siehe z. B. Hoerl und Kennard, 1970; Hastie et al., 2009) nicht immer eine eindeutige Lösung, obwohl dies normalerweise der Fall ist. Dies hängt von der Anzahl der Parameter im Modell ab, davon, ob die Variablen kontinuierlich oder diskret sind oder nicht, und vom Rang Ihrer Entwurfsmatrix. Bedingungen für die Einzigartigkeit finden sich in Tibshirani (2013).

Verweise:

Hastie, T., Tibshirani, R. und Friedman, J. (2009). Die Elemente des statistischen Lernens . Springer-Reihe in der Statistik. Springer, New York, 11. Druck, 2. Auflage.

Hoerl, AE und Kennard, RW (1970). Ridge-Regression: Verzerrte Schätzung für nichtorthogonale Probleme. Technometrics , 12 (1), 55 & ndash ; 67.

Tibshirani, RJ (2013). Das Lasso-Problem und die Einzigartigkeit. Electronic Journal of Statistics , 7, 1456-1490.

Was verursacht Nicht-Einzigartigkeit.

$s_ix_i$$s_i$$c_i$$\Vert c \Vert_1$

then there are an infinite number of combinations $c_i + \gamma\alpha_i$ that do not change the solution $Xc$ and the norm $\Vert c\Vert_1$.

For example:

has for $\Vert c \Vert_1 = 1$ the solutions:

with $0\leq \gamma \leq \frac{1}{2}$

We can sort of replace the vector $x_2$ by using $x_2 = 0.5 x_1 + 0.5 x_3$

Situations without this condition

In the article from Tibshirani (from Phil's answer) three sufficient conditions are described for lasso to have an unique solution.

1. Linearly independent When the null space $X$ is null or equivalently when the rank of $X$ is equal to the number of columns (M). In that case you do not have linear combinations like above.

2. Affinely independent When the columns $Xs$ are in general position.

   That is, no $k$ columns represent points in a $k-2$ dimensional plane. A k-2 dimensional plane can be parameterized by any $k-1$ points as $\sum \alpha_i s_ix_i$ with $\sum \alpha_i = 1$. With a $k$-th point $s_jx_j$ in this same plane you would have the conditions $\sum \alpha_i s_ix_i$ with $\sum \alpha_i = 0$

   Note that in the example the columns $x_1$, $x_2$ and $x_3$ are on a single line. (It is however a bit awkward here because the signs can be negative, e.g. the matrix $\left[ [2 \, 1] \, [1 \, 1] \, [-0 \, -1] \right]$ has just as well no unique solution)

3. When the columns $X$ are from a continuous distribution then it is unlikely (probability almost zero) that you will have columns of $X$ not in general position.

   Contrasting with this, if the columns $X$ are a categorical variable then this probability is not neccesarily almost zero. The probability for a continuous variable to be equal to some set of numbers (ie the planes corresponding to the affine span of the other vectors) is 'almost' zero. But, this is not the case for discrete variables.