Как решить формуляр SVM Soft Margin Primal в MATLAB quadprog

Question

Я пытаюсь решить формулу SVM Primal в MATLAB, используя функцию Quadprog. Когда два класса линейно разделимы, то СВМ Минимизация Задача, чтобы получить весовой вектор W становится 1/2 (|| W || 2)

при условии ограничения уг (wxi-B)> = 1

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

функция MATLAB quadprog решает следующее уравнение

х = quadprog (H, F, A, B) сводит к минимуму 1/2 * х '* H * х + е' * х при условии соблюдения ограничения A * x ≤ b. А - матрица двойников, а Ь - вектор двойников.

Таким образом, первичная форма легко может быть отображена на функцию квадропрога, чтобы легко получить весовой вектор w. H становится единичной матрицей. f 'становится матрицей нулей. A - левая сторона ограничения от более раннего b равна -1, поскольку исходное ограничение имеет> = 1, оно становится < = -1, когда мы умножаем с -1 с обеих сторон.

Когда я это делаю, весовой вектор получается отлично.

Теперь я пытаюсь решить дело SVM Soft Margin здесь

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

Уравнение Минимизация здесь является

мин ((1/2) || ж || 2 + с (суммирование эпсилон (я)) ж, б

при условии ограничения уг (wxi-б)> = 1 - eplison (я)> = 0.

Как решить эту проблему оптимизации с помощью функции Quadprog MATLAB. Неясно, как уравнение должно быть сопоставлено с параметрами функции quadprog. Я растрепал голову о том, как без везения.

Его давно не изучали СВМ, но из-за неопределенной памяти я помню, что Изначальная форма в мягкой маржи - проблема NP, поэтому мы ее конвертируем в двойное представление Вулфа, чтобы решить ее, но я не уверен.

Я преобразовал его в двойную форму и могу получить значения переменных Лагранжа в двойной форме, однако я хочу подтвердить, что первичная форма не может быть решена сама по себе.

Кто-нибудь знает, как это можно решить, используя функцию matlab quadprog? Или, если это проблема NP?

Answer 1

Я не вижу, как это может быть проблемой.Пусть z нашим вектор (2n + 1) переменных:

z = (w, eps, b) 

Тогда H становится диагональная матрица с первыми n значениями по диагонали, равных 1 и последний n + 1 набор к нулю:

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

Вектор f может выражаться следующим образом:

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

Первый набор становится ограничения:

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

, где A1 является той же матрицей, как и в первичной форме.

Второй набор ограничений становится нижние границы:

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

Тогда вы можете назвать MATLAB:

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

P.S. Я могу ошибаться в некоторых мелких деталях, но общая идея правильная.

Answer 2

Если пусть г = (ш; w0; ЭПС). Т быть длинный вектор с п + 1 + т элементов (м число точек) Затем

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

Неравенство ограничений может быть определен как:

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

, где Х представляет собой входной матрицы пХт в первичной form.Out из 2-х частей для а, первая часть для w 0, а вторая часть для ЭПС.

b = ones(m,1) 

Ограничения равенства:

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

Bounds:

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

Теперь z=quadprog(H,f,A,b,Aeq,beq,lb,ub)

Answer 3

Полный код. Идея такая же, как и выше.

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,:);