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

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)

Seu conselho será apreciado.

cross-validation error regularization validation optimization rf7
fonte

Respostas:

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$ $\infty$

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 e e a resposta . $(x_1,x_2,y)$ $x_1$ $x_2$ $y$

Dados de treinamento

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

$(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)

$(1,1,0.2),\ (1,2,0.4)$

glmnet::glmmetR $\lambda$ $1/\lambda$

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

Análise

$\beta=(\beta_1, \ldots, \beta_p)$ $x_i$ $y_i$

$\lambda \in [0, \infty)$ $\lambda=0$
$\hat\beta$ $\lambda$ $\hat\beta$
$\lambda\to\infty$ $\hat\beta\to 0$
$x$ $\hat\beta\to 0$ $\hat y(x) = f(x, \hat\beta) \to 0$
$y$ $\hat y$ $\mathcal{L}(y, \hat y)$ $|\hat y - y|$ $\mathcal{L}(|\hat y - y|)$

$(4)$

$\hat\beta(0)$ $(x_0, y_0)$ $f(x_0, \hat\beta(0))\ne 0$ $x_0$ $y_0=f(x_0, \hat\beta(0))/2$

$e: \lambda \to \mathcal{L}(y_0, f(x_0, \hat\beta(\lambda))$

$e(0) = \mathcal{L}(y_0, f(x_0, \hat\beta(0)) = \mathcal{L}(y_0, 2y_0) = \mathcal{L}(|y_0|)$ $y_0$
$\lim_{\lambda\to\infty}e(\lambda) = \mathcal{L}(y_0, 0) = \mathcal{L}(|y_0|)$ $\lambda\to\infty$ $\hat\beta(\lambda)\to 0$ $\hat{y}(x_0)\to 0$

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

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\lt \lambda \lt \infty$ $\lambda=0$ $\lambda\to\infty$
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 . $0$ $2y_0$ $e$ $e$ $e(\lambda)$ $\lambda$

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.) $\lambda\approx 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

@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 ))

(x, y)

$(\mathbf x, y)$

n

$n$

n \to \infty

$n \to \infty$

p

$p$

n

$n$

user795305

$\newcommand{\dbeta}{\frac{\partial}{\partial \lambda} \hat\beta_\lambda}$ $\newcommand{\ddbeta}{\frac{\partial^2}{{\partial \lambda}^2} \hat\beta_\lambda}$

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. $p$ $n$ $m$

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 . Com $X_{(1)} \in \mathbb{R}^{n \times p}$ $y_{(1)} \in \mathbb{R}^n$

\begin{matrix} (1) & {\hat{β}}_{λ} = \arg min_{β \in R^{p}} ‖ y_{(1)} - X_{(1)} β ‖_{2}^{2} + λ ‖ β ‖_{1}, \end{matrix}

$\hat\beta_\lambda = \arg\min_{\beta \in \mathbb{R}^p} \|y_{(1)} - X_{(1)} \beta\|_2^2 + \lambda \|\beta\|_1, \tag{1}$

{\hat{β}}_{λ}

$\hat\beta_\lambda$

X_{(2)} \in R^{m \times p}

$X_{(2)} \in \mathbb{R}^{m \times p}$

y_{(2)} \in R^{m}

$y_{(2)} \in \mathbb{R}^m$

\begin{matrix} (2) & \hat{λ} = \arg min_{λ \in R_{+}} ‖ y_{(2)} - X_{(2)} {\hat{β}}_{λ} ‖_{2}^{2}, \end{matrix}

$\hat\lambda = \arg\min_{\lambda \in \mathbb{R}_+} \|y_{(2)} - X_{(2)} \hat\beta_\lambda\|_2^2, \tag{2}$ estamos interessados em estudar a função de erro que dá origem ao nosso estimador controlado por dados .

e (λ) = ‖ y_{(2)} - X_{(2)} {\hat{β}}_{λ} ‖_{2}^{2}

$e(\lambda) = \|y_{(2)} - X_{(2)} \hat\beta_\lambda\|_2^2$

{\hat{β}}_{\hat{λ}}

$\hat\beta_{\hat\lambda}$

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)$ $X$ $y$

\begin{aligned} \frac{\partial^{2}}{{\partial λ}^{2}} ‖ y_{(2)} - X_{(2)} {\hat{β}}_{λ} ‖_{2}^{2} & = \frac{\partial}{\partial λ} {- 2 y_{(2)}^{T} X_{(2)} \frac{\partial}{\partial λ} {\hat{β}}_{λ} + 2 {\hat{β}}_{λ}^{T} X_{(2)}^{T} X_{(2)} \frac{\partial}{\partial λ} {\hat{β}}_{λ}} \\ = - 2 y_{(2)}^{T} X_{(2)} \frac{\partial^{2}}{{\partial λ}^{2}} {\hat{β}}_{λ} + 2 {({\hat{β}}_{λ})}^{T} X_{(2)}^{T} X_{(2)} \frac{\partial^{2}}{{\partial λ}^{2}} {\hat{β}}_{λ} + 2 \frac{\partial}{\partial λ} {\hat{β}}_{λ}^{T} X_{(2)}^{T} X_{(2)}^{T} \frac{\partial}{\partial λ} {\hat{β}}_{λ} \\ = - 2 {{(y_{(2)} - X_{(2)} {\hat{β}}_{λ})}^{T} \frac{\partial^{2}}{{\partial λ}^{2}} {\hat{β}}_{λ} - ‖ X_{(2)} \frac{\partial}{\partial λ} {\hat{β}}_{λ} ‖_{2}^{2}} . \end{aligned}

$\begin{align*} \frac{\partial^2}{{\partial \lambda}^2} \|y_{(2)} - X_{(2)} \hat\beta_\lambda\|_2^2 & = \frac{\partial}{\partial \lambda} \left\{ -2 y_{(2)}^T X_{(2)} \dbeta + 2 \hat\beta_\lambda^T X_{(2)}^T X_{(2)} \dbeta \right\} \\ & = -2 y_{(2)}^T X_{(2)} \ddbeta + 2 \left( \hat\beta_\lambda \right)^T X_{(2)}^T X_{(2)} \ddbeta + 2 \dbeta^T X_{(2)}^T X_{(2)}^T \dbeta \\ & = -2 \left\{ \left( y_{(2)} - X_{(2)} \hat\beta_\lambda \right)^T \ddbeta - \|X_{(2)} \dbeta\|_2^2 \right\}. \end{align*}$ 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 .

{\hat{β}}_{λ}

$\hat\beta_\lambda$

λ \notin K

$\lambda \not\in K$

K

$K$

\frac{\partial}{\partial λ} {\hat{β}}_{λ}

$\dbeta$

\frac{\partial^{2}}{{\partial λ}^{2}} {\hat{β}}_{λ}

$\ddbeta$

λ \notin K

$\lambda \not\in K$

\frac{\partial^{2}}{{\partial λ}^{2}} ‖ y_{(2)} - X_{(2)} {\hat{β}}_{λ} ‖_{2}^{2} = 2 ‖ X_{(2)} \frac{\partial}{\partial λ} {\hat{β}}_{λ} ‖_{2}^{2},

$\frac{\partial^2}{{\partial \lambda}^2} \|y_{(2)} - X_{(2)} \hat\beta_\lambda\|_2^2 = 2 \|X_{(2)} \dbeta\|_2^2,$

λ

$\lambda$

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)} \dbeta \neq 0$ $\lambda < \lambda_\max$ $e(\lambda)$ $\mathbb{R} \setminus K$ $\hat\beta_\lambda$ $e(\lambda)$

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)} \hat\beta_\lambda\|_2^2$ $\lambda$ $\|X_{(2)} \hat\beta_\lambda\|_2^2$ $e(\lambda)$ $\mathcal{L} \left( X_{(1)} \right) = \mathcal{L} \left( X_{(2)} \right)$

user795305
fonte

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.

\hat{β}

$\hat\beta$

λ

$\lambda$

\hat{e}

$\hat e$

\hat{β} (λ) = | λ - [λ] |

$\hat\beta(\lambda)=|\lambda-[\lambda]|$

[]

$[]$

y_{(2)} = 0

$y_{(2)}=0$

X_{(2)} = 1

$X_{(2)}=1$

\hat{e} (λ) = \hat{β} (λ)^{2}

$\hat {e}(\lambda)=\hat\beta(\lambda)^2$

whuber

@whuber Bom ponto! Obrigado! Vou editar este post em breve.

user795305