svm算法简介..ppt

svm(supported vector machine) 线性可分 线性不可分 情况1：样本本质上是非线性可分的 解决方法：核函数 情况2：本质上线性，非线性由噪音导致 强制使用非线性函数，会导致过拟合 解决方法：软间隔 线性可分 定义： 对于来自两类的一组模式 ,如果能用一个线性判别函数正确分类,则称他们是线性可分的。 线性可分情况 函数间隔 定义函数间隔为： 接着，我们定义超平面（w,b）关于训练数据集T的函数间隔为超平面（w,b）关于T中所有样本点（xi,yi）的函数间隔最小值，其中，x是特征，y是结果标签，i表示第i个样本，有 定义函数间隔的原因 一般而言，一个点距离超平面的远近可以表示为分类预测的确信或准确程度。在超平面 确定的情况下， 能够相对的表示点X到超平面的远近，而 的符号与类标记y的符号是否一致表示分类是否正确，所以，可以用量 的正负性来判定或表示分类的正确性和确信度，于是引出函数间隔概念。 函数间隔的局限性 上述定义的函数间隔虽然可以表示分类预测的正确性和确信度，但在选择分类超平面时，只有函数间隔还远远不够，因为如果成比例的改变w和b，如将他们改变为2w和2b，虽然此时超平面没有改变，但函数间隔的值却发生改变。我们可以对法向量w加些约束条件，使其表面看起来规范化，如此，我们引入了真正意义点到超平面的距离--几何间隔。 几何间隔 在函数间隔 的基础上，对w和b进行归一化，即为几何间隔： 这时如果成比例的改变w和b，几何间隔的值不会发生改变。 因为wx+b=0，为了方便，我们可以按任意比例缩放w和b，而不会改变结果。我们可以添加这样的约束条件 ，这意味着可以先求出w和b的解，之后重新缩放这些参数，就可以轻易地满足这个条件。 最大间隔分类器的定义 由于函数间隔的缺陷，不适合用来最大化一个量，因为在超平面固定以后，我们可以等比例地缩放w好b的值，这样可以使得 的值任意打，亦即函数间隔可以在超平面不变的情况下被取得任意大。 而几何间隔则没有这个问题，因为除上 这个分母，所以缩放w和b的时候几何间隔不会随之改变，它只随超平面的变动而变动，因此更加适合用其来定义最大距离。 因此，我们的最大间隔分类的目标函数可以定义为： 事实证明这个约束是一个非凸性约束，我们需要避免，所以我们需要改变优化问题的表述方式。 添加约束条件， 这是一个隐含的缩放约束，因为假设你已经解出了w和b，并且发现最差情形的函数间隔是10或者其他值，这样，通过对w和b除以10或者其他值，我们可以将函数间隔变为1。 此时，优化问题的表达式为： 我们的优化问题转变成了一个凸优化问题 拉格朗日乘数法的扩展形式 minf(w) s.t. gi(w)≤0 i=1,2,...,k hi(w)=0 i=1,2,...,l （这里0指的是零向量） 定义： 对偶问题 2.求对α的极大，即是关于对偶变量的优化问题 （SMO优化算法--序列最小最优化算法） 然后根据 可求出最优的w和b，即最优超平面。 一个简单的例子： 线性不可分情况下 情况1：样本本质上是非线性可分的 解决方法：核函数 但是能找到一条二次曲线将正负类分开，它的函数表达式可以写为： 原来在二维空间中一个线性不可分的问题，映射到四维空间后，变成了线性可分的。因此，这也形成了我们最初想解决线性不可分问题的基本思路---向高维空间转化，使其变得线性可分。 而转化的关键的部分在于找到x到y的映射方法。遗憾的是，如何找到这个映射没有系统的方法，此外，在数据维度较大时，计算困难（我们对一个二维空间做映射，选择的新空间是原始空间的所有一阶和二阶的组合，得到了五个维度；如果原始空间是三维，那么我们会得到 19 维的新空间，这个数目是呈爆炸性增长的，这给 的计算带来了非常大的困难，而且如果遇到无穷维的情况，就根本无从计算了）。 如果有一种方式可以在特征空间中直接计算内积〈φ(xi ）· φ(x)〉，就像在原始输入点的函数中一样，就有可能将两个步骤融合到一起建立一个非线性的学习器，这样直接计算法的方法称为核函数方法，于是，核函数便横空出世了。 核函数：对所有x,z属于X，满足 这里 是从X到内积特征