1.1 Đặt vấn đề Trong thời đại bùng nổ công nghệ thông tin hiện nay, các tài liệu giấy dần được số hóa thành các dạng tài liệu được lưu trữ trên máy tính thay thế cho những tài liệu giấy cồng kềnh. Tài liệu số với những ưu điểm gọn nhẹ, dễ bảo quản, lưu trữ được lâu, dễ dàng chia sẻ với bạn bè, có thể sửa đổi. đã ngày càng trở nên phổ biến và tiện dụng. Vì vậy mà số lượng tài liệu số tăng nhanh đến chóng mặt. Với ¬¬¬¬một khối lượng lớn các tài liệu số như vậy, làm cách nào chúng ta có thể lọc ra được những tài liệu thực sự cần thiết cho một mục đích nào đó của chúng ta? Câu trả lời đó là phân loại văn bản tự động! Một chương trình có thể tự động phân loại văn bản theo các chủ đề cụ thể. Khi đó sẽ giúp chúng ta giới hạn được nội dung của tài liệu theo đúng mục đích sử dụng. Với một khối lượng khổng lồ các tài liệu số. Thì việc phân loại văn bản tự động sẽ giúp chúng ta tiết kiệm được rất nhiều thời gian và công sức tìm kiếm. Theo Yang & Xiu (1999), “Việc phân loại văn bản tự động là việc gán các nhãn phân loại lên một văn bản mới dựa trên mức độ tương tự của văn bản đó so với các văn bản đã được gán nhãn trong tập huấn luyện”. Dựa trên thống kê của Yang & Xiu và các tài liệu khác, một số phương pháp phân loại thông dụng hiện nay là: Naïve Bayes [Baker & Mccallum, 2000], k-Nearest Neighbor [Yang, 1994], Linear Least Squares Fit [Yang & Chute, 1994], Support Vector Machine [Joachims, 1998] , 1998], Maximum Entropy [Berger, 1996 và Della Pietra, 1997]. Các phương pháp đều dựa vào xác suất thống kê hoặc thông tin về trọng số của từ trong văn bản. Chi tiết về các phương pháp sẽ được trình bày trong chương 2. Trong phân loại văn bản tiếng Anh, kết quả phân loại là rất khả quan. Còn đối với tiếng Việt vẫn còn nhiều hạn chế. Hạn chế về mặt ngôn ngữ: Tiếng Anh định nghĩa từ là một tập hợp các ký tự có nghĩa và chúng được tách biệt với nhau bởi khoảng trắng. Ví dụ: this, house, wonderland, pacific. Do đó việc tách từ đối với tiếng Anh là rất đơn giản. Tuy nhiên, với tiếng Việt thì việc xác định các từ trở nên khó khăn hơn. Các từ không phải được xác định dựa vào khoảng trắng mà nó phụ thuộc vào ngữ cảnh. Ví dụ các từ sau: “thế giới”, “tiền”, “chiến binh”, “quyển sách”. Hạn chế về tập dữ liệu huấn luyện và kiểm thử chuẩn. Tuy nhiên cũng đã có nhiều nhà nghiên cứu trong lĩnh vực này và đạt được những kết quả ban đầu như [Huỳnh Quyết Thắng và Đinh Thị Phương, 1999], [Nguyễn Linh Giang và Nguyễn Mạnh Hiển, 2005]. Các hướng tiếp cận bao gồm: lý thuyết đồ thị [Đỗ Bích Diệp, 2004], sử dụng lý thuyết tập thô [Nguyễn Ngọc Bình, 2004], thống kê [Nguyễn Linh Giang và Nguyễn Duy Hải, 1999], học không giám sát và đánh chỉ mục [Huỳnh Quyết Thắng và Đinh Thị Phương, 1999]. Luận văn là một đóng góp tiếp tục trong việc nghiên cứu lý thuyết và phát triển các hệ thống thực nghiệm cho việc phân loại văn bản tiếng Việt. Phương pháp phân loại được nghiên cứu trong luận văn là mô hình cực đại entropy [Berger, 1996 và Della Pietra, 1997]. 1.2 Giới thiệu mô hình cực đại entropy Mô hình cực đại entropy là phương pháp phân loại văn bản được sử dụng rộng rãi trong nhiều lĩnh vực của xử lý ngôn ngữ tự nhiên như: ngôn ngữ mô hình hóa [Chen và Rosenfeld, 1999], gán nhãn từ loại [Ratnaparkhi, 1996], phân loại văn bản [Beeferman, 1999]. Mô hình cực đại entropy là kỹ thuật dùng để đánh giá phân phối xác suất của dữ liệu văn bản. Tư tưởng chính của phương pháp là những gì chưa biết hoặc không rõ ràng thì không có bất kỳ giả định gì (cực đại hóa độ hỗn loạn). Tức là áp đặt một phân phối đều lên các sự kiện chưa biết. Dữ liệu đã được gán nhãn được sử dụng để lấy ra tập các ràng buộc cho mô hình mà nó mô tả đặc điểm riêng cho từng lớp cụ thể có thể được gán cho văn bản cần phân lớp. Cuối cùng, thuật toán IIS sẽ tìm ra phân phối mà nó thỏa mãn các ràng buộc đã đưa ra và thỏa mãn cực đại entropy với phân phối xác suất là đều nhất. Để có thể áp dụng được thật toán IIS trên văn bản cần phân lớp. Bước đầu tiên cần phải thực hiện là chuyển văn bản đang ở dạng chuỗi các ký tự thành các vector đặc trưng. Một yếu tố trong quá trình huấn luyện của mô hình cực đại entropy chính là việc lựa chọn các vector đặc trưng cho từng lớp. Các vector đặc trưng này phải miêu tả được đầy đủ nhất tính riêng biệt của từng lớp và phải có khả năng phân loại giữa các lớp với nhau. Mô hình cực đại entropy có được tối ưu hay không là phụ thuộc rất nhiều vào việc lựa chọn này. Ưu điểm lớn nhất của mô hình cực đại entropy là tính mềm dẻo của mô hình: nó cung cấp một hệ thống các quy luật có tính thống kê ngẫu nhiên để bổ sung các cú pháp, ngữ nghĩa và căn cứ vào các vector đặc trưng. Tuy nhiên, mô hình cực đại entropy đòi hỏi một chi phí khá lớn cho việc tính toán để ước lượng chính xác các tham số của mô hình. Trong khi đó mô hình có hàng trăm hàng ngàn thông số. Tuy nhiên, với khả năng mạnh mẽ của máy tính hiện nay thì đó không hẳn là vấn đề. Hiện tại có khá nhiều các thuật toán dùng để ước lượng các thám số như: Generalized Iterative Scaling (GIS) và Improved Iterative Scaling (IIS), cũng như Igradient ascent, conjugate gradient. Trong luận văn này sử dụng thuật toán IIS. 1.3 Mục tiêu của luận văn Nguyên cứu một số phương pháp phân loại văn bản tiếng Anh như: Naïve Bayes [Baker & Mccallum, 2000], k-Nearest Neighbor [Yang, 1994], Linear Least Squares Fit [Yang & Chute, 1994], Support Vector Machine [Joachims, 1998] , 1998], mô hình cực đại Entropy [Berger, 1996 và Della Pietra, 1997]. Từ những phương pháp đó, lựa chọn phương pháp áp dụng cho phân loại văn bản tiếng Việt. Phương pháp phân loại văn bản tiếng Việt được sử dụng trong luận văn là mô hình cực đại Entropy [Berger, 1996 và Della Pietra, 1997]. Phần lý thuyết của mô hình trình bày về cách biểu diễn của dữ liệu huấn luyện. Các khái niệm về thống kê, đặc trưng và ràng buộc. Nguyên lý hoạt động của mô hình cực đại entropy. Tham số hình thức và cách tính toán các tham số đó. Ý nghĩa và cơ sở của việc lựa chọn các đặc trưng sao cho hiệu quả nhất. Từ đó áp dụng lý thuyết vào bài toán phân loại văn bản tiếng Việt và ứng dụng chặn nội dung web trên cơ sở phân loại nội dung trang web (dựa vào bài toán phân loại văn bản). Để hiểu sâu sắc thuật toán, luận văn đề ra mục tiêu xây dựng từ đầu thuật toán mô hình cực đại entropy (chương trình phân loại văn bản tiếng Việt) cũng như ứng dụng chặn nội dung web. Trong đó, chương trình phân loại văn bản tiếng Việt sẽ có đầy đủ các chức năng như: huấn luyện, kiểm thử và gán nhãn. Với ứng dụng chặn nội dung web. Do giới hạn về mặt thời gian và điều kiện nên luận văn mới chỉ dừng lại ở mức: phân tích những địa chỉ url mà người dùng nhập vào trình duyệt Internet Explorer rồi đưa ra quyết định nên chặn hay cho phép người dùng truy cập vào trang web đó. Mục đích cuối cùng là hướng tới xây dựng chương trình có khả năng ngăn chặn những trang web có nội dung xấu và giúp người dùng phân loại nội dung của các trang web với các chủ đề khác nhau. Việc phân loại giúp người dùng tìm kiếm thông tin dễ dàng và nhanh chóng hơn. Và cũng giúp tránh được những trang web với nội dung không phù hợp.