ѧ
JOURNAL OF SOFTWARE
1999 19 3  Vol.19 No.3 1999



ģһָĽطӦ
ӡƲ
ժҪطǽͳģ͵һЧķ,нǿ֪ʶ.,еطͳģʱڼ.һ,һָĽط.÷ʹûϢĸ,ͨZ-Խѡ.÷Ӧں,ʵ㷨нϸߵļЧʺȷ.
ؼʡģ,ģ,,ѡ,Ϣ,Z-.
ͼšTP18
An Improved Maximum Entropy Language Model and Its Application
LI Juan-zi HUANG Chang-ning
(Department of Computer Science and Technology Tsinghua University Beijing 100084)
(State Key Laboratory of Intelligent Technology and Systems Tsinghua University Beijing 100084)
Abstract The maximum entropy approach is proved to be expressive and effective for the statistics language modeling, but it suffers from the computational expensiveness of the model building. An improved maximum entropy approach which makes use of mutual information of information theory to select features based on Z-test is proposed. The approach is applied to Chinese word sense disambiguation. The experiments show that it has higher efficiency and precision.
Key wordsLanguage model, maximum entropy model, parameter estimation, feature selection, mutual information, Z-test.
ģͼӳ¼ʹȻдڵĹɣ1.ȻԴоз,طһֽͳģ͵Ч,нǿ֪ʶ.,еطͳģʱڼ2.һ,һµѡ㷨.㷨ʹûϢĸ,ͨZ-Եķѡ.ѡ,½ģģ͵Kullback-Leiblerѡ.ʵ,㷨нϸߵļЧ.
ԭ,еĲƺѡ񷽷,;ȻʹZ-Եѡ㷨,ָĽطӦں.
1 ԭ
ԭE.T.Jayness1950,Della Pietra1992״νӦȻԴģͽУ1.ֻǼ򵥽ԭ,ϸοף3,4.
ֱϽ,ԭĻ˼:ѵݼѵ,ѡһеѵһµģ.Ӣ,һдĴ,һǰΪһڴʵĸΪ50%,ǰΪһݴʵĸΪ30%,ģӦѡЩ۲һµĸʷֲ.ڳ֮,ģ͸ĸʷֲΪȷֲ.
1.1 
Pеֵ޼Y,ÿyY,ɾϢxӰ.֪yйصϢɵļΪX,ģ͵Ŀ:xX,ΪyY,p(yx)й.p(yx)ʾΪxʱ,ģΪy,yYxX.:,YǾĳһWпɵļ,XΪԴWÿγ,ΪѡĻɵļ.
1.2 ѵ
ģǾ˹ѱעϿгȡĴ(x,y)ѵ,ϿĶÿγ,ȷȡֵyӦĻx.øʷֲļȻѵбʾ.
(1)
freq(x,y)(x,y)гֵĴ.
1.3 Լ
֪,PϢxй,yֵͬϢ,ģͻܷ,Ҵ֪ʶ,yֻеĲϢй.,xҳyȡֵõ֪ʶģ׷Ŀ.Щõ֪ʶģҪѰҵ.
1. 
xXx=w1w2...wn,cxһӴȡ1,cyYб,ƣc,y Ϊģ͵һ.
Ϊԭ͸.cĳΪ1,ƣc,yΪԭ,,ƣc,y Ϊ.
2. 
һֵ,ʾx,y)Ƿc,yй,壨x,y)c,yΪ
2
϶Կ,гΧеĴʺ͸öȷֵһ𶼿Ϊģ͵,,ģйصĺѡɵļϻܴ.ģѡֻģõ,ǺѡϵһӼ,ܽرѵе.ɴԼ.
3. Լ
(f)Ϊfھʷֲ(x,y)ѧ,ʾΪ
,3
p(f)Ϊfģȷĸp(x,y)ѧ,ʾΪ
,4
p(x,y)=p(x)p(yx),p(x)=(x),޶ģ͵ĸΪй۲쵽¼ĸ,пֵܳ¼ĸ.fģ,
p(f)=(f),5
ʽ(5)ΪԼ.
1.4 ԭ
nfii=1,2,...,n,ģԼģͼ,
C={pPp(fi)=(fi),i{1,2,...,n}},6
Լģкܶ,ģ͵ĿǲԼ¾ȷֲģ,p(yx)ԵһѧΪ,Ϊ
,7
0H(p)logy.
ԭ. ĸʷֲCѡģ,صģpxCΪѡģ.
.8
2 Ƽѡ
ؽģ͵Ĺ̷Ϊ:ѡͲ.ѡѡģб;ԭÿһвֵ,ʹÿһһӦ,Դ˽ģ.
2.1 
DanrochRatcliff1972һΪGISgeneralized iterative scaling algorithm㷨,㷨һĵ㷨.Della Pietra1995㷨˽һĽ,IISimproved iterative scaling algorithm㷨,㷨ĸp(x,y)Gibbsֲʽ
9

,10
Z(x)Ϊһ,֤x,.
2.2 ѡ
GISIISĲƷṩľֵķ,֤Ԧ˽ģͲκζļ.㷨ܱ֤ģǾñ,,ڽģʮҪһֹѡ.Della Pietraԭ㷨˼:ʼSΪ,˺󲻶S,ÿӵѵݾ.ѵݵĶȻΪѡ,SΪѡе,fΪѡ,L(ps)ʾSģ͵ĶȻ,ÿѡfӦΪʹʽ
L(s,)L(ps)-L(Ps),11
.
.12
㷨Ǽ,ÿѡһҪеĺѡIIS㷨,Ԧ¼,ҪѵݵĶȻм,Ȼѡһʹģ͵ĶȻ,⼸ǲɲ.Ϊʹѡ̿,Della PietraָһϵŻ㷨,ģмһµʱ,ǰIIS̹ƵĦֵ,ֻIIS¼ĶӦֵ,ѡ,µһIIS,Ц˽һ¼,ַȻԼӿѡĹ,ܱ֤ÿμģ͵õ.
3 ʹZ-Եѡ㷨
ģ͵ĹؼҪѡԤõ,ֻܱ֤õĽǶģõĽ.ȻDella Pietra˵ԭѡ񷽷,ѡõԤõ,ַȫѧĻ֮,ż.
ȻѡĿҪѡģ;ԤõϢ,ϢҪԤڵֵнеĴϵ.Ǵһ,һʹûϢ,Z-Եķѡ㷨.
3.1 ԭѡ
֪ѵеNѵ(x1,y1),(x2,y2),...,(xN,yN),xiXyiY,A=ajajxiӴ,ajĳΪ1,i=1,2,...,N,ԭѡǴAѡֱܹYĲͬȡֵСF=f1,f2,...,fn,fi=(ai,yi)aiA,yiY,i=1,2,...,nΪԭ.
ڴ,ǲKullback-Leiblerⶨȷģ͵.ѵȷĸģ,pΪȷģ,Kullback-Leibler붨Ϊ
 .(13)
ҪҵģpΪ
.(14)
3.2 Z-Խԭѡ
(1) Ϣ5ݿɺǿ
ѡĿҪѡģ;ԤõϢ,ϢӦԤڵֵнеĴϵ,ϢеĻϢǲǿȵһ.ӦҪΪ:ĳһϢyб,yĵĻϢϴ.
(2) Z-ԣ6ݿΪϢһ
ȻϢΪǿȵ,,ѡֱȷѡϢĳһֵϢΪʱ,ԲͬϢķֲ,趨ֵҲͬ,,㷨Բ.Z-ԿԽϢķֲб׼任,Ϊ׼ֲ̬,,ۻϢηֲ,Դһͳһֵʼ.
3.3 ԭѡ㷨
:ѵx1,y1,x2,y2,...,xN,yN;
:Dmn.m=Y,yпȡֵĸ;n=ajajxiӴ,ajĳΪ1,i=1,2,...,N,yĲֵֵͬͬĺѡеԪظ.
 .

1.
.x1,y1,x2,y2,...,xN,yNõYԪAԪصִͬFmn,
fij=f(yi,aj)={(xk,yk)ajxsӴ,ҳΪ1,yk=yi,s=1,2,...,N}.
.㻥ϢImn,
 ,
MΪϿĴС,f(yi)f(aj)ֱΪyiajϿгֵĴ.ɻϢĶ֪:Iij0ʱ,yiajȫ,,aj,yiΪģ͵.
2.
ÿyi,
.yiĻϢֵ
;(15)
.
.(16)
3.
Z-Զÿyiɱ(di1,di2,...,dim);
.ÿyii=1,2,...,n ,
.ÿaj,
 ,(17)
* zijT,ajyiΪѡһ,dij=1;dij=0;
4.
.ѡԭS={f1,f2,...,fk}IIS㷨,õZ,1,2,...,k;
.ùʽ(9)(10)p(yx).
5.
.p(yx)ȷģ뾭ʷֲģ(yx)ľD(p);
.D(p)ϴεD(p)Ƚ;D-D䣼,̽;,T=T-T,ת3.
3.4 ֵTȷ
(1) Tֵȷ
㷨Կ,ھʽ(17),ѽϢķֲΪֲ̬.Ӹۿ֪:ֲ̬-3,+3,ʸǶȿɴ99%.,Tڣ-3,+3ڽȡֵ.ΪʼʱҪѡ,ӦTһϴĳֵ.
(2) Tֵı仯
ֵȷ,ԺÿһT,ζÿθTѡеһ,Ǿͬȱ̶ȵһѡӼ,ѡӼаһѡ.,ڽһεĲʱ,ǰֵԴϴȷֵʼ,Խʡʱ.ѡյõȷģ͵D(p)СҾнһļ.
3.5 ԭѡ㷨ļȽ
(1) Della Pietraѡ㷨ļ
ѡ㷨ÿȷһʱļ,IISÿһѡвƺͼģ͵ĶȻ.ܵļɱʾΪ
C1=n*(IIS1+L1)+(n-1)*(IIS2+L2)+...+(n-k)*(IISk+Lk).18
nΪѡкѡĸ,kΪе,IISiLiֱʾѡiʱƵļͶȻļ.
IISminΪkѡ,ƹʱ,
C1n*(IISmin+L1)+(n-1)*(IISmin+L2)+...+(n-k)*(IISmin+Lmin).
ɹʽ(12)֪,L1=L2=...=Lk,
C1n*(IISmin+L1)+(n-1)*(IISmin+L1)+...+(n-k)*(IISmin+L1).
= .19
(2) ѡ㷨ļ
ѡ㷨ÿѡж,̵ļ3,ϢļƵļKullback-Leiblerļ.ܵļΪ
C2=O(m*n)+(IISa1+Da2)+(IISa2+Da2)+...+(IISai+Dai).20
O(m*n)ΪϢļ,aiΪiѡе,IISaiDaiֱʾڵiѡʱƵļKullback-Leiblerļ.
IISmaxΪiѡвʱ,
C2O(m*n)+(IISmax+Da1)+(IISmax+Da2)+...+(IISmax+Dai).
ɹʽ(13)֪,Da1=Da2=...=Dai,
C2O(m*n)+i.IISmax+i.Da1.(21)
㷨֪,mn,ikkn,IISminIISmaxļ㸴Ӷͬһ,Ȼļ㸴ӶKullback-Leiblerļͬ,,ѡ㷨СDella Pietraѡ㷨.
4 Ľģ͵Ӧüʵ
4.1 ԭ
߽Ľģ͵ķӦڽıе.
ģ: ֪wNɵռ:(x1,y1),(x2,y2),...,(xn,yn),(xi,yi)ʾϢΪxiʱ,wΪyi.xiΪyiĻ.ģ͵Ŀԭѧϰģp(yx),京ΪΪxʱΪyĸ.
ģ: Ӧ,S,ˡ;S={f1,f2,...,fn}Ҧ={1,2,...,n}.
4.2 ʵ
(1) Ͽʵ
ʵ,2 000Ѿ˴зֺʹԱעġձϿΪϵͳԴ,ϿгֵĴΪʻʵĸƵΪĶ.ڶԶʽעʱ,õǡͬʴ֡е,ɴСС,硰ࡰHc05͡Hd01,Ƿֱֲͬ.
(2) 
ģ,ģ͵ռΪϿгĳʵĴʼΧĻ,Ȼÿ˹,γռ.ݵ׼,Ĺ.(1)ȷĶΪͬһڵ;(2)ԶΧȡĵĳȵԭΪ:ԾΪλ,һѡôΧǰ7.ԡ򡱡͡3ĴΪʵ,ϿгֵĴѡĸ1.
(3) ѡͲ
ѡ㷨ղTֵ2.
1 2

ѡTֵ
1 6421 1451.117377
1 9283 0291.216402
2 6823 7661.343285

ģͲйء򡱵Ĳ3.
3

y=Fa10ҡx
y=Fa10ҡx
y=Fa10ҡסx
y=Hi44ҡx
y=Hi44ҡʿx
y=Hi44ҡ²Сx

(4) ģͽĹ̼
Ϊ:
. ҳָwģx,w,xΪwĻ;
. ģѧϰĹwĲS,ˡ,ùʽ9ͣ10wĸxµp(yix),yiY.
. ȡʽϴ߶ӦΪѡ.
ڴ,Ƿֱ÷ղԺͿŲַģͽв,ȷʶΪ
 .
õĲԽ4.ӱݿԿ,ñѡ㷨ģͿԱ֤нϸߵ׼ȷ.
4

ղԿŲ
ȷ(%)ȷ(%)
10089.55083.7
10093.25090.6
10091.85089.1

5 
һָĽط,÷ûϢĸ,ʹZ-Էѡ,Խģ뾭ģ͵Kullback-LeiblerΪ̵Ľ,,Ա֤ģ͵׼ȷ.ģں,ȡ˽ϸߵȷ.ķڴԱעӱ߽ʶ.
лĵоõȻѧĿΪ69433010.
оõȻѧصĿ.,Ů,1964,ʿ,ҪоΪѧ.Ʋ,1937,ڣʿʦ,ҪоΪѧ,˹.
ͨѶϵ:ӣ100084,廪ѧѧ뼼ϵ
ߵλ廪ѧѧ뼼ϵ 100084
廪ѧܼϵͳصʵ  100084
E-mail: ljz@s1000e.cs.tsinghua.edu.cn
ο
1Ronnald Rosenfeld. A maximum entropy to adaptive statistical language learning. Computer Speech and Language, 1996,10(3):187228 
2Andrei Mikheev et al. Collocation Lattices and maximum entropy models. In: Zhou Joe ed. Proceedings of the 5th Workshop on Very Large Corpora. Beijing: Association for Computational Lingnistics, 1997. 216230
3Berger A L, Della Pietra S et al. A maximum entropy approach to natural language processing. Computational Linguistics, 1996,22(1):4072
4Della Pietra S, Della Pietra V et al. Inducing features of random fields. IEEE Transactions on Pattern Analysis and Machine Intelligent, 1997,19(4),380393
5Church K, Hanks P. Word association norms, mutual information, and lexicography. Computational Linguistics, 1990,16(1),2229
6Frank Smadja. Retrieving collocation from text: Xtract. Computational Linguistics, 1993,19(1):143175
1998-03-12ո壩
