Khóa luận Phân lớp tài liệu web độc lập ngôn ngữ

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CƠNG NGHỆ Nguyễn Thị Thuỳ Linh PHÂN LỚP TÀI LIỆU WEB ĐỘC LẬP NGƠN NGỮ KHỐ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Cơng nghệ thơng tin Cán bộ hướng dẫn: NCS. Phan Xuân Hiếu Cán bộ đồng hướng dẫn: TS. Hà Quang Thuỵ HÀ NỘI – 2006 LỜI CẢM ƠN Em xin gửi lời cảm ơn chân thành và biết ơn sâu sắc tới Tiến sĩ Hà Quang Thuỵ (Trường Đại học Cơng Nghệ) và Nghiên cứu sinh Phan Xuân Hiếu (Japan Advanced Institute of Science and Technology) đã chỉ bảo và hướng dẫn tận tình cho tơi trong suốt quá trình nghiên cứu Khoa học và quá trình thực hiện khố luận này. Em xin gửi lời cảm ơn và biết ơn sâu sắc tới các thày, cơ đã dạy dỗ em trong suốt quá trình học tập tại trường Đại học Cơng Nghệ. Những kiến thức các thày, cơ dạy tơi là hành trang để tơi vững bước vào đời. Em cũng xin chân thành cảm ơn các thày, cơ, anh, chị trong Bộ mơn Các hệ thống thơng tin đã tạo điều kiện, giúp đỡ và động viên tinh thần cho em trong quá trình làm khố luận. Tơi xin gửi lời cảm ơn tới các bạn sinh viên trong nhĩm seminar “Khai phá dữ liệu và khám phá tri thức” đã ủng hộ và khuyến khích tơi trong quá trình nghiên cứu và làm khố luận này. Và cuối cùng, con xin gửi lời cảm ơn và biết ơn vơ hạn tới bố, mẹ, cảm ơn em trai tơi, những người thân yêu của tơi, đã nuơi nấng, dạy dỗ và luơn động viên, làm chỗ dựa tinh thần cho tơi trong cuộc sống cũng như trong học tập và làm việc. Xin chân thành cảm ơn! Hà Nội, ngày 25 tháng 05 năm 2006 Sinh viên Nguyễn Thị Thuỳ Linh i TĨM TẮT NỘI DUNG Phân lớp văn bản là một trong những bài tốn cơ bản và quan trọng nhất của lĩnh vực xử lý ngơn ngữ tự nhiên. Nĩ cĩ ứng dụng rất nhiều trong các bài tốn thực tế ví dụ như: ứng dụng lọc nội dung văn bản (lọc thư rác, lọc trang web cĩ nội dung phản động, trang web cĩ nội dung khơng lành mạnh,…), bài tốn phân lớp văn bản sau tìm kiếm,… Hiện nay cĩ rất nhiều bộ phân lớp đạt được độ chính xác cao (đều xấp xỉ 90%), tuy nhiên các bộ phân lớp này hầu hết chỉ áp dụng cho một ngơn ngữ cụ thể. Thực tế cho thấy, đối với bài tốn lọc nội dung trang Web thì một vấn đề đặt ra là phải xử lý trên nhiều ngơn ngữ khác nhau. Một trong hướng nghiên cứu phân lớp văn bản được quan tâm gần đây là phân lớp đa ngơn ngữ [7]. Khố luận này nghiên cứu và đề xuất một phương pháp phân lớp nội dung Web độc lập ngơn ngữ. Phương pháp này cho phép tích hợp thêm các ngơn ngữ mới vào bộ phân lớp và giải quyết vấn đề bùng nổ đặc trưng thơng qua hướng tiếp cận entropy cực đại và sử dụng chiến lược tối ưu hố hàm nhiều biến rất hiệu quả. Các kết quả thực nghiệm cho thấy hướng tiếp cận của khố luận rất khả quan, cụ thể, khi huấn luyện riêng biệt trên từng ngơn ngữ đều nhận được kết quả rất cao (Anh trên 98%, Việt trên 91%), cịn khi cĩ sự kết hợp của hai ngơn ngữ kết quả đạt được cũng rất khả quan (Anh-Việt xấp xỉ 95%). Đặc biệt khi cho mơ hình kiểm tra trên một tập dữ liệu hồn tồn mới kết quả cũng rất khả quan (độ chính xác Anh-Việt xấp xỉ 84%). Bên cạnh đĩ, khố luận cũng đã phân tích các vấn đề cơ bản của bài tốn phân lớp văn bản độc lập ngơn ngữ đĩ là sự nhập nhằng ngơn ngữ và sự bùng nổ đặc trưng, sau đĩ đã đưa ra các phương pháp khắc phục khá hiệu quả. Một đề xuất mới mà khố luận đưa ra là mơ hình dựa trên cây phân lớp thơng minh. Đề xuất này cĩ nhiều triển vọng cho các ứng dụng nhỏ cần phân loại văn bản và nhận diện được ngơn ngữ. ii MỤC LỤC LỜI CẢM ƠN.................................................................................................................. i TĨM TẮT NỘI DUNG................................................................................................... i MỤC LỤC ...................................................................................................................... ii BẢNG KÍ HIỆU VIẾT TẮT ......................................................................................... iv DANH MỤC BẢNG SỐ LIỆU.......................................................................................v DANH MỤC HÌNH ẢNH............................................................................................. vi MỞ ĐẦU .........................................................................................................................1 CHƯƠNG 1. KHÁI QUÁT VỀ PHÂN LỚP VĂN BẢN ĐỘC LẬP NGƠN NGỮ ......3 1.1. Bài tốn phân lớp văn bản ...................................................................................3 1.1.1. Tổng quan......................................................................................................3 1.2. Phân lớp văn bản độc lập ngơn ngữ .....................................................................4 1.2.1. Đặt vấn đề......................................................................................................4 1.2.2. Phân lớp văn bản độc lập ngơn ngữ ..............................................................5 1.2.3. Ý nghĩa và ứng dụng .....................................................................................5 CHƯƠNG 2. CÁC MƠ HÌNH VÀ THUẬT TỐN PHÂN LỚP VĂN BẢN...............7 2.1. Giới thiệu.............................................................................................................7 2.2. Mơ hình Maximum Entropy................................................................................7 2.2.1. Giới thiệu.......................................................................................................7 2.2.2. Xây dựng mơ hình .........................................................................................9 2.3. Tổng kết chương.................................................................................................16 CHƯƠNG 3. PHÂN LỚP TÀI LIỆU WEB ĐỘC LẬP NGƠN NGỮ VỚI MƠ HÌNH ENTROPY CỰC ĐẠI ...................................................................................................17 3.1 Giới thiệu............................................................................................................17 3.2. Bài tốn phân lớp văn bản độc lập ngơn ngữ ....................................................17 3.2.1. Vấn đề nhập nhằng ngơn ngữ ......................................................................17 3.2.2. Vấn đề bùng nổ đặc trưng ...........................................................................18 3.3. Quy trình xây dựng bộ phân lớp........................................................................19 3.3.1. Tiền xử lý dữ liệu ........................................................................................19 3.3.2. Xây dựng đặc trưng .....................................................................................20 3.3.3. Lựa chọn đặc trưng......................................................................................21 3.3.4. Huấn luyện mơ hình ....................................................................................23 3.3.5. Phân lớp văn bản mới ..................................................................................23 3.4. Đánh giá độ chính xác của bộ phân lớp ............................................................24 iii 3.4.1. Các độ đo.....................................................................................................24 3.4.2. Áp dụng phương pháp ước lượng chéo trên k tập con ................................25 3.5. Xây dựng bộ phân lớp trên cây phân lớp thơng minh .......................................25 3.5.1. Bản chất bài tốn .........................................................................................26 3.5.2. Phân lớp cho văn bản mới ...........................................................................26 3.5.3. Thảo luận .....................................................................................................27 3.6. Tổng kết chương................................................................................................27 CHƯƠNG 4. KẾT QUẢ THỬ NGHIỆM VÀ ĐÁNH GIÁ .........................................28 4.1. Mơi trường thử nghiệm ......................................................................................28 4.1.1. Mơi trường phần cứng.................................................................................28 4.1.2. Cơng cụ phần mềm......................................................................................28 4.2. Dữ liệu kiểm thử.................................................................................................29 4.2.1. Tiền xử lý dữ liệu ........................................................................................29 4.2.2. Cây phân lớp................................................................................................30 4.3. Kết quả thử nghiệm ............................................................................................31 4.3.1. Quá trình huấn luyện ...................................................................................31 4.3.2. Lần lặp cho độ chính xác cao nhất ..............................................................34 4.3.3. Kết quả kiểm tra trên dữ liệu mới ...............................................................35 4.4. Tổng kết chương.................................................................................................36 KẾT LUẬN ...................................................................................................................37 PHỤ LỤC. DANH SÁCH STOP-WORD ....................................................................38 TÀI LIỆU THAM KHẢO .............................................................................................41 iv BẢNG KÍ HIỆU VIẾT TẮT Kí hiệu Diễn giải GIS Generalized Interative Scaling HTML Hyper Text Markup Language IDF Inverse Document Frequency IIS Improved Iterative Scaling kNN K Nearest Neighbours L-BFGS Limited-memory Broyden-Fletcher-Goldfarb-Shannon MaxEnt Maximum Entropy NCR Numeric Character References TF Term Frequency UTF Unicode Transformation Formats v DANH MỤC BẢNG SỐ LIỆU Bảng 1. Cây phân lớp thơng minh tổng quát.................................................................26 Bảng 2. Bảng ví dụ cho cây phân lớp thơng minh ........................................................26 Bảng 3. Cấu hình hệ thống chạy thử nghiệm ................................................................28 Bảng 4. Danh sách phần mềm sử dụng để thử nghiệm .................................................28 Bảng 5. Danh sách cơng cụ sử dụng để thử nghiệm .....................................................29 Bảng 6. Cây phân lớp thơng tin.....................................................................................31 Bảng 7. Tập dữ liệu huấn luyện của cả 3 mơ hình ........................................................31 Bảng 8. Độ chính xác 10 lần huấn luyện của tiếng Anh ...............................................32 Bảng 9. Độ chính xác 10 lần huấn luyện của tiếng Việt ...............................................32 Bảng 10. Độ chính xác 10 lần huấn luyện kết hợp Anh-Việt........................................32 vi DANH MỤC HÌNH ẢNH Hình 1. Tập ràng buộc C ...............................................................................................12 Hình 2. Mơ tả các bước xây dựng bộ phân lớp .............................................................19 Hình 3. Trang tin tức tiếng Việt VnExpress.net............................................................29 Hình 4. Trang tin tức tiếng Anh BBC News .................................................................30 Hình 5. Độ chính xác của 3 bộ phân lớp trong 10 lần huấn luyện ................................33 Hình 6. Sự phụ thuộc độ chính xác theo bước lặp của cả 3 mơ hình ............................34 Hình 7. Kết quả kiểm tra bộ dữ liệu độc lập Anh-Việt .................................................35 1 MỞ ĐẦU Hiện nay, nhờ khả năng cho phép mã hố được phần lớn các ngơn ngữ thơng dụng trên tồn thế giới của bảng mã Unicode, khoảng cách giữa các quốc gia, dân tộc do hạn chế về ngơn ngữ gây ra đang dần được xố đi. Theo thống kê [20] hiện nay đã cĩ 141 ngơn ngữ được sử dụng trên Internet và xu hướng tất yếu là sẽ ngày càng xuất hiện thêm nhiều ngơn ngữ trên Internet. Bộ phân lớp văn bản đã cĩ hiện nay mới chỉ dừng ở mức phân lớp cho các văn bản cùng trên một ngơn ngữ. Nếu với 141 ngơn ngữ chúng ta xây dựng 141 bộ phân lớp thì quả thật tốn kém. Hơn thế nữa các trang web thương mại, web cĩ nội dung khơng lành mạnh hiện nay thể hiện và ẩn náu dưới nhiều hình thức đa dạng (nhiều ngơn ngữ cùng xuất hiện trong một trang web) với mục đích đi qua bộ lọc trong máy tìm kiếm, chúng gây rất nhiều phiền tối cho người dùng. Vì vậy, bài tốn phân lớp văn bản độc lập ngơn ngữ được đặt ra nhằm mục đích xây dựng một bộ phân lớp duy nhất cho nhiều ngơn ngữ. Ý thức được vấn đề đĩ, khĩa luận này tập trung xây dựng một bộ phân lớp tài liệu web độc lập ngơn ngữ dựa trên việc áp dụng nguyên lý entropy cực đại. Đây là phương pháp cĩ khả năng tích hợp mạnh hàng nghìn hàng triệu đặc trưng quan trọng. Qua kết quả thực nghiệm, với tập dữ liệu lên tới 12.000 trang Web bao gồm hai ngơn ngữ Anh và Việt, kết quả cho thấy rất khả quan. Mục tiêu mà khố luận hướng tới: 9 Xây dựng bộ phân lớp duy nhất cho nhiều ngơn ngữ dựa trên mơ hình entropy cực đại. 9 Khơng cần sử dụng một bộ phân nhận dạng ngơn ngữ nào khác. 9 Thử nghiệm và đánh giá, và vạch ra hướng phát triển tiếp theo. Cấu trúc của luận văn được tổ chức như sau: 9 Chương 1: Giới thiệu tĩm tắt bài tốn phân lớp văn bản, đặt vấn đề và phát biểu bài tốn phân lớp văn bản độc lập ngơn ngữ. 9 Chương 2: Trình bày cụ thể hơn về bài tốn phân lớp, đề cập đến các vấn đề cơ bản của nguyên lý entropy cực đại theo hướng áp dụng vào bài tốn phân lớp văn bản. 9 Chương 3: Phát biểu bài tốn phân lớp văn bản độc lập ngơn ngữ, phân tích các vấn đề cần giải quyết đối với bài tốn và các bước xây dựng bộ 2 phân lớp trên cơ sở áp dụng mơ hình entropy cực đại. Đưa ra một đề xuất mới cĩ thể áp dụng và các ứng dụng vừa và nhỏ. 9 Chương 4: Trình bày những kết quả đánh giá thử nghiệm của khố luận áp dụng cho bài tốn cây phân lớp tin tức với hai ngơn ngữ Anh và Việt. Cuối cùng là kết luận lại những điểm chính, những đĩng gĩp chính của luận văn, đồng thời chỉ ra những điểm cần khắc phục và vạch ra hướng cải tiến nhằm hướng tới xây dựng một hệ ứng dụng thực trên mơi trường Internet. 3 Chương 1 KHÁI QUÁT VỀ PHÂN LỚP VĂN BẢN ĐỘC LẬP NGƠN NGỮ Bài tốn phân lớp độc lập ngơn ngữ là một bài tốn con, phát triển trên nền của bài tốn phân lớp văn bản. Trước khi trình bày về bài tốn chính, chương này trình bày một cách sơ lược lịch sử cũng như ứng dụng của bài tốn phân lớp văn bản. 1.1. Bài tốn phân lớp văn bản 1.1.1. Tổng quan Phân lớp văn bản được coi là quá trình phân loại một văn bản bất kì vào một hay nhiều lớp cho trước. Theo phương pháp học máy (machine learning), quá trình này gồm hai bước. Ở bước thứ nhất, một mơ hình phân lớp (classfication model) được xây dựng dựa trên tri thức kinh nghiệm. Ở đây, tri thức kinh nghiệm chính là một tập dữ liệu huấn luyện (training dataset) được cung cấp bởi con người bao gồm một tập văn bản và phân lớp tương ứng của chúng. Bước này cịn gọi là bước xây dựng huấn luyện (training process) hay ước lượng mơ hình phân lớp. Ở bước thứ hai, mơ hình phân lớp xây dựng ở bước đầu sẽ được sử dụng để phân lớp cho những văn bản (chưa được phân loại) trong tương lai. Bước đầu tiên được xem như là việc học cĩ giám sát mà chúng ta cĩ thể sử dụng rất nhiều các kĩ thuật học máy đã cĩ như: Nạve Bayes, k láng giếng gần nhất (kNN), cây quyết định (Decision Tree),… Mục tiêu của bài tốn phân lớp là nhằm xây dựng mơ hình cĩ khả năng gán nhãn cho một văn bản bất kì với độ chính xác cao nhất cĩ thể. Nhu cầu cĩ một bộ phân lớp hiệu quả đã xuất hiện ngay từ thủa ban đầu của thời kì bùng nổ thơng tin trên Internet. Vì thế bài tốn phân lớp văn bản khơng phải là một khái niệm mới mẻ. Tuy nhiên, hiện nay càng ngày hệ thống máy tính cĩ khả năng xử lý càng mạnh, lượng thơng tin trên Internet biến đổi khơng ngừng cả về chất lượng và số lượng. Nên bài tốn phân lớp văn bản vẫn luơn là một vấn đề thời sự [7]. Đồng hành với lịch sử đĩ cho đến nay đã cĩ rất nhiều các cơng cụ, bộ phân lớp ra đời, cĩ thể là bộ phân lớp với từng ứng dụng cụ thể, hay bộ phân lớp cho một bài tốn nhưng áp dụng những kĩ thuật học máy khác nhau. Ứng dụng lớn nhất của bài tốn phân lớp văn bản là áp dụng vào bài tốn phân loại hay lọc nội dung. Trong bài tốn lọc nội dung: một văn bản được phân loại vào 4 nhĩm: cĩ ích hoặc khơng cĩ ích. Sau đĩ lấy tất cả những văn bản thuộc nhĩm cĩ ích, nhĩm cịn lại bị loại bỏ. Các ứng dụng cụ thể như: lọc thư rác, lọc trang web phản động,… Một ứng dụng khác của bài tốn phân lớp là xây dựng bộ phân lớp sau tìm kiếm, ứng dụng này rất hữu ích vì nĩ định vị nội dung thơng tin cần tìm kiếm nhanh và dễ dàng hơn. Tĩm lại, với tất cả ý nghĩa thực tế trên, một lần nữa cĩ thể khẳng định rằng trong thời đại Internet được coi là một phần khơng thể thiếu trong cuộc sống, phân lớp văn bản luơn là vấn đề đáng được quan tâm để cĩ thể phát triển và xây dựng được những cơng cụ ngày càng hữu dụng hơn. 1.2. Phân lớp văn bản độc lập ngơn ngữ 1.2.1. Đặt vấn đề Nếu thường xuyên theo dõi các trang tin của các hãng tin lớn, chúng ta dễ dàng nhận thấy chúng được thể hiện trên nhiều ngơn ngữ. Trên BBC hiện nay cĩ tới 33 ngơn ngữ, CNN cĩ 5 ngơn ngữ,… Hoặc khi chúng ta nhập câu truy vấn trong một hệ thống tìm kiếm trực tuyến (Google, Yahoo) để tìm kiếm thơng tin mà ta quan tâm, kết quả trả về là một danh sách các địa chỉ trang web chứa từ khố cần tìm và chúng hiển thị dưới nhiều ngơn ngữ khác nhau. Như vậy cĩ thể thấy rằng khá nhiều ngơn ngữ đã được đưa lên Internet. Hiện nay theo thống kê [20] đã cĩ tới 141 ngơn ngữ được mã hố và được sử dụng trên Internet, và theo xu thế này thì sẽ cịn cĩ nhiều hơn nữa các ngơn ngữ được mã hố và đưa vào sử dụng. Trong giai đoạn nền kinh tế hội nhập này, khơng chỉ các hãng tin lớn mà cả các tập đồn xuyên quốc gia cũng xây dựng trang web của mình trên nhiều ngơn ngữ khác nhau. Bên cạnh đĩ cịn cĩ các quốc gia muốn giới thiệu về nền văn hố, lịch sử nước mình bằng việc xây dựng các trang web trên Internet nhằm giao lưu văn hố và thu hút khách du lịch. Hơn thế nữa, hiện nay thư rác, các trang web thương mại, trang web phản động, trang web cĩ nội dung khơng lành mạnh,… ngày càng xuất hiện dưới nhiều hình thức phong phú hơn. Chúng khơng chỉ được biểu diến một ngơn ngữ mà cịn bởi đồng thời nhiều ngơn ngữ nhằm đi qua bộ lọc thư rác, hay các bộ lọc nội dung của máy tìm kiếm. Vì thế, việc xây dựng bộ phân lớp văn bản tự động cho nhiều ngơn ngữ là rất cần thiết. 5 Chúng ta cĩ thể xây dựng một bộ phân lớp như vậy bằng cách sử dụng một bộ nhận dạng ngơn ngữ cho văn bản rồi mới tiến hành phân lớp. Đây là một phương pháp hay, tuy nhiên khĩ khăn gặp khi phân lớp các tài liệu cĩ nhiều ngơn ngữ xuất hiện đồng thời. Hướng đến việc xây dựng cơng cụ áp dụng cho các ứng dụng vừa và nhỏ, trong khố luận này, chúng tơi đề xuất tiếp cận cho bài tốn phân lớp văn bản trên nhiều ngơn ngữ theo hướng khơng phụ thuộc ngơn ngữ (độc lập) sử dụng mơ hình entropy cực đại. 1.2.2. Phân lớp văn bản độc lập ngơn ngữ Phân lớp văn bản độc lập ngơn ngữ là một bài tốn phân lớp văn bản, cho phép sắp xếp một văn bản vào một lớp bất kì mà khơng cần quan tâm đến ngơn ngữ trên văn bản đĩ. Điều đĩ cũng cĩ nghĩa là các văn bản trên những ngơn ngữ khác nhau được coi là bình đẳng. Ý nghĩa của chữ “độc lập” là như vậy. Trong [7], Fuchen đề xuất ý tưởng sử dụng mơ hình ngơn ngữ N-gram giải quyết các bài tốn xử lý ngơn ngữ tự nhiên độc lập ngơn ngữ. Mơ hình N-gram là một mơ hình thống kê thuần tuý, nếu xét trên một tập dữ liệu lớn thì nĩ sẽ gặp phải vấn đề bùng nổ đặc trưng, là một trong thách thức với bài tốn phân xử lý ngơn ngữ tự nhiên độc lập ngơn ngữ nĩi chung và bài tốn phân lớp văn bản độc lập ngơn ngữ nĩi riêng. Bản chất các ngơn ngữ trong tự nhiên tồn tại sự nhập nhằng: Cĩ nhiều từ mượn, từ dùng chung giữa các ngơn ngữ với nhau. Sự nhập nhằng này rõ ràng sẽ ảnh hưởng đến độ chính xác bộ phân lớp của chúng ta một mức độ nhất định. Bên cạnh đĩ, một vấn đề cốt lõi cần phải giải quyết khi muốn xây dựng bộ phân lớp cho văn bản độc lập ngơn ngữ là sự bùng nổ đặc trưng. Cả hai vấn đề này sẽ được phân tích và được đưa ra cách giải quyết trong Chương 3. Trong khố luận này, chúng tơi sử dụng kĩ thuật học máy entropy cực đại để xây dựng mơ hình phân lớp . Entropy cực đại là một phương pháp cho phép khả năng tích hợp mạnh nhiều đặc trưng, cĩ thể là hàng nghìn hàng triệu đặc trưng. Qua thử nghiệm đã cho thấy kết quả rất khả quan. Độ chính xác trong quá trình huấn luyện của bộ phân lớp của hai ngơn ngữ Anh – Việt xấp xỉ 95%, trong khi bộ phân lớp của tiếng Anh là 98% và của tiếng Việt là trên 91%. 1.2.3. Ý nghĩa và ứng dụng Phân lớp tài liệu Web độc lập ngơn ngữ là bài tốn cĩ ý nghĩa và ứng dụng thực tiễn cao. Nĩ cho phép áp dụng vào các bài tốn như: 6 - Bài tốn lọc nội dung: lọc thư rác, lọc web phản động, web khơng lành mạnh,… Hiện nay, bất kì ai sử dụng email cũng đối mặt với nạn thư rác được viết bằng đủ mọi thứ tiếng Anh, Pháp, Nga, Nhật, Hàn,… Chúng vào hịm thư của chúng ta và gây nhiều phiền tối nên việc ngăn chặn chúng là rất cần thiết. Bên cạnh đĩ, trên Internet hiện nay xuất hiện ngày càng nhiều các trang Web khơng lành mạnh cĩ ảnh hưởng xấu tới các em thiếu niên, học sinh. Web khơng lành mạnh ở đây khơng chỉ cĩ sex mà cịn cĩ thể cĩ nội dung về “chế tạo hoặc sử dụng vũ khí mang tính bạo lực” hay “web hướng dẫn về tự tử tập thể” (như ở Nhật),… Bảo vệ các em thiếu niên trước những thơng tin khơng lành mạnh như vậy là điều rất cần thiết. - Sử dụng làm bộ phân lớp cho các hãng tin, tổ chức xuyên quốc gia, thậm chí là các trang web giới thiệu về mình của các quốc gia trên tồn thế giới. - Một ứng dụng cũng rất hữu ích là làm cơng cụ phân lớp cho các thư viện sách lớn, thay thế cho cơng việc của một thủ thư. Ở đây, mơ hình được xây dựng bằng cách đọc các tĩm tắt trên mỗi quyển sách và sau đĩ tiến hành phân lớp. Xếp mỗi quyển sách vào một trong cách lĩnh vực: Tốn học, Vật lý, Hố học, Văn học,… một cách chính xác; khi đĩ người thủ thư sẽ dễ dàng sắp xếp các quyển sách vào các khu vực với lĩnh vực tương ứng mà khơng phải đọc và phân tích tĩm tắt của quyển sách. - Hiện nay, chúng tơi đang đề xuất ứng dụng nghiên cứu của khố luận vào dự án “Nghiên cứu, phát triển hệ thống lọc nội dung hỗ trợ quản lý và đảm bảo an tồn – an ninh thơng tin trên mạng Internet”. Tuy nhiên, cần phải khẳng định lại rằng, ứng dụng lớn nhất của bài tốn phân lớp văn bản độc lập ngơn ngữ là ứng dụng lọc thư rác, web phản động,… Ngồi ra với tuỳ những đặc điểm của các ứng dụng khác mà ta xây dựng bộ phân lớp cho phù hợp. 7 Chương 2 CÁC MƠ HÌNH VÀ THUẬT TỐN PHÂN LỚP VĂN BẢN 2.1. Giới thiệu Như đã đề cập ở chương 1, hiện nay đã cĩ rất nhiều kĩ thuật học máy được áp dụng để giải quyết bài tốn phân lớp [7]. Điển hình là các phương pháp như: • Naive Bayes: phân lớp Nạve Bayes sinh ra từ luật Bayes. Nĩ địi hỏi giả thiết độc lập giữa các cứ liệu quan sát được từ dữ liệu mẫu. Kĩ thuật này được ứng dụng nhiều trong các bài tốn phân loại văn bản, và bài tốn word sense disambiguation. • Cây quyết định thống kê: Thuật tốn phân hoạch đệ quy cho phép cây quyết định thống kê học trong tập dữ liệu huấn luyện. Nhược điểm chính của cây quyết định là sự phân mảnh dữ liệu do bị phân hoạch dữ liệu mẫu trong quá trình học. Vì vậy chúng phải sử dụng các kĩ thuật phân cụm (clustering) và làm trơn (smoothing). Vấn đề lớn nhất với bài tốn phân lớp văn bản là ở chỗ tích hợp được các quan sát từ dữ liệu mẫu vào mơ hình càng nhiều càng tốt, và phải cĩ thuật tốn học tối ưu. So với các mơ hình khác, mơ hình phân loại dựa trên nguyên lý entropy cực đại cĩ thế mạnh là khả năng học và nhớ đến hàng trăm nghìn đặc trưng, thậm chí hàng triệu đặc trưng từ dữ liệu mẫu nhờ vào một chiến lược tối ưu hố hàm nhiều biến rất hiệu quả. Khả năng này rất phù hợp với bài tốn phân lớp văn bản và đặc biệt là bài tốn phân lớp văn bản độc lập ngơn ngữ khi mà lượng đặc trưng là rất lớn. 2.2. Mơ hình Maximum Entropy Mơ hình entropy cực đại [4][11][12][14][15][16][17] là mơ hình dựa trên xác suất cĩ điều kiện cho phép tích hợp các thuộc tính đa dạng từ dữ liệu mẫu nhằm hỗ trợ quá trình phân lớp. 2.2.1. Giới thiệu Trước khi trình bày về mơ hình entropy cực đại, chúng ta cùng xem xét một ví dụ đơn giản sau. Xét một quá trình ngẫu nhiên: gieo con súc sắc, đồng chất, cân đối. Quan sát 1.000 lần thử, thống kê xác suất xuất hiện của từng mặt ta cĩ nhận xét: 8 6 1 ( ) 1 i p i = =∑ (1) p(i) là xác suất xuất hiện của mặt cĩ i chấm. Dễ dàng nhận thấy cĩ rất nhiều nghiệm thoả mãn phương trình (1), ví dụ với ( )1 1p = và tất cả các mặt khác cĩ xác suất bằng 0 nghĩa là mặt xuất hiện luơn là mặt 1. Tuy nhiên, ta biết rằng trong thực tế quá trình sinh các mặt là ngẫu nhiên nên phân phối giống với phân phối thực nhất là: xác suất xuất hiện cho từng mặt là bằng nhau, hay nĩi khác phân phối xác suất ở đây là phân phối đều: ( ) ( ) ( ) ( ) ( ) ( )1 2 3 4 5 6 1/ 6p p p p p p= = = = = = Giả sử, vì một lý do sản xuất nào đĩ, con súc sắc bị lệnh về hai mặt 1 và 4. Trong 1000 lần gieo thử, ta quan sát thấy rằng số lần xuất hiện mặt 1 và mặt 4 chiếm 50% số lần tung: ( ) ( )1 4 1/ 2p p+ = (2) Vì phân phối xác suất cho các mặt vẫn tuân theo phương trình (1) nên ta cĩ: ( ) ( ) ( ) ( )2 3 5 6 1/ 2p p p p+ + + = (3) Rõ ràng cĩ rất nhiều phân phối thoả mãn cho cả phương trình (2) và (3), ví dụ với ( ) ( )1 1/ 3, 4 1/ 6p p= = và ( )2 1/8p = , các mặt 3, 5, 6 cĩ xác suất xuất hiện là 0. Tuy nhiên, lại một lần nữa ta thấy rằng, phân phối giống với phân phối thực nhất là: ( ) ( )1 4 1/ 4p p= = ( ) ( ) ( ) ( )2 3 5 6 1/8p p p p= = = = Dữ liệu trong thế giới thực là vơ hạn, khĩ đốn nhận, ta mong muốn xây dựng được một mơ hình mà ước lượng được gần đúng với phân phối thực thơng qua một tập dữ liệu mẫu. Qua ví dụ vừa nêu trên chúng ta cĩ nhận xét rằng: trong tập dữ liệu mẫu mà ta cĩ được, mơ hình cĩ phân phối đều nhất thì sẽ gần giống với phân phối thực nhất. Vì vậy, vấn đề đặt ra là: làm thế nào để tìm được một mơ hình như vậy? Phương pháp entropy cực đại cho phép tìm ra được mơ hình này. Tư tưởng chủ đạo của nguyên lý entropy cực đại rất đơn giản: ta phải xác định mơt phân phối mơ hình sao cho phân phối đĩ tuân theo mọi giả thiết đã quan sát từ 9 thực nghiệm, ngồi ra khơng cho thêm bất kì giả thiết nào khác. Điều này cĩ nghĩa là phân phối mơ hình phải thoả mãn các ràng buộc quan sát từ thực nghiệm, và phải gần nhất với phân phối đều. Entropy là độ đo về tính đồng đều hay tính ko chắc chắn của một phân phối xác suất. Một phân phối xác suất cĩ entropy càng cao thì phân phối của nĩ càng đều. Độ đo Entropy điều kiện của một phân phối xác suất trên một chuối các trạng thái với điều kiện biết từ một chuỗi dữ liệu quan sát được tính như sau: ( ) ( ) ( ) ( ) , | log | x y H p p x p y x p y x≡ −∑ % 2.2.2. Xây dựng mơ hình Xem xét bài tốn phân lớp, với Y là tập các lớp, X là tập các thơng tin ngữ cảnh, là những thơng tin quan trọng cần cho việc phân lớp văn bản vào lớp Y một cách chính xác. Nhiệm vụ trong bài tốn phân lớp là xây dựng một mơ hình thống kê mà dự đốn chính xác lớp của văn bản bất kì. Mơ hình như vậy chính là phương pháp ước lượng xác suất cĩ điều kiện ( )xyp | . Mơ hình entropy cực đại cung cấp một phương pháp đơn giản để ước lượng xác suất cĩ điều kiện ( )xyp | thơng qua việc thống kê các thuộc tính quan trọng quan sát được từ tập dữ liệu huấn luyện. 2.2.2.1. Tập dữ liệu huấn luyện Như các phương pháp học máy khác, để làm bài tốn phân lớp trước tiên phải xây dựng tập dữ liệu huấn luyện ( ) ( ){ }1 1, , , ,N NT x y x y= K trong đĩ { }1, , Nx xK là tập các thơng tin ngữ cảnh đã được gán nhãn tương ứng là tập các lớp { }1, , Ny yK . Với một cặp ( ),i ix y , phân phối xác suất thực nghiệm của nĩ được tính bởi: ( ) 1,i ip x y N=% × số lần xuất hiện của ( ),i ix y trong tập dữ liệu mẫu Thơng thường thì mỗi cặp ( ),i ix y khơng thể khơng xuất hiện trong tập mẫu, mà nĩ sẽ xuất hiện ít nhất một lần. 10 2.2.2.2. Thống kê, đặc trưng và ràng buộc Những thống kê từ dữ liệu mẫu chính là những viên gạch đầu tiên để xây dựng mơ hình. Ví dụ, khi xét bài tốn lọc thư rác. Một thư được xếp vào một trong 3 nhĩm sau: thư rác (Spam), khơng phải thư rác (non-Spam), để xem xét (warning). Quan sát từ tập dữ liệu mẫu là 1.000 thư đã được gán nhãn, ta cĩ nhận xét như sau: “nếu thư cĩ chứa cụm từ “sản phẩm mới”, thì xác suất thư đĩ là thư rác là 80%”. Đây chính là một thống kê. Trong [4] đưa ra cách biểu diễn sự kiện “thư cĩ chứa cụm từ “sản phẩm mới” là thư rác” như sau: ( ), 1 if and, 0document_has san_pham_moi Spam y Spam document_has san_pham_moi true f x y = =⎧= ⎨⎩ Gọi hàm f được biểu diễn như trên là hàm đặc trưng hay đặc trưng. Giá trị kì vọng của f đối với phân phối thực nghiệm ( , )p x y% là giá trị thống kê được một cách chính xác (trong ví dụ trên thì đĩ là: 0,8): số lần xuất hiện của f trong tập dữ liệu huấn luyện. Nĩ được biểu diễn như sau: ( ) ( ) , , ,p i i x y E f p x y f x y=∑% % (4) Bất kì thống kê nào sinh ra từ tập dữ liệu mẫu cũng cĩ thể được biểu diễn một hàm kì vọng của đặc trưng f theo quy tắc như trên. Trong [16] cung cấp một cách cĩ hệ thống cách xây dựng hàm đặc trưng. Thơng tin “thư cĩ chứa cụm từ “sản phẩm mới”” được xây dựng thành một mệnh đề thơng tin ngữ cảnh: [document_has sản phẩm mới] → { },true false kí hiệu là ( )cp x , hàm này là một ánh xạ cặp ( ),x y một giá trị trong tập { },true false . Nĩ cĩ dạng tổng quát như sau: ( ) { }: ,cp x X true false→ Trong [16] biễu diễn hàm đặc trưng dạng tổng quát: ( ) ( ), ' 1 ', 0cp y y y cp x true f x y = =⎧= ⎨⎩ nÕu vµ ng−ỵc l¹i 11 Hàm đặc trưng là hàm kiểm tra sự xuất hiện đồng thời của mệnh đề thơng tin ngữ cảnh và lớp được dự đốn. Thống kê vừa nêu trong ví dụ ở phần trước là một thơng tin quan trọng: xác suất xuất hiện lên tới 80%. Trong quá trình quan sát tập dữ liệu, ta sẽ nhận được rất nhiều thống kê hữu ích. Vì thế, nếu coi đĩ là một điều kiện mà mơ hình phải tuân theo thì sẽ giúp mơ hình dự đốn được lớp của văn bản một cách chính xác hơn. Biểu diễn theo tốn học, ta cĩ phương trình như sau: p i p iE f E f=% (5) Phương trình này được gọi là ràng buộc, gọi đầy đủ là phương trình ràng buộc, trong đĩ: ( ) ( ) ( ) , | ,p i i x y E f p x p y x f x y=∑ % (6) p iE f là kì vọng của f đối với mơ hình ( )|p y x Từ (4), (5) và (6) ta cĩ: ( ) ( ) ( ) ( ) ( ) , , , , | ,i i x y x y p x y f x y p x p y x f x y=∑ ∑% % Thêm một ràng buộc cĩ nghĩa là đã loại bỏ bớt đi những mơ hình khơng tuân theo dữ liệu mẫu, điều này được biễu diễn một cách hình học ở Hình 1. Đến đây, chúng ta thấy được ý nghĩa của việc biễu diễn các cứ liệu thống kê được từ dữ liệu mẫu (chính là p iE f% ), và ý nghĩa của việc ràng buộc mơ hình của chúng ta tuân theo những sự kiện đĩ (chính là p i p iE f E f=% ). 2.2.2.3. Nguyên lý entropy cực đại Giả sử quá trình thống kê từ tập dữ liệu huấn luyện sinh ra n đặc trưng if , mỗi đặc trưng này sẽ xác định một ràng buộc. Gọi P là khơng gian của tất cả các phân phối xác suất, C là tập con của P sẽ được mơ tả như sau: { }{ }| 1,2,..,p i p iC p P E f E f i n≡ ∈ = ∈víi% Hình 1 mơ tả 4 trường hợp tập C khi cĩ các ràng buộc. P biểu diễn khơng gian của tất cả các phân phối xác suất. Ở hình (a), khơng cĩ ràng buộc nào, tất cả các Pp∈ đều thoả mãn. Ở hình (b), C1 cắt bớt đi một phần các mơ hình p cĩ thể. Đến hình (c), mơ hình của ta chỉ cịn nằm trong phần giới hạn bởi C1 và C2: 21 CCp ∩∈ . Trong 12 hình (d), hai ràng buộc C1 và C3 mâu thuẫn ( 1 3C C∩ =∅ ), khơng cĩ Pp∈ nào thoả mãn cả hai ràng buộc đĩ. (a) (b) (c) (d) P P P C1 C1 C2 C1 C3 Hình 1. Tập ràng buộc C Nguyên lý entropy cực đại được phát biểu rằng: “Từ tập các phân bố xác suất cĩ thể được là C, sẽ tìm ra được một mơ hình *p C∈ thoả mãn điều kiện làm cực đại độ đo entropy H(p): ( )* argmax p C p H p ∈ = Dễ dàng chỉ ra rằng *p luơn luơn xác định và trong bất kì một tập C nào, cũng chỉ cĩ duy nhất một mơ hình *p làm cực đại entropy [4]. 2.2.2.4. Dạng tham số Từ nguyên lý entropy cực đại ta cĩ thể phát biểu lại rằng: tư tưởng chủ đạo của entropy cực đại là ta phải xây dựng được một phân phối thoả mãn các ràng buộc và gần nhất với phân phối đều. Vấn đề đặt ra ở đây là làm thế nào để ta tối ưu được 13 các ràng buộc, tức tìm ra được *p C∈ làm cực đại ( )H p . Trong những trường hợp đơn giản, chúng ta dễ dàng tìm ra mơ hình phù hợp bằng các phương pháp giải tích. Tuy nhiên trong thực tế, số các ràng buộc là rất lớn và chồng chéo nhau. Vì vậy, chúng ta sẽ giải bài tốn này theo một hướng tiếp cận khác. Với mỗi một đặc trưng if , ta đưa vào một tham số iλ là một thừa số nhân Lagrange. Hàm Lagrange ( ),p λΛ được định nghĩa như sau: ( ) ( ) ( ), i p i p i i p H p E f E fλ λΛ ≡ + −∑ % (7) Theo lý thuyết thừa số Lagrange, phân phối xác suất ( | )p y x làm cực đại độ đo entropy ( )H p và thoả mãn tập ràng buộc C thì cũng làm cực đại hàm ( ),p λΛ trên khơng gian phân phối xác xuất P. Gọi pλ là mơ hình làm cực đại hàm Lagrange ( ),p λΛ , và ( )λΨ là giá trị cực đại. ( )argmax , p P p pλ λ∈= Λ (8) ( ) ( ),pλλ λΨ = Λ (9) Ta gọi ( )λΨ là hàm đối ngẫu (dual function). Các hàm pλ , ( )λΨ đã được tính tốn, chúng cĩ cơng thức như sau: ( ) ( ) 1( | ) exp ,i i i p y x f x y Z xλ λ λ⎛ ⎞= ⎜ ⎟⎝ ⎠∑ (10) ( ) ( ) ( )log i p i x i p x Z x E fλλ λΨ = − +∑ ∑ %% (11) Trong đĩ ( )Z xλ là thừa số chuẩn hố để thoả mãn ( )| 1 y p y xλ =∑ đối với mọi x: ( ) ( )iexp ,i y i Z x f x yλ λ⎛ ⎞= ⎜ ⎟⎝ ⎠∑ ∑ Cuối cùng thay cho việc phải tìm phân phối thoả mãn tập ràng buộc lớn và phức tạp làm cực đại độ đo entropy, ta đưa về bài tốn chỉ cần tìm tập tham số *λ làm cực đại hàm đối ngẫu ( )λΨ khơng cịn ràng buộc. 14 Kết quả này cĩ một ý nghĩa quan trọng. Khi đĩ, bất kì một thuật tốn tìm cực đại *λ cho hàm ( )λΨ cĩ thể sử dụng để tìm ra phân phối cực đại *p của ( )H p thoả mãn *p C∈ . 2.2.2.5. Mối quan hệ với Maximum Likelihood Maximum likelihood là một phương pháp thống kê cổ điển, tư tưởng của nĩ là làm cực đại độ đo likelihood giữa phân phối mơ hình và phân phối thực nghiệm. Hàm log-likelihood ( )pL p% của phân phối thực nghiệm p% được định nghĩa: ( ) ( ) ( ) ( ) ( ), ,, log | , log |p x yp x yx y L p p y x p x y p y x≡ =∑∏ %% % (12) Gọi pλ là mơ hình làm cực đại hàm likelihood ( )pL p% , thay (10) vào phương trình (12) ta thu được biểu thức nằm bên vế phải của phương trình (11). Từ đĩ ta cĩ: ( ) ( )pL pλλΨ = % Đến đây với kết quả từ phần trước, ta kết luận được rằng: “Mơ hình *p C∈ với entropy cực đại là mơ hình dưới dạng tham số ( )|p y xλ làm cực đại likelihood trên mẫu dữ liệu huấn luyện”. Sự tương đương này cung cấp một phương pháp mới cho phép ước lượng tham số cho các phân phối mơ hình dựa trên nguyên lý entropy cực đại bằng cách sử dụng các phép ước lượng tham số cho likelihood cực đại. 2.2.2.6. Các thuật tốn ước lượng tham số Cĩ nhiều thuật tốn dùng để ước lượng tham số, điển hình là các thuật tốn GIS, IIS, L-BFGS. Trong khố luận này, chúng tơi xin giới thiệu thuật tốn L-BFGS là thuật tốn ước lượng tập tham số hiệu quả nhất hiện nay. Cho tập dữ liệu huấn luyện ( ) ( ){ }1 1, ,..., ,N NT x y x y= . Phân phối mũ: ( ) ( ) 1( | ) exp ,i i i p y x f x y Z xλ λ λ⎛ ⎞= ⎜ ⎟⎝ ⎠∑ Huấn luyện mơ hình entropy cực đại chính là ước lượng tập trọng số { },...,i kλ λ λ= để phân phối mũ ở trên đạt cực đại cao nhất. 15 Thuật tốn L-BFGS là phương pháp giới hạn bộ nhớ cho phương pháp quasi- Newton (Limited memory BFGS). Phương pháp này cung cấp khả năng tối ưu hàng triệu tham số với tốc độ rất nhanh vì vậy trong các nghiên cứu mới đây nĩ được đánh giá là hiệu quả hơn các phương pháp khác. Viết lại hàm log-likelihood khi thay ( )|p y xλ từ () vào (): ( ) ( ) ( ) 1 1 1 1 , log exp , N k N k j j i i j j i i j i a A j L p f x y f y xλ λ λ = = = ∈ = ⎛ ⎞= − ⎜ ⎟⎝ ⎠∑∑ ∑ ∑ ∑ Tư tưởng của thuật tốn là sử dụng phương pháp leo đồi tìm kiếm cực đại tồn cục. Vì bề mặt của hàm ( )L pλ là lồi nên hồn tồn cĩ thể thực hiện được điều này. Các thủ tục lặp được sử dụng để tiến gần đến tối ưu tồn cục của hàm ( )L pλ . Tại mỗi bước lặp ta tìm vec-tơ gradient nào cĩ hướng tiến tới cực đại tồn cục nhất. Trên bề mặt của một hàm lồi, vec-tơ gradient thoả mãn điều kiện đĩ sẽ cĩ giá trị bằng 0 r . Với mỗi một vec-tơ gradient ( ) ( ) 1 ,..., N L p L pλ λ λ λ ∂ ∂⎛ ⎞⎜ ⎟∂ ∂⎝ ⎠ hiện tại xác định cho ta một tập các trọng số. Thành phần thứ i của vec-tơ gradient của ( )L pλ là: ( ) ( ) ( )( ) ( )( )( ) ( ) ( ) ( ) ( ) ( ) n i=1 n 1 1 i=1 1 1 exp , , , exp , , | , , , N N i i j j jy Y i j j j ji i i jy Y N N i j j j i j j j y Y p i p i f y x f y xL p f x y f y x f x y p y x f y x E f x y E f x yλ λ λ λ λ λ ∈ = = ∈ = = ∈ ∂ = −∂ = − = − ∑ ∑∑ ∑ ∑ ∑ ∑ ∑∑ % Trong mỗi bước lặp thủ tục L-BFGS yêu cầu giá trị hiện tại của ( )L pλ và vec-tơ gradient hiện tại. Sau đĩ nĩ tính tốn để cập nhật giá trị mới cho tập tham số { }1,..., Nλ λ . Cuối cùng, ta thu được tập trọng số tối ưu { }* *1 ,..., Nλ λ sau một số hữu hạn các bước lặp. ( ) ( ) ( )( ) | | p x y p y p y x p x = 16 2.3. Tổng kết chương Trong chương này chúng ta đã xem xem xét các vấn đề cơ bản của nguyên lý entropy cực đại theo hướng ứng dụng vào bài tốn phân lớp văn bản. Chúng ta đã hiểu được tư tưởng chủ đạo của nguyên lý entropy, thấy được khả năng cho phép tích hợp được hàng nghìn đặc trưng của mơ hình này. Chương này cũng trình bày được mối liên hệ giữa lilelihood cực đại và entropy cực đại, đĩ là sự tương đương trong ước lượng tham số cho mơ hình tối ưu. Thuật tốn ước lượng L-BFGS là phương pháp ước lượng tham số tối ưu thơng qua log-likelihood cũng đã được trình bày ở đây. Điều đĩ khẳng định sức mạnh của phương pháp entropy cực đại, đặc biệt là khi ứng dụng vào bài tốn phân lớp văn bản. Chương đầu đã giới thiệu về bài tốn phân lớp văn bản độc lập ngơn ngữ nĩi chung và bài tốn phân lớp tài liệu web độc lập ngơn ngữ nĩi riêng. Chương tiếp theo sẽ đề cập đến bài tốn chính của khố luận một cách chi tiết, phân tích những vấn đề sẽ gặp phải với bài tốn phân lớp văn bản độc lập ngơn ngữ. Và cũng trong chương tới, chúng ta sẽ xem xét việc xây dựng bộ phân lớp tài liệu web độc lập ngơn ngữ với mơ hình entropy cực đại. 17 Chương 3 PHÂN LỚP TÀI LIỆU WEB ĐỘC LẬP NGƠN NGỮ VỚI MƠ HÌNH ENTROPY CỰC ĐẠI 3.1 Giới thiệu Trong chương 1, chúng ta đã giới thiệu một cách tổng quát về bài tốn phân lớp văn bản độc lập ngơn ngữ, về các những nhu cầu thực tế, ứng dụng cũng như ý nghĩa của bài tốn. Chương này trình bày việc giải quyết bài tốn phân lớp độc lập ngơn ngữ, phân tích đầy đủ các vấn đề là thách thức đối với bài tốn, và đưa ra các cách giải quyết cho các vấn đề đĩ. Trong đĩ cĩ đề xuất một chiến lược loại bỏ stop- word trong n-gram khá hiệu quả. Đồng thời, trong chương này cũng trình bày được các bước xây dựng bộ phân lớp ứng dụng nguyên lý entropy cực đại. Đặc biệt ở phần cuối chương chúng tơi đề xuất cách xây dựng một bộ phân lớp văn bản cĩ khả năng đặc biệt, cho phép phân lớp và nhận dạng ngơn ngữ cho văn bản mà khơng cần sử dụng cơng cụ nhận dạng. 3.2. Bài tốn phân lớp văn bản độc lập ngơn ngữ Như đã phân tích ở chương 1, nhu cầu phân lớp và lọc các tài liệu web đa ngơn ngữ hiện nay là rất cần thiết. Vì vậy bài tốn phân lớp văn bản cho nhiều ngơn ngữ ra đời. Kèm theo đĩ là những vấn đề mà bài tốn phân lớp văn bản đa ngơn ngữ nĩi chung, bài tốn phân lớp văn bản độc lập ngơn ngữ nĩi riêng cần phải giải quyết. Hai vấn đề quan trọng nhất: 9 Sự nhập nhằng ngơn ngữ: giữa hai hay nhiều ngơn ngữ cĩ từ trùng nhau - vấn đề này chưa hề xuất hiện trong các bài tốn phân lớp văn bản trên một ngơn ngữ. 9 Số lượng đặc trưng vơ cùng lớn cĩ thể dẫn tới bùng nổ tổ hợp. Vì vậy nhiệm vụ cốt lõi cho bài tốn là phải cĩ những chiến lược trích chọn đặc trưng tốt. 3.2.1. Vấn đề nhập nhằng ngơn ngữ Trường hợp xuất hiện các từ giống nhau giữa hai ngơn ngữ khơng phải hiếm, trong khố luận này tạm gọi đĩ là hiện tượng nhập nhằng ngơn ngữ. Ở đây đã loại trừ 18 trường hợp hai chữ khác nhau của hai ngơn ngữ cĩ mã giống nhau vì Unicode đã hỗ trợ khả năng mã hố và nhận diện được chúng. Ở một số ngơn ngữ cĩ số lượng từ trùng nhau nhiều nhưng nghĩa của chúng lại gần như tương đồng. Ví dụ, chữ Trung Quốc và Nhật Bản cùng sử dụng một lượng lớn chữ Kanji nhưng nghĩa lại hồn tồn giống nhau. Hoặc với tiếng Anh, Pháp, Đức là ba ngơn ngữ cĩ hệ từ vựng khá giống nhau, các từ giống nhau thì nghĩa cũng khá giống nhau. Các trường hợp nêu trên thường chỉ xảy ra với các ngơn ngữ cùng một Hệ chữ viết. Cịn trong trường hợp các ngơn ngữ khác hệ chữ viết, cĩ khi cả các ngơn ngữ trong cùng một Hệ chữ viết vẫn xảy ra sự nhập nhằng. Ví dụ: chữ “can” trong tiếng Việt cĩ nghĩa hồn tồn khác với chữ “can” trong tiếng Anh. Nếu xét về bản chất, vấn đề này giống như hiện tượng đồng âm khác nghĩa của từ trong bài tốn phân lớp văn bản đơn ngơn ngữ. Do đĩ nghĩa của từ dễ dàng được xác định khi cĩ sự hỗ trợ của các từ xung quanh. Rõ ràng “can_nước” khác với “can_you” nên đặc trưng của các N- gram này cĩ độ tin cậy cao khi phân lớp. Mà xu thế những đặc trưng cĩ đơ tin cậy cao thì được gán trọng số lớn hơn trong quá trình học. Như vậy, qua đây cĩ thể khẳng định vấn đề nhập nhằng ngơn ngữ khơng ảnh hưởng đến độ chính xác của bộ phân lớp, nếu cĩ cũng chỉ là rất nhỏ. 3.2.2. Vấn đề bùng nổ đặc trưng Trong các bài tốn phân lớp văn bản trên một ngơn ngữ thì giai đoạn lựa chọn đặc trưng luơn được coi là một nhiệm vụ quan trọng. Đặc trưng càng được lựa chọn tinh tế thì độ chính xác và tốc độ của bộ phân lớp càng tăng. Với bài tốn phân lớp văn bản đa ngơn ngữ nĩi chung và bài tốn phân lớp văn bản độc lập ngơn ngữ nĩi riêng cịn xảy ra hiện tượng bùng nổ đặc trưng: số lượng các đặc trưng quá lớn. Ví dụ, giả sử một văn bản cĩ độ dài trung bình là 2.000 từ, giả sử ta dùng n-gram với n= 1, 2, 3 thì với 16.000 văn bản Anh, Pháp và Việt số đặc trưng sẽ xấp xỉ 96 triệu. Đây quả là một con số khổng lồ, địi hỏi phải thao tác trên máy tính cĩ hiệu năng rất lớn. Với tập các đặc trưng lớn như vậy cịn nảy sinh hai vấn đề: dữ liệu thưa và overfitting. Dữ liệu thưa tồn tại các đặc trưng xuất hiện rất ít, hoặc rất nhiều. Overfitting là hiện tượng tương đối đặc biệt và ít gặp trong thực tế. Vì vậy cĩ thể nĩi, nhiệm vụ lựa chọn đặc trưng là một nhiệm vụ quan trọng trong bài tốn phân lớp đa ngơn ngữ. 19 Để giải quyết vấn đề này, trong khố luận chúng tơi cố gắng một cách tối đa loại bỏ những đặc trưng khơng quan trọng. Điều này được thực hiện trong các bước xây dựng mơ hình như lọc các nhiễu một cách triệt để, đưa ra và sử dụng các chiến lược lựa chọn đặc trưng như: loại bỏ các n-gram chứa stop-word, đặt ngưỡng, sử dụng trọng số TF.IDF. 3.3. Quy trình xây dựng bộ phân lớp Các bước xây dựng bộ phân lớp được tiến hành theo một quy trình như sau: Xử lý dữ liệu Dữ liệu huấn luyện Sinh N-gram Xây dựng đặc trưng Lựa chọn đặc trưng Huấn luyện mơ hình Tập trọng số Văn bản mới Văn bản được phân lớp Hình 2. Mơ tả các bước xây dựng bộ phân lớp 3.3.1. Tiền xử lý dữ liệu 3.3.1.1. Lọc nhiễu Tập dữ liệu huấn luyện trong các kĩ thuật học máy giám sát luơn địi hỏi phải được làm sạch trước khi đưa vào huấn luyện. Trên Internet cĩ rất nhiều thơng tin xuất hiện dưới nhiều dạng khác nhau. Loại bỏ đi những thơng tin dưới dạng hình ảnh, âm thanh, quảng cáo, thơng tin khơng nằm trong phần nội dung của trang web, các thẻ html,… được gọi là lọc nhiễu. 20 Làm sạch dữ liệu cho bài tốn phân lớp khơng phải là một việc dễ dàng, và với bài tốn phân lớp nhiều ngơn ngữ thì cịn địi hỏi nhiều cơng sức hơn. Thơng thường ta lấy dữ liệu từ nhiều nguồn, nên mỗi một trang sẽ cĩ một bố cục khác nhau, điều này gây khĩ khăn cho chúng ta khi muốn xây dựng một cơng cụ lọc nhiễu áp dụng cho tất cả các trang web. 3.3.1.2. Cây phân lớp chuẩn Cũng như các mơ hình phân lớp văn bản đơn ngơn ngữ, mơ hình phân lớp văn bản độc lập ngơn ngữ cũng phải xây dựng một cây phân lớp chuẩn. Cây phân lớp chuẩn là tập các lớp mà ta muốn xếp văn bản vào. Với mỗi một ứng dụng cụ thể ta phải xây dựng những cây phân lớp khác nhau. Ví dụ, cây phân lớp cho bộ lọc thư rác là: Spam, non-Spam, Warning; cây phân lớp cho bộ phân lớp lĩnh vực sách giáo khoa: Tốn học, Vật lý, Hố học,… Cây phân lớp phải đảm bảo tính tồn vẹn và tính tách rời. Một văn bản bất kì phải được phân vào một trong các lớp của cây. 3.3.2. Xây dựng đặc trưng Chúng tơi sử dụng mơ hình ngơn ngữ N-gram để xây dựng các mệnh đề thơng tin ngữ cảnh, từ đĩ xây dựng các đặc trưng trước khi đưa vào huấn luyện mơ hình. 3.3.2.1. Mơ hình ngơn ngữ N-gram Xét trong một văn bản, N-gram là một cụm từ gồm N từ liên tiếp cùng xuất hiện trong văn bản đĩ. Nếu độ dài tính theo từ của một văn bản là L, thì số N-gram sinh ra là 2 )1(* +− NLL . Như vậy N càng lớn thì số lượng N-gram sinh ra càng lớn. Qua quá trình thử nghiệm, xây dựng đặc trưng với 1, 2, 3, 4N = và với 1, 2, 3N = chúng tơi nhận thấy với cách sử dụng tối đa 3N = thời gian huấn luyện và thời gian phân lớp nhanh hơn so với cách sử dụng tối đa 4N = , trong khi đo độ chính xác mơ hình là gần như nhau. Vì vậy chúng tơi sử dụng 1, 2, 3N = . 3.3.2.2. Đặc trưng Cĩ được tập hợp các N-gram, ta tiến hành xây dựng các mệnh đề thơng tin ngữ cảnh. Mệnh đề mơ tả thơng tin ngữ cảnh là một mệnh đề chỉ ra văn bản hiện tại chứa một N-gram nào đĩ. Ví dụ, [document has giá_xăng_dầu] 21 Theo cách mà nguyên lý Entropy đã cung cấp để xây dựng đặc trưng: một đặc trưng là sự kết hợp giữa mệnh đề mơ tả thơng tin ngữ cảnh ( )cp x và nhãn của lớp tương ứng với văn bản. Ví dụ, với 'y là lớp “bss” (business) ta cĩ một đặc trưng như sau: ( ) ⎩⎨ ⎧ === 0 ___andif1 ,,___ truedauxanggiahasdocumentbssy yxf bssdauxanggiahasdocument Đặc trưng này sẽ cĩ giá trị đúng nếu văn bản hiện tại chứa cụm từ “giá xăng dầu” và nĩ được gán nhãn “bss”. Cần chú ý rằng, số lượng các mệnh đề thơng tin ngữ cảnh sinh ra nhỏ hơn số lượng các N-gram (vì cĩ những N-gram trùng nhau cũng xuất hiện trong một văn bản), và cũng khơng bằng số lượng các đặc trưng. 3.3.3. Lựa chọn đặc trưng 3.3.3.1. Chiến lược loại bỏ stop-word Bản chất của các ngơn ngữ tự nhiên là luơn cĩ các từ xuất hiện nhiều, nhưng khơng mang nhiều ý nghĩa để phân loại. Trong tiếng Anh gọi đĩ là stop-word. Ngơn ngữ nào cũng cĩ stop-word, tuy nhiên do tiếng Anh được xử lý nhiều nên người ta xây dựng danh sách stop-word cho nĩ khá rõ ràng. Ở một số ngơn ngữ khác, ví dụ như tiếng Việt cũng sẽ cĩ danh sách stop-word cụ thể như tiếng Anh nếu được xử lý nhiều trong tương lai [2]. Stop-word khơng những dư thừa, khi kết hợp với các từ khác để xây dựng đặc trưng chúng cịn gây ra hiện tượng overfitting. Qua thử nghiệm trên một bộ phân lớp văn bản trên tiếng Anh, sau khi lọc stop-word độ chính xác huấn luyện (trainning accuracy) tăng lên đáng kể. Vì vậy loại bỏ stop-word là rất cần thiết. Tuy nhiên, nếu đối với bài tốn phân lớp văn bản trên nhiều ngơn ngữ, loại bỏ stop-word cho văn bản thì nghiễm nhiên các văn bản đã mất đi sự bình đẳng. Nĩi cách khác, các văn bản địi hỏi được nhận dạng ngơn ngữ. Bài tốn phân lớp trong Khĩa luận khơng hướng tới việc nhận dạng ngơn ngữ để loại bỏ stop-word nhưng làm thế nào để loại bỏ chúng. Ở đây, chúng tơi đề xuất một phương pháp khá hiệu quả: vẫn tận dụng được đặc điểm về ngơn ngữ mà vẫn giữ tính độc lập ngơn ngữ của bài tốn. Phương pháp này áp dụng sau khi sinh n-gram, và loại bỏ theo hai quy tắc sau: - Loại bỏ các 1-gram, 2-gram, 3-gram là stop-word: điều này cĩ lợi với các ngơn ngữ mà đơn vị nhỏ nhất khơng phải là từ. Ví dụ, với tiếng Việt đơn vị nhỏ nhất là âm tiết: từ “cĩ_thể” rõ ràng là một stop-word. 22 - Loại bỏ 2-gram, 3-gram mà mỗi gram là một stop-word. Ví dụ, câu “he is in Hanoi” sinh ra 2-gram “is_in” chứa 2 stop-word là “is” và “in”. Qua thực nghiệm mà chúng tơi tiến hành, phương pháp này làm giảm đi 31,7% tổng số đặc trưng so với loại stop-word từ văn bản trước khi sinh n-gram là 33%. Như vậy đây thực sự là chiến lược tốt. 3.3.3.2. Đặt ngưỡng Thực tế cho thấy, cĩ những mệnh đề thơng tin ngữ cảnh xuất hiện nhiều lần trong một văn bản và những mệnh đề thơng tin ngữ cảnh xuất hiện rất ít lần. Ví dụ trong câu “Giá dầu đang ngày một leo thang”: [document has dầu_đang_ngày] Để loại bỏ những mệnh đề thơng tin ngữ cảnh khơng cĩ nhiều ý nghĩa này, chiến lược lọc đặt ngưỡng chỉ đơn giản đặt ngưỡng cho sự xuất hiện của một mệnh đề thơng tin ngữ cảnh trong tồn bộ tập mệnh đề thơng tin ngữ cảnh: nếu số lần xuất hiện nằm ngồi một khoảng nào đĩ thì bị loại bỏ. 3.3.3.3. TF.IDF TF.IDF là một kĩ thuật thống kê đánh giá ý nghĩa, độ quan trọng của một cụm từ đối với một văn bản, hoặc một lớp. TF (term frequency) là độ đo tần số: tần suất xuất hiện của cụm từ trong một văn bản: i kk ntf n = ∑ in là số lần xuất hiện của cụm từ trong tồn bộ văn bản. IDF (inverse document frequency) là độ đo tổng quát độ quan trọng của cụm từ: Trọng số TF.IDF được tính bằng cơng thức: ( ). log j i D tf idf tf d t ⎛ ⎞⎜ ⎟= × ⎜ ⎟⊃⎝ ⎠ trong đĩ, - D: là số các văn bản trong tập dữ liệu huấn luyện. - ( )ij td ⊃ : là số các văn bản mà cụm từ ti xuất hiện thoả mãn in khác 0. 23 Một cụm từ t xuất hiện nhiều lần trong văn bản, và xuất hiện ít lần trong các văn bản khác của tập dữ liệu mẫu thì cĩ trọng số TF.IDF cao. Với tính chất như vậy, TF.IDF cĩ ý nghĩa trong việc lọc bỏ các cụm từ chung. Chúng ta cũng cĩ thể sử dụng phương pháp này để tìm những cụm từ mang ý nghĩa phân lớp cao bằng cách đánh trọng số của từ trên một lớp. 3.3.4. Huấn luyện mơ hình Sau khi đã xây dựng được tập các đặc trưng ta tiến hành huấn luyện mơ hình. Ở bước này chính là lúc áp dụng các thuật tốn ước lượng tham số để tìm ra tập trọng số λ (mỗi một đặc trưng if sẽ được gán một trọng số iλ ). Một văn bản mới cĩ một tập các đặc trưng, chính tập trọng số sẽ quyết định mức độ quan trọng của các đặc trưng và chúng ảnh hưởng trực tiếp đến quá trình phân lớp cho văn bản mới, từ đĩ dự đốn một cách chính xác lớp cho văn bản đĩ. Trong quá trình huấn luyện mơ hình, chúng ta cần tiến hành đánh giá độ chính xác của bộ phân lớp. Nĩi cách khác, trong quá trình này cần đánh giá khả năng đốn nhận của mơ hình thơng qua độ chính xác (accuracy) của quá trình huấn luyện. 3.3.5. Phân lớp văn bản mới Với một văn bản mới, bộ phân lớp sẽ thực hiện tính tốn xác suất trên từng lớp của văn bản. Tổng các giá trị xác suất này bằng 1. Lớp nào cĩ giá trị cao nhất, văn bản sẽ thuộc lớp đĩ. Lớp cho văn bản mới được tính theo cơng thức sau: * argmax ( | ) y y p y xλ= trong đĩ, *y là lớp tương ứng với xác suất ( )xyp |λ cao nhất. Hàm argmax là hàm cực đại đối số, nĩ trả về giá trị của argument (ở đây là y) mà tại đĩ hàm đạt max. Rõ ràng, những đặc trưng quan sát được trong văn bản mới mà khơng cĩ trong mơ hình, tức là khơng quan sát thấy trong tập dữ liệu huấn luyện sẽ nhận giá trị sai, xem như là khơng cĩ vì vậy chúng khơng làm ảnh hưởng đến xác suất của văn bản trên từng lớp. Chỉ những đặc trưng cĩ giá trị là đúng mới cĩ ý nghĩa quan trọng quyết định văn bản đĩ thuộc lớp nào. Thực tế, tính tách rời của cây phân lớp chuẩn khĩ cĩ thể được đảm bảo, vì cĩ rất nhiều văn bản cĩ thể được chia vào nhiều lớp. Trong trường hợp này, chúng ta sẽ sử dụng chiến lược phân đa lớp dựa trên độ lệch chuẩn đã đề xuất tại [1]. 24 3.4. Đánh giá độ chính xác của bộ phân lớp Bên cạnh việc xây dựng một bộ phân lớp hồn chỉnh thì việc đánh giá ước lượng độ chính xác của bộ phân lớp đĩ khơng kém phần quan trọng. Trên cơ sở đĩ mới so sánh được chất lượng của các bộ phân lớp khác nhau (trên cùng một tập dữ liệu thử nghiệm). Đã cĩ rất nhiều các phương pháp ước lượng độ chính xác của một bộ phân lớp, ví dụ như: handout method, ước lượng chéo trên k tập con (k-fold cross validation), hay leave-one-out cross validation,… Trong khố luận, chúng tơi sử dụng phương pháp ước lượng chéo trên k tập con. Ý nghĩa của phương pháp này là để đo độ chính xác của mơ hình trên tồn tập dữ liệu; cĩ nghĩa là đánh giá mức độ thích ứng cũng như sức mạnh phân lớp của mơ hình một cách chính xác hơn, tồn diện hơn. 3.4.1. Các độ đo Độ hồi tưởng, độ chính xác, độ đo F1 là các độ đo cơ bản trong lý thuyết nhận thơng tin (Information Retrival). 2* * num_of_matchprecision num_of_model num_of_matchrecall num_of_manual precision recallF1 precision recall = = = + trong đĩ, - num_of_match: số lượng văn bản trùng hợp mà mơ hình và con người cùng phân lớp vào một lớp nào đĩ. - num_of_model: số lượng văn bản mà mơ hình đã gán cho một lớp nào đĩ. - num_of_manual: số lượng văn bản được con người (gán bằng tay) gán vào một lớp nào đĩ. Độ chính xác mà chúng ta sử dụng để đánh giá mơ hình được tính là số lượng văn bản được phân lớp đúng bởi mơ hình chia cho tổng số lượng văn bản. Vì vậy nếu xét trên tổng thế thì độ chính xác, precision, recall, F1 cĩ cùng giá trị. 25 3.4.2. Áp dụng phương pháp ước lượng chéo trên k tập con Tư tưởng của phương pháp ước lượng chéo trên k tập con là phương pháp đánh giá độ chính xác của hệ thống thơng qua việc tính tốn độ chính xác trung bình trên k tập con. Ưu điểm của phương pháp này là tồn bộ tập dữ liệu huấn luyện đều được lấy làm tập kiểm tra [21]. Trong khố luận, chúng tơi sử dụng k = 10 là giá trị phổ biến để cĩ được một ước lượng chính xác. Hệ thống chia dữ liệu thực nghiệm thành 10 phần bằng nhau một cách ngẫu nhiên. Quá trình huấn luyện được thực hiện 10 lần. Tại lần huấn luyện thứ i ( 0 < i < 10), tập con thứ i được chọn làm tập kiểm tra, 9 tập cịn lại được trộn lại với nhau làm tập huấn luyện. Cũng trong mỗi lần huấn luyện này, sau mỗi bước lặp tập trọng số λ được cập nhật, hệ thống tiến hành phân lớp tập dữ liệu kiểm tra, rồi tính tốn độ chính xác của mơ hình. 3.5. Xây dựng bộ phân lớp trên cây phân lớp thơng minh Phần 3.2 và 3.3 đã trình bày về cách giải quyết khĩ khăn cho bài tốn phân lớp văn bản độc lập ngơn ngữ, và cách xây dựng bộ phân lớp cho bài tốn này. Tuy nhiên, cĩ thể thấy rằng ứng dụng cho bài tốn này là các bài tốn khơng địi hỏi nhận diện ngơn ngữ cho văn bản. Trong thực tế, cĩ thể thấy rất nhiều ứng dụng phân lớp văn bản địi hỏi nhận diện được ngơn ngữ. Ví dụ, bộ phân lớp sách thay cho cơng việc của một thủ thư kho sách điện tử cần xếp sách vào lớp với ngơn ngữ tương ứng, hay các tin bài của các hãng tin lớn cần được xếp vào chuyên mục tin của ngơn ngữ tương ứng. Tuy nhiên nếu sử dụng thêm một bộ nhận dạng ngơn ngữ tốn kém và làm chậm quá trình phân lớp. Xuất phát từ nhu cầu đĩ, và hướng tới các ứng dụng nhỏ khố luận đề xuất xây dựng một bộ phân lớp văn bản độc lập ngơn ngữ trên cây phân lớp thơng minh. Quá trình xây dựng bộ phân lớp này hồn tồn giống với quá trình xây dựng bộ phân lớp trong phần 3.3. Điểm khác duy nhất nằm ở cây phân lớp. Giả sử trong cây phân lớp chuẩn của bộ phân lớp L ngơn ngữ cĩ N lớp, thì ở cây phân lớp thơng minh sẽ cĩ L N× lớp. 26 Bảng 1. Cây phân lớp thơng minh tổng quát STT lang1 lang2 … langL 1 lang1_class1 lang2_class1 … langL_class1 2 lang1_class2 lang2_class3 … langL_class2 … N lang1_classN lang2_classN … langL_classN Bộ phân lớp xây dựng trên cây phân lớp thơng minh, vừa cĩ khả năng phân lớp văn bản, vừa cĩ khả năng nhận dạng văn bản được viết bởi nhưng ngơn ngữ nào. Đây là một ví dụ cây phân lớp thơng minh cho bài tốn phân lớp tác phẩm văn học: giả sử chỉ lấy trên 3 lớp là: Thơ, Truyện, Tuỳ bút đối với 2 ngơn ngữ là tiếng Anh và tiếng Trung. Bảng 2. Bảng ví dụ cho cây phân lớp thơng minh STT Anh Trung Quốc Mơ tả 1 en_po cn_po tác phẩm là thơ 2 en_st cn_st tác phẩm là truyện, truyện ngắn, tiểu thuyết,… 3 en_dl cn_dl tác phẩm là kí sự, tuỳ bút,… 3.5.1. Bản chất bài tốn Xét hai bài tốn phân lớp văn bản trên nhiều ngơn ngữ, và bài tốn nhận dạng ngơn ngữ. Điểm chung giữa hai bài tốn này là đều cĩ thể sử dụng chung một tập dữ liệu chú ý rằng đây khơng phải là tập dữ liệu huấn luyện. Với bài tốn phân lớp thì gán nhãn văn bản theo lớp, bài tốn nhận dạng ngơn ngữ gán nhãn văn bản theo ngơn ngữ. Lợi dụng điều này, ta sẽ gán nhãn văn bản theo cả lớp và ngơn ngữ. Trong ví dụ trên en_po là nhãn cho lớp thơ và ngơn ngữ là tiếng Anh. Như vậy, thực chất nhãn trong cây phân lớp thơng minh là bao gồm nhiều nhãn, cụ thể ở đây là: nhãn lớp (lĩnh vực) và nhãn ngơn ngữ. Chính vì lý do này, chúng tơi gọi cây phân lớp như vậy là cây phân lớp thơng minh. 3.5.2. Phân lớp cho văn bản mới Với một văn bản mới, bộ phân lớp tiến hành phân lớp cho văn bản. Các bước thực hiện giống như việc phân lớp văn bản của bộ phân lớp trên cây phân lớp chuẩn. Nếu văn bản được viết bởi 1 ngơn ngữ, các n-gram sinh ra sẽ mang đặc trưng của ngơn ngữ. Nên sác xuất của văn bản đĩ sẽ cĩ xu hướng nghiêng hẳn về một lớp. Với trường hợp lĩnh vực của văn bản cĩ sự nhập nhằng ta sẽ sử dụng chiến lược phân 27 đa lớp cho văn bản. Nếu văn bản được phân vào lớp en_st tức là văn bản thuộc thể loại Truyện nhưng viết bằng tiếng Anh. Nếu văn bản được phân vào lớp cn_st và cn_dl thì văn bản được phân vào cả hai lớp Truyện và Tuỳ bút nhưng nĩ được viết bằng tiếng Trung. Nếu văn bản được viết bởi nhiều ngơn ngữ, sẽ xuất hiện n-gram sinh ra đặc trưng cho nhiều ngơn ngữ khác nhau. Đến đây là tiếp tục sử dụng chiến lược phân đa lớp để tìm lớp cho văn bản. Nếu văn bản được phân vào hai lớp: en_dl và cn_dl cĩ nghĩa là văn bản thuộc lĩnh vực Tuỳ bút nhưng được viết bởi cả hai ngơn ngữ Anh và Trung. 3.5.3. Nhận xét về phương pháp Thời gian huấn luyện bằng với thời gian huấn luyện của bộ phân lớp văn bản độc lập ngơn ngữ trên cây phân lớp chuẩn. Nhưng thời gian phân lớp thì lâu hơn. Nguyên nhân là do sự kết hợp giữa tập mệnh đề thơng tin ngữ cảnh và số các lớp làm số lượng đặc trưng tăng gấp L lần (số các ngơn ngữ). Do đĩ một lần nữa chúng ta khẳng định lại rằng, bộ phân lớp này phù hợp cho các ứng dụng nhỏ. 3.6. Tổng kết chương Chương này đã xem xét các khía cạnh điển hình về bài tốn phân lớp văn bản độc lập ngơn ngữ cũng như cách xây dựng bộ phân lớp với việc ứng dụng mơ hình Entropy cực đại. Đặc biệt, hai vấn đề nhập nhằng ngơn ngữ và bùng nổ đặc trưng là những khĩ khăn thách thức đối với bài tốn phân lớp văn bản độc lập ngơn ngữ đã được phân tích và giải quyết bằng các phương pháp cụ thể. Khĩa luận đã cĩ một đề xuất lựa chọn đặc trưng rất ý nghĩa là phương pháp loại bỏ stop-word trong n-gram khá hiệu quả. Và cuối cùng một đề xuất cĩ ý nghĩa ứng dụng và tính thực tế cao đĩ là việc xây dựng bộ phân lớp trên cây phân lớp thơng minh. Bộ phân lớp như vậy rất hiệu quả trong việc giải quyết các bài tốn phân lớp văn bản và muốn nhận dạng ngơn ngữ mà khơng cần sử dụng một bộ nhận dạng ngơn ngữ nào khác. Bài tốn này rất phù hợp cho các ứng dụng nhỏ. Chương tiếp theo trình bày các thử nghiệm thực tế các nghiên cứu lý thuyết trên tập dữ liệu cụ thể được lấy từ các hãng tin cho hai ngơn ngữ Anh, Việt và đánh giá kết quả thu được. 28 Chương 4 KẾT QUẢ THỬ NGHIỆM VÀ ĐÁNH GIÁ 4.1. Mơi trường thử nghiệm 4.1.1. Mơi trường phần cứng Bài tốn được thử nghiệm trên máy chủ IBM cĩ cấu hình như sau: Bảng 3. Cấu hình hệ thống chạy thử nghiệm Thành phần Chỉ số CPU 2 Xeon 3.00GHz RAM 4096MB HDD 4 x 36.4 GB OS Debian 3.1 (Sarge) 4.1.2. Cơng cụ phần mềm Tồn tại một số phần mềm nguồn mở đối với bài tốn phân lớp văn bản sử dụng MEM như FlexME, MaxEnt... Chúng tơi chọn lựa cơng cụ mã mở MaxEnt của tác giả Zhang Le tại Centre for Speech Technology Research, University of Edinburgh. Đây là một bộ cơng cụ ứng dụng entropy cực đại viết trên nền Python và C++. Ngồi ra, khố luận sử dụng một số cơng cụ phần mềm hỗ trợ trong quá trình thử nghiệm được mơ tả trong bảng sau: Bảng 4. Danh sách phần mềm sử dụng để thử nghiệm STT Tên phần mềm Nguồn 1 Offline Explorer Enterprise 2 PHP 3 Debian 3.1 Trong quá trình chuẩn bị dữ liệu, đối với mỗi ngơn ngữ tự nhiên, chúng tơi viết một số cơng cụ chạy trên nền Linux và bộ thơng dịch PHP. 29 Bảng 5. Danh sách cơng cụ sử dụng để thử nghiệm STT Tên cơng cụ Mơ tả 1 gethtml.php Thu thập các file HTML trong thư mục lưu trang Web của phần mềm Explorer Offline. 2 html2text.php Cơng cụ lọc nhiễu và chuyển đổi biểu diễn kí tự Unicode (NCR sang UTF-8). Cơng cụ này trích phần tiêu đề và nội dung bài báo. 3 text2ngram.php Cơng cụ sinh n-gram từ các file text do html2text.php sinh ra. Cĩ loại bỏ các từ phổ biến. 4 maketrain.php Cơng cụ tạo file train từ các file n-gram do text2ngram.php sinh ra cĩ gán nhẵn lớp tương ứng. 5 maketest.php Cơng cụ tạo file kiểm tra trực tiếp từ file html bất kì (cĩ loại các thẻ HTML và chuyển đổi biểu diễn kí tự Unicode). 4.2. Dữ liệu kiểm thử Dữ liệu dùng để huấn luyện mơ hình là các tin bài được lấy từ các trang báo điện tử của hai ngơn ngữ Anh và Việt. Đây đều là những hãng tin cĩ uy tín về nội dung tin bài cũng như độ tin cậy của các chuyên mục tin được phân chia. Tiếng Anh: Tiếng Việt: Trong khố luận chúng tơi tiến hành thử nghiệm trên từng bộ phân lớp đơn ngơn ngữ, và trên bộ phân lớp kết hợp ngơn ngữ. 4.2.1. Tiền xử lý dữ liệu Hình 3. Trang tin tức tiếng Việt VnExpress.net 30 Hình 4. Trang tin tức tiếng Anh BBC News Trong hình 3 và hình 4, chúng ta cần lấy phần “Nội dung cần lấy”, các phần cịn lại được gọi là nhiễu và sẽ bị loại bỏ bằng quá trình tiền xử lý trong cơng cụ html2text.php. Mỗi một ngơn ngữ cĩ một cơng cụ html2text.php riêng. Sau khi đã thu được các file text do html2text.php sinh ra, ta tiến hành xây dựng tập dữ liệu huấn luyện theo định dạng mà thư viện MaxEnt hỗ trợ bằng hai cơng cụ sau: text2ngram.php và maketrain.php. Khi đĩ, tệp tin sinh ra chưa dữ liệu huấn luyện theo định dạng được biểu diễn như sau: Trên một dịng, đầu dịng là nhãn của văn bản. Tiếp theo là tất cả các n-gram được sinh ra bởi văn bản đĩ do cơng cụ text2gram.php sinh ra. Cũng trong cơng cụ sinh n-gram từ file text (cơng cụ text2gram.php) chúng tơi tiến hành lọc bỏ các n-gram bằng phương pháp loại bỏ stop-word trong n-gram (giảm được ~32% tổng số n-gram). Điều này đã làm giảm đáng kể các đặc trưng khơng cĩ ích. 4.2.2. Cây phân lớp Quan sát hai hình vẽ trên, ta nhận thấy rõ ràng hai cây phân lớp này khơng giống nhau, và việc để tìm ra một cây phân lớp chung cho chúng khơng dễ dàng. Nĩi như vậy, để khẳng định một điều rằng: tìm cây phân lớp chuẩn cho bài tốn phân lớp văn bản độc lập ngơn ngữ gặp nhiều khĩ khăn. 31 Sau khi quan sát và nghiên cứu các trang tin, chúng tơi đưa ra cây phân lớp tin tức như sau: Bảng 6. Cây phân lớp thơng tin STT Tên Nhãn Mơ tả 1 Kinh tế bss Các nội dung liên quan đến thị trường, kinh doanh,… 2 Giáo dục edu Các nội dung liên quan đến giáo dục. 3 Văn hố / Giải trí ent Các nội dung liên quan đến nghệ thuật, âm nhạc, điện ảnh. 4 Sức khoẻ hel Các nội dung liên quan đến sức khoẻ. 5 Chính trị / Xã hội plt Các nội dung liên quan đến tình hình chính trị, xã hội,… 6 Khoa học sci Các nội dung liên quan đến khoa học. 7 Thể thao spt Các nội dung liên quan đến thể thao 8 Cơng nghệ tec Các nội dung liên quan đến cơng nghệ Ở tập dữ liệu huấn luyện trên từng bộ phân lớp cho một ngơn ngữ, mỗi lớp ta chọn 800 văn bản. Ở tập dữ liệu huấn luyện cho bộ phân lớp hai hoặc ba ngơn ngữ kết hợp, ta chọn mỗi lớp 600 văn bản. 4.3. Kết quả thử nghiệm Tiến hành thử nghiệm trên tập dữ liệu tiếng Anh, tập dữ liệu tiếng Việt và tập dữ liệu trộn lẫn nhau của hai ngơn ngữ Anh và Việt. 4.3.1. Quá trình huấn luyện Thơng tin về tập các thơng tin ngữ cảnh và các đặc trưng đối với cả 3 mơ hình: Bảng 7. Tập dữ liệu huấn luyện của cả 3 mơ hình Mơ hình Mệnh đề thơng tin ngữ cảnh Đặc trưng Tiếng Anh 3.127.333 3.709.185 Tiếng Việt 2.806.899 3.686.768 Anh – Việt 4.743.595 5.860.664 Sau 10 lần huấn luyện trên tập dữ liệu 6207 văn bản tiếng Anh, 6400 văn bản tiếng Việt và 12607 văn bản cho cả hai ngơn ngữ Anh và Việt, độ chính xác được cho trong bảng sau. Mỗi lần huấn luyện ta chỉ lấy kết quả của lần lặp cĩ độ chính xác (accuracy) cao nhất. 32 Bảng 8. Độ chính xác 10 lần huấn luyện của tiếng Anh Fold Highest Log-likelihood Accuracy Time (s) 0 -1.447281E-04 98.55% 117.31 1 -1.435894E-04 98.39% 121.36 2 -1.450561E-04 98.07% 102.54 3 -1.433849E-04 98.87% 109.57 4 -1.425671E-04 98.07% 110.98 5 -1.455252E-04 99.19% 122.17 6 -1.444749E-04 97.90% 143.42 7 -1.450292E-04 99.19% 95.54 8 -1.417561E-04 97.74% 111.57 9 -1.440164E-04 97.26% 114.22 Trung bình -1.440127E-04 98.32% 114.87 Bảng 9. Độ chính xác 10 lần huấn luyện của tiếng Việt Fold Highest Log-likelihood Accuracy Time (s) 0 -3.056967E-04 92.19% 154.26 1 -3.048419E-04 90.31% 157.51 2 -2.988322E-04 92.03% 160.89 3 -2.722667E-04 91.25% 148.85 4 -2.994259E-04 90.63% 146.56 5 -3.022941E-04 91.25% 147.26 6 -3.152480E-04 92.03% 157.12 7 -3.350586E-04 91.88% 150.19 8 -3.773065E-04 91.56% 153.25 9 -2.782285E-04 92.50% 154.72 Trung bình -3.089199E-04 91.56% 153.06 Bảng 10. Độ chính xác 10 lần huấn luyện kết hợp Anh-Việt Fold Highest Log-likelihood Accuracy Time (s) 0 -3.278943E-04 95.21% 193.22 1 -2.680606E-04 96.04% 197.82 2 -3.204758E-04 94.27% 221.17 3 -2.829994E-04 94.06% 183.24 4 -2.668655E-04 94.17% 187.87 5 -3.191257E-04 92.92% 187.89 6 -3.248740E-04 94.90% 184.76 7 -2.815305E-04 94.38% 187.32 8 -2.663499E-04 94.79% 172.98 9 -2.792563E-04 96.25% 195.85 Trung bình -2.937432E-04 94.70% 191.21 33 84.00% 86.00% 88.00% 90.00% 92.00% 94.00% 96.00% 98.00% 100.00% 0 1 2 3 4 5 6 7 8 9 Lần huấn luyện (Fold) Đ ộ ch ín h xá c Tiếng Anh Tiếng Việt Anh - Việt Hình 5. Độ chính xác của 3 bộ phân lớp trong 10 lần huấn luyện Hình 5 là biểu đồ biểu diễn độ chính xác của 3 mơ hình: Anh, Việt, Anh-Việt trên 10 fold. Mỗi fold ta chọn ra độ chính xác ở lần lặp cao nhất của mỗi mơ hình. Các bảng số liệu, đồ thị biểu diễn các kết quả thử nghiệm đã trình bày ở trên cho thấy kết quả thử nghiệm rất khả quan. - Độ chính xác của bộ phân lớp tiếng Anh là: 98.32%. - Độ chính xác của bộ phân lớp tiếng Việt là: 91.56%. - Độ chính xác của bộ phân lớp tiếng Anh-Việt là: 94.70%. Biểu đồ 5 biễu diễn độ chính xác của 3 mơ hình sau 10 lần huấn luyện ta nhận thấy cĩ sự chênh lệch giữa độ chính xác của mơ hình tiếng Anh và mơ hình tiếng Việt, mặc dù tập dữ liệu của tiếng Việt lớn hơn của tiếng Anh (6400 văn bản và 6207 văn bản). Sở dĩ như vậy là vì, tập các đặc trưng của mơ hình phân lớp tiếng Anh được lọc tinh tế hơn của tiếng Việt. Trong quá trình xử lý dữ liệu trước khi đưa vào huấn luyện, chúng tơi sử dụng cơng cụ text2ngram.php và làm giảm được 32% tổng số đặc trưng cho mơ hình phân lớp tiếng Anh, và giảm 6% tổng số đặc trưng cho mơ hình phân lớp tiếng Việt. Vì vậy, từ kết quả hai bộ phân lớp trên hai ngơn ngữ Anh và Việt chúng ta cĩ kết luận như sau: - Khẳng định tính đúng đắn của kết luận trong lý thuyết rằng đặc trưng được chọn lọc càng tinh tế thì độ chính xác càng tăng. - Sử dụng phương pháp lọc bỏ stop word đã đề xuất ở phần lý thuyết cho kết quả tốt. Do tiếng Anh được xử lý nhiều nên danh sách stop word khá đầy đủ, việc lọc bỏ sẽ dễ dàng và đạt hiệu quả cao. Trong khố luận chúng tơi 34 đưa ra thống kê chưa đầy đủ các stop word trong tiếng Việt nên kết quả cĩ phần hạn chế. Cũng trên hình 5, chúng ta cĩ sự so sánh độ chính xác giữa 3 mơ hình: Anh, Việt và Anh-Việt. Độ chính xác của mơ hình Anh-Việt luơn nằm giữa hai độ chính xác của mơ hình tiếng Anh và mơ hình tiếng Việt. Rõ ràng sự nhập nhằng của hai ngơn ngữ Anh và Việt khơng ảnh hưởng nhiều đến độ chính xác của mơ hình Anh-Việt. Và kết quả của mơ hình này cho thấy rõ điều đĩ: 94.70%. Quan sát các bảng 8, 9 và 10, ta dễ dàng nhận thấy thời gian huấn luyện rất nhanh. Trung bình một lần huấn luyện trên bộ phân lớp văn bản tiếng Anh là 114.87 (s). Đến đây ta khẳng định sức mạnh của phương pháp entropy cực đại bằng kết quả của các con số: tích hợp gần 6 triệu đặc trưng vào mơ hình và chỉ huấn luyện trong 32 phút (mơ hình Anh-Việt). 4.3.2. Lần lặp cho độ chính xác cao nhất 0.00% 20.00% 40.00% 60.00% 80.00% 100.00% 120.00% 0 5 10 15 20 25 30 Bước lặp Đ ộ ch ín h xá c Tiếng Anh Tiếng Việt Anh-Việt Hình 6. Sự phụ thuộc độ chính xác theo bước lặp của cả 3 mơ hình Hình vẽ trên biểu diễn sự phụ thuộc độ chính xác theo bước lặp của cả 3 mơ hình. Số liệu dùng để vẽ đồ thị được lấy từ thơng số của lần huấn luyên cĩ độ chính xác cao nhất tại mỗi mơ hình. Từ đồ thị trên ta cĩ nhận xét rằng tốc độ tăng của độ chính xác tại mỗi bước lặp là khơng đều nhau. Điều này cĩ thể lý giải được bằng hiện tượng overfitting. Tức là, ngay trên chính tập dữ liệu huấn luyện, những đặc trưng xuất hiện trong 1 phần kiểm tra khơng xuất hiện trong tập dữ liệu học của 9 phần sẽ khơng được nhận biết. 35 4.3.3. Kết quả kiểm tra trên dữ liệu mới Tập dữ liệu kiểm tra bao gồm 400 văn bản tiếng Anh, 400 văn bản tiếng Việt được lấy từ nhiều nguồn. Number of Predicates: 4743595 Number of Parameters: 5860664 Optimized version iter loglikelihood training accuracy heldout accuracy ================================================================== 0 -2.079442E+00 12.500% 12.500% 1 -1.566180E+00 67.656% 44.250% 2 -9.132070E-01 84.167% 59.750% 3 -7.543474E-01 87.490% 66.625% 4 -5.646942E-01 91.479% 71.875% 5 -4.754881E-01 92.323% 74.500% 6 -3.445148E-01 93.906% 81.250% 7 -2.715653E-01 94.385% 80.875% 8 -1.921838E-01 95.823% 82.750% 9 -1.628873E-01 96.448% 83.125% 10 -1.205699E-01 97.260% 83.625% 11 -9.134130E-02 97.781% 85.500% 12 -7.489992E-02 98.240% 85.750% 13 -5.539846E-02 98.740% 85.625% 14 -2.927394E-02 99.365% 85.250% 15 -1.338378E-02 99.698% 85.625% 16 -6.036523E-03 99.896% 85.250% 17 -4.328826E-03 99.938% 85.250% 18 -1.414540E-03 100.000% 84.875% 19 -9.727452E-04 100.000% 84.875% 20 -7.786723E-04 100.000% 85.000% 21 -5.644801E-04 100.000% 84.500% 22 -4.865722E-04 100.000% 84.375% 23 -4.318329E-04 100.000% 84.125% 24 -4.265314E-04 100.000% 84.125% 25 -4.217743E-04 100.000% 84.125% 26 -4.120439E-04 100.000% 84.125% 27 -3.779965E-04 100.000% 83.875% 27 -3.889546E-04 100.000% 83.625% 28 -3.629248E-04 100.000% 83.750% 29 -3.607414E-04 100.000% 83.875% 30 -3.365570E-04 100.000% 83.875% Maximum numbers of 30 iterations reached in 199.81 seconds Highest log-likelihood: -3.365570E-04 Accuracy: 83.875% Hình 7. Kết quả kiểm tra bộ dữ liệu độc lập Anh-Việt Đây là kết quả xuất ra của quá trình kiểm tra mơ hình Anh-Việt trên nguồn dữ liệu hồn tồn mới. Kết quả nhận được là: 83.875%. Kết quả này rất cĩ ý nghĩa, nĩ thể hiện sức mạnh thực sự của mơ hình, nĩ nĩi lên khả năng đốn nhận của mơ hình với dữ liệu mới. Cột log likelihood là giá trị của hàm log likelihood tại lần lặp hiện tại. Cột training accuracy là độ chính xác huấn luyện được tính bằng độ chính xác (precision). 36 Trong quá trình thử nghiệm trên nhiều tập kiểm tra, kết quả thực nghiệm cho thấy rằng một mơ hình cĩ mạnh hay khơng cịn phụ thuộc vào nguồn dữ liệu huấn luyện. Dữ liệu huấn luyện được thu thập càng phong phú, khả năng đốn nhận của mơ hình với dữ liệu mới càng tăng. Chúng tơi đã tiến hành thử nghiệm mơ hình tiếng Anh trên hai tập kiểm tra. Một tập được lấy từ các nguồn tin bài rất lạ, là các trang tin bài của Mỹ (New York Times, Washington Post,…) và một tập là trên các trang tin của Anh (Guaridan Unlimited). Kết quả test tương ứng là 52.23% và 96.75%. Cĩ sự chênh lệch này là do tập dữ liệu huấn luyện của mơ hình tiếng Anh khơng đủ phong phú để cho phép mơ hình đốn nhận dữ liệu “lạ”. Vì vậy chúng ta cĩ kết luận rằng muốn xây dựng một bộ phân lớp cĩ khả năng đốn nhận một cách tồn diện phải xây dựng một tập dữ liệu huấn luyện đủ lớn, đủ phong phú. 4.4. Tổng kết chương Trong chương này chúng ta đã xem xét những kết quả của quá trình huấn luyện và kiểm tra mơ hình phân lớp tài liệu web ứng dụng mơ hình entropy cực đại. Tập dữ liệu huấn luyện của mơ hình được xây dựng cơng phu từ 6207 văn bản tiếng Anh và 6400 văn bản tiếng Việt. Chúng ta cũng đã xem xét những đánh giá về kết quả thực nghiệm và đưa ra những kết luận khẳng định mạnh mẽ hơn tính đúng đắn cho những nghiên cứu lý thuyết ở ba chương trước. Qua kết quả thử nghiệm và những đánh giá đĩ chúng ta nhận thấy rằng với khả năng đốn nhận lên tới 94.70%, bài tốn phân lớp văn bản độc lập ngơn ngữ nĩi chung và bài tốn phân lớp tài liệu web độc lập ngơn ngữ nĩi riêng rất cĩ triển vọng áp dụng vào các ứng dụng trong tương lai. 37 KẾT LUẬN Khố luận đã tìm hiểu và nghiên cứu về bài tốn phân lớp văn bản độc lập ngơn ngữ. Các vấn đề cơ bản của bài tốn đã được trình bày, phân tích và đưa ra các hướng giải quyết cụ thể. Khố luận đã sử dụng tiếp cận entropy cực đại là một phương pháp rất phù hợp với những bài tốn cĩ số lượng đặc trưng lớn như bài tốn phân lớp văn bản nĩi chung và bài tốn phân lớp văn bản độc lập ngơn ngữ nĩi riêng. Những kết quả chính mà khố luận đạt được: - Đề xuất xây dựng một bộ phân lớp văn bản cho nhiều ngơn ngữ mà khơng cần nhận biết ngơn ngữ sử dụng phương pháp entropy cực đại. - Phân tích và đưa ra các phương pháp nhằm khắc phục hai vấn đề cơ bản của bài tốn phân lớp văn bản độc lâp ngơn ngữ: sự nhập nhằng ngơn ngữ và sự bùng nổ đặc trưng. - Đưa ra một phương pháp lựa chọn đặc trưng một cách khá hiệu quả. - Đề xuất xây dựng bộ phân lớp trên cây phân lớp thơng minh với khả năng nhận diện ngơn ngữ và phân lớp cho các ứng dụng vừa và nhỏ. - Kiểm thử trên một tập dữ liệu lớn của hai ngơn ngữ Anh và Việt, và đã cho kết quả khả quan. Kết quả thực nghiệm trên tập dữ liệu trộn văn bản của hai ngơn ngữ Anh và Việt cho thấy rất khả quan và cĩ nhiều triển vọng ứng dụng thực tế cao với độ chính xác huấn luyện lên tới xấp xỉ 95%. Do khuơn khổ cĩ hạn về thời gian cũng như lượng kiến thức cĩ được và gặp khĩ khăn trong quá trình thu thập dữ liệu thử nghiệm nên cịn một số vấn đề mà khố luận phải tiếp tục hồn thiện và phát triển trong thời gian tới: - Thử nghiệm trên một tập dữ liệu lớn hồn chỉnh, phong phú về ngơn ngữ. - Xây dựng các phương pháp hiệu quả hơn trong việc khắc phục vấn đề bùng nổ đặc trưng: ví dụ như trừu tượng hố dữ liệu là số và ngày tháng. Tích hợp mơ hình vào mơ-đun bộ lọc nội dung và mơ-đun phân lớp của máy tìm kiếm Vinahoo. 38 Phụ lục DANH SÁCH STOP-WORD Danh sách các stop word của tiếng Anh cĩ trong [23]: a's able about above according accordingly across actually after afterwards again against ain't all allow allows almost alone along already also although always am among amongst an and another any anybody anyhow anyone anything anyway anyways anywhere apart appear appreciate appropriate are aren't around as aside ask asking associated at available away awfully be became because become becomes becoming been before beforehand behind being believe below beside besides best better between beyond both brief but by c'mon c's came can can't cannot cant cause causes certain certainly changes clearly co com come comes concerning consequently consider considering contain containing contains corresponding could couldn't course currently definitely described despite did didn't different do does doesn't doing don't done down downwards during each edu eg eight either else elsewhere enough entirely especially et etc even ever every everybody everyone everything everywhere ex exactly example except far few fifth first five followed following follows for former formerly forth four from further furthermore get gets getting given gives go goes going gone got gotten greetings had hadn't happens hardly has hasn't have haven't having he he's hello help hence her here here's hereafter hereby herein hereupon hers herself hi him himself his hither hopefully how howbeit however i'd i'll 39 i'm i've ie if ignored immediate in inasmuch inc indeed indicate indicated indicates inner insofar instead into inward is isn't it it'd it'll it's its itself just keep keeps kept know knows known last lately later latter latterly least less lest let let's like liked likely little look looking looks ltd mainly many may maybe me mean meanwhile merely might more moreover most mostly much must my myself name namely nd near nearly necessary need needs neither never nevertheless new next nine no nobody non none noone nor normally not nothing novel now nowhere obviously of off often oh ok okay old on once one ones only onto or other others otherwise ought our ours ourselves out outside over overall own particular particularly per perhaps placed please plus possible presumably probably provides que quite qv rather rd re really reasonably regarding regardless regards relatively respectively right said same saw say saying says second secondly see seeing seem seemed seeming seems seen self selves sensible sent serious seriously seven several shall she should shouldn't since six so some somebody somehow someone something sometime sometimes somewhat somewhere soon sorry specified specify specifying still sub such sup sure t's take taken tell tends th than thank thanks thanx that that's thats the their theirs them themselves then thence there there's thereafter thereby therefore therein theres thereupon these they they'd they'll they're they've think third this thorough thoroughly those though three through throughout thru 40 thus to together too took toward towards tried tries truly try trying twice two un under unfortunately unless unlikely until unto up upon us use used useful uses using usually value various very via viz vs want wants was wasn't way we we'd we'll we're we've welcome well went were weren't what what's whatever when whence whenever where where's whereafter whereas whereby wherein whereupon wherever whether which while whither who who's whoever whole whom whose why will willing wish with within without won't wonder would would wouldn't yes yet you you'd you'll you're you've your yours yourself yourselves zero Danh sách stop word của tiếng Việt được thống kê trong [2]: và cịn hay hoặc khơng khơng những khơng chỉ mà cịn nếu thì nên hễ tuy nhưng vả lại giá vì bởi tại do song dầu mặc dầu dù dẫu dẫu cho chẳng lẽ làm như thế mà vậy mà cĩ điều hơn nữa huống hồ huống gì huống nữa ngay cũng chính cả 41 TÀI LIỆU THAM KHẢO [1] Nguyễn Việt Cường, Bài tốn lọc và phân lớp tài liệu Web tiếng Việt với hướng tiếp cận entropy cực đại, Luận văn tốt nghiệp đại học, Trường Đại học Cơng nghệ, Đại học Quốc gia Hà Nội, 2005. [2] Nguyễn Đức Dân, Lơ gich ngữ nghĩa cú pháp, NXB ĐH&TH chuyên nghiệp, Hà Nội, 1987. [3] Nguyễn Cẩm Tú, Nhận biết các loại thực thể trong văn bản tiếng Việt nhằm hỗ trợ Web ngữ nghĩa và tìm kiếm hướng thực thể, Luận văn tốt nghiệp đại học, Trường Đại học Cơng nghệ, Đại học Quốc gia Hà Nội, 2005. [4] Berger, A., Della Pietra, S., and Della Pietra, V. A maximum entropy approach to natural language processing. Computational Linguistics, volume 22, number 1, 1996, pages 39-71. [5] Cavnar, W. B. and Trenkle, J. M. N-Gram-Based Text Categorization. Proceedings of {SDAIR}-94, 3rd Annual Symposium on Document Analysis and Information Retrieval, 1994, pages 161-175. [6] Darroch, J. and Ratcliff, D. Generalized iterative scaling for log-linear models. Annals Mathematical Statistics, volume 43, number 5, 1972, pages 1470–1480. [7] Fuchen, P., Dale, S. and Shaojun, W. Language and Task independent text categorizationg with simple language models, Proceedings of HLT-NAACL, 2003 [8] Jaynes, E. R. (1957). Information Theory and Statistical Mechanics. Physic Review, volume 106, 1957, pages 620-630. [9] Joachims, T. Text Classification with Support Vector Machines: Learning with many relevant features. Machine Learning: ECML-98, Tenth European Conference on Machine Learning, 1998, pages 137-142. [10] Liu, D. C. and Nocedal J. On the limited memory BFGS method for large scale optimization. Mathematical Programming, volume 45, number 3, 1989, pages 503-528. 42 [11] Malouf, R. A comparison of algorithms for maximum entropy parameter estimation. Proceedings of the Sixth Conference on Natural Language Learning (CoNLL-2002), 2002, pages 183-186. [12] Nigam, K., Lafferty, J. and McCallum, A. Using maximum entropy for text classification. IJCAI-99 Workshop on Machine Learning for Information Filtering, 1999, pages 61-67. [13] Nigam K., McCallum, A., Thrun S. and Mitchell, T. Text Classification from Labeled and Unlabeled Documents using EM. Machine Learning, volume 39, number 2/3, 2000, pages 103-134. [14] Ratnaparkhi, A. A Maximum Entropy Part-Of-Speech Tagger. Proceedings of the Empirical Methods in Natural Language Processing Conference, May 17-18, 1996. [15] Ratnaparkhi, A. A simple introduction to maximum entropy models for natural language processing. Technical Report 97-08, Institute for Research in Cognitive Science, University of Pennsylvania, 1997. [16] Ratnaparkhi, A. Maximum Entropy Models for Natural Language Ambiguity Resolution. Ph.D. thesis, University of Pennsylvania, Philadelphia, PA, 1998. [17] Rosenfeld, R. A maximum entropy approach to adaptive statistical language modeling. Computer, Speech, and Language, volume 10, 1996, pages 187-228. [18] Zhang, L., Maximum Entropy Modeling Toolkit for Python and C++, 2004. [19] Website: [20] Website: [21] Website: [22] Website: [23] Website: