机器学习神经网络与支持向量机部分.ppt

3.选取两个向量作为需要调整的点（例如第一次下标为1，2两点，第二次下标3，4...........），然后序贯最小优化算法（SMO）第158页,共158页，星期六，2024年，5月线性不可分的核函数方法 对于线性不可分（非线性）问题：采用一个非线性变换φ(x)把输入数据映射到一个高维特征空间，然后在高维特征空间进行线性分类，最后再映射回到原空间就成为输入空间的非线性分类。 考虑到可能存在一些样本不能被分离超平面分离，增加一个松弛变量ξ，优化问题为： 约束为 其中，C为一常数，起控制对错分样本惩罚的程度的作用，实现在错分样本的比例与算法复杂度之间的折衷。C值越大，表示主要把重点放在减少分类错误上，C值越小，表示主要把重点放在分离超平面，避免过学习问题。第126页,共158页，星期六，2024年，5月线性不可分的核函数方法 Lagrange函数定义如下： 式中，αi≥0,βi≥0。第127页,共158页，星期六，2024年，5月线性不可分的核函数方法 分别对w，b和ξi求偏微分并置0，得 带入Lagrange函数，得优化问题的对偶形式： 在约束条件： 下，求下列函数的最大值：第128页,共158页，星期六，2024年，5月 特征空间的维数非常高,在大多数情况下难以直接在特征空间计算最优分类面。支持向量机通过定义核函数(KernelFunction)方法将这一问题转化到输入空间进行计算： 假设有非线性映射φ:Rn→H将输入空间的样本映射到高维特征空间H中，当在特征空间构造最优分类面时,训练算法仅使用特征空间的点积，即φ(xi)Tφ(xj)。所以，只要构造一个函数K()使得K(xi,xj)=φ(xi)Tφ(xj),这样，在高维空间中实际上只需进行内积计算，不必知道变换φ的形式。 线性不可分的核函数方法第129页,共158页，星期六，2024年，5月根据泛函的有关理论，只要一种函数K(x,xi)满足Mercer条件，它就对应某一变换空间的内积。满足Mercer条件的内积函数K(x,xi)称为核函数，常用的核函数主要有： 高斯径向基函数： 神经网络函数：d次多项式：线性不可分的核函数方法第130页,共158页，星期六，2024年，5月 优化问题变为： 约束条件： 求下列函数的最大值 对应的分类函数为：线性不可分的核函数方法第131页,共158页，星期六，2024年，5月…K(x1,x)…K(x2,x)K(xs,x)α1y1α2y2αsysy权值wi=αiyi基于s个支持向量x1,x2,…,Xs的非线性变换（内积）输入向量xxdx1x2线性不可分的核函数方法第132页,共158页，星期六，2024年，5月支持向量机的学习算法①给出一组输入样本xi,i=1,2,…,n及其对应的期望输出yi∈{+1,-1}；②在约束条件：下求解下面函数的最大值，得到；③计算： 其中xs为一个特定的支持向量；④ 对于待分类向量x，选择某一特定类型的核函数K(x,xi),计算： 为+1或-1，决定x属于哪一类。线性不可分的核函数方法-归纳第133页,共158页，星期六，2024年，5月 支持向量机求解实际是二次规划问题，经典的解法有积极方集法、对偶方法、内点算法等。当训练样本增多时，这些算法便面临“维数灾难”将导致无法训练，近年来许多学者提出了多种算法来解决对偶寻优问题。1、块算法 选择一部分样本构成工作样本集，在工作样本集上使用通用的优化算法训练数据。算法保持了支持向量而剔除其中的非支持向量，并用训练结果对剩余样本进行检验，将不符合训练结果的样本与本次结果的支持向量合并成为一个新的工作样本集，重新训练，如此重复直至获得最优结果。当支持向量的数目远远小于训练样本数目时，块算法能够大大提高运算速度。支持向量机的学习算法第134页,共158页，星期六，2024年，5月2、分解算法 分解算法把问题分解成为固定样本数的子问题，工作样本集的大小固定在算法速度可以容忍的限度内，每次只针对工作集中固定样本个数进行训练。在对工作集进行优化训练后，该方法只更新乘子αi的一个固定大小的子集，其他保持不变。即每当一个新样本加入到工作集中，工作集中另一个样本要被移走，即使支持向量的个数超过工作样本集的大小也不改变工作样本集的规模。然后再进行优化训练，重复进行。该方法关键是如何选择一种最优工作集，使得对应的二次规划子问题的优化成为整个目标函数的改进。支持向量机的学习算法第135页,共158页，星期六，2024年，5月SVM支持向