Structured Learning 4: Sequence Labeling on YouTube
序列标注是一种在NLP中很基础但是也很重要的任务。以POS词性标注为例，输入是一个句子，输出是每个单词的词性。
如果每个单词只有一种词性，我们可以简单的做一个hash table，读到单词直接去查找就可以了。然而问题就在于很多单词不只一种词性，我们需要根据上下文对其词性进行推测，这要求我们读到整个句子的信息。
HMM的假设，认为你在说一句话的时候，是会现在脑中呈现一个词性序列，然后在词性序列的基础上构建对应语义的单词。
你的脑子里现在有一个马尔可夫链，表示了你构建一个句子，从一个词性\(u\)后面再接一个另一个词性\(v\)的概率\(p(v|u)\)，起点是start，重点是end。整个句子的概率就是：
如果我们还知道了，给出每一个词性之后我选择某一个单词的概率\(p(v_j|w_i)\)，那么我可以得到这个词性序列对应的一个确定单词的句子的概率：
且有：
我们称\(p(y)\)中的连乘为转移概率(transition probability)，\(p(x|y)\)中的连乘为发射概率(emission probability)。这两个概率我们都可以从数据中统计出来。
现在我们已经知道了\(x\)，求序列\(y\)，一个猜测就是我要的应该满足下面这个条件。
利用上面的式子，我们可以通过枚举\(y\)序列选出最大值，然而这种做法相当低效。下面介绍一种名为Viterbi的算法在\(O(L|S|^2)\)的时间里解决这个问题。
通过对式子的观察，我们容易发现，一个位置选择词性之后的概率只和这个位置的单词和前一个词性有关，那我们直接简单的动态规划解决就完了，这个做法就叫Viterbi Algorithm。
HMM虽然简单，但是它却有一个问题：他会从训练数据中预测出训练数据本来没有的结果。注意这些结果不一定是正确的。
问题在于HMM认为发射概率和转移概率是无关的，分开训练，也就是用\(p( x\_i |y\_i)\)而不是\(p(x\_i | y\_i,y_{ i -1} )\)。如果你还没有明白这个问题，可以想一下这两个概率表达式的区别。
CRF全称为条件随机场。之前HMM产生的问题，CRF可以很好的解决。
令
我们找一个目标函数
由之前的推导，我们知道
因为要最大化这个函数，我们需要 Gradient Ascent。在\(w\)里面，有两部分需要求导：
** CRF 之所以能够改善 HMM 存在的问题，就在于矩阵\(w\)是一个 learnable 的参数，它的 weights 并不是拘泥于数据中的概率的，它可以通过下面的 steps 一点点改善其中的概率。**
从中观察到2点：
如果\((s,t)\)在训练数据样本中出现次数多，\(w\_{s,t}\)就应该增加。
如果\((s,t)\)在其他数据中出现也很多，\(w\_{s,t}\)就会减小。
这种改进方法相比HMM就好太多了，它可以自己调出需要的\(P_{s,t}(x,y)\)。
将梯度写出来：
这一项也可以用 Viterbi Algorithm 进行计算。
Structed Perceptron 有助于我们联系理解Structed Learning 和 CRF。与 CRF 相比，Structed Perceptron 的 train 是这样的：
而 CRF 是
如果不看 learning rate，它们的相似性是很大的。CRF 是对所有的\(y\)以不同权重减去他们的特征，而 Structed Perceptron 是只减去当前判断概率最大的那个\(\tilde y^n\)。
由于 Structed SVM 还不太明白，也没有办法和深度模型作结合，暂且搁置，回头再更 ??咕咕咕~
原文：https://www.cnblogs.com/TABball/p/12727287.html