Optimización de una máquina de vectores de soporte con programación cuadrática

Estoy tratando de entender el proceso para entrenar una máquina de vectores de soporte lineal . Me doy cuenta de que las propiedades de los SMV permiten que se optimicen mucho más rápido que mediante el uso de un solucionador de programación cuadrática, pero con fines de aprendizaje, me gustaría ver cómo funciona esto.

Datos de entrenamiento

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

Encontrar el hiperplano de margen máximo

De acuerdo con este artículo de Wikipedia sobre SVM , para encontrar el hiperplano de margen máximo que necesito resolver

\arg min_{(w, b)} \frac{1}{2} ‖ w ‖^{2}

$\arg\min_{(\mathbf{w},b)}\frac{1}{2}\|\mathbf{w}\|^2$ sujeto a (para cualquier i = 1, ..., n)

y_{i} (w \cdot x_{i} - b) \geq 1.

$y_i(\mathbf{w}\cdot\mathbf{x_i} - b) \ge 1.$

¿Cómo 'conecto' mis datos de muestra a un solucionador de QP en R (por ejemplo, quadprog ) para determinar ? $\mathbf{w}$

r svm optimization Ben
fuente

Tienes que resolver el problema dual

@fcop puedes elaborar? ¿Cuál es el dual en este caso? ¿Cómo lo resuelvo usando R? etc.

Ben

Respuestas:

SUGERENCIA :

Quadprog resuelve lo siguiente:

\begin{aligned} min_{X} {re}^{T} X + 1 / / 2 X^{T} re X \\ tal que {UNA}^{T} X \geq X_{0 0} \end{aligned}

$\begin{align*} \min_x d^T x + 1/2 x^T D x\\ \text{such that }A^T x \geq x_0 \end{align*}$

Considere

X = (\begin{matrix} w \\ si \end{matrix}) y re = (\begin{matrix} yo & 0 0 \\ 0 0 & 0 0 \end{matrix})

$x = \begin{pmatrix} w\\ b \end{pmatrix} \text{and } D=\begin{pmatrix} I & 0\\ 0 & 0 \end{pmatrix}$

donde es la matriz de identidad. $I$

Si es e es : $w$ $p \times 1$ $y$ $n \times 1$

\begin{aligned} X & : (2 pag + 1) \times 1 \\ re & : (2 pag + 1) \times (2 pag + 1) \end{aligned}

$\begin{align*} x &: (2p+1) \times 1 \\ D &: (2p+1) \times (2p+1) \end{align*}$

En líneas similares:

X_{0 0} = {(\begin{matrix} 1 \\ 1 \end{matrix})}_{norte \times 1}

$x_0 = \begin{pmatrix} 1\\ 1 \end{pmatrix}_{n \times 1}$

Formule usando las sugerencias anteriores para representar su restricción de desigualdad. $A$

derechos
fuente

Estoy perdido. ¿Qué es ?

d^{T}

$d^T$

Ben

¿Cuál es el coeficiente de en su función objetivo? No pero ?

w

$w$

| | w | |_{2}^{2}

$||w||^2_2$

w

$w$

Rightskewed el

Agradezco la ayuda. Yo pensaba que me di cuenta de esto, pero cuando me puse D = la matriz que sugiero quadprogdevuelve el error "matriz D en función cuadrática no es definida positiva!"

Ben

HACK: Perturb agregando un pequeño valor, digamos en la diagonal

D

$D$

1 e - 6

$1e-6$

derechos de autor

Siguiendo los consejos 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)))

Ben
fuente