Xemtailieu Tải về Nghiên cứu phát triển một số kỹ thuật tách từ tiếng việt
BỘ GIÁO DỤC VÀ ĐÀO TẠO BỘ QUỐC PHÒNG HỌC VIỆN KỸ THUẬT QUÂN SỰ TRẦN NGỌC ANH NGHIÊN CỨU PHÁT TRIỂN MỘT SỐ KỸ THUẬT TÁCH TỪ TIẾNG VIỆT LUẬN ÁN TIẾN SĨ TOÁN HỌC HÀ NỘI – NĂM 2016 BỘ GIÁO DỤC VÀ ĐÀO TẠO BỘ QUỐC PHÒNG HỌC VIỆN KỸ THUẬT QUÂN SỰ TRẦN NGỌC ANH NGHIÊN CỨU PHÁT TRIỂN MỘT SỐ KỸ THUẬT TÁCH TỪ TIẾNG VIỆT Chuyên ngành : Cơ sở toán học cho tin học Mã số : 62.46.01.10 LUẬN ÁN TIẾN SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: 1. PGS. TS. Đào Thanh Tĩnh 2. PGS. TS. Nguyễn Phương Thái HÀ NỘI – NĂM 2016 - ii - LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi. Các kết quả viết chung với các tác giả khác đều được sự đồng ý của đồng tác giả trước khi đưa vào luận án. Các số liệu, kết quả nghiên cứu trong luận án là trung thực và chưa từng được công bố trong bất kì công trình nào khác. Tác giả luận án Trần Ngọc Anh - iii - LỜI CẢM ƠN Trước hết, tác giả xin chân thành cảm ơn hai thầy hướng dẫn, PGS. TS. Đào Thanh Tĩnh và PGS. TS. Nguyễn Phương Thái, đã định hướng, tận tình hướng dẫn, giúp đỡ tác giả trong suốt thời gian nghiên cứu, đã đóng góp nhiều ý kiến khoa học cho luận án này. Tác giả xin bày tỏ lời cảm ơn chân thành đến tập thể Bộ môn Hệ thống thông tin, Khoa Công nghệ Thông tin và Phòng Sau đại học, Học viện Kỹ thuật Quân sự; tác giả xin chân thành cảm ơn đến tập thể cán bộ Trung tâm 2, Cục Công nghệ Thông tin, Bộ Tổng Tham mưu; xin cảm ơn tập thể Khoa Công nghệ Thông tin, Trường Đại học Công nghệ, Đại học Quốc gia Hà Nội đã tạo điều kiện thuận lợi cho tác giả hoàn thành luận án của mình. Tác giả cũng xin cảm ơn sự hỗ trợ của Đề tài Đại học Quốc gia Hà Nội (mã số QG.12.49) và Đề tài Quốc gia (mã số KC.01.20/11-15) trong quá trình nghiên cứu, thực hiện luận án. Tác giả xin bày tỏ lời cảm ơn đến GS. TSKH. Phạm Thế Long, PGS. TS. Lương Chi Mai, PGS. TS. Lê Thanh Hương, PGS. TS. Lê Anh Cường, PGS. TS. Bùi Thu Lâm, PGS.TS. Nguyễn Xuân Hoài, PGS.TS. Ngô Thành Long, TS. Nguyễn Thị Minh Huyền, TS. Hoa Tất Thắng, TS. Nguyễn Văn Vinh và TS. Lê Hải Sơn đã có nhiều ý kiến đóng góp quý báu giúp tác giả hoàn thiện bản thảo luận án của mình. Tác giả xin bày tỏ lời cảm ơn đến các chuyên gia: TS. Lê Hồng Phương (với VnTokenizer), TS. Nguyễn Cẩm Tú (với JvnSegmenter), KS. Lưu Tuấn Anh (với DongDu), TS. Nguyễn Chí Thành và TS. Trần Văn An đã hỗ trợ tác giả thực hiện quá trình huấn luyện lại và chạy thử nghiệm tách từ trên các hệ thống. Tác giả cũng xin bày tỏ lời cảm ơn đến các chuyên gia ngôn ngữ học: TS. Nguyễn Thị Trung Thành và TS. Trương Thị Thu Hà đã nhiệt tình giúp đỡ tác giả một số vấn đề liên quan đến ngôn ngữ học trong quá trình nghiên cứu. Tác giả gửi lời cảm ơn những người anh em, những người đồng đội luôn giúp đỡ, ủng hộ và động viên tác giả kể từ khi bắt đầu nghiên cứu đến nay. Cuối cùng, tác giả bày tỏ lòng biết ơn sâu sắc đối với cha mẹ và những người thân trong gia đình, đặc biệt là hai mẹ con Giang Nguyên và Khánh Linh đã luôn chia sẻ và ủng hộ tác giả trong suốt thời gian thực hiện luận án này. - iv - MỤC LỤC Trang DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT ........................................ vii DANH MỤC CÁC BẢNG ........................................................................................ ix DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ.................................................................. xi DANH MỤC CÁC THUẬT TOÁN........................................................................ xii MỞ ĐẦU ......................................................................................................................1 Chương 1 TỔNG QUAN VỀ BÀI TOÁN TÁCH TỪ TIẾNG VIỆT ....................4 1.1. BÀI TOÁN TÁCH TỪ TIẾNG VIỆT ...............................................................4 1.1.1. Phát biểu bài toán tách từ tiếng Việt ...........................................................4 1.1.2. Đặc trưng của đơn vị từ vựng tiếng Việt.....................................................5 1.1.3. Những vấn đề khó trong tách từ tiếng Việt .................................................8 1.1.4. Phương pháp đánh giá kết quả tách từ tiếng Việt .....................................10 1.2. NHỮNG TIẾP CẬN TRÊN THẾ GIỚI VÀ TRONG NƯỚC ........................10 1.2.1. Những tiếp cận trên thế giới ......................................................................11 1.2.2. Những tiếp cận trong nước........................................................................14 1.2.3. Những kết quả đạt được trong tách từ tiếng Việt ......................................16 1.2.4. Những tồn tại trong nghiên cứu tách từ tiếng Việt....................................17 1.3. ĐỀ XUẤT HƯỚNG GIẢI QUYẾT.................................................................20 1.3.1. Xác định tài nguyên cho bài toán tách từ tiếng Việt .................................20 1.3.2. Thống kê chất lượng các kho ngữ liệu mẫu tiếng Việt .............................21 1.3.3. Chọn mô hình tích hợp cho tách từ tiếng Việt ..........................................24 Chương 2 TÁCH TỪ VÀ NHẬN DIỆN THỰC THỂ VĂN BẢN TIẾNG VIỆT .. 26 2.1. THUẬT TOÁN TÁCH TỪ TIẾNG VIỆT.......................................................26 2.1.1. Thuật toán tách từ tiếng Việt VWS ...........................................................26 2.1.2. Các thuật toán dùng chung trong tách từ...................................................26 2.1.3. Thử nghiệm thuật toán so khớp cực đại cải tiến AMM ............................32 2.2. NHẬN DIỆN THỰC THỂ VÀ KHỬ NHẬP NHẰNG TÊN RIÊNG.............33 2.2.1. Bài toán nhận diện thực thể trong văn bản................................................33 2.2.2. Nhận diện các thực thể trong văn bản tiếng Việt ......................................34 2.2.3. Nhận diện và khử nhập nhằng ranh giới tên riêng tiếng Việt ...................38 2.2.4. Kết quả thử nghiệm ...................................................................................44 Chương 3 NHẬN DIỆN TỪ LÁY VÀ TỪ GHÉP ĐẲNG LẬP TIẾNG VIỆT ..... 46 3.1. NHẬN DIỆN TỪ GHÉP BẰNG HỌC KHÔNG GIÁM SÁT ........................46 -v- 3.1.1. Chọn độ dài từ ghép tiếng Việt cho học không giám sát ..........................46 3.1.2. Một số độ đo thống kê nhận diện từ ghép có 2 âm tiết tiếng Việt ............46 3.1.3. Giải pháp nhận diện từ ghép có 2 âm tiết tiếng Việt dựa vào đỉnh nhọn ..50 3.1.4. Kết quả thử nghiệm ...................................................................................51 3.2. NHẬN DIỆN TỪ LÁY TIẾNG VIỆT.............................................................54 3.2.1. Các đặc điểm cấu tạo từ láy tiếng Việt......................................................55 3.2.2. Nhận diện và xây dựng từ điển từ láy đôi tiếng Việt ................................56 3.2.3. Nhận diện từ láy ba, từ láy tư tiếng Việt ...................................................58 3.2.4. Kết quả thử nghiệm ...................................................................................60 3.3. NHẬN DIỆN TỪ GHÉP ĐẲNG LẬP TIẾNG VIỆT .....................................61 3.3.1. Các đặc trưng về cấu tạo từ ghép đẳng lập tiếng Việt...............................61 3.3.2. Nhận diện và xây dựng từ điển từ ghép song tiết đẳng lập tiếng Việt ......63 3.3.3. Nhận diện tổ hợp từ, thành ngữ có 3 hay 4 âm tiết ...................................69 3.3.4. Kết quả thử nghiệm ...................................................................................71 Chương 4 KHỬ NHẬP NHẰNG RANH GIỚI TỪ TIẾNG VIỆT ......................73 4.1. NHẬP NHẰNG RANH GIỚI TỪ TIẾNG VIỆT ............................................73 4.1.1. Khái niệm và phân loại nhập nhằng ranh giới từ tiếng Việt .....................73 4.1.2. Thống kê và giải pháp khử nhập nhằng ranh giới từ.................................74 4.1.3. Tạo ngữ liệu nhập nhằng cho huấn luyện và thử nghiệm .........................76 4.2. KHỬ NHẬP NHẰNG RANH GIỚI TỪ BẰNG TỪ ĐIỂN............................77 4.2.1. Phương pháp khử nhập nhằng CA bằng từ điển (VWS5.1)......................77 4.2.2. Kết quả thử nghiệm ...................................................................................79 4.3. KHỬ NHẬP NHẰNG BẰNG ĐỘ PHỨC TẠP VĂN BẢN...........................80 4.3.1. Độ phức tạp văn bản theo xác suất bigram mức từ ...................................80 4.3.2. Độ phức tạp văn bản của mô hình Markov ẩn gán nhãn từ loại................81 4.3.3. Độ phức tạp văn bản của bigram mức từ và gán nhãn từ loại...................82 4.3.4. Kết quả thử nghiệm ...................................................................................84 4.4. KHỬ NHẬP NHẰNG BẰNG MÔ HÌNH ĐIỂM SỐ .....................................87 4.4.1. Mô hình điểm số khử nhập nhằng chồng lấp OA theo ngữ cảnh..............88 4.4.2. Mô hình điểm số khử nhập nhằng ghép tách CA theo ngữ cảnh ..............90 4.4.3. Kết quả thử nghiệm ...................................................................................92 Chương 5 THỬ NGHIỆM VÀ ĐÁNH GIÁ ...........................................................95 5.1. THỬ NGHIỆM TÁCH TỪ TIẾNG VIỆT.......................................................95 5.1.1. Mô tả các bước trong thuật toán tách từ tiếng Việt ...................................96 5.1.2. Các nhóm giải pháp dùng cho thử nghiệm tách từ tiếng Việt...................97 5.1.3. Thử nghiệm tách từ và đánh giá ................................................................97 - vi - 5.2. SO SÁNH VỚI MỘT SỐ CÔNG CỤ TÁCH TỪ TIẾNG VIỆT ..................102 5.2.1. Giới thiệu về một số công cụ tách từ hiện nay ........................................102 5.2.2. Kết quả thử nghiệm tách từ, đánh giá và so sánh....................................104 5.3. KIỂM LỖI CHÍNH TẢ VĂN BẢN TIẾNG VIỆT........................................107 5.3.1. Giới thiệu bài toán kiểm lỗi chính tả tiếng Việt ......................................107 5.3.2. Kiểm lỗi cách dùng từ và cụm từ bằng mô hình ngram mức âm tiết ......109 5.3.3. Kiểm lỗi chính tả bằng mô hình tách từ và gán nhãn từ loại ..................113 KẾT LUẬN..............................................................................................................117 DANH MỤC CÔNG TRÌNH CỦA TÁC GIẢ .....................................................119 TÀI LIỆU THAM KHẢO ......................................................................................120 PHỤ LỤC.................................................................................................................129 A. CÁC THUẬT TOÁN HỖ TRỢ .......................................................................129 A1. Thuật toán tìm số từ chung dài nhất của hai dãy từ....................................129 A2. Thuật toán chuyển mã unicode...................................................................129 A3. Thuật toán sửa lỗi chính tả dấu thanh tiếng Việt tự động ..........................131 A4. Thuật toán xây dựng từ điển automat tối thiểu...........................................132 B. MINH HOẠ KẾT QUẢ THỐNG KÊ TỪ CÁC TÀI NGUYÊN.....................139 B1. Minh hoạ một số lỗi trong kho ngữ liệu VietTreeBank..............................139 B2. Thống kê sửa lỗi chính tả các kho ngữ liệu mẫu tiếng Việt .......................141 B3. Thống kê các kí tự đặc biệt trong các kho ngữ liệu....................................141 B4. Thống kê phân loại thực thể và độ dài thực thể trong các kho ngữ liệu.....142 B5. Danh sách các từ tố tên riêng, tên riêng đặc biệt và tên họ người Việt ......143 C. PHÉP ĐO ĐỘ TƯƠNG TỰ NGỮ NGHĨA DÙNG TỪ ĐIỂN VCL ..............147 C1. Độ tương tự dựa vào so khớp chuỗi xấp xỉ theo khoảng cách ...................148 C2. Độ tương tự dựa vào phép đo đồng xuất hiện ............................................148 C3. Độ tương tự theo vector (Vector Space Model) .........................................149 D. MỘT SỐ THUẬT TOÁN SO KHỚP CỰC ĐẠI.............................................150 D1. So khớp cực đại MM (Maximum Matching) .............................................150 D2. So khớp cực đại có cửa sổ ..........................................................................152 E. THUẬT TOÁN NHẬN DIỆN VÀ KHỬ NHẬP NHẰNG TÊN RIÊNG .......153 E1. Thuật toán nhận diện tên riêng, nhận diện số và phân số bằng chữ ...........153 E2. Các thuật toán khử nhập nhằng tên riêng....................................................155 F. THUẬT TOÁN TÌM THAM SỐ HỌC TỐI ƯU..............................................158 F1. Thuật toán di truyền GA và cực đại hoá kỳ vọng EM ................................158 F2. Thuật toán EM trên các đoạn con ...............................................................161 - vii - DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT Kí hiệu ACO AM/AMM BM/BMM CA CC/TGĐL CRF DFA EM ER FM/FMM FSM GA HMM LCS MEM MI MinDFA MM NE NER NLP NW OA Pb Pk PN POS PP PSO Pu RW SC/TGCP Mô tả Tối ưu đàn kiến (Ant Colony Optimization) So khớp cực đại cải tiến (Advanced Maximum Matching) So khớp cực đại lùi (Backward Maximum Matching) Nhập nhằng ghép-tách (Combinated Ambiguity) Từ ghép đẳng lập (Coordinated Compound) Trường ngẫu nhiên có điều kiện (Conditional Random Field) Automat [hữu hạn tiền định] (Determine Finite Automata) Thuật toán cực đại hoá kỳ vọng (Expectation Maximization) Nhận diện thực thể văn bản (Entity Recognition) So khớp cực đại tiến (Forward Maximum Matching) Máy trạng thái hữu hạn (Finite State Machine) Giải thuật di truyền (Genetic Algorithms) Mô hình Markov ẩn (Hidden Markov Model) Dãy con chung dài nhất (Longest Common Substring) Mô hình Entropy cực đại (Maximum Entropy Model) Độ thông tin tương hỗ (Mutual Information) Automat tối thiểu (Minimal Determine Finite Automata) So khớp cực đại (Maximum Matching) Thực thể có tên (Named Entity) Nhận diện thực thể có tên (Named Entity Recognition) Xử lý ngôn ngữ tự nhiên (Natural Language Processing) Từ mới (New Word) Nhập nhằng chồng lấp (Overlaping Ambiguity) Xác suất bigram (bigram Probability) Xác suất bigram có điều kiện (conditional bigram Probability) Tên riêng (Private/Proper Name)/Nhận diện tên riêng Từ loại (Part-Of-Speech) Độ phức tạp văn bản (Perplexity) Tối ưu bầy đàn (Particle Swarm Optimization) Xác suất unigram (unigram Probability) Từ láy (Reduplicative Word) Từ ghép chính phụ (Subordinated Compound) - viii - Sim SP731 SP732 SP733 SP73POS VCL VFD VLP VSD VWS Độ tương tự (Similarity) Kho ngữ liệu đã tách từ, gồm 1.542.673 từ, 68.000 câu (10 MB) Kho ngữ liệu đã tách từ, gán nhãn từ loại, 221.221 từ, 10.000 câu Kho ngữ liệu đã tách từ, gán nhãn từ loại và cú pháp, 10.000 câu Kho ngữ liệu đã tách từ, gán nhãn từ loại, 20.000 câu. Từ điển từ vựng tiếng Việt (Vietrnamese Computation Lexicon) Từ điển tên họ người Việt (Vietnamese Family Dictionary) Xử lý ngôn ngữ tiếng Việt (Vietnamese Language Processing) Từ điển âm tiết tiếng Việt (Vietnamese Syllable Dictionary) Tách từ tiếng Việt (Vietnamese Word Segmenation) Các kí hiệu cho phép đo đánh giá độ chính xác tách từ dùng trong luận án: Kí hiệu Nm Nt Nđ R P F1 Mô tả Số lượng đơn vị từ trong kho mẫu. Số lượng đơn vị từ tách được. Số lượng đơn vị từ tách đúng. (dùng LCS để xác định, Phụ lục A1) Độ đo hồi tưởng (Recall) : R = Nđ/Nm Độ đo chính xác (Precision) : P = Nđ/Nt Độ đo F1-score : F1 = 2RP/(R+P) - ix - DANH MỤC CÁC BẢNG Bảng 1.1. Thống kê độ dài từ trong các kho ngữ liệu mẫu (đã sửa lỗi)......................... 17 Bảng 1.2. Tách từ theo dấu cách và dấu câu các kho ngữ liệu mẫu (đã sửa lỗi)........... 18 Bảng 1.3. Kết quả thử nghiệm của [29], PN là nhận diện tên riêng .............................. 19 Bảng 1.4. Thống kê phân loại đơn vị từ trong các kho ngữ liệu mẫu............................ 22 Bảng 1.5. Thống kê tỉ lệ từ theo độ dài tối đa trong các kho ngữ liệu mẫu................... 23 Bảng 1.6. Thống kê độ phủ từ - từ điển của các kho ngữ liệu tiếng Việt ...................... 23 Bảng 2.1. Thử nghiệm tách từ với các mô hình FMM, BMM và AMM ...................... 32 Bảng 2.2. Mô tả các trường hợp nhập nhằng tên riêng với tên riêng............................. 41 Bảng 2.3. Kết quả nhận diện & khử nhập nhằng tên riêng của kho SP731................... 44 Bảng 2.4. Kết quả tách từ có nhận diện thực thể với FMM, BMM và AMM .............. 44 Bảng 3.1. Nhận diện từ ghép có 2 âm tiết dựa theo chọn đỉnh nhọn............................. 52 Bảng 3.2. Nhận diện từ ghép có 2 âm tiết theo đỉnh nhọn vượt ngưỡng....................... 52 Bảng 3.3. Nhận diện từ ghép có 2 âm tiết theo đỉnh nhọn và unigram dưới ngưỡng ... 53 Bảng 3.4. Nhận diện từ ghép có 2 âm tiết với đỉnh nhọn vượt max unigram ............... 53 Bảng 3.5. Nhận diện từ ghép với đỉnh nhọn vượt max unigram có tham số .............. 53 Bảng 3.6. Minh hoạ nhận diện từ láy ba và từ láy tư ..................................................... 60 Bảng 3.7. Thử nghiệm tách từ với các mô-đun ER, AM, RW ...................................... 61 Bảng 3.8. Mô tả thông tin từ điển VCL của hai từ "cha" và "mẹ"................................. 65 Bảng 3.9. Một số thông tin từ điển VCL của hai từ "dút dát" và "an tâm" ................... 65 Bảng 3.10. Minh hoạ một phần các cặp từ đồng nghĩa (4.958 cặp) .............................. 68 Bảng 3.11. Minh hoạ một phần các cặp từ đối nghĩa (762 cặp) .................................... 69 Bảng 3.12. Minh hoạ độ đo tương tự các cặp từ (SimDice > 0,5: 14.452 cặp)................ 69 Bảng 3.13. Minh hoạ dùng MI (từ internet) để xác định TGĐL (4.718 cặp)................ 69 Bảng 3.14. Kết quả phát hiện danh sách các từ ghép song tiết đẳng lập ....................... 69 Bảng 3.15. Minh hoạ nhận diện tổ hợp từ có 3-4 âm tiết (TGĐL) ................................ 70 Bảng 3.16. Tách từ với các mô-đun ER, AM và CC ..................................................... 71 Bảng 4.1. Thống kê nhập nhằng OA và CA trong các kho ngữ liệu ............................. 74 Bảng 4.2. Tỉ lệ gây lỗi của các nhập nhằng trong các kho ngữ liệu .............................. 74 Bảng 4.3. Minh hoạ nhập nhằng chồng lấp OA trong các kho ngữ liệu ....................... 75 Bảng 4.4. Minh hoạ nhập nhằng ghép-tách CA trong các kho ngữ liệu........................ 75 Bảng 4.5. Phân chia ngữ liệu VietTreeBank cho huấn luyện và thử nghiệm................ 77 Bảng 4.6. Minh hoạ nhập nhằng CA với quán từ ở đầu/cuối cụm từ............................ 78 Bảng 4.7. Tỉ lệ khử nhập nhằng với từ điển quán từ BE................................................ 79 Bảng 4.8. Kết quả tách từ bằng FM, BM, AM với các mô-đun ER và BE................... 79 -x- Bảng 4.9. Kí hiệu 22 từ loại của kho ngữ liệu SP73POS 20.000 câu............................ 84 Bảng 4.10. Kết quả khử nhập nhằng với các mô hình M2x........................................... 86 Bảng 4.11. Kết quả tách từ bằng ER, AM và khử nhập nhằng với PB, PO .................. 86 Bảng 4.12. Minh hoạ khử nhập nhằng OA/CA bằng mô hình M22 và M23................ 87 Bảng 4.13. Kết quả tỉ lệ khử nhập nhằng với các mô hình điểm số M3x...................... 92 Bảng 4.14. Kết quả tách từ và khử nhập nhằng bằng các mô hình điểm số M3x ......... 93 Bảng 4.15. Minh hoạ khử các nhập nhằng OA bằng M21 và M3x............................... 94 Bảng 5.1. Mô tả các mô-đun (đặc trưng) tích hợp cho mô hình tách từ........................ 95 Bảng 5.2. Kết quả tách từ với giải pháp cải tiến so khớp cực đại cho TEST.OCA ...... 98 Bảng 5.3. Kết quả tách từ với giải pháp cải tiến so khớp cực đại cho TEST.ALL ....... 99 Bảng 5.4. Kết quả tách từ với mô hình độ phức tạp văn bản cho TEST.OCA ........... 100 Bảng 5.5. Kết quả tách từ với mô hình độ phức tạp văn bản cho TEST.ALL ............ 100 Bảng 5.6. Kết quả tách từ với mô hình điểm số cho TEST.OCA................................ 101 Bảng 5.7. Kết quả tách từ với mô hình điểm số cho TEST.ALL ................................ 101 Bảng 5.8. Kết quả so sánh thử nghiệm tách từ giữa các công cụ với TEST.OCA ........... 105 Bảng 5.9. Kết quả so sánh thử nghiệm tách từ giữa các công cụ với TEST.ALL ............ 105 Bảng 5.10. Kết quả so sánh nhận diện từ mới có 2 âm tiết trở lên với TEST.ALL.......... 105 Bảng 5.11. Kết quả so sánh nhận diện tên riêng giữa các công cụ với TEST.ALL.......... 106 Bảng 5.12. Kết quả so sánh khử nhập nhằng OA-CA giữa các công cụ với TEST.OCA 106 Bảng 5.13. So sánh thời gian chạy trung bình (giây) giữa các công cụ với TEST.ALL .. 106 Bảng 5.14. Kiểm lỗi cụm từ theo mô hình độ phức tạp văn bản ................................. 112 Bảng 5.15. Kiểm lỗi trigram theo xác suất ................................................................... 112 Bảng 5.16. Kết quả đo LPP cho mô hình PB+PO với văn bản kiểm lỗi ..................... 114 Bảng 5.17. Kết quả sắp xếp độ đo LPP giảm dần theo từng cụm từ/câu..................... 115 - xi - DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ Hình 0.1. Tiếp cận phân tích và hiểu văn bản theo các mức............................................ 1 Hình 1.1. Văn bản tin tức tiếng Việt được tách từ (thực thể in đậm) .............................. 5 Hình 1.2. Phân loại từ tiếng Việt theo cấu tạo.................................................................. 5 Hình 1.3. Một số câu tiếng Việt được tách từ bị lỗi ....................................................... 17 Hình 1.4. Mô hình ghép nối có thứ tự cho tách từ tiếng Việt ........................................ 24 Hình 2.1. Cây quyết định nhị phân để tách các kí tự đặc biệt........................................ 27 Hình 2.2. Minh hoạ sơ đồ mạng từ được sinh theo từ điển cho câu 1 ........................... 29 Hình 2.3. Minh hoạ sơ đồ mạng từ được sinh theo từ điển cho câu 2 ........................... 29 Hình 2.4. Minh hoạ nhận diện ranh giới tên riêng cho tách từ tiếng Việt ..................... 33 Hình 2.5. Minh hoạ nhận diện thực thể có tên sau khi tách từ tiếng Việt...................... 34 Hình 2.6. Mô tả khử nhập nhằng tên riêng với từ hậu tố ............................................... 40 Hình 3.1. Đồ thị xác suất unigram từng âm tiết trong câu ............................................. 47 Hình 3.2. Đồ thị xác suất bigram các cặp âm tiết trong câu........................................... 48 Hình 3.3. Xác suất bigram có điều kiện các cặp âm tiết trong câu ................................ 49 Hình 3.4. Lược đồ thông tin tương hỗ của âm tiết và cặp âm tiết.................................. 49 Hình 3.5. Độ tương hỗ thông tin của các cặp âm tiết trong câu..................................... 50 Hình 3.6. Phân loại từ láy tiếng Việt............................................................................... 55 Hình 3.7. Giao diện công cụ bổ sung và cập nhật từ điển VCL..................................... 64 Hình 4.1. Tỉ lệ ngữ liệu VietTreeBank cho huấn luyện và thử nghiệm......................... 77 Hình 4.2. Mô hình Markov ẩn HMM (có dãy quan sát X độc lập) ............................... 81 Hình 4.3. Mô hình Markov ẩn với dãy quan sát X phụ thuộc........................................ 83 Hình 5.1. Mô tả văn bản thử nghiệm kiểm lỗi chính tả................................................ 112 - xii - DANH MỤC CÁC THUẬT TOÁN Thuật toán VWS. Thuật toán tổng quát cho tách từ tiếng Việt...................................... 26 Thuật toán VWS1. Tách kí tự đặc biệt dựa vào cây quyết định nhị phân. .................... 27 Thuật toán VWS3. Sinh ứng viên từ có cửa sổ âm tiết dựa vào từ điển........................ 30 Thuật toán VWS6. Tìm dãy tách từ tối ưu. .................................................................... 30 Thuật toán VWS2.21. Nhận diện tên riêng và khử nhập nhằng từ tiền tố..................... 39 Thuật toán VWS2.22. Khử nhập nhằng tên riêng với từ hậu tố sau tách từ.................. 40 Thuật toán VWS2.23. Khử nhập nhằng giữa tên riêng với tên riêng. ........................... 42 Thuật toán 3.1. Tìm kiếm các từ láy đôi mới.................................................................. 57 Thuật toán 3.2. Tính độ tương tự giữa hai từ dựa vào từ điển VCL. ............................. 66 Thuật toán 3.3. Nhận diện từ ghép song tiết đẳng lập.................................................... 68 Thuật toán VWS5.1. Khử nhập nhằng bằng từ điển quán từ BE................................... 78 -1- MỞ ĐẦU 1. Tính cấp thiết của luận án Xử lý ngôn ngữ tự nhiên (hay ngôn ngữ học tính toán) là lĩnh vực được nhiều chuyên gia trên thế giới cũng như trong nước quan tâm nghiên cứu, nhằm tạo ra các sản phẩm phần mềm có tri thức và thông minh, hiểu được ngôn ngữ con người và trao đổi được giữa các ngôn ngữ khác nhau. Trong các bài toán xử lý ngôn ngữ tự nhiên thì bài toán tách từ là một trong những bài toán cơ bản vì nó là nền tảng cho các nghiên cứu để hiểu ngôn ngữ và ứng dụng vào thực tiễn như: kiểm lỗi chính tả, tóm tắt văn bản trả lời câu hỏi tự động, dịch máy,... Ta có thể thấy vai trò nền tảng của đơn vị từ trong các bước phân tích và hiểu ngôn ngữ văn bản như hình 0.1. Hình 0.1. Tiếp cận phân tích và hiểu văn bản theo các mức Đối với tiếng Việt, từ được cấu tạo bởi một hay nhiều âm tiết ghép lại, không có ký hiệu phân tách rõ ràng giữa các từ với nhau. Do vậy, tách từ tiếng Việt là một bài toán khó. Qua các khảo sát nghiên cứu, một số vấn đề quan trọng trong bài toán tách từ tiếng Việt còn bỏ ngỏ gồm có: nhận diện và khử nhập nhằng tên riêng, nhận diện từ mới, và xử lý nhập nhằng ranh giới từ. Đây cũng là những vấn đề khó mà hầu hết các nghiên cứu về tách từ trong một số ngôn ngữ ở châu Á như: tiếng Trung, tiếng Nhật, tiếng Thái, tiếng Lào, tiếng Khmer,… đang quan tâm giải quyết. Chính vì thế, trong mục tiêu và phạm vi nghiên cứu, tác giả chọn đề tài luận án là “Nghiên cứu phát triển một số kỹ thuật tách từ tiếng Việt”. -2- 2. Mục tiêu nghiên cứu của luận án Mục tiêu chính của luận án là giải quyết một số vấn đề khó trong bài tách từ tiếng Việt hiện nay là: nhận diện và khử nhập nhằng tên riêng, nhận diện từ mới và xử lý nhập nhằng ranh giới từ. Mục tiêu cụ thể là phân tích những điểm tồn tại trong nghiên cứu tách từ tiếng Việt, xác định cách thức tích hợp tri thức từ các từ điển, các kho ngữ liệu, các quy tắc cấu tạo từ, nâng cao hiệu quả nhận diện từ mới và khử các nhập nhằng ranh giới từ trong tách từ tiếng Việt. 3. Đối tượng và phạm vi nghiên cứu của luận án - Nhận diện các thực thể trong văn bản: được giới hạn trong phạm vi của bài toán tách từ, xem như các đơn vị từ: tên riêng (tên người, tên địa điểm, tên tổ chức), tên viết tắt, biểu thức ngày tháng, thời gian, biểu thức số, địa chỉ email, địa chỉ url,… Nghĩa là trong bài toán tách từ, chỉ nghiên cứu tách ranh giới thực thể (chủ yếu là tên riêng) chứ không thực hiện nghiên cứu phân lớp các thực thể. - Nhận diện từ ghép mới: nhận diện từ mới gồm 2 âm tiết trở lên, gồm hai loại tiêu biểu là từ láy và từ ghép đẳng lập. - Xử lý nhập nhằng ranh giới từ trong văn bản tiếng Việt gồm 2 loại: nhập nhằng chồng lấp và nhập nhằng ghép tách. Trong đó, các tiêu chí xác định đơn vị từ tiếng Việt dựa vào tài liệu hướng dẫn tách từ đã nghiệm thu của đề tài KC01.01/06-10, và một số tài liệu về từ vựng, ngữ pháp tiếng Việt giảng dạy chuyên ngành ngôn ngữ học. Các khảo sát thống kê, kết quả thử nghiệm được thực hiện trên kho ngữ liệu mẫu VietTreeBank và từ điển VCL. 4. Phương pháp nghiên cứu của luận án Luận án sử dụng tổng hợp các phương pháp nghiên cứu chuyên ngành và liên ngành trên cơ sở một số lĩnh vực: Ngôn ngữ học tiếng Việt và các dạng nhập nhằng; Lý thuyết về mô hình thống kê ngôn ngữ n-gram; Lý thuyết về Ô-tô-mát trạng thái hữu hạn; Lý thuyết về học máy thống kê; Lý thuyết về độ phức tạp thuật toán; Lý thuyết về tối ưu hoá; và Lý thuyết về trí tuệ nhân tạo trong xử lý ngôn ngữ tự nhiên. Tiếp cận nghiên cứu bằng hệ thống các phương pháp: - Phương pháp lô-gích - Phương pháp thống kê - khảo sát - đánh giá - Phương pháp phân tích - tổng hợp. - Phương pháp chuyên gia. - Phương pháp hệ thống -3- Trong đó, kết hợp chặt chẽ có hệ thống các phương pháp lôgíc, thống kê – khảo sát, phân tích – tổng hợp và phương pháp chuyên gia. 5. Một số kết quả đạt được trong luận án 1) Đề xuất kỹ thuật nhận diện và khử nhập nhằng tên riêng, làm tăng đáng kể độ chính xác tách từ: nhận diện và khử nhập nhằng từ tiền tố với tên riêng; khử nhập nhằng tên riêng với từ hậu tố; và khử nhập nhằng tên riêng với tên riêng. 2) Đề xuất kỹ thuật nhận diện từ láy và từ ghép đẳng lập cho tách từ tiếng Việt ([A7], [A9], [A10]) dựa trên độ thông tin tương hỗ cùng với các quy tắc ngôn ngữ học nhận diện chúng. Trên cơ sở đó, mở rộng nhận diện các tổ hợp từ có 3-4 âm tiết. 3) Đề xuất kỹ thuật khử các loại nhập nhằng chồng lấp và nhập nhằng ghép tách theo ngữ cảnh thống kê ([A2], [A8] và [A11]) trong điều kiện kho ngữ liệu huấn luyện có kích thước nhỏ, có nhiều xác suất 0. Thực hiện khảo sát các mẫu nhập nhằng khác nhau và đưa ra một số giải pháp và công thức linh hoạt biểu diễn theo ngữ cảnh để khử nhập nhằng hiệu quả. Các kết quả của luận án được thực hiện trên cơ sở khảo sát thống kê và thử nghiệm tách từ với các kho ngữ liệu mẫu của VietTreeBank. Các thuật toán đề xuất cho tách từ trong luận án có độ phức tạp tính toán là O(n), với n là số lượng âm tiết trong dãy vào, và kết quả thử nghiệm tách từ đạt độ chính xác F1-score là 98,78%. Ngoài ra, luận án cũng đã đề xuất thử nghiệm giải pháp kiểm lỗi chính tả tiếng Việt ([A4]), có thể ứng dụng trong thực tế. 6. Bố cục luận án Ngoài phần mở đầu và kết luận, luận án gồm 5 chương: Chương 1: Tổng quan về bài toán tách từ tiếng Việt. Chương 2: Tách từ và nhận diện thực thể văn bản tiếng Việt. Chương 3: Nhận diện từ láy và từ ghép đẳng lập tiếng Việt. Chương 4: Khử nhập nhằng ranh giới từ tiếng Việt. Chương 5: Thử nghiệm và đánh giá. -4- Chương 1 TỔNG QUAN VỀ BÀI TOÁN TÁCH TỪ TIẾNG VIỆT 1.1. BÀI TOÁN TÁCH TỪ TIẾNG VIỆT 1.1.1. Phát biểu bài toán tách từ tiếng Việt Khi thực hiện nhiệm vụ xử lý ngôn ngữ tự nhiên cho bất kì ngôn ngữ nào thì bước đầu tiên cần phải làm là tách từ (word segmentation). Vì thế, việc nhận biết ranh giới từ một cách nhanh chóng và chính xác là vấn đề có ý nghĩa quan trọng. Đối với một số ngôn ngữ như tiếng Nga, Anh, Pháp hay Đức, ranh giới từ được cho bởi khoảng trắng hay các dấu ngắt câu. Với tiếng Việt, về mặt hình thức, từ được cấu tạo bởi một hay nhiều âm tiết (tiếng) ghép lại, nên nếu chỉ dùng khoảng trắng sẽ không thể phân biệt ranh giới từ. Minh hoạ từ tiếng Việt: - Từ có một âm tiết: nhà, cửa, đi, chạy, xanh, đỏ,... - Từ có từ hai âm tiết trở lên: + Từ kép : nhà trường, tổ chức, lung linh, lấp lánh, đu đưa,... + Từ bộ ba: phương pháp luận, bất đắc dĩ, sạch sành sanh,... + Từ bộ tư: xã hội chủ nghĩa, nói đi nói lại, đu đa đu đưa,... Bài toán tách từ tiếng Việt có thể được phát biểu như sau: Cho cụm từ gồm n âm tiết (tiếng): S = s1 s2 s3 ... sn-1 sn Yêu cầu tách thành m từ (m ≤ n) : S = w1 w2 w3... wm-1 wm Về mặt ngôn ngữ học tính toán, "từ" ở dạng từ phức và "ngữ" ở dạng cụm từ được cấu tạo bởi nhiều âm tiết ghép lại, nên việc phân biệt khái niệm giữa "từ" và "ngữ" (hay "từ" và "cụm từ") vẫn còn chưa rõ ràng. Trong thực tế xử lý bằng máy tính có sử dụng từ điển từ vựng, có nhiều trường hợp rất khó phân biệt ranh giới từ. Chẳng hạn với dãy âm tiết "đón tiếp tân" trong ví dụ sau thì máy tính phải chọn phương án nào cho đúng. Ví dụ: Họ đang chuẩn bị đón tiếp tân giám đốc. Để biểu diễn từ, có thể dùng dấu nối “_” để ghép các âm tiết lại với nhau trong mỗi từ. Với ví dụ trên, ta sẽ có hai phương án tách từ như sau: (a) Họ đang chuẩn_bị đón tiếp_tân giám_đốc . (b) Họ đang chuẩn_bị đón_tiếp tân giám_đốc . -5- Ranh giới không rõ ràng như vậy được gọi là sự nhập nhằng trong ngôn ngữ. Nhập nhằng ranh giới từ là vấn đề thường xuất hiện trong tiếng Việt và một số ngôn ngữ khác như tiếng Trung, tiếng Thái, tiếng Lào, tiếng Khmer,... Trong tiếng Việt, do có nhiều quy tắc cấu tạo từ (từ láy, từ ghép đẳng lập, từ ghép chính phụ), nên trong thực tế sử dụng và phát triển ngôn ngữ, có rất nhiều từ mới được tạo ra mà từ điển không thể chứa đựng hết được (được gọi là từ - từ điển). Đây cũng là vấn đề hóc búa cho bài toán tự động hoá tách từ tiếng Việt. Ngoài vấn đề nhập nhằng ranh giới từ và xác định từ mới đã nêu, thì bài toán tách từ đòi hỏi phải nhận diện các "thực thể" văn bản (entity, theo [47] và [48]) như tên riêng (tên người, tên tổ chức, tên địa điểm), tên viết tắt, ngày tháng, thời gian, biểu thức số, phần trăm, đơn vị đo, thư điện tử,... Có thể thấy qua minh hoạ tách từ và thực thể trong hình 1.1. Hình 1.1. Văn bản tin tức tiếng Việt được tách từ (thực thể in đậm) 1.1.2. Đặc trưng của đơn vị từ vựng tiếng Việt Theo [8], đơn vị từ vựng tiếng Việt gồm hai lớp: từ và ngữ cố định. 1.1.2.1. Từ tiếng Việt * Phân loại từ tiếng Việt theo cấu tạo Hình 1.2. Phân loại từ tiếng Việt theo cấu tạo Theo [3], từ tiếng Việt bao gồm từ đơn và từ phức. Từ đơn chỉ có một âm tiết, còn từ phức có từ hai âm tiết trở lên. Trong đó, từ phức về mặt ngữ âm, ngữ pháp và -6- ngữ nghĩa chia thành ba loại: từ ghép, từ láy và từ ngẫu hợp. Từ ghép được phân chia thành hai dạng: từ ghép chính phụ, từ ghép đẳng lập. Trong đó, từ láy và từ ghép đẳng lập (khối đậm trong hình 1.2) có những đặc điểm về cấu tạo về ngữ âm, ngữ pháp và ngữ nghĩa khá rõ ràng. * Đặc điểm cấu tạo từ tiếng Việt Cấu tạo từ tiếng Việt được phân loại theo hình 1.2 có một số đặc điểm sau: a. Từ đơn: Từ đơn là những từ được cấu tạo bởi một âm tiết độc lập. Ví dụ: nhà, cửa, đi, chạy, xanh, đỏ,... b. Từ phức: Từ phức là những từ được cấu tạo bởi hai âm tiết trở lên, ghép lại với nhau để tạo nghĩa. Về mặt quan hệ nghĩa, chúng được chia thành ba dạng sau: i) Từ ngẫu hợp: các thành phần không có quan hệ với nhau, được kết hợp với nhau một cách ngẫu nhiên. Ví dụ: bồ hóng, mít tinh, rơ moóc, tắc kè,... ii) Từ ghép: là những từ được cấu tạo bởi hai âm tiết trở lên, chúng được ghép với nhau về mặt ngữ nghĩa để tạo nghĩa mới. Từ ghép chính phụ: có chứa một thành tố chính chỉ loại lớn, một thành tố phụ có vai trò chi tiết hoá loại lớn. + Từ ghép chính phụ thuần Việt (chính trước, phụ sau) như: xe máy, xe đạp, hoa hồng, hoa nhài, máy xay, máy xát,... + Từ ghép chính phụ gốc Hán (phụ trước, chính sau) như: dân ca, đồng ca, xướng ca, bác học, văn học, kinh tế học, nông dân, ngư dân, cư dân,… Mở rộng từ ghép chính phụ bậc hai ở dạng thêm phần phụ chi tiết hơn như: xe đạp điện, xe đạp mini, hoa hồng trắng, hoa hồng vàng, máy xay thịt,... Từ ghép đẳng lập: các thành tố bình đẳng nhau về ngữ nghĩa và từ loại. Từ ghép song tiết đẳng lập có thể chia thành ba nhóm: + Đồng nghĩa: đợi chờ, xinh đẹp, chùa chiền, xe cộ,... + Đối nghĩa: cha mẹ, nam nữ, âm dương, được mất, đúng sai,... + Gần nghĩa: nhà cửa, đồi núi, sông suối, cát bụi, gà vịt, vui tươi,... Mở rộng từ có ba, bốn âm tiết có các đơn vị đẳng lập như: anh chị em, thanh thiếu nhi, cơ xương khớp, xuân hạ thu đông, bà con cô bác,... hoặc tổ hợp xen song tiết đẳng lập như: con ông cháu cha, cơm no áo ấm,… Mở rộng ghép chính phụ và đẳng lập: hai từ ghép chính phụ "thầy giáo" và "cô giáo" có hai thành phần đẳng lập là "thầy" và "cô", nên từ ghép mở rộng -7- là: "thầy cô giáo". Tương tự, "y sĩ" và "bác sĩ" có thể tạo từ ghép "y bác sĩ". Ghép giữa tổ hợp song tiết đẳng lập với từ đứng trước: chạy ngược chạy xuôi, bữa no bữa đói, khi nắng khi mưa,... hoặc có thể ghép với từ đứng sau: phòng cháy chữa cháy, phòng bệnh chữa bệnh, ăn miếng trả miếng,... Lặp lại từ ghép chính phụ: hư hư thực thực, đi đi về về, quần quần áo áo,... iii) Từ láy: là những từ phức (đa số là có hai tiếng) được cấu tạo theo các quy tắc hài âm và hài thanh của tiếng Việt (theo quy tắc “vừa điệp vừa đối” trên phụ âm đầu, vần và dấu thanh). Đối với từ láy đôi: theo [13] có 8 mẫu như: lăm lăm, đo đỏ, chúm chím, vằng vặc, lòng thòng, khéo léo, đỏ đắn, lập loè. Mở rộng từ láy ba, bốn âm tiết: + Từ láy bộ ba: đỏ lòm lòm, đen sì sì, xanh lè lè, tối om om,… đỏ hon hỏn, đen trùi trũi, thẳng đuồn đuột,… sạch sành sanh, cuống cuồng cuồng, xốp xồm xộp,... + Từ láy bộ tư: ấm a ấm ức, nhí nha nhí nhảnh, đù đà đù đờ, bậu xà bậu xậu, linh ta linh tinh, hớt hơ hớt hải,... Láy bổ sung cho một số các từ đơn, từ ghép: phần láy luôn đứng sau. Ví dụ: điệp phụ âm đầu và thêm vần "iếc", "iệc", "ang", "ung". + phở: phở phiếc; lớp: lớp lang; vải: vải vung; + máy bay: máy bay máy biếc; máy bay máy bung; + hoa tai: hoa tai hoa tiếc; hoa tai hoa tung; + đàn ông: đàn ông đàn iếc; đàn ông đàn ang;... Dạng lặp: là sự mở rộng của từ láy, có thành phần được lặp lại trong từ/cụm từ. Ví dụ: với từ có hai, ba hay bốn âm tiết + người người, ngày ngày, tháng tháng, xanh xanh, hây hây,… + ha ha ha, ầm ầm ầm,... + hăm hăm hở hở, hối hối hả hả, vội vội vàng vàng,... + tẩn ngẩn tần ngần, bổi hổi bồi hồi, bấu xấu bậu xậu,... + nói vội nói vàng, đen thui đen thủi,... Một số dạng lặp đặc biệt khác: + đen đen là; sợ sợ là; vui vui là; thương thương là;... + đẹp ơi là đẹp; xinh ơi là xinh; thương ơi là thương;... + ngoan thật là ngoan; khôn thật là khôn;... Tải về bản full