春节充电系列：李宏毅2017机器学习课程学习笔记23之结构化学习-Structured SVM（part 1）

【导读】我们在上一节的内容中已经为大家介绍了台大李宏毅老师的机器学习课程的Structured learning-linear model，这一节将主要针对讨论Structured learning-Structured SVM。本文内容主要针对机器学习中Structured learning-Structured SVM的Separable Case,proof of Termination以及Non-separable Case 分别详细介绍。话不多说，让我们一起学习这些内容吧

课件网址：

http://speech.ee.ntu.edu.tw/~tlkagk/courses_ML17_2.html

http://speech.ee.ntu.edu.tw/~tlkagk/courses_ML17.html

视频网址：

https://www.bilibili.com/video/av15889450/index_1.html

李宏毅机器学习笔记23 Structured learning-Structured SVM（part 1）

今天我们介绍Structured learning-Structured SVM，对于解决Structured learning 的问题都可以分为三个问题，第一个问题就是Evaluation.我们要求F(x,y)需要是linear的，不然后面的讨论都不成立。

第二个问题inferenece寻找y使得F(x,y)最大

而对于第二个问题前人已经针对不同的应用提出了不同的解决方法，故不是我们的讨论重点

第三个问题就是Training，使得正确的(x,y)使得F(x,y)最大。第三个问题是今天我们讨论的重点

今天要谈论主要分为如下八个部分

1.Separable case

对于Separable case，我们想要求得一个w使得正确的F(x,y)比错误的F(x,y’)总大于一个常数。

所采用的算法也很简单明了，上一次笔记我们已经介绍过了

2.Proof of Termination

下面讲述这个算法的数学证明

W每次在看到一个错误的时候更新一次，并且假设w的模为1

W是向量，如果算法收敛的话，w和正确的w’的夹角会越来越小

我们将wk模的平方展开，因为我们之间假设了两个特征向量的距离小于R，并且展开式的第三项小于0，所以我们得到了一个不等式。

将得到的不等式带入cos的式子，最终我们得到了算法的收敛次数k是有上限的

3.Non-separable Case

Separable case一般在现实生活中很难找到，所以我们要讨论non-separable Case。虽然我们还没有讲non-separable case，但是从下图中我们可以直觉感觉到w’比w’’好

我们可以自己定义cost function，例如定义cost function为最大的F(x,y’)和正确的F(x,y)之间的距离。

这里我们可以用Stochastic Gradient Descent去最小化C

由于w不同，对应的y也不同。所以W空间被分为几部分。那怎么微分呢，就分区域微分

这样我们就可以用Stochastic Gradient Descent了

然后对于不正确的y我们也希望能够区分它。

明显下图右边的结果更容易让人接受

那我们如果衡量不正确的y呢

例如在人脸探测我们可以定义正确的y和不正确的y’交接的面积△

然后将正确的y和不正确的y’交接的面积△ 加入cost function里面

依然使用梯度下降方法，得到最终结果

请关注专知公众号

• 后台回复“LHY2017” 就可以获取 2017年李宏毅中文机器学习课程下载链接~