2012年以来，数据的爆发式增长为深度学习算法在语音和视觉识别上实现突破，令人工智能产业落地和商业化发展成为可能，人工智能市场前景巨大。

通常将人工智能分为弱人工智能和强人工智能，前者让机器具备观察和感知的能力，可以做到一定程度的理解和推理，而强人工智能让机器获得自适应能力，解决一些之前没有遇到过的问题。但是目前的科研工作都集中在弱人工智能这部分
弱人工智能有希望取得突破，是如何实现的，“智能”又从何而来呢？这主要归功于一种实现人工智能的方法——机器学习
机器学习是一种实现人工智能的方法。机器学习最基本的做法是使用算法来解析数据、从中学习，然后对真实世界中的事件做出决策和预测。机器学习是用大量的数据来“训练”，通过各种算法从数据中学习如何完成任务。

深度学习是一种实现机器学习的技术。深度学习本来并不是一种独立的学习方法，其本身也会用到有监督和无监督的学习方法来训练深度神经网络。
下面用一幅图来梳理一下机器学习



最基础的是线性回归和神经网络，线性回归只能描述非常简单的映射关系，稍微复杂一点关系的描述就要加上非线性回归。如果把这些非线性的映射关系叠加起来就是一个神经网络。
神经网络输入的信息是一维的信息，输入是一维，不同的网络之间进行的是一个简单的代数运算，经过非线性激励形成新的学习层和下一层进行信息的交互。
CNN基本的代数运算用卷积和来代替，卷积核是二维的处理算子，神经网络到CNN（卷积神经网络）是空间上的扩展。CNN中卷积本质上就是利用共享的参数过滤器，通过计算中心像素点以及相邻像素点的加权和来构成feature map实现空间上的提取，当加权系数就是卷积核的权重系数。CNN的两大核心思想：网络局部连接、卷积核参数共享。
神经网络到RNN（循环神网络）是一个时间上的扩展，神经网络处理一维信息时，但是这些信息是有时间联系的，比如人的语音。神经网络处理这些关系的时候，把在某一刻的输出作为下一刻的输入，处理的是前一刻和这一刻的信息，通过时域递归方式，就可以找到之前信息和之后信息的关系，同时还能学习信息到最后判断映射关系。但是在信息的传递的过程中，每一次获取前一时刻的信息或出现信息的衰减。为了避免信息的逐层衰减，引入了LSTM（长短期记忆网络），长短记忆都可以学习。根据输入信息判断一些信息是需要提前记住的，在下一刻处理的时候判断前面记住的信息是否要释放。
线性回归，神经网络，卷积神经网络、循环神经网络，长短期记忆网络是整个深度学习的基础。在这个基础之上，我们可以辐射出很多方向。CNN是应用于图片分类，图片经过神经网络进行提取特征，再经过传统神经网络进行处理，最后进行判断。但是在现实生活中，收集到的图片并不是特别理想，比如有云、草、树等。那我们在处理图片的时候就要做目标分类和目标检测。
再转到LSTM，它善于处理一维信息。现在在语言的提取和生成方面发挥着巨大的作用，用于语言生成。
CNN和LSTM的结合，CNN善于图片的理解，LSTM善于语句的生成和时域信息的处理，可以用于视频的分类。
随着社会的发展辐射出了很多的应用，比如增强学习和对抗网络。增强学习是模仿人类学习的模型，不停地学习反馈，慢慢的学会决策的能力。另一个是对抗网络，是生成网络和判别网络的结合，有利于生成很多数据，相当于是一个无监督学习。
介绍到这里，相信大家对机器学习的结构已经有一些了解，接下来就来了解一下神经网络的实现过程吧

神经网络的实现过程分为四个部分

1、准备数据集

2、搭建NN结构，从输入到输出，先搭建计算图，再用会话执行

3、大量特征数据喂给NN，迭代优化NN参数

4、使用训练好的模型预测和分类
搭建神经网络一般按照八股

搭建神经网络的八股：准备、前向传播、反向传播、迭代

前向传播定义输入、参数和输出

反向传播定义损失函数、返乡传播方法，在会话中完成迭代

互联网的浪潮席卷全球，它功成名遂，高处不胜寒，一览众山小。然而时代的弄潮儿不会止步于此，他们还要站在新的浪潮之巅，去征服更大的世界。

一、前言：为何要学习机器学习
我不知道下一个风口到底是什么，但我相信人工智能、虚拟现实、区块链，至少有一种将重塑我们的未来。
经过数十年的发展，机器学习被认为是人工智能中最成熟、应用最广泛、成果最令人振奋的一环。人们对人工智能的遐想通常是拥有独立思维的人型机器，这从各个层面上来看都任重而道远。但机器学习带来的好处已经十分实在——语音/图像识别、人脸识别、智能推送（虽然很烦），以及日趋成熟的自动驾驶。
也许大家对铺天盖地的人工智能培训广告感到厌倦，对广告上诱人的高价薪酬半信半疑，但只要你用心学习一段机器学习，你就会发现它的魅力所在。互联网时代积累下来浩瀚的原始数据，我们需要一种强有力的工具去挖掘它们的价值，这种工具，或许正是打开新世界大门的钥匙。每一个技术人都不希望自己被淘汰，也许机器学习的知识不能帮你找到工作，但却是一张入场券。
据我所知，目前 AI 行业的门槛仍然较高，短期甚至有供过于求的情况。但互联网行业的发展也同样经历过这个时期。等到它真正爆发的时候再去入坑，其实已经晚了。二十年前一个学历普通的年轻人决定进入 IT 行业，只需要稍微培训一下甚至是自学一段时间就能进大厂，而且可能已经成为了行业大牛，但在今天想复制同样的成功却十分困难。为什么股市里那么多韭菜？牛市一窝蜂进去，熊市一窝蜂出来，止跌不止盈，高买低卖。也许道理我们都懂，但这是人性的弱点，我体会过，很难克服，所以，成功的永远只是少数人。
如果你只是为了找工作，想花费一两个月时间（甚至还坚持不了）去学机器学习，那还是放弃吧。如果我是公司老板，这个行业我不会冒险，直接从高学历应届毕业生里找人成本才是最低的。
如果你想真正掌握这门技术，Welcome to Westworld！
二、知识结构分析
下图是根据《机器学习实战》一书制作的思维导图，我们可以利用它来分析一下机器学习的知识结构。



图中，用红色星星标注的是前期需要重点学习的内容，也是比较通用的部分。绿色的饼状图代表我对特点知识的理解程度。
我想，这个结构比我们接触过的大部分学科都要简单。所以没有必要因为高大上的名字就产生畏难情绪。甚至可以再进一步将其简化为 “回归” 和 “分类” 两大部分。也许将来还会有 “极简机器学习手册” 之类的书籍诞生吧，谁知道呢。
书中按顺时针顺序组织章节内容，我觉得是 OK 的。
当然，机器学习还有其它的分支，比如大名鼎鼎的深度学习。但有了基础的 “思维” 之后，其它的部分其实可以看做是一种 “工具”，可以自然而然地掌握。
1 机器学习基础部分
机器学习需要什么先导知识呢？
本科正常毕业水平的线性代数、概率论，和一点点计算机知识即可。
忘了的知识可以复习，真遇到不懂的上网查查就好了。至于编程，由于有 Python 这样的语言在，只需要花费很少的时间（一周以内），就能从 0 开始读懂程序。如果你有任何一门语言的基础，那么根本不用单独花时间学 Python，遇到看不懂的语法直接搜索就完了。
关于线代和概率论，无论有没有基础，都推荐看一遍 「3Blue1Brown 的视频」，相信你会对这两门学科产生更深刻的认识，amazing!
2 分类
分类分为监督分类和非监督分类，又各自有不同的方法。
监督分类，如图所示，大致就是 KNN、决策树、贝叶斯、逻辑回归、SVM，其中 SVM 相对复杂点，其它的很容易理解。
非监督分类，主要就是聚类和密度估计。
3 回归
回归即定量的分析或预测。包括线性回归（简单线性回归和多元线性回归）和树回归。这部分的模型也很好理解。
关于回归和分类的区别，举个例子：
预测明天下不下雨，属于分类问题；

预测明天的降雨量，属于回归问题。
4 研究方向
其一，是寻找新的分类与回归问题的算法。
其二，是如何改进已有的算法，提高他们的准确度与运算效率。
其三，是研究如何把机器学习与实际应用更好地结合。
对于不打算走算法路线的同学们，只要不断跟进新的成果，并尝试去应用它们就足够了，把机器学习当做一个强有力的工具即可。
三、学习路径与资料分享
1 学习路径
其实刚才的结构分析中已经体现出来了。我的学习路径是这样的：
机器学习是什么 -> 线性回归 -> 逻辑回归 -> SVM -> 线代 -> KNN -> 贝叶斯 -> 决策树 …
各个算法的学习顺序无所谓，一个一个攻克即可。先把基础的学下来，并动手写代码实践，再尝试去改进它。
数学基础不用担心！！！
编程不用担心！！！
找不到对象完全不用担心！！！
2 学习资料
最后给大家推荐一些学习资料。
[1] GitHub - Avik-Jain/100-Days-Of-ML-Code，一个小哥分享的学习笔记与实践代码，时间比较充裕的学生党可以按照他每日的进度学习。
[2] 网盘 - 一些参考书籍与视频教程，提取密码：dnxs。是大佬分享给我的，内容很多，大家各取所需。
[3] MIT 的线代教程 ，需要补线代知识的同学可以刷一遍。这是比较正儿八经的数学课程。
[4] 斯坦福的机器学习教程，吴恩达老师是我们共同的老师。
[5] 一些培训机构的在线课程，比较适合没有大把时间学习的上班族，有人替你规划学习路线、督促你学习，目前来看价格还是不便宜的，大家自己做取舍吧。
[6] 「CSDN - Evan 的博客」，一个和你一起成长进步的热爱学习的新时代优秀青年，最大的优点是为人谦虚，低调。并没有太多才华，就是长得比较帅。关注我，让你体验超越我的感觉，重拾学习的自信与快乐。
声明
上述资源来自互联网，如有侵犯版权请联系我，我会在第一时间处理。
资料仅作为个人学习使用，切勿用在商业用途，请于下载后24小时之内删除，否则由此引发的法律纠纷及连带责任本人概不承担。
声明
上述资源来自互联网，如有侵犯版权请联系我，我会在第一时间处理。
资料仅作为个人学习使用，切勿用在商业用途，请于下载后24小时之内删除，否则由此引发的法律纠纷及连带责任本人概不承担。

引言
关于支持向量可以参考机器学习入门——支持向量机和李宏毅机器学习——支持向量机。
关于结构化学习的知识建议先阅读下李宏毅机器学习——结构化学习(二)。

本文主要介绍结构化支持向量机的理论知识。
文章目录
引言
可分的情况
不可分的情况
考虑错误
正则项
结构化支持向量机
分割平面法
用结构化SVM来做多分类和二分类
多分类SVM
二分类SVM
参考

在李宏毅机器学习——结构化学习(二)中我们说，我们要找到合适的框把目标给框出来。今天我们假设无法找到一个这样的框，但是能找到一个近似的，这个问题要怎么解呢。


下文会介绍这个问题的解法。
先看下本文的结构。

可分的情况
我们已经在李宏毅机器学习——结构化学习(二)中讨论了可分(Separable case)的情况。
在这里我们引入了margin。


现在有两份数据，一个用圈圈表示，另一个用星星表示。红色的代表是正确的结果。
所谓可分的意思是存在一个向量$\hat w$，如果我们把所有的点都对$\hat w$做内积，会发现我们能让红点(正确的点)内积结果比同份数据蓝色点内积结果都大一个值，记为$\delta$。

比如红色圈圈比所有蓝色圈圈的内积值都大一个$\delta$，红色星星也一样。

如果用数学描述就是这样：



如果是可分的话，我们就可以用下面的算法来找到我们要的参数$w$。


接下来证明下我们能找到这个向量$w$。

先看下结论，在可分的情况下，我们最多只要更新$(R/\delta)^2$次就能找到$\hat w$。
$R$是最大$\phi(x,y)$距离的最大值。在同份数据中，把所有的点都代入$\phi(x,y)$可以得到一个距离，任何两点距离了最大的值就是$R$。
所以这个算法需要迭代的次数与$y$的空间是无关的，即无论$y$有多少，只要$R$确定，迭代次数就确定。
证明如下：
$w$在每次发现错误点的时候就会更新。

把$w$的更新过程写出来，我们先看$w^k$与$w^{k-1}$的关系。
我们知道，它们一定有这样的关系：


某个正确结果形成的$\phi(x^n,\hat y^n)$减去某个错误的$\overset{\sim}y$形成的$\phi(x^n,\overset{\sim}y^n)$。
我们考虑的是可分的情况，先假设存在一个$\hat w$使得

正确结果的$\phi$与$\hat w$的内积比非正确结果的内积都要大一个$\delta$。
不失一般性，假设$||\hat w||=1$，假如我们找到了一个$\hat w$，它可以让我们的数据可分，那我们对这个$\hat w$做归一化，把它的长度变成1的话，它一样还是可以让我们的数据可分。
我们看下$\hat w$与$w^k$之间的关系，如果我们计算这两个向量的夹角，这个夹角记为$\rho_k$，我们会发现当$k$越来越大的时候，夹角越来越小。
我们可以计算$cos \rho_k$(夹角越小，$\cos$值越大)


在$(0,\pi)$之间，当$x$越来与小，$cos x$的值越来越大。
而

接下来看下$\hat w \cdot w^k$的值。


我们把右边的括号展开会发现



红线标出的这项一定大于等于一个$\delta$。这是来自我们的定义，现在$\hat w$可以让我们的数据可分的，那不管找到一个怎样的$\overset{\sim} y^n$，它与$\hat w$的内积一定比$\hat y^n$与$\hat w$的内积还小一个$\delta$。
所以红线的两项相减得到的结果是大于等于一个$\delta$的。

所以我们可以说 $\hat w \cdot w^k \geq \hat w \cdot w^{k-1} + \delta$。
因为初始$w^0=0$。
$\hat w \cdot w^1 \geq \hat w \cdot w^0 + \delta$。

所以 可以说 $\hat w \cdot w^1 \geq \delta$
而$\hat w \cdot w^2 \geq \hat w \cdot w^1 + \delta \cdots$
所以$\hat w \cdot w^2 \geq 2 \delta$
同理 $\hat w \cdot w^k \geq k \delta$
也就是看$cos \rho_k$的分子的话，它是不断增加的。

接下来我们再算下分母的$||w^k||$，因为我们已经假定$||\hat w||=1$。
如果我们发现$||w^k||$没有很快的增加，而这两向量的内积又增加的话，我们就可以知道$w^k$和$\hat w$是越来越接近的(随着$k$的增加)。

还是用这个$w^k$的表达式
$w^{k-1}$当成一项，剩下的当成另一项，把平方展开得到：


展开完后，首先红线标出的式子是一个长度，它一定大于0：



那右边的这项应该是什么样的值呢


上面这项是小于0的，在预测错误的情况下，$w^{k-1}$的方向和更新方向的夹角是大于90度的，所以小于0。

以上篇文章中更新$w$的图为例，更新方向向量是绿色的，预测错误的$w$是向上的那个，它们的夹角是大于90度的。


我们假设任何两个数据点的距离是小于$R$的。
所以
$||w^k||^2 \leq ||w^{k-1}||^2 + R^2$
于是我们可以得到$w^k$长度的上界。

我们知道：


而

以此类推


我们现在得到的结论是：



也就是说内积不断增加，而$w^k$的长度并没有增加的很快：


上式为什么是$\geq$呢，因为$||w^k||^2$取最大值，作为分母的话，就是使得整个式子最小，而分子又是取的最小值，所以上式是$\geq$。

随着$k$不断增加，这个$\cos$的值可能会增加，我们知道$cos$函数的值最大只能是$1$。
它的上边界就是$1$。也就是：


证明完毕。
从这个式子我们可以发现什么呢

如果$\delta$越大，那么这个式子的结果越小，也就是训练的越快。这很合理，如果红色的点与蓝色的点分得越开，我们训练的就越快。
但是在实际情况中我们很难找到正确和错误的结果是可分的。常见的都是不可分的情况，接下来我们就一起看下这种情况。
不可分的情况
在不可分的情况中，还是会有一些权值$w$比其他的要好。
假设没有任何一个向量可以让正确答案和错误答案被分开。但是在这些向量里面，

我们还是可以区分出好坏的。
假设我们有一个向量$w^{'}$，它把正确答案排在第二。

有另外一个向量$w^{''}$，它把正确答案排在最后一名。


虽然这两个向量都无法让正确答案的分数高过错误的，但是显然$w^{'}$是更好的。
那我们如何用式子来描述这种情况呢
我们可以定义一个损失$C$来评估$w$有多差，然后选择使得损失$C$最小的$w$。
$C$的定义可以是全部的$y$里面，可以让最大$w \cdot \phi(x^n,y)$的值，减去正确的$\hat y$所形成的值$w \cdot \phi (x^n,\hat y^n)$。



从图上可以看出，就是第一名的值减去正确的结果的值，这是很直观的。


对每份数据都有一个$C^n$，累加起来就得到了$C$。
我们来想下这个值有可能是负数吗，如果正确的红色框框排在第一名的话，那就变成自己减去自己，最小就是0了。
接下来如何找到一个$w$去使$C$最小呢

其实我们用梯度下降就好了，虽然这个$C^n$里面含有$max$。在maxout网络中我们已经看到过类似的解法：


虽然里面有个$max$，还是可以计算对$w$的梯度的。


当$w$不同的时候，选出来的$y$是不一样的。

可以把$w$所形成的空间想象成如下：

这个空间其实是被$max$切分成好几块的，比如$y ^ {'}$形成的$max$区域是下面涂蓝色的部分：

当$w$的值落在蓝色区域内，得到来的$y$是$y ^ {'}$。
在每个区域里面的函数是可以容易的算出来的，比如在蓝色区域的式子就可以写成这样：



其他区域也是一样的：



在每个区域里面都是可以微分的。

接下来就可以用梯度下降法来找到使$C$最小的$w$


假设更新$T$次，做随机梯度下降。


首先要知道落在哪个区域里面(上面应该是$arg\, max$,$max$只是一个最大值，加上$arg$才会返回一个$y$)，然后我们算出来是在$\overset{\sim}y^n$的区域里面。
所以算梯度就简单了

然后我们就可以更新$w$

如果把学习率$\eta$设成$1$，那我们做的就是structured perceptron。

就是下图这个算法：


考虑错误
我们刚才的损失函数，对所有错的情况都是一视同仁的。

但事实上并非如此，因为输出有很多种可能，在这些可能情况里面，有一些和真实的输出是很接近的。


比如正确的是红框，但是你的系统框出的是第二名的那个，其实它也是框在了练功春日上面，也是可以接收的。但是其他的错误框框就无法接受了。
所以不同的错误之间还是有差别的。我们应该把这件事情考虑进去。


比如说，框在樱花树上是很差的，不能接受的，但是第二名那个是可以接受的。我们希望框在樱花树上的分数很低，而第二名的分数要能和正确的结果分数接近。



如果你今天的权重能做到，使得结果能按照框框的好坏来排序，那么训练的结果是比较安全的。假如你的测试数据和训练数据有一些差距的话，虽然你得到的第一名不是正确的，但是至少能保证分数比较高的和正确的差距不是很大。
那如果把这件事情考虑到损失函数中去呢

正确的框框是红色的，这里有两个错误的框框。当错误的框框和正确的框框很像时，我们希望第二名那个错误的框框分数与正确框框的分数差距是比较小的；而错误很离谱的第三名那个框框和正确的框框分数差距是较大的。
现在的问题是如何衡量框框的好坏。其实这是与任务有关的，在不同的任务中你要想办法去定义它。
我们用$\Delta(\hat y,y)$表示正确的框框和其他框框之间的差距。

至于这个$\Delta(\hat y,y)$的式子需要你自己去定义，我们假设下面的讨论中定义如下：



$A(y)$代表$y$这个框框的面积。如果某个框框和正确的框框相交的面积越大的话，并且它们面积的并集也不是很大，我们就可以得到一个比较小的差距。
那有了$\Delta$以后，我们需要修改损失函数。

现在评判的方法是用$y$的分数$w \cdot \phi(x^n,y)$再加上$\Delta(\hat y^n,y)$，然后再减去 正确结果的分数$w \cdot \phi(x^n,\hat y ^n)$
我们会看看哪个$y$，它不止是分数大，$\Delta$也大，我们才会觉得它是真正的第一名。然后我们会拿这样的$y$来减去$\hat y$的分数。
可以想象成，如果今天有个$y$的$\Delta$值很大，我就希望它和正确答案的分数差距越大越好。



反之如果今天有个框框，它和正确的框框其实很像的话，那就算它们的分数没有拉开也没关系。


那看下$C^n$在什么状况下会得到0，当正确的$\hat y$所得到的分数，不仅是比其他的$y$还要到，而且都要大过一个损失函数所形成的$\Delta$值的时候，那你的$C^n$会是最小的。


这个$\Delta$所形成的差距就是margin。如果$y$是一个很不好的框框，那么它和正确答案之间的margin就会很大；反之是个可以接受的框框，那么它和正确答案之间的margin就要比较小。
我的理解是，这个$\Delta$相当于是一个惩罚项，它惩罚那些$\Delta$值很大的框。

现在加上了$\Delta$的这是式子如何用梯度下降去优化它呢


现在找的是让$w \cdot \phi(x^n,y)$加上$\Delta$最大，找出来的$y$记作$\overline{y}$	。
梯度的计算也变了




下面这个损失函数其实有另外一个观点来解释。


这个观点认为这个损失函数是训练数据上的误差的上界。
当你在最小化这个损失函数的时候，你是在最小化训练数据误差的上界。
最小化上界并不一定代表说误差会变小，但是是有可能会跟着变小的。


假设我们让上面这个内积最大的$y$，当做我们系统的输出。


那我们希望最小化的是$C^{'}$，我们希望能找到一个$w$，让$\hat y$与$\overset{\sim} y$之间的差距越小越好。
但是最小化$C^{'}$这件事情并没有那么容易，因为$y$可以是任何的对象；$\Delta()$可以是任何的函数。如果$\Delta()$比那些不可微分的函数更复杂，比如是阶梯状的，那么梯度下降法就无能为力了。 可以想象是对$w$做了一点改变，但是对$\Delta$一点影响都没有。


不过还好有我们刚才可以用来做损失函数$C$，它是$C^{'}$的上界，我们希望通过最小化$C$来达到最小化$C^{'}$的效果。


接下来证明$C^n$是$\Delta(\hat y^n,\overset{\sim} y^{n}$的上界。


首先看下面这项是大于等于0的。


因为$\overset{\sim} y^{n}$是可以让 $w \cdot \phi(x^n,y)$最大的$y$。
所以不管减去什么，一定是大于等于0的。

所以下式是成立的：


接下来换下右边这项括号里的内容：


然后我们说它是小于含$\max$的那项的



本来是计算$\overset{\sim} y$的$\Delta$加上$\overset{\sim} y$的内积，现在变成了找一个$y$，它使得$\Delta$加上内积最大。
既然这个$y$是$\Delta$加上内积最大的那个$y$，它一定大过$\overset{\sim} y$。



而包含$\max$的这一项就是$C^n$。


证明完毕。
其实还有别的方法可以让



成立。
刚才说的是这个：


还有下面这种方法：

正则项
接下来再加上正则项。
训练数据和测试数据可能有不同的分布，$w$如果和0比较接近的话，就可以最小化这种不匹配的影响。

在原来的损失函数中加上$\frac{1}{2} ||w||^2$。蓝色下划线这一项是要让错误的$y$和正确的$y$之间差一个margin。


前面绿色下划线这一项就是正则项，它希望$w$接近0。这两项中间会有一个$\lambda$，来调整这两项的差距。

那右边新的这一项如何做优化呢


优化过程如上。
接下来看看为什么今天讲的这个东西叫结构化支持向量机。
结构化支持向量机

最后我们用的损失函数是这样的。我们可以稍微修改下这个式子。


首先把右边的负号项移到左边。


把上面那项改成对所有的$y$，都有$C^n+ w \cdot \phi(x^n,\hat y^n)$大于等于


它们是一样的吗



我们今天要最小化$C^n$，那我们就说这一项

就等于$max$就好了。如果这一项比$max$大的话，就不是最小化的值。

(这里其实没有看懂，李老师讲的SVM不好理解啊)。
接下来把$C^n$移到右边


现在就变成这样



习惯上这里会把$C^n$换成$\varepsilon^n$



这个$\varepsilon^n$称为松弛变量(Slack variable)。
在下面这个等式中，定好$w$后，$\varepsilon^n$的值并没有直接决定，所以我们要改下描述。

现在要解的问题就变成了蓝框框出的问题：



当$y=\hat y^n$时



得到$\varepsilon^n \geq 0$。
所以可以重新描述下上面蓝框中的不等式。

如果听不懂的话，李老师说我们可以换个说法。


我们希望正确的框得到分数和错误的框得到分数中间差了个margin。如果它们的差越大，那么margin就要越大。
反之如果它们的差越小，那么margin就应该越小。
我们把红框和黄框的$\Delta$当做它们之间应该有的差，如果它们越相近，那么margin就应该越小。
所以我们可以列出一个限制条件，说我们今天要找到的$w$应该满足以下条件。


因为我们有非常多个黄框，所以不等式也有非常多个。所有不等于$\hat y$的$y$都会有一个不等式。
但是有一个问题是你可能找不到一个$w$让上面的不等式都满足。
所以我们把margin改的小一点，把margin都减去一个$\varepsilon$


为了把margin变小，这个$\varepsilon$要是大于等于0的。



因为margin变小了，也就说要找的$w$的限制被放宽了。所以叫$\varepsilon$为松弛变量。
当然限制不能放得太宽，可以想象说今天$\varepsilon$是无穷大，那么所有的margin都变成负值，那么随便找到一个$w$都会让这些不等式被满足的话，这个就不是我们要的东西。
我们希望放宽的幅度必须是最小的，也就是说我们希望$\varepsilon$的值能越小越好。

假设我们今天有两笔数据，$x^1$和$x^2$。对$x^1$来说，我们希望正确的减掉错误的要大于它们之间的$\Delta$减掉$\varepsilon^1$。对所有的$y$除了$\hat y^1$以外，这些不等式都成立。

接下来有另外一笔数据$x^2$，我们希望正确的减掉错误的一样大于$\Delta$减掉$\varepsilon^2$。
在满足这些不等式的前提下，我们希望这些$\varepsilon$的和是最小的。
这样得到的式子就和刚才推导出来的是一样：


这个东西和SVM的关系是什么呢，它和SVM的式子其实是大同小异的。它们都是二次规划问题。
现在唯一的问题是限制条件太多了，接下来的问题是，在限制这么多的情况下应该要怎么办。且听下节分解。
分割平面法
现在的问题是，我们有一个参数空间，由$w$和$\varepsilon$所形成。

参数空间上面的颜色代表需要最小化的$C$值：




在没有限制的情况下，青色星星这一点是最小值。但是我们有大量的限制条件。


这些限制告诉我们，在这个空间里面只有中间那个灰色区域是符合我们所有的限制的。


我们要在灰色区域中找最小值，我们得到的结果就是上图青色星星那一点。限制的问题是如何找出这个灰色区域。
虽然这里的限制很多，但是大部分的限制都是冗余的。



比如说我们看这两条红色的限制，我们只要有这两条红色的限制，就能决定大部分灰色区域的形状。这样下面绿色的这条限制，其实是不会对结果有影响的。



所以我们可以优化下限制条件表达式，不需要穷举所有的$y$了。我们只需要从有影响的限制条件集合中去取。



这个小部分的有影响的限制条件集叫工作集(working set)，这里用$A^n$表示。
如果有能找出这样的工作集的话，在优化的时候我们只要考虑$A^n$里面的$y$。
现在的问题是如何找到这个工作集。我们通过迭代的方法来找，每次找到一个元素加到工作集里面。
一开始为每个样本初始化一个空工作集，然后根据这个工作集去解下面的问题：



我们考虑工作集里面的$y$，假设我们根据这个工作集解出一个$w$后，我们再用这个$w$去重新检查下，增加新的元素到工作集。此时工作集就不一样了。然后我们再用这个工作集去重新解上面的QP问题。
这样又可以得到不一样的$w$，又可以找到新的成员添加到工作集。就这样一直循环。
我们用图示的方式来解释下这个过程是如何运作的。

先假设初始化样本$n$的工作集为$A^n=null$，表示它是空集合，也就是没有任何限制；
假设我们在没有限制的情况下，得到的结果是蓝色的点。


找出这个蓝色的点后，我们需要看看有哪些限制是没有被满足的。比如下图这些红色的线都没有被满足


虽然有很多没有被满足的限制，但是我们只选择没有满足的最严重的那个。假设我们找到的是下图红线那个，并记这个限制为$y^{'}$


我们就把这条限制加到工作集里面，现在工作集就有一个成员了。
根据我们现在工作集唯一的成员，它告诉我们说，最小的值是下面蓝色星星


接下来我们以蓝色星星作为结果，看还有哪些限制没有被满足。此时还有很多，比如新的红线就没有被满足


再把这条没有被满足的限制(就是上图没有经过蓝色星星的那条红线)加到工作集中。我们就根据现有的两条限制，得到一个新的值：


接下来要继续检查还有哪些限制没有被满足，比如说下面这条新的线就没有被满足。


再把这条新线加到工作集中，现在工作集中有3条线了，我们就根据这3条线，得到一个新的最小值。


于是就找到我们要的解，就结束整个算法

上面有个问题就是如何寻找没有满足的最严重的那个限制。



我们先来看下限制的表达式，当一个限制被违反(violate)的时候，给定$w^{'},\varepsilon^{'}$,就是说



但是不满足(违反)的限制可能有很多个，我们要定义一个违反的程度:


就是不等式右边这一项减去左边，它大的越多就越违反。

我们还可以简化下这个式子，对所有的$x,y$来说，$\varepsilon^{'}$是一个固定的值，它与$y$没有关系，而$w^{'} \cdot \phi(x,\hat y)$也不影响我们计算。因此可以简化为：



最后违反程度最严重的$y$就是可以让上式的值最大的$y$：


我们现在来看下这个分隔平面法的样子：



这里用$\overline{y}$表示当前找出的违反程度最严重的限制。知道我们无法找出一个新的$\overline{y}$放入工作集时，整个算法就结束了。
用结构化SVM来做多分类和二分类
多分类SVM
假设有$K$个类别，有$K$个权重，它们组成一个权重向量。



$F(x,y)$就可以写成


这个$x$就是我们要去分类的数据，用向量表示。

如果我们用结构化SVM的是，一般$F(x,y)$是长这样的：



那和下面这个公式是同一个吗



其实它们是同一个。我们可以把$w$用列向量的形式表示，$\phi(x,y)$写成这样：



在$\phi(x,y)$，$\overrightarrow {x}$放的位置与$y$的取值有关，假设这里$y=8$，我们把$\overrightarrow {x}$放到这个位置。



因此这两个式子是可以一样的。


那推断类别的时候怎么做呢，就是穷举所有可能的$y$，看哪个的$w^y \cdot \overrightarrow {x}$的取值最大。因为类别是有限的，所以这里的穷举很容易。
解下来就做一下训练。此时的限制条件是有限的。所以也用不着分隔平面法。



那有多少个限制呢，假设有$n$份训练数据，每份训练数据都有$K-1$个不正确的$y$。因此整个限制的数量就是$N(K-1)$。
根据上面$\phi$的形式，我们可以把$w$乘进去：



得到上面两项，然后代入限制条件公式中：



那这里的$\Delta(\hat y^n,y)$是什么呢，这个其实可以自己定义。可以说如果我们预测的类别和真实类别不一样就是1，一样就是0。
但是可以考虑另外一种问题，就是某种类型当成另一个类别是比较严重的，而当成其他某种类别是不严重的。
比如说$y$有狗、猫、公交车和小汽车。



然后我们就可以自己定义，本来类别是狗，我们预测的是猫，相差就不是很严重；而本来是狗，预测的是公交车，相差程度就很大。


这样在训练的时候，我们的模型就会尽量避免把狗识别成公交车。
二分类SVM
二分类其实就是多分类中的$K=2$而已。



本来我们的限制是写成这样的，但是因为我们只有两个类别。我们就可以把正确答案是类别1，弄错成类别2与正确答案是类别2，弄错成类别1的$\Delta$不一样。


我们这里假设只要弄错$\Delta=1$。今天我们$K=2$，你会发现只有两种情形：

要么它属于类别1


要么它属于类别2



我们可以假设$w^1 -w^2 =w$而$w^2 - w^1 = -w$，代入上面就可以得到。



参考

李宏毅机器学习

本文随着学习的积累会不断更新，逐渐形成一个索引。


1、机器学习基础

1.1什么是机器学习

1.2为什么要用机器学习

1.3使用机器学习的先决条件

1.3.1计算能力



1.3.2海量数据



1.3.3算法

1.4机器学习的应用场景

1.5利用机器学习的步骤

2、机器学习算法

3、机器学习案例