机器学习 05：非线性支持向量机

主要思想

---

定理：
对于线性不可分的点，一定可以有一个维度使其线性可分。

基于此定理，我们可以使用支持向量机解决线性不可分的数据，即把数据集映射到一个高纬度，之后再进行线性分类。

升维

---

假设原先的样本点是 ${\vec{x}}_i$，用 $\varphi ({\vec{x}}_i)$ 表示映射到新的特征空间后的新样本点。那么分割超平面可以表示为

$$f(\vec{x})=\vec{w}\varphi (\vec{x})+b$$

于是非线性支持向量机的对偶问题就成了：

$$\begin{gathered} \underset{\vec{\alpha }}{\max }\sum _{i=1}^N{\alpha }_i-\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j\varphi ({\vec{x}}_i{)}^T\varphi ({\vec{x}}_j) \\ s.t.\sum _{i=1}^N{\alpha }_i{y}_i=0,0\le {\alpha }_i\le C \end{gathered}$$

但是从低维空间映射到高维空间后的维度可能很高，这样会大大增加 $\varphi ({\vec{x}}_i{)}^T\varphi ({\vec{x}}_j)$ 的计算量，所以需要通过其它办法来简化运算。这就用到了核函数。

核函数

---

核函数的作用

由于目标函数和分类决策函数都只涉及样本之间的内积，所以不需要显式地指定非线性变换，而是用核函数替换当中的内积。设 $K(x,z)$ 是一个核函数，或正定核，则存在一个从输入空间到特征空间的映射 $\varphi (\vec{x})$，对任意输入空间的 $\vec{x},\vec{z}$ 有

$$K(\vec{x},\vec{z})=\varphi (\vec{x})\cdot \varphi (\vec{z})$$

假设我们的输入空间是 $m$ 维，特征空间是 $d$ 维，那么通过核函数就可以把 $d$ 维运算降到 $m$ 维运算。当 $d$ 非常大甚至是无穷时，核函数可以减少大量的运算。

常见的核函数

1. 线性核函数：$K({\vec{x}}_i,{\vec{x}}_j)={\vec{x}}_i^T{\vec{x}}_j+c$

2. 多项式核函数：$K({\vec{x}}_i,{\vec{x}}_j)=(\alpha {\vec{x}}_i^T{\vec{x}}_j+c{)}^d$

3. 径向基核函数（高斯核函数）：$K({\vec{x}}_i,{\vec{x}}_j)=e^{-\gamma \parallel {\vec{x}}_i-{\vec{x}}_j{\parallel }^2}$

4. $sigmod$ 核函数：$K({\vec{x}}_i,{\vec{x}}_j)=\tanh (\alpha {\vec{x}}_i^T{\vec{x}}_j+c)$

同步更新于：SP-FA 的博客

---

返回