第9章：自然语言句法分析

No.95,ZhongguancunEastRoadBeijing100080,China:[phone]第第99章章句法分析句法分析NLPR,CAS-IA2007-5-4宗成庆：《自然语言理解》讲义NLPR9.19.1概述概述NLPR,CAS-IA2007-5-4宗成庆：《自然语言理解》讲义NLPR9.19.1概述概述任务：句法分析(syntacticparsing)的任务就是识别句子的句法结构(syntacticstructure)。‰例如（前面第四章的例子）：他还提出一系列具体措施的政策要点。他/PN还/AD提出/VV一/CD系列/M具体/JJ措施/NN和/CC政策/NN要点/NN。/PUNLPR,CAS-IA2007-5-4宗成庆：《自然语言理解》讲义NLPR(IP(NP-SBJ(PN他))(VP(ADVP(AD还))(VP(VV提出))(NP-OBJ(QP(CD一)(CLP(M系列)))(NP(NP(ADJP(JJ具体)(NP(NN措施)))(CC和)(NP(NN政策)(NN要点))))))(PU。))9.19.1概述概述NLPR,CAS-IA2007-5-4宗成庆：《自然语言理解》讲义NLPR9.19.1概述概述树状表示：IPNPVPPUPNADVPVP。他ADVVNP还提出QPNPCDCLPNPCCNP一MADJPNP和NNNN系列JJNN政策要点具体措施NLPR,CAS-IA2007-5-4宗成庆：《自然语言理解》讲义NLPR‰目标：实现高正确率、高鲁棒性(robustness)、高速度的自动句法分析过程。‰困难：自然语言中存在大量的复杂的结构歧义（structuralambiguity）。9.19.1概述概述NLPR,CAS-IA2007-5-4宗成庆：《自然语言理解》讲义NLPR9.19.1概述概述例如：(1)Isawaboyinthepark.[Isawaboy]inthepark.Isawa[boyinthepark].(2)Isawaboyintheparkwithatelescope.(3)Isawaboyswimmingonthebridge.(4)关于鲁迅的文章。(5)把重要的书籍和手稿带走了。‹结构歧义NLPR,CAS-IA2007-5-4宗成庆：《自然语言理解》讲义NLPR9.19.1概述概述英语中的结构歧义随介词短语组合个数的增加而不断加深的，这个组合个数我们称之为开塔兰数(Catalannumber，记作CN)。如果句子中存在这样n(n为自然数)个介词短语，CN可由下式获得[Samuelsson,2000]：112+⎟⎟⎠⎞⎜⎜⎝⎛=nnnCN)1()!()!2(2+=nnnNLPR,CAS-IA2007-5-4宗成庆：《自然语言理解》讲义NLPR9.19.1概述概述‰基本方法：‹基于CFG规则的分析方法：•线图分析法(chartparsing)•CYK算法•Earley(厄尔利)算法•LR算法/Tomita算法……－Top-down:Depth-first/Breadth-first－Bottom-upNLPR,CAS-IA2007-5-4宗成庆：《自然语言理解》讲义NLPR9.19.1概述概述‹基于PCFG的分析方法PCFG:ProbabilisticContext-FreeGrammar，有时也写作StochasticCFG,SCFG。规则形式:AJα,pNLPR,CAS-IA2007-5-4宗成庆：《自然语言理解》讲义NLPR9.29.2线线图分析法图分析法NLPR,CAS-IA2007-5-4宗成庆：《自然语言理解》讲义NLPR9.29.2线线图分析法图分析法‰三种策略自底向上（Bottom-up）从上到下（Top-down）从上到下和从下到上结合NLPR,CAS-IA2007-5-4宗成庆：《自然语言理解》讲义NLPR9.29.2线线图分析法图分析法‰自底向上的Chart分析算法•给定一组CFG规则:XP→α1…αn(n≥1)•给定一个句子的词性序列：•构造一个线图：一组结点和边的集合；012n-1nW1W2Wnn=•建立一个二维表：记录每一条边的起始位置和终止位置。NLPR,CAS-IA2007-5-4宗成庆：《自然语言理解》讲义NLPR9.29.2线线图分析法图分析法执行操作：查看任意相邻几条边上的词性串是否与某条重写规则的右部相同，如果相同，则增加一条新的边跨越原来相应的边，新增加边上的标记为这条重写规则的头(左部)。重复这个过程，直到没有新的边产生。012n-1nW1W2WnNLPR,CAS-IA2007-5-4宗成庆：《自然语言理解》讲义NLPR9.29.2线图分析法线图分析法点规则：用于表示规则右部被归约(reduce)的程度。设有规则：NPJDetANNPJDetNNPJAN句子:ThegoodbookDetANNPJDet◦ANNPJDet◦NNPJDetA◦NNPJDetAN◦活性边(活动弧)：规则右部未被完全匹配非活性边(非活动弧,或完成弧)：规则右部已被完全匹配点规则NLPR,CAS-IA2007-5-4宗成庆：《自然语言理解》讲义NLPR9.29.2线图分析法线图分析法‰数据结构‹线图(Chart)：保存分析过程中已经建立的成分（包括终结符和非终结符）、位置（包括起点和终点）。通常以n×n的数组表示（n为句子包含的词数）。‹代理表(待处理表)(Agenda)：记录刚刚得到的一些重写规则所代表的成分，这些重写规则的右端符号串与输入词性串(或短语标志串)中的一段完全匹配，通常以栈或线性队列表示。NLPR,CAS-IA2007-5-4宗成庆：《自然语言理解》讲义NLPR9.29.2线图分析法线图分析法‹活动边集(ActiveArc)：记录那些右端符号串与输入串的某一段相匹配，但还未完全匹配的重写规则，通常以数组或列表存储。NLPR,CAS-IA2007-5-4宗成庆：《自然语言理解》讲义NLPR……9.29.2线图分析法线图分析法‰算法描述：从输入串的起始位置到最后位置，循环执行如下步骤：(1)如果待处理表(Agenda)为空，则找到下一个位置上的词，将该词对应的(所有)词类X附以(i,j)作为元素放到待处理表中，即X(i,j)。其中，i,j分别是该词的起始位置和终止位置，ji，j-i为该词的长度。(2)从Agenda中取出一个元素X(i,j)。(3)对于每条规则，将(i,j)加入活动边集ActiveArc中，然后调用扩展弧子程序。γXA→γoXA→XijNLPR,CAS-IA2007-5-4宗成庆：《自然语言理解》讲义NLPR9.29.2线图分析法线图分析法‡扩展弧子程序：(a)将X插入图表(Chart)的(i,j)位置中。(b)对于活动边集(ActiveArc)中每个位置为(k,i)(ik≥0)的点规则，如果该规则具有如下形式：,如果A=S,则把S(1,n+1)加入到Chart中，并给出一个完整的分析结果；否则，则将A(k,j)加入到待处理表中。(c)对于每个位置为(k,i)的点规则：，则将(k,j)加入到活动边集中。βαXAo→βαoXA→XAoα→NLPR,CAS-IA2007-5-4宗成庆：《自然语言理解》讲义NLPR9.29.2线图分析法线图分析法例：G(S):SJNPVPNPJDetNVPJVNPVPJVPPPPPJPrepNP输入句子：theboyhitsthedogwitharod形态分析：……hit……词性标注结果：DetNVDetNPrepDetNNLPR,CAS-IA2007-5-4宗成庆：《自然语言理解》讲义NLPR9.29.2线图分析法线图分析法Det(1,2)NPJDet◦N(1,2)Det(1,2)分析过程：AgendaActiveArcChart12DetNVDetNPrepDetN34N(2,3)N(2,3)NPJDetN◦(1,3)NP(1,3)SJNP◦VP(1,3)NP(1,3)NP……NLPR,CAS-IA2007-5-4宗成庆：《自然语言理解》讲义NLPR9.29.2线图分析法线图分析法VPJV◦NP(3,4)Det(1,2)NPJDet◦N(1,2)Det(1,2)分析过程：AgendaActiveArcChartN(2,3)NPJDetN◦(1,3)N(2,3)NP(1,3)SJNP◦VP(1,3)NP(1,3)V(3,4)V(3,4)Det(4,5)NPJDet◦N(4,5)Det(4,5)N(5,6)N(5,6)NPJDetN◦(4,6)NP(4,6)SJNP◦VP(4,6)NP(4,6)VPJVNP◦(3,6)VP(3,6)VP(3,6)SJNPVP◦(1,6)VPJVP◦PP(3,6)…………NLPR,CAS-IA2007-5-4宗成庆：《自然语言理解》讲义NLPR9.29.2线图分析法线图分析法最后分析结果：DetNVDetNPrepNNPNPVPPPVPSDetNPNLPR,CAS-IA2007-5-4宗成庆：《自然语言理解》讲义NLPR9.29.2线图分析法线图分析法分析结果的直观图：VPPPSNPDetNVPtheboyhitsthedogPrepVNPwithNPDetNarodDetNNLPR,CAS-IA2007-5-4宗成庆：《自然语言理解》讲义NLPR9.29.2线图分析法线图分析法‰Chartparsing评价‹优点：¾算法简单，容易实现，开发周期短‹弱点：¾算法效率低，时间复杂度为K*n3(n为句子长度，K为常量)。¾需要高质量的规则，分析结果与规则质量密切相关；¾难以区分歧义结构。NLPR,CAS-IA2007-5-4宗成庆：《自然语言理解》讲义NLPR9.39.3CYKCYK分析算法分析算法NLPR,CAS-IA2007-5-4宗成庆：《自然语言理解》讲义NLPR9.39.3CYKCYK分析算法分析算法‰Coke-Younger-Kasami(CYK)算法¾对Chomsky文法进行范式化：AJa或AJBCA,B,C∈VN,a∈VT,G=(VN,VT,P,S)¾自下而上的分析方法¾构造(n+1)×(n+1)识别矩阵，n为输入句子长度。假设输入句子x=a1a2…an，n=|x|。NLPR,CAS-IA2007-5-4宗成庆：《自然语言理解》讲义NLPR9.39.3CYKCYK分析算法分析算法‰识别矩阵的构成¾方阵对角线以下全部为0；¾主对角线以上的元素由文法G的非终结符构成；¾主对角线上的元素由输入句子的终结符构成。NLPR,CAS-IA2007-5-4宗成庆：《自然语言理解》讲义NLPR9.39.3CYKCYK分析算法分析算法i+1,ji,j-1i,ji,ii,i+1j-1,jj,j0,n1,10,00,1n,nNLPR,CAS-IA2007-5-4宗成庆：《自然语言理解》讲义NLPR9.39.3CYKCYK分析算法分析算法‰识别矩阵构造步骤(1)首先构造主对角线，令t0,0=0，然后，从t1,1到tn,n在主对角线的位置上依次放入输入句子x的单词。(2)构造主对角线以上紧靠主对角线的元素ti,i+1,其中，i=0,1,2,…,n-1。对于输入句子x=a1a2…an，从a1开始分析。NLPR,CAS-IA2007-5-4宗成庆：《自然语言理解》讲义NLPR9.39.3CYKCYK分析算法分析算法如果在文法G的产生式集中有一条规则：AJa1则t0,1=A。依此类推，如果有AJai+1，则ti,i+1=A。即，对于主对角线上的每一个终结符ai，所有可能推导出它的非终结符写在它的右边主对角线上方的位置上。NLPR,CAS-IA2007-5-4宗成庆：《自然语言理解》讲义NLPR9.39.3CYKCYK分析算法分析算法(3)按平行于主对角线的方向，一层一层地向上填写矩阵的各个元素ti,j，其中，i=0,1,…,n-d,j=d+i，d=2,3,…,n。如果存在一个正整数k,i+1≤k≤