Étant donné les points de données et les étiquettes , le problème principal de la marge absolue SVM esty 1 , … , y n ∈ { - 1 , 1 }
s.t.
qui est un programme quadratique avec variables à optimiser pour et contraintes. Le doublei
S.T.
est un programme quadratique avec variables à optimiser pour et inégalité et égalité de contrainte.n n
Lors de la mise en œuvre d'une SVM à marge dure, pourquoi devrais-je résoudre le problème dual au lieu du problème primal? Le problème primordial me semble plus «intuitif», et je n'ai pas besoin de me préoccuper de l'écart de dualité, de la condition de Kuhn-Tucker, etc.
Il serait logique pour moi de résoudre le double problème si , mais je soupçonne qu'il existe de meilleures raisons. Est-ce le cas?
Réponses:
D'après les notes de cours référencées dans la réponse de @ user765195 (merci!), Les raisons les plus évidentes semblent être les suivantes:
En résolvant le problème primal, nous obtenons le optimal , mais nous ne savons rien sur le . Afin de classer un point de requête nous devons calculer explicitement le produit scalaire , qui peut être coûteux si est grand.α i x w T x dw αi x wTx d
En résolvant le problème dual, nous obtenons le (où pour tous les points sauf quelques points - les vecteurs de support). Afin de classer un point de requête , nous calculonsα i = 0 xαi αi=0 x
Ce terme est calculé très efficacement s'il n'y a que peu de vecteurs de support. De plus, étant donné que nous avons maintenant un produit scalaire impliquant uniquement des vecteurs de données , nous pouvons appliquer l’astuce du noyau .
la source
<x1, x>
etwTx
. Le premier est utilisé comme symbole pour une évaluation du noyau K (x1, x), qui projette x1 et x dans un espace de très haute dimension et calcule implicitement le produit scalaire des valeurs projetées. Ce dernier est le produit scalaire normal,w
etx
doit donc être projeté explicitement, puis le produit scalaire est calculé explicitement. Selon le choix du noyau, un seul calcul explicite peut nécessiter beaucoup plus de calculs que de nombreuses évaluations du noyau.Lisez le deuxième paragraphe de la page 13 et la discussion qui suit dans les notes suivantes:
http://cs229.stanford.edu/notes/cs229-notes3.pdf
la source
Voici une des raisons pour lesquelles la double formulation est attrayante du point de vue de l'optimisation numérique. Vous pouvez trouver les détails dans l' article suivant :
Hsieh, C.-J., Chang, K.-W., Lin, C.-J., Keerthi, SS et Sundararajan, S., «Méthode de descente à deux coordonnées pour une SVM linéaire à grande échelle», Actes du 25ème conférence internationale sur l'apprentissage automatique, Helsinki, 2008.
La double formulation implique une seule contrainte d'égalité affine et n contraintes liées.
1. La contrainte d'égalité affine peut être "éliminée" de la formulation double.
Cela peut être fait simplement en regardant vos données dans R ^ (d + 1) via l’incorporation de R ^ d dans R ^ (d + 1), résiliant l’ajout d’une seule coordonnée "1" à chaque point de données, c.-à-d. R ^ d ----> R ^ (d + 1): (a1, ..., ad) | ---> (a1, ..., ad, 1).
Cela permet de reformuler le problème de séparabilité linéaire dans R ^ (d + 1) et d’éliminer le terme constant w0 de votre classifieur, ce qui élimine à son tour la contrainte d’égalité affine du dual.
2. Au point 1, le dual peut facilement être transformé en un problème d'optimisation quadratique convexe dont les contraintes ne sont que des contraintes liées.
3. Le problème dual peut maintenant être résolu efficacement, c'est-à-dire via un algorithme de descente à deux coordonnées qui donne une solution epsilon-optimale en O (log (1 / epsilon)).
Ceci est fait en notant que la fixation de tous les alphas sauf un donne une solution de forme fermée. Vous pouvez ensuite parcourir tous les alphas un par un (par exemple, en choisir un au hasard, en fixant tous les autres alphas, en calculant la solution de formulaire fermé). On peut montrer que vous obtiendrez ainsi une solution quasi optimale "assez rapidement" (voir le théorème 1 dans l'article susmentionné).
Le double problème est attrayant du point de vue de l'optimisation pour de nombreuses autres raisons, certaines exploitant le fait qu'il n'a qu'une seule contrainte d'égalité affine (les contraintes restantes sont toutes des contraintes liées), tandis que d'autres exploitent l'observation qui se pose lors de la solution. du problème double "souvent, la plupart des alphas" sont égaux à zéro (des alphas non nuls correspondant aux vecteurs de support).
Vous pouvez obtenir un bon aperçu des considérations relatives à l'optimisation numérique des SVM à partir de la présentation de Stephen Wright à l'atelier d'apprentissage par ordinateur (2009).
PS: Je suis nouveau ici. Toutes mes excuses pour ne pas être bon à utiliser la notation mathématique sur ce site.
la source
À mon avis, dans les notes de conférence de Andrew ng, il a été clairement mentionné que le problème fondamental de 1 / || w || est un problème non convexe. Le dual est un problème convexe et il est toujours facile de trouver l’optimum d’une fonction convexe.
la source