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à

Kỹ thuật điện tử & Khoa học máy tính 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 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 Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 33, 10 - 2014 91 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. leftfirst_token from i to next bracket; Kỹ thuật điện tử & Khoa học máy tính 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 8. delete(function lable) in left; 9. if (stack==null){ 10. newRule.leftleft ; 11. push(stack,newRule);} 12. else { 13. ruleTop  pop(stack) 14. if (ruleTop.right=) 15. ruleTop.rightleft 16. else 17. ruleTop.right ruleTop.right+”|” left; 18. push(stack,ruleTop); 19. newRule.left  left; 20. push(stack, newRule); 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. pop(stack); 25. else 26. Rulbeans[] pop(stack); 27. 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(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) Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 33, 10 - 2014 93 P(A ) = )( )( Afrequency Afrequency  (2.1) Bước 3. Chuyển PCFG thành PCFG ở dạng chuẩn Chomsky 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. Kỹ thuật điện tử & Khoa học máy tính 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 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 (LhRh) (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) (3.1) (vì P(T,S)=P(T)*P(S|T) và P(S|T)=1vậy nên P(T,S)=P(T)). Theo [5] P(Tk, S)= )( 1 ii n i RLP   (3.2), trong đó n là số luật tạo nên cây T, Tk 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 P(Tk,S) )2.3(    1 1 ( n t P TLt từt)* )( 2 1 hh n h RLP   (3.3) 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à chọn ra 1 cây phân tích có xác suất lớn nhất ( maxarg kT P(Tk|S)). Gọi T’ là cây phân tích thỏa mãn P(T’|S)= maxarg kT P(Tk|S), mặt khác ta lại có P(Tk|S)= )( ),( SP STP k P(T’,S)= maxarg kT )( ),( SP STP k , đối với mỗi cây thì P(S) là một hằng số (3.4)  maxarg kT )( ),( SP STP k chỉ phụ thuộc vào maxarg kT ),( STP k (3.5) Mà ),( STP k  )3.5(   1 1 ( n t P TLt từt)* )( 2 1 hh n h RLP   , trong đó P(TLt từt) của mỗi luật (TLt từt) là không thay đổi trong văn phạm (được tính từ Treebank). => Nên maxarg kT )( ),( SP STP k chỉ phụ thuộc vào maxarg kT )( 2 1 hh n h RLP   . Hay nói 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 các luật (LhRh) (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(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 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 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 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[] Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 33, 10 - 2014 95 - 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. for (j=1  LENGTH (words)) 2. for all{A|A->words[j] grammar } 3. table[j-1,j,A]  1 4. for (i= j-2  0) 5. for (k = i+1  j-1) 6. for all {A|ABC  grammar and table[i,k,B]>0 and table[k,j,C]>0} 7. if(table[i,j,A]<P(ABC)xtable[i,k,B]xtab le[k,j,C]) table[i,j,A]P(ABC)xtable[i, k, B]x table[i,j,C] back[i, j, A]  {k, B, C }; 8. return BUILD-TREE(back[1, LENGTH(words),S]), 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 Test dữ liệu Độ lớn khối Test (KB) Tỷ lệ (khối test và VietTreebank) Số luật CNF Recall Precision F1 129.00 0.01858 1274 0.68711 0.64117 F2 137.00 0.01973 1325 0.65934 0.68267 F3 169.00 0.02434 1884 0.75488 0.76713 F4 222.00 0.03198 1866 0.71864 0.71251 F5 413.00 0.05949 3007 0.76937 0.76071 F6 800.00 0.11523 5271 0.78085 0.79865 F7 867.00 0.12488 6409 0.75358 0.65969 F8 2682.88 0.38643 15696 0.78434 0.68908 F9 5478.40 0.78909 25560 0.79750 0.69610 F10 6010.88 0.86578 27577 0.81751 0.71505 Kỹ thuật điện tử & Khoa học máy tính 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 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 Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 33, 10 - 2014 97 [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 [8]. 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; E-mail: hathiphan@yahoo.com; Số điện thoại: 0948672246.