核函数
设$X$是输入空间（欧氏空间$R^n$的子集或离散集合），又设$H$为特征空间（希尔伯特空间），如果存在一个从$X$到$H$的映射：
$$
\phi(x): X \rightarrow H
$$
使得对所有的$x,z \in X$，函数$K(x,z)$满足条件：
$$
K(x,z) = \phi (x) \cdot \phi (z)
$$
则称$K(x,z)$为核函数，$\phi (z)$为映射函数。式中$\phi (x) \cdot \phi (z)$为$phi (x)$和$\phi (z)$的内积。
使用核函数的乘积代替向量内积
$$
W(\alpha) = \frac{1}{2} \sum\limits_{i=1}^N \sum\limits_{j=1}^N \alpha_i \alpha_j y_i y_j K(x_i,x_j) - \sum\limits_{i=1}^N \alpha_i
$$
$$
f(x)=sign \left(\sum\limits_{i=1}^{N_s} \alpha_i^0 y_i K(x_i,x) + b^0\right)
$$
定义映射和线性组合
定义映射：
$$
\phi : x \rightarrow K(\cdot, x)
$$
定义线性组合：
$$
f(\cdot) = \sum\limits_{i=1}^m \alpha_i K(\cdot, x_i)
$$
考虑由线性组合为元素的集合$S$，它构成一个向量空间。
求内积
对任意的$f,g \in S$，
$$
f(\cdot) = \sum\limits_{i=1}^m \alpha_i K(\cdot, x_i)
$$
$$
g(\cdot) = \sum\limits_{j=1}^m \beta_j K(\cdot, z_j)
$$
定义运算 $*$
$$
f * g = \sum\limits_{i=1}^m \sum\limits_{j=1}^l \alpha_i \beta_j K(x_i, z_j) \label{1}
$$
易知
$$
(cf) * g = c(f * g) \label{2}
$$
$$
(f+g) * h = f * h + g * h \label{3}
$$
$$
f * g = g * f \label{4}
$$
$$
f * f \ge 0 \label{5}
$$
下面证明$f * f = 0 \Rightarrow f = 0 \label{6}$
构造关于$\lambda$的二次式：
$$
(f + \lambda g) * (f + \lambda g) \ge 0 恒成立
$$
$$
(g * g) \lambda^2 + 2 \lambda (f * g) + f * f \ge 0 恒成立
$$
$$
\Delta = 4 [(f * g)^2 - (f * f)(g * g)] \lt 0
$$
于是
$$
|f * g| ^2 \le (f * f) \cdot (g * g)
$$
易知
$$
K(\cdot, x) * f = \sum\limits_{i=1}^m \alpha_i K(x, x_i) = f(x)
$$
于是
$$
\begin{split}
|f(x)|^2
& = |K(\cdot, x) * f | ^2 \
& \le (K * K) \cdot (f * f) \
& = K(x, x) \cdot (f * f)
\end{split}
$$
当$f * f = 0$时， 有：
$$
|f(x)|^2 \le K(x, x) \cdot (f * f) \le 0
$$
于是$f = 0$，证毕。
易知$f = 0 \Rightarrow f * f = 0 \label{7}$
由以上7式，$*$是$S$的内积，可用$\cdot$表示。
内积空间完备化
范数：
$$
||f|| = \sqrt{f \cdot f}
$$
因此$S$是一个赋凡向量空间，完备化得到赋范向量空间$H$。
正定核的充要条件
设$K: X \times X \rightarrow R$ 是对称函数，则$K(x,z)$为正定核的充要条件是：
$$
\forall x_i \in X,i=1,2,\dots,m
$$
$K(x,z)$对应的Gram矩阵：
$$
K = [K(x_i, x_j)]_{m \times m}
$$
是半正定矩阵。
正定核的等价意义
设$X \subseteq R^n$， $K(x,z)$是定义在$X \times X$ 上的对称函数，如果对任意的$x_i \in X, i=1, 2, \dots,m$，$K(x,z)$对应的Gram矩阵
$$
K=[K(x_i,x_j)]_{m \times m}
$$
是半正定矩阵，则称$K(x,z)$是正定核。
常用核函数
##多项式核函数
$$
K(x, z) = (x \cdot z + 1) ^p
$$
$$
f(x) = sign \left(\sum\limits_{i=1}^{N_s} \alpha_i^0 y_i (x_i + x + 1) ^p + b^0\right)
$$
高斯核函数
$$
K(x,z) = \exp \left( - \frac{||x - z ||^2}{2 \sigma ^2} \right)
$$
$$
f(x) = sign \left(\sum\limits_{i=1}^{N_s} \alpha_i^0 y_i \exp\left(- \frac{||x - z||^2}{2\sigma^2}\right) + b^0 \right)
$$
字符串核函数
两个字符串s和t上的字符串核函数是基于映射$\phi _n$的特征空间中的内积。
$$
K_n(s,t)
= \sum\limits_{u \in {\Sigma ^n}} [\phi_n (s)]_u [\phi_n (t)]_u
$$
$$
= \sum\limits_{u \in \Sigma^n} \sum\limits_{(i,j) : s(i) = t(j) = u} \lambda^{l(i)} \lambda^{l(j)}
$$
$0 \lt \lambda \le 1$ 是衰减参数，$l(i)$表示字符串$i$的长度。
非线形支持向量机学习算法
输入：训练数据集$T = \{ (x_1,y_1), \dots, (x_N,y_N) \}$，其中$x_i \in X = R^n,y_i \in Y = \{-1, 1\}, i=1, 2, \dots, N$
输出：分类决策函数
（1）选取适当的核函数$K(x,z)$和适当的参数$C$，构造并求解最优化问题：
$$
\min \limits_\alpha \frac{1}{2} \sum\limits_{i=1}^N \sum\limits_{j=1}^N \alpha_i \alpha_j y_i y_j K(x_i, x_j) - \sum\limits_{i=1}^N \alpha_i
$$
$$
\begin{split}
s.t. & \sum\limits_{i=1}^N \alpha_i y_i = 0 \\
& 0 \le \alpha_i \le C, i=1, 2, \dots, N
\end{split}
$$
求解得到最优解$\alpha^0 = (\alpha_1^0, \dots, \alpha_N^0)^T$
（2）选择$\alpha^0$的一个正分量$0 \lt \alpha_j^0 \lt C$，
$$
b^0 = y_j - \sum\limits_{i=1}^N \alpha_i^0 y_i K(x_i, x_j)
$$
（3）决策函数：
$$
f(x) = sign\left(\sum\limits_{i=1}^N \alpha_i^0 y_i K(x, x_i) + b^0\right)
$$
当$K(x,z)$是正定函数时，最优化问题是凸二次规划问题。