Dérivation d'une solution de lasso sous forme fermée

Pour le problème de lasso tels que . Je vois souvent le résultat de seuillage souple pour le cas orthonormé . On prétend que la solution peut être "facilement démontrée", mais je n'ai jamais vu de solution efficace. Quelqu'un en a-t-il déjà vu une ou a-t-il déjà fait la dérivation? $\min_\beta (Y-X\beta)^T(Y-X\beta)$ $\|\beta\|_1 \leq t$

β_{j}^{lasso} = s g n (β_{j}^{LS}) (| β_{j}^{LS} | - γ)^{+}

$\beta_j^{\text{lasso}}= \mathrm{sgn}(\beta^{\text{LS}}_j)(|\beta_j^{\text{LS}}|-\gamma)^+$

X

$X$

lasso Gary
la source

Cela semble un peu confus. Au début, vous assumez une contrainte

t

$t$ et dans la solution, vous introduisez un paramètre

γ

$\gamma$ . J'imagine que vous avez l'intention de relier ces deux problèmes via le double problème, mais vous pouvez peut-être préciser ce que vous recherchez.

Cardinal

Répondre partiellement à @cardinal, trouver le

β

$\beta$ qui minimise

(Y - X β)^{'} (Y - X β)

$(Y-X\beta )'(Y-X\beta )$ soumis à

‖ β ‖_{1} \leq t

$\|\beta\|_1 \leq t$ équivaut à trouver le

β

$\beta$ qui minimise

(Y - X β)^{'} (Y - X β) + γ \sum_{j} | β_{j} |

$(Y-X\beta )'(Y-X\beta )+\gamma\sum_j |\beta_j |$ . Il existe une relation 1-1 entre

t

$t$ et

γ

$\gamma$ . Pour "facilement" comprendre pourquoi le résultat du seuillage souple est vrai, je vous recommande de résoudre la deuxième expression (dans mon commentaire).

Une autre remarque, lors de la recherche de la

β

$\beta$ minimisant

(Y - X β)^{'} (Y - X β) + γ \sum_{j} | β_{j} |

$(Y-X\beta )'(Y-X\beta )+\gamma\sum_j |\beta_j |$ ,

le problème dans les cas

β_{j} > 0

$\beta_j >0$ ,

β_{j} < 0

$\beta_j<0$ et

β = 0

$\beta=0$ .

@ cardinal Ah oui, 1-1 est incorrect. Correction: pour chaque

t \geq 0

$t\geq0$ , vous pouvez trouver un

γ \geq 0

$\gamma\geq 0$ .

Merci pour une bonne discussion! Je suis tombé sur cette vidéo sur coursera - Dériver de la mise à jour de la descente de coordonnées au lasso , qui est très pertinente pour cette discussion, et présente la solution de manière très élégante.

Cela

Réponses:

Cela peut être attaqué de différentes manières, y compris par des approches relativement économiques via les conditions de Karush – Kuhn – Tucker .

Ci-dessous, un argument alternatif assez élémentaire.

La solution des moindres carrés pour un dessin orthogonal

Supposons que soit composé de colonnes orthogonales. La solution des moindres carrés est alors $X$

{\hat{β}}^{LS} = (X^{T} X)^{- 1} X^{T} y = X^{T} y .

$\newcommand{\bls}{\hat{\beta}^{{\small \text{LS}}}}\newcommand{\blasso}{\hat{\beta}^{{\text{lasso}}}} \bls = (X^T X)^{-1} X^T y = X^T y \>.$

Quelques problèmes équivalents

Via la forme lagrangienne, il est évident qu'un problème équivalent à celui considéré dans la question est

min_{β} \frac{1}{2} ‖ y - X β ‖_{2}^{2} + γ ‖ β ‖_{1} .

$\min_\beta \frac{1}{2} \|y - X \beta\|_2^2 + \gamma \|\beta\|_1 \>.$

En élargissant le premier terme, on obtient et depuis ne contient pas des variables d’intérêt, nous pouvons l’écarter et envisager un autre problème équivalent, $\frac{1}{2} y^T y - y^T X \beta + \frac{1}{2}\beta^T \beta$ $y^T y$

min_{β} (- y^{T} X β + \frac{1}{2} ‖ β ‖^{2}) + γ ‖ β ‖_{1} .

$\min_\beta (- y^T X \beta + \frac{1}{2} \|\beta\|^2) + \gamma \|\beta\|_1 \>.$

En notant que , le problème précédent peut être réécrit sous la forme $\bls = X^T y$

min_{β} \sum_{i = 1}^{p} - {\hat{β}}_{i}^{LS} β_{i} + \frac{1}{2} β_{i}^{2} + γ | β_{i} | .

$\min_\beta \sum_{i=1}^p - \bls_i \beta_i + \frac{1}{2} \beta_i^2 + \gamma |\beta_i| \> .$

Notre fonction d'objectif est maintenant une somme d'objectifs, chacun correspondant à une variable distincte , afin qu'ils puissent être résolus individuellement. $\beta_i$

Le tout est égal à la somme de ses parties

Fixer un certain . Ensuite, nous voulons minimiser $i$

L_{i} = - {\hat{β}}_{i}^{LS} β_{i} + \frac{1}{2} β_{i}^{2} + γ | β_{i} | .

$\mathcal L_i = -\bls_i \beta_i + \frac{1}{2}\beta_i^2 + \gamma |\beta_i| \> .$

Si , alors nous devons avoir sinon nous pourrions retourner son signe et obtenir une valeur inférieure pour la fonction objectif. De même si , alors nous devons choisir . $\bls_i > 0$ $\beta_i \geq 0$ $\bls_i < 0$ $\beta_i \leq 0$

Cas 1 : . Depuis , différenciant par rapport à et en le fixant à zéro , nous obtenons et ceci n’est réalisable que si le droite n’est pas négatif, donc dans ce cas la solution actuelle est $\bls_i > 0$ $\beta_i \geq 0$

L_{i} = - {\hat{β}}_{i}^{LS} β_{i} + \frac{1}{2} β_{i}^{2} + γ β_{i},

$\mathcal L_i = -\bls_i \beta_i + \frac{1}{2}\beta_i^2 + \gamma \beta_i \> ,$

β_{i}

$\beta_i$

β_{i} = {\hat{β}}_{i}^{LS} - γ

$\beta_i = \bls_i - \gamma$

{\hat{β}}_{i}^{lasso} = ({\hat{β}}_{i}^{LS} - γ)^{+} = s g n ({\hat{β}}_{i}^{LS}) (| {\hat{β}}_{i}^{LS} | - γ)^{+} .

$\blasso_i = (\bls_i - \gamma)^+ = \mathrm{sgn}(\bls_i)(|\bls_i| - \gamma)^+ \>.$

Cas 2 : . Cela implique que nous devons avoir et donc En différenciant par rapport à et en fixant la valeur à zéro, nous obtenons . Mais, encore une fois, pour que cela soit réalisable, nous avons besoin de , qui est obtenu en prenant $\bls_i \leq 0$ $\beta_i \leq 0$

L_{i} = - {\hat{β}}_{i}^{LS} β_{i} + \frac{1}{2} β_{i}^{2} - γ β_{i} .

$\mathcal L_i = -\bls_i \beta_i + \frac{1}{2}\beta_i^2 - \gamma \beta_i \> .$

β_{i}

$\beta_i$

β_{i} = {\hat{β}}_{i}^{LS} + γ = s g n ({\hat{β}}_{i}^{LS}) (| {\hat{β}}_{i}^{LS} | - γ)

$\beta_i = \bls_i + \gamma = \mathrm{sgn}(\bls_i)(|\bls_i| - \gamma)$

β_{i} \leq 0

$\beta_i \leq 0$

{\hat{β}}_{i}^{lasso} = s g n ({\hat{β}}_{i}^{LS}) (| {\hat{β}}_{i}^{LS} | - γ)^{+} .

$\blasso_i = \mathrm{sgn}(\bls_i)(|\bls_i| - \gamma)^+ \>.$

Dans les deux cas, nous obtenons le formulaire souhaité et nous avons donc terminé.

Remarques finales

cardinal
la source

Grande écriture @ cardinal!

Gary

+1 Toute la seconde moitié peut être remplacée par la simple observation que la fonction objectif est une union de parties de deux paraboles convexes avec des sommets à , où le signe négatif est pris pour et le positif sinon. La formule est juste une manière élégante de choisir le sommet inférieur.

β \to \frac{1}{2} β^{2} + (\pm γ - \hat{β}) β

$\beta\to\frac{1}{2}\beta^2+(\pm\gamma-\hat{\beta})\beta$

\pm γ - \hat{β}

$\pm\gamma-\hat{\beta}$

β < 0

$\beta\lt 0$

whuber

Si possible, j'aimerais voir les dérivations en utilisant les conditions d'optimalité KKT. Quels sont les autres moyens d'obtenir ce résultat?

user1137731

@ Cardinal: merci pour cette belle dérivation. Une observation. Si je me souviens bien, une matrice à colonnes orthogonales n’est pas identique à une matrice orthogonale (ou orthonormée). Alors pour une matrice diagonale (pas nécessairement une matrice d'identité). Avec l'hypothèse de matrice orthogonale (comme dans la question initiale), nous avons et tout est superbe :)

X^{'} X = D

$X'X=D$

D

$D$

X^{'} X = I

$X'X=I$

Oleg Melnikov

@ cardinal Je ne comprends pas pourquoi vous dites "sinon nous pourrions retourner son signe et obtenir une valeur inférieure pour la fonction objectif". Nous prenons la dérivée de la fonction objectif. Alors que se passe-t-il si la fonction objectif est supérieure ou inférieure, qui s'en soucie. Tout ce qui nous importe, c’est que le dérivé est réglé à zéro, nous nous soucions des extrema. Qu'il soit supérieur ou inférieur d'une constante n'affecte pas l'argmin.

utilisateur13985

On suppose que la covariables , les colonnes de , sont également normalisées de sorte que . C’est pour plus de commodité par la suite: sans cela, la notation n’est que plus lourde puisque n’est que diagonale. Supposons en outre que . Ceci est une hypothèse nécessaire pour que le résultat soit valide. Définissez l’estimateur des moindres carrés . Ensuite, la forme (lagrangienne) de l’estimateur de lasso $x_j$ $X \in \mathbb{R}^{n \times p}$ $X^T X = I$ $X^T X$ $n \geq p$ $\hat\beta_{OLS} = \arg\min_\beta \|y - X \beta\|_2^2$

\begin{aligned} (defn.) & {\hat{β}}_{λ} & = \arg min_{β} \frac{1}{2 n} ‖ y - X β ‖_{2}^{2} + λ ‖ β ‖_{1} \\ (OLS is projection) & = \arg min_{β} \frac{1}{2 n} ‖ X {\hat{β}}_{O L S} - X β ‖_{2}^{2} + λ ‖ β ‖_{1} \\ (X^{T} X = I) & = \arg min_{β} \frac{1}{2 n} ‖ {\hat{β}}_{O L S} - β ‖_{2}^{2} + λ ‖ β ‖_{1} \\ (algebra) & = \arg min_{β} \frac{1}{2} ‖ {\hat{β}}_{O L S} - β ‖_{2}^{2} + n λ ‖ β ‖_{1} \\ (defn.) & = {p r o x}_{n λ ‖ \cdot ‖_{1}} ({\hat{β}}_{O L S}) \\ (takes some work) & = S_{n λ} ({\hat{β}}_{O L S}), \end{aligned}

$\begin{align*} \hat\beta_\lambda & = \arg\min_{\beta} \frac{1}{2n} \|y - X \beta\|_2^2 + \lambda \|\beta\|_1 \tag{defn.} \\ & = \arg\min_\beta \frac{1}{2n} \|X \hat\beta_{OLS} - X \beta\|_2^2 + \lambda \|\beta\|_1 \tag{OLS is projection} \\ & = \arg\min_\beta \frac{1}{2n} \|\hat\beta_{OLS} - \beta\|_2^2 + \lambda \|\beta\|_1 \tag{$X^TX=I$} \\ & = \arg\min_\beta \frac{1}{2} \|\hat\beta_{OLS} - \beta\|_2^2 + n \lambda \|\beta\|_1 \tag{algebra} \\ & = \mathrm{prox}_{n \lambda \|\cdot\|_1} \left( \hat\beta_{OLS} \right) \tag{defn.} \\ & = S_{n \lambda} \left( \hat\beta_{OLS} \right) \tag{takes some work}, \end{align*}$ \ end {align *} où est l'opérateur proximal d'une fonction et seuils variables de la quantité

{p r o x}_{f}

$\mathrm{prox}_f$

f

$f$

S_{α}

$S_{\alpha}$

α

$\alpha$ .

C’est une dérivation qui ignore la dérivation détaillée de l’opérateur proximal élaborée par Cardinal, mais, j’espère, clarifie les principales étapes permettant de créer une forme fermée.

utilisateur795305
la source