ѧ
JOURNAL OF SOFTWARE
1999 1 No.1 1999



ھֲȵĺ䷨*
ܡǿƲ
ժҪһþֲϢԺ㷨Ż·,ͨôϿԶȡĽṹȹϵΪж.˷ʹĿǰĺʷЧ˽30%,ʾ˺ܺõӦǰ.
ؼʡȷ,䷨,ʷ,Ͽ.
ͼšTP18
An Improved Approach for Chinese Parsing Based on Local Preference Information
ZHOU QiangHUANG Chang-ning
AbstractIn this paper, a new technique based on local preference information is proposed to improve the efficiency of Chinese parsing algorithm. By using the statistics of structure preference relations as the figures of merit, the overall efficiency of the current Chinese probabilistic parser has been improved 30% by this method, which shows good application prospects.
Key wordsPreference-based parsing, parsing, Chinese probabilistic parser, corpus.
ͼ(Chart Parsing)㷨,һֺܳõŻBest-First.Ҫ˼ڷ(Agenda)Ŀ,ÿξѡѵĳɷֱ߽չ,ӶѸٵõӵѷ,˷Ч.һ,ѡʵۻ,Ըͬɷȷľ䷨гֵĿԽ׼ȷ,ͳһؼ.,Magerman & Weir1ݺCharaballo & Charniak2ݿʼ̽ϢBest-First,ȡ˺ܺõЧ.
Best-FirstҪڴȫϰղͬ䷨ɷڷеȹϵ.(Preference-based)3ڶԾֲﾳµṹ紦.һ͵ǶӢĽʶ(Prepositional Phrase Attachment)Զ紦.HindleRooth4ôԶϿлȡĽĶԼʵĹǿȵĲͬųPP.R.Basiliˣ5ݽһϢ,.CollinsBrooks6Backing-OffԴд.
һּֽлĸЧ.ֲϢΪBest-Firstѡƻ,ͨųֲСľ䷨ɷ,ӶﵽЧʵĿ.Ŀǰĺʷ7вõƥ㷨8,ֲϢ˴ϿԶȡĽṹȹϵ(SPR).Ŀǰʵ,˷ӦʹЧ˽30%,ʾ˺ܺõĴЧ.ĵ1ڼҪ˺ƥ㷨Ļ,2ڷ˾ֲŻĻ˼·,3ڽ˾ʵַ,4ڸĿǰһЩʵ,Դ˽˷,5ǽ.
1ƥ㷨
ף7ĺʷԺӵķҪͨ3׶ɣ ɷֱ߽Ԥ; ƥ; ͳ.ƥ䴦ųµ,Ҫһ⣺S=WTB,MRRΪ,ͨŵĺƥ,ϲпܵľ䷨ɷ,γӵɭ֣.
WTB=W,T,B,W=w1,w2,...,wnΪӵĴﴮ,T=t1,t2,...,tnΪӦĴǴ,B=b1,b2,...,bnһɷֱ߽Ϣ,biȡֵ0,12,ֱʾwiĳ䷨ɷֵмλá߽磨ţұ߽磨ţλ,ǽƥĻ,ҿеĳɷֱ߽ԶԤ⹤ߣ9ݵõ.MRRһƥ,ǽƥЧ.10
ƥ㷨ʵֽ漰Ҫ⣺(1) ɷֻ,ЩŶԿ໥ƥγһܵľ䷨ɷ;(2) ɷֶ,Щƥγɵĳɷܱʲôľ䷨.ֱϿ,Уɨ,ֱһƥ*,Ӵ˳ɷֳ,ڵƥ**,ͨƥγµľ䷨ɷ,ȻԴ³ɷΪ,ƵĲ.ҡԵϲϽ,ֱɨ赽ӽΪֹ.
㷨3ƽṹʵֵ,ͨLR11ݺͼ12ݵЧƽṹĺպʵĽγɵ.
(1) ƥջ(BMS)˽о䷨б߽Ϣ,൱Tomita㷨11еͼṹջ.
(2) ѹɭ(PSF)˾ƥõо䷨ɷϢ,chartṹ.
(3) ƥɷֱ(PEL)дƥϢ,Ϊһ(Agenda).
йһ㷨ϸݿɲף8.
2ھֲȵŻ
µϢƬΣwiwi+1wi+2wi+3(Ϊ,ʡ˴Ϣ).еƥ㷨,ͬʱõͼ1ʾ÷(a)(b)е5ƥɷAi,iʣ1,5,ʵ,ֻһԳȷľ䷨.Ƕȿ,Ŀǰƥ㷨лƥ,кܴĿŻ.

ͼ1һƬεƥ
ͼ1طԵó,ѡĹؼȷƥɷA1ھֲﾳwiwi+3µϹϵ,ƥ䷨ɷA2,ѡ(a),ƥ䷨ɷA3,ѡ(b),߱ؾһ.ݴ,ǿγһþֲϢƥ㷨ŻĻ˼·ھֲﾳϢԼ,ֻѡȽṹϽƥ,ųԲȽṹƥ,Ӷﵽƥ,߷ЧʵĿ.봫ͳBest-FirstʵֻƲͬ,˷ͨԾֲϲųBest-First˼,ΪĿǰĸʷвõƥͳͬʱеķƺܺõںһ.
жַжϾֲﾳµϹϵ.ĿǰȽϳõǴʹ(Word Association),Ϣ(Mutural Information)ȵ.ǣȡмɷֵĴwmh,ֱﾳĴwlhﾳĴwrhĹMI(wlh,wmh)MI(wmh,wrh),ȻѡеĽϴΪϽṹ.ǰᵽĶӢĽʶĴǲַ.˽ṹȹϵ(SPR)Ϣ.ʽΪIS,LP,RP,ISΪνṹ,ʾΪ{ǰ ޽γɷ κ},LPRPǽγɷھֲﾳISµϸʺϸ,,SPR{p np vp, 0.97, 0.03}ͼ¼Ϣγɷ,ʶ(np)ھֲﾳ{p np vp}뽻ǰ,(p)ϵĸΪ0.97,뽻κ,ʶ(vp)ϵĸΪ0.03.ЩϢԴʵıԶȡ,ΪøʷʵıԶ,õÿӵȫ,иɷֶиʷֲϢȻ,пܵĽνṹ,нϵԤƵ.ݽĽ.
ݴ,еƥ㷨ŻһƥɷA,ھƥﾳLMCƥﾳRMC,γһֲﾳƬ{LMC A RMC},SPR,зһSPRIS˾ֲﾳƬͬ,ɸLPRPĲ̶ѡ.½ڽܾʵַ.
3Ż㷨ʵ
ƥŻ㷨ľʵֹ,Ӧ¼⣺(1) ȷһƥɷֵľֲﾳ;(2) α֤õSPRݵĿɿ;(3) ΰѲͬŻƻƺܺõؽԭƥ㷨.潫ֱϸ.
3.1ֲﾳȷ
һƥɷA,ֲﾳڵƥƥɵ.Ŀǰҵƥ䴦,ƥȷǺ׵,ΪڵõƥɷA֮ǰ,ߵпܵƥ,,ֻBMSPSFͿԵõ.ѵƥĻȡ,Ϊڵǰķ״̬,ɷAҲƥûн.
һƬΣwiA wi+1wi+2ݣwi+3wi+4ݣ,ڸոƥɵĳɷA,ƥӦΪwi+3wi+4ƥĳɷB,Ŀǰܵõ,Ӱ˶ԳɷAŻѡж.Ϊ,һӳѡ,巽ǣһӳƥɷֱ(DCL),ÿĲȷƥʱ,ͽóɷַDCL,ִҵƥ,ÿһ³ɷʱ,DCLеӳٳɷﾳǷ,,DCLȡ,²ƥɷֱ(PEL).,ͨPELDCL໥,֤ÿƥɷֶܻȡֲﾳŻѡ.
3.2SPRֵĺѡ
ĿǰSPRݵӦΪ|LPRP|>,еֵ·ӳھֲﾳ½ϸʵĲ̶.ڴ,LP>RP,ֻƥ䣻֮,ֻƥ.
һ˵,Խ,ŻĿԾԽС,ΪֻųЩھֲﾳ¼ٿֵܳƥ.SPRĹǿ,ʹŻЧʵԵòǺܳ,Ǧ=1,ʱŻƽ.֮,ԽС,һSPRԽ,ӶԶԾдľֲﾳŻ,˷Ч,ͬʱܻųһЩȷƥ,Ӷʹշ׼ȷ½.,ͨѡһʵֵ,ڱ֤õSPRݵĿɿԵǰ,Ӧ÷Χ,ӶŻЧʺͷ׼ȷ֮Ѱҵһƽ.
3.3Ż㷨Ļ
ͨڽܵŻƻЧؽԭеƥ㷨8,γһĽŻƥ㷨,Ŀ.,(2)(3)ʵﾳӳѡ,6˾ֲж,ݴ˿ųֲԽСƥ.
(1) PELлһƥɷA
(2) BMSƥRMC
(3) Ҳ,򽫳ɷADCL,ת(8)
(4) BMSPSFõһƥLMC
(5) ֲﾳ{LMC A RMC}µϹϵ
(6) ,ƥLMC A,ת(7)
(7) ƥ,ת(4)ת(8)
(8) PEL,ת(1)㷨.
4ʵ
ǲף10пĺ(Treebank)Ϊʵ,ɣ(1) ӢоĲ⣨A.ϵĹģΪ1 434,Լ11 821,Ϊ17 058,ƽ䳤Ϊ8.243/;(2) ¼СѧĿαϣB*,ܹģΪ4 139,Լ52 609,Ϊ72 434,ƽ䳤Ϊ12.711/.
ͨʵϵľȳ,γ11,ƽÿԼ507.Ȼȡеǰ10ѵ,5 071,ѵõоֲȷSPRݺͳ.ĵ11Ϊ,506,ڼŻ㷨ķЧ.
ʵҪĿǼֲϢöԺʷķЧʺͷ׼ȷȵӰ.,Է׼ȷȵҪ¼ָ꣺ ٻ(MR), ȷ(MP), (CBs), ȷ(LP).йǵϸɲף7,10.Чͨ¼ֳģ
(1) ƥɷ(MCSum)ƥPSFеƥɷֵĿ,еƥĿһһӦ.
(2) (PTSum)PSFе**Ŀ,һ淴ӳ˶Ծӷ紦׳̶,㷽ɲף10.
(3) CPUʱ䣺ΪӶѵCPUʱ䣨ͳʱ䣩.
ȽSPRֵѡʵ.ͨ0.10.9֮9ֵͬ,¼ֵͬµŻ,ǵõ1ʾʵ.ͬʱгԭδŻƥ㷨Ӧݣ=1У,ΪŻЧж.
1ͬSPRֵµŻ

MR(%)MP(%)CBsLP(%)MCSumPTSumCPUʱ(s)
189.9390.010.8795.171.191046.53106228
0.989.8790.000.8795.218.551031.91105184
0.890.1090.240.8495.228.391039.44104166
0.790.0890.210.8595.278.251036.92104179
0.690.3190.440.8295.318.131034.46104173
0.590.4090.530.8295.318.081034.02104170
0.490.5790.700.8095.308.031033.57104158
0.390.5090.640.8195.327.941033.11104166
0.290.4690.580.8195.297.931033.10104176
0.190.4890.600.8195.247.821032.0310417

ӰУ=0.4Ϊֵ
ӱ1пԿ,ֵµĲϽͣ0.90.1,Ż㷨ķЧʵı仯ƻǵԤڹһµģŶSPRĲϷſ,ԶԽԽľֲﾳµƥŻ,Ӷʹƥɷͷ½.ͳ̵Ӱ,ʹCPUʱı仯ԵòǺ.Ͽ,Чʻڲߵ.
ֵעǷ׼ȷȵı仯ơһߣֱﵽߵ㣨=0.4,Ȼ½ı仯.Ϊֵϴʱ,SPRӳľֲ֪ʶȽϿɿ,ƥ㷨Ż,ƲΣ,,ΪǿԾųھֲﾳ¼ٿֵܳľ䷨ɷ,ЩųɷֵĿŦµļٶ,Ӷʹͳ㷨ԴӿԽϸߵĳɷи졢õѡһøѵķ.ֵ½һ̶ʱ,SPRϢĿɿԽȽ,ʱƥŻ,ͿܰѴȷĳɷھֲﾳʱų,Ӷʹ׼ȷ½.
ۺϷ,Ϊ,ĿǰõľֲSPR,ѡ=0.4ΪֵǱȽϺʵ.ڴ¶ԭеƥ㷨Ż,õĽ:ʷCPUʱ䡢ƥɷͷֱ½30.7%,32.5%99.5%,շ׼ȷҲ,ʾܺõŻЧ.
ͼ2ͼ3һʾŻǰͦ=0.4Ż,овͬȵľӼϵƽƥɷƽķֲص.пԿ,ڼ򵥵ľӣеĴ(еĴͱ)<20,ֲŻЧǺԣڸӵľӣеĴ20,㷨ʾ˺ǿŻ.ҪΪ,ڸӾ,ֿɽŻľֲﾳֵƵȺܸ,ͬʱ,ڶԾֲﾳµĳ䷨ɷϵų,ᵼ¶ɭаɷֵĳǧ÷ų,ԴӲľӣ=61Żǰķܵı仯ؿ,2.


ͼ2Ͼӳƽƥɷϵ

ͼ3Ͼӳƽϵ
2һӾӣ=61Ż

MR(%)MP(%)CBsLP(%)MCSumPTSumCPUʱ(s)
Żǰ80.0076.60994.442.091025.221064
Ż82.2278.72894.591.661021.611044

5
һֻھֲϢŻ䷨.ʵʾ,ʹֻûڴǺ;䷨ıȽϼ򵥵ĽṹȹϵݽŻ,ʵSPRֵ,ҲʹЧԼ30%,Աֺܸߵķ.Ҫȱ,ڽϸССSPRֵľֲ,Żƽ.Ϊ,ڽо,ԽһôʻϢSPRĲ֮,ӶõطӲͬεľֲϢۺŻЧܡΪԵķ̽о,ĵĳɹΪ롢ϢϢȡӦоṩ֧֡
оõȻѧйʿѧ
߽ܣǿ,1967,ʿ,оԱ,ҪоΪϿѧ,,ѧϰ
Ʋ,1937,,ʿʦ,ҪоΪѧ
ͨѶϵˣǿ, 100084,廪ѧܼϵͳصʵ
עͣ*:(1)ұ߽ԤǵĴ(bi=2)(2)ƥµľ䷨ɷ([...])
**:(1)߽ԤǵĴ(bi=1)(2)ƥµľ䷨ɷ([...])
*ϵĵӰ汾ɹ¼´ѧ𶨲ʿṩڴ˱ʾл
**һķָӵдķ
ߵλܡǿ廪ѧѧ뼼ϵ100084
Ʋ廪ѧܼϵͳصʵҡ100084
E-mail: zhouq@s1000e.cs.tsinghua.edu.cn
ο
1Magerman D M, Weir C. Efficiency, robustness and accuracy in Picky chart parsing. In: Church K ed. Proceedings of the 30th Conference of ACL (Association of Computational Linguistics). Newark, Delaware, 1992. 4047
2Caraballo S A, Charniak E. New figures of merit for best-first probabilistic chart parsing. Technical Report, Brown University, Nov. 26, 1996
3Church K W, Mercer R L. Introduction to the special issues on computational linguistics using large corpora. Computational Linguistics, 1993,19(1):124
4Hindle D, Rooth M. Structural ambiguity and lexical relations. Computational Linguistics, 1993,19(1):103120
5Basili R, Pazienza M T, Velardi P. Semi-automatic extraction of linguistic information for syntactic disambiguation. Applied Artificial Intelligence, 1993,(7):339364
6Collins M, Brooks J. Prepositional phrase attachment through a backed-off model. In: Yarowsky D, Church K eds. Proceedings of the 3rd Workshop on Very Large Corpora. Cambridge, Massachusetts: Massachusetts Institute of Technology, 1995. 2738
7Zhou Qiang. A statistics-based Chinese parser. In: Zhou Joe, Church K eds. Proceedings of the 5th Workshop on Very Large Corpora. Beijing: Tsinghua University Press, 1997. 415
8ǿƥ㷨ʵ֡:Ϊ,Ԭ.Թ.:廪ѧ,1997.194200(Zhou Qiang. Implementation of Chinese parsing algorithm based on bracket matching principle. In: Chen Li-wei, Yuan Qi eds. Language Engineer. Beijing: Tsinghua University Press, 1997. 194200)
9ǿһԶ綨ģ.ѧ,1996,7():315322(Zhou Qiang. A model for automatic prediction of Chinese phrase boundary location. Journal of Software, 1996,7(supplement):315322)
10ǿϿĶԶֺͱ׼о۲ʿѧλģ.ѧ,1996(Zhou Qiang. Phrase bracketing and annotating on Chinese language corpus Ph.D. Dissertation. Beijing University, 1996)
11Tomita M. Efficient Parsing for Natural Languagea Fast Algorithm for Practical System. Boston: Kluwer Academic Publishers, 1986
12Winograd T. Language as a Cognitive Process. Vol.1, Syntax. Reading, MA: Addison-Wesley, 1983. 116129
1997-11-20յԭ,1998-01-23յ޸ĸ
