matlab - 如何使用 Matlab 的 quadprog 实现 soft-margin SVM 模型？

Question

假设我们有一个训练数据集 {yᵢ, xᵢ} , 对于 i = 1, ..., n , 其中yᵢ可以是 -1或 1和 xᵢ可以是例如2D 或 3D 点。

一般来说，当输入点线性可分时，SVM模型可以定义如下

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

受约束(for i = 1, ..., n)

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

这通常称为 hard-margin SVM model ，因此是一个 constrained minimization problem ，其中未知数为 w和 b .我们也可以省略 1/2在要最小化的函数中，假设它只是一个常数。

现在，documentation关于 Matlab 的 quadprog州

x = quadprog(H, f, A, b) minimizes 1/2*x'*H*x + f'*x subject to the restrictions A*x ≤ b. A is a matrix of doubles, and b is a vector of doubles.

我们可以使用 quadprog 实现 hard-margin SVM 模型函数，得到权重向量w ，如下

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

---

现在，我正在尝试实现 soft-margin SVM model .这里的最小化方程是

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

受约束(for i = 1, ..., n)

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

这样ζᵢ >= 0 , 其中∑是求和符号，ζᵢ = max(0, 1 - yᵢ*(w*xᵢ - b))和 C是 hyper-parameter .

如何使用 Matlab 的 quadprog 解决这个优化问题？功能？我不清楚方程式应该如何映射到 quadprog 的参数。功能。

soft-margin SVM 模型的“primal”形式(即上面的定义)可以转换为“dual”形式。我这样做了，并且能够获得拉格朗日变量值(对偶形式)。但是，我想知道我是否可以使用 quadprog直接求解原始形式，无需将其转换为对偶形式。

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

附言我可能在一些小细节上有误，但总体思路是正确的。