支持向量机SVM

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

非线性支持向量机与核函数

核技巧

非线性分类问题

        非线性分类问题是指通过利用非线性模型才能很好地进行分类的问题。
        假设给定一个特征空间上的的训练数据集 $T=\{(x_1, y_1),(x_2,y_2),...,(x_N,y_N)\}$T={(x1​,y1​),(x2​,y2​),...,(xN​,yN​)}，如果能用$R^n$Rn中的一个超曲面将正负例正确分开，则称这个问题为非线性可分问题。非线性问题往往不好求解，所以希望能用解线性分类问题的方法解决这个问题。采用的方法是进行一个非线性变换，将非线性问题转换成线性问题，如下图示例。

        假设原空间为$\mathcal{X} \subset R^2,x=(x^{(1)},x^{(2)})^T\in \mathcal{X}$X⊂R2,x=(x(1),x(2))T∈X，新空间为$\mathcal{Z} \subset R^2,z=(z^{(1)},z^{(2)})^T\in \mathcal{Z}$Z⊂R2,z=(z(1),z(2))T∈Z，定义从原空间到新空间的变换（映射）：
$z=\phi(x)=((x^{(1)})^2,(x^{(2)})^2)^T$z=ϕ(x)=((x(1))2,(x(2))2)T
经过变换$z=\phi(x)$z=ϕ(x)，原空间$\mathcal{X} \subset R^2$X⊂R2变为新空间$\mathcal{Z} \subset R^2$Z⊂R2，原空间中的椭圆
$w_1(x^{(1)})^2+w_2(x^{(2)})^2+b=0$w1​(x(1))2+w2​(x(2))2+b=0
变成新空间中的直线
$w_1z^{(1)}+w_2z^{(2)}+b=0$w1​z(1)+w2​z(2)+b=0
        用线性分类方法求解非线性分类问题（核技巧）分为两步：

• 使用一个变换将原空间的数据映射到新空间
• 在新空间里用线性分类学习方法从训练集学习模型

        核技巧应用到SVM，其基本想法就是通过一个非线性变换将输入空间对应于一个特征空间，使得在输入空间$R^n$Rn中的超曲面模型对应于特征空间$\mathcal{H}$H中的超平面模型（SVM），分类问题可以通过在特征空间中求解线性SVM完成。

---

核函数的定义

定义 核函数
        设 $\mathcal{X}$X是输入空间（欧氏空间$R^n$Rn的子集或离散集合），又设$\mathcal{H}$H是特征空间（希尔伯特空间），如果存在一个从$\mathcal{X}$X到$\mathcal{H}$H的映射
$\phi(x)：\mathcal{X} \rightarrow \mathcal{H} \tag{1}$ϕ(x)：X→H(1)
使得对所有的$x,z \in \mathcal{X}$x,z∈X，函数$K(x,z)$K(x,z)满足条件
$K(x,z) = \phi(x)·\phi(z) \tag{2}$K(x,z)=ϕ(x)⋅ϕ(z)(2)
则称$K(x,z)$K(x,z)为核函数，$\phi(x)为映射函数$ϕ(x)为映射函数，式子中的$·$⋅代表内积。
        核技巧的想法是，在学习与预测中只定义核函数$K(x,z)$K(x,z)，而不显示地定义映射函数$\phi$ϕ。通常直接计算$K(x,z)$K(x,z)比较容易，通过$\phi$ϕ计算并不容易。对于给定的核$K(x,z)$K(x,z)，特征空间$\mathcal{H}$H和映射函数$\phi$ϕ的取法并不唯一，可以取不同的特征空间，即使同一特征空间也可以取不同的映射。

---

核技巧在SVM中的应用

        在线性SVM的对偶问题中，无论目标函数还是决策函数（分离超平面）都只涉及输入实例与实例之间的内积，对偶问题中的内积可以用核函数代替。此时，对偶问题的目标函数成为：
$W({\alpha}) = \frac12\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_jK(x_i,x_j)-\sum_{i=1}^N\alpha_i\tag {3}$W(α)=21​i=1∑N​j=1∑N​αi​αj​yi​yj​K(xi​,xj​)−i=1∑N​αi​(3)
同样，分类决策函数中的内积也可以用核函数代替，分类决策函数就变成：
$f(x)=sign \left(\sum_{i=1}^N\alpha_i^*y_i\phi(x_i)·\phi(x)+b^*\right) =sign \left(\sum_{i=1}^N\alpha_i^*y_iK(x_i,x)+b^*\right) \tag{4}$f(x)=sign(i=1∑N​αi∗​yi​ϕ(xi​)⋅ϕ(x)+b∗)=sign(i=1∑N​αi∗​yi​K(xi​,x)+b∗)(4)
        这等价于经过映射函数$\phi$ϕ将原来的输入空间变成一个新的特征空间，将输入空间中的内积变成特征空间中的内积，在新的特征空间中学习线性SVM。当映射函数是非线性时，学习到的含有核函数的SVM是非线性分类模型。学习是隐式地在特征空间进行的，不需要显示地定义特征空间和映射函数。核函数选择的有效性需要通过实验验证。

---

正定核

        函数$K(x,z)$K(x,z)满足什么条件才能成为核函数？
        依据函数$K(x,z)$K(x,z)构成一个希尔伯特空间，其步骤是：

• 定义映射，构成向量空间$S$S
• 在$S$S上定义内积，使其成为内积空间
• 将内积空间$S$S完备化为希尔伯特空间

定义 正定核的充要条件
        设$K:\mathcal{X}×\mathcal{X} \rightarrow R$K:X×X→R是对称函数，则$K(x,z)$K(x,z)为正定核函数的充要条件是对任意$x_i\in \mathcal{X}, i=1,2,..., m,\;K(x,z)$xi​∈X,i=1,2,...,m,K(x,z)对应的Gram矩阵：
$K=\left[K(x_i,x_j)\right]_{m×m} \tag{5}$K=[K(xi​,xj​)]m×m​(5)
是半正定矩阵。