假设给定训练数据集{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
这通常被称为hard-marginSVM模型,因此它是constrained minimization problem,其中未知数是w
和b
,我们也可以在要最小化的函数中省略1/2
,因为它只是一个常数。
现在,关于Matlab的quadprog
的documentation状态x = quadprog(H, f, A, b)
在A*x ≤ b
的约束下最小化1/2*x'*H*x + f'*x
。A
是双精度矩阵,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))
和C
是hyper-parameter。
如何使用Matlab的quadprog
函数解决这个优化问题?我不清楚如何将方程Map到quadprog
函数的参数。
软余量SVM模型的“primal”形式(即上面的定义)可以转换为“dual”形式。我这样做了,并且我能够得到拉格朗日变量值(以对偶形式)。但是,我想知道我是否可以使用quadprog
直接求解原始形式,而不需要将其转换为对偶形式。
4条答案
按热度按时间6l7fqoea1#
我看不出这有什么问题,让
z
作为(2n + 1)
变量的向量:然后,
H
变为对角线上的第一个n
值等于1
并且最后一个n + 1
被设置为零的对角矩阵:矢量
f
可表示为:第一组约束变为:
其中
A1
是与原始形式相同的矩阵。第二组约束变为下限:
然后你可以调用MATLAB:
我可能会在一些小细节上犯错误,但总体思路是正确的。
atmip9wb2#
我想澄清@vharavy answer,因为你可能会在尝试推导他代码中"n"的含义时迷失方向。以下是我根据他的答案和SVM维基百科文章所做的版本。我假设我们有一个名为 "test.dat" 的文件,该文件保存了上一列中测试点的坐标及其类成员身份。包含3D点的 "test.dat" 的示例内容:
下面是代码:
vq8itlhq3#
若设z =(w;w 0; eps)T是具有n+1+m个元素的长向量。(m是点的数目)那么,
不等式约束可指定为:
其中X是原始形式的n x m输入矩阵。在A的2个部分中,第一部分用于w 0,第二部分用于eps。
等式约束:
界限:
现在,x1月1x
omhiaaxx4#
完整的代码.思想和上面一样.