kernal

定义

核方法是一类把低维空间的非线性可分问题，转化为高维空间的线性可分问题的方法。

理论基础:核方法的理论基础是Cover’s theorem，指的是对于非线性可分的训练集，可以大概率通过将其非线性映射到一个高维空间来转化成线性可分的训练集。

核函数是映射关系的内积，映射函数本身仅仅是一种映射关系，并没有增加维度的特性，不过可以利用核函数的特性，构造可以增加维度的核函数。

设 $X$ 是输入空间（即 $x_{i} \in X$ ， $X$ 是 $ℝ^{n}$ 的子集或离散集合），又设 $H$ 为特征空间（ $H$ 是希尔伯特空间），如果存在一个从 $X$ 到 $H$ 的映射

$ϕ (x) : X \to H$

使得对所有 $x, z \in X$ ,函数 $K (x, z)$ 满足条件

$K (x, z) = ⟨ ϕ (x), ϕ (z) ⟩$

则称 $K$ 为核函数。其中 $ϕ (x)$ 为映射函数， $⟨ \cdot, \cdot ⟩$ 为内积。

即核函数输入两个向量，它返回的值等于这两个向量分别作 $ϕ$ 映射然后点积【内积】的结果。

核技巧是一种利用核函数直接计算 $⟨ ϕ (x), ϕ (z) ⟩$ ，以避开分别计算 $ϕ (x)$ 和 $ϕ (z)$ ，从而加速核方法计算的技巧。

注意
得益于SVM对偶问题的表现形式，核技巧可以应用于SVM。
TODO 没有了解
核函数的选择是SVM的最大变数，如果核函数选择不适，那么将不能将输入空间映射到线性可分的特征空间。

判断核函数

不知道 $ϕ$ 的情况下，如何判断某个 $K$ 是不是核函数？

答案: 是 $K$ 是核函数当且仅当对任意数据 $D = x_{1}, x_{2}, \dots, x_{m}$ ，核矩阵(kernal matrix,gram matrix)总是半正定的

知识补充：实对称矩阵
如果有n阶矩阵A，其矩阵的元素都为实数，且矩阵A的转置等于其本身（aij=aji），(i,j为元素的脚标），则称A为实对称矩阵。

知识补充：「正定矩阵」(positive definite)和「半正定矩阵」(positive semi-definite)
正定矩阵： 给定一个大小为 $n \times n$ 的实对称矩阵 $A$ ，若对于任意长度为 $n$ 的非零向量 $x$ ，有 $x^{T} A x > 0$ 恒成立，则矩阵 $A$ 是一个正定矩阵。
半正定矩阵： 给定一个大小为 $n \times n$ 的实对称矩阵 $A$ ，若对于任意长度为 $n$ 的向量 $x$ ，有 $x^{T} A x > 0$ 恒成立，则矩阵 $A$ 是一个正定矩阵。
半正定矩阵包括了正定矩阵，核矩阵与协方差矩阵都要半正定