如何用Matlab的quadprog实现软间隔SVM模型?

pprl5pva  于 2023-01-26  发布在  Matlab
关注(0)|答案(4)|浏览(234)

假设给定训练数据集{yᵢ, xᵢ},对于i = 1, ..., n,其中yᵢ可以是-11,并且xᵢ可以是例如2D或3D点。
通常,当输入点是“线性可分的”时,SVM模型可定义如下

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

受约束(对于i = 1, ..., n

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

这通常被称为hard-marginSVM模型,因此它是constrained minimization problem,其中未知数是wb,我们也可以在要最小化的函数中省略1/2,因为它只是一个常数。
现在,关于Matlab的quadprogdocumentation状态
x = quadprog(H, f, A, b)A*x ≤ b的约束下最小化1/2*x'*H*x + f'*xA是双精度矩阵,b是双精度向量。
我们可以使用quadprog函数来实现硬间隔SVM模型,以获得权重向量w,如下

  • H变为单位矩阵。
  • f'变为零矩阵。
  • A是约束的左侧
  • b等于-1,因为原始约束具有>= 1,当我们在两侧乘以-1时,它变为<= -1

现在,我尝试实现一个软余量SVM模型。

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

受约束(对于i = 1, ..., n

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

使得ζᵢ >= 0(其中是求和符号)、ζᵢ = max(0, 1 - yᵢ*(w*xᵢ - b))Chyper-parameter
如何使用Matlab的quadprog函数解决这个优化问题?我不清楚如何将方程Map到quadprog函数的参数。
软余量SVM模型的“primal”形式(即上面的定义)可以转换为“dual”形式。我这样做了,并且我能够得到拉格朗日变量值(以对偶形式)。但是,我想知道我是否可以使用quadprog直接求解原始形式,而不需要将其转换为对偶形式。

6l7fqoea

6l7fqoea1#

我看不出这有什么问题,让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);

我可能会在一些小细节上犯错误,但总体思路是正确的。

atmip9wb

atmip9wb2#

我想澄清@vharavy answer,因为你可能会在尝试推导他代码中"n"的含义时迷失方向。以下是我根据他的答案和SVM维基百科文章所做的版本。我假设我们有一个名为 "test.dat" 的文件,该文件保存了上一列中测试点的坐标及其类成员身份。包含3D点的 "test.dat" 的示例内容:

-3,-3,-2,-1
-1,3,2,1
5,4,1,1
1,1,1,1
-2,5,4,1
6,0,1,1
-5,-5,-3,-1
0,-6,1,-1
-7,-2,-2,-1

下面是代码:

data = readtable("test.dat");
tableSize = size(data);
numOfPoints = tableSize(1);
dimension = tableSize(2) - 1;
PointsCoords = data(:, 1:dimension);
PointsSide = data.(dimension+1);

C = 0.5; %can be changed
n = dimension;
m = numOfPoints; %can be also interpretet as number of constraints
%z = [w, eps, b]; number of variables in 'z' is equal to n + m + 1
H = diag([ones(1, n), zeros(1, m + 1)]);
f = [zeros(1, n), C * ones(1, m), 0];
Aineq = [-diag(PointsSide)*table2array(PointsCoords), -eye(m), PointsSide];
bineq = -ones(m, 1);
lb = [-inf(1, n), zeros(1, m), -inf];
z = quadprog(H, f, Aineq, bineq, [], [], lb);
vq8itlhq

vq8itlhq3#

若设z =(w;w 0; 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的2个部分中,第一部分用于w 0,第二部分用于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)]

现在,x1月1x

omhiaaxx

omhiaaxx4#

完整的代码.思想和上面一样.

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

相关问题