Optymalizacja maszyny wektora pomocniczego za pomocą programowania kwadratowego

Próbuję zrozumieć proces szkolenia maszyny wektora liniowego wsparcia . Zdaję sobie sprawę, że właściwości SMV pozwalają na ich optymalizację znacznie szybciej niż za pomocą kwadratowego solvera programistycznego, ale do celów edukacyjnych chciałbym zobaczyć, jak to działa.

Dane treningowe

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

Znalezienie hiperpłaszczyzny maksymalnego marginesu

Zgodnie z tym artykułem Wikipedii na temat maszyn SVM , aby znaleźć hiperpłaszczyznę maksymalnego marginesu, którą muszę rozwiązać

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

$\arg\min_{(\mathbf{w},b)}\frac{1}{2}\|\mathbf{w}\|^2$ zastrzeżeniem (dla dowolnego i = 1, ..., n)

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

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

Jak „podłączyć” moje przykładowe dane do solvera QP w R (na przykład quadprog ), aby ustalić ? $\mathbf{w}$

r svm optimization Ben
źródło

Musisz rozwiązać podwójny problem

@fcop możesz rozwinąć? Jaki jest dual w tym przypadku? Jak rozwiązać za pomocą R? itp.

Ben

Odpowiedzi:

WSKAZÓWKA :

Quadprog rozwiązuje następujące problemy:

\begin{aligned} min_{x} {re}^{T.} x + 1 / 2) x^{T.} re x \\ takie, że {ZA}^{T.} x \geq x_{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*}$

Zastanów się

x = (\begin{matrix} w \\ b \end{matrix}) i re = (\begin{matrix} ja & 0 \\ 0 & 0 \end{matrix})

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

gdzie matrycą tożsamości. $I$

Jeśli jest a jest : $w$ $p \times 1$ $y$ $n \times 1$

\begin{aligned} x & : (2) p + 1) \times 1 \\ re & : (2) p + 1) \times (2) p + 1) \end{aligned}

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

W podobnych wierszach:

x_{0} = {(\begin{matrix} 1 \\ 1 \end{matrix})}_{n \times 1}

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

Sformułuj korzystając z powyższych wskazówek, aby przedstawić swoje ograniczenie nierówności. $A$

prawoskrętny
źródło

Zgubiłem się. co to jest ?

d^{T}

$d^T$

Ben

Co to jest współczynnik w funkcji celu? Nie ale ?

w

$w$

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

$||w||^2_2$

w

$w$

przesunięty w prawo

Doceń pomoc. Myślałem, że to rozgryzłem, ale kiedy ustawię D = macierz, którą sugerujesz, quadprogzwraca błąd: „macierz D w funkcji kwadratowej nie jest pozytywnie określona!”

Ben

HACK: Perturb , dodając małą wartość powiedz na przekątnej

D

$D$

1 e - 6

$1e-6$

prawy przekrzywiony

Podążając za wskazówkami po prawej stronie ...

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
źródło