Как реализовать модель SVM с мягкой маржой, используя quadprog от Matlab?

Предположим, нам дан обучающий набор данных {yᵢ, xᵢ} для i = 1, ..., n, где yᵢ может быть либо -1, либо 1, а xᵢ может быть, например. 2D или 3D точка.

В общем случае, когда входные точки линейно отделимы, модель SVM можно определить следующим образом.

min 1/2*||w||²
w,b

с учетом ограничений (для i = 1, ..., n)

yᵢ*(w*xᵢ - b) >= 1

Ее часто называют моделью жесткая маржа SVM, что, таким образом, представляет собой задачу ограниченной минимизации, где неизвестными являются w и b. Мы также можем опустить 1/2 в минимизируемой функции, учитывая, что это просто константа.

Теперь документация о quadprog состояниях Matlab.

x = quadprog(H, f, A, b) минимизирует 1/2*x'*H*x + f'*x с учетом ограничений A*x ≤ b. A — матрица двойников, а b — вектор двойников.

Мы можем реализовать модель SVM с жесткими границами, используя функцию quadprog, чтобы получить вектор весов w следующим образом.

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

Теперь я пытаюсь реализовать модель SVM soft-margin. . Уравнение минимизации здесь

min (1/2)*||w||² + C*(∑ ζᵢ)
w,b

с учетом ограничений (для i = 1, ..., n)

yᵢ*(w*xᵢ - b) >= 1 - ζᵢ

так что ζᵢ >= 0, где ∑ — символ суммирования, ζᵢ = max(0, 1 - yᵢ*(w*xᵢ - b)) и C — это гиперпараметр.

Как можно решить эту проблему оптимизации с помощью функции quadprog Matlab? Мне непонятно, как уравнение должно быть сопоставлено с параметрами функции quadprog.

«primal» форма модели SVM с мягкой маржой (т. е. определение выше) может быть преобразована в «двойная. Я сделал это, и я могу получить значения переменных Лагранжа (в двойственной форме). Однако я хотел бы знать, могу ли я использовать quadprog для непосредственного решения первичной формы без необходимости преобразования ее в двойную форму.


machine-learning matlab svm quadprog
person user1067334    schedule 20.03.2013    source источник

Ответы (3)


arrow_upward
9
arrow_downward

Я не понимаю, как это может быть проблемой. Пусть 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. Могу ошибаться в каких-то мелких деталях, но общая мысль верная.

person vharavy    schedule 20.03.2013
comment
То, как была использована переменная n, смутило меня еще больше, но я уловил общую идею. Переменная n не совпадает во многих местах. Большое Вам спасибо. - person user1067334; 22.03.2013
comment
@ user1067334 Представляет ли n количество функций или количество обучающих выборок? - person tusharfloyd; 02.11.2015

arrow_upward
-1
arrow_downward

Если пусть z = (w; w0; eps)T — длинный вектор с n+1+m элементами (m — количество точек). Тогда

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)],

где X — входная матрица размера n x m в простой форме. Из двух частей для A первая часть предназначена для w0, а вторая — для eps.

b = ones(m,1)

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

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

Границы:

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)

person akuriako    schedule 31.03.2017

arrow_upward
-1
arrow_downward

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

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,:);
person ashwin kumar    schedule 31.10.2017
comment
Этот код не работает. Можете ли вы привести работающий пример? Например, вы должны указать X и т. д. - person nbro; 13.05.2018