19/05/2020 05:59:50 AM

Ứng dụng

THIẾT KẾ VÀ CÀI ĐẶT THỬ NGHIỆM PHÂN TÍCH CÚ PHÁP

Như chúng ta đã giới thiệu ở trên, việc phân tích cú pháp cho ngôn ngữ tiếng Việt sẽ không thể thực hiện nếu chúng ta không có kho dữ liệu corpus hay treebank cho nó. Và hiện cũng chưa có một treebank nào cho tiếng Việt. Chính vì thế, tác giả đã nghiên cứu và xây dựng nó dựa trên nền tảng Penn treebank có sẳn của tiếng Anh, tất nhiên sẽ gặp khó khăn về cú pháp khác biệt giữa hai ngôn ngữ Anh - Việt. Với khả năng hạn chế về ngôn ngữ, tác giả không thể liệt kê tất cả sự khác biệt về cú pháp cũng như vị trí từ loại nằm trong câu của mỗi ngôn ngữ. Với sự phân tích và liệt kê ở chương 03 và một số cú pháp khác biệt trong quá trình xây dựng luật sinh cho tiếng Việt, hy vọng nó sẽ giải quyết được những yêu cầu đặt ra.

2.1. Mô hình thiết kế đề tài

Quá trình thiết kế đề tài được chia làm hai giai đoạn sau:

2.1.1. Phân tích Peen treebank và xây dựng tập luật sinh cho tiếng Việt

Giai đoạn phân tích treebank và xây dựng tập luật sinh cho tiếng Việt được mô hình hóa như sau:

Hình 2.1: Mô hình phân tích treebank và xây dựng luật sinh tiếng Việt

Từ Penn treebank đã có, ta thực hiện các thao tác sau:

1. Rút trích tập từ loại - POS set từ Penn treebank: Thao tác này sẽ chúng ta sẽ có được tập từ loại POS set rút trích từ Penn treebank.

2. Rút trích những câu tiếng Anh trong treebank: việc rút những câu trong treebank bằng cách ứng với mỗi câu trong treebank chúng ta duyệt từ trái sang phải theo thứ tự và lấy nút lá của chúng. Sau khi có tập câu, chúng ta tiến hành chuyển tập câu này sang tiếng Việt để làm tập thử nghiệm cho phân tích cú pháp tiếng Việt.

3. Tạo treebank dạng nonlexical: treebank mà đã loại bỏ nút lá: Từ treebank đã có, ứng với mỗi câu trong Penn treebank duyệt từ trái sang phải đồng thời loại bỏ nút lá của chúng.

4. Tạo tập luật sinh nguyên thủy: Sau khi có treebank-nonlexical ta tiến hành tạo luật sinh từ treebank-nonlexical này. Đây là tập luật sinh nguyên thủy tiếng Anh nó chưa được chuẩn hóa theo dạng chuẩn Chomsky CNF.

5. Ánh xạ tập luật sinh sang tập luật sinh sang tiếng Việt: Sau khi có tập luật sinh tiếng Anh, chúng ta tiến hành ánh xạ luật sinh này sang tập luật tiếng Việt như nghiên cứu ở chương 03.

Ví dụ giai đoạn cho giai đoạn này:

Giả sử ta có một câu được rút ra từ treebank như sau:

((S (NP (DT The) (NNP Fulton) (NNP County) (NNP Grand) (NNP Jury) ) (VP (VBD said) (NP (NNP Friday) ) (SBAR (-NONE- 0) (S (NP (DT an) (NN investigation) (PP (IN of) (NP (NP (NNP Atlanta) ) (POS 's) (JJ recent) (JJ primary) NN election) ))) (VP (VBD produced) (NP (OQUOTE OQUOTE) (DT no) (NN evidence) (CQUOTE CQUOTE) (SBAR (IN that) (S (NP (DT any) (NNS irregularities) ) (VP (VBD took) (NP (NN place) ))))))))))

Quá trình rút trích thông tin từ loại, câu và tạo ra treebank dạng nonlexical ở giai đoạn này cho câu trên. Kết quả như sau:

1. Rút trích và tạo tập từ loại POS set:

-NONE-

NNP

VBD

POS

CQUOTE

NNS

VBD

Bảng 2.1: Corpus từ loại rút trích từ treebank

2. Câu khi rút trích từ cây trên là:

“ The Fulton County Grand Jury said Friday 0 an investigation of Atlanta 's recent primary election produced OQUOTE no evidence CQUOTE that any irregularities took place”.

3. Cây dạng nonlexical như sau:

((S (NP DT NNP NNP NNP NNP ) (VP VBD (NP NNP ) (SBAR -NONE- (S (NP DT NN (PP IN (NP (NP NNP ) POS JJ JJ NN election) ))) (VP VBD (NP OQUOTE DT NN CQUOTE (SBAR IN (S (NP DT NNS ) (VP VBD (NP NN ))))))))))

4. Dựa vào cây dang nonlexical ta có luật sinh cho tiếng Anh như sau:

NP ---> DT NNP NNP NNP NNP

NP ---> NNP

NP ---> NP POS JJ JJ NN

PP ---> IN NP

NP ---> DT NN PP

S ---> NP

NP ---> DT NNS

NP ---> NN

S ---> NP VP

SBAR ---> IN S

NP ---> OQUOTE DT NN CQUOTE SBAR

VP ---> VBD NP

SBAR ---> -NONE- S VP

VP ---> VBD NP SBAR

S ---> NP VP

VP ---> VBD NP

Bảng 2.2: Luật sinh tiếng Anh được tạo ra từ treebank

5. Sau khi có luật sinh cho tiếng Anh, tiến hành ánh xạ luật sinh này sang luật sinh tiếng Việt. Kết quả như sau:

NP ---> DT NNP NNP NNP NNP

NP ---> NNP

NP ---> NP POS NN JJ JJ

PP ---> IN NP

NP ---> DT NN PP

S ---> NP

NP ---> DT NNS

NP ---> NN

S ---> NP VP

SBAR ---> IN S

NP ---> OQUOTE DT NN CQUOTE SBAR

VP ---> VBD NP

SBAR ---> -NONE- S VP

VP ---> VBD NP SBAR

S ---> NP VP

VP ---> VBD NP

Bảng 5.3: Luật sinh tiếng Việt được chuyển đổi từ luật sinh tiếng Anh

Ví dụ trên cho ta thấy tiến trình xây dựng luật sinh, tập từ loại, câu thử nghiệm, … tiếng Việt xuất phát từ Penn treebank tiếng Anh. Sau khi có luật sinh tiếng Việt, tiến hành chuẩn hóa luật sinh này theo dạng CNF đồng thời thống kê và tính xác suất dựa trên tập luật sinh tiếng Việt. Khi đã có đầy đủ dữ liệu như tập từ loại, tập luật sinh, … tiến hành thực hiện tích cú pháp. Quá trình phân tích cú pháp được thực hiện như sau:

2.2. Phân tích cú pháp tiếng Việt theo phương pháp thống kê

Sau khi đã có được tập luật sinh cho tiếng Việt ở dạng thô đã được tạo ra ở phần trên, ta tiến hành chuẩn hóa tập luật sinh theo dạng CNF và tiến hành phân tích cú pháp dựa trên tập luật sinh này. Mô hình phân tích cú pháp được trình bày như sau:

Hình 2.2: Mô hình phân tích cú pháp tiếng Việt theo phương pháp thống kê

Theo mô hình trên, từ tập luật sinh tiếng Việt ở dạng thô tiến hành chuyển tập luật sinh về dạng right-branch-binary - tập luật sinh theo dạng nhị phân chuẩn chomsky. Sau đó từ tập luật sinh dạng chuẩn chomsky này, ta chuyển và đếm số lần xuất hiện của tất cả các luật sinh để ước lượng tập PCFG.

Tiếp theo, trên cơ sở PCFG vừa ước lượng, dùng giải thuật để tìm cây phân tích (parse tree) có khả năng xảy ra lớn nhất cho câu cần phân tích. Sau khi đã tìm được cây phân tích cho câu dữ liệu đầu vào được sinh ra từ PCFG, ta tiến hành tái chuyển đổi về dạng cây nguyên thuỷ ban đầu. Cuối cùng dùng tập các cây phân tích mẫu chuẩn trong Treebank để kiểm tra và đánh giá mô hình thông qua các thông số kiểm định.

2.3. Pháp phân tích cú pháp theo phương pháp thống kê giải quyết sự nhập nhằng

Như ta đã giới thiệu, sự nhập nhằng xảy ra khi cùng một câu dữ liệu nhập vào đưa ra nhiều cây phân tích cú pháp khác nhau. Vấn đề ở đây là ta chọn cây phân tích nào tối ưu nhất và phù hợp nhất với câu nhập vào.

Hiện nay, có rất nhiều phương pháp phân tích cú pháp khác nhau nhưng tác giả chọn phương pháp phân tích cú pháp theo phương pháp xác suất vì phương pháp này cho chúng ta biết được xác suất của từng cây phân tích tương ứng với câu nhập vào. Vì thế chúng ta sẽ dễ dàng chọn được cây phân tích tối ưu nhất, phù hợp với câu nhập vào dựa trên xác suất cao nhất của nó. Chính vì điều này, sẽ giải quyết được sự nhập nhằng về ngữ nghĩa mà đề tài đã nêu.

2.4. Lựa chọn sự biểu diễn cho các cây (Tree representation) để tối ưu mô hình

Văn phạm phi ngữ cảnh có xác suất (PCFG) cung cấp một mô hình thống kê đơn giản trong xử lý ngôn ngữ tự nhiên. Người ta thường đưa ra một phương pháp minh bạch về việc xây dựng và ước lượng tần số xuất hiện của tập văn phạm này từ treebank, và một hệ thống phân tích cú pháp trên phạm vi thông tin lớn (broad coverage parsing) vẫn có thể được sử dụng bằng cách dùng một giải thuật phân tích cú pháp để tìm cây phân tích cú pháp phù hợp nhất với câu dữ liệu đầu vào đối với văn phạm sinh từ treebank. Hệ thống phân tích cú pháp bằng PCFG thường được đánh giá là hoạt động tốt như các hệ thống phân tích cú pháp trên phạm vi thông tin lớn khác để dự đoán cấu trúc cây phân tích cú pháp từ câu dữ liệu đầu vào đã được POS tag (Charniak, 1996). Mặc dù mô hình PCFG không hoạt động tốt như mô hình dependence-grammar của Collin, nhưng sự đơn giản của nó làm cho quá trình phân tích trở nên minh bạch cả về mặc lý thuyết lẫn kinh nghiệm [20].

Theo Mark Jonshon, một trong những điểm yếu của mô hình PCFG là nó không nhạy cảm với mối quan hệ không cục bộ (non-local relationship) giữa các nút, tức là nó không mô tả được một cách đầy đủ mối quan hệ giữa cây con bị chi phối bởi một nút và những nút chi phối cây này. Nếu những mối quan hệ này là đáng kể thì PCFG sẽ trở thành một mô hình ngôn ngữ nghèo nàn.

Nói một cách nôm na, nếu các cây trong tập huấn luyện càng có nhiều nút thì càng làm tăng thêm giả định độc lập (independence assumptions) trong mô hình PCFG được sinh ra từ tập huấn luyện các cây này. Do đó, để làm giảm giả định độc lập tiềm ẩn này trong một PCFG: thứ nhất, số lượng nút trên các cây trong tập huấn luyện càng ít thì sẽ giảm được giả định độc lập trong mô hình ngôn ngữ được sinh ra, phương pháp thứ hai là mã hoá thêm những thông tin vào mỗi nhãn các nút của cây. Theo trực giác, mỗi nhãn trên một nút là một “kênh truyền đạt thông tin” (comunication chanel), làm nhiệm vụ chuyển tải thông tin giữa cây con bị chi phối bởi nút và phần của cây không bị chi phối bởi chính nút đó. Thông tin bổ sung được thêm vào nhãn của nút về mặt ngữ cảnh sẽ làm giảm đi giả định độc lập tìm ẩn trong mô hình PCFG[38].

Với lý do này, bên cạnh việc chuyển cây ban đầu trong treebank về dạng right_branching binary để ước lượng PCFG, để tối ưu, đề tài còn chọn phương pháp trên để chuyển dạng cây ban đầu trong treebank về dạng cây có gán thêm thông tin nút cha (nhãn của nút cha) vào các nhãn cây (parent annotation trees), trong đó:

Nhãn của tất cả các nút không phải là nút kết thúc và không phải là nút gốc (nút trung gian) của cây sẽ được gắn thêm từ loại của nút cha.
Nhãn của các nút gốc, nút chứa ký hiệu kết thúc (nút lá) thì không thay đổi.

2.5. Mô hình thống kê

Mục đích chính của quá trình phân tích cú pháp là nhận câu cần phân tích đã được part-of-speech tagging và cho kết quả là một cây có cấu trúc tương ứng (phrase-structure tree).

Theo cách tiếp cận thống kê, phân tích cú pháp bao gồm 2 phần, thứ nhất là mô hình thống kê (statistical model), thứ hai là phương pháp phân tích, nghĩa là đi tìm cây phân tích cú pháp có khả năng xảy ra lớn nhất t_best . Trong đó mô hình thống kê ấn định xác suất cho mỗi cây phân tích của câu nhập. Thông thường, cho câu nhập s và cây t, mô hình ước lượng xác suất có điều kiện P(t|s), khi đó cây phân tích phù hợp nhất với mô hình cần tìm là:

t_best= arg max_t P(t|s)

Trong đó, P(s|t) được định nghĩa bằng cách gán xác suất trong quá trình dẫn xuất ra cây t bởi các luật sinh. Mỗi luật sinh có dạng LHS --> RHS (LHS: vế bên trái, RHS: vế bên phải). Trong văn phạm phi ngữ cảnh có xác suất PCFG, mỗi cây phân tích cú pháp t được dẫn xuất ra bởi n luật sinh LHS_i -->RHS_i 1£ i £n, khi đó xác suất cây t được tính bởi công thức:

Trong mỗi luật sinh, LHS là một ký hiệu không kết thúc, RHS là một hoặc chuỗi ký hiệu không kết thúc và ký hiệu kết thúc.

Vấn đề chính trong PCFG là đi tìm xác suất P(RHS | LHS) cho mỗi luật sinh LHS --> RHS trong văn phạm. Trong phạm vi đề tài nghiên cứu, cách đơn giản là thống kê từ kết quả đếm được ở treebank và sau đó sử dụng tham số ước lượng khả năng xảy ra lớn nhất:

3. Một số giải thuật và phương pháp đánh giá hiệu suất

3.1. Rút trích câu, từ loại đồng thời tạo loại bỏ nút lá trong treebank

Thủ tục này rút trích những ký hiệu kết thúc tức là POS tag, câu trong treebank đồng thời tạo ra treebank dạng nonlexical – treebank mà đã loại bỏ nút lá. Mã giả của giải thuật được trình bày như sau:

- Duyệt từ trái sang phải qua từng cây trong treebank

- Nếu gặp POS tag thì tạo kho lưu trữ và lưu POS tag này

- Nếu gặp một nút lá thì lưu theo thứ tự từ trái sang phải (sẽ được câu tương ứng)

- Nếu gặp nút lá thì loại bỏ nút lá (sé được treebank dạng nonlexical)

Minh họa khi thực hiện giải thuật: Giả sử ta có cây cú pháp từ treebank như sau:

NP VP

NP PP VBD NP NP

DT NN IN NNP PRP$ NN DT NN

The president of IBM announced his resignation this morning

Hình 2.3: Cây cú pháp minh họa cho rút trích thông tin và tạo cây nonlexical_tree

Sau khi thực hiện thủ tục, kết quả như sau:

Rút trích POS tag

DT The

NN president

IN of

NNP IBM

VBD announced

PRP$ his

NN resignation

DT this

NN morning

Khi rút trích POS tag từ treebank, sẽ có rất nhiều POS tag trùng nhau. thực hiện việc thống kê đếm số lần xuất hiện của mỗi POS tag là ta đã có được Corpus thống kế từ loại cho ngôn ngữ.

Rút trích câu: “The president of IBM announced his resignation this morning”.
Loại bỏ nút lá của cây ta có cây dạng Nonlexical như sau:

NP VP

NP PP VBD NP NP

DT NN IN NNP PRP$ NN DT NN

Hình 2.4: Cây dạng nonlexical tree

3.2. Gán thông tin nút cha (parent annotation) lên cây nguyên thủy

Trước khi thực hiện việc gán thông tin nút cha, tiến hành chuẩn hóa cây theo dạng CNF - dạng chuẩn chomsky (tức là mỗi nút trong cây chỉ có không nhiều quá hai con). Nhưng thứ từ này không phù hợp với tiếng Việt, ví dụ:

Giả sử ta có cây cú pháp sau:

NP NP

Chuẩn hóa right_branching_binary

JJ NN . JJ NN_.

NN .

Hình 2.5: Ví dụ minh họa chuẩn hóa theo dang CNF

Sau khi chuẩn hóa ta có cây cú pháp (b), cây cú pháp này là đúng với ngôn ngữ tiếng Anh, vậy liệu nó có đúng với cú pháp tiếng Việt không? Quay lại văn phạm giữa tiếng Anh và tiếng Việt ta thấy:

Ta có qui luật trong tiếng Anh “JJ” đứng trước “NN” khi chuyển qua tiếng Việt thì “NN” đứng trước “JJ”. Nếu xét về luật sinh cho cây sau khi chuẩn hóa ta thấy:

NP à JJ NN_.

NN_. à NN .

Nếu chúng ta thực hiện chuyển ánh xạ luật sinh tiếng Việt thì

NP à NN_. JJ

NN_. à NN .

Ta thấy luật sinh tiếng Việt trên không đúng với văn phạm tiếng Việt. Như vậy để giải quyết trường hợp này chúng ta sẽ thực hiện việc ánh xạ cú pháp tiếng Việt trước sau đó chuẩn hóa theo dạng CNF sau. Theo thứ tự này, ví dụ trên được giải quyết như sau:

NP NP

Chuyển đổi cú pháp

JJ NN . NN JJ .

(a’) (b’)

Sau khi chuyển đổi cú pháp xong ta tiến hành chuẩn hóa, việc chuyển hóa như sau:

NP NP Chuẩn hóa dạng CNF

NN JJ . NN JJ_.

JJ .

(c’) (d’)

Hình 2.6: Ví dụ minh họa chuẩn hóa cây cú pháp tiếng Việt theo dạng CNF

Như vậy ta có luật sinh cho cây sau khi chuẩn hóa ở (d’) như sau:

NP àNN JJ_.

JJ_. à JJ .

Luật sinh này đúng với cú pháp và văn phạm của tiếng Việt.

Sau khi chuyển đổi cây và chuẩn hóa dang CNF song, tiến hành thực hiện việc gán thông tin nút cha cho mỗi nút con. Trong đó:

1) Nhãn của tất cả các nút không phải là nút kết thúc[1] và không phải là nút gốc của cây có gắn thêm từ loại (nhãn) của nút cha.

2) Nhãn của các nút gốc, nút chứa ký hiệu kết thúc thì không thay đổi.

Hình 5.7 là cây dạng parent annotation được chuyển từ cây ban đầu trong Hình 5.4.

NP^S VP^S

NP PP VBD^VP NP_NP^VP

DT NN IN NNP

NP^NP_NP NP^NP_NP

PRP$ NN DT NN

Hình 5.7: Biểu diễn cây dạng parent annotation right_braching_binary

Mã giả của giải thuật được tóm tắt như sau:

Nhập : file treebank ban đầu

Xuất : file treebank lưu các cây dạng parent_ annotation right_ branching_ binary

Phương pháp:

parent_anno_right_branch_bin(treebank_file,treebank_anno_file):

While not EOF(treebank_file) do

tree = readtree(treebank_file)

Insert ‘ROOT’ to tree

Delete all lexicals and empty nodes

tree1 = parent_annotation(tree, NULL)

tree2 = Right_binarize(tree1)

Save (treebank_anno_file, tree2)

End while

parent_annotation(tree, parent_label):

If tree <> NULL then

label = tree.label

If (parent_label <> NULL) and (tree.subtree<>NULL) then

anno_tree.label = label + “^” + “parent_label”

Else

anno_tree.label = tree.label

anno_tree.sibling = parent_annotation(tree.sibling, parent_label)

anno_tree.subtree = parent_annotation(tree.subtree, label)

return anno_tree

Else

return NULL

3.3. Nhận diện và chuyển đổi cú pháp

Thủ tục này có khả năng nhận biết những điểm cú pháp thay đổi trong luật sinh, sau đó chuyển luật sinh đó về đúng với cấu trúc cú pháp luật sinh tiếng Việt. Quá trình làm việc của thủ tục này như sau:

Duyệt từ trái sang phải của luật sinh
Chọn ra vế bên phải của luật sinh
Nhận biết chuỗi luật sinh có cú pháp thay đổi
Nếu nhận thấy có chuỗi luật sinh có cú pháp thay đổi thì tiến thực hiện chuyển đổi chuỗi luật sinh.
Nếu không tìm thấy thoát khổi thủ tục

Ví dụ của quá trình thực hiện thủ tục như sau:

Giả sử ta có luật sinh như sau:

NP à JJ NN

Thủ tục sẽ nhận ra được luật sinh trên có một điểm ngữ pháp thay đổi đó là “JJ NN”. Như ta biết, khi ánh xạ luật sinh sanh tiếng Việt tính từ phải đứng sau danh từ. Do đó, sau khi nhận ra được điểm thay đổi cú pháp, thủ tục tiến hành chuyển đổi cú pháp cho luật sinh này. Kết quả là: NP à NN JJ

Ví dụ trên đơn giản cho 1 điểm thay đổi cú pháp cho luật sinh, nếu luật sinh có nhiều điểm thay đổi thì sao? Ta xét một ví dụ phức tạp hơn như sau:

NP à DT JJ NNP JJ NN

Thủ tục sẽ nhận ra được ở luật sinh này có hai điểm cần chuyển đổi chuỗi luật sinh đó là “JJ NNP” và “JJ NN”. Sau khi nhận biết được hai chuỗi cần chuyển đổi, tiến hành thực hiện chuyển đổi luật sinh của chuỗi này. Kết quả trả về cuối cùng là:

NP à DT NNP JJ NN JJ

3.4. Chuyển đổi luật sinh về dạng right_branching_ binary

Sau khi có tập luật sinh cho tiếng Việt, tiến hành chuẩn hóa đưa luật sinh về dạng right branching binary. Việc chuẩn hóa được thực hiện như sau:

Duyệt tất cả tập luật sinh
Nếu tập luật sinh nào có quá hai con thì
Tách luật sinh thành nhiều luật sinh khác nhau, và mỗi luật không vượt quá hai con.

Có rất nhiều cách tách luật khác nhau nhưng sao cho phải bảo toàn được luật sinh. Nguyên tắt tách phổ biết ở đây là:

Giữ nguyên nút con thứ nhất, nút con thứ hai sẽ là hợp của tất cả nút con kế phải nút thứ nhất.
Nếu tập hợp con thứ hai còn nhiều hơn một con thì chuyển thành nút bố của luật sinh kế tiếp.
Lặp lại quá trình như vậy cho đến khi tập con thứ hai chi con một con.

Ví dụ cho thủ tục này như sau:

Xét luật sinh: NP à DT NNP JJ NN JJ

Quá trình tách luật trên như sau:

NP à DT NNP_JJ_NN_JJ

NNP_JJ_NN_JJ à NNP JJ_NN_JJ

JJ_NN_JJ àJJ NN_JJ

NN_JJ àNN JJ

3.5. Thống kê và xây dựng tập huấn luyện PCFG

Sau khi có tập luật sinh đã được chuẩn hóa theo dạng Right Branching Binary, tiến hành thống kê đếm số lần xuất hiện tương ứng với luật sinh trong tập huấn luyện và tính xác suất cho từng luật sinh. Xác suất của luật sinh được tính theo công thức sau:

Trong đó LHS đại diện 1 ký hiệu không kết thúc bên trái luật sinh, RHS đại diện 1 hoặc 2 ký hiệu không kết thúc (luật 1 ngôi và luật 2 ngôi) bên phải luật sinh. C_t(LHS àRHS) là số lần xuất hiện của luật sinh LHS àRHS trong tập huấn luyện, C_t(LHS à RHS’) là số lần xuất hiện của luật sinh mà có vế trái có cùng ký hiệu không kết thúc với LHS trong tập huấn luyện.

Ví dụ thống kê và tính xác suất cho cây cú pháp sau:

Giả sử ta có tập luật sinh tiếng Việt với số lần xuất hiện được thống kê như sau:

Luật

Số lần xuất hiện

S à NP VP

NP à NP PP

NP àDT NN

PP à IN NNP

VP à VBD NP_ NP

NP_ NP à NP NP

NP à NN PRP$

1/1

1/4

2/4

1/1

Hình 2.7: ví dụ thống kê đếm số lần xuất hiện luật sinh

Bảng thống kê lần xuất hiện luật sinh là tổng số lần xuất hiện của luật sinh so với tổng số lần xuất hiển RHS của luật sinh đó. Như vậy ta có xác suất của tập luật sinh trên như sau:

Luật

Xác suất

S à NP VP

NP à NP PP

NP àDT NN

PP à IN NNP

VP à VBD NP_ NP

NP_ NP à NP NP

NP à NN PRP$

0.25

0.5

0.25

Hình 2.7: ví dụ tính xác suất luật sinh

Như vậy ta có tập huấn luyện PCFG cho từng luật sinh được rút từ treebank. tiếp theo ta tiến hành xây dựng giải thuật phân tích cú pháp cho câu nhập vào, và dựa vào tập huấn luyện PCFG chúng ta sẽ tìm được cây phân tích có xác suất cao nhất.

5.2.6. Giải thuật phân tích cú pháp và tìm cây có xác suất cao nhất

Đây là thủ tục quan trọng nhất của đề tài, đề tài đã chọn giải thuật CKY có cải tiến gọi là CKY₊ để tìm cây phân tích cú pháp có xác xuất lớn nhất.

Giải thuật CKY₊ sử dụng văn phạm nhập là văn phạm phi ngữ cảnh G trong dạng chuẩn Chomsky (CNF). Trong CNF, mỗi luật có một trong hai dạng:

A --> B C A, B, C Î V

A --> a A Î V và a Î T

Phương pháp:

1. Thêm vào chart tất cả các luật sinh unary (k --> w_i) Î G và xác suất tương ứng của luật sinh đó, trong đó w_i là từ loại tương ứng từ thứ i trong câu.

2. Với mỗi cạnh có chiều dài l (từ 2 đến n):

Duyệt từ trái qua phải, kết hợp các cạnh để tạo nên cạnh mới với chiều dài l, trong đó, các luật sinh nào có vế phải trùng nhau thì chọn luật sinh có xác suất lớn hơn.

3. Nếu ‘ROOT’ Î chart [0,n], cho kết quả là cây phân tích cú pháp tương ứng câu w.

Cấu trúc dữ liệu của giải thuật được định nghĩa như sau:

- Câu dữ liệu đầu vào gồm n từ : w₁w₂..w_n.

- Giả sử |N| là số ký hiệu không kết thúc trong văn phạm G và được xếp thứ tự 1, 2, .. |N|. Không mất tính tổng quát, ta xem 1 là ký hiệu bắt đầu.

- Cấu trúc dữ liệu chính của giải thuật là một mảng 3 chiều c[i,j,k] có n(n+1)/2 phần tử. Trong đó n là số từ của câu dữ liệu đầu vào. Mỗi phần tử chứa 2 thành phần: cây dẫn xuất có gốc là nhãn k (tức k àa b) và xác suất lớn nhất tương ứng của cụm từ w_i.. w_j.

- Mục đích của giải thuật là đi tìm c[1,n,1] chứa cây phân tích cú pháp của câu w có xác suất lớn nhất .

Mã giả giải thuật được tóm tắt như sau:

Nhập : nhập câu w gồm n từ w₁… w_n.

Xuất : parse_tree và xác suất của w nếu w Î L(G) và parse_failure nếu không thuộc.

For i=1 to n do

Add w_i to chart

For k =1 to |unary rule (k --> w_i) Î G|

Add (k --> w_i) to chart[i,i+1]

p[i,i+1,k] = P(k --> w_i)

For j = 2 to n do

For i = j - 2 downto 0 do

For mid = i+1 to j do

For k = 1 to |binary rule (k--> k1 k2) Î G | do

If ((k1 -->a)Î chart[i, mid]) and ((k2 -->b)Îchart[mid, j]) then

prob = p[i, mid, k1]*p[mid, j, k2] * P(k --> k1 k2)

If prob > p[i, j, k] then

add [k --> k1 k2] to chart[i,j]

p[i,j,k] = prob

For k’ =1 to |unary rule (k’ --> k) Î G| loop

If p[i,j,k] * P(k’ --> k) > p[i, j,k’] then

add (k’ --> k) to chart[i,j]

p[i, j, k] = p[i,j,k] * P(k’ --> k)

If ‘ROOT’ Î chart[0,n] then

return parse_tree

Else

Parse_failure.

3.6. Kiểm tra sự phù hợp của cây phân tích cú pháp kết quả và chuyển về dạng cây phù hợp với treebank

Sau khi tìm ra cây phân tích cú pháp có xác suất lớn nhất của câu nhập, bước tiếp theo là kiểm tra sự phù hợp của cây phân tích cú pháp với tập huấn luyện và chuyển cây phân tích cú pháp được sinh ra bởi các luật sinh về dạng cây ban đầu của treebank.

3.7. Đánh giá hiệu suất [11][20]

Một vấn đề quan trọng nữa là làm sao để đánh giá được hiệu quả của mô hình phân tích cú pháp bằng phương pháp thống kê. Thông thường, để đánh giá hiệu quả của một “chương trình” phân tích cú pháp, ngoài việc so sánh cây phân tích cú pháp bằng chương trình với cây phân tích cú pháp bằng tay, người ta đề nghị đánh giá hiệu quả chương trình dựa trên 2 tiêu chuẩn cơ bản sau:

- Độ chính xác (Precision): cho biết có bao nhiêu ngoặc đơn (brackets) trong cây phân tích cú pháp (t) phù hợp với cây phân tích cú pháp chuẩn (t’). Hay phần trăm số ngoặc đơn mà cây phân tích cú pháp (t) khớp với cây phân tích cú pháp chuẩn (t’) chia cho tổng số ngoặc đơn của cây (t’).

- Khả năng gọi về (Recall): cho biết có bao nhiêu ngoặc đơn trong cây phân tích cú pháp chuẩn (t’) xuất hiện trong cây phân tích cú pháp (t). Hay phần trăm số ngoặc đơn mà cây phân tích cú pháp (t) khớp với cây phân tích cú pháp chuẩn (t’) chia cho tổng số ngoặc đơn của cây (t).

Giả sử xem cây phân tích cú pháp t như một tập các cạnh E(t) gồm ba phần , trong đó N là ký hiệu không kết thúc, l và r là vị trí ngoặc đơn bên trái và ngoặc đơn bên phải. t’ là cây phân tích cú pháp chuẩn để kiểm tra tương ứng. Khi đó tiêu chuẩn đánh giá precision và recall của cây t và t’ được tính như sau:

Precision =

Recall =

(a) ROOT

NP VP NP

NNS NNS VBD VP NN

₀sale ₁ executives ₂ were ₃ yester day ₁₀

VBG NP PP

examing ₄

DT NNS IN NP

The ₅ figure ₆ with ₇

JJ NN

Great ₈ care 9

(b)

‘ROOT’

NP VP

NNS NNS VBD VP

₀sale ₁ executives ₂ were ₃

VBG NP

examing ₄

NP PP

DT NNS IN NP

The ₅ figure ₆ with ₇

JJ NN NN

Great ₈ care ₉ yesterday ₁₀

E(t): S(0,10); NP(0,2); VP(2,9); VP(3,9); NP(4,6); PP(6,9); NP(7,9); NP(9,10)

(d) Các cặp ngoặc đơn (cạnh) trong cây phân tích cú pháp phù hợp nhất tương ứng (b):

E(t’): S(0,10); NP(0,2); VP(2,10); VP(3,10); NP(4,10); NP(4,6); PP(6,10); NP(7,10)

(e) Các cặp ngoặc đơn khớp nhau trong 2 cây (a) và (b)

E(t) Ç E(t’) = S(0,10); NP(0,2); NP(4,6)

(f) Precision = 3/8 = 37.5%

recall = 3/8 = 37.5%

Hình 5.8 : Một ví dụ về cách đánh giá 2 tiêu chuẩn Precision và Recall.

3.3. Demo chương trình

3.1. Lựa chọn ngôn ngữ để phát triển ứng dụng

Ngày nay MS .NET đang ngày càng phát triển mạnh mẽ, với những tính năng mạnh mẽ, ưu việt, trực quan của nó đồng thời để dễ dàng phát triển cải tiến sau này. Tác giả chọn ngôn ngữ C#.NET để phát triển đề tài. Quá trình chạy và thực hiện chương trình được thực hiện chi tiết như sau.

3.2. Demo chương trình

Khi chạy chương trình, giao diện chính của chương trình như sau:

a. Màn hình chính

Hình 2.9: Màn hình giao diện chính chương trình

Màn hình giao diện chính được chia làm 6 phần

- Hiển thị dữ liệu nguồn có sẳn treebank đã có

- Từ treebank đã có, tạo dữ liệu để phục vụ cho việc phân tích cú pháp. Các dữ liệu được tạo ra ở phần này như: tạo luật sinh, chuyển đổi cú pháp luật sinh, thống kê tập luật sinh, …

- View making data - hiển thị những tập dữ liệu được tạo ở phần make data

- Corpus form Treebank: cho phép hiển thị corpus từ loại được rút trích từ treebank

- Statistic Rules and PCFG: thống kê và tạo tập huấn luyện PCFG - tập luật sinh có gáng xác suất

- Vietnamese Parsing: Phân tích cú pháp cho câu tiếng Việt

b. Màn hình hiển thị treebank

Cho ta thấy cấu trúc của một treebank

Hình 2.10: Màn hình hiển thị Penn Treebank

3. Màn hình tạo dữ liệu:

- Click vào Transform, với treebank đã có, hệ thống sẽ tưh động rút trích từ loại đồng thời tạo ra treebank_bin (treebank mà đã loại bỏ nút lá).

- Sau khi transform được complete, click vào Generate Rules for English hệ thống sẽ tự động sinh ra tập luật sinh cho tiếng Anh xuất phát từ treebank_bin

- Sau khi có luật sinh cho tiếng Anh, tiến hành chuyển đổi cú pháp sang luật sinh cho tiếng Việt bằng cách click vao Convert Vetnamese Grammar. Khi click vao nút này hệ thống sẽ tự động nhận biết những điểm ngữ pháp nào cần chuyển đổi và chuyển đổi nó theo đúng với cú pháp của tiếng Việt.

- Sau khi có luật sinh cho tiếng Việt, tiếng hành chuẩn hóa tập luật sinh này đưa tập luật sinh về dạng Right Branching Binary.

- Cuối cùng click vào nút close để đóng cửa sổ

Hình 2.11: Màn hình tạo dữ liệu, luật sinh

d. Màn hình hiển thị kết quả của quá trình tạo dữ liệu

Màn hình hiển thị quá trình tạo dữ liệu, nút “View VN Branching” - Hiển thị VietNamese right branching binary; nút “View Vietnamese Statistic Rule” - hiển thị thống kê luật sinh, nút “View PCFG” - hiển thị tập huấn luyện có gắn xác suất.

Hình 2.12: Màn hình hiển thị dữ liệu

e. Màn hình hiển thị tập luật sinh chuẩn hóa theo dạng Right Branching Binary:

Hình 2.13: Màn hình hiển thị luật sinh chuẩn hóa dạng CNF

f. Màn hình thống kế luật sinh

Màn hình thống kê luật sinh, cho phép thêm một luật sinh mới nếu như luật sinh này chưa được thống kê và tồn tại trong tập luật sinh. Quá trình thêm mới luật sinh được thực hiện như sau:

Statistic: số lần thống kê của luật cần thêm
Left Rule: về bên trái của luật
Right Rule: vế bên phải của luật

Sau khi nhập xong những trường trên, click vào Add rule để thêm luật sinh vào tập luật.

Hình 2.14: Màn hình thống kê luật sinh tiếng Việt

f. Màn hình hiển thị tập PCFG có xác suất

Hình 2.14: Màn hình hiển thị tập huấn luyện PCFG

g.Màn hình hiển thị corpus POS Tag được rút trích từ treebank

Hình 2.15: Màn hình hiển thị corpus POS Tag

h. Màn hình thực hiện xử lý cú pháp tiếng Việt

Màn hình này cho phép xử lý cú pháp tiếng Việt. Khi người sử dụng nhập một câu tiếng Việt theo định dạng đã qui định. Click vào nút Parse, hệ thống sẽ xử lý, phân tích cú pháp cho câu nhập và đưa ra cây phân tich cú pháp tương ứng với câu nhập với xác suất cao nhất. Màn hình giao diện như sau: