¿Es la tasa de error una función convexa del parámetro de regularización lambda?

Al elegir el parámetro de regularización lambda en Ridge o Lasso, el método recomendado es probar diferentes valores de lambda, medir el error en el conjunto de validación y finalmente elegir el valor de lambda que devuelve el error más bajo.

No está claro para mí si la función f (lambda) = error es convexa. ¿Podría ser así? Es decir, esta curva podría tener más de un mínimo local (lo que implicaría que encontrar un mínimo del Error en alguna región de lambda no excluye la posibilidad de que en alguna otra región haya una lambda que devuelva un Error aún más pequeño)

Su consejo será apreciado

cross-validation error regularization validation optimization rf7
fuente

Respuestas:

La pregunta original preguntaba si la función de error debe ser convexa. No, no lo hace. El análisis presentado a continuación tiene la intención de proporcionar una idea e intuición sobre esto y la pregunta modificada, que pregunta si la función de error podría tener múltiples mínimos locales.

Intuitivamente, no tiene que haber ninguna relación matemáticamente necesaria entre los datos y el conjunto de entrenamiento. Deberíamos poder encontrar datos de entrenamiento para los cuales el modelo inicialmente es pobre, mejora con cierta regularización y luego empeora nuevamente. La curva de error no puede ser convexa en ese caso, al menos no si hacemos que el parámetro de regularización varíe de a . $0$ $\infty$

¡Tenga en cuenta que convexo no es equivalente a tener un mínimo único! Sin embargo, ideas similares sugieren que son posibles múltiples mínimos locales: durante la regularización, primero el modelo ajustado podría mejorar para algunos datos de entrenamiento sin cambiar apreciablemente para otros datos de entrenamiento, y luego mejorará para otros datos de entrenamiento, etc. La combinación de dichos datos de entrenamiento debería producir múltiples mínimos locales. Para mantener el análisis simple, no intentaré mostrar eso.

Editar (para responder a la pregunta modificada)

Tenía tanta confianza en el análisis presentado a continuación y la intuición detrás de esto que empecé a buscar un ejemplo de la manera más cruda posible: generé pequeños conjuntos de datos aleatorios, ejecuté un Lazo sobre ellos, calculé el error cuadrado total para un pequeño conjunto de entrenamiento, y trazó su curva de error. Algunos intentos produjeron uno con dos mínimos, que describiré. Los vectores están en la forma para las características y y la respuesta . $(x_1,x_2,y)$ $x_1$ $x_2$ $y$

Datos de entrenamiento

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

Datos de prueba

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

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

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

Una curva de error con mínimos locales múltiples

Análisis

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

Por lo tanto, su gráfico conecta continuamente dos puntos finales igualmente altos (y finitos).

Cualitativamente, hay tres posibilidades:

La predicción para el conjunto de entrenamiento nunca cambia. Esto es poco probable: casi cualquier ejemplo que elija no tendrá esta propiedad.
Algunas predicciones intermedias para son peores que al inicio o en el límite . Esta función no puede ser convexa. $0\lt \lambda \lt \infty$ $\lambda=0$ $\lambda\to\infty$
Todas las predicciones intermedias se encuentran entre y . La continuidad implica que habrá al menos un mínimo de , cerca del cual debe ser convexo. Pero dado que aproxima a una constante finita asintóticamente, no puede ser convexo para suficientemente grande . $0$ $2y_0$ $e$ $e$ $e(\lambda)$ $\lambda$

La línea discontinua vertical en la figura muestra dónde cambia el gráfico de convexo (a su izquierda) a no convexo (a la derecha). (También hay una región de no convexidad cerca de en esta figura, pero este no será necesariamente el caso en general). $\lambda\approx 0$

whuber
fuente

Gracias por tu elaborada respuesta. Si es posible, revise la pregunta tal como la edité y actualice su respuesta.

rf7

Gran respuesta (+1). En la práctica, creo que a menudo no hay tan pocos puntos de entrenamiento y datos de prueba. ¿Cambia la conclusión de esta respuesta cuando hay suficientes puntos de entrenamiento y datos de prueba extraídos de la misma distribución (fija y suficientemente regular)? En particular, en este escenario, ¿existe un mínimo local único con alta probabilidad?

user795305

@Ben No es el número de puntos de prueba lo que importa: este resultado depende completamente de la distribución de puntos de prueba en relación con la distribución de puntos de entrenamiento. Por lo tanto, la cuestión de "con alta probabilidad" no será responsable sin hacer algunas suposiciones específicas sobre la distribución multivariada de las variables regresoras. Además, con muchas variables en juego, este fenómeno de mínimos locales múltiples será mucho más probable. Me sospechar que la selección aleatoria de un conjunto de ensayo grande (con tantas veces como muchas observaciones como variables) pueden a menudo tienen una única min mundial.

whuber

@whuber Gracias! Estoy de acuerdo: la distribución (verdadera) entre los puntos de entrenamiento y prueba debe ser la misma, y debe haber suficientes muestras para que las distribuciones empíricas del entrenamiento y el conjunto de prueba tengan un acuerdo. (Parece que lo expresé mal en mi comentario anterior). Por ejemplo, si tiene una distribución normal conjunta (con covarianza no degenerada), sospecho que la probabilidad de que la curva de error tenga un min local único converge a 1 (si, por ejemplo, hay muestras en el conjunto de entrenamiento y prueba con con fijo (o incluso aumentando lentamente en relación con ))

(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 respuesta se refiere específicamente al lazo (y no es válido para la regresión de cresta).

Preparar

Supongamos que tenemos covariables que estamos usando para modelar una respuesta. Supongamos que tenemos puntos de datos de entrenamiento puntos de datos de validación. $p$ $n$ $m$

Deje que la entrada de entrenamiento sea y la respuesta sea . Usaremos el lazo en estos datos de entrenamiento. Es decir, ponga una familia de coeficientes estimados a partir de los datos de entrenamiento. qué usar como nuestro estimador en función de su error en un conjunto de validación, con la entrada y la respuesta . Con $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}$ nos interesa estudiar la función de error que da lugar a nuestro estimador basado en datos .

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

Ahora, vamos a calcular la segunda derivada del objetivo en la ecuación , sin hacer ningún supuestos de distribución en la 's o ' s. Utilizando la diferenciación y alguna reorganización, calculamos (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 es lineal por partes para (para es el conjunto finito de nudos en la ruta de la solución del lazo), la derivada es constante por partes y es cero para todos . Por lo tanto, una función no 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$

Conclusión

Si suponemos además que se extrae de una distribución continua independiente de , el vector casi seguro para . Por lo tanto, la función de error tiene una segunda derivada en que es (casi seguramente) estrictamente positiva. Sin embargo, sabiendo que es continuo, sabemos que el error de validación es continuo. $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, del lazo dual, sabemos que disminuye monotónicamente a medida que aumenta. Si podemos establecer que también es monótono, entonces sigue la fuerte convexidad de . Sin embargo, esto se cumple con una probabilidad cercana a uno si . (Completaré los detalles aquí pronto). $\|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)$

usuario795305
fuente

Solo confía en que es una función lineal continua por partes de para concluir que es estrictamente convexo. Veamos si esa deducción es generalmente válida. Una de esas funciones es(donde denota redondeo al entero más cercano). Supongamos que y , de modo que . Esta función de error tiene infinitos mínimos locales. No es convexo, ¡solo es convexo en todas partes, excepto en puntos aislados! Eso me lleva a creer que estás haciendo suposiciones adicionales no declaradas.

\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 Buen punto! ¡Gracias! Editaré esta publicación más pronto.

user795305