基于核函数的学习算法教程文件.ppt

Kernel-Based Learning Algorithms;引言;理论基础 监督学习:SVM、KFD 无监督学习：KPCA 模型选择;理论基础;SLT(Statistical Learning Theory); 机器学习;风险最小化－机器学习问题表示;VC维;一般而言,VC维越大, 学习能力就越强,但学习机器也越复杂。 目前还没有通用的关于计算任意函数集的VC维的理论,只有对一些特殊函数集的VC维可以准确知道。 ;结构风险最小化准则;核函数;核方法分为核函数设计和算法设计两个部分,具体情况如图1所示。核方法的实施步骤,具体描述为: ①收集和整理样本,并进行标准化; ②选择或构造核函数; ③ 用核函数将样本变换成为核矩阵; ④在特征空间对核矩阵实施各种线性算法;⑤得到输入空间中的非线性模型。 ;核函数;有监督学习(supervised?learning);SVM（Support vector machines);支持向量机方法建立在统计学习理论基础之上，专门针对小样本情况下的机器学习问题。 对于分类问题，支持向量机方法根据区域中的样本计算该区域的分类曲面，由该曲面决定该区域中的样本类别。 已知样本x 为m 维向量, 在某个区域内存在n个样本: (x1,y1)，(x2,y2)，…，(xn,yn) 其中，xi 是训练元组，xi∈Rm，yi是类标号，yi∈{1,-1}。 若存在超平面( hyperplane): ω·x + b = 0 (1);其中·表示向量的点积，如图1 所示，超平面能将这n 个样本分为两类,那么存在最优超平面不仅能将两类样本准确分开，而且能使两类样本到超平面的距离最大。式(1) 中的ω和b 乘以系数后仍能满足方程，进行归一化处理之后，对于所有样本xi ，式| ω·xi + b| 的最小值为1 , 则样本与此最优超平面的最小距离为|ω·xi + b |/‖ω‖= 1/‖ω‖,那么最优超平面应满足条件: yi（ω·xi + b）≥1，i=1，…，n. (2) ;根据最优超平面的定义可知:ω和b 的优化条件是使两类样本到超平面最小距离之和2/‖ω‖最大。 此外，考虑到可能存在一些样本不能被超平面正确分类,因此引入松弛变量 (slack variable)： ζi≥0， i=1，…，n. （3） 这样上述二元分类问题转换为在式(2) 和式(3)的约束下最小化： （4） 其中,非负常数C 为惩罚因子，C 值越大表示对错误分类的惩罚越大。这是一个具有线性约束的二次规划问题，利用拉格朗日乘子法可以将式(4) 转化为其对偶形式: (5) 约束条件: (6);其中ai为原问题中与约束条件式(2) 对应的拉格朗日乘子。 这是一个不等式约束下的二次函数寻优问题，存在高效的算法求解。可以证明，在此寻优问题的解中有一部分ai不为0，它们所对应的训练样本完全确定了这个超平面，因此称其为支持向量(support vector)。 对于类型未知的样本x , 可以采用线性判决函数: 来判断其所属类别,综合式(9)，可得分类判决函数: ;根据核函数的相关知识，可以使用核函数K( xi ·xj )替代线性分类问题中的点积形式，从而实现非线性变换后的线性分类。由此,式(5) 的对偶形式可变为： 约束条件： 相应的分类判决函数转变为: ;Kernel Fisher discriminant analysis（基于核的Fisher判别方法）;线性Fisher判别分析;考虑到J(w)的尺度不变性,令分母为非零常数,用Lagrange乘子法求解得到下面的特征值： W*就是J(w)中的极值解,也就是矩阵S - 1ω Sb的最大特征值对应的特征向量。测试样本在这个向量上的投影系数就是所提取的测试样本的特征值。 则FDA的判别函数为 b为偏移