标注问题

应用：词性标注，命名实体标注，命名实体抽取，中文分词等

目标：从训练数据中获取一个函数或者算法，使得它在接收一个句子作为输入时能产出一个标注序列。

约束：local（一般来说，单词can更可能是一个动词而不是名词），contextual（the后面的更可能是一个名词，而不是动词）

生成模型和判别模型

监督学习：给定一个训练集\((x_i, y_i), i = 1...n\)，得到一个从y到x的映射关系\(f(x)\)。

判别模型：从训练集出发，获得一个条件概率分布\(p(y|x)\)；对于任何一个测试样本x，定义\(f(x) = argmax_y p(y|x)\)。

生成模型：从训练集出发，获得一个联合概率分布\(p(x, y) = p(y)p(x|y)\)。

生成模型比判别模型拥有更多的信息，因为任何条件概率分布都可以由联合分布通过边缘化得到。

\[p(y|x) = \frac{p(y)p(x|y)}{p(x)} = \frac{p(y)p(x|y)}{\sum_y p(y)p(x|y)}\]

对于测试样本x，生成模型要做的跟判别模型本质上是一样的

\[f(x) = argmax_y p(y|x) = argmax_y p(y)p(x|y)\]

其中分母\(p(x)\)不影响argmax_y，所以可以被忽略掉。

隐马尔科夫模型HMM

基本定义

HMM是一种生成模型，对于任意一个单词序列\(x_1, ..., x_n\)，任意一个标记序列\(y_1, ..., y_n\)，HMM定义的是一个联合分布

\[p(x_1, ..., x_n, y_1, ..., y_n)\]

而当给定这个分布，同样再给出测试样本\(x_1, ..., x_n\)时，我们要做的就是找到能最大化联合分布的那一个\(y_1, ..., y_n\)

\[argmax_{y_1, ..., y_n} p(x_1, ..., x_n, y_1, ..., y_n)\]

跟第二章讲的一样，HMM为了简化计算都会有一个对上下文长度约束的假设。Trigram的假设是说

\[p(x_1, ..., x_n, y_1, ..., y_{n+1}) = \Pi_{i=1...n+1} q(y_i|y_{i-2}, y_{i-1}) \Pi_{i=1...n} e(x_i|y_i)\]

其中\(x_1, ..., x_n \in V, y_1, ..., y_n \in S, y_{n+1} = STOP, y_{-1} = y_0 = *\)。所以这个模型的参数就是

\[q(s|u, v), s \in S \cup \{STOP\}, u, v \in S \cup \{*\}\]

\[e(x|s), s \in S, x \in V\]

回过头来再看前面这个联合分布，等号右侧的第二项实际就是\(p(x|y)\)，而第一项就是\(p(y)\)，所以说HMM是生成模型。

参数估计

要想使用这个模型就得先把q和e这两套参数先从训练数据中搞出来：

对于q参数，可以直接借鉴上一章中language model里的smooth estimation方法，比如线性插值（就是带\(\lambda\)的那套方法）；

对于e参数，最直接的方法就是MLE，然后我们又遇到了同样的问题：Sparse Data，肿么办？

课程中给出了一个word class的方法：简单来说就是高频词直接MLE（比如出现次数大于等于5的），低频词则按照一定的特征划分到有限个类别中，类别可以是twoDigitNum, containDigitAndSlash, allCaps等，通常需要人工指定规则，划分之后针对\(e(wordClass|y)\)来做统计，而不是原来的\(e(word|y)\)，以丢失word中一些信息为代价来保证有估计得到的参数足够的统计意义。

Viterbi算法

假设使用前面的方法已经获得了想要的参数，那么HMM就已经构造完成了，后面就是看怎么用这个模型来对测试样本做标注了，即

\[argmax_{y_1, ..., y_{n+1}} p(x_1, ..., x_n, y_1, ..., y_n)\]

其中\(y_{n+1} = STOP, y_{-1} = y_0 = *\)。首先说暴力方法是行不通的，因为需要\(O(|S|^{n})\)，指数级别，会被搞死的。。。

下面要说Viterbi算法就是利用动态规划的思想来解决这个标注问题的，懒得费劲了直接上图。

其中递归式\(\pi(k, u, v)\)表示的是"maximum probability of a tag sequence ending in tags u, v at position k"，bp里面存在是回溯指针，用于循环结束后向回寻找最优的tag sequence。

由于Viterbi算法计算每个\(\pi(k, u, v)\)项需要遍历所有\(S_{k-2}\)，而一共有n*|S|*|S|个项需要计算，所以其算法复杂度为\(O(n|S|^3)\)，比指数级别的暴力搜索要强很多。

这个算法的优点是简单，而且在一些应用中也表现得很好，缺点就是前面所说的e参数不好估计。

PS：这个课程里讲的HMM其实并不全面，HMM相关的有三类问题

1. 给定模型，它能产出给定x序列的可能性是多大（forward算法）
2. 给定模型，给定x序列所对应的最可能的y序列是啥（这个就是课程里讲的标注问题，Viterbi算法）
3. 非监督条件下如何估计参数，即训练数据中没有y的情况下怎么搞（forward-backward算法，本质是EM）

52nlp网站中有一系列很赞的文章《HMM学习最佳范例》，里面讲得更加细致全面一些，所以把相关的链接放在这里，就当是备忘吧。