Optimisation d'une machine à vecteur de support avec programmation quadratique

12

J'essaie de comprendre le processus de formation d'une machine à vecteur de support linéaire . Je me rends compte que les propriétés des SMV leur permettent d'être optimisées beaucoup plus rapidement qu'en utilisant un solveur de programmation quadratique, mais à des fins d'apprentissage, j'aimerais voir comment cela fonctionne.

Données d'entraînement

set.seed(2015)
df <- data.frame(X1=c(rnorm(5), rnorm(5)+5), X2=c(rnorm(5), rnorm(5)+3), Y=c(rep(1,5), rep(-1, 5)))
df
           X1       X2  Y
1  -1.5454484  0.50127  1
2  -0.5283932 -0.80316  1
3  -1.0867588  0.63644  1
4  -0.0001115  1.14290  1
5   0.3889538  0.06119  1
6   5.5326313  3.68034 -1
7   3.1624283  2.71982 -1
8   5.6505985  3.18633 -1
9   4.3757546  1.78240 -1
10  5.8915550  1.66511 -1

library(ggplot2)
ggplot(df, aes(x=X1, y=X2, color=as.factor(Y)))+geom_point()

entrez la description de l'image ici

Trouver l'hyperplan de la marge maximale

Selon cet article Wikipedia sur les SVM , pour trouver l'hyperplan de marge maximale que je dois résoudre

argmin(w,b)12w2
sous réserve (pour tout i = 1, ..., n)
yi(wxib)1.

Comment «brancher» mes données d'exemple dans un solveur QP dans R (par exemple quadprog ) pour déterminer ?w

Ben
la source
Vous devez résoudre le double problème
2
@fcop pouvez-vous élaborer? Quel est le double dans ce cas? Comment résoudre l'utilisation R? etc.
Ben

Réponses:

6

CONSEIL :

Quadprog résout les problèmes suivants:

minxdTx+1/2xTDxsuch that ATxx0

Considérez

x=(wb)and D=(I000)

où est la matrice d'identité.I

Si est et est :wp×1yn×1

x:(2p+1)×1D:(2p+1)×(2p+1)

Sur des lignes similaires:

x0=(11)n×1

Formulez utilisant les conseils ci-dessus pour représenter votre contrainte d'inégalité.A

droits
la source
1
Je suis perdu. qu'est-ce que ? dT
Ben
1
Quel est le coefficient de dans votre fonction objectif? Pas mais ? w||w||22w
Rightskewed
1
Appréciez l'aide. Je pensais avoir compris cela, mais lorsque j'ai défini D = la matrice que vous suggérez quadprogrenvoie l'erreur "la matrice D en fonction quadratique n'est pas définie positive!"
Ben
3
HACK: Perturbez en ajoutant une petite valeur disons sur la diagonaleD1e6
Rightskewed
7

Suivre les conseils de rightskewed ...

library(quadprog)

# min(−dvec^T b + 1/2 b^T Dmat b) with the constraints Amat^T b >= bvec)
Dmat       <- matrix(rep(0, 3*3), nrow=3, ncol=3)
diag(Dmat) <- 1
Dmat[nrow(Dmat), ncol(Dmat)] <- .0000001
dvec       <- rep(0, 3)
Amat       <- as.matrix(df[, c("X1", "X2")])
Amat <- cbind(Amat, b=rep(-1, 10))
Amat <- Amat * df$Y
bvec       <- rep(1, 10)
solve.QP(Dmat,dvec,t(Amat),bvec=bvec)

plotMargin <- function(w = 1*c(-1, 1), b = 1){
  x1 = seq(-20, 20, by = .01)
  x2 = (-w[1]*x1 + b)/w[2]
  l1 = (-w[1]*x1 + b + 1)/w[2]
  l2 = (-w[1]*x1 + b - 1)/w[2]
  dt <- data.table(X1=x1, X2=x2, L1=l1, L2=l2)
  ggplot(dt)+geom_line(aes(x=X1, y=X2))+geom_line(aes(x=X1, y=L1), color="blue")+geom_line(aes(x=X1, y=L2), color="green")+
    geom_hline(yintercept=0, color="red")+geom_vline(xintercept=0, color="red")+xlim(-5, 5)+ylim(-5, 5)+
    labs(title=paste0("w=(", w[1], ",", w[2], "), b=", b))
}

plotMargin(w=c(-0.5065, -0.2525), b=-1.2886)+geom_point(data=df, aes(x=X1, y=X2, color=as.factor(Y)))

entrez la description de l'image ici

Ben
la source