感知机 +SVM+LR


本文地址:http://www.6aiq.com/article/1535303033153
知乎专栏 点击关注
本文版权归作者和AIQ共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出

整理人:张辽,厦门大学信科院 计算机技术专业

weChat: zhangliaobet

主要内容

1. 补充

? 1.1 最小二乘法的概率解释

2. 支持向量机

? 2.1 模型与策略

? 2.2 硬间隔最大化

????2.2.1 函数间隔与几何间隔

????2.2.2 间隔最大化原理

????2.2.3 线性可分 SVM 狗万赢钱(速度)_狗万 提款到账快_狗万取款免费6算法——最大间隔法

????2.2.4 最大间隔法示例

????2.2.5 线性可分 SVM 狗万赢钱(速度)_狗万 提款到账快_狗万取款免费6的对偶算法

????2.2.6 对偶狗万赢钱(速度)_狗万 提款到账快_狗万取款免费6算法示例

??2.3 软间隔最大化(下)

3. LR(下)

  1. 补充

    1.1?最小二乘法的概率解释

? ?前文向大家介绍了最小二乘的解析式以及它的几何解释,下面我们尝试从概率的角度,去探讨最小二乘与极大似然估计的关系。先做这样几个假设:

  • 误差总是存在的

? ?首先要说明的,所有的预测值都不可能完美地与真实值契合,所以误差必然存在,而我们的目的就是如何让误差尽可能地小。这样就可以假设有一组θ,使真实的数据存在以下关系式,y(i) 表示真实值,θTx(i) 表示预测值,ε表示误差项:

  • 假设误差服从高斯分布

? ??至于为什么可以这样假设,原因是人们认为误差是随机的,所以服从高斯分布。根据中心极限定理,也能够做出这样的假设。该定理指出,如果一个随机变量是若干独立随机变量的总和,当被加的个数趋近于无穷大时,他的概率密度函数近似高斯密度。并且误差也是独立同分布 (Independent Identical Distribution,IID)。

?其中μ是正态分布随机变量的均值,σ2 是此随机变量的方差,也可以记作 N(μ,σ2)。

? 设ε的平均值为 0,方差为ε2,ε的高斯分布,也就是ε的概率密度函数表示如下:

  • 求真实值的概率分布

? ? ?ε的概率密度函数,就是预测值与真实值差的概率密度函数,那么可以把上述两个等式合并,经过变换,得到如下等式:

  • 求联合概率分布

? ?这样相当于给定一组θ、x,求出了 y 的概率密度分布,联合概率分布等于边缘概率分布的乘积:

  • 定义对数似然函数

? ?这里我们就得到了一个关于 x、y、θ的模型,它表示真实值 y 的联合概率分布。当我们想使预测正确的概率最大时,只需要将 L(θ) 最大化就可以了。于是,求值问题又变成了求最大值问题。为了方便计算,我们定义对数似然函数,L(θ),也就是对 L(θ) 取对数,再求最大值。对数函数为一个单调递增函数,所以不会对原函数造成影响。取对数后,累乘变成累加。

?? ? ? ?

? ?等式第一项是一个常数项,第二项是一个负数项。要让 L(θ) 最大,就要让负数项最小:

? 这又回到了我们熟悉的式子上面来了,简单的来说,最小二乘法就是误差服从高斯分布且独立同分布下的极大似然估计。

  1. 支持向量机

    2.1 模型与策略

90 年代的时候,在贝尔实验室,Yann Lecun 和 Vapnik 经常就 SVM 和神经网络的优劣展开激烈的讨论,但那个时候,神经网络发展的并不是很强大,反观 SVM 的理论研究则更加深入,通过核技巧成功将 SVM 的应用层面从线性可分扩展到线性不可分的情况,一度占据上风。

支持向量机 (SupportVector Machine, SVM) 是一种二类分类模型,它的基本模型是定义在特征空间上的间隔最大的线性分类器,间隔最大使它有别于感知机;支持向量机的狗万赢钱(速度)_狗万 提款到账快_狗万取款免费6策略是间隔最大化,可形式化为一个求解凸二次规划 (convex quadratic programming) 的问题,也等价于正则化的合页损失函数的最小化问题。

当训练数据可分时,通过硬间隔最大化 (hardmarginmaximization),狗万赢钱(速度)_狗万 提款到账快_狗万取款免费6一个线性的分类器,即线性可分支持向量机,又称为硬间隔支持向量机;当训练数据近似可分时,通过软间隔最大化 (softmargin maximization)?,也狗万赢钱(速度)_狗万 提款到账快_狗万取款免费6一个线性分类器,称为软间隔支持向量机。

**?2.2 硬间隔最大化 **

? 对于二维特征空间的线性可分的二分类问题,如上图所示两种类别。这时有无数个直线能将两类数据正确区分。但哪种看起来分的更呢?也就是说如何去定义“好”呢,有这样两种度量方式,一种叫做函数间隔,另外一种叫 ** 几何间隔,** 函数间隔与几何间隔的概念如下。

??1.2.1?函数间隔与几何间隔

  • ** 函数间隔 ?**

? ?对于给定的训练数据集 _T和超平面 (w,b),定义超平面 (w,b) 关于样本点 (x__i,y_i) 的函数间隔为

如图所示,数据点到分界面的在 y 轴上的距离即函数间隔(蓝线所示)。

定义超平面 (w,b) 关于训练数据集 T 的函数间隔为超平面 (w,b) 关于 T 中所有样本点 (xi,yi) 的函数间隔之最小值,即

? 函数间隔可以表示分类预测的正确性及确信度。但是当等比例的改变 w 和 b 时,如

? 超平面没有改变,但是函数间隔变为原来的 k 倍,即

? 如果对超平面的法向量 w 加以约束,使得间隔是确定的,这时函数间隔成为几何间隔。

  • ** 几何间隔 ? ?**

    对于给定的训练数据集 T 和超平面 (w,b),定义超平面(w,b) 关于样本点 (xi,yi) 的几何间隔为

? 其中,||w|| 为 w 的 L2 范数。

? 下图为几何间隔的示例图。其中 w 为超平面的法向量,A 点到超平面的距离为γi

? 定义超平面 (w,b) 关于训练数据集 T 的几何间隔为超平面 (w,b) 关于 T 中所有样本点 (xi,yi) 的几何间隔之最小值,即

? 如果等比例的改变超平面参数 w 和 b, 函数间隔按比例改变,而几何间隔不变。

**? 1.2.2 间隔最大化原理 **

  • 最大间隔分离超平面

? ?对于一个线性可分的数据来说,我们总能找到一个超平面能将它区分开来,那么对这个超平面来说,我们也可以找到距离这个超平面最近的一些数据点,也就是与超平面几何间隔最小的这些数据点,即,但是我们找的这个超平面可能不是最优的,这个最优的意思是说,不仅将这些数据正确分开,并且对于那些距离超平面最近的数据点(难分的数据点)也让它离超平面尽可能的远,这样的超平面对于未知数据就有很好的预测能力。因此我们要最大化几何间隔。也称之为硬间隔最大化。

?下面我们狗万赢钱(速度)_狗万 提款到账快_狗万取款免费6如何求得最大间隔分离超平面。这个问题可以转化为下面的约束最优化问题:

? 该问题第一项表示的是要求最大化超平面 (w,b) 关于训练集的几何间隔γ,第二项约束条件表示的是超平面 (w,b) 关于每个训练样本的几何间隔至少是γ。

? 考虑到几何间隔与函数间隔的关系,上述问题可改写为如下问题:

? 假设把 w 和 b 按照比例变为 k 倍,约束优化问题变为如下形式:

?可以看出函数间隔的这一变化,对上述最优化问题的不等式约束没有影响,对目标函数的优化同样没有影响,也就是说,它产生了一个等价的最优化问题。为此取=1。另外考虑到最大化和最小化和最小是等价的。于是我们可以得到如下的线性可分支持向量机狗万赢钱(速度)_狗万 提款到账快_狗万取款免费6的最优化问题:

**? 1.2.3 线性可分 SVM 狗万赢钱(速度)_狗万 提款到账快_狗万取款免费6算法——最大间隔法 **

**??** 求解出上述约束最优化问题的解 w和 b后,那么就可以得到最大间隔分离超平面

**?w*******·x+ b*******?= 0**

及分类决策函数

f(x)= sign(w*****·x +b*****),

即线性可分支持向量机模型。

下面我们总结一下整个算法流程。

输入:线性可分训练数据集 _T={(x1,y1),(x2,y2),···,(xN,yN)},其中,xi∈χ=Rn_yi∈У={-1,+1},i= 1,2,···,N

输出:最大间隔分离超平面和分类决策函数。

  1. 构造并求解约束最优化问题:

? 求得最优解 w和 b

  1. 由此得到分离超平面:

    w*****·x + b*****=_?_0

    分类决策函数

    f(x) = sign(w*****·x+ b*****)

**? ?1.2.4 最大间隔法示例 **

**
**

**??** 有如下一组数据集:

? 在坐标轴上如下所示:

? 根据上述算法,根据训练数据集构造约束最优化问题:

? 化简可得:

? 问题转化为求圆心到某一区域最小值的问题,如下图所示:



上图中红色标记所示点,即为我们要求的解。求得:

带入约束条件求 b 得:

最终可得:

其中棕色直线是我们求得的最终分界面,而与之平行的另外两条虚线是支撑向量所在的直线,落在这两条直线上的数据点到分界面的距离相等,它们支撑起了整个分类器的分类性能,保证了最优的分类效果。

**? ?1.2.5 线性可分 SVM 狗万赢钱(速度)_狗万 提款到账快_狗万取款免费6的对偶算法 **

  • 拉格朗日对偶性 ?

? ?在约束最优化问题中,常常利用拉格朗日对偶性将原始问题转换为对偶问题,通过解对偶问题而得到原始问题的解。这样做一是因为对偶问题往往更容易求解;二是因为自然引入核函数,进而推广到非线性分类问题。

  • 原始问题

    考虑如下约束最优化问题

? 称此约束最优化问题为原始最优化问题或原始问题。

? 首先引入拉格朗日函数

? 考虑 x 的函数

? 这里,下标 P 表示原始问题。

? 若存在 x, 使得 ci(x)>0 或者 hj(x)≠0,则有

? 相反地,如果 x 满足约束条件,则

? 因此

? 所以如果考虑极小化问题

? 它与原始问题是等价的,即它们有相同的解。上述称为广义拉格朗日的极小极大问题。

? 定义原始问题的最优值

称为原始问题的值。

  • 对偶问题

    定义

? 考虑极大化上述定义,即:

? 上述问题称为广义拉格朗日函数的极大极小问题。

? 可以把广义拉格朗日的极大极小问题表示为约束最优化问题:

称为原始问题的对偶问题。

? 定义对偶问题的最优值

称为对偶问题的值。

  • 原始问题与对偶问题的关系

    对任意的α,β和 x, 有

?? ?

? ?即

? 由于原始问题和对偶问题均有最优值,所以,

? 即

  • KKT**** 对偶互补条件

? ?假设函数 f(x) 和 ci(x) 是凸函数,hj(x) 是仿射函数,且约束 ci(x) 严格可执行,则 x和α,β分别是原始问题和对偶问题的解的充分必要条件是 x和α*,β* 满足如下的 KKT 条件:

? 其中αici(x)=0 称为 KKT 的对偶互补条件。若αi*>0, 则 ci(x*)=0

  • 狗万赢钱(速度)_狗万 提款到账快_狗万取款免费6的对偶算法

    根据拉格朗日对偶性,原始问题得对偶问题是极大极小问题:

? 为了得到对偶问题的解,需要先求 _L(w,b,α)_ 对 w,b 的极小,再求对α的极大。

? 首先,定义拉格朗日函数:

? 求对拉格朗日函数 L(w,b,α) 分别求偏导并令其为 0 得:

? 把求导所得带入拉格朗日函数:

? 即

接下来再求对α的极大,即是对偶问题:

将该问题的目标函数由求极大转为求极小,得到与之等价的对偶最优化问题:

把目标函数展开成如下形式:

是上述对偶最优化问题的解,设原始最优化问题的解 w和 b。我们接下来求原始最优化问题的解

根据李航书中定理 C.3,KKT 条件成立,可得:

由此可得:

最终,分类决策函数为:

1.2.6 对偶狗万赢钱(速度)_狗万 提款到账快_狗万取款免费6算法示例

我们还是使用最大间隔法中的数据集:

首先根据

带入数据得:

最终求得:

把求得的α带入

带入数据得:

最终得到的超平面为:

如图所示为分离超平面:

可以看到所获得分界面与硬间隔最大化的结果一致,也验证了通过求解对偶问题来解决原始问题的有效性,并且这其中还可以得出一些有意思的结论,我们通过上述算法求得了关于每个数据点的值,其中支撑向量的是不为 0(),而其他数据点的为 0(),从 w 的更新公式也可以看出一些端倪:

只有支撑向量(或支持向量)才会改变 w,也就是说除了支撑向量外,其余数据点对于分类是没有帮助的,即值为 0。

对线性可分问题来说,硬间隔最大化算法解决的十分完美,但是现实世界中,往往并不是线性可分的,那么如何解决呢?是否有更一般的算法呢?那么下一讲,将会为大家讲解软间隔最大化以及逻辑斯蒂回归等相关内容。

注:文中所有推导过程均可在课件中找到,获取本讲课件,请回复课件二字即可领取。

Reference

[1]?Suykens, Johan AK, and Joos Vandewalle. “Least squares support vector machine classifiers.”?_Neural processing letters?_9.3 (1999): 293-300.

[2]?Smola, Alex J., and Bernhard Sch?lkopf. “A tutorial on support vector regression.”?Statistics and computing?14.3 (2004): 199-222.

[3]?李航. “统计狗万赢钱(速度)_狗万 提款到账快_狗万取款免费6方法.”?清华大学出版社, 北京?(2012).


本文地址:http://www.6aiq.com/article/1535303033153
知乎专栏 点击关注
本文版权归作者和AIQ共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出