Comment appliquer la méthode des moindres carrés itérativement repondérés (IRLS) au modèle LASSO?

J'ai programmé une régression logistique en utilisant l' algorithme IRLS . Je souhaite appliquer une pénalisation LASSO afin de sélectionner automatiquement les bonnes fonctionnalités. À chaque itération, le problème suivant est résolu:

$$\mathbf{\left(X^TWX\right) \delta\hat\beta=X^T\left(y-p\right)}$$

Soit un nombre réel non négatif. Je ne pénalise pas l'interception comme suggéré dans The Elements of. Apprentissage statistique . Idem pour les coefficients déjà nuls. Sinon, je soustrais un terme du côté droit:$\lambda$

$$\mathbf{X^T\left(y-p\right)-\lambda\times \mathrm{sign}\left(\hat\beta\right)}$$

Cependant, je ne suis pas sûr de la modification de l'algorithme IRLS. Est-ce la bonne façon de procéder?

---

Edit: Bien que je n'étais pas confiant à ce sujet, voici une des solutions que j'ai finalement trouvé. Ce qui est intéressant, c'est que cette solution correspond à ce que je comprends maintenant de LASSO. Il y a en effet deux étapes à chaque itération au lieu d'une seule:

• la première étape est la même que précédemment: on fait une itération de l'algorithme (comme si dans la formule du gradient ci-dessus),$\lambda=0$
• la deuxième étape est la nouvelle: on applique un seuillage progressif à chaque composante (à l'exception de la composante , qui correspond à l'ordonnée à l'origine) du vecteur obtenu à la première étape. C'est ce qu'on appelle l' algorithme itératif de seuil doux .$\beta_0$$\beta$

$$\forall i \geq 1, \beta_{i}\leftarrow\mathrm{sign}\left(\beta_{i}\right)\times\max\left(0,\,\left|\beta_{i}\right|-\lambda\right)$$

Ce problème est généralement résolu par ajustement par descente de coordonnées ( voir ici ). Cette méthode est à la fois plus sûre, plus efficace numériquement, algorithmiquement plus facile à mettre en œuvre et applicable à un tableau plus général de modèles (y compris également la régression de Cox). Une implémentation R est disponible dans le package R glmnet . Les codes sont open source (en partie en et en C, en partie en R), vous pouvez donc les utiliser comme modèles.

La fonction de perte LASSO a une discontinuité à zéro le long de chaque axe, donc IRLS va avoir des problèmes avec elle. J'ai trouvé une approche de type optimisation minimale séquentielle (SMO) très efficace, voir par exemple

http://bioinformatics.oxfordjournals.org/content/19/17/2246

une version avec le logiciel MATLAB est

http://bioinformatics.oxfordjournals.org/content/22/19/2348

le logiciel est disponible ici:

http://theoval.cmp.uea.ac.uk/~gcc/cbl/blogreg/

L'idée de base est d'optimiser les coefficients un par un et de tester pour voir si vous traversez la discontinuité un coefficient à la fois, ce qui est facile car vous effectuez une optimisation scalaire. Cela peut sembler lent, mais il est en fait assez efficace (même si je m'attends à ce que de meilleurs algorithmes aient été développés depuis - probablement par Keerthi ou Chih-Jen Lin qui sont tous deux des experts de premier plan dans ce genre de choses).

Vous pouvez consulter l'article: Régression logistique régularisée L1 efficace, qui est un algorithme basé sur IRLS pour LASSO. Concernant l'implémentation, le lien peut vous être utile (http://ai.stanford.edu/~silee/softwares/irlslars.htm).

L'IRL pour le problème LASSO est le suivant:

$$\arg \min_{x} \frac{1}{2} \left\| A x - b \right\|_{2}^{2} + \lambda \left\| x \right\|_{1} = \arg \min_{x} \frac{1}{2} \left\| A x - b \right\|_{2}^{2} + \lambda {x}^{T} W {x}$$

Où est une matrice diagonale - . Cela vient de .$W$‖X‖1=∑i| xi| =∑ix 2 ${W}_{i, i} = \frac{1}{ \left| {x}_{i} \right| }$
$\left\| x \right\|_{1} = \sum_{i} \left| {x}_{i} \right| = \sum_{i} \frac{ {x}_{i}^{2} } { \left| {x}_{i} \right| }$

Maintenant, ce qui précède est juste la régularisation de Tikhonov .
Pourtant, puisque dépend de il faut le résoudre de manière itérative (cela annule également le facteur 2 de la régularisation de Tikhonov , car la dérivée de par rapport à tout en maintenant comme constante est qui est égal à ):x x T W x x x diag ( signe ( x ) ) W $W$$x$${x}^{T} W x$$x$$x$$\operatorname{diag} \left( \operatorname{sign} \left( x \right) \right)$$W x$

$${x}^{k + 1} = \left( {A}^{T} A + \lambda {W}^{k} \right)^{-1} {A}^{T} b$$

Où .${W}_{i, i}^{K} = \frac{1}{ \left| {x}^{k}_{i} \right| }$

L' initialisation peut être par .$W = I$

Faites attention, cela ne fonctionne pas bien pour les grandes valeurs de et vous feriez mieux d'utiliser ADMM ou Coordinate Descent.$\lambda$