3. 非线性SVM
3.1 问题定义
现实任务中，训练样本经常不是线性可分的，即原始样本空间中并不存在一个能正确划分两类样本的超平面。
对于这样的问题，基于Mercer核展开定理，通过内积函数定义的非线性变换，将样本从原始空间映射到一个高维特征空间（Hibbert空间），使得样本在这个高维特征空间内线性可分（升维线性化）。
令ϕ ( x ) 表示将x 映射后的特征向量，在特征空间中划分超平面对应的模型可表示为
优化目标为
其对偶问题为
该问题和线性可分SVM的优化目标函数的区别仅仅是将内积x i x j 替换为ϕ ( x i ) T ϕ ( x j )
ϕ ( x i ) T ϕ (x j )是x i 与x j映射到特征空间后的内积，由于特征空间维数很高，甚至是无穷维，因此直接计算ϕ ( x i ) T ϕ ( x j )通常是困难的。
如对于一个2维特征的数据(X1,X2) ，需要将其映射到5维( 1 ，
)来做特征的内积。
3.2 核函数
假设ϕ 是一个从低维的输入空间χ（欧式空间的子集或者离散集合）到高维的希尔伯特空间H的映射。如果存在函数K ( , ) 对于任意x i x j∈χ都有：
即x i 与x j在特征空间的内积等于它们在原始样本空间中通过函数K ( , ) 计算的结果，则称K ( , )为核函数。
核函数使得计算在低维特征空间中进行，避免了高维特征空间中的巨大计算量，同时还利用了高维空间线性可分的特性。
对于任意 x i∈ χ , i = 1 , 2 , 3... m ,i=1,2,3...m，K ( ⋅ , ⋅ ) 是正定核函数，当且仅当K (x i ,x j )对应的Gram矩阵K = [ K (x i , x j ) ] 为半正定矩阵。
径向基函数核（RBF,Radial basis Function）又称高斯核。
