凡科建站免费版可以做什么,公众号编辑器96,网站降权分析,网站开发工程师资格证线性感知机分类 支持向量机
线性感知机#xff08;Perceptron#xff09;
感知机是线性二值分类器。
注意#xff1a;什么是线性#xff1f;线性分割面就是#xff0c;就是在分割面中#xff0c;任意两个的连线也在分割面中#xff0c;这个分割面#xff0c;就是线… 线性感知机分类 支持向量机
线性感知机Perceptron
感知机是线性二值分类器。
注意什么是线性线性分割面就是就是在分割面中任意两个的连线也在分割面中这个分割面就是线性分割面。 f(x,w,b)sign(wxb)
wxb0, f1
wxb0, f-1 为什么分割面能写成 wxb0w 一个向量。
对于普通的方程 ykxb,那么我们可以写成 kx-yb0,写成向量方程就是
当k1时w(1,-1) 如下图知w 是分割面的法向量。 感知机--目标函数
最小化错误率
I 函数是当预测值 f() 与实际值 y 不相等时I1相等是 I0 。所以求和为错误的样本数。
我们可以转换成后边的函数sign 函数是wxb0 是 函数值为1wxb0 时函数值为-1.
那么如果分对sign 与 y 符号相同相减为 0如果分错sign 与 y 符号相反那么相减为2 或者 -2 所以需要除以2就是分错样本数了。 由于sign() 函数不是处处可导给算法设计带来困难。所以我们换一个容易的策略。 函数 ①
这个函数只统计分错样本所以如果全分对L0如果有分错样本时L0 (0,所以函数前边有个负号 结论线性可分时最小化 L 等价于最小化错误率。
注意如果不是线性不可分时这个结论不成立。
如w1xib0.2 分错 w1xjb0.3 分错 L10.5 w2xkb0.6 分错 L20.6 当为 w1 是有两个 样本点分错了错误率为2L10.5 但是当为 w2 时 有一个样本点分错了错误率为1 L20.6L1 现在我们要 最小化 函数 ①那么我对函数① 分别对w 和 b 求偏导。-xiyi,-yi
我们用梯度下降法来找函数① 的极值。
w w p*y_i*x_i
b b p*y_i 是学习率。
算法步骤 随机设定w b 的值 用当前wb轮流对所有的样本点分类如果分错更新(w,b) 的继续。 重复步骤2直到所有的点都被分对
感知机的不足 有无穷多个可行解 由于感知机是贪婪算法所以结果依赖初始值和误分点的顺序。 线性限制对于线性不可分的特征空间线性感知机无能为力 不足 1 不足 3
线性感知机有这些不足接下来我们看看在支持向量中是怎么弥补的。 支持向量机Support Vector Machine 线性可分硬间隔SVM 适用于线性不可分软间隔SVM SVM对偶问题和解的性质 非线性Kernel SVM
硬间隔 SVM 图 1 图 2 图 3
看图1这里有两个分割线到底哪个好呢对于新数据哪个方框到底应该属于哪一类呢我看到超平面不同对新数据的影响不同。
看图2间隔分界面到最近样本距离的两倍。 我们认为使间隔最大的分界面是最好的分界面因为间隔最大将来落在间隔内的新数据更够跟准确的分到所属的类中。 最大间隔分类器是使得间隔宽度最大的线性分类器。
看图3 要求对正样本wxb1 对负样本wxb-1
原因由于wxb0 那么肯定存在一个非常接近0的ε 使 wxbε ,两边同时除以 ε 得 wx/εb/ε1那么我将w/εw,b/εb(先的未知数),于是就有wxb1,同理wxb-1 求间隔margin M 由向量投影公式投影向量与投影方向单位向量的内积。
第二个式子是根据直角三角形计算出来的 将conθ 带入二式就得到了M的值。
wxb1 , y1
wxb1 , y-1 所以y(wxb)1
我们要最大 就等价于最小化因为而 是一个单调递增函数最小化的也就是最小化 x 同理最小化化优化问题前边加一个1/2 系数对优化问题没有影响添加一个1/2 系数是为了对二次求导有一个2系数相消。 这样就转化为一个关于 w 和 b 的二次规划问题 软间隔 SVM 感知机是有无穷多个可行解现在硬间隔SVM 通过最大间隔有唯一解。那么目前还有什么缺点对噪音的处理。现在都是要求线性可分如果存在噪音那么将会出现震荡。那么我们接下来看看软间隔是怎么解决噪音问题的。 如果存在噪音点。 软间隔 通过引入松弛变量ξi使得错分样本得到惩罚注意当还没有找到最优解时一些非噪音点也会遭到惩罚。 最小化松弛项同时最大化间隔。 minimize 错分样本对应的 ξi1,所以Σiξi错误样本个数。 硬间隔 VS 软间隔 硬间隔 软间隔 拉格朗日函数
为什么要引入拉格朗日函数呢?对于一般函数我们要极值我们只需求导等于零即可。那么对于带约束的函数求导我们怎么求他的极值。我们用拉格朗日乘子将目标函数和约束函数写到一个新函数中对这个新函数我们求导等于零即可。 优化问题 对每个约束引入拉格朗日乘子 ai,ui 得到 且 a0,u0
这个拉个朗函数根据 α和u 求最大然后根据wb ξ 求最小。
那么经这转换最后求出解还是原问题的解吗
分析内部最大化当不成立也就是小于 0 根据式子值α的系数是正数 且 α0那么这时根据 α 求拉格朗日函数的最大值为正无穷。 同理当不成立时 且 u0 拉格朗日函数最大值为正无穷。 当成立时α的系数是负数且α0 ,所以只有 α0 时拉个朗日函数的最大值为0. 当成立时 u 的系数是负数且u0 ,所以只有 u0 时拉个朗日函数的最大值为0.
结论 当 成立时拉格朗日函数 根据 a,u求得最大值为0则此在根据wb,ξ 求最小值就是原函数的最小值 当 不成立时拉格朗日函数 根据 a,u求得最大值为正无穷则此在根据wb,ξ 求最小值没有意义。 图1 图2
原问题就像图1
朗格朗日函数就像图2 拉个朗日的对偶问题 且ai0,ui0
对偶函数只是将最大化和最小化交换了一下位置。那么优化对偶函数的解和拉格朗日函数的解是一致的吗
凸优化是一样的。因为凸规划满足KKD条件。凸规划问题就是约束是凸集目标函数是凸函数。 求极值问题L对 w,b,ξ 求导等于零。 式1得到带入L 需满足式2,3和对偶条件 ai0 ui0 C-ai-ui0 Σyiai0
使用uiC-ai 消掉ui得到最终的对偶问题 由于 预测函数变为
求b满足 0aiC 的i 对应的支持向量解yif(xi)1得到b
对偶问题有点只需内积不需 x 具体值。这样也就可以用核函数了。
KKT 条件 最优化问题最后变成求KKT条件。只要满足KKT 条件的解就是原问题的最优解。 非线性SVM
对于线性可分数据线性SVM表现很好了。 如果训练数据本身存在复杂非线性关系在给定的特征空间中很难用线性模型较好的处理。 解决办法通过一个函数将原来的特征空间中的样本映射到高维的特征空间中: 将原来的数据的平方作为第二维。
原始空间中任意形状的两个区域总是可以在某些高维特征空间中映射成线性可分的区域。 将到原点的距离最为第四维的数据。 核函数 之前我们讲过SVM分类器的训练和预测都仅依赖于样本对的内积值 Kxi,xjxi^Txj
核函数对应某个特征空间中的内积。 核函数例子 线性这就是内积定义就是映射的还是原来的空间 p次多项式 高斯核RBF核特征空间是无限维空间此核可以用来逼近任意复杂的分类面σ 参数需要自己调 Sigmoir
注意引入Kernel 的同时带来高计算复杂度 Kernel SVM 中支持向量个数随样本数增多。 Kernel SVM 问题求解至少是n^2 复杂度。因为我们需要计算每个特性向量与其他特征向量的内积
最著名的两个工具包
LIBSVM: http://www.csie.ntu.edu.tw/~cjlin/libsvm/
SVM Light: http://www.cs.cornell.edu/People/tj/svm_light/ liblinear-1.93这个是针对线性可分的数据做了很多优化比libsvm-3.17 快很多。
