Untitled 1

一、问题设定：线性可分的二分类问题

给定训练集：

(x_{1}, y_{1}), (x_{2}, y_{2}), \dots, (x_{n}, y_{n}), x_{i} \in R^{d}, y_{i} \in {- 1, 1}

目标：找到一个超平面

w^{⊤} x + b = 0

将正负样本严格分开，并最大化到两类样本的间隔。

对任意一个样本 $(x_{i}, y_{i})$ ，几何间隔定义为：

γ_{i} = \frac{y _{i} ( w ^{⊤} x _{i} + b )}{∥ w ∥}

整个分类器的几何间隔为：

γ = i min γ_{i}

为了简化优化问题，我们固定几何间隔为 $1$ ，变成以下约束问题：

w, b min s.t. \frac{1}{2} ∥ w ∥^{2} y_{i} (w^{⊤} x_{i} + b) \geq 1, i = 1, \dots, n

这相当于最大化间隔的二次规划问题。

若数据线性不可分，引入松弛变量 $ξ_{i}$ ：

w, b, ξ min s.t. \frac{1}{2} ∥ w ∥^{2} + C i = 1 \sum n ξ_{i} y_{i} (w^{⊤} x_{i} + b) \geq 1 - ξ_{i}, ξ_{i} \geq 0

其中 $C > 0$ 控制间隔和误差的权衡。

原始问题是带不等式约束的凸优化问题。引入拉格朗日乘子 $α_{i}$ ，构造拉格朗日函数：

L (w, b, α) = \frac{1}{2} ∥ w ∥^{2} - i = 1 \sum n α_{i} [y_{i} (w^{⊤} x_{i} + b) - 1]

对 $w, b$ 求极小，对 $α$ 求极大，得到对偶问题：

α max s.t. i = 1 \sum n α_{i} - \frac{1}{2} i, j = 1 \sum n α_{i} α_{j} y_{i} y_{j} x_{i}^{⊤} x_{j} i = 1 \sum n α_{i} y_{i} = 0, 0 \leq α_{i} \leq C

求解后，可恢复：

w = i = 1 \sum n α_{i} y_{i} x_{i}

若数据非线性不可分，引入特征映射 $ϕ (x)$ 到高维空间，令：

K (x_{i}, x_{j}) = ϕ (x_{i})^{⊤} ϕ (x_{j})

然后直接在对偶问题中使用核函数 $K (x_{i}, x_{j})$ ：

常见核函数包括：

在对偶问题中，只有 $α_{i} > 0$ 的样本才参与最终模型，它们被称为支持向量。

最终分类器形式为：

f (x) = sign (i = 1 \sum n α_{i} y_{i} K (x_{i}, x) + b)

核函数对应某一映射 $ϕ$ 的充分条件是对应的 Gram 矩阵：

K_{ij} = K (x_{i}, x_{j})

为正定矩阵。