Otimizando uma máquina de vetores de suporte com programação quadrática

12

Estou tentando entender o processo de treinamento de uma máquina de vetores de suporte linear . Percebo que as propriedades dos SMVs permitem que elas sejam otimizadas muito mais rapidamente do que usando um solucionador de programação quadrática, mas, para fins de aprendizado, gostaria de ver como isso funciona.

Dados de treinamento

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()

insira a descrição da imagem aqui

Localizando o hiperplano de margem máxima

De acordo com este artigo da Wikipedia sobre SVMs , para encontrar o hiperplano de margem máxima que preciso resolver

argmin(w,b)12w2
sujeito a (para qualquer i = 1, ..., n)
yi(wxib)1.

Como conecto meus dados de amostra a um solucionador de QP no R (por exemplo, quadprog ) para determinar ?w

Ben
fonte
Você tem que resolver o problema duplo
2
@fcop você pode elaborar? Qual é o dual neste caso? Como faço para resolver usando R? etc.
Ben

Respostas:

6

DICA :

Quadprog resolve o seguinte:

minxdTx+1/2xTDxsuch that ATxx0

Considere

x=(wb)and D=(I000)

onde sou a matriz de identidade.I

Se for e for :wp×1yn×1

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

Em linhas semelhantes:

x0=(11)n×1

Formule usando as dicas acima para representar sua restrição de desigualdade.A

direitos
fonte
11
Estou perdido. o que é ? dT
Ben
11
Qual é o coeficiente de na sua função objetiva? Não mas ? w||w||22w
precisa saber é o seguinte
11
Agradecemos a ajuda. Eu pensei que tinha descoberto isso, mas quando defino D = a matriz que você sugere, quadprogretorna o erro "matriz D na função quadrática não é positiva definida!"
Ben
3
HACK: Perturb , adicionando um pequeno valor, digamos na diagonalD1e6
rightskewed
7

Seguindo as dicas 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)))

insira a descrição da imagem aqui

Ben
fonte