一、Sequence Labeling 问题概述

---

---

---

二、Hidden Markov Model(HMM)

---

---

---

---

---

上图 training data 中的黑色字为x，即文字序列。红色字为$\hat{y}$，即词性序列。

---

$count(s)$为训练数据中所有$s$的个数。
$count(s\to s^{\prime })$为训练数据中所有$s后面接s^{\prime }$的个数。
$count(s\to t)$为训练数据中所有word $t$的标签为$s$的个数。
$P(y_1|start)$为标签$y_1$在句首出现的个数，除以句子总个数。
$P(end|y_L)$为标签$y_L$在句尾出现的个数，除以$y_L$总个数。

---

---

---

---

---

---

这里$N\to V\to a$并没有在训练数据中出现过，但是计算的概率反而比训练数据中出现过一次的$N\to D\to a$高。所以HMM会脑补一些没有出现过的数据。

---

HMM产生这种脑补的情况是因为转移概率和发射概率是相互独立的。解决这个问题的方法是用一个更复杂的模型去处理这个问题。用CRF也可以处理这个问题。

三、Conditional Random Field(CRF)

因为$\exp (w\cdot \varphi (x,y))$可能大于1，所以无法把它当成概率，只能说$P(x,y)$正比于它。
因为${\sum }_{y^{\prime }\in \mathbb{Y}}\exp (w\cdot \varphi (x,y^{\prime }))$由于和变量$y^{\prime }$没有关系，只和$x$有关系，所以简记为$Z(x)$。

---

---

---

---

---

红色的向量中的每一维都依赖于$(x,y)$，所以可以认为它是这个向量所形成的特征，记为$\varphi (x,y)$

---

由于w的元素可正可负，当为正数的时候，求EXP，就会大于1。并且例如，给定s，求和所有的t，我们也无法保证等于1。所以我们说$\text{P}(x,y)$正比于$\exp (w\cdot \varphi (x,y))$，而不说等于。

---

---

---

Part 2 的维度大小：|S|个tag中的每个tag后面都能再接|S|个tag，所以是|S|$\times$|S|。然后start后面能接|S|个tag，end前面能接|S|个tag，所以是2|S|。
CRF比HMM强的点在于，可以自己定义$\varphi (x,y)$

---

---

---

---

---

---

---

---

---

横轴表示HMM犯错的百分比，纵轴表示CRF犯错的百分比。如果点在$45°$对角线左侧，表示HMM表现比较好；在$45°$对角线右侧，表示CRF表现比较好。

---

---

四、Structured Perceptron/SVM

---

如果CRF中，另学习率为1，那么两者参数迭代的公式是相近的。其中Strucured Perceptron参数迭代公式中，减掉的最后一项$\varphi (x^n,{\tilde{y}}^n)$是其概率最大的一项。而CRF减掉的最后一项，则是所有$\varphi (x^n,y^{\prime })$与其概率的加权之和。

---

---

---

---

五、Towards Deep Learning

---

---

可以将$\text{P}(x_l,y_l)$用神经网络，例如RNN的输出进行替换。

因为用HMM做inference的时候是给定x，看哪一个y可以让这个概率最大。所以x是给定的，不管$\text{P}(x_l)$是多少，都不会影响最后得到的y了。故，不用管$\text{P}(x_l)$了。

---

也有如下应用：

上图中的x不再是input的，而是RNN的output。

---