【机器学习】支持向量机（4）——非线性支持向量机（核函数）

前言当训练数据集线性可分或者近似线性可分时，前面我们在文一以及文二已经介绍了线性可分支持向量机和线性支持向量机。但是有时训练数据集是非线性的，这时就可以使用非线性支持向量机。非线性支持向量机的主要特点就是利用了核技巧。非线性分类问题如上面左图，是一个分类问题，图中实心点为正类，空心点为负类；我们很容易看出，无法用直线（线性模型）将正负实例正确分开，但是可以通过椭圆曲线（...

Day-yong

4854人浏览 · 2018-07-30 19:37:13

Day-yong · 2018-07-30 19:37:13 发布

前言

当训练数据集线性可分或者近似线性可分时，前面我们在文一以及文二已经介绍了线性可分支持向量机和线性支持向量机。但是有时训练数据集是非线性的，这时就可以使用非线性支持向量机。

非线性支持向量机的主要特点就是利用了核技巧。

非线性分类问题

如上面左图，是一个分类问题，图中实心点为正类，空心点为负类；我们很容易看出，无法用直线（线性模型）将正负实例正确分开，但是可以通过椭圆曲线（非线性模型）将它们正确分开。

非线性问题往往不好求解，所以我们希望用线性分类问题的方法来解决这个问题。所采用的方法是进行非线性变换。

线性分类方法求解非线性分类问题一般分为两步：

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

核技巧

核技巧就是属于上诉介绍的方法，应用到支持向量机的基本思想就是通过一个非线性变换将输入空间对应于一个特征空间，使得在输入空间中的超曲面模型对应于特征空间中的超平面模型。

这样，分类问题的学习任务通过在特征空间中求解线性支持向量机就可以完成。

核函数的定义

设 X <script type="math/tex" id="MathJax-Element-124">\mathcal{X}</script> 是输入空间， H <script type="math/tex" id="MathJax-Element-125">\mathcal{H}</script>为特征空间，如果存在一个从 X <script type="math/tex" id="MathJax-Element-126">\mathcal{X}</script> 到 H <script type="math/tex" id="MathJax-Element-127">\mathcal{H}</script>的映射：

ϕ (x) : X \to H

x,z∈X, x , z ∈ X , <script type="math/tex" id="MathJax-Element-129">x,z \in \mathcal{X},</script>函数

K(x,z) K ( x , z ) <script type="math/tex" id="MathJax-Element-130">K(x,z)</script>满足条件：

K (x, z) = ϕ (x) \cdot ϕ (z)

K(x,z) K ( x , z ) <script type="math/tex" id="MathJax-Element-132">K(x,z)</script>为核函数，

ϕ(x) ϕ ( x ) <script type="math/tex" id="MathJax-Element-133">\phi(x)</script>为映射函数，式中

ϕ(x)⋅ϕ(z) ϕ ( x ) ⋅ ϕ ( z ) <script type="math/tex" id="MathJax-Element-134">\phi(x) \cdot \phi(z)</script>为内积

核技巧的想法：在学习与预测中只定义核函数 K(x,z) <script type="math/tex" id="MathJax-Element-135">K(x,z)</script>，而不显式地定义映射函数 ϕ <script type="math/tex" id="MathJax-Element-136">\phi</script>；
因为通常计算 K(x,z) <script type="math/tex" id="MathJax-Element-137">K(x,z)</script>比较容易，而通过 ϕ(x)和ϕ(z) <script type="math/tex" id="MathJax-Element-138">\phi(x)和\phi(z)</script>的内积来计算 K(x,z) <script type="math/tex" id="MathJax-Element-139">K(x,z)</script>并不容易；
ϕ <script type="math/tex" id="MathJax-Element-140">\phi</script>是输入空间到特征空间的映射，特征空间 H <script type="math/tex" id="MathJax-Element-141">\mathcal{H}</script>往往是高维的，甚至是无穷维；
对于给定的核 K(x,z) <script type="math/tex" id="MathJax-Element-142">K(x,z)</script>，特征空间 H <script type="math/tex" id="MathJax-Element-143">\mathcal{H}</script>和映射函数 ϕ <script type="math/tex" id="MathJax-Element-144">\phi</script>的取法并不唯一。

在我们之前学习线性可分支持向量机和线性支持向量机时，无论是目标函数还是决策函数（分离超平面）都只涉及输入实例与实例之间的内积。在对偶问题的目标函数中的内积 xi,xj <script type="math/tex" id="MathJax-Element-145">x_i,x_j</script>，可以用核函数 K(xi,xj)=ϕ(xi)⋅ϕ(xj) <script type="math/tex" id="MathJax-Element-146">K(x_i,x_j) = \phi(x_i) \cdot \phi(x_j)</script>来代替。此时对偶问题的目标函数成为：

W (α) = 1 2 \sum i = 1 N \sum j = 1 N α i α j y i y j K (x i, x j) - \sum i = 1 N α i

f (x) = s i g n (\sum i = 1 N s α * i y i K (x i, x) + b *)

这就等价于：
经过映射函数 ϕ <script type="math/tex" id="MathJax-Element-149">\phi</script>将原来的输入空间变换到一个新的特征空间，将输入空间中的内积 xi⋅xj <script type="math/tex" id="MathJax-Element-150">x_i \cdot x_j</script>变换为特征空间中的内积 ϕ(xi)⋅ϕ(xj) <script type="math/tex" id="MathJax-Element-151">\phi(x_i) \cdot \phi(x_j)</script>，在新的特征空间里，从训练样本中学习线性支持向量机，当映射函数是非线性函数时，学习到的含有核函数的支持向量机是非线性模型。

在核函数 K(x,z) <script type="math/tex" id="MathJax-Element-152">K(x,z)</script>给定的条件下，可以利用求解线性分类问题的方法求解非线性分类问题的支持向量机。学习是隐式地在特征空间进行，不需要显式地定义特征空间和映射函数，这样的技巧称为核技巧。

非线性支持向量机学习算法

输入：训练数据集
T={(x1,y1),(x2,y2),...,(xN,yN)} <script type="math/tex" id="MathJax-Element-103">T = \{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}</script>，其中 xi∈X=Rn，yi∈Y={−1,+1}，i=1,2,...,N <script type="math/tex" id="MathJax-Element-104">x_i \in \mathcal{X} = R^n，y_i \in \mathcal{Y} = \{-1,+1\}，i = 1,2,...,N</script>；

输出：分类决策函数。

（1）选取适当的核函数 K(x,z) <script type="math/tex" id="MathJax-Element-105">K(x,z)</script>和适当的参数 C <script type="math/tex" id="MathJax-Element-106">C</script>，构造并求解最优化问题：

min_{α} \frac{1}{2} \sum_{i = 1}^{N} \sum_{j = 1}^{N} α_{i} α_{j} y_{i} y_{j} K (x_{i}, x_{j}) - \sum_{i = 1}^{N} α_{i} s . t . \sum_{i = 1}^{N} α_{i} y_{i} = 0 0 ⩽ α_{i} ⩽ C ， i = 1, 2, . . ., N

α∗=(α∗1,α∗2,...,α∗N)T α ∗ = ( α 1 ∗ , α 2 ∗ , . . . , α N ∗ ) T <script type="math/tex" id="MathJax-Element-108">\alpha^* = (\alpha_1^*,\alpha_2^*,...,\alpha_N^*)^T </script>。

（2）选择 α∗ <script type="math/tex" id="MathJax-Element-109">\alpha^*</script>的一个正分量 0<αj<C <script type="math/tex" id="MathJax-Element-110">0 < \alpha_j < C</script>，计算：

b * = y j - \sum i = 1 N α * i y i K (x i, x j)

（3）构造决策函数：

f (x) = s i g n (\sum i = 1 N α * i y i K (x, x i) + b *)

当 K(x,z) <script type="math/tex" id="MathJax-Element-113">K(x,z)</script>是正定核函数时，该问题为凸二次规划问题，解是存在的。

常用核函数

名称	表达式	参数
线性核	k(xi,xj)=xTixj <script type="math/tex" id="MathJax-Element-114">k(x_i,x_j) = x_i^Tx_j</script>
多项式核	k(xi,xj)=(xTixj)p <script type="math/tex" id="MathJax-Element-115">k(x_i,x_j) = (x_i^Tx_j)^p</script>	p⩾1 <script type="math/tex" id="MathJax-Element-116">p \geqslant 1</script>为多项式的次数
高斯核	k(xi,xj)=exp(−\|\|xi−xj\|\|22σ2) <script type="math/tex" id="MathJax-Element-117">k(x_i,x_j) = exp(-\frac{\|\|x_i-x_j\|\|^2}{2\sigma^2})</script>	σ⩾1 <script type="math/tex" id="MathJax-Element-118">\sigma \geqslant 1</script>为高斯核的带宽
拉普拉斯核	k(xi,xj)=exp(−\|\|xi−xj\|\|σ) <script type="math/tex" id="MathJax-Element-119">k(x_i,x_j) = exp(-\frac{\|\|x_i-x_j\|\|}{\sigma})</script>	σ>0 <script type="math/tex" id="MathJax-Element-120">\sigma > 0</script>
Sigmoid核	k(xi,xj)=tanh(βxTixj+θ) <script type="math/tex" id="MathJax-Element-121">k(x_i,x_j)=tanh(\beta x_i^Tx_j + \theta)</script>	tanh <script type="math/tex" id="MathJax-Element-122">tanh</script>为双曲正切函数， β>0，θ<0 <script type="math/tex" id="MathJax-Element-123">\beta > 0，\theta < 0 </script>