结构化预测

Beam search: greedy

P(y|x): x中文句子, y英文句子

|V|^n 50000^20

sampling:

dynamic programming: HMM

什么是结构化预测？

分类器

• 将输入x匹配到输出y

• 一种简单的分类器

• 对任意一个输入x，计算每个可能的y的分数 score (x, y, \theta)，其中\theta是模型参数

• 选择分数最高的label y作为预测的类别

• 一般来说，如果输出空间是指数(exponential)级别或者无限的，我们把这类问题成为结构化预测(structured prediction)

y = argmax_{candidate}(score(x, candidate, \theta))

结构化预测案例

• POS Tagging

• Unlabeled Segmentation

• 莎拉波娃现在居住在美国东南部的佛罗里达。

• 莎拉波娃 现在 居住 在 美国 东南部 的 佛罗里达 。

• Labeled Segmentation (Named Entity Recognition 命名实体识别)

• Some questioned if Tim Cook’s first product would be a breakaway hit for Apple.

• Constituency Parsing

• Coreference Resolution

• 语言生成：有很多NLP任务涉及到生成一段话，一个短语，一篇文章等等

• 问答系统

• 文本翻译

• 文本摘要

什么是结构化预测？

• 比较官方的定义是，当parts functions无法被拆分成minimal parts的时候，这就是一个结构化预测的问题。但是我们这里不详细展开。

• part是一个问题的一部分子问题

• parts function：用来把输入/输出拆分成parts

• parts可以重叠

• minimal parts：该任务最小的parts

• minimal parts是不重叠的

• 结构化score/loss函数是没有办法拆分成minimal parts的。当我们使用一个结构化的score或者损失函数的时候，我们就在做structured predcition。

结构化预测解决的问题

序列标签问题

• 输入长度为T

• 输出长度也是T

• 每个位置可能的候选是N个label中的一个

• 输出空间为 N ^ T

序列标签的案例

• 前向神经网络做POS tagging

• 输入是一个单词和它相邻的单词

• 输出是中心词的POS tag

• 训练loss: 每个位置中心词的log loss，每个位置的loss相加

• 这不是一个”结构化预测“问题

如果我们采用一个RNN模型来做词性标注，这就成为了一个结构化预测的问题。

如果我们使用HMM模型，这也是一个结构化预测问题。

• 不要把语言当做“bag of words”，单词之间有“结构”。

训练完模型之后，如何很好地快速地做搜索？

Viterbi 算法

https://shimo.im/docs/TRvGRjwJP8TDrCjc

图解Viterbi维特比算法

https://zhuanlan.zhihu.com/p/63087935

Viterbi算法的时间复杂度比较高。（回忆一下Viterbi算法的时间复杂度是多少？）

所以人们发明了一些近似的算法，例如greedy decoding，以及Beam Seaech。

CRF模型

CRF的条件概率公式

分母是很大的

y 有五种不同的可能性

20 5^20

参考资料

http://www.robots.ox.ac.uk/~davidc/pubs/crfs_jan2015.pdf

http://www.cs.cmu.edu/~10715-f18/lectures/lecture2-crf.pdf

http://www.davidsbatista.net/blog/2017/11/13/Conditional_Random_Fields/

Michael Collins’ notes

Log Linear tagggers http://www.cs.columbia.edu/~mcollins/fall2014-loglineartaggers.pdf

CRF Model http://www.cs.columbia.edu/~mcollins/crf.pdf

Forward-Backward算法 http://www.cs.columbia.edu/~mcollins/fb.pdf

参考资料

• Advanced Topics in Machine Learning: Structured Prediction

• Noah Smith的课件

• 条件随机场