学习笔记：机器学习之支持向量机(七、求核函数)

活动地址：CSDN21天学习挑战赛

​1 简介

  求和函数可以通过求映射函数$\phi$，再求$\phi (x)$与$\phi (z)$之间的内积即可得到核函数$K(x,z)$,但是实际应用中可以不直接定义映射函数$\phi$，而是直接计算核函数$K(x,z)$。

概念介绍

1.Gram矩阵介绍

   n维欧氏空间中任意k(k${\alpha }_1,{\alpha }_2,...,{\alpha }_k$的内积组成的矩阵。
Δ ( α 1 , α 2 , ⋯   , α k ) = ( ( α 1 , α 1 ) ( α 1 , α 2 ) ⋯ ( α 1 , α k ) ( α 2 , α 1 ) ( α 2 , α 2 ) ⋯ ( α 2 , α k ) ⋯ ⋯ ⋯ ⋯ ( α k , α 1 ) ( α k , α 2 ) ⋯ ( α k , α k ) ) \Delta\left(\alpha_{1}, \alpha_{2}, \cdots, \alpha_{\mathrm{k}}\right)=\left(

(α1,α1)(α1,α2)⋯(α1,αk)(α2,α1)(α2,α2)⋯(α2,αk)⋯⋯⋯⋯(αk,α1)(αk,α2)⋯(αk,αk)" role="presentation">(α1,α1)(α2,α1)⋯(αk,α1)(α1,α2)(α2,α2)⋯(αk,α2)⋯⋯⋯⋯(α1,αk)(α2,αk)⋯(αk,αk)$$\begin{array}{cccc}\left({\alpha }_1,{\alpha }_1\right)& \left({\alpha }_1,{\alpha }_2\right)& \cdots & \left({\alpha }_1,{\alpha }_{\mathrm{k}}\right)\\ \left({\alpha }_2,{\alpha }_1\right)& \left({\alpha }_2,{\alpha }_2\right)& \cdots & \left({\alpha }_2,{\alpha }_{\mathrm{k}}\right)\\ \cdots & \cdots & \cdots & \cdots \\ \left({\alpha }_{\mathrm{k}},{\alpha }_1\right)& \left({\alpha }_{\mathrm{k}},{\alpha }_2\right)& \cdots & \left({\alpha }_{\mathrm{k}},{\alpha }_{\mathrm{k}}\right)\end{array}$$

\right) Δ(α1​,α2​,⋯,αk​)=⎝ ⎛​(α1​,α1​)(α2​,α1​)⋯(αk​,α1​)​(α1​,α2​)(α2​,α2​)⋯(αk​,α2​)​⋯⋯⋯⋯​(α1​,αk​)(α2​,αk​)⋯(αk​,αk​)​⎠ ⎞​

2.对称函数

   在对称函数中，函数的输出值不随输入变数的排列而改变。从函数的形式中可以看出若输入变量排列后，方程式不会改变。例如：$c{a}^2+3ab+c{b}^2$，在a和b对调后其值不变。

2 怎么找核函数

核函数满足的特征：

1. 核函数应该是对称函数
      $\phi (x_i)\cdot \phi (x_j)=K(x_i,x_j)$，核函数变量对调后值不变，所以核函数应该是对称函数。
2. $K(x_i,x_j)$对应的Gram矩阵半正定。
      核函数是内积的形式，所以其值大于等于0。

得到核函数$K(x_i,x_j)$之后构成一个希尔伯特空间(Hilbert Space)。
步骤为：
  1.定义映射φ ，并构成向量空间S；
    映射关系：$\varphi :x\to K(\cdot ,x)$
    定义线性组合：$f(\cdot )={\sum }_{i=1}^m{\alpha }_{i}K\left(\cdot ,x_i\right)$
    此时就构成了一个向量空间S。
  2.在S上定义内积构成内积空间;
    定义一个运算*， $f\ast g={\sum }_{i=1}^m{\sum }_{j=1}^l{\alpha }_i{\beta }_{j}K\left(x_i,z_j\right)$,再证明*是空间S的内积。
  3.最后将S完备化构成希尔伯特空间.

3 引入和函数后的非线性支持向量机

输入：训练集 T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , ⋯   , ( x N , y N ) } , y i ∈ − 1 , + 1 , i = 1 , 2 , . . . , N T=\left\{\left(x_{1}, y_{1}\right),\left(x_{2}, y_{2}\right), \cdots,\left(x_{N}, y_{N}\right)\right\},y_i \in{-1,+1},i=1,2,...,N T={(x1​,y1​),(x2​,y2​),⋯,(xN​,yN​)},yi​∈−1,+1,i=1,2,...,N
构造最优化问题：
${\min }_{\alpha }\frac{1}{2}{\sum }_{i=1}^N{\sum }_{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_{j}K\left(x_i,x_j\right)-{\sum }_{i=1}^N{\alpha }_i$
$s.t.{\sum }_{i=1}^N{\alpha }_i{y}_i=0,0⩽{\alpha }_i⩽C,i=1,2,\cdots ,N$
得到最优解${\alpha }^{\ast }$.
计算$b^{\ast }=y_j-{\sum }_{i=1}^N{\alpha }_i^{\ast }{y}_{i}K\left(x_i\cdot x_j\right)$
构造决策函数：
$$f(x)=\mathrm{sign}\left(\sum _{i=1}^N{\alpha }_i^{\ast }{y}_{i}K\left(x\cdot x_i\right)+b^{\ast }\right)$$

输出：分类决策函数

参考

1.《统计学习方法》——李航
2.https://zh.m.wikipedia.org/zh-cn/%E5%AF%B9%E7%A7%B0_(%E6%95%B0%E5%AD%A6)
​