支持向量机SVM

接上文：线性可分支持向量机与硬间隔最大化

线性支持向量机与软间隔最大化

线性SVM

        线性可分问题SVM学习方法，对线性不可分训练数据是不适用的，因为此时上文中的不等式约束并不能都成立。需要修改硬间隔最大化，使其成为软间隔最大化。
        假设给定一个特征空间上的的训练数据集
$T=\{(x_1, y_1),(x_2,y_2),...,(x_N,y_N)\}$T={(x1​,y1​),(x2​,y2​),...,(xN​,yN​)}
再假设训练数据集不是线性可分的。通常情况是，训练数据中有一些特异点（噪声点），将这些点除去后，剩下的大部分样本点组成的集合是线性可分的。
        线性不可分意味着某些样本点$(x_i,y_i)$(xi​,yi​)不能满足函数间隔大于等于1的约束条件，即上文中的式（14）。为了解决这个问题，可以对每个样本点$(x_i,y_i)$(xi​,yi​)引入一个松弛变量 $\xi \geq 0$ξ≥0，使得函数间隔加上松弛变量大于等于1。这样，约束条件变为：
$s.t. \;\;\;\; y_i(w·x_i+b) \geq 1-\xi_i$s.t.yi​(w⋅xi​+b)≥1−ξi​
同时，对每个松弛变量$\xi_i$ξi​，支付一个代价$\xi_i$ξi​。目标函数由原来的$\frac12||w||^2$21​∣∣w∣∣2变成
$\frac12||w||^2 + C\sum_{i=1}^N\xi_i \tag {1}$21​∣∣w∣∣2+Ci=1∑N​ξi​(1)
这里，$C>0$C>0称为惩罚参数，一般由应用问题决定。$C$C值大的时候对误分类的惩罚增大，$C$C值小的时候对误分类的惩罚减小。最小化目标函数（1）包含两层含义：

• 使 $\frac12||w||^2$21​∣∣w∣∣2尽量小即间隔尽量大
• 同时使误分类点的个数尽量小

C是调和二者的系数。

        线性不可分的SVM学习问题变成如下凸二次规划问题（原始问题）：
$\min_{w,b,\xi}\;\;\;\;\frac12||w||^2 + C\sum_{i=1}^N\xi_i \tag 2$w,b,ξmin​21​∣∣w∣∣2+Ci=1∑N​ξi​(2)
$s.t. \;\;\;\; y_i(w·x_i+b) \geq 1-\xi_i,\;\;\;i=1,2,...,N \tag{3}$s.t.yi​(w⋅xi​+b)≥1−ξi​,i=1,2,...,N(3)
$\;\;\;\;\;\;\;\; \xi_i \geq 0,\;\;\;i=1,2,...,N \tag{4}$ξi​≥0,i=1,2,...,N(4)
        如果求出来约束最优化问题（2）~（4）的解$w^*,b^*$w∗,b∗，就可以得到最大间隔分离超平面$w^*·x+b^*=0$w∗⋅x+b∗=0及分类决策函数$f(x)=sign(w^*·x+b^*)$f(x)=sign(w∗⋅x+b∗)，即训练样本线性不可分时的线性SVM。 显然，线性SVM是包含线性可分SVM的。

定义 线性SVM
        对于给定线性不可分训练数据集，通过求解凸二次规划问题，即软间隔最大化问题（2）~（4），得到的分离超平面为：
$w^*·x+b^*=0 \tag5$w∗⋅x+b∗=0(5)
以及相应的分类决策函数
$f(x)=sign(w^*·x+b^*) \tag6$f(x)=sign(w∗⋅x+b∗)(6)
称为线性SVM。

---

学习的对偶算法

        原始问题（2）~（4）的对偶问题是
$\min_{\alpha} \;\;\; \frac12\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i·x_j)-\sum_{i=1}^N\alpha_i\tag {7}$αmin​21​i=1∑N​j=1∑N​αi​αj​yi​yj​(xi​⋅xj​)−i=1∑N​αi​(7)
$s.t. \;\;\;\;\sum_{i=1}^N\alpha_iy_i=0 \tag{8}$s.t.i=1∑N​αi​yi​=0(8)
$0 \leq\alpha_i\leq C,\;\;\;i=1,2,...,N \tag{9}$0≤αi​≤C,i=1,2,...,N(9)
        通过求解对偶问题而得到原始问题的解，进而确定分离超平面和决策函数。

---

定理
        设$\alpha^*=(\alpha_1^*,\alpha_2^*,...,\alpha_N^*)^T$α∗=(α1∗​,α2∗​,...,αN∗​)T是对偶最优化问题（7）~（9）对 $\alpha$α 的解，则存在下标$j$j，使得$0<\alpha_j^*<C$0<αj∗​<C，并可按下式求得原始最优化问题（2）~（4）的解$w^*,b^*$w∗,b∗:
$w^* = \sum_{i=1}^N\alpha_i^*y_ix_i \tag{10}$w∗=i=1∑N​αi∗​yi​xi​(10)
$b^* = y_j-\sum_{i=1}^N\alpha_i^*y_i(x_i·x_j) \tag{11}$b∗=yj​−i=1∑N​αi∗​yi​(xi​⋅xj​)(11)

        由定理可知，分离超平面可以写成
$\sum_{i=1}^N\alpha_i^*y_i(x·x_i)+b^*=0 \tag{12}$i=1∑N​αi∗​yi​(x⋅xi​)+b∗=0(12)
$f(x)=sign \left(\sum_{i=1}^N\alpha_i^*y_i(x·x_i)+b^*\right) \tag{13}$f(x)=sign(i=1∑N​αi∗​yi​(x⋅xi​)+b∗)(13)
式（24）称为线性SVM的对偶形式。

---

算法 线性可分SVM学习算法

输入：线性可分的训练集$T=\{(x_1, y_1), (x_2, y_2), ..., (x_N, y_n=N))\}$T={(x1​,y1​),(x2​,y2​),...,(xN​,yn​=N))}，其中$X\in \mathcal{X} =R^n$X∈X=Rn，$y_i\in \mathcal{Y}=\{+1,-1\},\;\;i=1,2,...,N$yi​∈Y={+1,−1},i=1,2,...,N
输出：分离超平面和分类决策函数。

（1）选择惩罚参数$C>0$C>0，构造并求解约束最优化问题
$\min_{\alpha} \;\;\; \frac12\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i·x_j)-\sum_{i=1}^N\alpha_i$αmin​21​i=1∑N​j=1∑N​αi​αj​yi​yj​(xi​⋅xj​)−i=1∑N​αi​
$s.t. \;\;\;\;\sum_{i=1}^N\alpha_iy_i=0$s.t.i=1∑N​αi​yi​=0
$0 \leq\alpha_i\leq C,\;\;\;i=1,2,...,N$0≤αi​≤C,i=1,2,...,N
求得最优解$\alpha^*=(\alpha_1^*,\alpha_2^*,...,\alpha_N^*)^T$α∗=(α1∗​,α2∗​,...,αN∗​)T。

（2）计算
$w^* = \sum_{i=1}^N\alpha_i^*y_ix_i$w∗=i=1∑N​αi∗​yi​xi​
并选择$\alpha^*$α∗的一个正分量$0<\alpha_j^*<C$0<αj∗​<C，计算
$b^* = y_j-\sum_{i=1}^N\alpha_i^*y_i(x_i·x_j)$b∗=yj​−i=1∑N​αi∗​yi​(xi​⋅xj​)

（3）求得分离超平面
$w^*·x+b^*=0$w∗⋅x+b∗=0
分类决策函数：
$f(x)=sign(w^*·x+b^*)$f(x)=sign(w∗⋅x+b∗)

        由于原始问题对$b$b的解并不唯一，在实际计算时可以取在所有符合条件的样本点上的平均值。

---

支持向量

        在线性不可分的情况下，将对偶问题（7）~（9）的解$\alpha^*=(\alpha_1^*,\alpha_2^*,...,\alpha_N^*)^T$α∗=(α1∗​,α2∗​,...,αN∗​)T中对应于$\alpha_i^*>0$αi∗​>0的样本点$(x_i,y_i)$(xi​,yi​)的实例$x_i$xi​称为支持向量（软间隔的支持向量）。如下图所示：

        软间隔的支持向量$x_i$xi​或者在间隔边界上，或者在间隔边界与分离超平面之间，或者在分离超平面误分一侧。

• 若 $\alpha^*<C，则\xi_i=0$α∗<C，则ξi​=0，支持向量$x_i$xi​恰好落在间隔边界上；
• 若 $\alpha^*=C，0<\xi_i<1$α∗=C，0<ξi​<1，则分类正确，支持向量$x_i$xi​在间隔边界与分离超平面之间；
• 若 $\alpha^*=C，\xi_i=1$α∗=C，ξi​=1，则支持向量$x_i$xi​在分离超平面上；
• 若 $\alpha^*=C，\xi_i>1$α∗=C，ξi​>1，则支持向量$x_i$xi​位于分离超平面误分一侧。

---

合页损失函数

        线性SVM学习还有另外一种解释，就是最小化以下目标函数：
$\sum_{i=1}^N \left[1-y_i(w·x_i+b)\right]_++\lambda||w||^2 \tag{14}$i=1∑N​[1−yi​(w⋅xi​+b)]+​+λ∣∣w∣∣2(14)
目标函数的第1项是经验损失或经验风险，函数
$L(y(w·x+b))=\left[1-y_i(w·x_i+b)\right]_+ \tag{15}$L(y(w⋅x+b))=[1−yi​(w⋅xi​+b)]+​(15)
称为合页损失函数(hinge loss function)。下标“+”表示以下取正值的函数：
$[z]_+=\begin{cases} z & z>0 \\ 0 & z \leq 0 \end{cases} \tag{16}$[z]+​={z0​z>0z≤0​(16)
这就是说，当样本点$(x_i,y_i)$(xi​,yi​)被正确分类且函数间隔（确信度）$y_i(w·x_i+b)$yi​(w⋅xi​+b)大于1时，损失是0，否则损失是$1-y_i(w·x_i+b)$1−yi​(w⋅xi​+b)。目标函数的第2项是系数为 $\lambda$λ 的 $w$w 的 $L_2$L2​ 范数，是正则化项。

---

定理
        线性SVM原始最优化问题：
$\min_{w,b,\xi}\;\;\;\;\frac12||w||^2 + C\sum_{i=1}^N\xi_i$w,b,ξmin​21​∣∣w∣∣2+Ci=1∑N​ξi​
$s.t. \;\;\;\; y_i(w·x_i+b) \geq 1-\xi_i,\;\;\;i=1,2,...,N$s.t.yi​(w⋅xi​+b)≥1−ξi​,i=1,2,...,N
$\;\;\;\;\;\;\;\; \xi_i \geq 0,\;\;\;i=1,2,...,N$ξi​≥0,i=1,2,...,N
等价于最优化问题
$\min_{w,b}\;\;\;\;\sum_{i=1}^N \left[1-y_i(w·x_i+b)\right]_++\lambda||w||^2$w,bmin​i=1∑N​[1−yi​(w⋅xi​+b)]+​+λ∣∣w∣∣2

---

        合页损失函数的图形如下所示，横轴是函数间隔$(y(w·x+b)$(y(w⋅x+b)，纵轴是损失。由于函数形状像一个合页，所以称为合页损失函数。
        图中还画出了0-1损失函数，可以认为它是二类分类问题真正的损失函数，而合页损失函数是0-1损失函数的上界。由于0-1损失函数不是连续可导的，直接优化由其构成的目标函数比较困难，可以认为线性SVM是优化0-1损失函数的上界（合页损失函数）构成的目标函数。这时的上界损失函数又称为代理损失函数。

        上图中虚线显示的是感知机的损失函数$\left[y_i(w·x_i+b)\right]_+$[yi​(w⋅xi​+b)]+​。这时，当样本点$(x_i,y_i)$(xi​,yi​)被正确分类时，损失是0，否则损失是$-y_i(w·x_i+b)$−yi​(w⋅xi​+b)。相比之下，合页损失函数不仅要分类正确，而且确信度足够高时损失才是0。也就是说，合页损失函数对学习有更高的要求。