李宏毅老师Structured Learning课堂笔记 以及在 自然语言句法分析上的应用
每次写博客，都是我最开心的时候，因为每次决定写博客都是我觉得学到了非常重要的知识点。这篇博客，我会来谈论一下Structured Learning 以及在句法分析上的应用，Structured Learning 应用很广泛，只要掌握了这一思想，我们自然就会去应用它，我们的毕业论文方向是信息检索，我也会用你Structured Learning 方法来看一下效果会怎样。
在这篇博客中，我们会深入探讨Structured Learning 的各个细节，如果仅仅是想应用它的话，可以把中间探讨过程略过，但是如果可以，还是耐心看完，因为我都是从初学者角度去解释它，针对自己踩过的坑重点讲解。在这里，我用的资料都是来自李宏毅老师的PPT。
在大多数机器学习教材里面，你会发现很少讲Structured Learning的，我也是在看cs224d课程的时候，在recursive neural network中提到句法树学习里看Structured Learning 一脸懵逼，到处找资料才学习到Structured Learning 。我们就通过一个问题来引出接下来我们要学习的内容。
我们都都知道在分类问题中，我们会给一个训练数据，标记好了类。如果让你用一个模型来解决它，你会怎么做？ so easy,有很多方法，knn,svm朴素贝叶斯，决策树等等哪个不行啊，这个问题我们可以看到，它的输出可能是数（每个类都用数字来标识）。现在我们再来问一个问题，我们知道在自然语言里面有句法树分析这样的一个重要任务，给定了一组训练数据，让你来判断学习这个树结构，这个时候你会用什么方法呢？ 这个问题，就是属于Structured Learning 的范畴。
首先我们来看看关于Structured Learning 的框架
如图所说，我们给一函数F,对于输入X和标记Y,我们都会输出出一个实数R，这里的Y是一个抽象的概念，对应到我们句法分析上代表树的结构。输出的实数R就是代表我们的X和Y有多匹配，匹配度越高，R的值就越大。然后我们测试集上就是寻找一个能F(X,Y)的输出值最大的Y.
写到这里，有的人可能会觉得F(X,Y)的表达很奇怪，而且整个式子有一种似曾相识的感觉，是不是很像机器学习里的朴素贝叶斯学习方法？ 我们只要把F(X,Y)换成P(X,Y)就可以了。 这样做其实是可以的，我们之所以用F(X,Y)，因为它是更一般的表达式，P(X,Y)是F(X,Y)的一种形式，我们之所以用F(X,Y)是因为，不是在任何情况下都一个用P(X,Y)来表达。我们就用F(X,Y)抽象的表示X和Y匹配的程度，具体的表达形式，还是需要根据你要处理的具体任务来定，这个我们会在后面讲到句法分析的时候讲解。
我们学习的Structured Learning 的时候，我们主要要解决这三个问题。
现在我们来看看第一个问题，F(x,y)是什么东西
那个和w相称的函数叫特征函数，这个在传统方法里是人工标注的，现在一般都是用深度学习来表征。（对于这个，我不想详细解释了，如果有问题可以私信，或者自己看看条件随机场，和最大熵模型，里面也都有关于特征函数概念），可以举一个例子就是，在我们自然语言里面，可以用向量表示词，而这个词的各个维度权重就是对应某个特长函数的值（就解释这么多吧，这些都是基本概念了）。
再来看看第二个问题，我们怎么来找到最大值对应的y，其实F(x,y)的表达已经知道了，用穷举的办法就可以找到啊，所以寻找方法还是基于已经知道F(x,y)的表达的基础上，所以为了方便理解，你可以想想朴素贝叶斯里面是怎么寻找最大y了。在这里，我们就假定我们已经知道了最大的值。
第三个问题是我们要重点展开讨论的，我们怎么去学习F(x,y)，其实就是学习里面的参数w.
用语言来直白描述就是，我们希望学习这么一些参数w，使得用参数w乘以正确的正确标记样本的特征函数，他们的值要大过于参数w诚意错误标记样本的特征函数。下面举例李宏毅老师在课上讲的例子
这个是关于人脸识别的task，不同的人脸识别位置会对应不同的特征函数，我们希望正确的人脸识别乘以w,可以获得更高的分数。
解释到这里，这种方法我们是不是很熟悉的呢？ 像不像SVM的精神，有征服样本，学习一些参数w,使正样本和负样本分隔开来。其实跟道理都是一样的，所以这种方法有一个统一的名称叫max margin method，我么们也会在后面看到，我们在structured learning 里面，最终是把它的推导方式转化到svm的问题。
这个是我们的更新参数w的算法，至于这个算法为什么会收敛，会在后面证明。
具体的算法举例如下图
图中的w向量是我们最终要学习的向量（在这里w向量是二维，这个只是我们为了方便可视化做的假设，在我们实际应用中，我们的w向量维度往往很大）。
以上就是我们更w的方法。我们在自然语言句法分析上学习参数w的时候，并不是用这样的方法，我们是用深度学习的方法来更新w.
接下来，我们还要做进一步的工作，就是证明这个更新算法它是收敛的。
首先我们要假设，样本可分割性。就是假设存在函数F(x,y)可以让正确的样本分数最高。
以上就是关于算法收敛的证明。
以上我们讨论的是样本可分的情况，事实上我们在实际应用中更多的是碰到样本不可分的情况，这个时候我们还需要用别的方法。
所以在这里我们就定义一个cost function
以上我们很好的解决了怎么让正确标记的F(x,y)他的值更大，但是我们把所有错误样本都是同等对待，为了让我们的模型更加robust，我们还要对错误标记的label进行打分，让那些更接近正label的获得分数更高一些。所有我们引进来 error function
相应地，我们地梯度方程也要修改一些
从另一个角度来看看 这种方法
这里我提一下slack variable rescaling, 因为我们之前地cost function 是把delta 和 特征函数地差值加起来，但是有它地不合理性，因为delete 和特征函数差值可能不在一个scale上，他们相加起来有时候是没意义地，针对这种情况，用 delta乘以 他们地插值相对来说更合理一些。另一方面，这样做地话delta值很大地时候，他地cost function 也会变大，相反，delta比较小地时候，他地cost function 值会缩小。
在regularization里面，我们是加了一个w的优化，我们希望w更小，这样受到错误样本的y影响就会减少，模型也会更加robust。
接下来我们来引出structured learning
在这里我们能看到转换
从数学意义上来讲，这两个式子并不是严格意义上的等价，因为上面的式子他表达的是最大值，是一个数值，而下面他是一个大于号，表达是一个集合，但是在我们这个方程里面却可以这样转换，因为我们要minimize C,也就是说我们要在集合中找最小的值，也就是第一个式子中max值了。这个是一个细节，就这么提一下。
接下来，我们再做进一步的变换
到这里是不是有很熟悉的感觉，这个就有点像SVM里面软间隔模型了。
再这一步做的唯一变换就是把 y 等于 y head情况单拿出来，形成一个大于零的条件。
那现在问题是我们怎么去解决这个方程，这个方程有太多的限定的条件，我们有没有好的办法呢？ 我们要用的方法是cutting plane 方法。
接下来我们就来介绍一下cutting plane的方法
如图所示，我们要对cost function进行优化，就是要在阴影部分的范围内进行优化。
cutting plane的本质思想是这样的，虽然我们有很多限定条件，但是真正构成阴影部分的线就那么几条，我们就是想把这部分线给找出来。
这个是算法的详细描述。
用大白话来描述就是，我们先initialize N个空的集合，这个N对应的是样本的集合，这个N个集合分别代表N个限定条件。我们最开始是initialize 参数w(比如初始化化为零)，给定了参数，我们就有了新的约束条件，我们在这些约束条件中寻找most violate的限定条件(怎么找，下面会详细谈一下)，找出了most violate条件之后，更新集合，在这些条件下我们再求一次最优化w,更新了w之后，我们再寻找most violate的条件，如此迭代，一直到我们的集合不再更新为止。
现在我们来谈一下怎么去找most violate的条件的问题。
本质的思想就是我们给定w 和柯西，我们寻找最违的限制条件，如图所示其中y是我们要求的变量，所以最终就变化上图中最后的式子。