о뷢չ
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
1999 36 5 Vol.36 No.5 1999



һֶṹԶȡ
쾸ūhܡҦ˳
ժҪһµ֪ʶȡȫûκαעϿУNAԶѵݣûڶԶȡʶṹ.÷ص㣺 ڴûκαעϿԶȡѵݣʹݹģԺܴ׹첻ͬĴϿ⣻ ȡĶṹиԣڷӦеʶȡ.Ϊ֤ЧԣBerlitz˾ʵϽвԣǰ50ʶṹ׼ȷʸߴ80%.
ؼʡʶṹ򣬾뺯ڶ
ͼšTP391
A NEW APPROACH TO PHRASE STRUCTURE RULE ACQUISITION
ZHU Jing-Bo, ZHANG Yue-Jie, and YAO Tian-Shun
(Institute of Computer Science, School of Information Science and Engineering, Northeastern University, Shenyang110006)
AbstractHere presented is a new approach to NP phrase structure rule acquisition based on multi-feature similarity estimation from corpora without bracketed and nonterminal labels. By computing the distance between a rule and all feature rules based on their local contextual information, the system could sort all rules by their distances. The smaller the distance, the larger the similarity. Experiments using Berlitz corpus show that the approach presented achieves a relatively high accuracy: 80% in the first 50 rules. This result demonstrates that training data acquisition based on NA assumption is effective for rule acquisition and parsing.
Key wordsnoun phrase structure rule, distance function, multi-feature-based similarity estimation
1
ĿǰȻԴϵͳûķľӷֹķѶȴʮָ.ѧϿͳƵķԶȡ.ЩԶȡԸʹõϿص࣬ѵϿǷж߽ע߷սűעȵ.һЩб߽ȫעͷսűǵӢķϿ⣬ܶоԱЩϿķ14.ͬʱӾзսעϿͳķĸʣӦӵķĸ.
ʵĿǰܶͳƵķȡ˺ܺõʵ̶ܴϿ⹹Ĵ.Ϊ˼˹עϿƿ⣬δӸٱע۵Ͽлȡࡢε֪ʶĻȡоԽԽ.ûзսעֱ߲עϿͳƷ.кܶϿֻб߽עûзսעEDRϿ5ݣATISϿ6ݵȵ.Baker7ݺInside-Outside㷨ûзսעϿлȡ޹ķʶ89.ǻȡĸķϸΪCNFChomsky normal-formѵϿģ󣬻ȡķļ㸴Ӷر.Thanaruk TheeramunkongManabu Okumura10ݴûзսעб߽עϿУþȡйķо䷨.ʵڶ̾ȡ˺ܺõЧ.
һЩ⣬һµ֪ʶȡȫûκαעϿУNAԶѵݣûڶԶȡʶṹ.ַص㣬ڴѵǴûκαעϿԶȡģʹѵݵĹģԺܴ󣬲Һ׹첻ͬĴϿ.Σ÷ȡĶṹиԣͬʱþֲģǰԣĸʷֲ.˶ṹʷֲڴıгȡʶڷӦõȵ.Ϊ֤÷ЧԣĲBerlitz˾ʵϽвԣʵ.
2뺯
ڽһЩڲԲͬʷֲƳ̶ȵĺļԣǳЩΪ뺯.ͨ뺯㲻ͬʷֲ֮ľ룬ԽСƳ̶Խ.Ҫ־뺯Kullback-Leibler11ݾľ뺯ͻڼʽľ뺯.ĵʵ֤־뺯Ч.
2.1ʷֲ
oʷֲPoʹȻƷmaximum likelihood estimateMLE.MLEʹѵPo=PMLE(c|o)
(1)
R(o,c)ʾoھֲcѵгֵĴ.ͬR(o)ʾoѵгֵĴ.趨R(o,c)=0PMLE(c|o)=0.Ҳ˵ܵϵĹģƣһĳһݶ(x,y)ûгѵУǿܵóݶԵPMLE(c|o)Ϊ0.ʵ鷢֣ݶԼʹѵУóĽҲڵ͸¼ϡ.صϡᵼʽΪûֵ̫.
Ϊ˽ϡ⣬һЩMLEĸĽ.˼뽫MLEΪȻݶԵ֮С1һָʸδеĿݶ.ǳ֮Ϊƽsmoothing.
JelinekMercer12ڲ巨ƽ.ǲü򻯵ڲ巨ƽʽ
(2)
R(o,c)ʾ(o,c)ѵгֵĴR(o)ʾoѵгֵĴ.|CT|ʾֲĵĿ.ĿǵľֲΪǰһʵĴԺͺһʵĴԣ˿Եó|CT|=13ִԡ13ִ=169־ֲ.ڱĵʵУòֵΪ0.99ȡ˺ܺý.
2.2Kullback-Leiblerľ뺯
ȶo1o2ΪͬĶCTΪֲģcCTʾĳһֲ.Po1Po2ֱʾo1o2ĸʷֲ.Kullback-Leibler빫ʽ£
(3)
ǿD(Po1Po2)+D(Po2Po1)ͬʷֲPo1Po2ľ룬뺯(Po1,Po2)£
(4)
2.3ڼʽľ뺯
ǰ(Po1, Po2,Pon)һռ䣬Ϳͨηʽ㲻ͬʷֲľ룬ӶǵƳ̶.
ʽľ뺯ʽ
(1) L1ʽ㹫ʽ£
(5)
(2) L2ʽ㹫ʽ£
(6)
ԣҽcCTPo1=Po2L1(Po1,Po2)=L2(Po1,Po2)=0.
3ѵݵԶ
3.1Nonambiguity-Ambiguity
Ϊ˷Nonambiguity-Ambiguity裬NA.ΪԶȡдԱעѵݣĶϿо֮һĴʻΪ󣬷֮Ϊ.4£
(1) ʵֻеһԵĴʻ㣬ӢĴʴʻ㡰we
(2) ̬ͨȷΨһԵĴʻ㣬ӢĶʴʻ㡰bought
(3) ͨǰ׺ͺ׺ȷΨһԵĴʻ㣬Ӣݴʴʻ㡰well-founded
(4) ӢĴʻ㣬֡ŵ.
1.Ϊ󼯺ϣAΪ󼯺ϣNΪ󼯺.ԣAȦN =.
NA裺æNѵϿ⣬ѵN-Gramģ͵ĲɶԦA紦ǿе.
ӢĴʻ㡰I͡report֪ӢĴʻ㡰IֻһִԴ(R)Դʻ㡰IʦNӢĴʻ㡰reportִԣ(N)Ͷ(V)Դʻ㡰reportʦA.
NA裬ǿԽԺͨ򵥴ΨһȷԵ󹹳ɴѵϣѵNԪ﷨ģ͵Ĳ.
3.2ѵݵԶ
ǲõԴBerlitz˾ʵϣδκδ˹ע.Ϊ˴ԴϿгȡѵݣǹʿ⣺ʿ⣺дԼ4ʻ㣬ÿʻдȫרҵʿ⣺дԼרҵʻ㣬ÿרҵʻдȫ.ӢĴʻԶ13£
1ӢĴʻ

NVݴA
DPX
C̾ER
MڴZW
O


ΪʵֶӢĴʻ̬ǹһڹ̬.ѵݵԶ̷Ϊ4裺
1. ԷӢĴʻʶ𣬰͡ͺͣ
2. ֱӲʿ̣ʿдΪע鲻עΪNULL
3. ͨͲ򶯴ʱǰ׺ͺ׺ӢĴʻ̬
4. ѵݵ.
һ˵̣
They reported the enemy to be 10 miles away.
1ʶ
They reported the enemy to be 10(M) miles away.(W)
2ʶ
They(R) reported(NULL) the(Z) enemy(N) to(P) be(V,X) 10(M) miles(NULL) away(D).(W)
3ʶ
They(R) reported(V) the(Z) enemy(N) to(P) be(V,X) 10(M) miles(N) away(D).(W)
4ʶ 
2ѵԶȡ

Ŵʻѵݴѵ
1They reported the enemy toR V Z N P
2beNULL
310 miles away.M N D W


3.3ѵݵԶȡ
ǲõԴBerlitz˾ʵϣʹúάݣûκαעԼ4Ӣľ.ݵĳȡP266΢PWindows98£ƽٶȴԼΪ15/.ѵݳȡͳ£ 
3ѵԶȡͳ

ԴϿģСѵϿģСNݹģСA
674116402722271394


Ϊ֤NAѵԶȡЧԣԶȡĴѵϿڴԶעӦУʴιʵϽпԲԣ׼ȷʴﵽ93%.ĽԶȡĴѵݽѵʶṹԶȡģ͵Ĳ. 
4ʶṹԶȡ
꣬ѧô߽ͷսעϿлȡ޹ķһЩѧֻж߽עûзսעϿлȡķ.ĸķȡõϿûж߽硢սʹԱעûڶƶԶȡʶṹ.ʵϣĻȡʶṹǾиԣͬʱ˾ֲϢǰԣʶṹĸʷֲ.Щ˾ֲĵЧ10.ķԶȡҪΪ5裺
Step1.ȹʶṹʽͬʱǵĸʷֲ
Step2.ʶṹʽѡϣòʽұ󳤶Ϊ5
Step3.ѡвʽĸʷֲ
Step4.ѡвʽĸʷֲʽĸʷֲľ룻
Step5.ƽԺѡвʽдС.
4.1ѡȡ͹
ʶṹܶ࣬ĵʵҪѡȡ3F ݴʼʿʶ ʼʿʶ ڴʼʿʶ.ǿԲòʽʽ3F F1NPA+N F2NP M+N F3NPZ+N.ݵ2.1Ĺʽ(2)ֱ3ĸʷֲ
(1) 즸(F1)=(P(c1|F1),P(c2|F1), ,P(cn|F1))ciCT
(2) 즸(F2)=(P(c1|F2),P(c2|F2), ,P(cn|F2))ciCT
(3) 즸(F3)=(P(c1|F3),P(c2|F3), ,P(cn|F3))ciCT
ʽĸʷֲ(F)=((F1), (F2), (F3)).
4.2ѡϵĹ
Ǽκζṹʶʵʶ󳤶Ϊ5ʻ.裬Ǻ׹ʶṹĺѡϦգ̷Ϊ5
(1) ȡ1EʽProNPEProʦգ 
(2) ȡ2E1E2ʽProNPE1 E2Proʦգ
(3) ȡ3E1E2E3ʽProNPE1 E2 E3Proʦգ 
(4) ȡ4E1E2E3E4ʽProNPE1 E2 E3 E4Proʦգ
(5) ȡ5E1E2E3E4E5ʽProNPE1 E2 E3 E4 E5Proʦգ
˵ַɵʶṹĿΪ402233㹫ʽΪ135+134+133+132+13=402233.ʵӴĿĲʽдǲϷĲʽ.Ϊ˼ٲҪʵвԭгɸѡ.ɸѡԭ£
ԭ1.òʽṹϿٳһΣ
ԭ2.šʡʡʡ̾ʡʲһʶﱾһһʻλó.
ǰѾɸѡĲʽΪѡϣڱĵʵУѡвʽĿ͵432.Ȼݵ2.1Ĺʽ(2)ѡвʽĸʷֲ.㷽£
ȡһʽProiʦ즸(Proi)=(P(c1|Proi),,P(cn|Proi))ciCT.
4.3ڶ
ǲõ2ڽܵľ뺯ѡвʽʽĸʷֲƶȣԽСƶԽ.ķʽʷֲ֮ƽƶ.ݵ2ڽܵ3뺯ʽ(4)(6)Ƶ3ƽDIS(Pro,F)ļ㹫ʽ.
æξ뺯ʽ(4)㹫ʽ1
(7)
L1뺯ʽ(5)㹫ʽ2
(8)
L2뺯ʽ(6)㹫ʽ3
(9)
УѡʽProʦʽFiFʵв3ʽn=3.
5ʵ
Ϊ֤÷Чԣʵ.ԴϿBerlitz˾ʵϣʹúάݣûκιڶ߽硢սʹԵıע.ڵ3ϸѵݵԶȡ̣ԶѵϿģСΪ402722ʴ.ʵɷֱ3ƽ㹫ʽ(7)(9)Զȡʶṹʽ.ͼòͬ㹫ʽƽԶɵĲʽĿ֮Ĺϵ.
