Le taux d'erreur est-il une fonction convexe du paramètre de régularisation lambda?

En choisissant le paramètre de régularisation lambda dans Ridge ou Lasso, la méthode recommandée consiste à essayer différentes valeurs de lambda, à mesurer l'erreur dans l'ensemble de validation et enfin à choisir la valeur de lambda qui renvoie l'erreur la plus faible.

Ce n'est pas pour moi si la fonction f (lambda) = error est convexe. Serait-ce ainsi? C'est-à-dire que cette courbe pourrait avoir plus d'un minimum local (ce qui impliquerait que trouver un minimum de l'erreur dans une région de lambda n'exclut pas la possibilité que dans une autre région il y ait un lambda renvoyant une erreur encore plus petite)

Vos conseils seront appréciés.

cross-validation error regularization validation optimization rf7
la source

Réponses:

La question initiale demandait si la fonction d'erreur devait être convexe. Non. L'analyse présentée ci-dessous vise à fournir un aperçu et une intuition à ce sujet et à la question modifiée, qui demande si la fonction d'erreur pourrait avoir plusieurs minima locaux.

Intuitivement, il ne doit pas y avoir de relation mathématiquement nécessaire entre les données et l'ensemble d'entraînement. Nous devrions être en mesure de trouver des données de formation pour lesquelles le modèle est initialement mauvais, s'améliore avec une certaine régularisation, puis empire à nouveau. La courbe d'erreur ne peut pas être convexe dans ce cas - du moins pas si nous faisons varier le paramètre de régularisation de à . $0$ $\infty$

Notez que convexe n'est pas équivalent à avoir un minimum unique! Cependant, des idées similaires suggèrent que plusieurs minima locaux sont possibles: pendant la régularisation, le modèle ajusté pourrait d'abord s'améliorer pour certaines données d'entraînement sans changer de façon appréciable pour d'autres données d'entraînement, puis plus tard il s'améliorerait pour d'autres données d'entraînement, etc. la combinaison de ces données de formation devrait produire de multiples minima locaux. Pour garder l'analyse simple, je n'essaierai pas de le montrer.

Modifier (pour répondre à la question modifiée)

J'étais tellement confiant dans l'analyse présentée ci-dessous et l'intuition derrière elle que j'ai commencé à trouver un exemple de la manière la plus grossière possible: j'ai généré de petits ensembles de données aléatoires, j'ai exécuté un Lasso sur eux, calculé l'erreur quadratique totale pour un petit ensemble d'entraînement, et tracé sa courbe d'erreur. Quelques tentatives en ont produit un avec deux minima, que je décrirai. Les vecteurs sont sous la forme pour les entités et et la réponse . $(x_1,x_2,y)$ $x_1$ $x_2$ $y$

Données d'entraînement

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

Données de test

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

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

Le Lasso a été exécuté en utilisant glmnet::glmmetin R, avec tous les arguments laissés à leurs valeurs par défaut. Les valeurs de sur l'axe x sont les inverses des valeurs rapportées par ce logiciel (car il paramètre sa pénalité avec ). $\lambda$ $1/\lambda$

Une courbe d'erreur avec plusieurs minima locaux

Une analyse

Examinons toute méthode de régularisation pour ajuster les paramètres aux données et aux réponses correspondantes qui ont ces propriétés communes à Ridge Regression et Lasso: $\beta=(\beta_1, \ldots, \beta_p)$ $x_i$ $y_i$

(Paramétrage) La méthode est paramétrée par des nombres réels , avec le modèle non régularisé correspondant à . $\lambda \in [0, \infty)$ $\lambda=0$
(Continuité) L'estimation des paramètres dépend en permanence de et les valeurs prévues pour toutes les fonctionnalités varient continuellement avec . $\hat\beta$ $\lambda$ $\hat\beta$
(Rétrécissement) Comme , . $\lambda\to\infty$ $\hat\beta\to 0$
(Finitude) Pour tout vecteur d'entité , comme , la prédiction . $x$ $\hat\beta\to 0$ $\hat y(x) = f(x, \hat\beta) \to 0$
(Erreur monotone) La fonction d'erreur comparant toute valeur à une valeur prédite , , augmente avec l'écartde sorte que, avec un certain abus de notation, nous pouvons l'exprimer comme . $y$ $\hat y$ $\mathcal{L}(y, \hat y)$ $|\hat y - y|$ $\mathcal{L}(|\hat y - y|)$

(Le zéro dans peut être remplacé par n'importe quelle constante.) $(4)$

Supposons que les données soient telles que l'estimation initiale (non régularisée) des paramètres n'est pas nulle. Let la construction d' un ensemble de données d'apprentissage constitué par une observation pour laquelle . (S'il n'est pas possible de trouver un tel , alors le modèle initial ne sera pas très intéressant!) Définissez . $\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$

Les hypothèses impliquent que la courbe d'erreur a les propriétés suivantes: $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|)$ (en raison de le choix de ). $y_0$
$\lim_{\lambda\to\infty}e(\lambda) = \mathcal{L}(y_0, 0) = \mathcal{L}(|y_0|)$ (car comme , , d'où ). $\lambda\to\infty$ $\hat\beta(\lambda)\to 0$ $\hat{y}(x_0)\to 0$

Ainsi, son graphique relie en permanence deux points d'extrémité également élevés (et finis).

Qualitativement, il y a trois possibilités:

La prédiction pour l'ensemble d'entraînement ne change jamais. C'est peu probable - à peu près tout exemple que vous choisirez n'aura pas cette propriété.
Certaines prédictions intermédiaires pour sont pires qu'au début ou dans la limite . Cette fonction ne peut pas être convexe. $0\lt \lambda \lt \infty$ $\lambda=0$ $\lambda\to\infty$
Toutes les prédictions intermédiaires se situent entre et . La continuité implique qu'il y aura au moins un minimum de , près duquel doit être convexe. Mais comme s'approche d'une constante finie asymptotiquement, elle ne peut pas être convexe pour un suffisamment grand . $0$ $2y_0$ $e$ $e$ $e(\lambda)$ $\lambda$

La ligne pointillée verticale sur la figure montre où le tracé passe de convexe (à gauche) à non convexe (à droite). (Il y a aussi une région de non-convexité près de sur cette figure, mais ce ne sera pas nécessairement le cas en général.) $\lambda\approx 0$

whuber
la source

Merci pour votre réponse élaborée. Si possible, passez en revue la question au fur et à mesure de ma modification et mettez à jour votre réponse.

rf7

Excellente réponse (+1). Dans la pratique, je pense qu'il n'y a souvent pas si peu de points de données de formation et de test. La conclusion de cette réponse change-t-elle lorsqu'il y a suffisamment de points de données de formation et de test tirés de la même distribution (fixe et suffisamment régulière)? En particulier, dans ce scénario, existe-t-il un minimum local unique avec une probabilité élevée?

user795305

@Ben Ce n'est pas le nombre de points de test qui compte: ce résultat dépend entièrement de la distribution des points de test par rapport à la distribution des points d'entraînement. Par conséquent, la question de «avec une probabilité élevée» ne sera pas résolue sans formuler des hypothèses spécifiques sur la distribution multivariée des variables régressives. De plus, avec de nombreuses variables en jeu, ce phénomène de minima locaux multiples sera beaucoup plus probable. Je soupçonne que la sélection aléatoire d'un grand ensemble de tests (avec plusieurs fois plus d'observations que de variables) pourrait souvent avoir un min global unique.

whuber

@whuber Merci! Je suis d'accord: la (vraie) distribution entre les points d'entraînement et de test doit être la même, et il doit y avoir suffisamment d'échantillons pour que les distributions empiriques de l'ensemble de formation et de test soient d'accord. (Il semble que je l'ai mal formulé dans mon commentaire précédent.) Par exemple, si a une distribution normale commune (avec une covariance non dégénérée), je soupçonne la probabilité que la courbe d'erreur ayant un min local unique converge vers 1 (si, disons, il y a échantillons dans l'ensemble de formation et de test avec avec fixe (ou même en augmentant lentement par rapport à ))

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

Cette réponse concerne spécifiquement le lasso (et ne vaut pas pour la régression de crête.)

Installer

Supposons que nous ayons covariables que nous utilisons pour modéliser une réponse. Supposons que nous ayons points de données d'apprentissage et points de données de validation. $p$ $n$ $m$

Soit l'entrée d'entraînement et la réponse . Nous utiliserons le lasso sur ces données d'entraînement. Autrement dit, mettez une famille de coefficients estimés à partir des données d'entraînement. Nous choisirons le à utiliser comme estimateur en fonction de son erreur sur un ensemble de validation, avec l'entrée et la réponse . Avec $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}$ nous souhaitons étudier la fonction d'erreur qui donne naissance à notre estimateur basé sur les données .

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

Calcul

Nous allons maintenant calculer la dérivée seconde de l'objectif dans l' équation , sans faire aucune des hypothèses sur la répartition « s ou s ». En utilisant la différenciation et une certaine réorganisation, nous calculons (formellement) 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*}$ Étant donné que est linéaire par morceaux pour (pour étant l'ensemble fini de nœuds dans le chemin de la solution au lasso), la dérivée est constante par morceaux et est zéro pour tous . Par conséquent, une fonction non négative 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$

Conclusion

Si nous supposons en outre que est tiré d'une distribution continue indépendante de , le vecteur presque sûrement pour . Par conséquent, la fonction d'erreur a une dérivée seconde sur qui est (presque sûrement) strictement positive. Cependant, sachant que est continue, nous savons que l'erreur de validation est continue. $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)$

Enfin, à partir du double du lasso, nous savons que diminue de façon monotone à mesure que augmente. Si nous pouvons établir que est également monotone, alors la forte convexité de suit. Cependant, cela vaut avec une probabilité approchant une si . (Je remplirai les détails ici bientôt.) $\|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
la source

Vous vous basez uniquement sur comme une fonction linéaire continue par morceaux de pour conclure que est strictement convexe. Voyons si cette déduction est généralement valable. Une de ces fonctions est(où indique l'arrondi à l'entier le plus proche). Supposons que et , de sorte que . Cette fonction d'erreur a une infinité de minima locaux. Ce n'est pas convexe - c'est seulement convexe partout sauf à des points isolés! Cela m'amène à croire que vous faites des hypothèses supplémentaires non énoncées.

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

blanc

@whuber Bon point! Merci! Je modifierai prochainement ce message.

user795305