计算语言学第9讲句法分析（三）刘群中国科学院计算技术研究所liuqun@ict.ac.cn中国科学院研究生院2011年春季课程讲义内容提要计算语言学讲义(09)句法分析(三)2依存分析•依存结构和依存语法•短语结构树转依存树•专门的依存分析模型–概率依存模型–最大生成树模型–状态转移模型计算语言学讲义(09)句法分析(三)3依存分析简介•依存分析与短语结构分析类似，但有所不同：依存分析丢掉了跨度信息和跨度上的句法标识IP是XNPVP√PU。PNVCNP我学生。我是QPNPCDCLPNN一个一M学生个计算语言学讲义(09)句法分析(三)4依存分析简介•大多数语言，包括汉语和英语，满足投射性。所谓投射性是指：如果词p依存于词q，那么p和q之间的任意词r就不能依存到p和q所构成的跨度之外Xp…r…q…s计算语言学讲义(09)句法分析(三)5短语结构树转依存树•任何短语结构树句法分析模型输出的句法树，通过YamadaandMatsumoto(2003)的中心词映射规则即可转化为依存结构树IP是NPVPPU。PNVCNP我学生。我是QPNPCDCLPNN一个一M学生个计算语言学讲义(09)句法分析(三)6短语结构树转依存树•中心词映射规则示例–规则：IPright{IPVP}–意义：对于句法树中标识为IP的节点，自右向左扫描该节点的所有孩子，第一个出现在列表{IPVP}中的孩子即为中心孩子节点。其他孩子节点的中心词将依存到中心孩子节点的中心词•对于给定的短语结构树，自底向上应用中心词映射规则，即可确定各词之间的依存关系计算语言学讲义(09)句法分析(三)7依存分析模型•生成式依存模型–词汇依存概率模型（Collins模型）–依存生成概率模型（Eisner模型）•判别式依存模型–状态转移模型–最大生成树模型计算语言学讲义(09)句法分析(三)8词汇依存概率模型•Collins,1996•训练：通过极大似然估计，在树库中统计出任意两个词之间存在特定依存关系的概率•解码：寻找使得所有依存词对的依存概率的乘积最大的依存树，采用自底向上分析法计算语言学讲义(09)句法分析(三)9依存分析模型•生成式依存模型–词汇依存概率模型（Collins模型）–依存生成概率模型（Eisner模型）•判别式依存模型–状态转移模型–最大生成树模型计算语言学讲义(09)句法分析(三)10概率依存模型(Eisner,1996)给定输入语句（含词性标记）的一棵可能的依存树，设该树中任一节点P，它的左孩子由近及远分别为LC1，LC2，…，LCm；右孩子分别为RC1，RC2，…，RCnP</s>LCmLC2LC1<s>RC1RC2RCn</s>定义P生成其所有孩子的概率为：m=Gen()P∏Pr(LCwordi.|LCi−1.POSPword,.)i=1n×∏Pr(RCi.word|RCi−1.POS,P.word)i=1计算语言学讲义(09)句法分析(三)11概率依存模型(Eisner,1996)•对于每棵候选依存树T，整棵树的生成概率定义为树中所有节点生成概率的乘积Gen(T)=∏Gen(x)x∈T•解码的任务就是寻找生成概率最大的依存树计算语言学讲义(09)句法分析(三)12依存分析模型•生成式依存模型–词汇依存概率模型（Collins模型）–依存生成概率模型（Eisner模型）•判别式依存模型–状态转移模型–最大生成树模型计算语言学讲义(09)句法分析(三)13最大生成树模型•McDonaldetal.,2005•McDonaldandPereira,2006•给定一个包含N个词的句子，任意两个词之间都可能存在依存关系，共有N*(N-1)种可能的依存边（不能含有依存到自己的自环），只是依存强弱不同•将依存强弱表示为这个完全图中边的分数。于是，寻找最可能的依存树的任务就转化为寻找这个完全图的最大生成树计算语言学讲义(09)句法分析(三)14最大生成树模型•每条边pc的分数定义为score(p→c)=f(p→c)⋅w•f()函数返回依存边pc的特征向量；w为权重向量，它由判别式训练得到计算语言学讲义(09)句法分析(三)15最大生成树模型－特征设计•特征设计针对边进行，而非节点•任意一条pc的特征可以取那些呢？计算语言学讲义(09)句法分析(三)16最大