Comparaison de méthodes de régularisations

[invitea7369f8e]

Bonjour,

Dans le cadre d'un projet, je dois etudier les caractéristiques de différentes régularisations l1,l2 , lp ... et leurs caractéristiques (continuité, convexité ..) afin de les utiliser dans des problèmes d'optimisation (quadratique en particulier). Etant débutant sur le sujet c'est cette dernière partie qui me pose problème

Pouvez-vous m'éclairer sur la place des normes lp dans ces problèmes et comment choisir telle ou telle régularisation dans un problème d'optimisation ?
-----

[invitea7369f8e]

petit up !

[acx01b]

ta question est un peu générale, non ?

un problème d'optimisation quadratique :

avec et

f(x) est donc
l'ensemble des x qui respectent les contraintes est un ensemble convexe.

Pour la convexité de la fonction à minimiser : une fonction est convexe si pour tout vecteur y : est convexe par rapport à la variable réelle a.
On a donc que la somme de 2 fonctions convexes est convexe.
est convexe puisqu'elle ne traverse jamais ses tangentes et est convexe si seulement Q est semi défini positive (à toi de le montrer).
Donc est convexe ssi est semi défini positive.

Ensuite la régularisation :
tu remplaces f(x) par
avec p=2 et k=2 ça reste convexe et g(x) est toujours ,
avec p=1 ...
avec p=infini ...

[acx01b]

ha oui et la régularisation la plus simple à étudier (du type norme L2) mais qui reste assez générale :


Où est semi défini positive et de préférence est défini positive.
Dans ce cas ça se réduit à un problème linéaire.

[A voir en vidéo sur Futura]

[GrisBleu]

Salut

dans un modèle linéaire (qui amène des optimisations quadratiques) ou à kernel (ce qui est plus ou moins la même chose)
+ Une régularisation L1 permet de réduire le nombre de coefficients non nuls mais n'est pas simple à résoudre (idem pour une régularisation L0)
+ Une régularisation L2 permet de lisser les coefficients et a des solutions exactes
Cdlt

[acx01b]

Oui, je suis d'accord.

Avec les normes L1 et L0 on a la notion de "sparsity" : on veut un résultat avec beaucoup de nuls.

Par contre si tous les la régularisation L1 ne pose plus de problème de convexité/continuité. C'est utilisé par exemple pour NMF où on fait une série de "alternated least square" en général avec régularisation L1 plutôt que L2.

[invitea7369f8e]

Bonjour,
Merci pour vos réponses !

acx01b , merci pour l'explication sur le problème d'optimisation quadratique, par contre je ne comprends pas comment tu en viens à remplacer f(x), par g(x) ?
avec ton deuxième message, je vois un peu mieux comment choisir les normes (par exemple L1 à la place de L0 si il n'y a pas de coefficient nul),
Mais dans son message GrisBleu dit qu'il est plus simple d'utiliser la régularisation L2 (car elle donne des résultats exact).

Ma question est de savoir quelle norme utiliser en fonction du problème ? (j'ai représenté les boules unité des normes sous scilab mais je ne suis pas sur que cela m'aide beaucoup)

[GrisBleu]

Bonjour

Je ne connaissais pas les NMF
Pour L2, ce que je voulais dire, c'est qu'une solution exacte est calculable
Pour L1, en général, tu dois utiliser des approximations et des descente de gradient (et donc être potentiellement bloqué dans un minimum local). Voir ici par exemple http://cseweb.ucsd.edu/~saul/teachin...s07/L1norm.pdf
++
Cdlt

[acx01b]

je résume ce que comprends de la question :

• à première vue le but de la régularisation : imposer une solution unique à un problème mal formulé qui a une infinité de solutions
• quand on régularise on change la fonction à minimiser, c'est un peu comme si on donnait un a priori sur quels x nous plaisent plus que d'autres : pour être rigoureux sur cette histoire d'a priori en général on part sur une formulation probabiliste/statistique
• la régularisation L2 veut une norme L2 de x pas trop grande, ça s'interprète bien comme une histoire d'énergie ou même de filtrage. en supposant les données suivant une loi gaussienne (données bruitées) on tombe sur le problème d'optimisation quadratique régularisé L2.
• un problème quadratique régularisé L2 reste un problème quadratique : on a donc un moyen facile de trouver la solution (minimum local de g(x) puis simplexe si pas de minimum local)
• la régularisation L1 ou L0 (ou même L3/2) est un autre type de régularisation. l'apriori qu'on a sur x est qu'il est sparse (contient beaucoup de valeurs nulles ou presque nulles)
• la régularisation L1 est pratique quand on a la contrainte x_i >= 0, dans ce cas ça reste un problème quadratique
• sinon la régularisation L1 introduit des problèmes de calculs : minimum locaux / fonction non convexe / non dérivable.
• le "kernel trick" s'applique aux problèmes quadratiques, mais pas trop aux autres (il faut que x soit dans le sous espace engendré par les données pour appliquer le kernel trick)

à toi de faire tes recherches maintenant !

commence par ça :
http://fr.wikipedia.org/wiki/R%C3%A9...tion_Tychonoff
puis tout ce qu'on a dit

après je pense qu'il faut se concentrer sur un problème précis/concret pour que ça devienne plus intéressant.