机器学习中大部分问题考虑的输入都是一个向量，输出是另外一个向量。而现实生活中的问题往往比这复杂地多，输出可能是一个sequence，list，tree或者bounding box。如何处理这种结构化的数据呢？而这种结构化的数据在现实生活中又比比皆是。想语音辨识(Speech recognition，输入一个声音信号，输出一段文本)，翻译(Translation，输入一段文本，输出一段文本)，目标检测(Object Detection，输入一张图片，输出bounding box)，摘要生成(Summarization，输入一长串文本，输出摘要)，检索(Retrieval，输入是一个关键字，输出是一个list)。  

Unified Framework

  听起来比较难做，其实是有一个通用的框架的。我们知道机器学习算法通常分为两步：训练和测试。这个通用的框架也分为两步：   1.Step 1: Training：在这里我们是希望寻找到一个函数F （大写的),输入是$(x,y)$，输出是一个分数，用于评价这个x 和这个y 究竟是有多匹配，表示为：$\mathrm{F}:X\times Y\to \mathrm{R}$。   2.Step 2: Inference (Testing)：测试阶段也被称为推理阶段，假设我们已近找到 Y ，在测试的时候，给一个新的 x ，我们去穷举所有可能的 y  (可以理解为穷举所有可能的标签)，一一代进大写的 F ，看看哪一个 y  能够使得其输出分数最大：y~​=argmaxy∈Y​F(x,y)。y~​ 就是模型辨识的结果。   上述过程其实就是$GAN$的思想，不过是用Deep Learning来做这样一件事情。  

• 举个例子：假设我们现在要做目标检测，输入是一张图片，输出是一个bounding box。

  在训练的时候，给定图片和bounding box，(也就是输入是图片和bounding box) 如果比较匹配的话分数就会很高，如果不匹配的话，分数就会很低。   在测试的时候，给定一张从来没有见过的例子，穷举所有可能的bounding box，看看哪一个bounding box能够拿到最高分，能拿到最高分的bounding box就是我们最终的输出。  

Statistics

  上述的说法如果在统计学中描述就与贝叶斯推论联系起来了。同样分为两步：  

1. Step 1: Training：训练过程评估$(x,y)$一起出现的机率，也就是联合概率$p(x,y)$，范围是0到1：$\mathrm{P}:X\times Y\to [0,1]$。
2. Step 2: Inference (Testing)：测试的时候，是去计算条件概率 $p(y|x)$，给定 x 的情况下，哪个 y 的概率最高，作为模型的输出结果。

    给定x ，计算$P(y|x)$的概率，哪一个y 的机率最高，它就是我的答案。$P(x)$ 对我们最后找出的 y 没有影响，因此可以得出上述结果。与之前的方式一样，最终也是算 x 与哪一个 y 的联合概率分布最高，就是其结果。   这种概率的方法需要穷举所有的 y ，这一步有时候会变得很难。单这种方式更容易理解，可解释性也比较强。与这个算法比较类似的有能量模型(Energy Model)，图模型(Graph Model)也是说的一样的东西。    

• Energy-based Model：https://cs.nyu.edu/home/index.html

 

求解

  现在我们大概知道了算法的大体思想，接下来我们需要看看如何求解这个模型。如果我们要解这个通用的框架，我们需要计算三件事：  

1. Evaluation：$F(x,y)$ 长什么样子？比如目标检测中输入是图像和bounding box，这两样东西组合起来应该长什么样子？
2. Inference：在推理过程中需要计算：y~​=argmaxy∈Y​F(x,y)，如何解argmax这个问题？如果是做目标检测求上述结果，我们需要穷举所有可能的bounding box。
3. Training：在训练过程中如何找到能够使得样本集中的样本满足正确标签的$F(x,y)$能够大过其它的情况？真的能够训练出来吗？

  这三个问题也就是HMM (Hidden Markov Model)需要解决的三个问题。   那这种structured learning与DNN有什么区别；以手写数字为例，我们输入一张image，得到输出向量$N(x)$，标签是一个十维的向量 y ，把 y  与 $N(x)$ 算交叉熵(cross entropy) 得到$CE(N(x),y)$。将其取负号就是 $F(x,y)=-CE(N(x),y)$。在测试的时候，就是穷举是个可能的标签(十个one-hot向量)，看哪一个标签能够使得$F(x,y)$ 最大。所以DNN是Structed learning的一个特殊例子。这里只有十个label，我们是可以穷举的。   说回来我们如何解决上述三个问题呢？  

1. 对于如何表示$F(x,y)$这个问题，可以采用多个characteristic线性加权组成。即先将$(x,y)$用characteristic表示为$\varphi (x,y)$，在将多个这样的characteristic线性加权：F(x,y)=w1​ϕ1​(x,y)+w2​ϕ2​(x,y)+⋯ ，参数wi​为待学习参数。那$\varphi (x,y)$在做一件什么事情呢？以目标检测为例，可以想象成在bounding box中看看某些特征出现了多少次这样。那这样的特征又如何来找呢？可以用CNN的方法来找，也就是CNN抽取bounding box里面的图像特征。因为$F(x,y)$是线性的，所以一般期望$\varphi (x,y)$抽特征的能力比较强。
2. 测试部分(推理部分)：对于找一个 y 能够满足y~​=argmaxy∈Y​w1​ϕ1​(x,y)+w2​ϕ2​(x,y)+⋯，这一部分我们先假设能够求解(之后再说)。
3. 训练部分，也就是需要将F ( x , y ) 这个函数训练出来，也就是对所有的训练数据(x^r,y^​r)，正确的数据标签对应的w⋅ϕ(xr,y^​r) 要大于任何错误的情况 w⋅ϕ(xr,y)，即w⋅ϕ(xr,y^​r)>w⋅ϕ(xr,y)。那对于分类数目很多的情况(y 有很多)，如何来找到参数w 呢？可采用下面这个算法：

    可以看出算法的思想就是先基于当前的 w 找其最大的 y~​，如果 y~​ 与真实标签不符，则更新 w 重新找，直到 w  不再更新。  

Proof of Termination

  假设我们已经解决了前两步，也就是知道如何抽$\varphi (x,y)$，知道如何解argmax的问题，考虑第三个问题，求解参数w 。   那上述求解$w$的过程真的会收敛吗？因为里面有穷举所有的label这一步，看起来会比较难处理，并且收敛性好像难以直观理解。   由上述推导可知 w 的更新公式为：     假设存在向量w^，对所有的训练样本(xn,y^​n)满足以下关系式：     不失一般性假设 $||w||=1$。   现在的问题就转换到 w^ 和 wk 之间的关系求解。我们知道当 $k$ 越来越大时，w^ 和wk 之间的夹角ρk​是会越来越小的，cosρk​越来越大，即的值越来越大，对分子部分展开：     由于，上述公式是个递推公式，所以可以得到     可以看出随着 k  的增加，cosρk​的 low bound 也在不断地增加。而cosρk​≤1，因此可以看出$k$并不会需要迭代无穷次。   中如果 $\delta$ 很大，迭代次数 k  就会越小。这件事情也很直觉，就是正确的样例和错误的样例距离很远，那迭代就会很快。那我们现在想要迭代快一点，就需要有意把$\delta$变大，如何来做呢？   先回顾一下$\delta$的定义：     因此我们如果把抽特征的$\varphi ()$都乘以2会不会使得$\delta$变大两倍呢？其实不会，R 也会变大两倍，因此不会变快。  

不可分情况

  wk更新前与更新后可能并不会使得其在数据集上做到：正确的数据标签对应的w⋅ϕ(xr,y^​r) 要大于任何错误的情况 w⋅ϕ(xr,y)，单更新后如果能够做到更多数量的样本满足上述要求呢？是不是说明了算法的效果变好了，单依旧不是完美的情况。单也是我们希望看到的，由此定义一个损失函数(Cost Function)，它用来评估w 有多不好。   损失函数可定义为：当前的样本最高的得分与正确标签的得分的差距：     对于所有的样本有：   这里取max也与上面第二问取argmax对应，如果取前三名的平均减去正确标签也可以，但是计算第二名第三名的得分就更困难了。   那现在问题就变成了如何找一个 w  来最小化cost C 。能不能用(Stochastic) Gradient Descent的方法来做呢？损失函数C 中含有max这一项，如何来求其梯度呢？   对于下述损失函数：     最难处理的就是max这一项，我们采用分段函数的思想，w 取值某块区域的时候取max得到y′，w 取值另一块区域的时候取max得到y′′，这样我们就可以对每一个由w 分割开的region进行微分：     到此我们就可以找到线性不可分情况的求解点。  

Considering Errors

  我们应该如何定义准确值和错误值之间的差距呢？ 常用的做法有以下几种方法：  

1. Error Function：定义正确值和错误值之间的差距。

      对于上述公式依然可以求梯度，然后更新参数w ，与之前的不同在于argmaxy​找出来的的y 是有可能不一样的。当y 能找到的话，之后的事情就是一样的，将其划分为不同的区域，然后做梯度更新。最优化这个新的cost function其实就是在最小化训练集样本上的upper bound。     直觉上考虑的是如果预测标签与实际标签差距很大，那这个差距就会被放大，这么做的原因就是考虑  

Regularization

  我们知道w 越接近0就越能减小mismatch带来的影响，所以我们这里在原本的 C 的基础上进行修改，添加了一个1/2⋅∣∣w∣∣2这项，令w 趋于0，就可以减小mismatch带来的影响了。    

Structured SVM

  回归一下原问题：期望寻找到一个参数 w ，它能够最小化 C ：     等价于：   期望寻找到一个参数 w ，它能够最小化 C ：     Cn 可以用 εn 代替，称之为松弛变量(Slack variable)。(本来是w 的值确定下来Cn也会定下来，这里我们不考虑这一点，把εn 也作为一个待优化参数)。   此时问题又转变成了：   期望寻找到一个参数 w ，ε1,⋯,εn它能够最小化 C ：     对于任意的n 和y 有：     上述问题就跟SVM一样，转换成了一个凸二次规划问题。   现在的问题就是约束(constraints)太多了，在这么多约束的情况下如何来做呢？  

Cutting Plane Algorithm

  虽然参数空间中有很多约束(constraints)，但是大部分的约束对我们找的结果是没有影响的。(Red line是我们需要的两个constraint，而例如绿色的constraint即使忽略，也不会对结果产生影响)。     如果我们能够找到只与结果有关的约束项(work set)，我们的求解就会比较容易。约束条件可以改为对于任意的 n 和 y∈An有：     现在的问题就是我们如何来找到这样一个working set An? 我们可以通过迭代的方法来做。  

1. 为每一个样本初始化一个空的working set An。
2. 我们只需要考虑working set里面的y ，求解上述约束最优化二次问次，能够求解出一个新的w 。
3. 依据w ，重新找一个working set成员，这样working set就不一样了。（每次找没有满足约束最严重的那一个约束，将其添加到working set中，如何来找到最严重的这一项呢？不满足约束的条件可表示为：w′⋅(ϕ(x,y^​)−ϕ(x,y))<Δ(y^​,y)−ε′，因此当Δ(y^​,y)−ε′−w′⋅(ϕ(x,y^​)−ϕ(x,y))值最大的时候就是最难搞的那个约束，也就是求解哪个y 对应的约束，找到y 就找到了对应的约束。对于y 来说，ε′和w′⋅ϕ(x,y^​)是不变项，因此我们需要求解的y 为argmaxy​[Δ(y^​,y)+w⋅ϕ(x,y)] 。
4. 再得到一个w ，再重新找到一个新的working set，不断地循环。

    上述算法用于分类问题也是一样，甚至用DNN去替代上述抽取特征的步骤也同样是可以的。  

Sequence Labeling Problem

  Sequence Labeling Problem说的是我们需要找一个函数f ，它的输入是一个Sequence，输出也是一个Sequence。  

Hidden Markov Model (HMM)

  隐马尔可夫模型(Hidden Markov Model,HMM)大体上可以分为两步：1. 基于语法生成一个合法的词性序列(generate a POS sequence based on the grammar)；2. 在第一步生成的词性序列的基础上，基于字典生成一个句子序列(gengerate a sentence based on the POS sequence;based on a dictionary)。  

1. 语法可以假设成一个Markov Chain，那语法长什么样子呢？假设我们现在要产生一句话，那句首的第一个词汇有0.5的概率是一个冠词，0.4的概率是一个专有名词，0.1的概率是一个动词这样。第二个动词就在第一个词汇之上再产生下一个词的概率：

      基于第一步，我们可以计算出一个词性序列的概率。  

2. 基于这个词性序列，我们可以计算出在第一步生成的合法词性序列的条件下生成对应句子的概率：

      假设产生词性序列的概率为$p(y)$，那么在词性确定的情况下产生句子的概率为$p(x|y)$，两者同时发生的概率则可以表示为：$p(x,y)=p(y)p(x|y)$。  

• $p(y)$可表示为P(y)=P(PN∣ start )×P(V∣PN)×P(D∣V)×P(N∣D)​。
• $p(x|y)$可表示为$P(x|y)=P(\mathrm{John}|PN)\times P(\mathrm{saw}|V)\times P(\mathrm{th}e|D)\times P(\mathrm{saw}|N)$

  将其一般化，可将第一步的概率称为转移概率(transition probability)，第二步的概率称为输出概率(emission probability)。  

• transition probability：

   

• emission probability：

    接下来我们就需要从训练数据中去获取这些概率值，最简单的方法就是直接统计。     假设我们现在要做一个词性标注的问题，就是给定句子序列x ，找词性序列y ，y 其实是隐变量，如何把y 找到呢？最有可能的y 就是给定x ，能够使得$P(y|x)$最大的那个y ，就是最有可能的词性序列y 。     可以发现我们需要遍历所有的 y  才能求解上述问题。如果序列长度为 L ，词性序列为 $|S|$ 的话，我们会有 ∣S∣L 种可能，如何来做呢？  

Viterbi algorithm

  Viterbi algorithm 算法求解上述问题算法复杂度仅有O(L∣S∣2)。  

HMM - Summary

  HMM也是structured learning的一种方法，structured learning的方法需要解决三个问题，HMM是如何解决的呢？  

• Problem 1 Evaluation：$F(x,y)=P(x,y)=p(y)p(x|y)$。
• Problem 2 Inference：y~​=argmaxy∈Y​P(x,y)。
• Problem 3 Training：$p(x|y)$都可以通过训练数据统计出来。

  HMM的方法也存在一些缺点：  

1. 计算转移概率和输出概率是分开计算的，认为其是相互独立的。然而序列标注问题不仅和单个词相关，而且和观察序列的长度，单词的上下文，等等相关。因此x 和y 会条件独立吗？
2. 目标函数和预测目标函数不匹配问题，HMM学到的是状态和观察序列的联合分布$P(Y,X)$，而预测问题中，我们需要的是条件概率$P(Y|X)$。

 

Conditional Random Field (CRF)

  条件随机场对隐马尔可夫模型进行了改进。CRF同样要描述$p(x,y)$假设概率$P(x,y)$正比于一个函数。     $Z(x)$是一个简化，因为分母的值只与x 有关。   CRF的训练准则是找到满足的权值向能够在最大化目标函数。能够最大化我们所观察到的同时，最小化我们没有观察到的。如给定训     在求得权值向量和特征向量后，同样可以和隐马尔可夫模型一样使用维特比算法找到y 。    

CRF - Summary

   

Structured Perceptron/SVM

    与HMM比较。CRF没有HMM那样严格的独立性假设条件，因而可以容纳任意的上下文信息。CRF模型解决了标注偏置问题，去除了HMM中两个不合理的假设，当然，模型相应得也变复杂了。因此训练代价大、复杂度高。  

参考

  【1】https://www.youtube.com/watch?v=5OYu0vxXEv8&list=PLJV_el3uVTsNHQKxv49vpq7NSn-zim18V 【2】https://www.bilibili.com/video/BV1Rt41197Dj?p=3