Si p> n, le lasso sélectionne au plus n variables

L'une des motivations du filet élastique était la limitation suivante de LASSO:

Dans le cas $p > n$ , le lasso sélectionne au plus n variables avant de saturer, en raison de la nature du problème d'optimisation convexe. Cela semble être une caractéristique limitante pour une méthode de sélection de variables. De plus, le lasso n'est pas bien défini à moins que la limite sur la norme L1 des coefficients ne soit inférieure à une certaine valeur.

( http://onlinelibrary.wiley.com/doi/10.1111/j.1467-9868.2005.00503.x/full )

Je comprends que LASSO est un problème de programmation quadratique mais peut également être résolu via LARS ou une descente de gradient par élément. Mais je ne comprends pas où dans ces algorithmes je rencontre un problème si $p > n$ où $p$ est le nombre de prédicteurs et $n$ est la taille de l'échantillon. Et pourquoi ce problème est-il résolu en utilisant un filet élastique où j'augmente le problème à $p+n$ variables qui dépassent clairement $p$ .

regression optimization feature-selection lasso user1137731
la source

Si le lasso restreint l'utilisation à garder p <= n, pourquoi est-ce un inconvénient plutôt qu'une vertu. le sur-ajustement est un problème grave qui survient lorsque p = n. Le modèle avec p = n est un modèle saturé et souvent ce modèle est surajusté car il s'adaptera parfaitement aux données observées mais ne prédira pas nécessairement bien les futurs cas.

Michael R. Chernick

Le fait que le lasso ne sélectionne que jusqu'à

variables peut être considéré comme une conséquence du fait qu'il peut être résolu en utilisant (une légère modification de) l'algorithme LARS, qui n'admet que jusqu'à

variables dans l'ensemble actif à un moment donné. Le fait que cela ne se vérifie pas dans le cas du filet élastique résulte essentiellement de l'incorporation de la pénalité

et se comporte donc plus comme une régression de crête, cette dernière entraînant normalement tous les coefficients non nuls.

n

$n$

n

$n$

ℓ_{2}

$\ell_2$

Cardinal

Merci pour les réponses, et comment pourrais-je voir pour la descente de gradient qui au plus n variables peuvent être sélectionnées: Présentation à cs.cmu.edu/afs/cs/project/link-3/lafferty/www/ml-stat2/talks/ … Papier (section 4) sur datamining.dongguk.ac.kr/papers/GLASSO_JRSSB_V1.final.pdf

user1137731

@user: Je pense que vous confondez le problème mathématique avec sa solution numérique. L'algorithme LARS montre que la solution de lasso sélectionnera au plus

variables. Ceci est indépendant des moyens numériques réels pour arriver à la solution, c'est-à-dire que l'algorithme LARS donne un aperçu du problème, mais bien sûr, toute autre méthode qui résout le problème de manière équivalente doit avoir la même propriété! :-)

n

$n$

Cardinal

Considérons une fonction

fois dupliquée . Il existera un estimateur au lasso avec exactement

zéros (même si

) Par conséquent, votre affirmation n'est pas vraie telle qu'elle est écrite.

p

$p$

p

$p$

p > n

$p>n$

user795305

Réponses:

Comme dit, ce n'est pas la propriété d'un algorithme mais du problème d'optimisation. Les conditions KKT donnent essentiellement que pour que le coefficient soit non nul, il doit correspondre à une corrélation fixe avec le résidu ( $\beta_j$ $|X_j^t(y-X\beta)| = \lambda$ est le paramètre de régularisation). $\lambda$

Après avoir résolu les diverses complications avec une valeur absolue, etc., vous vous retrouvez avec une équation linéaire pour chaque coefficient non nul. Puisque le rang de la matrice est au plus lorsque $X$ $n$ , c'est le nombre d'équations qui peuvent être résolues, et donc il y a au plus n non-zéros (sauf s'il y a des redondances). $p>n$

Soit dit en passant, cela est vrai pour toute fonction de perte, pas seulement pour le lasso standard avec perte de . C'est donc en fait une propriété de la peine de lasso. Il existe de nombreux articles qui montrent cette vue KKT et les conclusions qui en résultent, je peux citer notre article: Rosset et Zhu, Piecewise Linear Regularized Solutions Paths, Annals of Stats 2007 et les références qui s'y trouvent. $L_2$

Saharon Rosset
la source

Que signifie KKT? En outre, est-il possible que vous parliez d'une perte de L1 lorsque vous parlez du lasso standard?

miura

Salut Saharon et bienvenue sur le site. Vous pouvez utiliser LaTeX pour rendre les formules plus propres (je l'ai fait dans votre réponse) et vous n'avez pas besoin de signer vos messages, car une signature est ajoutée automatiquement.

Peter Flom - Réintègre Monica

@miura: KKT signifie Karush-Kuhn-Tucker. Les conditions KKT sont certaines équations que les solutions aux problèmes d'optimisation (suffisamment réguliers) doivent remplir ( article wikipedia ).

mogron

Je viens de voir que Ryan Tibshirani a un document de travail très pertinent «Le problème du lasso et l'unicité»: stat.cmu.edu/~ryantibs/papers/lassounique.pdf

user1137731

Une autre explication est la suivante: si , le rang de la matrice de données est au plus , donc la dimension de son espace nul (à droite) est au moins . Écrivez n'importe quel vecteur dans cet espace nul comme . Ensuite, en tout point réalisable , on peut toujours se déplacer dans cet espace nul dimensionnel vers les axes de coordonnées de l' espace ambiant dimensionnel, pour arriver à a , où (au plus) s sont non nul et la fonction objectif LASSO $n < p$ $X$ $n$ $p - n$ $z$ $\beta$ $p - n$ $p$ $\beta+z$ $n$ $\beta_j$

‖ y - X (β + z) ‖_{2}^{2} + λ ‖ β + z ‖_{1} = ‖ y - X β ‖_{2}^{2} + λ ‖ β + z ‖_{1} < ‖ y - X β ‖_{2}^{2} + λ ‖ β ‖_{1}

a diminué.

user2969758
la source

(+1) There's a gap here: see my comment on OPs post.

user795305