SVM

2018-08-16 本文已影响9人水之心

SVM

Input: 设有数据集 $\mathcal{D} = \{x_i,y_i \}_{i=1}^m$ , 令 $X = [x_1^T; \cdots; x_m^T], y = [y_1; \cdots; y_m]$ , 其中 $y_i\in \{1,-1\}$

可以将数据集 $\mathcal{D}$ 看作线性空间中的点. 数据集 $\mathcal{D}$ 中的点 $x_i$ 到超平面 $y = x^Tw + b$ 的距离为
$\frac{|b + (x_j, w)|}{||w||}$

因而, 正负超平面的距离为
$d = \frac{2}{||w||}$

$d$ (被称为间隔, margin) 越大, 则各个样本对于自身类别的预测估计愈自信, 因而, 我们需要将 $d$ 最大化. 即
$\begin{cases} \displaystyle \max_{w,b} &\frac{2}{||w||}\\ s.t. &y_i(w^Tx_i + b) \geq 1, & i= 1,2,⋯,m \end{cases}$
等价于
$\begin{cases} \displaystyle \min_{w,b} &\frac{||w||^2}{2}\\ s.t.&y_i(w^Tx_i + b) \geq 1, & i= 1,2,⋯,m \end{cases}$

该问题可以通过拉格朗日乘子法求解:
引入拉格朗日乘子 $λ = \{λ_1,\cdots,λ_m\}, λ \succeq 0$ , 有
$L(w, b ,λ) = \frac{||w||^2}{2} + ∑_{i=1}^m λ_i(1-y_i(w^Tx_i+b))$

由 $\frac{∂L}{∂w}=0$ , $\frac{∂L}{∂b}=0$ 得
$\begin{cases} w = \sum_{i=1}^m λ_iy_ix_i = [x_1,\cdots,x_m][λ_1y_1;\cdots;λ_my_m] = X^T (λ \circ y)\\ 0 = \sum_{i=1}^m λ_iy_i = \vec{1}^T (λ \circ y) \end{cases}$

消去 $w,b$ , 得到 (7) 式的对偶问题

$\begin{cases} \displaystyle\max_{λ} & \vec{1}^Tλ - 0.5 (λ ∘ y)^T XX^T (λ ∘ y)\\ s.t. &\vec{1}^T (λ \circ y)=0, λ \succeq 0 \end{cases}$

为了更加高效解决 (9) 的问题, 人们提出了一种高效的算法: SMO. SMO 之所以高效, 恰由于在固定其他参数, 仅仅优化两个的参数的过程便将二次规划问题转换为具有闭式解的二次规划问题.

前面的讨论是建立在数据集是线性可分的情况下的, 对于线性不可分的情况, 我们可以引入核函数.

令 $φ(x)$ 表示将 $x$ 映射后的特征向量, 于是在特征空间中划分超平面所对应的模型可以表示为
$f(x) = w^T\phi(x) + b$
这样 (9) 便可转换为

$\begin{cases} \displaystyle\max_{λ} & \vec{1}^Tλ - 0.5 (λ ∘ y)^T \phi(X)\phi(X)^T (λ ∘ y)\\ s.t. &\vec{1}^T (λ \circ y)=0, λ \succeq 0 \end{cases}$

SVM

猜你喜欢

热点阅读