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
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
Phan thÞ Hµ, hµ H¶I Nam
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
cña v¨n ph¹m PCFG (Probability Context Free Grammar) tõ VietTreebank vµ thuËt
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
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õ
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
®Ç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µ
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õ
dùa vµo kho¶ng tr¾ng.
Keywords: CFG, PCFG, CYK, PCYK, Treebank, Probability Context Free Grammar, Parser
1. Giíi thiÖu
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
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ö
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.. .
§è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,
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
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
trong dù ¸n KC01.01/06-101, ®ã lµ kho ng÷ liÖu chó gi¶i có ph¸p (VietTreebank).
Trong VietTreebank, nhãm c¸c chuyªn gia ng«n ng÷ häc ®· thùc hiÖn viÖc chó gi¶i
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
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
ø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
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
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
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
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
vÒ VietTreebank ®-îc tr×nh bµy trong tµi liÖu [1].
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é
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
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
v¨n ph¹m PCFG (Probability Context Free Grammar) tõ VietTreebank, cµi ®Æt thö
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
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
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,
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
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,
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õ)
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
1
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."
90
Nghiªn cøu khoa häc c«ng nghÖ
cao nhÊt (®· chøng minh ë môc 3) nªn trong thuËt to¸n ph©n tÝch có ph¸p PCYK
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×
ph¶i tÝnh x¸c suÊt ®ã trong VietTreebank.
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
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
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
5 lµ kÕt luËn.
2. ThuËt to¸n trÝch rót tõ v¨n ph¹m tõ VietTreebank
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
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÷
kh¸c nhau, nh- tiÕng Anh [5], tiÕng §øc,… §èi víi tiÕng ViÖt, vÊn ®Ò khai th¸c
VietTreeBank cho nghiªn cøu vµ x©y dùng c¸c øng dông xö lý ng«n ng÷ cho tiÕng
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
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ã
tªn lµ VietTreebank, ph-¬ng ph¸p sö dông ë ®©y t-¬ng tù nh- ph-¬ng ph¸p cña
Roberto Valenti [8] vµ Jurafsky and Martin [5]. Nh-ng thuËt to¸n chi tiÕt trong
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
®-îc thùc hiÖn qua nh÷ng b-íc sau:
B-íc1. TrÝch rót c¸c luËt cña v¨n ph¹m CFG
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 )
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Ý
dô, Np->Lan). VietTreebank sÏ ®-îc ®äc tõng tÖp vµ t¸ch ra thµnh tõng c©u, bé luËt
trong mçi c©u ®-îc trÝch rót b»ng ThuËt to¸n 1.
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
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õ,
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
phÇn nÕu cã t-¬ng øng víi sè c¹nh trong ®å thÞ.
Trong thuËt to¸n, mçi phÇn tö trong m¶ng l-u tr÷ Rulebeans[] lµ mét luËt
(RuleBean) bao gåm 2 thµnh phÇn:
String left: nh·n phÝa bªn tr¸i cña luËt
String right: c¸c nh·n bªn ph¶i cña luËt, c¸ch nhau bëi dÊu ph¶y
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
®Ønh cña Stack.
ThuËt to¸n 1. Rulebeans[] RulbuildRules(String S)
input : Mét c©y ph©n tÝch S trong VietTreebank
ouput : Danh s¸ch c¸c luËt (RulBeans) phan tich duoc
1. {
2. Rulbeans[]=;
3. stack=null;
4. for (i= first bracket;i<= end bracket; i=next
bracket)
5. {
6. if (i =="(")/*TH ngoÆc më*/{
7. leftfirst_token from i to next bracket;
91
T¹p chÝ Nghiªn cøu KH&CN qu©n sù, Sè 33, 10 - 2014
Kü thuËt ®iÖn tö & Khoa häc m¸y tÝnh
8. delete(function lable) in left;
9. if (stack==null){
10.
11.
12. else {
newRule.leftleft ;
push(stack,newRule);}
13.
ruleTop pop(stack)
14.
if (ruleTop.right=)
ruleTop.rightleft
else
15.
16.
17.
ruleTop.right ruleTop.right+”|” left;
push(stack,ruleTop);
18.
19.
newRule.left left;
push(stack, newRule);
20.
21. }
22. else /*Tr-êng hîp ngoÆc ®ãng*/{
23.
if((chuçi ë gi÷a dÊu ngoÆc phÝa
tr-íc vµ dÊu ngoÆc thø i)!=Null)
24.
25.
26.
27.
pop(stack);
else
Rulbeans[] pop(stack);
28. }
29. }
30. return(Rulbeans)}
VÝ dô, víi mét c©u chó gi¶i có ph¸p VÝ dô : ng÷ ®o¹n: “NguyÔn Thanh Mü ch-a
bao giê nãi víi t«i lµ anh yªu n-íc”
<s>
(S(NP-SUB(Np NguyÔn Thanh Mü))
(VP(R ch-a)(P bao giê)(V nãi)
(PP-DOB(E víi)(P t«i))
(C lµ)
(SBAR-DOB(NP-SUB(N anh))
(VP(V yªu)(N n-íc)))))
(,,))
Sau khi trÝch rót, bé luËt thu ®-îc (®· lo¹i bá c¸c luËt sinh ra kÝ hiÖu kÕt, vÝ dô,
luËt R-> ch-a, P->bao giê) sÏ lµ:
NP->Np; PP->E|P;
NP->N; VP->V|N;
SBAR->NP|VP;
VP->R|P|V|PP|C|SBAR;
S->NP+VP
B-íc 2. ChuyÓn CFG thµnh phi ng÷ c¶nh kÕt hîp x¸c suÊt (PCFG)
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µ
mét kÝ tù bÊt kú kh¸c rçng) ®-îc tÝnh theo c«ng thøc (2.1)
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."
92
Nghiªn cøu khoa häc c«ng nghÖ
frequency(A )
frequency(A)
B-íc 3. ChuyÓn PCFG thµnh PCFG ë d¹ng chuÈn Chomsky
P(A ) =
(2.1)
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
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
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
ë d¹ng CNF, trong ®ã mçi luËt chØ cã thÓ ë 1 trong 2 d¹ng A->a hoÆc A->BC, trong
®ã a lµ kÝ hiÖu kÕt thóc, A,B,C lµ c¸c kÝ hiÖu kh«ng kÕt thóc.
Bé luËt thu ®-îc tõ v¨n ph¹m VietTreebank ë b-íc 2 sÏ kh«ng cßn d¹ng A->a,
hoÆc A-> n÷a mµ chØ cßn d¹ng A->B (x¸c suÊt p) hoÆc A->BCDE… (p)
- NÕu luËt cã d¹ng A->BC (p) th× gi÷ nguyªn
- NÕu luËt A->B (p) th× ®-îc chuyÓn lu«n thµnh A->B (p).
- NÕu luËt cã d¹ng A->BCDE….(p) th× ®-îc chuyÓn thµnh A->BC’
3. Ph©n tÝch có ph¸p tiÕng ViÖt víi v¨n ph¹m PCFG
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
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
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÷
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
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
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ú.
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ã
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
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µ
Martin qu¸ tr×nh xö lý ®-îc chia ra lµm hai giai ®o¹n:
Giai ®o¹n 1: T¸ch tõ.
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
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
sÏ ®-îc -u tiªn lùa chän.
§è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),
®©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
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ô
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
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
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,
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
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
qua hai giai ®o¹n:
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õ)
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
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].
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é
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
cao nhÊt sÏ ®-îc -u tiªn lùa chän.
93
T¹p chÝ Nghiªn cøu KH&CN qu©n sù, Sè 33, 10 - 2014
Kü thuËt ®iÖn tö & Khoa häc m¸y tÝnh
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ô
thuéc vµo x¸c suÊt cña c¸c luËt (LhRh) (víi Lh, Rh lµ c¸c nót kh«ng kÕt thóc) mµ
kh«ng phô thuéc vµo x¸c suÊt P(tõ lo¹i | tõ).
Chøng Minh:
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
nh·n tõ lo¹i ®-îc ®inh nghÜa lµ P(T,S),
P(T,S)=P(T)
(v× P(T,S)=P(T)*P(S|T) vµ P(S|T)=1vËy nªn P(T,S)=P(T)).
(3.1)
n
Theo [5] P(T , S)= P(L R ) (3.2), trong ®ã n lµ sè luËt t¹o nªn c©y T, T
k
k
i
i
i1
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
trong v¨n ph¹m.
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
n2=n-n1
(3.2)
n1
n2
P(Tk,S)
P(TL tõ )* P(L R ) (3.3)
h1
t
t
h
h
t1
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µ
P(T |S)). Gäi T’ lµ c©y ph©n
chän ra 1 c©y ph©n tÝch cã x¸c suÊt lín nhÊt (
argmax
k
Tk
P(Tk , S)
tÝch tháa m·n P(T’|S)=
P(T |S), mÆt kh¸c ta l¹i cã P(T |S)=
k
arg max
k
P(S)
Tk
P(Tk , S)
P(S)
P(T’,S)=
, ®èi víi mçi c©y th× P(S) lµ mét h»ng sè (3.4)
arg max
Tk
P(Tk , S)
P(S)
chØ phô thuéc vµo
P(Tk , S) (3.5)
arg max
arg max
Tk
Tk
n1
n2
(5.3)
Mµ P(Tk , S)
P(TL tõ )* P(L R ), trong ®ã P(TL tõ ) cña mçi
h1
t
t
t
t
h
h
t1
luËt (TLt tõt) lµ kh«ng thay ®æi trong v¨n ph¹m (®-îc tÝnh tõ Treebank).
n2
P(Tk , S)
=> Nªn
chØ phô thuéc vµo
P(L R ). Hay nãi
arg max
arg max
h
h
h1
P(S)
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
Tk
Tk
c¸c luËt (LhRh) (víi Lh, Rh lµ c¸c nót kh«ng kÕt thóc)
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
nhÊt b»ng thuËt to¸n PCYK cña Martin ta thay b»ng thuËt to¸n 2 (thay
P(TLttõ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
luËt TLttõt vµ còng kh«ng ph¶i tÝnh P(TLttõt)=>kh«ng cÇn ph¶i trÝch rót c¸c
luËt cã d¹ng (TLttõt), c¸c luËt nµy sÏ bÞ lo¹i bá ngay tõ khi trÝch rót c¸c luËt CFG
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
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.
ThuËt to¸n 2 Function PCYK()
Input:
- Chuçi tõ (words) ®· ®-íc t¸ch tõ vµ g¸n nh·n tõ lo¹i l-u trong m¶ng words[]
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."
94
Nghiªn cøu khoa häc c«ng nghÖ
- Bé luËt sinh (grammar) vµ x¸c suÊt t-¬ng øng cña v¨n ph¹m PCFG
Output:
- C©y ph©n tÝch cã x¸c suÊt cao nhÊt vµ s¸c xuÊt cña c©y
1.
2.
3.
4.
5.
6.
for (j=1 LENGTH (words))
for all{A|A->words[j] grammar }
table[j-1,j,A] 1
for (i= j-2 0)
for (k = i+1 j-1)
for all {A|ABC grammar and
table[i,k,B]>0 and table[k,j,C]>0}
7.
if(table[i,j,A]<P(ABC)xtable[i,k,B]xtab
le[k,j,C])
table[i,j,A]P(ABC)xtable[i,
B]x table[i,j,C]
k,
back[i, j, A] {k, B, C };
return BUILD-TREE(back[1, LENGTH(words),S]),
8.
table[1, LENGTH(words), S];
1.
2.
4. Thö nghiÖm vµ ®¸nh gi¸
PhÇn mÒm ph©n tÝch có ph¸p dùa trªn v¨n ph¹m PCFG ®· ®-îc nhãm t¸c gi¶
x©y dùng, trong ®ã cã 2 chøc n¨ng chÝnh, chøc n¨ng 1, trÝch rót tù ®éng c¸c luËt
cña v¨n ph¹m PCFG VietTreebank, chøc n¨ng 2, ph©n tÝch có ph¸p cho c©u ®Çu
vµo bÊt kú dùa trªn bé luËt cña v¨n ph¹m PCFG.
KÕt qu¶ trÝch rót ®-îc chØ ra ë ë b¶ng 4.1, d÷ liÖu huÊn luyÖn ®-îc chia ra thµnh
c¸c vïng, trong ®ã F1,F2,F3, F4,F7, F8 lµ c¸c vïng chøa d÷ liÖu kh«ng giao nhau
vµ lµ tËp con cña F9 F10 víi ®é lín kh¸c nhau ®-îc lÊy tõ VietTreebank
(6.78MB).
B¶ng 4. 1. Sè c¸c luËt thu ®-îc.
Khèi
§é lín
khèi Test
(KB)
Tû lÖ
(khèi test vµ
VietTreebank)
Test
d÷
liÖu
F1
Sè luËt
CNF
Recall
Precision
129.00
137.00
169.00
222.00
413.00
800.00
867.00
2682.88
5478.40
6010.88
0.01858
0.01973
0.02434
0.03198
0.05949
0.11523
0.12488
0.38643
0.78909
0.86578
1274
1325
1884
1866
3007
5271
6409
15696
25560
27577
0.68711
0.65934
0.75488
0.71864
0.76937
0.78085
0.75358
0.78434
0.79750
0.81751
0.64117
0.68267
0.76713
0.71251
0.76071
0.79865
0.65969
0.68908
0.69610
0.71505
F2
F3
F4
F5
F6
F7
F8
F9
F10
95
T¹p chÝ Nghiªn cøu KH&CN qu©n sù, Sè 33, 10 - 2014
Kü thuËt ®iÖn tö & Khoa häc m¸y tÝnh
KÕt qu¶ ch¹y ch-¬ng tr×nh cho thÊy sè l-îng luËt CNF t¨ng dÇn theo kÝch th-íc
cña VietTreebank chøng tá VietTreebank vÉn ch-a ®ñ ®é lín. §é chÝnh x¸c cña bé
ph©n tÝch ®-îc tÝnh nh- sau: §é chÝnh x¸c dùa vµo cÆp ngoÆc (i, j, nh·n thµnh
phÇn) cña c©y ph©n tÝch ®Çu ra d-íi d¹ng ®Æt ngoÆc, trong ®ã:
Recall = (Sè cÆp ngoÆc ®óng cña c©y sinh ra)/(sè cÆp ngoÆc ®óng cña c©y
chuÈn);
Precision=(Sè cÆp ngoÆc ®óng cña c©y sinh ra)/(Sè cÆp ngoÆc cña c©y sinh ra).
§ång thêi nhãm t¸c gi¶ còng cµi ®Æt tuËt to¸n theo c¸ch tiÕp cËn cña Martin vµ
ch¹y thö nghiÖm trªn cïng mét sè c©u ®Çu vµo th× thuËt to¸n c¶i tiÕn theo h-íng
tiÕp cËn cña nhãm t¸c gi¶ cho kÕt qu¶ tèt h¬n. Cô thÓ, khi ch¹y thö 30 c©u tiÕng
ViÖt trªn 200 c©u d÷ liÖu huÊn luyÖn, ph-¬ng ph¸p c¶i tiÕn cña nhãm t¸c gi¶ cho
kÕt qu¶ ph©n tÝch có ph¸p (®é chÝnh x¸c 67.7%) tèt h¬n ph-¬ng ph¸p cña
Jurafsky vµ Martin (®é chÝnh x¸c 62.2%).
KÕt luËn
Bµi b¸o nµy tr×nh bµy vÒ viÖc ph¸t triÓn thuËt to¸n trÝch rót bé luËt v¨n ph¹m
CFG, PCFG tõ VietTreebank vµ thuËt to¸n ph©n tÝch có ph¸p ®-îc c¶i tiÕn tõ thuËt
to¸n ph©n tÝch có ph¸p PCYK cña Martin. X©y dùng hÖ thèng trÝch rót tù ®éng c¸c
luËt cho v¨n ph¹m PCFG vµ bé ph©n tÝch có ph¸p cho c©u tiÕng ViÖt trªn v¨n ph¹m
PCFG. Víi bé ph©n tÝch có ph¸p tèt, VietTreebank cã thÓ ®-îc t¸i më réng b»ng
c¸ch ph©n tÝch tù ®éng có ph¸p cña c¸c c©u ®· chó gi¶i tõ lo¹i tiÕng ViÖt ®-îc lÊy
trùc tiÕp tõ Internet. Tuy nhiªn, nÕu c¸c bé ph©n tÝch có ph¸p hiÖn t¹i cho kÕt qu¶
ch-a cao, VietTreebank cã thÓ më réng b»ng c¸ch b¸n tù ®éng, tøc lµ sö dông bé
ph©n tÝch có ph¸p ®Ó chó gi¶i tù ®éng có ph¸p tõng c©u, sau ®ã, nhµ chó gi¶i cã thÓ
chØnh söa tõng c©u nÕu thÊy cÇn thiÕt. Ph-¬ng ph¸p nµy mang l¹i tÝch chÝnh x¸c
cho VietTreebank vµ gi¶m thiÓu c«ng søc cho c¸c nhµ chó gi¶i.
Tµi liÖu tham kh¶o
[1]. NguyÔn Ph-¬ng Th¸i vµ c¸c céng sù, B¸o c¸o kÕt qu¶ s¶n phÈm SP 7.3- Kho
ng÷ liÖu tiÕng ViÖt cã chó gi¶i, QuyÓn 1, 2009, KC01/01, Dù ¸n VLSP,2009.14
[2]. NguyÔn Quèc ThÓ, Lª Thanh H-¬ng, Ph©n tÝch có ph¸p tiÕng ViÖt sö dông v¨n
ph¹m phi ng÷ c¶nh tõ vùng hãa kÕt hîp x¸c suÊt, FAIR conference, Nha
Trang, ViÖt Nam, 2007.
[3]. Uû ban khoa häc x· héi ViÖt Nam, Ng÷ ph¸p tiÕng ViÖt, NXB Khoa häc X·
héi, Hµ néi, 1993.
[4]. Chomsky, N. Three models for the description of language. IRI Transactions
on Information Theory, 2(3), 113-124. 1956. 39
[5]. D.Jurafsky, J. H Martin, Introduction to natural language processing,
computational linguistics and speech recognition, Prentice Hall, Second
Edition, 2009.
[6]. Nguyen P.T., Xuan L. V., Nguyen T. M. H., Nguyen V. H., Le H. P., Building
a largesyntactically-annotated corpus of Vietnamese. In Proceedings of the
3rd Linguistic AnnotationWorkshop,ACL-IJCNLP, Singapore. 2009.78
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."
96
Nghiªn cøu khoa häc c«ng nghÖ
[7]. P.L.Hong, A.Roussanaly, T.M.H.Nguyen, M. Rossignol, An empirical study of
maximum entropy approach for part-of-speech tagging of Vietnamese texts,
TALN 2010, MontrÐal, 19–23 juillet 2010.81
ABSTRACT
EXPLOITING THE SYNTAX-ANNOTATED CORPUS
FOR ANALYSING VIETNAMESE SYNTAX
This paper presents algorithms for extracting the rules of
PCFG (Probability Context Free Grammar) from VietTreeBank, analysing
the Vietnamese syntax and building the Vietnamese syntax analyzer based on
PCFG. The syntax analyser proposed by Jurafsky and Martin [1] has been
extended for Vietnamese syntax analysis. Applied for Vietnamese language,
each input sentence is labeled by the available tool. Meanwhile, in Jurafsky
and Martin algorithm, each input sentence is a sequence of unlabeled words,
which are separated by spaces.
Keywords: CFG, PCFG, CYK, PCYK, Treebank, Probability Context Free Grammar, Parser
Nhận bài ngày 15 tháng 8 năm 2014
Hoàn thiện ngày 20 tháng 9 năm 2014
Chấp nhận đăng ngày 25 tháng 9 năm 2014
§Þa chØ: Häc viÖn C«ng nghÖ B-u chÝnh ViÔn th«ng, 122 Hoµng Quèc ViÖt, Hµ Néi;
97
T¹p chÝ Nghiªn cøu KH&CN qu©n sù, Sè 33, 10 - 2014
8 trang
15/01/2024
9220
Free
Bạn đang xem tài liệu "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", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- khai_thac_kho_ngu_lieu_chu_giai_cu_phap_cho_phan_tich_cu_pha.pdf
