Se p> n, o laço seleciona no máximo n variáveis

Uma das motivações para a rede elástica foi a seguinte limitação do LASSO:

No caso $p > n$ , o laço seleciona no máximo n variáveis antes de saturar, devido à natureza do problema de otimização convexa. Esse parece ser um recurso limitante para um método de seleção de variáveis. Além disso, o laço não é bem definido, a menos que o limite na norma L1 dos coeficientes seja menor que um determinado valor.

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

Entendo que o LASSO é um problema de programação quadrática, mas também pode ser resolvido via LARS ou descida gradiente por elementos. Mas eu não entendo onde nestes algoritmos me deparo com um problema se onde é o número de preditores e é o tamanho da amostra. E por que esse problema é resolvido usando uma rede elástica, onde eu aumento o problema para variáveis que claramente excede . $p > n$ $p$ $n$ $p+n$ $p$

regression optimization feature-selection lasso user1137731
fonte

Se o laço restringe o uso para manter p <= n, por que isso é uma desvantagem, e não uma virtude. overfitting é um problema sério que ocorre quando p = n. O modelo com p = n é um modelo saturado e, com freqüência, se adapta a ele, porque ajustará perfeitamente os dados observados, mas não necessariamente predisporá bem os casos futuros.

Michael R. Chernick 30/09/12

O fato de o laço selecionar apenas até

variáveis pode ser visto como uma conseqüência do fato de poder ser resolvido usando (uma leve modificação) o algoritmo LARS, que admite apenas

variáveis no conjunto ativo a qualquer momento. O fato de isso não se sustentar no caso da rede elástica decorre essencialmente da incorporação da penalidade de

e, portanto, se comporta mais como a regressão de crista, a última das quais normalmente resulta em todos os coeficientes diferentes de zero.

n

$n$

n

$n$

ℓ_{2}

$\ell_2$

cardeal

Obrigado pelas respostas e como eu veria a descida do gradiente que no máximo n variáveis podem ser selecionadas: Apresentação em cs.cmu.edu/afs/cs/project/link-3/lafferty/www/ml-stat2/talks/ …

Artigo

@ usuário: Eu acho que você pode estar confundindo o problema matemático com sua solução numérica. O algoritmo LARS mostra que a solução de laço selecionará no máximo

variáveis. Isso é independente dos meios numéricos reais para chegar à solução, ou seja, o algoritmo LARS fornece informações sobre o problema, mas é claro que qualquer outro método que resolva o problema de forma equivalente deve ter a mesma propriedade! :-)

n

$n$

cardeal

Considere um recurso duplicado

vezes. Existirá um estimador de laço com exatamente

zero (mesmo que

). Portanto, sua afirmação não é verdadeira como está escrita.

p

$p$

p

$p$

p > n

$p>n$

user795305

Respostas:

Como dito, isso não é propriedade de um algoritmo, mas do problema de otimização. As condições KKT basicamente dar que para coeficiente para ser não-zero, tem de corresponder a uma correlação fixa com o resíduo ( é o parâmetro de regularização). $\beta_j$ $|X_j^t(y-X\beta)| = \lambda$ $\lambda$

Depois de resolver as várias complicações com valor absoluto etc., você fica com uma equação linear para cada coeficiente diferente de zero. Como a classificação da matriz é no máximo quando $X$ $n$ $p>n$ , esse é o número de equações que podem ser resolvidas e, portanto, existem no máximo n não zeros (a menos que haja redundâncias).

A propósito, isso é válido para qualquer função de perda, não apenas para o laço padrão com perda de . Portanto, é de fato uma propriedade da penalidade de laço. Existem muitos artigos que mostram essa visão da KKT e as conclusões resultantes. Posso apontar para o nosso artigo: Rosset e Zhu, Caminhos de soluções regularizadas lineares por partes, Anais de estatísticas de 2007 e refs. $L_2$

Saharon Rosset
fonte

KKT de quê? Além disso, é possível que você queira dizer perda de L1 ao falar sobre o laço padrão?

Miura

Olá Saharon e bem-vindo ao site. Você pode usar o LaTeX para tornar as fórmulas mais limpas (eu fiz isso na sua resposta) e não precisa assinar suas postagens, pois uma assinatura é adicionada automaticamente.

Peter Flom - Restabelece Monica

@miura: KKT significa Karush-Kuhn-Tucker. As condições KKT são certas equações que as soluções para problemas de otimização (suficientemente regulares) devem cumprir ( artigo da wikipedia ).

mogron 1/10/12

Eu só ver que Ryan Tibshirani tem um papel de trabalho muito relevante 'O Lasso Problema e singularidade.': Stat.cmu.edu/~ryantibs/papers/lassounique.pdf

user1137731

$n < p$ $X$ $n$ , portanto, a dimensão do seu espaço nulo (direito) é pelo menos $p - n$ . Escreva qualquer vetor neste espaço nulo como $z$ . Então, em qualquer ponto possível $\beta$ , pode-se sempre mover neste $p - n$ nulo tridimensional em direção aos eixos de coordenadas do $p$ tridimensional do ambiente, para chegar a um $\beta+z$ , onde (no máximo) $n$ $\beta_j$ s são diferentes de zero e a função objetivo do LASSO

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

has decreased.

user2969758
fonte

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

user795305