Khai thác kho ngữ liệu chú giải cú pháp cho phân tích cú pháp tiếng Việt

Kü thuËt ®iÖn tö & Khoa häc m¸y tÝnh<br /> <br /> <br /> Khai th¸c kho ng÷ liÖu chó gi¶i có ph¸p<br /> cho ph©n tÝch có ph¸p tiÕng ViÖt<br /> Phan thÞ Hµ, hµ H¶I Nam<br /> Tãm t¾t: Bµi b¸o ®· tr×nh bµy viÖc ph¸t triÓn thuËt to¸n trÝch rót tù ®éng bé luËt<br /> cña v¨n ph¹m PCFG (Probability Context Free Grammar) tõ VietTreebank vµ thuËt<br /> to¸n ph©n tÝch có ph¸p tiÕng ViÖt, x©y dùng bé ph©n tÝch có ph¸p tiÕng ViÖt trªn v¨n<br /> ph¹m PCFG. Trong ®ã thuËt to¸n ph©n tÝch có ph¸p cho mçi c©u ®­îc ph¸t triÓn tõ<br /> thuËt to¸n cña Jurafsky and Martin [5]. Víi c¸ch tiÕp cËn cho tiÕng ViÖt, mét c©u<br /> ®Çu vµo ®· ®­îc g¸n nh·n tõ lo¹i b»ng c«ng cô cã s½n, trong khi ®èi víi Jurafsky vµ<br /> Martin th× c©u ®Çu vµo lµ mét chuçi c¸c tõ ch­a ®­îc g¸n nh·n tõ lo¹i, viÖc t¸ch tõ<br /> dùa vµo kho¶ng tr¾ng.<br /> Keywords: CFG, PCFG, CYK, PCYK, Treebank, Probability Context Free Grammar, Parser<br /> <br /> <br /> 1. Giíi thiÖu<br /> Ph©n tÝch có ph¸p lµ b­íc quan träng trong qu¸ trÝnh xö lý ng«n ng÷ tù nhiªn, víi<br /> bé ph©n tÝch có ph¸p chÊt l­îng cao sÏ gióp t¨ng tÝnh hiÖu qu¶ cña c¸c hÖ thèng xö<br /> lý ng«n ng÷ tù nhiªn nh­ dÞch m¸y, tãm t¾t v¨n b¶n, c¸c hÖ thèng hái ®¸p.. .<br /> §èi víi tiÕng ViÖt, mäi bé ph©n tÝch có ph¸p ®Òu cÇn bé luËt có ph¸p tiÕng ViÖt,<br /> hay cßn gäi lµ v¨n ph¹m cho tiÕng ViÖt, ®­îc biÓu diÔn bëi mét hÖ v¨n ph¹m h×nh<br /> thøc cô thÓ nµo ®ã. Bé luËt nµy cã thÓ thu thËp tõ mét sè kho ng÷ liÖu ®­îc x©y dùng<br /> trong dù ¸n KC01.01/06-101, ®ã lµ kho ng÷ liÖu chó gi¶i có ph¸p (VietTreebank).<br /> Trong VietTreebank, nhãm c¸c chuyªn gia ng«n ng÷ häc ®· thùc hiÖn viÖc chó gi¶i<br /> th«ng tin có ph¸p cho mét kho v¨n b¶n tiÕng ViÖt theo ®Þnh d¹ng chó gi¶i thµnh phÇn<br /> vµ ®· ®­îc m· hãa d­íi d¹ng ®Æt ngoÆc. Kho ng÷ liÖu ®­îc chia lµm ba tËp t­¬ng<br /> øng víi ba møc g¸n nh·n lµ t¸ch tõ, g¸n nh·n tõ lo¹i vµ g¸n nh·n có ph¸p. TËp g¸n<br /> nh·n có ph¸p gåm 10471 c©u (225085 ®¬n vÞ tõ vùng). §é dµi cña c¸c c©u n»m trong<br /> kho¶ng tõ 2 tíi 105 tõ, víi ®é dµi trung b×nh lµ 21.75 tõ. Cã 9314 c©u (chiÕm<br /> 88.95%) cã ®é dµi kh«ng lín h¬n 40 tõ. C¸c c©y có ph¸p cã chiÒu cao ®a sè n»m<br /> trong kho¶ng tõ 5 ®Õn 10, phæ biÕn nhÊt lµ b»ng 7 (1436 c©u). C¸c th«ng tin chi tiÕt<br /> vÒ VietTreebank ®­îc tr×nh bµy trong tµi liÖu [1].<br /> Dùa vµo th«ng tin có ph¸p trong VietTreebank bµi b¸o ®i s©u vµo x©y dùng bé<br /> luËt cña v¨n ph¹m phôc vô cho bµi to¸n ph©n tÝch có ph¸p tiÕng ViÖt. Trong ®ã, bµi<br /> b¸o ®· tr×nh bµy viÖc ph¸t triÓn vµ x©y dùng thuËt to¸n trÝch rót tù ®éng bé luËt cña<br /> v¨n ph¹m PCFG (Probability Context Free Grammar) tõ VietTreebank, cµi ®Æt thö<br /> nghiÖm vµ ®¸nh gi¸. §ång thêi x©y dùng ®­îc bé ph©n tÝch có ph¸p tiÕng ViÖt trªn<br /> v¨n ph¹m PCFG, trong ®ã thuËt to¸n ph©n tÝch có ph¸p cho mçi c©u ®­îc c¶i tiÕn<br /> tõ thuËt to¸n PCYK cña Jurafsky and Martin [5]. Víi c¸ch tiÕp cËn cho tiÕng ViÖt,<br /> mét c©u ®Çu vµo ®· ®­îc g¸n nh·n tõ lo¹i b»ng c«ng cô cã s½n, trong khi ®èi víi<br /> Jurafsky vµ Martin th× c©u ®Çu vµo lµ mét chuçi c¸c tõ ch­a ®­îc g¸n nh·n tõ lo¹i,<br /> viÖc t¸ch tõ dùa vµo kho¶ng tr¾ng. Sau khi g¸n nh·n tõ lo¹i x¸c suÊt P(tõ lo¹i| tõ)<br /> trong mét v¨n ph¹m kh«ng lµm ¶nh h­ëng ®Õn viÖc t×m c©y ph©n tÝch cã x¸c suÊt<br /> <br /> <br /> 1<br /> http://vlsp.vietlp.org:8080<br /> <br /> <br /> 90 P. T. Hµ, H. H¶i Nam, "Khai th¸c kho ng÷ liÖu… ph©n tÝch có ph¸p tiÕng ViÖt."<br /> Nghiªn cøu khoa häc c«ng nghÖ<br /> <br /> cao nhÊt (®· chøng minh ë môc 3) nªn trong thuËt to¸n ph©n tÝch có ph¸p PCYK<br /> nhãm t¸c gi¶ ®· ®­îc ®iÒu chØnh b»ng c¸ch thay x¸c suÊt P(tõ lo¹i|tõ)=1 thay v×<br /> ph¶i tÝnh x¸c suÊt ®ã trong VietTreebank.<br /> Bè côc bµi b¸o ®­îc chia thµnh c¸c môc nh­ sau: Môc 1 lµ giíi thiÖu, môc 2<br /> tr×nh bµy vÒ thuËt to¸n trÝch rót v¨n ph¹m PCFG tõ VietTreebank, môc 3 lµ ph©n<br /> tÝch có ph¸p tiÕng ViÖt víi v¨n ph¹m PCFG, môc 4 lµ thñ nghiÖm vµ ®¸nh gi¸, môc<br /> 5 lµ kÕt luËn.<br /> <br /> 2. ThuËt to¸n trÝch rót tõ v¨n ph¹m tõ VietTreebank<br /> Ph­¬ng ph¸p trÝch rót tù ®éng c¸c luËt v¨n ph¹m CFG, PCFG tõ ng©n hµng c©y<br /> có ph¸p phôc vô cho viÖc ph©n tÝch có ph¸p ®· ®­îc sö dông cho nhiÒu ng«n ng÷<br /> kh¸c nhau, nh­ tiÕng Anh [5], tiÕng §øc,… §èi víi tiÕng ViÖt, vÊn ®Ò khai th¸c<br /> VietTreeBank cho nghiªn cøu vµ x©y dùng c¸c øng dông xö lý ng«n ng÷ cho tiÕng<br /> ViÖt ®­îc ph¸t triÓn [1, 5]. ë ®©y bµi b¸o tr×nh bµy ph­¬ng ph¸p trÝch rót c¸c luËt<br /> v¨n ph¹m phi ng÷ c¶nh kÕt hîp x¸c suÊt tõ ng©n hµng kho ng÷ liÖu tiÕng ViÖt cã<br /> tªn lµ VietTreebank, ph­¬ng ph¸p sö dông ë ®©y t­¬ng tù nh­ ph­¬ng ph¸p cña<br /> Roberto Valenti [8] vµ Jurafsky and Martin [5]. Nh­ng thuËt to¸n chi tiÕt trong<br /> tõng b­íc cña ph­¬ng ph¸p ®· ®­îc x©y dùng tõ ®Çu. VÒ c¬ b¶n qu¸ tr×nh trÝch rót<br /> ®­îc thùc hiÖn qua nh÷ng b­íc sau:<br /> B­íc1. TrÝch rót c¸c luËt cña v¨n ph¹m CFG<br /> Trong b­íc nµy sÏ cho phÐp trÝch rót c¸c luËt cña v¨n ph¹m phi ng÷ c¶nh (CFG )<br /> tõ VietTreebank ë d¹ng ngoÆc vµ ®ång thêi lo¹i bá c¸c luËt sinh ra c¸c tõ kÕt (vÝ<br /> dô, Np->Lan). VietTreebank sÏ ®­îc ®äc tõng tÖp vµ t¸ch ra thµnh tõng c©u, bé luËt<br /> trong mçi c©u ®­îc trÝch rót b»ng ThuËt to¸n 1.<br /> ThuËt to¸n 1 ®· sö dông Stack ®Ó l­u tr÷ t¹m thêi c¸c luËt trÝch rót tõ mçi c©y<br /> ph©n tÝch, ®é phøc t¹p lµ O(n+m), trong ®ã n lµ sè nh·n thµ#nh phÇn (c©u, côm tõ,<br /> tõ lo¹i) t­¬ng øng víi sè ®Ønh trong ®å thÞ, m lµ mèi liªn hÖ gi÷a c¸c nh·n thµ#nh<br /> phÇn nÕu cã t­¬ng øng víi sè c¹nh trong ®å thÞ.<br /> Trong thuËt to¸n, mçi phÇn tö trong m¶ng l­u tr÷ Rulebeans[] lµ mét luËt<br /> (RuleBean) bao gåm 2 thµnh phÇn:<br /> String left: nh·n phÝa bªn tr¸i cña luËt<br /> String right: c¸c nh·n bªn ph¶i cña luËt, c¸ch nhau bëi dÊu ph¶y<br /> newRule vµ rulTop: lµ 2 luËt dïng ®Ó ®¸nh dÊu luËt míi ®­îc t¹o ra vµ luËt trªn<br /> ®Ønh cña Stack.<br /> ThuËt to¸n 1. Rulebeans[] RulbuildRules(String S)<br /> input : Mét c©y ph©n tÝch S trong VietTreebank<br /> ouput : Danh s¸ch c¸c luËt (RulBeans) phan tich duoc<br /> 1. {<br /> 2. Rulbeans[]=;<br /> 3. stack=null;<br /> 4. for (i= first bracket;i ch­a, P->bao giê) sÏ lµ:<br /> NP->Np; PP->E|P;<br /> NP->N; VP->V|N;<br /> SBAR->NP|VP;<br /> VP->R|P|V|PP|C|SBAR;<br /> S->NP+VP<br /> B­íc 2. ChuyÓn CFG thµnh phi ng÷ c¶nh kÕt hîp x¸c suÊt (PCFG)<br /> X¸c suÊt ®iÒu kiÖn mçi luËt cã d¹ng A  (víi A lµ kÝ tù kh«ng kÕt thóc,  lµ<br /> mét kÝ tù bÊt kú kh¸c rçng) ®­îc tÝnh theo c«ng thøc (2.1)<br /> <br /> <br /> 92 P. T. Hµ, H. H¶i Nam, "Khai th¸c kho ng÷ liÖu… ph©n tÝch có ph¸p tiÕng ViÖt."<br /> Nghiªn cøu khoa häc c«ng nghÖ<br /> <br /> frequency ( A   )<br /> P(A ) = (2.1)<br /> frequency ( A)<br /> B­íc 3. ChuyÓn PCFG thµnh PCFG ë d¹ng chuÈn Chomsky<br /> ThuËt to¸n ph©n tÝch có ph¸p PCYK [4] chØ thùc hiÖn ®­îc víi c¸c luËt thuéc<br /> v¨n ph¹m phi ng÷ c¶nh kÕt hîp x¸c suÊt ë d¹ng chuÈn Chomsky (CNF). Nªn trong<br /> b­íc nµy ph¶i chuyÓn c¸c luËt PCFG thu ®­îc thµnh c¸c luËt cña v¨n ph¹m PCFG<br /> ë d¹ng CNF, trong ®ã mçi luËt chØ cã thÓ ë 1 trong 2 d¹ng A->a hoÆc A->BC, trong<br /> ®ã a lµ kÝ hiÖu kÕt thóc, A,B,C lµ c¸c kÝ hiÖu kh«ng kÕt thóc.<br /> Bé luËt thu ®­îc tõ v¨n ph¹m VietTreebank ë b­íc 2 sÏ kh«ng cßn d¹ng A->a,<br /> hoÆc A-> n÷a mµ chØ cßn d¹ng A->B (x¸c suÊt p) hoÆc A->BCDE… (p)<br /> - NÕu luËt cã d¹ng A->BC (p) th× gi÷ nguyªn<br /> - NÕu luËt A->B (p) th× ®­îc chuyÓn lu«n thµnh A->B (p).<br /> - NÕu luËt cã d¹ng A->BCDE….(p) th× ®­îc chuyÓn thµnh A->BC’<br /> 3. Ph©n tÝch có ph¸p tiÕng ViÖt víi v¨n ph¹m PCFG<br /> Mét h­íng tiÕp cËn trong viÖc x©y dùng bé ph©n tÝch có ph¸p lµ sö dông ph­¬ng<br /> ph¸p thèng kª. Ph­¬ng ph¸p nµy sÏ sö dông bé luËt trong v¨n ph¹m CFG (Context<br /> Free Grammar)cïng víi th«ng tin x¸c suÊt cña mçi luËt (gäi lµ v¨n ph¹m phi ng÷<br /> c¶nh kÕt hîp x¸c suÊt - PCFG) ®Ó ®­a ra c©y ph©n tÝch có ph¸p cã x¸c suÊt cao nhÊt<br /> cho mçi c©u ®Çu vµo. ViÖc lùa chän nµy sÏ gi¶m thiÓu ®­îc vÊn ®Ò nhËp nh»ng so<br /> víi v¨n ph¹m phi ng÷ c¶nh khi ph©n tÝch có ph¸p mét c©u bÊt kú.<br /> Bé ph©n tÝch có ph¸p nhËn ®Çu vµo lµ mét c©u bÊt kú, ®Çu ra ng­êi sö dông cã<br /> thÓ lùa chän mÆc ®Þnh c©y ph©n tÝch cã x¸c suÊt lín nhÊt hoÆc tÊt c¶ c¸c c©y ph©n<br /> tÝch cã thÓ cã cïng th«ng tin x¸c suÊt kÌm theo. Theo ph­¬ng ph¸p cña Jurafsky vµ<br /> Martin qu¸ tr×nh xö lý ®­îc chia ra lµm hai giai ®o¹n:<br /> Giai ®o¹n 1: T¸ch tõ.<br /> Giai ®o¹n 2: Ph©n tÝch có ph¸p cña c©u ®· ®­îc g¸n nh·n tõ lo¹i, bé ph©n tÝch<br /> có ph¸p sÏ ph©n tÝch c©u thµnh c¸c c©y có ph¸p cã thÓ vµ c©y cã x¸c suÊt cao nhÊt<br /> sÏ ®­îc ­u tiªn lùa chän.<br /> §èi víi tiÕng ViÖt c«ng ®o¹n t¸ch tõ nµy rÊt phøc t¹p v× cßn cã tõ kÐp (®a ©m),<br /> ®©y lµ ®iÓm kh¸c so víi tiÕng tiÕng Anh hoÆc c¸c tiÕng kh¸c viÖc t¸ch tõ ®¬n gi¶n<br /> chØ dùa vµo kho¶ng trèng. HiÖn nay dù ¸n KC01/01 ®· cung cÊp mét sè c«ng cô<br /> tiÒn xö lý cho tiÕng ViÖt nh­ lµ t¸ch tõ, g¸n nh·n tõ lo¹i,…Dùa vµo ®Æc ®iÓm cña<br /> tiÕng ViÖt vµ ph­¬ng ph¸p cña Martin, bµi b¸o ®Ò xuÊt sö dông c«ng cô g¸n nh·n<br /> tõ lo¹i tù ®éng c©u tiÕng ViÖt (®ång thêi t¸ch tõ lu«n) vµ sau ®ã ph©n tÝch có ph¸p,<br /> c¸ch tiÕp cËn nµy còng sÏ gi¶m thiÓu ®­îc sù nhËp nh»ng trong viÖc sinh c©y ph©n<br /> tÝch so víi c¸ch tiÕp cËn cña Jurafsky vµ Martin. Qu¸ tr×nh xö lý ®­îc thùc hiÖn<br /> qua hai giai ®o¹n:<br /> Giai ®o¹n 1: Thay cho viÖc t¸ch tõ th× g¸n lu«n nh·n tõ lo¹i (®ång thêi t¸ch tõ)<br /> b»ng c¸ch sö dông bé c«ng cô g¸n nh·n tõ lo¹i ®· cã s½n. ë ®©y ®· sö dông c«ng<br /> cô g¸n nh·n tõ lo¹i tiÕng ViÖt cña nhãm t¸c gi¶ Lª Hång Ph­¬ng [7].<br /> Giai ®o¹n 2: Ph©n tÝch có ph¸p cña c©u ®· ®­îc t¸ch tõ vµ g¸n nh·n tõ lo¹i, bé<br /> ph©n tÝch có ph¸p sÏ ph©n tÝch c©u thµnh c¸c c©y có ph¸p cã thÓ vµ c©y cã x¸c suÊt<br /> cao nhÊt sÏ ®­îc ­u tiªn lùa chän.<br /> <br /> <br /> T¹p chÝ Nghiªn cøu KH&CN qu©n sù, Sè 33, 10 - 2014 93<br />  Kü thuËt ®iÖn tö & Khoa häc m¸y tÝnh<br /> <br /> Theo h­íng tiÕp cËn nµy th× viÖc lùa chän c©y cã x¸c suÊt cao nhÊt chØ phô<br /> thuéc vµo x¸c suÊt cña c¸c luËt (LhRh) (víi Lh, Rh lµ c¸c nót kh«ng kÕt thóc) mµ<br /> kh«ng phô thuéc vµo x¸c suÊt P(tõ lo¹i | tõ).<br /> Chøng Minh:<br /> X¸c suÊt kÕt hîp gi÷a mét c©y ph©n tÝch T cô thÓ vµ mét c©u S ®· t¸ch tõ vµ g¸n<br /> nh·n tõ lo¹i ®­îc ®inh nghÜa lµ P(T,S),<br /> P(T,S)=P(T) (3.1)<br /> (v× P(T,S)=P(T)*P(S|T) vµ P(S|T)=1vËy nªn P(T,S)=P(T)).<br /> n<br /> Theo [5] P(Tk, S)=  P(Li  Ri ) (3.2), trong ®ã n lµ sè luËt t¹o nªn c©y T, Tk<br /> i 1<br /> lµ mét c©y ph©n tÝch bÊt kú cña c©u S, Li vµ Ri lµ vÕ tr¸i vµ vÕ ph¶i cña luËt thø i<br /> trong v¨n ph¹m.<br /> Gi¶ sö c©u S cã n1 tõ => sau khi g¸n nh·n cã n1 luËt (TLt  tõt) (t=1  n1). §Æt<br /> n2=n-n1<br /> ( 3.2 ) n1 n2<br />  P(Tk,S)   P( TLt  tõt)*  P(Lh  Rh ) (3.3)<br /> t 1 h 1<br /> X¸c suÊt kÕt hîp cña c¸c c©y ph©n tÝch ®èi víi mét c©u cô thÓ sÏ ®­îc tÝnh vµ<br /> chän ra 1 c©y ph©n tÝch cã x¸c suÊt lín nhÊt ( arg max P(Tk|S)). Gäi T’ lµ c©y ph©n<br /> Tk<br /> <br /> P(Tk , S )<br /> tÝch tháa m·n P(T’|S)= arg max P(Tk|S), mÆt kh¸c ta l¹i cã P(Tk|S)=<br /> Tk P(S )<br /> P(Tk , S )<br />  P(T’,S)= arg max , ®èi víi mçi c©y th× P(S) lµ mét h»ng sè (3.4)<br /> Tk P(S )<br /> P(Tk , S )<br />  arg max chØ phô thuéc vµo arg max P(Tk , S ) (3.5)<br /> Tk P(S ) Tk<br /> ( 5.3) n1 n2<br /> Mµ P(Tk , S )   P( TLt  tõt)*  P(Lh  Rh ) , trong ®ã P(TLt  tõt) cña mçi<br /> t 1 h 1<br /> <br /> luËt (TLt  tõt) lµ kh«ng thay ®æi trong v¨n ph¹m (®­îc tÝnh tõ Treebank).<br /> P (Tk , S ) n2<br /> => Nªn arg max chØ phô thuéc vµo arg max  P(Lh  Rh ) . Hay nãi<br /> Tk P(S ) Tk h 1<br /> <br /> c¸ch kh¸c viÖc lùa chän c©y cã x¸c suÊt cao nhÊt chØ phô thuéc vµo x¸c suÊt cña<br /> c¸c luËt (LhRh) (víi Lh, Rh lµ c¸c nót kh«ng kÕt thóc)<br /> VËy ®Ó ®¬n gi¶n vµ kh«ng gi¶m tÝnh tæng qu¸t cho viÖc t×m c©y cã x¸c suÊt cao<br /> nhÊt b»ng thuËt to¸n PCYK cña Martin ta thay b»ng thuËt to¸n 2 (thay<br /> P(TLttõt)=1 t¹i dßng 3 cña thuËt to¸n ), lµm nh­ thÕ nµy ®ì tèn bé nhí ®Ó l­u c¸c<br /> luËt TLttõt vµ còng kh«ng ph¶i tÝnh P(TLttõt)=>kh«ng cÇn ph¶i trÝch rót c¸c<br /> luËt cã d¹ng (TLttõt), c¸c luËt nµy sÏ bÞ lo¹i bá ngay tõ khi trÝch rót c¸c luËt CFG<br /> tõ Treebank, ®iÒu nµy ®· ®­îc tr×nh bµy trong thuËt to¸n 1. C¸ch lµm nµy còng<br /> gi¶m thiÓu ®­îc sù nhËp nh»ng trong viÖc sinh c©y cña bé ph©n tÝch có ph¸p.<br /> <br /> ThuËt to¸n 2 Function PCYK()<br /> Input:<br /> - Chuçi tõ (words) ®· ®­íc t¸ch tõ vµ g¸n nh·n tõ lo¹i l­u trong m¶ng words[]<br /> <br /> <br /> 94 P. T. Hµ, H. H¶i Nam, "Khai th¸c kho ng÷ liÖu… ph©n tÝch có ph¸p tiÕng ViÖt."<br />  Nghiªn cøu khoa häc c«ng nghÖ<br /> <br /> - Bé luËt sinh (grammar) vµ x¸c suÊt t­¬ng øng cña v¨n ph¹m PCFG<br /> Output:<br /> - C©y ph©n tÝch cã x¸c suÊt cao nhÊt vµ s¸c xuÊt cña c©y<br /> <br /> 1. for (j=1  LENGTH (words))<br /> 2. for all{A|A->words[j] grammar }<br /> 3. table[j-1,j,A]  1<br /> 4. for (i= j-2  0)<br /> 5. for (k = i+1  j-1)<br /> 6. for all {A|ABC  grammar and<br /> table[i,k,B]>0 and table[k,j,C]>0}<br /> 7.<br /> if(table[i,j,A]