机器学习-吴恩达笔记7

Week7-SVM

本周主要是讲解了支持向量机SVM的相关知识点

硬间隔
支持向量
软间隔
对偶问题

优化目标Optimization Objectives

主要是讲解如何从逻辑回归慢慢的推导出本质上的支持向量机。逻辑回归的假设形式：

image

左边是假设函数
右边是Sigmoid激活函数

令 $z=\theta^Tx$ ，如果满足：

若 $y=1$ ，希望 $h(\theta)$ 约为1，将样本正确分类，那么z必须满足 $z>>0$
若 $y=0$ ，希望 $h(\theta)$ 约为0，将样本正确分类，那么z必须满足 $z<<0$

样本正确分类指的是：假设函数h(x)得到的结果和真实值y是一致的

image

总代价函数通常是对所有的训练样本进行求和，并且每个样本都会为总代价函数增加上式的最后一项（还有个系数 $\frac{1}{m}$ ，系数忽略掉）

如果 $y=1$ ，目标函数中只有第一项起作用，得到了表达式
$y=1-log(1-\frac{1}{1+e^{-z}})$

支持向量机

image

根据逻辑回归推导得到的支持向量机的公式
$min C\sum^m_{i=1}[y^{(i)}cost_1(\theta^Tx^{(i)})+(1-y^{(i)})cost_0(\theta^Tx^{(i)}]+\frac{1}{2}\sum^n_{i=1}\theta_{j}^2$
两个 $cost$ 函数是上面提到的两条直线。

对于逻辑回归，在目标函数中有两项：第一个是训练样本的代价，第二个是正则化项

大边界的直观解释

下面是支持向量机的代价函数模型。

image

SVM决策边界

image

SVM鲁棒性：间隔最大化，是一种大间距分类器。

image

关于上图的解释：

C太大的话，将是粉色的线
C不是过大的话，将是黑色的线

大间距分类器的描述，仅仅是从直观上给出了正则化参数C非常大的情形，C的作用类似于之前使用过的正则化参数 $\frac{1}{\lambda}$

C较大，可能导致过拟合，高方差
C较小，可能导致低拟合，高偏差

硬间隔模型

image

间隔和支持向量

注释：本文中全部采用列向量 $w=(w_1,w_2,…,w_n)^T$

给定一个样本训练集 $D=\{(x_1,y_1),(x_2,y_2),…,(x_m,y_m)\}$ ，其中 $y_i \in \{-1,+1\}$ 分类学习的基本思想就是：基于训练集D在样本空间上找到一个划分的超平面

image

上面红色的线是最好的。所产生的分类结果是最鲁棒的，最稳定的，泛化能力是最好的。

划分超平面的的线性描述：
$w \cdot x+b=0$
$w$ 称之为法向量（看做是列向量），决定平面的方向； $b$ 是位移项，决定了超平面和原点之间的距离。

空间中任意一点 $x$ 到超平面 $(w,b)$ 的距离是
$r=\frac{|w \cdot x + b|}{||w||}$
在 $+$ 区域的点满足 $y=+1$ ：
$w \cdot x_+ + b \geq1$
在 $-$ 区域的点满足 $y=-1$ ：
$w \cdot x_- + b \leq-1$
综合上面的两个式子有：
$y(w \cdot x_+ + b )-1 \geq0$

支持向量

距离超平面最近的几个点（带上圆圈的几个点）称之为“支持向量support vector”，这个点到超平面到距离称之为“间隔margin”

刚好在决策边界上的点（下图中带上圆圈的点）满足上式中的等号成立：
$y_i(w \cdot x + b) -1=0$

image

间距margin

求解间距margin就是求解向量 $(x_+-x_-)$ 在法向量上的投影
$\begin{align}margin& = (x_+-x_-)\cdot \frac{w}{||w||} \\& = \frac {(x_+ \cdot w-x_-\cdot w}{||w||}\end{align}$
决策边界上的正例表示为：
$y_i=+1 \rightarrow 1*(w\cdot x_+ +b) - 1 =0 \rightarrow w\cdot x_+ =1-b$
决策边界行的负例表示为：
$y_i=-1 \rightarrow -1*(w\cdot x_- +b) - 1 =0 \rightarrow w\cdot x_- =-1-b$
将两个结果带入margin 的表达式中
$margin=\frac {1-b-(-1-b)}{||w||}=\frac{2}{||w||}$

image

SVM的基本模型

最大间隔化只需要将 $||w||$ 最小化即可
$\min_{w,b}\frac{1}{2}||w||^2 \\s.t. y_i(w\cdot x_i+b) \geq 1 ;i=1,2,...,m$

SVM-对偶模型

模型参数推导

希望求解上面基本模型对应超平面的模型
$f(x)= w\cdot x+b$
利用拉格朗日乘子 $\alpha_i$ ，改成拉格朗日函数
$L(w,b,\alpha)=\frac{1}{2}||w||^2+\sum^m_{i=1}\alpha_i(1-y_i(w^Tx_i+b))$
分别对 $w,b$ 求导，可以得到
$w = \sum^m_{i=1}\alpha_iy_ix_i \\ 0 = \sum^m_{i=1}\alpha_iy_i$

对偶模型

原始问题是极大
$\min_{w,b}\max_{\alpha}L(w,b,\alpha)\rightarrow\max_{\alpha}\min_{w,b}L(w,b,\alpha)$
最大值问题：带入拉格朗日函数中，得到对偶问题（全部是关于 $\alpha$ 系数）
$\max _{\alpha}\sum^m_{i=1}\alpha_i-\frac{1}{2}\sum^m_{i=1}\sum^m_{j=1}\alpha_i\alpha_jy_i y_jx_i^Tx_j \\s.t. \sum^m_{i=1}\alpha_iy_i=0 \\\alpha_i \geq0;i=1,2,...,m$
转换一下，变成最小值问题（上面的式子加上负号）：
$\min _{\alpha}\frac{1}{2}\sum^m_{i=1}\sum^m_{j=1}\alpha_i\alpha_jy_i y_jx_i^Tx_j - \sum^m_{i=1}\alpha_i\\s.t. \sum^m_{i=1}\alpha_iy_i=0 \\\alpha_i \geq0;i=1,2,...,m$

那么超平面的模型
$\begin{align}f(x)& = w\cdot x+b \\& = \sum^m_{i=1}\alpha_iy_ix_i^Tx+b \end{align}$

SMO算法

思想

SMO算法指的是Sequential Minimal Optimization，序列最小优化算法。算法的根本思路是：

所有的 $\alpha$ 满足 $\sum^m_{i=1}\alpha_iy_i=0$ ：

先选取需要更新的变量 $\alpha_i$ 和 $\alpha_j$
固定变量 $\alpha_i$ 和 $\alpha_j$ 以外的参数，求解更新后的变量 $\alpha_i$ 和 $\alpha_j$

$\alpha_iy_i+\alpha_jy_j=c$

其中 $c$ 使得上式成立：
$c= \sum_{k \neq i,j}\alpha_ky_k$

将变量 $\alpha_i$ 和 $\alpha_j$ 的其中一个用另一个来表示，得到关于 $\alpha_i$ 的单变量二次规划问题，就可以求出来变量 $\alpha_i$

软间隔最大化

上面的结论和推导都是针对的线性可分的数据。线性不可分数据意味着某些样本点 $(x_i,y_i)$ 不再满足函数间隔大于等于1的约束条件，比如下图中的红圈中的点，故引入了松弛变量 $\xi_i \geq0$ ，满足：
$y_i(w \cdot x_i +b) +\xi_i \geq 1 \\ y_i(w \cdot x_i +b) \geq 1-\xi_i$

image

因此，目标函数由原来的 $\frac{1}{2}||w||^2$ 变成了
$\frac{1}{2}||w||^2+C\sum^N_{i=1}\xi _i$
其中 $C\geq0$ 是惩罚项参数，C值越大对误分类的越大，C越小对误分类的惩罚越小。

最后编辑于：2019.12.04 21:59:12

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 219,490评论 6赞 508
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 93,581评论 3赞 395
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 165,830评论 0赞 356
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 58,957评论 1赞 295
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 67,974评论 6赞 393
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 51,754评论 1赞 307
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 40,464评论 3赞 420
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 39,357评论 0赞 276
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 45,847评论 1赞 317
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 37,995评论 3赞 338
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 40,137评论 1赞 351
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 35,819评论 5赞 346
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 41,482评论 3赞 331
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 32,023评论 0赞 22
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 33,149评论 1赞 272
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 48,409评论 3赞 373
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 45,086评论 2赞 355

机器学习-吴恩达笔记7

优化目标Optimization Objectives

支持向量机

大边界的直观解释

SVM决策边界

硬间隔模型

间隔和支持向量

支持向量

间距margin

SVM的基本模型

SVM-对偶模型

模型参数推导

对偶模型

SMO算法

思想

软间隔最大化

推荐阅读更多精彩内容