Programmation quadratique et Lasso

J'essaie d'effectuer une régression au lasso, qui a la forme suivante:

Minimiser $w$ dans $(Y - Xw)'(Y - Xw) + \lambda \;|w|_1$

Étant donné un $\lambda$ , on m'a conseillé de trouver le optimal $w$ à l'aide de la programmation quadratique, qui prend la forme suivante:

Minimiser $x$ en , sous réserve de $\frac{1}{2} x'Qx + c'x$ $Ax \le b.$

Maintenant, je me rends compte que le terme doit être transformé en terme de contrainte , ce qui est assez simple. Cependant, je ne vois pas comment je pourrais transférer le premier terme de la première équation dans le premier terme du second. Je ne pouvais pas trouver grand-chose sur le net, alors j'ai décidé de demander ici. $\lambda$ $Ax \le b$

regression lasso quadratic-form spurra
la source

Réponses:

En gardant à l'esprit que nous travaillons avec comme variable ' ' dans le formulaire standard, développons et collectons les termes dans $w$ $x$ $(Y - Xw)'(Y - Xw)$ et dans et , et constantes. $w'\, [\,_{^{^\text{something}}}]\,w$ $w'$ $w$

Expliquez pourquoi vous pouvez ignorer les constantes.

Expliquez pourquoi vous pouvez combiner les termes et . $w'$ $w$

Comme BananaCode a maintenant compris avec un peu de leader le long du chemin, vous pouvez soit écrire et $Q=2X'X$ ouplus simplement, vous pouvez simplement écrire et (puisque et ont le même argument pour tout ). $c=-2X'Y$ $Q=X'X$ $c=-X'Y$ $f(x)$ $kf(x)$ $k>0$

Glen_b -Reinstate Monica
la source

Les constantes peuvent être ignorées, car si x_ est le minimum de f (x), alors x_ + c est le minimum de f (x) + c, donc nous pouvons ignorer la constante c. Je vais modifier ma question pour montrer où je suis resté coincé.

spurra

BananaCode votre explication a plusieurs défauts. Si par "est le minimum à

" vous voulez dire "est l'argument selon lequel

est minimisé", vous dites quelque chose comme "

f (x)

$f(x)$

f (x)

$f(x)$

est l'

". Mais votre conclusion est fausse. Si vous ajoutez

, vous n'ajoutez pas

à l'argmin.

x^{*}

$x^*$

argmin

$\text{argmin}$

f

$f$

c

$c$

f

$f$

c

$c$

Glen_b -Reinstate Monica

Voyez où j'ai écrit

dans ma réponse? Quel estquelque chose quevous avez maintenant entre le

et le

au bas de votre question ??

w^{'} [something] w

$w'\, [\,\text{something}]\,w$

w^{'}

$w'$

w

$w$

Glen_b -Reinstate Monica

Oui, je voulais dire que

est l'

. Pourriez-vous donner un exemple où ma conclusion est fausse? Le

est le

x *

$x*$

a r g m i n

$argmin$

f

$f$

[s o m e t h i n g]

$[something]$

Q

$Q$ matrice que j'essaie de former. Si j'étends

j'obtiens

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

$w'(X'Xw - X'Y)$

. La première partie représenterait la forme de la

matrice, mais je ne peux pas se débarrasser du second terme

w^{'} X^{'} X w - w^{'} X^{'} Y

$w'X'Xw - w'X'Y$

Q

$Q$

- w^{'} X^{'} Y

$-w'X'Y$

spurra

@ AD.Net Les contraintes sont principalement couvertes dans l'autre réponse.

Glen_b -Reinstate Monica

Je voulais ajouter comment résoudre la transformation des contraintes dans une forme utilisable pour la programmation quadratique, car ce n'est pas aussi simple que je le pensais. Il n'est pas possible de trouver une matrice réelletelle que . $\sum |w_i| \le s$ $A$ $Aw \le s \leftrightarrow \sum |w_i| \le s$

L'approche que j'ai utilisée était de diviser les éléments du vecteur en et , de sorte que . Si , vous avez et $w_i$ $w$ $w_i^+$ $w_i^-$ $w_i = w_i^+ - w_i^-$ $w_i \ge 0$ $w_i^+ = w_i$ , sinon vous avezet $w_i^- = 0$ $w_i^- = |w_i|$ $w_i^+ = 0$ . Ou en termes plus mathématiques, $w_i^+ = \frac{|w_i| + w_i}{2}$ et Les deux et sontnombres non négatifs. L'idée derrière la répartition des nombres est que vous avez maintenant , éliminant efficacement les valeurs absolues. $w_i^- = \frac{|w_i| - w_i}{2}.$ $w_i^-$ $w_i^+$ $|w_i| = w_i^+ + w_i^-$

La fonction d'optimisation se transforme en: , sous réserve de $\frac{1}{2}(w^+ - w^-)^TQ(w^+ - w^-) + c^T(w^+ - w^-)$ $w_i^+ + w_i^- \le s, \\ w_i^+,w_i^- \ge 0$

Où et sont donnés comme indiqué ci-dessus par Glen_b $Q$ $c$

Cela doit être transformé en une forme utilisable, c'est-à-dire que nous avons besoin d'un vecteur. Cela se fait de la manière suivante:

$\frac{1}{2} \bigg[ \begin{array}{c} w^+ \\ w^- \end{array} \bigg]^T \bigg[ \begin{array}{cc} Q & -Q \\ -Q & Q \end{array} \bigg] \bigg[ \begin{array}{c} w^+ \\ w^- \end{array}\bigg] + \big[ \begin{array}{cc} c^T & -c^T \end{array} \big] \bigg[ \begin{array}{c} w^+ \\ w^- \end{array}\bigg]$

sujet à

$\bigg[ \begin{array}{cc} I_D & I_D \\ -I_{2D} \end{array} \bigg]\bigg[ \begin{array}{c} w^+ \\ w^- \end{array}\bigg] \le \bigg[ \begin{array}{c} s_D \\ 0_{2D} \end{array}\bigg]$

Où est le matrice unité de dimension, a de dimension vecteur constitué uniquement de la valeur et a de dimension de vecteur nul. Le premier semestre assure , le second et $I_D$ $D$ $s_D$ $D$ $s$ $0_D$ $2*D$ $|w_i| = w_i^+ + w_i^- \le s$ Maintenant, il est sous une forme utilisable d'utiliser la programmation quadratique pour rechercher $w_i^+,w_i^- \ge 0$ $w^+$ $w^-$ , étant donné l' . Une fois cela fait, votre paramètre optimal par rapport à est . $s$ $s$ $w = w^+ - w^-$

Source et lectures complémentaires: Résolution d'un problème de programmation quadratique avec des contraintes linéaires contenant des valeurs absolues

spurra
la source

2 D

$2D$

(w^{+}, w^{-})

$(w^+, w^-)$

w^{+}

$w^+$

w^{-}

$w^-$

w

$w$

0

$0$

La matrice et le vecteur dans l'expression finale peuvent être plus simples et en fait plus corrects. Au lieu de [Id Id] [w + w−] '≤ Sd, vous pouvez simplement mettre [1 1 .... 1] [w + w-]' ≤ s. C'est littéralement équivalent à ∑ | wi | = ∑ (wi + + wi−) ≤ s.

Marko