A taxa de erro é uma função convexa do parâmetro Regularization lambda?

11

Ao escolher o parâmetro de regularização lambda em Ridge ou Lasso, o método recomendado é tentar diferentes valores de lambda, medir o erro no conjunto de validação e finalmente escolher o valor de lambda que retorna o erro mais baixo.

Não é óbvio para mim se a função f (lambda) = erro é convexa. Poderia ser assim? Ou seja, essa curva poderia ter mais de um mínimo local (o que implicaria que encontrar um mínimo do erro em alguma região do lambda não exclui a possibilidade de que em alguma outra região exista um lambda retornando um erro ainda menor)

insira a descrição da imagem aqui

Seu conselho será apreciado.

rf7
fonte

Respostas:

11

A pergunta original perguntou se a função de erro precisa ser convexa. Não, não tem. A análise apresentada abaixo pretende fornecer algumas dicas e intuição sobre isso e a questão modificada, que pergunta se a função de erro pode ter vários mínimos locais.

Intuitivamente, não precisa haver nenhum relacionamento matematicamente necessário entre os dados e o conjunto de treinamento. Deveríamos ser capazes de encontrar dados de treinamento para os quais o modelo inicialmente é ruim, melhora com alguma regularização e depois piora novamente. A curva de erro não pode ser convexa nesse caso - pelo menos não se fizermos o parâmetro de regularização variar de a .0

Note que convexo não é equivalente a ter um mínimo único! No entanto, idéias semelhantes sugerem a possibilidade de múltiplos mínimos locais possíveis: durante a regularização, primeiro o modelo ajustado pode melhorar para alguns dados de treinamento sem alterar sensivelmente outros dados de treinamento e, posteriormente, melhora para outros dados de treinamento, etc. A combinação desses dados de treinamento deve produzir vários mínimos locais. Para manter a análise simples, não tentarei mostrar isso.

Editar (para responder à pergunta alterada)

Eu estava tão confiante na análise apresentada abaixo e na intuição por trás dela que decidi encontrar um exemplo da maneira mais grosseira possível: gerei pequenos conjuntos de dados aleatórios, executei um Lasso neles, calculei o erro quadrático total para um pequeno conjunto de treinamento, e plotou sua curva de erro. Algumas tentativas produziram uma com dois mínimos, que descreverei. Os vetores estão no formato para os recursos x 1 e x 2 e a resposta y .(x1,x2,y)x1x2y

Dados de treinamento

(1,1,0.1), (2,1,0.8), (1,2,1.2), (2,2,0.9)

Dados de teste

(1,1,0.2), (1,2,0.4)

glmnet::glmmetRλ1/λ

Uma curva de erro com vários mínimos locais

Figura


Análise

β=(β1,,βp)xiyi

  1. λ[0,)λ=0

  2. β^λβ^

  3. λβ^0

  4. xβ^0y^(x)=f(x,β^)0

  5. yy^L(y,y^)|y^y|L(|y^y|)

(4)

β^(0)(x0,y0)f(x0,β^(0))0x0y0=f(x0,β^(0))/2

e:λL(y0,f(x0,β^(λ))

  1. e(0)=L(y0,f(x0,β^(0))=L(y0,2y0)=L(|y0|)y0

  2. limλe(λ)=L(y0,0)=L(|y0|)λβ^(λ)0y^(x0)0

Assim, seu gráfico conecta continuamente dois pontos finais igualmente altos (e finitos).

Figura mostrando um gráfico possível de $ e $.

Qualitativamente, existem três possibilidades:

  • A previsão para o conjunto de treinamento nunca muda. Isso é improvável - praticamente qualquer exemplo que você escolher não terá essa propriedade.

  • Algumas previsões intermediárias para são piores do que no início ou no limite . Esta função não pode ser convexa.0<λ<λ=0λ

  • Todas as previsões intermediárias estão entre e . A continuidade implica que haverá pelo menos um mínimo de , perto do qual deve ser convexo. Mas como aproxima de uma constante finita assintoticamente, ela não pode ser convexa para grande o suficiente .02y0eee(λ)λ

A linha tracejada vertical na figura mostra onde o gráfico muda de convexo (à esquerda) para não convexo (à direita). (Também há uma região de não-convexidade próxima a nesta figura, mas esse não será necessariamente o caso em geral.)λ0

whuber
fonte
Obrigado pela sua resposta elaborada. Se possível, revise a pergunta conforme editei e atualize sua resposta.
Rf7 18/08
Ótima resposta (+1). Na prática, acho que muitas vezes não há tão poucos pontos de dados de treinamento e teste. A conclusão desta resposta muda quando há pontos de dados de treinamento e teste suficientes retirados da mesma distribuição (fixa e suficientemente regular)? Em particular, nesse cenário, existe um mínimo local exclusivo com alta probabilidade?
user795305
@ Ben Não é o número de pontos de teste que importa: esse resultado depende inteiramente da distribuição dos pontos de teste em relação à distribuição dos pontos de treinamento. Portanto, a questão "com alta probabilidade" não será respondida sem fazer algumas suposições específicas sobre a distribuição multivariada das variáveis ​​do regressor. Além disso, com muitas variáveis ​​em jogo, esse fenômeno de múltiplos mínimos locais será muito mais provável. Eu suspeito que a seleção aleatória de um grande conjunto de teste (com muitas vezes o número de observações como variáveis) pode muitas vezes têm um min global única.
whuber
1
@whuber Obrigado! Concordo: a distribuição (verdadeira) entre os pontos de treinamento e teste deve ser a mesma, e é preciso haver amostras suficientes para que as distribuições empíricas do conjunto de treinamento e teste tenham concordância. (Parece que eu expressei mal isso no meu comentário anterior.) Por exemplo, se tiver uma distribuição comum normal (com covariância não-regenerada), suspeito que a probabilidade da curva de erro ter um min local único converge para 1 (se, por exemplo, há amostras em treinamento e conjunto de teste com com fixo (ou mesmo aumentando lentamente em relação ao ))n n p n(x,y)nnpn
user795305
0

Esta resposta diz respeito especificamente ao laço (e não se aplica à regressão de crista).

Configuração

Suponha que temos co-variáveis que estamos usando para modelar uma resposta. Suponha que tenhamos pontos de dados de treinamento e pontos de dados de validação.pnm

Seja a entrada do treinamento e a resposta seja . Usaremos o laço nesses dados de treinamento. Ou seja, coloque uma família de coeficientes estimados a partir dos dados de treinamento. Escolheremos qual usar como estimador com base em seu erro em um conjunto de validação, com a entrada e a resposta . ComX(1)Rn×py(1)Rn

(1)β^λ=argminβRpy(1)X(1)β22+λβ1,
β^λX(2)Rm×py(2)Rm
(2)λ^=argminλR+y(2)X(2)β^λ22,
estamos interessados ​​em estudar a função de erro que dá origem ao nosso estimador controlado por dados .e(λ)=y(2)X(2)β^λ22β^λ^

Cálculo

Agora, calcularemos a segunda derivada do objetivo na equação , sem fazer nenhuma suposição distributiva nos ou . Usando diferenciação e alguma reorganização, computamos (formalmente) que (2)Xy

2λ2y(2)X(2)β^λ22=λ{2y(2)TX(2)λβ^λ+2β^λTX(2)TX(2)λβ^λ}=2y(2)TX(2)2λ2β^λ+2(β^λ)TX(2)TX(2)2λ2β^λ+2λβ^λTX(2)TX(2)Tλβ^λ=2{(y(2)X(2)β^λ)T2λ2β^λX(2)λβ^λ22}.
Como é linear por partes para ( sendo o conjunto finito de nós no caminho da solução do laço), a derivada é constante por partes e é zero para todos . Portanto, uma função não negativa de .β^λλKKλβ^λ2λ2β^λλK
2λ2y(2)X(2)β^λ22=2X(2)λβ^λ22,
λ

Conclusão

Se assumirmos que é extraído de alguma distribuição contínua independente de , o vetor quase certamente para . Portanto, a função de erro possui uma segunda derivada em que é (quase certamente) estritamente positiva. No entanto, sabendo que é contínuo, sabemos que o erro de validação é contínuo.X(2){X(1),y(1)}X(2)λβ^λ0λ<λmaxe(λ)RKβ^λe(λ)

Finalmente, a partir do laço duplo, sabemos que diminui monotonicamente à medida que aumenta. Se pudermos estabelecer que também é monotônico, a forte convexidade de segue. No entanto, isso ocorre com alguma probabilidade se aproximando de um se . (Eu preencherei detalhes aqui em breve.)X(1)β^λ22λX(2)β^λ22e(λ)L(X(1))=L(X(2))

user795305
fonte
1
Você depende apenas de como uma função linear contínua por partes de para concluir é estritamente convexa. Vamos ver se essa dedução é geralmente válida. Uma dessas funções é(onde indica arredondamento para o número inteiro mais próximo). Suponha que e , de modo que . Essa função de erro possui infinitos mínimos locais. Não é convexo - é apenas convexo em todos os lugares, exceto em pontos isolados! Isso me leva a acreditar que você está fazendo suposições não declaradas adicionais. β^λe^β^(λ)=|λ[λ]|[]y(2)=0X(2)=1e^(λ)=β^(λ)2
whuber
@whuber Bom ponto! Obrigado! Vou editar este post em breve.
user795305