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