ѧ
JOURNAL OF SOFTWARE
1999 1 No.1 1999



ڸVNṹģȡģ*
ԡƲ
ժҪ˻ڸVNṹģȡģ.ͳƾģʷ,ȻСԭԶʷ֦,ɶʷƵVNṹģ.ʵ֤,ýṹģVNṹʶʱ,ģͱȻͼȻԭģ;иߵľȷʺٻ.
ؼʡȻԴ,Ͽ,,ͳƾ,Сԭ.
ͼšTP18
The Complex-feature-based Model for Acquisition of VN-construction Structure Templates
ZHAO JunHUANG Chang-ning
AbstractIn this paper, a complex-feature- and MDL-based model for acquisition of VN-construction structure templates is put forward. First, a verb classification tree is created using statistical decision tree model. Then, the tree is pruned based on MDL (minimum description length) principle. Finally, structure templates are derived based on the verb classification tree. The experiments show that using the structure templates acquired with the model to recognizing VN-structure, the system has its advantages over the model based on the sense and the MLE (maximum likelihood estimation) principle in precision and recall.
Key wordsNatural language processing, corpus, complex feature, statistical decision tree, minimum description length principle.
ں,VNͬ3֣ƫṹVN硰ŷṹVO硰ĽͷǷIC硰۷ĸĽݡеġ.İVOṹͷǷICͳΪVNṹ.ȷʶVNṹھ䷨ϢϢȡȶҪ,һҪķôṹģʶVNṹ,,ڡŷĽ͡,ܹĳַѵлʽĽṹģ壺Hh05+VN,Ih11+VO,Jd05+ICHh05Ih11Jd05ǡͬʴ֡1ݣ¼ơ֡룩,ȷʶǵĽṹ.
ڴʵVNṹģȡʽرʾ£жʼV=1,2,...,V,ʼN=n1,n2,...,nN,۲ݣ=(,n)|ԡV,nN,ģp(,n),ʹܹ͹۲O.Ϊָģ͵ĲĿڶࣨ|N|*|V|,,ڲʱϡ.
ڵȼĸģǽϡҪ.ַΪNĻPNVĻPV֮,cԡPVcnPN,ģp(c,cn),ԡPV,nPN,p(,n)=p(cv,cn).ϵĵȼ໮ַԶࣺѵԶѧϰĵȼ໮,ַõĻܹ͹۵طӳʵı,Ǿͬϡ,Ҿ㷨,ʵԽϲ2,3ݣڻʵĻ,,Ժ,ʵϵ,VNṹģ岻й,ľ䷨й,,ʵĻֶڴṹģȡǲֵ.4,5
˻ڶʸVNṹģȡģ,ģڶԼϽлֵͬʱ˶ʵ﷨,ڵʵģͣԶ෽Ƚ,ģͳøĶϢģ͵ռ,ʵԸǿ.
1ڸVNṹģȡģ
1.1ⶨ
һʺͬǹVNṹǡVNṹ,붯ʺʱ﷨й,ҲֶͬԵĻ﷨й.Ľ䱾Ϊ̬,ĻΪ̬.Ҫо⶯ʺضnͬʱĽṹ,ʵֻǶʵľ̬,УSUBVﶯʦt,ﶯʦiȣ,SYLmon,˫biȣ,ʵ䡶֡ĴSENSE1(FJ)SENSE2(an)SENSE3С(0167)ԼʵĴWORD.
ڸVNṹģȡģͿ£ضn,ʼV(n)=1,2,...,V,۲S=VN+VN,VN=(,n)|ԺnVNṹ,ԡV,nN,VN =(,n)|vnVNṹ,ԡV,nN,жvԸʽʾ£
 
fiΪ,xiΪֵ.
ڶʸVNṹģȡ˼ǣʶṹص,ЩԶʼV(n)л֣ڻڶʵĻ,ÿȼеĶnֹͬVN͡VNĸ.еĹؼǵȼĻ,V(n)һP,Ӧ
P2V(n)c=V(n)ci,cjP,cicj=գ
cԡP,cԣ1,ԡ٦,Сȱʾĺһ.
ڸûϽĸģͼȿԽӼ,ֿԶδ۲ĶʺֵͬĽṹȷж.ͳƾSDT(statistical decision tree)ģͣ6ݽжʵȼĻ,һ,SDTıǿNԪģ,൱ڲֵNԪģͣһ,SDTģ͵Զȡ.
1.2SDTģʷ
1.2.1SDTʾʷ
SDTһ߻,һϵ,ÿһֿܵѡһֵp(f|h),hʾһϵ,fΪǰѡ,ֵP(f|h) ǰnq1,q2,...,qn(еiʽǰi-1й).
 ͼ1SDTʾһöʷ,һĳЩĶʡɼͬʱVNṹVNṹĸ.,ڲʽ,һʽʾһ,Ӹý֦ܵȡֵҶѡ,ʾϴӸ㵽ý·СֵĶʡɼͬʱǹVNṹǡVNṹ.ʵУʵSUBVʵSYLʵSENSE.,8ʾSUBV=t,SYL=biSENSE=HgĶʡɼֹͬVNṹ.
 
ͼ1ͳƾͼ 
1.2.2ڼȻMLE(maximum likelihood estimation)ԭĶʷ㷨
ʷ㷨Ĺؼÿʽʵѡ,ûϢѡ񷽷6ʷ.X⶯ضnֶͬԹɵѵ,X={(,n,c,m)ԡV,cC},C={VN,VN}Ƿ༯,VǶʼ,mǦԺnִͬ趯ΪA={A1,...,Ap},AkȡֵļVk={k1,...,kn},ݹضnĶʷT㷨£
 ʷTĸroot,ѵXroot
 赱ǰΪnodei,nodeiѵΪXi,(,n,c,m)Xi,c=VNc=VN,ȷΪҶ,أ
 AiA,ֱ
H(Xi)=-Pclogpc;
H(XiAk)=-P(cAk=)logp(cAk=)
 AkʵϢ棺IG(Ak,Xi)=(H(Xi)H(XiAk)),IV(Ak)Ϊ˱ѡн϶ȡֵӵϵ,ʾΪIV(Ak)=-nj=1(|Xij|)/(|Xi|)log(|Xij|)/(|Xi|),|Xi|nodeiѵXiе,|Xij|ѵXiзAk=j
 ȷϢAm=argmaxAkIG(Ak,Xi)
 AmȡֵļVm={m1,...,vmn}nodeiĶӽnodei1,...,nodein,ѵXiΪnӼXi1,...,Xin,ֱXi1,...,Xinnodei1,...,nodein
 AɾAm
 ڽnodei1,...,nodein,ֱִТڡ,жӽѵĻ.
,һûڸĶʷ,еҶ㹹ɶʼV(n)Ż,ÿҶʾĸɴýнĸ.
1.3СMDL(minimum description length)ԭʷŻ
1.3.1MLEԭԻȡģͺͻMDLԭԻȡģ
۵ĶʷĻֺͻڻֵĸģ͵ĽԻȡ.MLEԭԻȡģΪ
M=argmaxMp(OM). 
ѡģ͵ı׼ģѵݵ,ģMҪܵؽѵO,ͨ,ṩѧϰߵֻĿԵһС,MLEԭȡ﷨Ȼܹܺõؽѵе,ǶѵݵĽ,ԻȡеĹʺ(Overfitting),ѵݵĲԺԹ,ȱ.֪Ĺ۲ݹɳȿԽֿ֪Խδ֪ݵ﷨ԻȡеĹؼ.,ͼ1ʾĻMLEԭSDT,ŻҶ㹹ɵĻ,ŵĸģǽŻϵģ,Կģ͵ĸ,޷жѵͬ֡/HcɼĽṹ.ֹʺϵ,ʹÿŲVNṹʶٻʲ.
Ҷ˹7ݵԻȡģΪ
M=argmaxMp(MO)=argmaxM{p(OM)p(M)}. 
MLEԭԻȡģ,Ҷ˹Իȡģͳ˿ģͺѵݵ,ģMp(M).СMDLԭ8ģ͵ۺ,ڸĹ۲ݵõĸģǾȵģ,ɣģl(G),ģ͵ı볤ȣl(O|M),ģΪݵԤʱ,ݵı볤.Ľ1.3.2о嶨l(M)l(O|M),ȶp(M)=2-l(M).P(M)򵥵﷨ߵĸ,Occam's Razorֱ,򵥵﷨ڸӵ﷨.7һ,MDLԭԻȡģֳԽOccam's Razor,ʹp(om)p(m)ﵽģM,P(M)ڼ򵥵ģ,P(O|M)ѵԺõģ.MDLԭҪϳ̶Ⱥģ͸Ӷ֮ҵһ.
1.3.2MDLԭĶʷŻ㷨
һöʷ,ԵõʼVɸ.,ͼ2Ķʷ,ԵõV»֣
.ȫV,
{SUBV=Vi,SUBV=Vt},

 
ͼ2ʷͼ 
ΪڶʷҶɵĻ֮ϵģѵݵ,,MLEģΪֻŻ֣MDLԭΪ,ŻֵĿӦģ͸ӶȺ϶ϵ.
ضnʼV(n)͹۲S=VN+VN,V(n)ĺѡּϦ={P1,P2,...,PS},ÿPiʦ(1is)ӦһĸģMi,Ŀںѡģŵģ.MDLԭģ͵ۺ,£
 ÿѡpi={c1,c2,...,cr},ӦĸģMi={p(,n)ԡV(n)},ЦԦi,jck,p(i,n)=p(j,n)=p(ck,n),pVN(ck,n)=f(,n)/f(,n),f(,n)ʾ(,n)ֵͬƵ.
 ÿģ͵ȣĶʺʵͬ(,n),ĽṹX=ʾ,XֲP{X=x}=.ʽP{X=x}=px(1-p)1-x,x=0,1.x1,x2,...,xnXΪnĹ۲ֵ,Xi(i=1,2,...,n)໥,Թ۲ֵx1,x2,...,xnֵĸ
L=P{X1=x1,X2=x2,...,Xn=xn}=P{Xi=xi}=(pi)xi(1-pi)1-xi. 
ȻΪ
logL=log(pi)xi(1-pi)1-xi.=xilogpi+(1-xi)log(1-pi), 
Ľ-logLΪ.
 ÿģ͵ģȣڱģ,Lpar͸Lpro.趯ʼV(n)ĺѡּΪ,򻮷ΪLpar(V(n))=logȵļ㷽£ΪMLEı׼ΪO(1/),ÿ׼ı볤ΪO(log(1/)=O(-log(1/|)=O(logS2),ÿɲı볤ΪO(C+logS2)=O(logS2),ĶΪLpar=(2)logS.
 MDLԭѡŻֺģͣMopt=argminM{Ldat(M)+Lpar(M)+Lpro(M)},ΪMiMj,Lpar(Mi)=Lpar(Mj),,Mopt=argminM{Ldat(M)+Lpro(M).
һöʷT,nodeiеһ,nodeiӦѵʾΪXi,nodeiӦĸʾΪnodei,{nodei}Xiһ,ڻ{nodei}ϵĸģΪMi.MDLԭŻoptĵݹ㷨£
 ǰΪ㣻
 赱ǰΪnode,nodeҶ,򷵻أnodeݣ
 ,nodeÿŮchildi,ݹĶӼCiŻPi,P=Pi,ڻPĸģΪM,ģMiСģM,L(Mi)<L(M),򷵻ػ{nodei},򷵻ػP.
ϵ㷨һöʷһʼϵŻ.,ͼ1ʾʷŻΪahɵĻ.
1.4ɶʷƵVNṹģ
ʷŻԺ,ɾ֦Ķʷ׵ƵVNṹģ.,ͼ1,ŻֶӦĽṹģΪ

2ڽṹģV+NͶĽṹʶ
ڽṹģV+NͶĽṹʶΪһ⣺һͬ(,n),ЦһضĶ,nһض,жVNṹǡVNṹ.õԴУʴԴʵ䡢ʵ䡢ɾ֦ĶʷƵĽṹģ.VNṹʶ㷨£
 ԶʦԱעʵķ,临ʾQ1,...,QmΪûȫų,˿ж
 ֱQ1,...,QmnͬʱVNṹĸpVN(Qi,n)=(Qi,n)+͹ɡVNṹĸpVN(Qi,n)=(Qi,n)+,(Qi,n)SDTṹģжϵQinͬʱVNṹĸʣ(Qi,n)SDTṹģжϵQinͬʱɡVNṹĸʣǶʦVNṹгֵĸʣnVNṹгֵĸʣǶvڡVNṹгֵĸʣnڡVNṹгֵĸʣ
 k=argmaxipVN(Qi,n)l=argmaxipVN(Qi,n);
 ȽpVN(i)pVN(Ql,n),
pVN(Qk,n)>pVN(Ql,n),ͬ(,n)ĽṹΪVN,ŶΪpVN(Qk,n)
pVN(Qk,n)<pVN(Ql,n),ͬ(,n)ĽṹΪVN,ŶΪpVN(Ql,n).
3ģͷͲԽ
3.1ģͷ
ֱѵͲԼѵͲԼĽ3.2ڣг10ʡ취׼Ʒɼλɲ˾ֵ̡ͬͬΪѵͲԼ,Ըģ͵.ָУԣȽģڲͬѵʱõĽṹģı仯ӵģͼٵģ֮ͣ,仯ԽС,ԽãģȽģڲͬѵʱõĽṹģ,ģԽС,ģԽ򵥣۾ȷʣp=100%ٻʣr=100%aжVN/VNжȷִͬ,bжVN/VNִͬ,cִͬ.
3.1.1MDLģͺͻMLEģ͵ıȽ
ͨȽϻڸMDLģڸMLEģ͵ĸָ,ȽϻMDLģͺͻMLEģ͵.ͼ36.

ͼ3MDLMLEԱȽϡͼ4MDLMLEģȽ

ͼ5MDLMLEȷʱȽϡͼ6MDLMLEٻʱȽ
ͨʵԵó½ۣ MDLģͱȻMLEģٶȿ죻 MDLģͱȻMLEģͼ򵥣 ȻMDLģ͵ľȷʱȲϻMLEģ,ѵݵ,MDLģ͵ľȷ𽥱ƽMLEģͣ MDLģ͵ٻڻMLEģ,ҪڣڻMDLģ͵ĸڻMLEģ,ʹøģͶδ۲ֵͬĴڻMLEģ,ڱ겻ֵͬĴڻMLEģ.
3.1.2ڸģͺͻģ͵ıȽ
ͨȽϻڸMDLģͺͻMDLģ͵ĸָ,Ƚϻڸģͺͻģ͵.ͼ710.

ͼ7ģͺģԱȽϡͼ8ģͺģģȽ

ͼ9ģͺģ;ȷʱȽϡͼ10ģͺģٻʱȽ
ͨʵԵó½ۣ ڸģٶȱȻģԿ죻 ڸģͱȻģͼ򵥣 ڸģͱȻģ͵ľȷʸߣ ڸģ͵ٻڻģ.
3.2Խ
70ֽڵ»гȡ(v,n)ͬ61 324ԣ238 694Σ,漰5 975ʺ6 568,аVNṹ14 081ԣ38 075Σ,漰2 946ʺ931.е(,n)ֱͬעԱǡǺ,Ӷѵ.
ѵȡ3 099(,n)ͬ,ɷղԼ,漰1 095ʺ1 468.ѵ10ֵгȡ(,n)ͬ3 165,עԱǡǺ,ɿŲԼ,漰1 173ʺ1 574.
VNṹģжϷղԼͿŲԼ(,n)ֵͬĽṹ,Խ1ʾ.
1(%) 

ȷٻ
ղ97.896.3
Ų94.190.3

3.3ʵм˵
3.3.1֡մʲ
ʶ׶,ڡ֡մʲĳЩû.ȱ,ڸģͿôϢϢ.磺ʡ֡ĴԱΪi,Ϊ2,ڡ֡û,ʶֳɼĽṹʱ,2.1ģжΪVNṹ.ʵ,Ų,ڶû(,n)ͬ,ڸģ͵ʶȷΪ85.3%,ٻΪ66.7%.
3.3.2
ѵͲԼ(,n)ͬеද,ȻôԱǽ,Ȼ.Ĳȡİ취Ǳ.ʵ,ЩѵʶӰ춼.ԭǣڸMDLԭģ͵õĽṹģ嶼йͬ.,о(Gb01/Hg14)ɼHgǳֵ,(Hg)ѵ(Hg)ѧϰ(Hg)(Hg),GbǸֵ.ڿŲ,ڶ(v,n)ͬ,ڸMDLԭģ͵ʶȷΪ89.5%,ٻΪ95.3%MLEԭģ͵ʶȷΪ82.5%,ٻΪ88.4%. 
4
˻ڸMDLԭVNṹģȡģ.ʵ,ýṹģVNṹʶʱ,ģͱȻͼȻԭģ;иߵľȷʺٻ.Ĳ㣺ٶVNṹʶ,Ӧÿɳɷֵľ䷨,ӦÿֵĻ.,ھӡϵͳܿɿ(v,n)ͬ֡ϵͳVNṹ,ھӡʵڷϵͳܡСϵͳɡVNṹ.ȻĿǵҪڲɳɷ,ǻڸMDLԭVNṹģȡģͨõ.Ļ븴,ģͬʱVNṹĻȻڸMDLԭģ͵³ڻMLEԭģ,֡մʲȻӰVNṹʶȷʺٻʵҪ.ڳ÷ֲƵķ.
оõȻѧ.
߽ܣԾ,1967,ʿ,ҪоΪȻԴ,Ϣ,Ͽѧ.
Ʋ,1937,,ʿʦ,ҪоΪȻԴ,Ϣ,Ͽѧ.
ͨѶϵˣԾ, 100084,廪ѧѧ뼼ϵ
ߵλԡ廪ѧѧ뼼ϵ100084
Ʋ廪ѧܼϵͳصʵҡ100084
ο
1÷ҾԵ.ͬʴ.Ϻ:Ϻ,1983(Mei Jia-ju et al. Tongyici Cilin. Shanghai: Shanghai Dictionary Press, 1983)
2Brown P F et al.Class-based n-gram Models of natural language. Computational Lingustics, 1992,18(4):467479
3Dagan I et al. Contextual word similarity and estimation from sparse data. Computer Speech and Language, 1995,9(2):123152
4Li Hang et al. Clustering words with the MDL principle. In: Proceedings of the 16th International Conference on Com-putational Linguistics. Copenhagen, Denmark: the Association for International Computational Linguistics. 1996
5Pereira F et al. Distributional clustering of English words. In: Proceedings of the 31th Annual Meeting of the Association for Computational Linguistics. Ohio, USA: Association for Computational Linguistics, 1993. 183190
6Magerman S F. Natural language parsing as statistical pattern recognition Ph. D. Dissertation. Stanford: Stanford University, 1994
7Stanley F Chen. Building probabilistic models for natural language Ph. D. Dissertation. Cambridge, Massachusetts: Harvard University, 1996
8Quinlan J R. Inferring decision trees using the minimum description length principle. Information and Computation, 1989,80(2):227148
1997-08-14յԭ,1998-01-23յ޸ĸ
