从低维空间映射到高维空间

异或问题式线性不可分的，但是可以通过把它映射到高维度空间实现线性可分。
令 ϕ(x) 表示将 x 后的特征向量。于是，在特征空间中划分超平面所对应的模型可以表示为：

f (x) = w T ϕ (x) + b

于是

prototype 可以表示为：

min w, b 1 2 | | w | | T s . t . y i (w T ϕ (x i) + b) \geq 1, i = 1, 2, \dots, m .

对偶问题：

max α s . t . \sum i = 1 m α i - 1 2 \sum i = 1 m \sum j = 1 m α i y i α j y j ϕ (x i) T ϕ (x j) \sum i = 1 m α i y i = 0, α i \geq 0, i = 1, 2, \dots, m .

因为涉及到计算

ϕ(xi)Tϕ(xj) ,这是样本映射到特征空间后的内积，由于特征空间维数可能很高，甚至可能式无穷维，因此直接计算

ϕ(xi)Tϕ(xj) 通常十分困难。

核函数

为了避开直接计算的障碍，可以设想一个函数。

k (x i, x j) = ⟨ ϕ (x i), ϕ (x j) ⟩ = ϕ (x i) T ϕ (x j)

即

xi 和

xj 在特征空间内的内积等于它们在原始样本空间通过函数

k(⋅,⋅) 计算的结果。
于是

prototype 可以被重写为：

max α s . t . \sum i = 1 m α i - 1 2 \sum i = 1 m \sum j = 1 m α i y i α j y j k (x i, x j) \sum i = 1 m α i y i = 0, α i \geq 0, i = 1, 2, \dots, m .

求解后得到：

f (x) = w T ϕ (x) + b = \sum i = 1 m a i y i ϕ (x i) T ϕ (x i) + b = \sum i = 1 m a i y i k (x i, x j) + b (A)

这里的函数 k(⋅,⋅) 就是“核函数”,展开式 A 就是“支持向量展开式”。

令 χ 为输入空间， k(⋅,⋅) 是定义在 χ×χ 上的对称函数，则 k 是核函数当且仅当对于任意的数据 D={x1,x2,…,xm} ,核矩阵 K 总是半正定的

K = ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ k (x 1, x 1) ⋮ k (x i, x 1) ⋮ k (x m, x 1) \dots ⋱ \dots ⋱ \dots k (x 1, x j) ⋮ k (x i, x j) ⋮ k (x m, x j) \dots ⋱ \dots ⋱ \dots k (x 1, x m) ⋮ k (x i, x m) ⋮ k (x m, x m) ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥

若 k1 和 k2 为核函数，则对于任意的正数 γ1 、 γ2 以下三种组合可以得到新的核函数：
线性组合：

γ 1 k 1 + γ 2 k 2

核函数直积：

k 1 \otimes k 2 (x, z) = k 1 (x, z) k 2 (x, z)

对任意的函数

g(x) :

k (x, z) = g (x) k 1 (x, z) g (z)