Dans la détection compressée, il existe un théorème garantissant que a une solution clairsemée unique c (voir l'annexe pour plus de détails).

Existe-t-il un théorème similaire pour le lasso? S'il existe un tel théorème, non seulement il garantira la stabilité du lasso, mais il fournira également au lasso une interprétation plus significative:

lasso peut découvrir le vecteur de coefficient de régression clairsemé $c$ qui est utilisé pour générer la réponse $y$ par $y = Xc$ .

Il y a deux raisons pour lesquelles je pose cette question:

1. Je pense que `` le lasso favorise une solution clairsemée '' n'est pas une réponse à la raison pour laquelle utiliser le lasso pour la sélection des fonctionnalités, car nous ne pouvons même pas dire quel est l'avantage des fonctionnalités que nous sélectionnons.

2. J'ai appris que le lasso est connu pour être instable pour la sélection des fonctionnalités. En pratique, nous devons exécuter des échantillons de bootstrap pour évaluer sa stabilité. Quelle est la raison la plus cruciale à l'origine de cette instabilité?

Appendice:

Étant donné $X_{N \times M} = (x_1, \cdots, x_M)$ . $c$ est un vecteur $\Omega$ -parsé ( $\Omega \leqslant M$ ). Le processus $y = Xc$ génère la réponse $y$ . Si $X$ a la NSP (propriété d'espace nul) d'ordre $\Omega$ et que la matrice de covariance de $X$ n'a pas de valeur propre proche de zéro, il y aura une solution unique à

Ce que dit également ce théorème, c'est aussi que si n'a pas le NSP d'ordre , il est tout simplement inutile de résoudre .$X$$\Omega$$\text{argmin}_{c: y = Xc} \Vert c \Vert_1$

ÉDITER:

Après avoir reçu ces excellentes réponses, j'ai réalisé que j'étais confus lorsque je posais cette question.

Pourquoi cette question prête à confusion:

J'ai lu un document de recherche dans lequel nous devons décider combien d'entités (colonnes) la matrice de conception va avoir (les entités auxiliaires sont créées à partir des entités principales). Puisqu'il s'agit d'un problème typique , devrait être bien construit de sorte que la solution au lasso puisse être une bonne approximation de la vraie solution creuse.$X_{N \times M}$$n < p$$D$

Le raisonnement est basé sur le théorème que j'ai mentionné en annexe: Si nous cherchons à trouver une solution -parse , a mieux d'avoir le NSP d'ordre .$\Omega$$c$$X$$\Omega$

Pour une matrice générale , si est violé, alors$N \times M$$N > C \Omega \ln M$

aucune récupération stable et robuste de partir de et n'est possible$c$$D$$P$

$D$ correspond à , correspond à$X$$P$$y$

... comme attendu de la relation , la sélection du descripteur devient plus instable, c'est-à-dire que pour différents ensembles d'apprentissage, le descripteur sélectionné diffère souvent ...$N = C \Omega \ln M$

La deuxième citation est la partie qui m'embrouille. Il me semble que lorsque l'inégalité est violée, ce n'est pas seulement la solution peut-être non unique (non mentionnée), mais le descripteur deviendra également plus instable.

MISE À JOUR

Voir ce deuxième article pour les commentaires de McDonald sur ma réponse où la notion de cohérence des risques est liée à la stabilité.

1) Unicité vs stabilité

Il est difficile de répondre à votre question car elle mentionne deux sujets très différents: l' unicité et la stabilité .

• Intuitivement, une solution est unique si on lui donne un ensemble de données fixe, l'algorithme produit toujours les mêmes résultats. La réponse de Martin couvre ce point en détail.

• La stabilité , d'autre part, peut être comprise intuitivement comme une stabilité pour laquelle la prédiction ne change pas beaucoup lorsque les données d'entraînement sont légèrement modifiées.

La stabilité s'applique à votre question car la sélection des fonctionnalités Lasso est (souvent) effectuée via la validation croisée, donc l'algorithme Lasso est exécuté sur différents plis de données et peut donner des résultats différents à chaque fois.

La stabilité et le théorème du déjeuner gratuit

En utilisant la définition d' ici si nous définissons la stabilité uniforme comme:

Un algorithme a une stabilité uniforme par rapport à la fonction de perte si les conditions suivantes sont réunies:$\beta$$V$

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

Considéré en fonction de , le terme peut s'écrire . Nous disons que l'algorithme est stable lorsque diminue avec .$m$$\beta$$\beta_m$$\beta_m$$\frac{1}{m}$

alors le "No Free Lunch Theorem, Xu et Caramis (2012)" déclare que

Si un algorithme est clairsemé , dans le sens où il identifie des caractéristiques redondantes, alors cet algorithme n'est pas stable (et la stabilité uniforme liée ne va pas à zéro). [...] Si un algorithme est stable, il n'y a aucun espoir qu'il soit rare. (pages 3 et 4)$\beta$

Par exemple, la régression régularisée est stable et n'identifie pas les entités redondantes, tandis que la régression régularisée (Lasso) est instable. $L_2$$L_1$

Une tentative de répondre à votre question

Je pense que «le lasso favorise une solution clairsemée» n'est pas une réponse à la raison pour laquelle utiliser le lasso pour la sélection des fonctionnalités

• Je ne suis pas d'accord, la raison pour laquelle Lasso est utilisé pour la sélection des fonctionnalités est qu'il fournit une solution clairsemée et peut être démontré qu'il a la propriété IRF, c'est-à-dire identifie les fonctionnalités redondantes.

Quelle est la raison la plus cruciale à l'origine de cette instabilité

• Le théorème du déjeuner gratuit

Aller plus loin

Cela ne veut pas dire que la combinaison de la validation croisée et du lasso ne fonctionne pas ... en fait, il a été démontré expérimentalement (et avec beaucoup de théorie à l'appui) qu'il fonctionne très bien dans diverses conditions. Les principaux mots clés ici sont la cohérence , le risque, les inégalités oracle, etc.

Les diapositives et le papier suivants de McDonald et Homrighausen (2013) décrivent certaines conditions dans lesquelles la sélection des caractéristiques du lasso fonctionne bien: diapositives et papier: "Le lasso, la persistance et la validation croisée, McDonald et Homrighausen (2013)" . Tibshirani lui-même a également publié un grand ensemble de notes sur la rareté , la régression linéaire

Les différentes conditions de cohérence et leur impact sur le Lasso est un sujet de recherche actif et n'est certainement pas une question banale. Je peux vous orienter vers des articles de recherche pertinents:

• Conférences vidéo sur le théorème du déjeuner gratuit, par Xu
• HM Bøvelstad et all, Une comparaison des approches de sélection des caractéristiques pour la sélection des gènes, (2007)
• Le lasso, la persistance et la validation croisée, McDonald et Homrighausen (2013)
• Huang et Bowick, Résumé et discussion de: «Sélection de la stabilité»
• Lim et Yu, Estimation de la stabilité avec validation croisée, (2015)
• Une conférence de Peter Buhlmann: Stability Selection for High-Dimensional Data, (2008) et le document qui l'accompagne
• Wang, Nan et all, Random Lasso, (2011)
• Après StackExchange: stabilité modèle lorsqu'ils traitent avec un grand , petit problème$p$$n$
• Roberts, Nowakm Stabiliser le lasso contre la variabilité de la validation croisée, (2014) qui soutiennent que "le centile-lasso, peut entraîner des réductions importantes de l'instabilité de sélection du modèle et de l'erreur de sélection du modèle, par rapport au lasso"
• Un ensemble impressionnant de notes de Tibshirani et Wasserman sur la rareté , la régression linéaire

Commentaires de Daniel J. McDonald

Professeur adjoint à l'Université d'Indiana Bloomington, auteur des deux articles mentionnés dans la réponse originale de Xavier Bourret Sicotte .

Votre explication est, en général, tout à fait correcte. Je voudrais souligner quelques points:

1. Notre objectif dans la série d'articles sur CV et lasso était de prouver que "Lasso + Cross Validation (CV)" fait aussi bien que "Lasso + optimal "$\lambda$ . En particulier, nous avons voulu montrer que les prédictions font aussi bien (sans modèle). Afin de faire des déclarations sur la récupération correcte des coefficients (trouver les bons non clairsemés), il faut supposer une vérité clairsemée, ce que nous ne voulions pas faire.

2. La stabilité algorithmique implique la cohérence des risques (prouvé pour la première fois par Bousquet et Elisseeff). Par cohérence des risques, je veux dire que leva à zéro où f est soit soit le meilleur prédicteur d'une classe si la classe est mal spécifiée. Ce n'est cependant qu'une condition suffisante. Il est mentionné sur les diapositives auxquelles vous avez lié comme, essentiellement, "une technique de preuve possible qui ne fonctionnera pas, car le lasso n'est pas stable".$||\hat{f}(X) - f(X)||$$E[Y|X]$

3. La stabilité est seulement suffisante mais pas nécessaire. Nous avons pu montrer que, dans certaines conditions, «lasso + CV» prédit ainsi que «lasso + optimal ». L'article que vous citez donne les hypothèses les plus faibles possibles (celles de la diapositive 16, qui permettent ), mais utilise la forme contrainte du lasso plutôt que la version lagrangienne la plus courante. Un autre article ( http://www3.stat.sinica.edu.tw/statistica/J27N3/J27N34/J27N34.html ) utilise la version lagrangienne. Cela montre également que dans des conditions beaucoup plus fortes, la sélection du modèle fonctionnera également. Un article plus récent ( https://arxiv.org/abs/1605.02214 ) par d'autres personnes prétend améliorer ces résultats (je ne l'ai pas lu attentivement).$\lambda$$p>n$

4. En général, parce que le lasso (ou tout algorithme de sélection) n'est pas stable, il faut une analyse plus approfondie et / ou des hypothèses solides pour montrer que «algorithme + CV» sélectionnera le modèle correct. Je ne connais pas les conditions nécessaires, bien que cela soit extrêmement intéressant en général. Il n'est pas trop difficile de montrer que pour le lambda fixe, le prédicteur du lasso est localement Lipschitz dans le vecteur (je pense qu'un ou plusieurs articles de Ryan Tibshirani le font). Si l'on pouvait également affirmer que cela est vrai dans , ce serait très intéressant et pertinent ici.$Y$$X_i$

Le principal point à retenir que j'ajouterais à votre réponse: la «stabilité» implique la «cohérence des risques» ou la «précision des prédictions». Elle peut également impliquer la «cohérence de l'estimation des paramètres» sous plus d'hypothèses. Mais le théorème du déjeuner gratuit signifie «sélection» "pas stable". Le lasso n'est pas stable même avec un lambda fixe. Il est certainement instable donc lorsqu'il est combiné avec CV (de tout type). Cependant, malgré le manque de stabilité, il est toujours cohérent avec les risques et la sélection est cohérente avec ou sans CV L'unicité n'a pas d'importance ici.$\rightarrow$

Le Lasso, contrairement à la régression Ridge (voir par exemple Hoerl et Kennard, 1970; Hastie et al., 2009) n'a pas toujours une solution unique, bien qu'elle l'ait généralement. Cela dépend du nombre de paramètres dans le modèle, du fait que les variables soient continues ou discrètes et du rang de votre matrice de conception. Les conditions d'unicité peuvent être trouvées dans Tibshirani (2013).

Les références:

Hastie, T., Tibshirani, R. et Friedman, J. (2009). Les éléments de l'apprentissage statistique . Série Springer en statistiques. Springer, New York, 11e impression, 2e édition.

Hoerl, AE et Kennard, RW (1970). Régression de crête: estimation biaisée pour les problèmes non orthogonaux. Technometrics , 12 (1), 55-67.

Tibshirani, RJ (2013). Le problème du lasso et l'unicité. Electronic Journal of Statistics , 7, 1456-1490.

Ce qui cause la non-unicité.

Pour les vecteurs (où est un signe indiquant si le changement de va augmenter ou diminuer ), chaque fois qu'ils sont affinement dépendants:$s_ix_i$$s_i$$c_i$$\Vert c \Vert_1$

alors il existe un nombre infini de combinaisons qui ne changent pas la solution et la norme .$c_i + \gamma\alpha_i$$Xc$$\Vert c\Vert_1$

Par exemple:

a pour les solutions:$\Vert c \Vert_1 = 1$

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

Nous pouvons en quelque sorte remplacer le vecteur en utilisant$x_2$$x_2 = 0.5 x_1 + 0.5 x_3$

Situations sans cette condition

Dans l'article de Tibshirani (de la réponse de Phil), trois conditions suffisantes sont décrites pour que le lasso ait une solution unique.

1. Linéairement indépendant Lorsque l'espace nul est nul ou de manière équivalente lorsque le rang de est égal au nombre de colonnes (M). Dans ce cas, vous n'avez pas de combinaisons linéaires comme ci-dessus.$X$$X$

2. Affinement indépendant Lorsque les colonnes sont en position générale.$Xs$

   Autrement dit, aucune colonne ne représente des points dans un plan dimensionnel . Un plan dimensionnel k-2 peut être paramétré par n'importe quel point comme avec . Avec un -ième point dans ce même plan, vous auriez les conditions avec$k$$k-2$$k-1$$\sum \alpha_i s_ix_i$$\sum \alpha_i = 1$$k$$s_jx_j$$\sum \alpha_i s_ix_i$$\sum \alpha_i = 0$

   Notez que dans l'exemple, les colonnes , et sont sur une seule ligne. (C'est cependant un peu gênant ici car les signes peuvent être négatifs, par exemple la matrice vient de ainsi aucune solution unique)$x_1$$x_2$$x_3$$\left[ [2 \, 1] \, [1 \, 1] \, [-0 \, -1] \right]$

3. Lorsque les colonnes proviennent d'une distribution continue, il est peu probable (probabilité presque nulle) que vous ayez des colonnes de pas en position générale.$X$$X$

   Contrairement à cela, si les colonnes sont une variable catégorielle, cette probabilité n'est pas nécessairement presque nulle. La probabilité qu'une variable continue soit égale à un ensemble de nombres (c'est-à-dire les plans correspondant à la plage affine des autres vecteurs) est «presque» nulle. Mais ce n'est pas le cas pour les variables discrètes.$X$