统计学习statisticallearning.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * COLT(Computational Learning Theory) * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Chap8 SVM Zhongzhi Shi * － Edgar Osuna(Cambridge,MA)等人在IEEE NNSP’97发表了An Improved Training Algorithm for Support Vector Machines ,提出了SVM的分解算法，即将原问题分解为若干个子问题，按照某种迭代策略，通过反复求解子问题，最终使得结果收敛于原问题的最优解。 传统的利用二次型优化技术解决对偶问题时： 需要计算存储核函数矩阵。当样本点数较大时，需要很大的存储空间。例如：当样本点超过4000时，存储核函数矩阵就需要多达128兆内存； SVM在二次型寻优过程中要进行大量的矩阵运算，通常寻优算法占用了算法时间的主要部分。 SVM寻优算法 * Chap8 SVM Zhongzhi Shi * 考虑去掉Lagrange乘子等于零的训练样本不会影响原问题的解，采用一部分样本构成工作样本集进行训练，移除其中的非支持向量，并把训练结果对剩余样本进行检验，将不符合KKT条件的样本与本次结果的支持向量合并成为一个新的工作集。然后重新训练，如此重复获得最优结果。 例如：基于这种思路的 算法。 根据子问题的划分和迭代策略的不同，大致分为： 块算法(Chunking Algorithm)： SVM寻优算法 * Chap8 SVM Zhongzhi Shi * SMO使用了块与分解技术，而SMO算法则将分解算法思想推向极致，每次迭代仅优化两个点的最小子集，其威力在于两个数据点的优化问题可以获得解析解，从而不需要将二次规划优化算法作为算法一部分。尽管需要更多的迭代才收敛，但每个迭代需要很少的操作，因此算法在整体上的速度有数量级的提高。另外，算法其他的特征是没有矩阵操作，不需要在内存中存储核矩阵。 块算法(Chunking Algorithm)： SVM寻优算法 * Chap8 SVM Zhongzhi Shi * SMO算法每次迭代时，在可行的区域内选择两点，最大化目标函数，从而优化两个点的最小子集。无论何时，当一个乘子被更新时，调整另一个乘子来保证线性约束条件成立，保证解不离开可行区域。每步SMO选择两个参数优化，其他参数固定，可以获得解析解。尽管需要更多的迭代才收敛，但每个迭代需要很少的操作，因此算法在整体上的速度有数量级的提高。另外，算法其他的特征是没有矩阵操作，不需要在内存中存储核矩阵。 SVM寻优算法 * Chap8 SVM Zhongzhi Shi * SVM寻优算法 类别名称 测试样本数 错误分类数 准确度（%） 政治 146 4 97.26 军事 83 0 100 经济 137 3 97.81 法律 32 2 93.75 农业 106 2 98.11 体育 90 1 98.89 卫生 34 1 97.06 工业 87 2 97.70 科技 111 2 98.20 交通 40 1 97.50 生活 91 1 98.90 宗教 3 0 100 天气 24 2 91.67 合计 984 21 97.87 * Chap8 SVM Zhongzhi Shi * SMO算法核缓存算法 SMO算法在每次迭代只选择两个样本向量优化目标函数，不需要核矩阵。虽然没有核矩阵操作，但仍需要计算被选向量和训练集中所有样本向量的核函数，计算次数为2n（n为训练集中的样本数）。如果训练集中的样本选取有误，在噪声比较多的情况下，收敛会很慢，迭代次数很多，则核函数的计算量也是非常可观的，SMO 算法的优点就完成失去了。同时，考虑到文本分类的文本向量一般维数比较大，核函数的计算将会非常耗时，尤其在高价多项式核和高斯核等核函数的计算中表现更加明显。 SVM寻优算法 * Chap8 SVM Zhongzhi Shi * SMO算法核缓存算法 在内存中为SMO算法核函数开辟n行m列的核矩阵空间。其中：n为训练集中的样本数；m是为可调节参数，根据实际的内存大小进行调整，每列存放训练集中某个样本向量与训练集中所有样本向量的核函数计算结果列表。在核矩阵列头生成m个节点的双向循环链表队列，每个节点指向核矩阵的列，通过双向循环链表队列实现核矩阵中的核函数列唤入唤出操作。同时，为了实现样本向量的核函数列的快速查找，为每个训练样本向量设计了快速索引列表，通过索引列表判断该训练样本向量的