5 线性分类 SVM.pdfVIP

机器学习 第五讲 张兆翔 课程回顾 线性分类模型 +1 -1 线性分类模型 +1 -1 线性分类模型 +1 -1 线性分类模型 +1 -1 线性分类模型 +1 -1 线性分类模型 +1 -1 线性分类模型 +1 -1 线性分类模型 +1 -1 线性分类模型 支持向量机 数学描述  训练样本的集合： 数学描述  分类超平面：  假设该分类超平面对应的Margin值为 ， 则可得到两个边的方程为： 数学描述  对于两类样本而言： 数学描述  求解最大的 情况下的分类超平面。 数学求解  拉格朗日乘数法 maximize minimize  w,b 数学求解  将等式代入拉格朗日函数： 数学求解 maximize   根据Karush‐Kuhn‐Tucker (KKT) 条件，分类面为最 优分类面的条件为： 几何意义  超平面法向量是支持向量的线性组合 决策方程 如果线性不可分怎么办？ 如果线性不可分怎么办？ 比较一下 硬Margin 软Margin 优化求解 maximize  优化求解 几何意义 非线性SVM  线性分类器在解决复杂问题时适应性较差  主要思想：  非线性映射，将线性不可分问题转化为线性可 分问题。  在映射空间中用线性SVM方法求解。 非线性可分问题  XOR 问题 线性SVM‐非线性SVM 非线性SVM 内积函数 核函数 核函数能够作为内积函数的条件 常用的核函数  多项式核函数  RBF核函数  Sigmoid核函数 SVM工具  LibSVM： .tw/~cjlin/libsvm/ VC维理论 VC维  为了研究经验风险最小化函数集的学习一致收敛速度 和推广性，统计学习理论（SLT）定义了一些指标来 衡量函数集的性能，其中最重要的就是VC维 (Vapnik-Chervonenkis Dimension) 。  VC维：对于一个指示函数（即只有0和1两种取值的 函数）集，如果存在h个样本能够被函数集里的函数 按照所有可能的2h种形式分开，则称函数集能够把h 个样本打散，函数集的VC维就是能够打散的最大样本 数目。 VC维的例子  线性分类器  VC维：h=d+1 VC维  一般而言,VC维越大, 学习能力就越强,但 学习机器也越复杂。  目前还没有通用的关于计算任意函数集的 VC维的理论,只有对一些特殊函数集的VC维 可以准确知道。  N维实数空间中线性分类器和线性实函数的 VC维是n+1。  Sin(ax)的VC维为无穷大。 回顾  SVM 的最终决策函数只由少数的支持向量所确定, 计算的复杂性取决于支持向量的数目,而不是样本 空间的维数,这在某种意义上避免了“维数灾难” 。  少数支持向量决定了最终结果,这不但可以帮助我 们抓住关键样本、“剔除”大量冗余样本,而且注定 了该方法不但算法简单,而且具有较好的“鲁棒”性。 这种“鲁棒”性主要体现在:  ①增、删非支持向量样本对模型没有影响;  ②