论文研究 中文复杂名词短语依存句法分析.pdf

针对中文复杂名词短语的依存句法分析进行了研究，提出简单边优先与SVM相结合的依存句法分析算法。算法的每一步迭代根据边的特征于每一对相邻子树之间的无向边中选择最优者，然后利用支持向量机根据边两端子树的特征确定该边的方向，即得到两棵子树的中心语之间的依存关系。实验证明对于复杂名词短语的依存句法分析，算法准确率比简单边优先算法有明显提高，且优于基于最大生成树算法的中文句法分析器；算法分析效率更高，时间复杂度为O（n2 log n）。第6期陈永波,等:中文复杂名词短语依存句法分析1619新 pending;否则利用当前的ω在“严格合法”的边中选择分值长度均在3-13个词之间。每一条短语对应一棵依存句法分最高的边 arc allowed,并同时用 arc best和arc_ allowed对析树。名词短语长度分布如图3所示。由图3以看出,大多数进行更新并继续循环卣至能够选择到合法边。训练过程屮添短语长度在3~5之间。加了一个有向边的集合Cold,其中存储语料中标注的有向边。狸多地跳训练算法的具体过程如下所示a)初始化。word ,, wordd t狐狸Gold= arc l arc E corpus欢快地欢快地b)循环直至 pending的长度为1。图2简单边优先算法对句子图3不同长度的复杂名词(a)得到“严格合法”的边的集合“小狐狸欢快址跳”的分析短语占语料的比重allowe =i are Iis_legal are, Gold, Ares)(b)利用 score()数选择当前的最优边a-hest,并4.2实验算法属于监督学习算法,需要训练集训练。本文在语料中判断分别选取20%、30%、…、70%的数据作为训练集,其余数据作如果 arc best∈ allowed,则根据语料提供的方向构造边are为测试集,观察基于SVM的简单边优先算法对复杂名词短语加入到Arcs中,更新 pending,并将该条边的方向和 are best的进行依存句法分析的效果随训练集比重的不同而发生的变化,特征向量加入到sVM的训练集合中;如果 arc_best f allowed,则在 allowed集合中选择分值最高以20%语料作训练集的结果与简单边优先算法、基于最大的边 are allowed,更m。算法效果衡量标准有三个指标:边的准确率、根节点的准c)退出循坏,返回m。确率和树的准确率。对于长为n的短语的依存句法分析树包无向边ac“完全合法”的定义为:arc在合法的边中有对含的n-1条边,算法执行结果也是n-1条边,因此召回率与应的有向边arc( parent,chld,且oold中所有以 child为父节准确率相同,只需关注准确率。痄确率计算定义如下点的有向边均已找到并添加到了Arcs集合中。函数isl-count(正确的边)lowed(are,gold,Ares)用来表示边arc是否严格合法,这就保证cout(请料中的边)00了在添加边arc( parent, child)并在 pending中删除节点 child之a=u(正确的村根)×100%前,其余的节点均不以 child为父节点。这就有效地保证了操作的合法性正确的短语100%(语料)3.3边的特征选取4.3实验结果和分析由丁 pending的元素为短语依存树的子树,每一步迭代实图4、5分别表示利用相同语料选取不同训练集大小对简际考察∫左右∫树的特征。随着树的生长,特征范围也随之扩单边优先算法和结合SM的简单边优先算法进行训练并测试大,因此这里的特征实际是全局特征,这也是算法优于基于转所得到的准确率。换算法的所在。实际可以表示为g(are)=φ(arc, pending,Arcs,Gold)。定义特征选择的窗口宽度为4,即对 pending第i70与第i+1棵子树之间的无向边,选取p-1~P;+的特征及其特征的组合。中文文本有多种特征可以选择。对每一对相邻20%30%40%50%60%70%80%20%30%40%50%60%70%80%子树,无向边特征的选择如表1所示。边一树根▲树边—树根▲树表1算法选择的特征集合图4训练集比童不同情况下图5训练集比重不同情况类别特征对象简单边优先算法的准确率结合SVM的简单边优先算法准确率结构征pⅢ{P;-1,Pz,P2+1+P:+2由图4可以看出,直接利用简单边优先算法得到的分析结元等征1,,,,fpm1p-1,P+P1+21果非常差。完全分析正确的氮语仅有20%~30%,正确找到for(p q)in!(pi-1, Pi)的边(代表了短语中存在的依存关系)的最优值也只有元特征b1-1,m,mm(1-1p1+1).P-1,P11)43.53%。另外由图中曲线的走势可以看出,算法用于复杂名令P表示子树,则lcn(p)表示p的长度;n表示p的根节词短语的依存分析时性能非常不稳定,随着训练数据的增加,点是否有子节点;t表示P的树根的间性;,和c分别表根和树的准确率甚至会出现大幅度的下降。而出图5可以看示P的最左子节点与最右子节点的词的词性;表示P的根出,结合了SM的算法的性能有了明显的提升,边的准确率出节点位置的词。40%上升到了80%左右;根的准确率由30%左右上升到了60%以上;完仝分析正确的短语更由低于30%上升到近60%。4实验和结果分析通过对照分析部分结果发现,由于复杂名词短语的内部特征多样性比较低,导致在分析同一组邻接节点之间不同方向的两条4.1语料边时,利用有限的特征并不能确定该条边的方向。而结合了实验语料包含15000条复杂名词短语、8209个词,短语sⅥ的算法在第一阶段仅仅利用特征来确定最优边的位置1620·计算机应用研究第32卷方向由SVM来确定,这样便提高了准确率。此外,后者的性能2009,43(2):105-121更为稳定,不会因为训练数据的改变而导致测试性能发生波21周强,孙茂松,黄舀宁,导汉语最长名词短语的自动识别[冂].软动。但是由图5可以看出,随着训练集比重的提高,算法的准件学报,2000,11(2):195-201确率并没有随之提高,原因在于数据量的庞大,20%的数据特[3- Goldberg y, dad M. An efficient algorithIn for easy-firsI ninrl-direc征已经能很好地训练算法。根据短语本身的特点分析,最能够tional dependency parsing[ C]//Proc of Annual Conference on Hu-影响算法性能的特征主要在于词性特征以及节点的位置、长度man Language Technologies and the North American Chapter of the等特征,词木身特征对算法的影响更小一些。Association for Computational Linguistics. 2010: 742-750木文还将结合SVM的简单边优先算法与基于最大生成树[4]冯志伟.机器翻译研究[Ⅵ].北京:宀国对外翻译出版公司,200421-622算法的 ctbparser的性能进行了比较,实验结果如表2所示。[s:李彬,刘挺,秦兵,等,基于语义依有的汉语句子相似度计算[parser基于宾州中文树库标准,能很好地应用于完整句子的计算机应用研究,2003,20(12):15-17依存分析。然而由表2可以看出对于复杂名词短语进行依存[61 Xue Nianwen, Xia Fei. The bracketing guidelines for the penn Chinese分析时,算法的边和根还有整个短语的准确率都高于 ctb parsertreebank(3. 0),IRCS-00-08[R. Philadelphia: University of Penn的结果,甚至算法的最坏值也均优丁 ctbparser。这也很好地说明∫复杂名词短语的依存分析对句」依存分析的重要性,将复「7 Zhang yue, Clark s. Transition-based parsing of the Chinese treebank杂名词短话成分和句」的其他成分分别分析,并将得到的」树using a global discriminative model C]//Proc of the 11 th Internation相结合得到句∫依存分析的完整结果,能够有效圯提高分析的al Conference on Parsing Technologies. 2009: 162-171效果。8 McDonald R, Pereira F. Non-projective dependency parsing using表2结合SⅤM简单边优先算法与 ctbparser性能比较spanning tree algorithms L C//Proc of Conference on Iluman Lar准确率 etbparser本文算法最优值本文算法最差值guage Technology and Empirical Methods in Natural Language Pro81.8675.89cessing.2005:523-530树根[9 McDonald R, Crammer K, Pereira F. Online large-margin training of43.7463.252.40dependency parsers[ C|//Proc of the 43rd Annual Meeting of the As4.4算法的不足oc iation for Computational Linguist ies. 2005: 91-98在分析算法的分析结果时,笔者发现当短语长度比较长或[0 J Zhang Yue, Clark S. a tale of two parsers; investigating and combi-者短语中有依存关系的两个词之问的距离较长而其中之一和ring graph-based and transition-tased tleperidency parsing using邻近的词也可以构成依存关系时,往往会优先将邻近的两个节beam-search[C]//Proc of Conference on Empirical Methods in Natu008:562点连接而导致错误。这相比基于图的算法是一个最大的不足11」胃忠巍,黄徳根,高洁,等.最大生成树算法和决策式算法相结合这也是笔者以后需要解决的问题的中文依存关糸解祈[J].中文信息学报,2012,26(3):l6-25结束语[12]辛霄,范士喜,王轩,等.基于最大熵的依存句決分析[J].中文信息学报,2009),23(2):18-22本文提出了对简单边优先的依衣句法分析算法,并用其对[13】刘挺,马全山,李生,于词江支配度的汉语依存分析模型[小复杂名词短话进行依存分析,算法应用的对象是包含至少三个软件学报,2006,17(9):1876-1883词语的复杂名词短语。本文对算法进行了改进,但算法性能仍「141庆琳,李艳梅,唐琦,基于ⅤSM的文本相似度计算的研究「J.有不足。下一步的工作主要包括两个方向:a)进一步解决长计算机应用研究,2008,25(11)[15] Collins M. Discriminative training methods for hidden Markov models距离依存关系的识别;b)对复杂名词短语内部依存关系类型theory and experiments with perceptron algorithms [C //Proc of的确定。Conference on Empirical Methods in Natural Language processing参考文献2007:1-8「 I Girju R, Nakoy p, Nastase V,eta. Classification of semantic relations[16]闫友彪,陈元琰。机器学习的主要策略综述[J]计算机应用研helween nominals [ J ] Language Resources and Evaluation究,2004,21(7):41(上接第1616页)York: ACM Press. 2011. 493-501[10 Peng Yi, Zhang Yong, Tang Yu, el al. An incident information man-[13 Thelwall M, Wilkinson D, Uppal S Data mining emotion in social net-agement framework baased onwork commUnieation gender differences in My Space[ J]. Journal ofcriteria decision making[ J. Decision Support Systems, 2011, 51the American Society for Infomation Science and Technology2010,61(1):190-199[11 Ngai E. W T, Hu Yong, Wong Y H, et al. The applicat ion of dala mil- [14] Sun Yih(l, HHn Jiawei, Yan Xifeng, ei al. Mining knwledge frorn ining techniques in financial fraud detection: a classification frameworkterconnected data: a heterogeneous information network analysis ap-and an academic review of literature[ J. Decision Support Sys-proach[ J. Proceedings of the VLDB Endowment, 2012. 5(12)tems,2011,50(3):559-562022-2023[12] Mohammed N, Chen Rui, Fung B, et al. Differentially private data [15 Bal M Rough sets theory as symbolic data mining method an applicrelease for data mining C|//Proc of the 17 th ACM SIGKDD Internation on complete decision table J. Information Sciences Letterstional Conference on Knowledge Discovery and Data Mining. New2013,2(1):111-116