Luận văn Xây dựng chương trình chuyển đổi cây cú pháp trong hệ dịch tự động Anh - Việt

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 LƯU THÙY NGÂN - 9912621 ĐỖ XUÂN QUANG - 9912652 XÂY DỰNG CHƯƠNG TRÌNH CHUYỂN ĐỔI CÂY CÚ PHÁP TRONG HỆ DỊCH TỰ ĐỘNG ANH - VIỆT LUẬN VĂN CỬ NHÂN TIN HỌC GIÁO VIÊN HƯỚNG DẪN TS. ĐINH ĐIỀN NIÊN KHÓA 1999-2003 Luận văn tốt nghiệp Trang 2 Lời cảm tạ Lời đầu tiên chúng em xin chân thành cảm ơn thầy Đinh Điền, người đã trực tiếp hướng dẫn chúng em hoàn thành luận văn này. Thầy là người đã truyền thụ cho chúng em rất nhiều kiến thức về tin học và ngôn ngữ học, giúp chúng em có được hiểu biết sâu hơn về một trong các ứng dụng có ý nghĩa vô cùng to lớn trong cuộc sống của tin học – vấn đề dịch máy. Chúng em cũng xin chân thành cảm ơn các thầy cô trong khoa Công nghệ thông tin đã tận tình chỉ bảo và giúp đỡ cho chúng em trong suốt thời gian chúng em học đại học và trong quá trình chúng em thực hiện luận văn. Chúng con xin chân thành cảm ơn ba mẹ, các anh và những người thân trong gia đình đã nuôi dạy, tạo mọi điều kiện tốt nhất cho chúng con học tập và động viên chúng con trong thời gian thực hiện luận văn. Và cuối cùng, chúng tôi xin gởi lời cảm ơn đến tất cả bạn bè và nhất là các bạn trong nhóm VCL (Vietnamese Computational Linguistics), những người đã hỗ trợ chúng tôi trong quá trình chúng tôi hoàn thiện luận văn này. Tp. Hồ Chí Minh, tháng 07 năm 2003 Nguyễn Lưu Thùy Ngân - 9912621 Đỗ Xuân Quang - 9912652 Luận văn tốt nghiệp Trang 3 NHẬN XÉT CỦA GIÁO VIÊN HƯỚNG DẪN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Tp. Hồ Chí Minh, tháng 07 năm 2003 TS. Đinh Điền Luận văn tốt nghiệp Trang 4 NHẬN XÉT CỦA GIÁO VIÊN PHẢN BIỆN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Tp. Hồ Chí Minh, tháng 07 năm 2003 Giáo viên phản biện Luận văn tốt nghiệp Trang 5 Lời nói đầu Cho đến nay, sau hơn 50 năm phát triển, dịch máy chứng tỏ là một ứng dụng vô cùng thiết thực, đồng thời cũng là một bài toán khá hóc búa đặt ra cho các nhà khoa học trên toàn thế giới. Từ đầu thập niên 1960, các nhà khoa học đã đúc kết lại ba chiến lược dịch máy cơ bản, đó là dịch trực tiếp, dịch thông qua ngôn ngữ trung gian và dịch dựa trên chuyển đổi. Và qua thực tế, chiến lược dịch dựa trên chuyển đổi đã khẳng định được tính hiệu quả và tiềm năng của nó, và đây cũng là cách tiếp cận mà chúng em đã và đang theo đuổi để xây dựng một hệ dịch tự động từ tiếng Anh sang tiếng Việt. Trong hệ dịch dựa trên sự chuyển đổi, khối chuyển đổi cây cú pháp (cấu trúc) giữ một vai trò quan trọng, quyết định chất lượng hệ dịch. Vì lý do đó, chúng em đã quyết định chọn “Xây dựng chương trình chuyển đổi cây cú pháp trong hệ dịch Anh-Việt” làm đề tài luận văn tốt nghiệp cử nhân của mình. Khối chuyển đổi cây cú pháp đảm nhiệm việc thay đổi trật tự, chèn, xoá các thành phần trong cây cú pháp của câu tiếng Anh sao cho sau khi hoàn tất việc gắn nghĩa, ta sẽ thu được câu tiếng Việt có trật tự từ hợp lý. Luận văn được tổ chức thành các phần chính sau: ™ Chương 1: Giới thiệu tầm quan trọng, mục tiêu, phạm vi của đề tài, cơ sở lý thuyết ngôn ngữ học, tin học và hướng tiếp cận vấn đề. ™ Chương 2: Điểm qua các cách tiếp cận chuyển đổi cấu trúc. ™ Chương 3: Thuật toán nền tảng, mô hình học và mô hình áp dụng chuyển đổi cây cú pháp. ™ Chương 4: Thiết kế – Cài đặt ™ Chương 5: Thử nghiệm – đánh giá ™ Chương 6: Kết quả – Kết luận – Hướng phát triển ™ Phần phụ lục. Tài liệu tham khảo. Luận văn tốt nghiệp Trang 6 Mục lục Lời nói đầu.......................................................................................................5 Mục lục.............................................................................................................6 Danh sách các hình .......................................................................................11 Danh sách các bảng.......................................................................................13 Chương 1........................................................................................................14 TỔNG QUAN VỀ CHUYỂN ĐỔI CÂY CÚ PHÁP......................................14 1.1 Đặt vấn đề .......................................................................................14 1.2 Các chiến lược dịch máy................................................................16 1.1.1 Chiến lược dịch trực tiếp.......................................................................16 1.1.2 Chiến lược dịch dựa trên ngôn ngữ trung gian .....................................17 1.1.3 Chiến lược dịch dựa trên sự chuyển đổi ...............................................18 1.2 Vai trò của chuyển đổi cây cú pháp trong cách tiếp cận dựa trên chuyển đổi ..................................................................................................20 1.3 Cơ sở lý thuyết................................................................................22 1.3.1 Cơ sở lý thuyết ngôn ngữ học của việc chuyển đổi ..............................23 1.3.2 Cơ sở lý thuyết tin học - Hướng tiếp cận vấn đề ..................................33 Chương 2........................................................................................................35 CÁC HƯỚNG TIẾP CẬN CHUYỂN ĐỔI CẤU TRÚC TRONG DỊCH MÁY................................................................................................................35 2.1 Hướng tiếp cận dựa trên luật cố định ..........................................35 2.1.1 Cơ chế chuyển đổi của cách tiếp cận dựa trên luật cố định ..................35 2.1.2 Nhận xét ................................................................................................38 Luận văn tốt nghiệp Trang 7 2.2 Hướng tiếp cận sử dụng case-frame.............................................39 2.2.1 Chuyển đổi các thông tin cấp độ câu ....................................................40 2.2.2 Chuyển đổi ngữ động từ........................................................................41 2.2.3 Sự chuyển đổi của định ngữ, bổ ngữ.....................................................42 2.2.4 Tự điển chuyển đổi................................................................................43 2.2.5 Nhận xét ................................................................................................44 2.3 Hướng tiếp cận sử dụng TAG đồng bộ (STAG)..........................44 2.3.1 Văn phạm TAG.....................................................................................45 2.3.2 TAG đồng bộ (STAG) ..........................................................................49 2.3.3 Nhận xét ................................................................................................52 2.4 Cách tiếp cận phân tích ngữ pháp song song ..............................53 2.4.1 Ngữ pháp chuyển dịch đảo có thống kê (SITG) ...................................53 2.4.2 Thuật toán phân tích cú pháp song song với SITG...............................55 2.4.3 Đánh nhãn cấu trúc................................................................................58 2.4.4 Chuyển đổi cây cú pháp song song cho cả hai ngôn ngữ .....................58 2.4.5 Nhận xét ................................................................................................59 2.5 Cách tiếp cận dựa trên cấu trúc vị từ - đối số .............................60 2.5.1 Rút trích các cấu trúc vị từ - đối số .......................................................60 2.5.2 Khối chuyển đổi cấu trúc ......................................................................62 2.5.3 Nhận xét ................................................................................................64 2.6 Tổng kết chương ............................................................................65 Chương 3........................................................................................................66 MÔ HÌNH CHUYỂN ĐỔI CÂY CÚ PHÁP .................................................66 3.1 Phương pháp học hướng lỗi dựa trên sự chuyển trạng thái ......66 3.1.1 Ý tưởng .................................................................................................66 3.1.2 Thuật toán học TBL của Eric Brill........................................................68 3.1.3 Nhận xét ................................................................................................70 Luận văn tốt nghiệp Trang 8 3.2 Thuật toán học nhanh FnTBL......................................................71 3.2.1 Hình thức hóa TBL ...............................................................................72 3.2.2 Thuật toán FnTBL.................................................................................73 3.3 Mô hình chuyển đổi cây cú pháp sử dụng thuật toán FnTBL ...78 3.3.1 Mô hình áp dụng chuyển đổi cây cú pháp ............................................80 3.3.2 Mô hình học luật chuyển đổi bằng phương pháp học FnTBL ..............82 3.4 Nâng cao khả năng mở rộng cho mô hình học ............................95 Chương 4........................................................................................................97 CÀI ĐẶT CHƯƠNG TRÌNH ........................................................................97 4.1 Thiết kế ...........................................................................................97 4.1.1 Mô hình tổng thể ...................................................................................97 4.2 Thuật toán gán nhãn cơ sở cho ngữ liệu ......................................99 4.2.1 Thuật toán..............................................................................................99 4.2.2 Xây dựng cây cú pháp...........................................................................99 4.2.3 Xây dựng cây quan hệ.........................................................................103 4.2.4 Thuật toán chuyển đổi theo nguyên tắc ..............................................105 4.3 Học chuyển đổi cùng cấp.............................................................106 4.3.1 Xây dựng ngữ liệu học ........................................................................106 4.3.2 Xây dựng khung luật cho bộ học chuyển đổi cùng cấp ......................108 4.3.3 Sơ đồ lớp của chương trình học ..........................................................114 4.3.4 Xây dựng bộ luật (giai đoạn học cùng cấp) ........................................114 4.3.5 Áp dụng bộ luật chuyển đổi cùng cấp.................................................116 4.4 Học chuyển đổi khác cấp.............................................................117 4.4.1 Xây dựng ngữ liệu học ........................................................................117 4.4.2 Xây dựng khung luật cho quá trình học chuyển đổi khác cấp ............120 4.4.3 Sơ đồ lớp của chương trình học ..........................................................125 4.4.4 Xây dựng bộ luật (giai đoạn học khác cấp) ........................................125 Luận văn tốt nghiệp Trang 9 4.4.5 Áp dụng bộ luật chuyển đổi khác cấp .................................................127 Chương 5......................................................................................................128 THỬ NGHIỆM – ĐÁNH GIÁ ....................................................................128 5.1 Thử nghiệm...................................................................................128 5.1.1 Độ đo sử dụng .....................................................................................128 5.1.2 Kết quả học rút luật chuyển đổi ..........................................................129 5.1.3 Một số kết quả chuyển đổi ..................................................................131 5.2 Đánh giá ........................................................................................134 5.2.1 Ngữ liệu thử nghiệm ...........................................................................134 5.2.2 Nhận xét ..............................................................................................135 Chương 6......................................................................................................137 TỔNG KẾT ..................................................................................................137 6.1 Kết quả..........................................................................................137 6.2 Hướng phát triển..........................................................................137 6.3 Kết luận.........................................................................................138 PHỤ LỤC 1..................................................................................................139 KHUNG LUẬT VÀ MỘT SỐ LUẬT CÙNG CẤP......................................139 PHỤ LỤC 2..................................................................................................141 KHUNG LUẬT VÀ MỘT SỐ LUẬT KHÁC CẤP......................................141 PHỤ LỤC 3..................................................................................................142 MỘT SỐ KẾT QUẢ DỊCH SỬ DỤNG KHỐI CHUYỂN ĐỔI CÂY CÚ PHÁP VCLTRANSFER ..............................................................................142 PHỤ LỤC 4..................................................................................................147 MỘT SỐ CÂU DỊCH CỦA HAI HỆ DỊCH ...............................................147 PHỤ LỤC 5..................................................................................................153 HỆ THỐNG NHÃN NGỮ PHÁP ...............................................................153 Luận văn tốt nghiệp Trang 10 PHỤ LỤC 6..................................................................................................156 CÁC NHÃN QUAN HỆ NGỮ PHÁP .........................................................156 TÀI LIỆU THAM KHẢO ............................................................................157 Luận văn tốt nghiệp Trang 11 Danh sách các hình Hình 1: Mô hình dịch trực tiếp .................................................................................. 16 Hình 2: Mô hình dịch dựa trên ngôn ngữ trung gian................................................. 17 Hình 3: Mô hình dịch dựa trên sự chuyển đổi........................................................... 18 Hình 4: Hình tháp minh họa các chiến lược dịch máy.............................................. 20 Hình 5: Cây cú pháp của câu “I have already read that interesting book.” .............. 21 Hình 6: So sánh trật tự định ngữ tiếng Anh và tiếng Việt ........................................ 26 Hình 7: Áp dụng luật cố định để thực hiện việc chuyển đổi cấu trúc ....................... 36 Hình 8: Trường hợp chuyển đổi khác cấp luật cố định không thể thực hiện được... 37 Hình 9: Khả năng chuyển đổi cú pháp của luật cố định............................................ 38 Hình 10: Giản đồ cây khởi tạo và cây phụ trợ của TAG........................................... 46 Hình 11: Tác tố kết hợp ............................................................................................. 47 Hình 12: Tác tố thay thế............................................................................................. 48 Hình 13: Một số mẫu cây sơ cấp trong tự điển chuyển đổi cây Anh-Pháp .............. 50 Hình 14: Cây phân tích ngữ pháp chuyển dịch đảo.. ................................................ 55 Hình 15: Chuyển đổi khung giữa các ngôn ngữ........................................................ 63 Hình 16: Sơ đồ phương pháp học TBL tổng quát ..................................................... 70 Hình 17: Một ví dụ minh hoạ chuyển đổi cây cú pháp ............................................ 79 Hình 18: Mô hình áp dụng chuyển đổi cây cú pháp.................................................. 81 Hình 19: Mô hình học luật chuyển đổi cây cú pháp theo thuật toán FnTBL............ 82 Hình 20: Ví dụ về các quan hệ ngữ pháp trong ngữ.................................................. 85 Luận văn tốt nghiệp Trang 12 Hình 21: Xây dựng ngữ tiếng Việt từ các quan hệ ngữ pháp.................................... 86 Hình 22: Lưu đồ thuật toán gán nhãn chuyển đổi cơ sở cho ngữ liệu ...................... 87 Hình 23: Lưu đồ thuật toán học luật chuyển đổi cùng cấp – FnTBL ................. 90 Hình 24: Lưu đồ học luật chuyển đổi khác cấp (FnTBL) ......................................... 94 Hình 25: Mô hình tổng thể của quá trình học luật chuyển đổi Anh-Việt ................. 97 Hình 26: Kết quả phân tích cú pháp: “Last week, I saw a very interesting film.”.. 100 Hình 27: Cây quan hệ của câu “Last week, I saw a very interesting film.”............ 104 Hình 28: Cây tiếng Anh đã chuyển đổi các thành phần đúng với tiếng Việt.......... 107 Hình 29: Cây cú pháp của câu “What is a computer ?” .......................................... 111 Hình 30: Cây cú pháp của (E) sau khi được áp dụng luật R................................... 113 Hình 31: Sơ đồ lớp khối học luật chuyển đổi cùng cấp .......................................... 114 Hình 32: Mô hình áp dụng tập luật chuyển đổi cùng cấp ....................................... 116 Hình 33: Cây cú pháp của câu tiếng Anh “It is a good type of book.”................... 118 Hình 34: Một cây cú pháp tiếng Anh sau khi chuyển sang cấu trúc tiếng Việt...... 119 Hình 35: Một phần cây cú pháp với đường đi của thành phần [ADVP] ................. 123 Hình 36: Sơ đồ lớp khối học luật chuyển đổi khác cấp........................................... 125 Hình 37: Mô hình áp dụng tập luật chuyển đổi khác cấp........................................ 127 Hình 38: Đánh giá tập luật học chuyển đổi cùng cấp.............................................. 130 Hình 39: Đánh giá tập luật học chuyển đổi khác cấp ............................................. 131 Luận văn tốt nghiệp Trang 13 Danh sách các bảng Bảng 1: Trật tự các thành phần trong ngữ danh từ tiếng Anh................................... 27 Bảng 2: Trật tự các thành phần trong ngữ danh từ tiếng Việt................................... 28 Bảng 3: Danh sách 23 cấu trúc vị từ - đối số trong tiếng Hoa .................................. 61 Bảng 4: Một số quan hệ ngữ pháp được ánh xạ cùng các ngoại lệ .......................... 84 Bảng 5: Các quan hệ trong câu tiếng Anh............................................................... 103 Bảng 6: Ý nghĩa các ký hiệu dùng trong mô tả ngữ liệu học giai đoạn 1............... 108 Bảng 7: Các thành phần trong khung luật học bước 1 ............................................ 109 Bảng 8: Các khung luật dùng trong học luật chuyển đổi cùng cấp......................... 109 Bảng 9: Ý nghĩa các khuôn mẫu trong khung luật .................................................. 110 Bảng 10: Các đặc trưng ngôn ngữ của các mẫu rút ra từ cây cú pháp tiếng Anh... 112 Bảng 11: Các thành phần trong khung luật học chuyển đổi khác cấp .................... 120 Bảng 12: Các khung luật dùng trong học luật chuyển đổi khác cấp....................... 121 Bảng 13: Ý nghĩa các thành phần trong khung luật bước 2 .................................... 122 Bảng 14: Một phần cây cú pháp minh hoạ việc đánh ID tương đối cho route....... 123 Bảng 15: Tóm tắt kết quả học luật chuyển đổi cùng cấp ........................................ 130 Bảng 16: Tóm tắt kết quả học luật chuyển đổi cùng cấp ........................................ 131 Bảng 17: Kết quả thử nghiệm việc áp dụng chuyển đổi cây cú pháp ..................... 135 Chương 1 - Tổng quan về chuyển đổi cây cú pháp Trang 14 Chương 1 TỔNG QUAN VỀ CHUYỂN ĐỔI CÂY CÚ PHÁP Chương này giới thiệu về đề tài luận văn - mục đích và phạm vi thực hiện. Phần 2 của chương trình bày một cách tổng quát về chuyển đổi cây cú pháp: vai trò, vị trí của khối chuyển đổi cây cú pháp trong hệ dịch Anh-Việt. Ngoài ra, những khái niệm then chốt liên quan đến đề tài, cũng như các cơ sở về lý thuyết ngôn ngữ học và tin học, là nền tảng để chúng em thực hiện luận văn, cũng lần lượt được nêu rõ trong phần 3 của chương. 1.1 Đặt vấn đề Chế tạo ra một loại máy có khả năng dịch tự động để giúp cho con người vượt qua rào cản ngôn ngữ là một mơ ước của loài người đã có từ thế kỷ XVII, rất lâu trước khi máy tính điện tử ra đời. Và chẳng bao lâu sau khi máy tính điện tử đầu tiên ra đời, bên cạnh những ứng dụng tính toán trong lĩnh vực toán học và vật lý, người ta đã nghĩ ngay đến việc sử dụng “bộ não máy tính” cho những ứng dụng không liên quan đến số, trong đó có vấn đề dịch tự động. Lần đầu tiên, việc sử dụng máy tính điện tử để dịch văn bản từ ngôn ngữ này sang ngôn ngữ khác được đề cập đến trong những cuộc thảo luận giữa Andrew D. Booth và Warren Weaver vào năm 1946. Vượt qua nhiều trở ngại về lý thuyết và công nghệ, Booth và các cộng sự của ông đã cho ra mắt “hệ dịch dựa trên tự điển” đầu tiên tại hội nghị của MIT vào năm 1952. Từ bước khởi đầu đó, dịch máy đã ngày càng thu hút được sự quan tâm nghiên cứu của nhiều nhà khoa học máy tính, nhiều nhà ngôn ngữ học,... và được cộng đồng thế giới thừa nhận hiệu quả to lớn của nó. Dịch máy không những giúp cho Chương 1 - Tổng quan về chuyển đổi cây cú pháp Trang 15 việc dịch các tài liệu, dịch các trang Web nhanh chóng và ít tốn công sức hơn, việc giao lưu trao đổi văn hoá giữa các nước dễ dàng hơn, mà còn có ý nghĩa trong việc bảo mật cho tài liệu quan trọng cần dịch thuật. Tuy vậy, để có được một hệ dịch tự động cho kết quả dịch tốt là cả một quá trình nghiên cứu và xây dựng cực kỳ phức tạp, phụ thuộc rất nhiều vào