[机器学习入门] 李宏毅机器学习笔记-27（Structured SVM part 2；结构化支持向量机 part 2）

PDF	VIDEO

---

Structure SVM

接上篇

这里写图片描述

Regularization

这里写图片描述

---

番外篇：
当我坐在杭州梦想小镇的咖啡厅学习到此处时，一位中年大叔说很喜欢我的形象希望给我拍照，我一愣心想这大叔真是有眼光啊，咱这形象终于得到了艺术圈的认可，没想到大叔满面春光地翻出一个巨大的相机包，摆满了各种镜头，看这架势仿佛自己要登上男人装封面了。大叔笑眯眯地对我说，你继续工作就好。OK，it's fine，我的machine learning正在呼唤我,坐怀不乱学习正是我们老柳家的传统。平静，平静，再平静…不好意思我没平静地下来，大叔的快门四面八方地咔嚓，咔嚓就咔嚓吧，奇怪咱这颜值难道不是随便角度都能成大片吗？可是大叔一边拍一边皱眉头叹气…wtf，就不能赞美我一下下吗，还嫌我黑用手机闪光灯给我补光，二十多分钟后终于结束了，总之还是挺nice的哈哈哈。好吧，你若问我为什么要说这么多废话，因为我实在不知道拍照敲键盘时该写点啥，不如做个即时的心情记录吧哈哈。

---

收住，回归正题。

这里写图片描述

---

Structured SVM

好了，那么接着来看究竟SVM是怎么体现的。对已知的cost function做两个变换，蓝绿两个框虽然是不一样的，但我们有要minimize C的条件，所以Cn正好等于minimize的值就好，就可以认为两式一样。

这里写图片描述

所以下图蓝绿两框的find任务是等价的，习惯上会把Cn换成篮筐Slack variable表示。

这里写图片描述

所以黄框就是我们求解的问题，接着利用 y = y^ 时的特殊情况，对for all y 做一下变换。

这里写图片描述

对于上面这个变换还有一个更直观的理解，如果两个答案的差越大，margin越大，反之越小，即为△,所有不等的情况都能写一个不等式。

这里写图片描述

寻找一个w满足所有不等式，很可能是一个空集，所以我们要把margin变小限制放宽，而且放宽的应该是恰到好处的，方法就是减去一个 ε （大于等于0）。

这里写图片描述

但是并不能无限放宽限制，那样margin都成负的了，秉持恰到好处的原则，ε要越小越好。在满足下面不等式的情况下， 希望ε的sum是最小的。这样得到了原式子，Solve it by the solver in SVM package。

这里写图片描述

---

Cutting Plane Algorithm for Structured SVM

上述问题有一个很大的困扰，constraints太多了，几千万几亿怎么办？先看一下我们究竟要解决一个怎样的问题，在三维坐标系中，constraints给划定了很多区域，规定了只有固定区域才是可行的，这就给寻找最小值增大了难度。

这里写图片描述

于是，Cutting Plane Algorithm能帮我们解决这个问题，颜色的深浅代表值的大小，如果成功构建，就很容易找到那个最小值。

这里写图片描述

constraints的特点是，冗员很多，真正起作用的不多，如果我们有办法找到working set，该问题就是可解的，只要考虑working set中的y就可以了，然后即得到一个w，用这个w找一些新的成员加入working set，然后再循环解决。

这里写图片描述 这里写图片描述

怎样用这个w找一些新的成员加入working set？

这里写图片描述

找出最不满足的constraints。

这里写图片描述

通过它们的交点，不断找出最小值，和最不满足的constraints，循环。

这里写图片描述

怎样找出最不满足的constraint呢？

这里写图片描述

好了，让我们看看整体运作起来是什么样子的。
QP：Quadratic Programming

这里写图片描述 这里写图片描述

Example：

这里写图片描述

加入一组working set

这里写图片描述

现在就有了一个具有两个constraints的QP问题，解出后更新w。

这里写图片描述 这里写图片描述 这里写图片描述

本节未完待续