Luận văn Gán nhãn phân tích cú pháp quan hệ cho song ngữ Anh Việt thông qua liên kết ngữ

TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN

KHOA CÔNG NGHỆ THÔNG TIN

BỘ MÔN CÔNG NGHỆ TRI THỨC

NGUYỄN THỐNG NHẤT – LÊ MINH SƠN

GÁN NHÃN PHÂN TÍCH CÚ PHÁP QUAN HỆ

CHO SONG NGỮ ANH VIỆT

THÔNG QUA LIÊN KẾT NGỮ

LUẬN VĂN CỬ NHÂN TIN HỌC

TP. Hồ Chí Minh – Năm 2003

TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN

KHOA CÔNG NGHỆ THÔNG TIN

BỘ MÔN CÔNG NGHỆ TRI THỨC

NGUYỄN THỐNG NHẤT – 9912053

LÊ MINH SƠN - 9912668

GÁN NHÃN PHÂN TÍCH CÚ PHÁP QUAN HỆ

CHO SONG NGỮ ANH VIỆT

THÔNG QUA LIÊN KẾT NGỮ

LUẬN VĂN CỬ NHÂN TIN HỌC

GIÁO VIÊN HƯỚNG DẪN

GS.TSKH. HOÀNG KIẾM

NIÊN KHOÁ 1999 - 2003

Lời cảm ơn

Trước hết, chúng tôi xin chân thành gởi lời cảm ơn đến GS.TSKH. Hoàng Kiếm,

người đã tận tụy dẫn dắt chúng tôi từng bước để hoàn thành bài luận văn này. Chúng

tôi cũng chân thành cảm ơn các Thầy Cô trong và ngoài khoa Công nghệ thông tin đã

truyền đạt kiến thức quý báu cho tôi trong suốt bốn năm học.

Để hoàn thành bài luận văn này, chúng tôi không thể không nhắc đến sự động viên

và chăm sóc của gia đình. Ngoài ra, chúng tôi gởi lời cám ơn đến những người mà

chúng tôi đã có dịp cộng tác và sự ủng hộ tinh thần của bạn bè.

Cuối cùng chúng tôi cũng muốn gởi lời cám ơn đến Thầy Đinh Điền và các thành

viên trong nhóm VCL, những người đã giúp đỡ cho chúng tôi hoàn tất bài luận văn

này.

Chúng tôi xin chân thành cảm ơn tất cả.

TP. Hồ Chí Minh, 7-2003

Nguyễn Thống Nhất và Lê Minh Sơn

Nhận xét của giáo viên hướng dẫn

.....................................................................................................................

TP. Hồ Chí Minh, ngày ........ tháng .......năm 2003

Giáo viên hướng dẫn

GS. TSKH. Hoàng Kiếm

Nhận xét của giáo viên phản biện

.....................................................................................................................

TP. Hồ Chí Minh, ngày ........ tháng .......năm 2003

Giáo viên phản biện

MỤC LỤC

LỜI NÓI ĐẦU................................................................................................................. 1

Chương 1: TỔNG QUAN ........................................................................................... 1

1.1. Phân tích cú pháp quan hệ................................................................................ 1

1.2. Liên kết từ/ngữ.................................................................................................. 1

1.3. Chiếu quan hệ cú pháp ..................................................................................... 3

1.3.1. Chiếu nhãn từ loại..................................................................................... 3

1.3.2. Chiếu quan hệ cú pháp..............................................................................4

Chương 2: CÁC CÁCH TIẾP CẬN........................................................................... 5

2.1. Phân tích cú pháp.............................................................................................. 5

2.1.1. Các phương pháp tiếp cận dùng luật phi ngữ cảnh (CFG)..................... 5

2.1.1.1. Cách tiếp cận từ trên xuống (Top-Down)......................................... 5

2.1.1.2. Thuật toán phân tích cú pháp từ trên xuống (Top-Down)............... 7

2.1.1.3. Cách tiếp cận Từ dưới lên (Bottom-Up)........................................... 8

2.1.1.4. Thuật toán phân tích cú pháp Earley...............................................11

2.1.1.5. Mạng ngữ pháp lan truyền...............................................................12

2.1.2. Phương pháp TBL (Transformation-Based Error-Driven Learning) ..15

2.1.3. Phương pháp phân tích cú pháp dựa trên văn phạm TAG ...................19

2.1.3.1. Văn phạm TAGs...............................................................................19

2.1.3.1.1. Cây sơ cấp..................................................................................19

2.1.3.1.2. Cây phụ trợ................................................................................19

2.1.3.2. Các tác tố trong TAGs......................................................................20

2.1.3.2.1. Tác tố thêm vào.........................................................................20

2.1.3.2.2. Tác tố thay thế:..........................................................................21

2.1.3.3. Những điều kiện kết hợp trên cây ...................................................21

2.1.3.4. Cây rỗng............................................................................................21

2.1.4. Phương pháp phân tích cú pháp dựa trên nguyên tắc...........................22

X

2.1.4.1.1. Thuyết X-Bar ( ) ....................................................................23

2.1.4.1.2. Nguyên lý Theta........................................................................23

2.1.4.1.3. Thuyết lọc vai (Case-filter) ......................................................23

2.1.4.1.4. Thuyết kết hợp...........................................................................23

2.1.4.1.5. Thuyết về tính cục bộ và trường rỗng......................................23

2.1.4.1.6. Thuyết dịch chuyển...................................................................24

2.2. Các cách tiếp cận trong việc liên kết từ/ngữ.................................................24

2.2.1. Char-Align – Hệ thống Termight...........................................................26

2.2.2. Phương pháp K-vec ................................................................................28

2.2.3. Phương pháp DK-vec .............................................................................29

2.2.4. Ánh xạ song ngữ với SIMR....................................................................30

2.2.5. Mô hình xác suất với thuật toán IPFP....................................................30

2.2.6. Mô hình dựa vào sự phân lớp (Class-based).........................................33

2.2.7. Mô hình liên kết dựa vào cách tiếp cận dịch máy thống kê (SMT).....33

2.3. Các phương pháp chiếu..................................................................................34

2.3.1. Chiếu nhãn từ loại...................................................................................34

2.3.1.1. Phương pháp trực tiếp......................................................................34

2.3.1.2. Phương pháp Noise-robust...............................................................34

2.3.1.3. Phương pháp sử dụng luật tương tác...............................................35

2.3.2. Chiếu quan hệ..........................................................................................35

2.3.2.1. Mô hình xác suất ..............................................................................35

2.3.2.2. Phương pháp DCA (Direct Correspondence Assumption)............35

2.3.2.3. Các phương pháp khác.....................................................................36

Chương 3: MÔ HÌNH THUẬT TOÁN....................................................................37

3.1. Phân tích cú pháp dựa trên nguyên tắc..........................................................37

3.1.1. Khái quát .................................................................................................37

3.1.2. Ý tưởng cơ bản của phương pháp phân tích dựa trên nguyên tắc........39

3.1.3. Một số ít những nguyên tắc thay thế cho rất nhiều luật .......................41

3.1.3.1. Những thành phần cơ bản................................................................41

3.1.3.2. Tham số.............................................................................................41

3.1.4. Câu hỏi đặt ra ..........................................................................................42

3.1.5. Các nguyên tắc........................................................................................43

X

3.1.5.1. Thuyết Xbar ( theory)...................................................................43

3.1.5.2. Tiêu chuẩn Theta (Theta Criterion).................................................44

3.1.5.3. Bộ lọc vai (Case-Filter)....................................................................45

3.1.5.4. Thuyết kết hợp(Binding Theory).....................................................47

3.1.5.5. Thuyết về tính cục bộ và trường rỗng.............................................47

3.1.5.6. Thuyết dịch chuyển..........................................................................48

3.1.6. Trật tự kết hợp các nguyên tắc...............................................................48

3.1.6.1. Dự đoán lỗi trước .............................................................................49

3.1.6.2. Mô hình động....................................................................................49

3.1.7. Các bước phân tích cú pháp ...................................................................50

3.1.7.1. Phân tích từ vựng..............................................................................50

3.1.7.2. Phân tích và tìm ra các cây cú pháp thích hợp ...............................50

3.1.7.3. Chọn cây cú pháp thích hợp nhất ....................................................55

3.1.7.4. Trọng số ............................................................................................55

3.1.7.5. Chọn cây ...........................................................................................55

3.2. Mô hình liên kết từ/ngữ trong song ngữ Anh-Việt.......................................56

3.2.1. Giới thiệu mô hình dịch máy thống kê..................................................56

3.2.2. Định nghĩa liên kết từ/ngữ......................................................................59

3.2.3. Mô hình ngôn ngữ...................................................................................62

3.2.4. Mô hình dịch ...........................................................................................64

3.2.4.1. Mô hình 1..........................................................................................67

3.2.4.2. Mô hình 2..........................................................................................69

3.2.4.3. Một cách đặt vấn đề khác.................................................................71

3.2.4.4. Mô hình 3..........................................................................................73

3.2.4.5. Mô hình 4..........................................................................................75

3.2.4.6. Mô hình 5..........................................................................................76

3.2.5. Thuật toán Ước lượng-Cực đại (Estimation-Maximization Algorithm –

viết tắt là thuật toán EM)...........................................................................................78

3.2.6. Cải tiến thuật toán EM trong mô hình 3, 4 và 5....................................80

3.2.7. Tìm liên kết từ tối ưu nhất......................................................................84

3.2.8. Cải tiến mô hình liên kết từ để liên kết ngữ..........................................85

3.3. Chiếu kết quả phân tích cú pháp sang Tiếng Việt........................................89

3.3.1. Chiếu nhãn từ loại...................................................................................89

3.3.2. Chiếu quan hệ..........................................................................................90

3.3.3. Sử dụng luật tương tác............................................................................90

Chương 4: CÀI ĐẶT THỰC NGHIỆM...................................................................91

4.1. Chương trình phân tích cú pháp quan hệ ......................................................91

4.1.1. Phân tích từ vựng....................................................................................91

4.1.1.1. Từ điển ..............................................................................................91

4.1.1.1.1. Cấu trúc .....................................................................................91

4.1.1.1.2. Sự phân loại động từ.................................................................94

4.1.1.1.3. Mục từ tham chiếu ....................................................................96

4.1.2. Phân tích cú pháp quan hệ......................................................................97

4.1.2.1. Từ điển chủ ngữ của động từ...........................................................97

4.1.2.2. Mạng cú pháp ...................................................................................98

4.1.2.3. Sơ đồ lớp...........................................................................................99

4.1.2.4. Kết quả đầu ra.................................................................................100

4.1.3. Các thuộc tính .......................................................................................101

4.2. Chương trình liên kết từ/ngữ........................................................................102

4.2.1. Phân tích................................................................................................102

4.2.1.1. Phân tích tổng quát.........................................................................103

4.2.1.2. Phân tích chi tiết.............................................................................104

4.2.1.2.1. Lưu đồ của mô hình huấn luyện dịch thống kê P(v | e) .......104

4.2.1.2.2. Lưu đồ của mô hình liên kết ngữ ...........................................105

4.2.2. Thiết kế..................................................................................................107

4.2.2.1. Sơ đồ lớp.........................................................................................107

4.2.2.2. Danh sách các thuộc tính của từng lớp .........................................108

4.2.2.3. Danh sách các phương thức của từng lớp.....................................109

4.2.2.4. Sơ đồ hoạt động tổng thể của các lớp cho quá trình huấn luyện.111

4.2.3. Cài đặt các hàm xử lý chính.................................................................112

4.2.3.1. Hàm khởi gán thông số t trong lớp Model1..................................112

4.2.3.2. Hàm khởi gán thông số a trong lớp Model2.................................112

4.2.3.3. Vòng lặp EM trong lớp Model1 ....................................................113

4.2.3.4. Vòng lặp EM trong lớp Model2 ....................................................113

4.2.3.5. Vòng lặp EM trong lớp Model3 ....................................................114

4.2.3.6. Tìm liên kết tối ưu nhất trong mô hình 1......................................115

4.2.3.7. Tìm liên kết tối ưu nhất trong mô hình 2......................................116

4.2.3.8. Tìm liên kết tối ưu nhất trong mô hình 3......................................117

4.3. Chiếu kết quả phân tích cú pháp sang Tiếng Việt......................................117

4.3.1. Chiếu nhãn từ loại.................................................................................117

4.3.2. Chiếu quan hệ........................................................................................118

4.3.3. Sử dụng luật tương tác..........................................................................119

Chương 5: KẾT QUẢ - ĐÁNH GIÁ – KẾT LUẬN – HƯỚNG PHÁT TRIỂN 120

5.1. Chương trình liên kết từ ...............................................................................120

5.1.1. Một số kết quả.......................................................................................120

5.1.2. Giao diện của chương trình thử nghiệm liên kết.................................124

5.1.3. Đánh giá.................................................................................................125

5.2. Chương trình phân tích quan hệ cú pháp ....................................................128

5.2.1. Kết quả...................................................................................................128

5.2.2. Đánh giá.................................................................................................130

5.2.2.1. Ngữ liệu mẫu ..................................................................................130

5.2.2.2. Kết quả đánh giá.............................................................................131

5.3. Chương trình chiếu kết quả phân tích cú pháp ...........................................132

5.3.1. Chiếu kết quả từ loại.............................................................................132

5.3.2. Chiếu kết quả phân tích quan hệ........................................................134

5.4. Kết luận.........................................................................................................134

5.5. Hướng phát triển...........................................................................................135

PHỤ LỤC A: Bảng qui ước các ký hiệu của mô hình dịch máy thống kê..............136

PHỤ LỤC B: Các thuộc tính trong phân tích cú pháp quan hệ................................139

PHỤ LỤC C: Bộ nhãn từ loại tiếng Anh...................................................................145

PHỤ LỤC D: Các mối quan hệ trong tiếng Anh.......................................................147

TÀI LIỆU THAM KHẢO ..........................................................................................149

LỜI NÓI ĐẦU

Với sự phát triển như vũ bão của khoa học kỹ thuật như hiện nay, tin học trở thành

một nhu cầu không thể thiếu được trong hầu hết các lĩnh vực của đời sống xã hội. Tuy

nhiên, việc giao tiếp giữa người và máy không phải lúc nào cũng tự nhiên, thuận lợi.

Nguyên nhân chính có lẽ là do có sự khác biệt lớn giữa hai thế giới người và máy.

Ngành học xử lý ngôn ngữ tự nhiên ra đời cũng nhằm mục đích xoá đi ngăn cách khác

biệt ngôn ngữ giữa người và máy tính.

Tuy nhiên, ngành xử lý ngôn ngữ tự nhiên là một lĩnh vực không dễ. Nó chỉ phát

triển mạnh trong mấy thập niên gần đây. Đặc biệt là đối với các ngôn ngữ phổ biến trên

thế giới như tiếng Anh, tiếng Hoa, tiếng Pháp… Quá trình nghiên cứu này đã để lại cho

nhân loại nhiều thành tựu to lớn. Nhu cầu về kế thừa những thành quả của tiếng Anh

để áp dụng cho các ngôn ngữ khác (như là tiếng Việt) là một nhu cầu thiết thực. Để

thừa hưởng được những thành quả này, chúng tôi nghiên cứu các kết quả của phân tích

cú pháp tiếng Anh và chiếu sang tiếng Việt thông qua liên kết từ/ngữ. Kết quả của việc

phân tích cú pháp tiếng Anh và chiếu sang tiếng Việt được làm ngữ liệu cho việc học,

giám sát và rút ra các luật chuyển đổi cú pháp giữa hai ngôn ngữ Anh-Việt để phục vụ

cho chương trình dịch tự động Anh Việt.

Các bước cơ bản cho việc chiếu kết quả phân tích cú pháp bao gồm ba bước chính:

đầu tiên là phân tích cú pháp cho ngôn ngữ nguồn (ở đây là tiếng Anh), sau đó liên kết

từ/ngữ, cuối cùng sử dụng kết quả liên kết từ/ngữ để chiếu sang ngôn ngữ đích (ở đây

là tiếng Việt). Trong bài luận văn này chúng tôi sẽ trình bày chi tiết các phương pháp

cho từng bước xử lý này.

Nội dung của bài luận văn được sắp xếp thành 5 chương như sau:

Chương 1: trình bày khái quát các bước giải quyết vấn đề.

Chương 2: chúng tôi trình bày sơ lược các cách tiếp cận cho các bước xử lý và

chọn ra cách tiếp cận tối ưu để nghiên cứu.

Chương 3: giới thiệu mô hình thuật toán chi tiết cho từng bước xử lý chính

theo các cách tiếp cận mà chúng tôi đã chọn và được trình bày trong chương 2.

Chương 4: cài đặt cụ thể cho các bước xử lý.

Chương 5: nêu ra một số kết quả và cách đánh giá các kết quả đó, và cuối

cùng là kết luận và đưa ra hướng phát triển.

Chương 1: TỔNG QUAN

Các bước cơ bản cho việc chiếu kết quả phân tích cú pháp bao gồm ba bước chính:

đầu tiên là phân tích cú pháp cho ngôn ngữ nguồn (ở đây là tiếng Anh), sau đó liên kết

từ/ngữ, cuối cùng sử dụng kết quả liên kết từ/ngữ để chiếu sang ngôn ngữ đích (ở đây

là tiếng Việt). Trong chương này chúng tôi sẽ giới thiệu sơ lược các bước chính này để

độc giả có thể nắm được khái quát các bước xử lý chính này.

1.1. Phân tích cú pháp quan hệ

Muốn có sự giao tiếp bằng ngôn ngữ tự nhiên giữa người và máy, đầu tiên máy tính

phải hiểu được ngôn ngữ tự nhiên. Bước đầu tiên để hiểu được một câu, máy phải biết

được cấu trúc của câu cũng như quan hệ giữa các thành phần trong câu. Xác định cấu

trúc, quan hệ này được gọi là phân tích cú pháp.

Tuy nhiên, muốn phân tích cú pháp thì đầu tiên phải đánh nhãn được từ loại của

từng từ trong câu, từ đó mới có thể tổng quát hoá cho máy hiểu được những cấu trúc và

những quan hệ ở mức tổng quát có thể được.

1.2. Liên kết từ/ngữ

Vấn đề dịch giữa các ngôn ngữ là vấn đề cổ xưa và rộng rãi. Nhiều nhà nghiên cứu

trên thế giới đã và đang làm việc cật lực để tìm ra các phương pháp cho dịch máy tự

động. Do đó có nhiều cách tiếp cận khác nhau trong việc dịch tự động. Mặc dù vậy,

vấn đề dịch máy vẫn còn là một vấn đề tranh cãi giữa các cách tiếp cận. Có một vài sự

bất đồng ý kiến về các phương pháp để thực hiện. Một nhóm các nhà nghiên cứu theo

cách tiếp cận cơ sở tri thức (knowledge-based) thì cho rằng để có được chất lượng dịch

1

Chương 1: TỔNG QUAN

cao thì đòi hỏi kiến thức ngôn ngữ học đáng kể và phải có cơ sở kiến thức lớn. Một

nhóm khác theo cách tiếp cận thống kê (statistic) thì cho rằng trong thực tế không thể

xây dựng một cơ sở tri thức đủ lớn để làm ngữ liệu khả thi, nhưng nếu dựa vào một

ngữ liệu song ngữ (tiếng Anh là bilingual corpus, parallel text, hay bitext) lớn để tạo ra

một mô hình thống kê thì có thể tạo một hệ thống dịch máy hiệu quả hơn. Còn một

nhóm khác nữa thì cho rằng cả hai phương pháp đều có mặt mạnh và mặt yếu riêng của

nó, và họ đã đề ra một phương pháp mới bằng cách kết hợp cả hai cách tiếp cận cơ sở

tri thức và tiếp cận thống kê, và cách tiếp cận đó được gọi là cách tiếp cận lai (hybrid

approach).

Đối với cách tiếp cận cơ sở tri thức thì công việc xây dựng từ điển, xây dựng các

luật chuyển đổi hầu hết đều được xây dựng bằng tay bởi các chuyên gia ngôn ngữ. Như

vậy, đối với cách tiếp cận này thì đòi hỏi công việc và thời gian rất lớn. Ngoài ra,

chúng ta sẽ đặt câu hỏi rằng: “Cơ sở dữ liệu cho từ điển và các luật chuyển đổi bao

nhiêu là đủ?”. Và đây là điểm yếu của cách tiếp cận cơ sở tri thức. Đối với cách tiếp

cận thống kê thì các công việc xây dựng từ điển và xây dựng các luật chuyển đổi hoàn

toàn tự động bằng máy tính. Máy tính sẽ thống kê và rút ra các thông số thống kê

tương ứng về từ/ngữ hay cấu trúc giữa hai ngôn ngữ cũng như xác suất dịch giữa hai

ngôn ngữ, và xác suất xuất hiện của từ/ngữ đó trong một ngữ cảnh nhất định nào đó.

Khuyết điểm của cách tiếp cận này là hoàn toàn dựa vào ngữ song ngữ đã được dịch

sẵn bởi con người, vì thế nếu dữ liệu được dịch tốt và ngữ liệu càng lớn thì độ chính

xác trong việc thống kê càng cao.

Trong những năm gần đây, dịch máy đã đạt được những thành công nhờ vào công

nghệ máy học, và việc học này được dựa vào ngữ liệu song ngữ. Để hệ dịch máy Anh-

Việt có thể tiếp cận theo hướng này thì bước đầu tiên trong việc xử lý ngữ liệu song

ngữ chính là việc liên kết từ/ngữ của ngôn ngữ nguồn (ở đây là tiếng Anh) với các

từ/ngữ của ngôn ngữ đích (ở đây là tiếng Việt). Việc liên kết từ/ngữ không thể đơn

thuần tra từ điển song ngữ Anh-Việt, vì sự phong phú trong cách dịch và tính đa nghĩa

2

Chương 1: TỔNG QUAN

của các từ trong cả hai ngôn ngữ. Ngoài ra còn có sự khó khăn rất lớn khác là do sự

khác biệt về mặt từ vựng hoá (lexicalization) của hai ngôn ngữ khác biệt về loại hình:

giữa tiếng Anh (một thứ tiếng biến hình) với tiếng Việt (một thứ tiếng đơn lập). Trong

khuôn khổ bài luận văn này, chúng tôi sẽ trình bày các mô hình dịch máy thống kê để

liên kết từ và cụm từ trong văn bản song ngữ Anh-Việt. Các mô hình mà chúng tôi đề

cập đến được thực hiện hoàn toàn tự động bằng máy. Ngữ liệu song ngữ mà chúng tôi

sử dụng khoảng một triệu câu song ngữ Anh-Việt được nhập từ cách sách song ngữ về

khoa học kỹ thuật và đã được đánh liên kết bằng tay. Ngữ liệu này sẽ được đưa vào hệ

thống để huấn luyện, tính xác suất, và thử nghiệm. Kết quả có được sau khi qua hệ

thống là các câu song ngữ trong ngữ liệu sẽ được liên kết.

Kết quả của việc liên kết từ/ngữ mà chúng tôi thu được trong cách tiếp cận thống kê

hết sức quan trọng đối với hệ dịch máy và góp phần không nhỏ cho các hướng tiếp cận

khác như: khảo sát sự thay đổi trật tự từ của cây cú pháp tiếng Việt và cây cú pháp

tiếng Anh, giải quyết vấn đề nhặp nhằng ngữ nghĩa, gán nhãn phân tích cú pháp cho

song ngữ Anh-Việt, … Trong bài luận văn này chúng tôi sẽ trình bày cụ thể ứng dụng

kết quả liên kết từ/ngữ cho việc gán nhãn phân tích cú pháp cho song ngữ Anh-Việt.

1.3. Chiếu quan hệ cú pháp

Chiếu quan hệ cú pháp là sử dụng kết quả liên kết từ/ngữ để ánh xạ kết quả của các

mối quan hệ cú pháp đã được đánh nhãn trong tiếng Anh sang tiếng Việt. Quá trình

chiếu này chia làm 2 giai đoạn: chiếu nhãn từ loại và chiếu quan hệ cú pháp.

1.3.1. Chiếu nhãn từ loại

Từ kết quả đánh nhãn từ loại trên câu tiếng Anh, thông qua mối liên kết từ/ngữ để

đánh nhãn từ loại cho các từ/ngữ trong câu tiếng Việt. Các vấn đề cần giải quyết là:

3

Chương 1: TỔNG QUAN

Trong tiếng Anh, các từ được cách nhau bằng khoảng trắng trong khi đó từ

trong tiếng Việt có thể gồm nhiều âm tiết ( mỗi âm tiết cách nhau bằng khoảng

trắng). Do đó, trước khi đánh nhãn từ loại cho tiếng Việt phải tách từ.

Tiếp theo, thông qua mối liên kết từ/ngữ, nhãn từ loại của tiếng Anh sẽ được

chiếu sang tiếng Việt. Tuy nhiên, đây không phải là phép ánh xạ 1-1 bởi vì: hệ

thống từ loại trong 2 ngôn ngữ là khác nhau. Ngoài ra, hai ngôn ngữ có sự khác

biệt lớn về phong cách trình bày. Do đó, không phải lúc nào cũng tìm ra được

sự tương ứng về từ loại giữa hai ngôn ngữ.

1.3.2. Chiếu quan hệ cú pháp

Cũng giống như chiếu nhãn từ loại, kết quả quan hệ cú pháp để chiếu sang tiếng

Việt thông qua mối liên kết từ/ngữ. Tuy nhiên, những nhập nhằng do sự khác biệt giữa

hai ngôn ngữ sẽ được giải quyết bằng các nhãn từ loại đã được đánh ở bước trước.

Hai bước này có mối quan hệ chặt chẽ, có thể nhờ vào từ loại để làm rõ cho quan hệ

cú pháp, ngược lại nhờ vào quan hệ cú pháp có thể làm rõ được những từ bị nhập

nhằng từ loại.

4

Chương 2: CÁC CÁCH TIẾP CẬN

Vấn đề chiếu kết quả phân tích cú pháp từ một ngôn ngữ này sang ngôn ngữ khác là

một nhu cầu cần thiết cho các nước mà việc xử lý ngôn ngữ tự nhiên chưa được phát

triển mạnh (như các nước đang phát triển trong đó có Việt Nam chúng ta). Do đó, trên

thế giới đã có nhiều nhà khoa học nghiên cứu nhiều cách tiếp cận khác nhau cho vấn

đề này. Các bước cơ bản để tiến hành công việc chiếu kết quả phân tích cú pháp bao

gồm: đầu tiên là phân tích cú pháp cho ngôn ngữ nguồn, sau đó liên kết từ/ngữ, cuối

cùng sử dụng kết quả liên kết từ/ngữ để chiếu sang ngôn ngữ đích. Phần đầu chúng tôi

sẽ giới thiệu các cách tiếp cận của các cách phân tích cú pháp cho ngôn ngữ nguồn

(tiếng Anh), phần hai chúng tôi sẽ giới thiệu các cách tiếp cận của liên kết từ/ngữ (từ

tiếng Anh sang tiếng Việt), cuối cùng chúng tôi trình bày các phương pháp chiếu sang

ngôn ngữ đích (tiếng Việt).

2.1. Phân tích cú pháp

2.1.1. Các phương pháp tiếp cận dùng luật phi ngữ cảnh (CFG)

2.1.1.1. Cách tiếp cận từ trên xuống (Top-Down)

Phân tích cú pháp theo cách tiếp cận từ trên xuống bắt đầu với kí hiệu S (sentence).

Đây chính là cấu trúc cao nhất của một câu và hình thành nên trạng thái ban đầu của

cấu trúc câu. Kế tiếp, mỗi kí hiệu trong chuỗi trạng thái hiện tại sẽ được viết lại thành

những cấu trúc thấp hơn dựa vào các luật có sẵn tạo thành một danh sách các kí hiệu.

Ví dụ : Câu bắt đầu với kí hiệu S, sau đó nó áp dụng luật S à NP VP. Danh sách kí

hiệu lúc này là (NP VP). Sau đó, kí hiệu NP được xét đến và thoả mãn luật NPà ART

N. Danh sách luật lúc này sẽ là (ART N VP)…

5

Chương 2: CÁC CÁCH TIẾP CẬN

Quá trình cứ lặp lại một cách đệ quy cho đến khi nào trạng thái của câu bao gồm

toàn những kí hiệu kết thúc. Tuy nhiên, đến lúc này, câu nhập vào cũng phải được đưa

vào kiểm tra để bảo đảm rằng toàn bộ câu đã được phân tích. Vì vậy, dù gặp phải một

danh sách bao gồm toàn những kí hiệu kết thúc nhưng câu vẫn còn từ chưa được phân

tích thì cấu trúc tìm được là một cấu trúc sai.

Tuy nhiên, bởi vì từ vựng của một ngôn ngữ là rất lớn cho nên có một loại luật dạng

kí hiệu kết thúcà từ vựng sẽ là rất lớn. Để tránh gặp phải trường hợp này, người ta đã

tách riêng nó thành một từ điển gọi là từ điển từ loại.

Book : N , V

Like : V , RB

…

Do từ điển từ loại đã được tách ra nên trong danh sách luật sẽ không còn luật nào

chứa luật từ vựng.

Một ví dụ đơn giản với bộ luật bao gồm 5 luật như sau:

Luật 1

Luật 2

Luật 3

Luật 4

Luật 5

S à NP VP

NP à ART N

NP à ART ADJ N

VP à V

VP à V NP

Bảng 2.1. Ví dụ một số luật

Trạng thái của câu bây giờ được định nghĩa thành một cặp : một danh sách kí hiệu

và một con số chỉ ra vị trí hiện tại trong câu. Vị trí này được đánh vào giữa 2 từ với 1

là vị trí trước từ đầu tiên ( từ số 1).

Ví dụ :

₁I ₂eat ₃rice₄

Và một trạng thái của câu:

((N VP)2)

6

Chương 2: CÁC CÁCH TIẾP CẬN

Trạng thái này chỉ ra rằng : chương trình phân tích muốn tìm ra một N (danh từ) và

được theo sau bởi một (ngữ động từ), bắt đầu từ vị trí 2. Dựa vào việc kí hiệu đầu tiên

trong danh sách kí hiệu có là kí hiệu từ vựng hay không mà trạng thái mới sẽ được hình

thành dựa trên trạng thái cũ.

Như vậy trạng thái kế tiếp sẽ là:

((VP)3)

Trạng trái này nói lên ý nghĩa là : cần phải tìm một V bắt đầu tại vị trí số 3 trong câu

nhập. Nếu kí hiệu đầu tiên là kí hiệu không kết thúc, giống như VP, thì viết lại kí hiệu

này bằng luật cú pháp phù hợp.

Trong ví dụ trên, nếu áp dụng luật (4) thì trạng thái kế tiếp sẽ là :

((V)3)

trong khi đó, nếu áp dụng luật (3) thì trạng thái kế tiếp sẽ là :

((V NP)3)

Thuật toán phân tích bảo đảm rằng tất cả các giải pháp đều được xét tới. Chính vì

đều này mà khi có nhiều hơn một trạng thái mới có thể được hình thành thì phải xử

dụng tất cả các trạng thái cho chép này. Một kĩ thuật đơn giản được gọi là quay lui theo

vết(backtracking). Theo cách tiếp cận này, thay vì chỉ sử dụng một trạng thái có thể thì

tất cả các trạng thái đều được xét tới. Lưu các trạng thái mới này thành những trạng

thái dự phòng (backup state) rồi sau đó xét qua hết tất cả các trạng thái này. Nếu có

một trạng thái nào đó dẫn đến không thể đi tiếp được nữa thì loại nó ra khỏi danh sách.

2.1.1.2. Thuật toán phân tích cú pháp từ trên xuống (Top-Down)

Thuật toán phát sinh ra một danh sách các trạng thái có thể gọi là posssibilities list.

Phần tử đầu tiên trong danh sách được chọn làm trạng thái hiện tại.

Thuật toán bắt đầu với trạng thái khởi tạo là ((S) 1) và không có trạng thái dự

phóng.

7

Chương 2: CÁC CÁCH TIẾP CẬN

Bước 1 : Chọn trạng thái hiện tại : phần tử đầu tiên trong possibilities list – gọi là

C - được chọn làm trạng thái hiện hành . Nếu danh sách này rỗng thì thuật

toán thất bại – không có một cấu trúc nào phù hợp với câu nhập vào.

Bước 2 : Nếu C rỗng và từ đang xét nằm ở cuối câu thì thuật toán thành công.

Bước 3 : Ngược lại, phát sinh ra trạng thái mới có thể:

Bước 4 : Nếu kí hiệu đầu tiên trong danh sách C là một kí hiệu từ vựng (từ loại) và

từ trong câu tại vị trí đang xét phù hợp với kí hiệu từ vựng này thì xoá đi

kí hiệu đầu tiên trong possibilities list và cập nhật vị trí từ vựng trong câu

tăng lên 1.

Bước 5 : Ngược lại, nếu kí hiệu đầu tiên trong danh sách kí hiệu của C là một kí

hiệu không kết thúc (non-terminal) thì phát sinh một trạng thái mới cho

mỗi luật mà có thể viết lại kí hiệu không kết thúc đó

2.1.1.3. Cách tiếp cận Từ dưới lên (Bottom-Up)

Giống như tên được gọi, quá trình hình thành cây cú pháp của phương pháp này đi

từ mức thấp lên mức cao hay từ lá lên gốc. Điểm khác biệt giữa cách tiếp cận từ dưới

lên và từ trên xuống được trình bày ở trên là các mà luật ngữ pháp được sử dụng. Ví dụ

khi xét đến luật :

NP à ART ADJ N

Trong hệ thống từ trên xuống, bạn sử dụng luật để tìm NP bằng các tìm kiếm chuỗi

ART ADJ N. Ngược lại, trong hệ thống từ dưới lên, từ kết quả hình thành ở bước trước

đó, bạn đã có một chuỗi ART ADJ N và bạn gán cho chuỗi này nhãn là NP.

Thao tác cơ bản trong hệ thống từ dưới lên là tìm các chuỗi tuần tự phù hợp với vế

phải và thay thế nó bằng vế trái của luật. Bạn có thể sử dụng xây dựng một bộ phân

tích cú pháp từ dưới lên đơn giản bằng việc xây dựng hai tiến trình : tiến trình so khớp

và tiến trình tìm kiếm. Cũng giống như cách tiếp cận từ dưới lên, trạng thái ban đầu sẽ

được khởi tạo và trạng thái cuối cùng dần được hình thành. Tuy nhiên, trạng thái khởi

8

Chương 2: CÁC CÁCH TIẾP CẬN

tạo ở đây là danh sách các từ trong câu và trạng thái thành công (nếu có) là kí hiệu S.

Trạng thái thành công có thể được hình thành từ việc tìm và tất cả các cách có thể để :

ü Viết lại một từ bằng từ loại có thể có của từ đó

ü Thay thế một chuỗi kí hiệu phù hợp với vế phải luật bằng kí hiệu vế trái.

Không may, những thao tác đơn giản trên đây lại có chi phí rất cao bởi vì nó cứ lặp

đi lặp lại công việc so khớp chuỗi kí hiệu với vế phải của các luật, điều này tăng gấp

bội công việc cần thiết thực sự cần phải làm. Để tránh tình trạng này, cấu trúc dữ liệu

gọi là sơ đồ (chart) được sử dụng để lưu lại các kết quả của các quá trình so sánh đã

được thực hiện để tránh đi việc thực hiện lặp lại này.

Việc so khớp luôn để ý tới một thành phần gọi là khoá (key). Để tìm luật phù hợp

với chuỗi, ta chỉ tìm kiếm những luật bắt đầu bằng trường khoá này để tìm ra luật có vế

phải trùng khớp với chuỗi kí hiệu.

Giả sử bạn đang phân tích một câu bắt đầu với ART. Kí hiệu ART này được xem

như là khoá. Như vậy, có 2 luật được tìm ra phù hợp với khoá là luật (2)(NP à ART

N) và luật (3) (NP à ART ADJ N). Để lưu lại dấu vết để có thể biết được trong lần

phân tích kế tiếp, sử dụng một dấu chấm ( ) để chỉ ra vị trí đã được xét tới cho đến

thời điểm hiện tại. Ta có 2 bản ghi như sau:

NP à ART ADJ N

NP à ART

(2’)

N

(3’)

Nếu khoá kế tiếp là ADJ thì luật 4 có thể được bắt đầu và và bản ghi 2’ được thay

đổi như sau:

NP’ à ART ADJ N (2’’)

Sơ đồ sẽ bảo đảm lưu trữ toàn bộ những luật ứng viên đã được xét. Nó cũng lưu trữ

bản ghi của những luật trùng khớp chỉ mới phần đầu.Những bản ghi này được gọi là

những cung đang hoạt động. Ví dụ, sau khi tìm ra ART theo sau bởi một ADJ trong ví

dụ trước đây, bạn sẽ có một sơ đồ như hình 2.1.

9

Chương 2: CÁC CÁCH TIẾP CẬN

ART

ADJ

1

2

3

NP à ART ADJ N

NP à ART N

NP à ADJ N

NP à ART ADJ N

Hình 2.1. Phân tích cú pháp bằng phương pháp Bottom-Up

Ta có thể diễn giải ý nghĩa của sơ đồ trên như sau:

Có 2 luật ứng viên đã hoàn tất là ART từ vị trí 1 đến 2 và ADJ từ vị trí 2 đến 3. Có

4 cung hoạt động tương ứng với 4 luật ứng viên tương ứng với 4 mũi tên trên hình.

Chiều của mũi tên là chiều đi từ thấp lên cao ( từ lá lên gốc của cây cú pháp). Ý nghĩa

của các cung trên hình là

ü Có 1 khả năng cho NP xuất hiện tại vị trí 1 cần một ADJ bắt đầu tại vị trí 2

ü Có 1 khả năng cho NP xuất hiện tại vị trí 2 cần một N bắt đầu tại vị trí 2

ü Có 1 khả năng cho NP xuất hiện tại vị trí 2 cần một N bắt đầu tại vị trí 3

ü Có 1 khả năng cho NP xuất hiện tại vị trí 1 cần một N bắt đầu ở vị trí 3

Phép toán cơ bản của phép phân tích cú pháp dựa trên sơ đồ là kết hợp các ứng cử

viên đã hoàn tất với các cung đang hoạt động. Một luật mới hoàn tất sẽ được giữ lại

trong một danh sách được gọi là nhật kí cho đến khi nó được thêm vào sơ đồ.

10

Chương 2: CÁC CÁCH TIẾP CẬN

2.1.1.4. Thuật toán phân tích cú pháp Earley

Giải thuật phân tích cú pháp là một giải pháp kết hợp 2 phương pháp vừa trình bày ở

trên. Trước khi đi chi tiết vào thuật toán, ta sẽ xét lại một số ưu khuyết điểm của từng

phương pháp để thấy được lợi điểm khi kết hợp 2 phương pháp lại với nhau.

ü Thuật toán phân tích cú pháp Top-Down có một ưu điểm là có một tầm nhìn

bao quát. Một từ có thể nhập nhằng về từ loại. Tuy nhiên, nếu một từ loại được

xét được thấy không có khả năng hình thành một cấu trúc cú pháp hợp lí thì nó

sẽ được loại bỏ ngay lập tức và khả năng tiếp theo sẽ được xét đến. Tuy nhiên,

bất lợi của thuật toán phân tích này là nó phải so sánh lặp lại nhiều lần những

trường giống nhau. Như trong ví dụ trên thì mạo từ a được xét là ART đến 2 lần.

Điều này làm tăng chi phí lên một cách không cần thiết.

ü Trong khí đó, thuật toán phân tích cú pháp Bottom-Down chỉ xét một từ với

một từ loại chỉ một lần. Tuy nhiên, bởi vì nó xét đến nhãn kí hiệu trước nên tất

cả các nhãn của một từ sẽ được xét tới mà không xét ngay đến tình hợp lí của từ

loại này. Đây chính là bất lợi của giải thuật phân tích cú pháp từ dưới lên.

Thuật toán phân tích cú pháp Earley sẽ tận dụng lợi điểm của cách tiếp cận từ dưới

lên bằng cách đi từ gốc về lá. Tuy nhiên, để tránh phải xét đi xét lại cùng một từ loại

cho một từ duy nhất, giải thuật này sẽ đi cùng một lúc tất cả các hướng (tương ứng với

các luật ứng viên thoả mãn xét đến thời điểm hiện tại). Đây chính là điểm tương đồng

của Earley so với cách tiếp cận từ dưới lên. Như vậy nó đã khai thác được ưu điểm của

hai phương pháp trên và cũng đồng nghĩa với việc loại bỏ đi những khuyết điểm của

từng phương pháp.

Bây giờ ta sẽ đi tìm cách tiếp cận cụ thể của phương pháp Earley để thực hiện điều

vừa trình bày trên.

Thuật toán phân tích Earley:

Gọi n là số từ trong câu. Ta xây dựng các bảng I_ivới i = 0,1,2….,n

11

Chương 2: CÁC CÁCH TIẾP CẬN

Bước 1 : Đầu tiên bảng I₀được xác định bằng tất cả các luật có dạng S à , thì

một trạm có dạng S à ,0 sẽ được thêm vào bảng I₀gọi là một trạm.

Bước 2 : Nếu [B

B , 0] thuộc I₀.

Bước 3 : Giả sử là [A B , 0] là một trạm trong I₀, ta thêm vào I₀, cho tất cả

các sản sinh trong P có dạng B , trạm [B , 0] (miễn là trạm này

chưa có trong I₀).

Bước 4 : Các bảng I_j( với j = 1…n ) lần lượt được hình thành như sau:Với mỗi

trạm [B a , i] trong bảng I_j-1mà trong đó a = a_j, ta thêm [B

, 0] thuộc I_0,ta thêm [A

B , 0] cho tất cả các trạm [A

a

, i] vào bảng I_j. Lặp lại các bước 5 và 6 cho tới khi không còn trạm nào

được thêm vào.

Bước 5 : Giả sử [A

có những trạm nào có dạng [B

thấy ta thêm [B , k] vào bảng I_j.

Bước 6 : Giả sử [A B , i] là một trạm trong bảng I_j. Đối với mọi sản sinh B

trong P, ta thêm [B , j] vào bảng I_j.

, i] là một bảng trong bảng I_j. Kiểm tra trong bảng I_ixem

A , k] hay không, với mỗi trạm tìm

A

2.1.1.5. Mạng ngữ pháp lan truyền

Cho đến lúc này, ta chỉ mới xét đến một phương pháp biểu diễn ngữ pháp gọi là luật

phi ngữ cảnh. Bây giờ ta xét đến một hình thức biểu diễn khác của ngữ pháp được sử

dụng rất rộng rãi trong các ứng dụng dó là mạng ngữ pháp lan truyền. Mạng ngữ pháp

này dựa trên các nốt và cung. Có 2 nốt đặc biệt là nốt bắt đầu và nốt kết thúc.

Để đơn giản, ta bắt đầu bằng một ví dụ cụ thể: biểu diễn NP (với các luật đã được

trình bày trong phần trước bằng mạng ngữ pháp).

NP à ART NP1

12

Chương 2: CÁC CÁCH TIẾP CẬN

NP1 à ADJ NP1

NP1 à N

Lúc này mạng ngữ pháp sẽ là

pop

art

n

N

NP1

adj

NP2

NP:

Hình 2.2.Mạng ngữ pháp NP

Trạng thái khởi đầu có nhãn là NP. Bắt đầu tại trạng thái khởi tạo, bạn có thể đi

ngang qua một cung nếu từ loại của từ đang xét giống với nhãn của cung đó. Nếu một

cung được chấp thuận thì vị trí của từ sẽ được cập nhật đến từ kế tiếp.

Một mạng lan truyền đơn giản như trên gọi là máy trạng thái hữu hạn (finete state

machines – FSMs). Loại mạng này là một công cụ đắc lực đối với ngữ pháp đúng quy

tắc thông thường nhưng không đủ sức mạnh để mô tả tất cả các ngôn ngữ có thể biễu

diễn dưới dạng luật phi ngữ cảnh (CFG). Để có được sức mạnh mô tả của CFGs, ta cần

quan tâm đến mạng ngữ pháp đệ quy. Cũng giống như mạng ngữ pháp đơn giản, tuy

nhiên mạng ngữ pháp đệ quy có một điểm mới hơn là nó cho phép các cung có thể là

một mạng khác (tương ứng với một nhãn không kết thúc) thay vì là một nhãn từ loại).

Như trong ví dụ trong hình 2.3, trường từ loại sẽ được biểu diễn là chữ thường,

trường tham chiếu đến một mạng ngữ pháp khác được kí hiệu là chữ in hoa. nốt S và

S₁được nối với nhau bằng một cung NP- đây chính là mạng ngữ pháp được biểu diễn

trong hình 2.2.

13

Chương 2: CÁC CÁCH TIẾP CẬN

NP

verb

NP

pop

S

S1

S2

S3

Hình 2.3. Mạng ngữ pháp đệ quy

Loại cung

Ví dụ

Ý nghĩa

CAT

Verb

Thành công chỉ khi từ đang xét có thể đánh nhãn

CAT

WRD

PUSH

JUMP

POP

Of

Thành công chỉ khi từ đang xét giống với WRD

Chỉ thành công khi mạng con thành công

Luôn thành công

NP

Jump

Pop

Thành công, trả về dấu hiệu thành công của mạng

Bảng 2.2.Ý nghĩa của các cung trong mạng ngữ pháp

Thuật toán phân tích cú pháp Top-Down sử dụng mạng ngữ pháp lan truyền đệ quy:

Các khái niệm:

ü Vị trí hiện tại: Con trỏ chỉ đến từ kế tiếp được xét.

ü Nốt hiện tại: Nốt đang xét đến trong mạng ngữ pháp.

ü Điểm trả về: Một ngăn xếp của những nốt trong mạng khác. Bạn sẽ chỉ tiếp

tục nếu mạng này trả về giá trị thành công (pop).

Giống như cách tiếp cận từ trên xuống truyền thống, nhưng thay vì xét tính hợp lệ

của một luật thì trong mạng ngữ pháp này, ta xét đến việc có thể di chuyển qua một

cung có được hay không

Trường hợp 1 : Nếu tên cung là nhãn từ loại và từ kế tiếp trong câu thuộc nhãn

từ loại đó

Thì

14

Chương 2: CÁC CÁCH TIẾP CẬN

ü Cập nhật vị trí hiện tại tới từ kế tiếp.

ü Cập nhật nốt hiện tại tới nốt đích của cung hiện tại.

Trường hợp 2 : Nếu cung là dạng cung đưa vào (push) một mạng N

Thì

ü Thêm đích của cung đến điểm trả về.

ü Cập nhật nốt hiện tại là nốt đầu tiên trong mạng N.

Trường hợp 3 : Nếu cung thuộc dạng cung đưa ra (pop) và điểm trả về khác

rỗng

Thì Xoá phần tử đầu tiên trong điểm trả về và lấy đó làm nốt

hiện tại.

Trường hợp 4 : Nếu cung thuộc dạng cung đưa ra (pop) và điểm trả về là rỗng

và không còn từ nào bị bỏ đi.

Thì phân tích cú pháp thành công.

2.1.2. Phương pháp TBL (Transformation-Based Error-Driven

Learning)

Phương pháp TBL được giới thiệu lần đầu tiên bởi Eric Brill vào năm 1993. Đến

năm 1995 thì nó được công bố rộng rãi. Đây là một phương pháp rất mạnh trong lĩnh

vực ngôn ngữ học và được áp dụng để giải quyết nhiều bài toán ngôn ngữ khác nhau.

Ý tưởng cơ bản của phương pháp TBL là dựa vào một ngữ liệu đã được đánh nhãn

đúng, nó cố gắng tự đi tìm những luật để sửa những lỗi sai theo nguyên lí tham lam.

Những luật được rút ra bởi TBL không giống với những luật phi ngữ cảnh ở các

phương pháp trước. Nó là những luật tương tác.

Giải thuật TBL có 2 giai đoạn riêng biệt là giai đoạn học và giai đoạn chạy.

Trong giai đoạn học, dựa vào ngữ liệu đã được đánh nhãn, hệ thống sẽ cố tìm ra các

luật tương tác để có thể đánh nhãn càng giống càng tốt.

15

Chương 2: CÁC CÁCH TIẾP CẬN

Ngược lại, trong giai đoạn chạy, dựa vào bộ luật đã được rút ra để đánh nhãn cho

một tập văn bản chưa được đánh nhãn.

Quá trình học:

Đầu tiền, ngữ liệu đã được đánh nhãn đúng sẽ được bỏ nhãn đi tạo thành một văn

bản không có nhãn.

Kế đó, văn bản không có nhãn này sẽ được đánh nhãn ban đầu gọi là nhãn ngây thơ

hay nhãn cơ sở. Nhãn ngây thơ có thể là sai rất nhiều theo cách đánh nhãn ngẫu nhiên

hay cũng có khi khá chính xác nếu sử dụng một chương trình đánh nhãn nào đó. Trong

lĩnh vực phân tích cú pháp, nhãn cơ sở có thể được đánh một cách đơn giản theo cách

phân câu thành những ngữ theo nguyên tắc nhị phân.

Có 2 điều cần lưu ý khi đánh nhãn cơ sở:

ü Không nên sử dụng những đặc trưng của ngôn ngữ, điều này làm giảm tính

cơ động của chương trình.

ü Hãy để cho chương trình tự học ra những luật hữu ích, không nên tốn quá

nhiều thời gian để tự xử lí.

Dựa vào các mẫu luật đã được tạo sẵn, các luật ứng viên sẽ được hình thành và được

áp dụng vào văn bản đã được đánh nhãn cơ sở. Khác với các luật CFG đã được trình

bày trong các chương trước, luật TBL là các luật chuyển đổi dùng để thay đổi nhãn của

từ. Quá trình đánh nhãn cú pháp sẽ là quá trình thêm và xoá các nhãn này.

Từng luật ứng viên, khi đưa vào áp dụng thử trên văn bản đã được đánh nhãn cơ sở

theo từng câu một. Điểm sẽ được chấm cho mỗi luật làm căn cứ cho việc chọn lựa luật

tốt nhất. Quy tắc chấm điểm như sau:

ü Nếu luật không làm thay đổi gì thì không thay đổi điểm.

ü Nếu luật sửa đúng thành sai thì cộng một điểm.

ü Nếu luật sửa sai thành đúng thì trừ một điểm.

ü Nếu luật sửa sai thành sai thì không thay đổi điểm.

16

Chương 2: CÁC CÁCH TIẾP CẬN

Sau khi tất cả các luật đã được áp dụng cho tất cả các câu trong văn bản, chọn ra

một luật có điểm lớn nhất để giữ lại nếu điểm nó vượt một ngưỡng cho trước. Dùng

luật này để sửa nhãn cho văn bản đã được đánh nhãn cơ sở. Bỡi vì điềm cua luật này

luôn dương (bởi ngưỡng là số dương) nên độ chính xác của văn bản bây giờ đã được

tăng lên.

Quá trình trên lại được lặp lại: từng luật sẽ được áp dụng thử trên văn bản đánh nhãn

cơ sở đã được sữa lại bởi luật được chọn. Luật tốt nhất lại được chọn ra…

Quá trình học sẽ ngừng khi tại một bước, số điểm của luật tốt nhất không vượt quá

một ngưỡng cho phép. Nếu ngưỡng này được chọn quá lớn, số luật rút ra sẽ không

được nhiều và độ chính xác không được cao. Ngược lại nếu ngưỡng được chọn quá

nhỏ sẽ dẫn đến tình trạng quá luyện.

17