此时问题又转变成了：
上述问题就跟SVM一样，转换成了一个凸二次规划问题。
现在的问题就是约束(constraints)太多了，在这么多约束的情况下如何来做呢？
Cutting Plane Algorithm
虽然参数空间中有很多约束(constraints)，但是大部分的约束对我们找的结果是没有影响的。(Red line是我们需要的两个constraint，而例如绿色的constraint即使忽略，也不会对结果产生影响)。
如果我们能够找到只与结果有关的约束项(work set)，我们的求解就会比较容易。约束条件可以改为对于任意的 n nn 和 y ∈ A n 有：
现在的问题就是我们如何来找到这样一个working setA n \mathbb{A}^{n}An? 我们可以通过迭代的方法来做。
- 为每一个样本初始化一个空的
working setA n \mathbb{A}^{n}An。 - 我们只需要考虑
working set里面的y yy，求解上述约束最优化二次问次，能够求解出一个新的w ww。 - 依据w ww，重新找一个
working set成员，这样working set就不一样了。（每次找没有满足约束最严重的那一个约束，将其添加到working set中，如何来找到最严重的这一项呢？不满足约束的条件可表示为：w ′ ⋅ ( ϕ ( x , y ^ ) − ϕ ( x , y ) ) < Δ ( y ^ , y ) − ε ′ w^{\prime} \cdot(\phi(x, \hat{y})-\phi(x, y))<\Delta(\hat{y}, y)-\varepsilon^{\prime}w′⋅(ϕ(x,y^)−ϕ(x,y))<Δ(y^,y)−ε′，因此当Δ ( y ^ , y ) − ε ′ − w ′ ⋅ ( ϕ ( x , y ^ ) − ϕ ( x , y ) ) \Delta(\hat{y}, y)-\varepsilon^{\prime}-w^{\prime} \cdot(\phi(x, \hat{y})-\phi(x, y))Δ(y^,y)−ε′−w′⋅(ϕ(x,y^)−ϕ(x,y))值最大的时候就是最难搞的那个约束，也就是求解哪个y yy对应的约束，找到y yy就找到了对应的约束。对于y yy来说，ε ′ \varepsilon^{\prime}ε′和w ′ ⋅ ϕ ( x , y ^ ) w^{\prime} \cdot \phi(x, \hat{y})w′⋅ϕ(x,y^)是不变项，因此我们需要求解的y yy为arg max y [ Δ ( y ^ , y ) + w ⋅ ϕ ( x , y ) ] \arg \max _{y}[\Delta(\hat{y}, y)+w \cdot \phi(x, y)]argmaxy[Δ(y^,y)+w⋅ϕ(x,y)] 。 - 再得到一个w ww，再重新找到一个新的
working set，不断地循环。
上述算法用于分类问题也是一样，甚至用DNN去替代上述抽取特征的步骤也同样是可以的。
Sequence Labeling Problem
Sequence Labeling Problem说的是我们需要找一个函数f ff，它的输入是一个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)。
- 语法可以假设成一个
Markov Chain，那语法长什么样子呢？假设我们现在要产生一句话，那句首的第一个词汇有0.5的概率是一个冠词，0.4的概率是一个专有名词，0.1的概率是一个动词这样。第二个动词就在第一个词汇之上再产生下一个词的概率：
基于第一步，我们可以计算出一个词性序列的概率。
- 基于这个词性序列，我们可以计算出在第一步生成的合法词性序列的条件下生成对应句子的概率：
接下来我们就需要从训练数据中去获取这些概率值，最简单的方法就是直接统计。
假设我们现在要做一个词性标注的问题，就是给定句子序列x ，找词性序列y ，y 其实是隐变量，如何把y 找到呢？最有可能的y yy就是给定x ，能够使得P ( y ∣ x ) 最大的那个y ，就是最有可能的词性序列y 。
可以发现我们需要遍历所有的 y 才能求解上述问题。如果序列长度为 L ，词性序列为 ∣ S ∣ 的话，我们会有 ∣ S ∣ 种可能，如何来做呢？
Viterbi algorithm
Viterbi algorithm 算法求解上述问题算法复杂度仅有
HMM - Summary
HMM也是structured learning的一种方法，structured learning的方法需要解决三个问题，HMM是如何解决的呢？
HMM的方法也存在一些缺点：
- 计算转移概率和输出概率是分开计算的，认为其是相互独立的。然而序列标注问题不仅和单个词相关，而且和观察序列的长度，单词的上下文，等等相关。因此x xx和y yy会条件独立吗？
- 目标函数和预测目标函数不匹配问题，
HMM学到的是状态和观察序列的联合分布P ( Y , X )，而预测问题中，我们需要的是条件概率P ( Y ∣ X ) 。
Conditional Random Field (CRF)
条件随机场对隐马尔可夫模型进行了改进。CRF同样要描述p ( x , y )假设概率P ( x , y ) 正比于一个函数。
Z ( x ) 是一个简化，因为分母的值只与x 有关。
CRF的训练准则是找到满足的权值向能够在最大化目标函数。能够最大化我们所观察到的同时，最小化我们没有观察到的。如给定训练数据
其中
CRF - Summary
Structured Perceptron/SVM
与HMM比较。CRF没有HMM那样严格的独立性假设条件，因而可以容纳任意的上下文信息。CRF模型解决了标注偏置问题，去除了HMM中两个不合理的假设，当然，模型相应得也变复杂了。因此训练代价大、复杂度高。
参考
【1】https://www.youtube.com/watch?v=5OYu0vxXEv8&list=PLJV_el3uVTsNHQKxv49vpq7NSn-zim18V
