PDF《PCFG 补充材料》

PCFG 补充材料 李正华

2015 年11 月12 日1编程作业 数据包括:训练数据 train.

bracketed,开发数据 dev.bracketed.数据为短语结构树 (phrase-structure tree, constituent tree) , 可以用工具进行可视化: http://christos-c.com/ treeviewer/. 1) 首先要进行数据处理(共10 分) ,包括: ? 将短语树的空节点删掉,即非终结符含 "NULL" 标记的节点和对应的分支. (有问 题可以跟我讨论) ? 将非终结符简化,只保留短语类型标记(如NP, VP) ,而去掉句法功能标记(如SBJ, TMP 等) .换句话说,如果非终结符为 NP-SBJ,那么只保留 NP.所有-后面 的标记都删除. ? 将短语树转化为 Chomsky Normal Form, 可参考https://en.wikipedia.org/wiki/Chomsky_ normal_form. 2) 通过极大似然估计 + 平滑方法,估计 PCFG 模型参数(5 分) . 3) 实现 CKY 算法,对dev.bracketed 数据进行自动处理,并将结果输出到文件中 (10 分) . 4)实现评价程序,得到模型的准确率 Precision、召回率 Recall、和F值(5 分) . 可参考 Collins 最后一个课件的后面几页 slides.

2 几点补充 CKY 算法是一个动态规划算法,和HMM 中的 Viterbi 是很类似的. 对于 PCFG 而言,也可以用无指导的方法来做参数估计,其过程和 HMM 中的 EM 算法很类似.CKY 为max-product, 对应有 Inside-Outside 为sum-product.和HMM 中Viterbi 与Forward-Backward 的对应是类似的. 1