Jak rozwiązać SVM Soft Margin Primal Form w MATLAB quadprog

Question

Próbuję rozwiązać SVM Primal Form w MATLAB przy użyciu funkcji Quadprog. Po dwóch klas liniowo rozdzielić, SVM minimalizacji problemu uzyskać wektor wag się 1/2 (|| W || 2)

przedmiotem yi Ograniczenie (wxi-b)> = 1

http://en.wikipedia.org/wiki/Support_vector_machine#Primal_form

funkcja Matlab quadprog rozwiązuje następujące równanie

x = quadprog (H, M, A, b) minimalizuje 1/2 * x '* h * x + f' * x z zastrzeżeniem ograniczenia A * x ≤ b. A jest macierzą podwójną, a b jest wektorem dubletów.

Tak więc, pierwotna forma może być łatwo zamapowana na funkcję quadprog, aby łatwo uzyskać wektor wagowy. H staje się matrycą tożsamości. f 'staje się matrycą zer. A to lewa strona ograniczenia z wcześniejszego b jest równa -1, ponieważ pierwotne ograniczenie miało> = 1, staje się < = -1, gdy pomnożymy przez -1 po obu stronach.

Kiedy to zrobię, wektor wagowy będzie świetny.

Teraz m próby rozwiązania sprawy SVM miękkie marginesu stąd

http://en.wikipedia.org/wiki/Support_vector_machine#Soft_margin

Równanie minimalizacji Oto

min ((1/2) w || || 2+ C (sumowanie epsilon (i)) w b

przy ograniczeniu yi (wxi-b)> = 1 - eplison (I)> = 0

W jaki sposób rozwiązać ten problem optymalizacji za pomocą funkcji quadprog MATLAB. Nie jest jasne, w jaki sposób równanie powinno być odwzorowane na parametry funkcji quadprog. Łapię sobie głowę, jak bez szczęścia.

Minęło sporo czasu, odkąd uczyłem się SVM, ale z mglistej pamięci, pamiętam, że Pierwotna Forma w Miękkim Marginesie jest problemem NP, dlatego przekształcamy go w Wolfe Dual Representation, aby go rozwiązać, ale jestem niepewny.

Przekształciłem go w podwójną formę i jestem w stanie uzyskać wartości zmiennych Lagrange'a w podwójnej formie, ale chcę potwierdzić, że pierwotna forma nie może być sama rozwiązana.

Czy ktoś wie, jak można go rozwiązać za pomocą funkcji quadprog Matlab? A może jest to problem NP?

Answer 1

Nie widzę, jak to może być problem.Niech z nasz wektor (2n + 1) zmiennych:

z = (w, eps, b) 

Następnie H staje się macierzą diagonalną z pierwszych n wartości na przekątnej równej 1 i ostatniej n + 1 ustawiony na zero:

H = diag([ones(1, n), zeros(1, n + 1)]) 

Vector f puszka być wyrażone jako:

f = [zeros(1, n), C * ones(1, n), 0]' 

pierwszy zestaw więzów postać:

Aineq = [A1, eye(n), zeros(n, 1)] 
bineq = ones(n, 1) 

gdzie A1 jest w tej samej matrycy, jak w pierwotnej postaci.

Drugi zestaw ograniczeń staje się niższe granice:

lb = (inf(n, 1), zeros(n, 1), inf(n, 1)) 

Następnie można wywołać MATLAB:

z = quadprog(H, f, Aineq, bineq, [], [], lb); 

PS: Mogę się pomylić z drobnymi szczegółami, ale ogólny pomysł jest właściwy.

Answer 2

przypadku niech z = (W; W0; EPS). T będzie długa wektor n + 1 + m elementów (m liczbę punktów) Następnie

H= diag([ones(1,n),zeros(1,m+1)]). 
f = [zeros(1; n + 1); ones(1;m)] 

Ograniczenia nierówności miały być określone jako:

A = -diag(y)[X; ones(m; 1); zeroes(m;m)] -[zeros(m,n+1),eye(m)], 

, gdzie X jest macierzą wejście nXM w pierwotnej form.Out z 2 części do pierwsza część jest W0 a druga część jest ePS.

b = ones(m,1) 

Ograniczenia równości:

Aeq = zeros(1,n+1 +m) 
beq = 0 

granic:

lb = [-inf*ones(n+1,1); zeros(m,1)] 
ub = [inf*ones(n+1+m,1)] 

Teraz z=quadprog(H,f,A,b,Aeq,beq,lb,ub)

Answer 3

kompletny kod. Pomysł jest taki sam jak powyżej.

n = size(X,1); 
m = size(X,2); 
H = diag([ones(1, m), zeros(1, n + 1)]); 
f = [zeros(1,m+1) c*ones(1,n)]'; 
p = diag(Y) * X; 
A = -[p Y eye(n)]; 
B = -ones(n,1); 
lb = [-inf * ones(m+1,1) ;zeros(n,1)]; 
z = quadprog(H,f,A,B,[],[],lb); 
w = z(1:m,:); 
b = z(m+1:m+1,:); 
eps = z(m+2:m+n+1,:);