Ӧо
APPLICATION RESEARCH OF COMPUTERS
2000Vol.17No.5P.6-8



ͳģ͵ĺʶо
ӦΤڡ
ժ  Ҫɷģ(HMM)ڽϺõԣʶоռλHMMʶ㷨Ҳȡ˽ϺõʶЧõ㷺Ӧáźŵѧģʶ˴ŲԵķѧ֪ʶʶĹȱݡ·NԪķ(N-gram)ͳģӦںʶƵģͲĹֵʽģ͵ѵʶ㷨ʵͳģڽʶѶȺ͸ʶܡ
ؼʡͳģ  N-gramķ   ʶ
1  
ʶоУɷģ(HMM)ϺõԣHMMʶ㷨Ҳȡ˱ȽϺõʶЧõ㷺ӦãHMMΪǰΪеʶģͣʶоռλһ棬ȻHMMȡ˺ܴĳɹʶоǰƽһ󲽡ڴֱ(Large vocabulary)ʶϵͳоУǷ֣зϵͳԶ⡣˵źŴĶźŽѧģ(Acoustic model)ķ[14]źŵʹȷƣʶϢûмá֪ƵоڽȻʶʱ˶в׽ͱϣͬʱѧϢ䷨塢ﾳȷ֪ʶһԻʶ⡣ˣЩ߲εķѧ֪ʶʵģͣϵʶϵͳУʶϵͳʶܡ
Ŀǰоģ֣ͳģͺȷģ͡Ͽ͸ͳƷͳģ(Statistical Language Modeling)Ӧʶ𣬳ΪʶرǴֱʶҪо֮һ[]
ʶϵͳģ͵ԭʵּҪĸ-(Entropy of Language)ģ͵ĸӶ(Perplexity of Language)ڴ˻ϣ˻ֵN-gramģ(Character-based N-gram Model)ĺʶ𷽷÷ȾеBigramռռٵŵ㣬ֿɳûڴ(Word-based)Bigramģͼ㷨ŵ㡣ʵ÷ЧʶѶȣʵҾнϸߵʶʡ
2  ʶѧģͺͺN-gramģ
2.1  ʶѧģ
AѧźţӦƴΪA=(a1, a2, ..., an)WǾӻʵУW=(W1, W2, ..., Wn), Wi={Wij}ƴaiӦĺ()ѡi=1, 2, .., nj=1, 2, ..., miSǴӺѡеõʶʶȡƥS׼У
(1)
BayesʽУ
(2)
Aǲģʿɲ迼ǣʽдɣ
(3)
(3)ʽԿʽP(A|W)ѧģƥõĸʣP(W)ѧź޹أɷѧģͼģ(Language Modeling)ġ(2)ʽǿԸʶϵͳһģͿͼͼ1ʾ

ͼ1ʶϵͳһģͿͼ
ûģ͵£еľWP(W)ͬʱУ
(4)
ǽѧģͽźƥʱʶʶеͳģ͡
Ϊ˶̻ģ͵ӦϢȻԺģ͵йظͶ壺ȻԺģ͵غ͸Ӷȡ
Ϣ۵Ĺ۵㣬ǿ԰ԿΪϢԴľӿԿǴʴnɣW=(W1, W2, ..., Wn)VΪʻ(Vocabulary)Ͽ(Corpus)дʵĸΪV
Ǹ¶壺
1)Ե(LP)
ȡÿʵΪȻԵأΪLP
(5)
2)ԵĸӶ(PP)
ǶȻԵĸӶΪ
(6)
ۺͷģ͵غ͸Ӷȼʡ
3)ģ͵(LMP)
ľӣд֮صģ˿ǵһԣ(5)ʽԵó
(7)
ʽ(7)иشӸϷӳ˴֮ϢϵǽΪģ͵ءڲͬԼ£Եõͬļ򻯵ģͣ(7)ʽɵõͬ򻯽
ֻѧģ͵ġʡֱʶϵͳ
ʱVʱɵȸʳ֣֮以أ(7)ʽУ
(8)
ڹʴֱʶϵͳ
ʱдʻأʷǵȸʳ֣(7)ʽУ
(9)
4)ģ͵ĸӶ(ΪLPP)
ȻԸӶȵĶ壬Ƕģ͵ĸӶΪ
  (10)
Ӧ3Ӧģ͵ĸӶȷֱǣ
  (11)
  (12)
ɸۺйض壬Ƶغ͸Ӷȵ£
1
  (13)
2
  (14)
2.2  N-gramģ
ʽ(7)еطӳд֮ĴϵҪͨģȡȻԵķḻʹԵĽģںܴѡʵʴУΪ˵õʵеģͣǱϵģĳЩԵļ裬ģʵּо
ڴģͳƵMarkovģͷʶȡ˽ϴĳɹ[]˷˴ͳĻڹʶ𷽷ȱ㣬пԴģʵı򵥡ٶȿŵ㡣N-gramģ;ͳģ͵ʵּģ֮һۺN-gramģ͡
(3)ʽͼ1Կģ͵ʵֹΪƸP(W)ݸʹʽP(W)дɣ
  (15)
ʽ(15)iWiֵĸW1W2...,Wi-1ʷйءȻʵӦм(15)ʽеǲܵģΪnܴʱһNP⡣ʵӦУǼȻһMarkovһ仰еĳֻǰN-1йءʽ(15)дɣ
  (16)
ʽ(16)ɴӴģͳеõǰN-1Ʋ⵱ǰֵMarkovģͳΪN-gram(NԪķ)ģ͡N=123ʱֱΪUnigramģ͡BigramģͺTrigramģ͡ͳƵĵԪǵ֣ΪN-gramģ͡ʵӦУNСʱ(N3)N-gramģͲűȽʵС
ʽ(16)ʽͨViterbi㷨
3  ѵʶ㷨
ۻڵͳƵBigramģ͵ѵʶ㷨
3.1  ѵ㷨
N-gramģ͵N=1ʱΪUnigramģ֮ͣ以ȫûϢӳֻǴƵͳԡʱУ
  (17)
N=2ʱΪBigramģͣʱ
  (18)
ͨԴѵıʶ(Word pairs)(Wi-1, Wi)ֵĴC(Wi-1,Wi)ͳƸʣ
  (19)
ɴ˿ɽһP(W)йơ
ʻΪV={W1,W2,...,WV}ΪVUnigramģͺBigramģ͵ģѵ㷨£
(1)ʼ;
(2)for i=1 to V;
(3)ѵȡWiWi-1V,ʽ(17)ʽ(19)ֱƵP(Wi)ʹʶԪͬƵP(Wi|Wi-1)
(4)P(Wi)=0P(Wi|Wi-1)=0,ȡP(Wi)=ŻP(Wi|Wi-1)=(Ϊһ趨СʣΪСķ㳣);
(5)i=i+1; if (i&gt;V)㷨;
(6)goto(2);
(7)еĸʽйһ㡣
3.2  ʶ㷨
ڸĴϵW=(W1, W2, ..., Wn)Viterbi㷨·ÿģ͵ƥ䣬
(20)
Ȼֵģ;ʶ
4  ʵ
4.1  ʵ
ʵԴֱʶʵʹõϴԼ100ʴ(ձ)Ϸֳ,ֱΪCORPUS1CORPUS2ʵУ
ȣõһֽеֶԪͬͳƣѡȡCORPUS1гƵߵ1,000ΪƵʼγͳݿ⡣⣬ǵӿͷб{};ĩ{}ΪĸƵʷڸƵʿУƵʿ⹲1,008ʡлõһһִʿ⣬6,773(һֿ)һִʿ⣬7,683ִʡ
Ȼ󣬽ʶʵ顣ǱȽַһûģ͵ʶһǼģUnigramBigramʶ𡣲УCORPUS1ΪϣCORPUS2ΪϡʵʱCORPUS1CORPUS2ȡݽвԡ
4.2  ʵ
Խ1ͱ2ʾУ1ǸӶȱȽϱ
1 ӶȱȽϱ

ıСӶģ
ģUnigramģBigramģ
40008PPu6773409.6166.3
29782PPb76832235.9885.0

2 ʶʲԽ

ǰnѡʶģģUnigramģBigramģ
R1R2R1R2R1R2
170.6842.6380.7557.4980.6558.64
280.7258.7387.1167.8392.5969.07
390.3164.3893.5978.2696.7980.12
696.7788.5296.7788.5397.1790.10
8100.0090.80100.0090.80100.0090.80

УPPuΪһִʵĸӶȣPPbǶִʵĸӶȡģʱĸӶȱûģʱΪͣø߽N-gramģͱȲõͽN-gramģ͵ĸӶнһؽ͡
2˴CORPUS2гȡһıTEST(к180һֱоеִ150)вԵʶʽR1ΪһִʵʶʣR2Ϊִʵʶʡ
ٴʵԿģͺʶԵߣҸ߽ģͱȵͽģ͵ĸĽЧԣԤһ¡
ͳģ͵صǴӴʵԲ֯ʽȡеԽṹϢˣòͬ͵ϣԼ֤Ͼ㹻Ĺģǽͳģ͵ҪʵõϵѡȽխҲ١˲֣Ӱ쵽ģ͵ܡ
N-gramģ͵һҪѵݲϡ裬ο˷һ⣬ֲڵϵͳһʮҪĿ⡣ 
5  ۺͽĹ
Ļͳģ͵ʶ𷽷ѧģϣЧؽʶѶȣЧʶЧڽĹУǽһо⣺
(1)ЧĸͳƼĽN-gramģͣԽϡ⡣
(2)оòͬͳƵԪ(ʡ)N-gramģͣԽһʶʡ
(3)Ľͳģ͵Ӧԡ
ĿȻѧ𲿷
Ӧ(ѧ̹ѧԺͨŹϵ    510641)
Τ(ѧ̹ѧԺͨŹϵ   510641)
(ѧ̹ѧԺͨŹϵ   510641)
ο
1P. F. Brown, The Accoustic-Modeling Problem in Automatic Speech Recongition, PH.D. Thesis CMU, May 1987
2L. R. Rabiner, A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition. Proc.IEEE, Feb.1989, 77(2): 257286
3÷  , Ⱥ, . ģĸʶ. ӿѧѧ199820(2)188193
4٣Ӣ½. ʶHMM֡Ϣһֲģ. ѧ199826(10): 5054
5Ӧ. N-gramģ͵ĺִо. ݣйѧ·ϵͳѧʮļ323327ҳ199911
6Yamamoto M.: A Re-estimation Method for Stochastic Language Modeling from Ambiguous Observations, in Proceeding of WVLC-96,pp.155167,1996
7Rosenfeld R. The CMU Statistical Language Modeling Toolkit and Its Use in the 1994 ARPA CSR Evaluation, In the Proceedings of ARPA Spoken Language Systems Technology Workshop,pp.4750, 1995
8L. R. Bahl, P.F. Brown, P.Desouza, R.L.Mercer. A Tree-Based Statistic Language Model for Natural Language Speech Recognition, K.F.Lee, Alex Wabel, 1990
9  㣬  . ڸ߽N-gramĵʾ͹ȡ㷨о. Ӧо1999,(5):1517
ոڣ1999-12-18
