Khóa luận Mô hình maximum entropy và ứng dụng - Trần Quang Dũng

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CƠNG NGHỆ Trần Quang Dũng MƠ HÌNH MAXIMUM ENTROPY VÀ ỨNG DỤNG KHỐ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Cơng Nghệ Thơng Tin HÀ NỘI - 2010 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CƠNG NGHỆ Trần Quang Dũng MƠ HÌNH MAXIMUM ENTROPY VÀ ỨNG DỤ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: Lê Anh Cường HÀ NỘI - 2010 TĨM TẮT NỘI DUNG Trong những năm gần đây, với sự phát triển mạnh mẽ của cơng nghệ thơng tin và nhu cầu sử dụng Internet của tất cả mọi người trên thế giới đã làm tăng vọt lượng thơng tin giao dịch trên Internet. Vì vậy mà số lượng văn bản xuất hiện trên Internet tăng nhanh chĩng mặt cả về số lượng và chủ đề. Với khối lượng thơng tin đồ sộ như vậy, để tìm được những thơng tin cần thiết cho mục đích của chúng ta sẽ mất rất nhiều thời gian và cơng sức. Một câu hỏi được đặt ra, làm thế nào cĩ thể tổ chức và tìm kiếm thơng tin một cách nhanh chĩng và hiệu quả nhất? Và câu trả lời hợp lý cho câu hỏi trên là phân loại thơng tin tự động bằng máy tính. Trong luận văn này, em tập trung tìm hiểu về mơ hình cực đại entropy và áp dụng mơ hình để xây dựng chương trình phân loại văn bản Tiếng Việt tự động dựa trên tập dữ liệu huấn luyện. Từ đĩ hướng tới việc xây dựng chương trình chặn nội dung web bằng việc phân tích nội dung web. Hiện nay, việc kiểm sốt truy cập Internet vẫn chưa đạt được hiệu quả tốt. Những trang web với nội dung xấu vẫn được truy cập rất dễ dàng mà khơng cĩ bất kỳ sự kiểm sốt nào. Với chương trình chặn nội dung web, em hy vọng cĩ thể giúp ngăn chặn được những trang web cĩ nội dung xấu. Bên cạnh đĩ, cũng giúp mọi người cĩ thể lọc ra được những trang web cĩ nội dung phù hợp với nhu cầu của từng người trong những lĩnh vực riêng biệt. LỜI CẢM ƠN Em xin gửi lời cảm ơn chân thành và sâu sắc nhất tới Thầy LÊ ANH CƯỜNG đã tận tụy hướng dẫn, động viên, giúp đỡ em trong suốt thời gian thực hiện đề tài. Em xin chân thành cảm ơn quý Thầy Cơ trong khoa Cơng Nghệ Thơng Tin đã truyền đạt những kiến thức quý báu cho chúng em trong những năm học vừa qua. Chúng con xin nĩi lên lịng biết ơn đối với Ơng Bà, Cha Mẹ luơn là nguồn động viên, chăm sĩc trên bước đường học vấn của chúng con. Xin chân thành cảm ơn các anh chị và bạn bè đã ủng hộ, giúp đỡ và động viên chúng em trong thời gian học tập và nghiên cứu. Mặc dù em đã cố gắng hồn thành luận văn trong phạm vi và khả năng cho phép nhưng chắc chắn sẽ khơng tránh khỏi những thiếu sĩt. Em kính mong nhận được sự cảm thơng và tận tình chỉ bảo của quý Thầy Cơ và các bạn. Hà nội, 06/2010 Sinh viên thực hiện, Trần Quang Dũng Mục lục Danh sách hình Hình 2.1: Các điểm được khoanh trịn là các vector hỗ trợ....................................10 Hình 3.1: Lựa chọn đặc trưng..................................................................................24 Hình 3.2 log-likelihood được biểu diễn như hàm lồi 2 tham số............................28 Hình 4.1: Giao diện chức năng huấn luyện..............................................................34 Hình 4.2: Giao diện chức năng kiểm thử.................................................................36 Hình 4.3: Giao diện chức năng gán nhãn.................................................................37 Hình 4.4: Giao diện giới thiệu..................................................................................38 Hình 4.5: Giao diện chặn nội dung web...................................................................41 Hình 4.6: Cửa sổ setting...........................................................................................42 Hình 4.7: Cửa sổ giới thiệu......................................................................................43 Danh sách bảng Bảng 4.1: Số lượng file của dữ liệu huấn luyện......................................................29 Bảng 4.2: Số lượng file của dữ liệu kiểm thử.........................................................30 Bảng 4.3: Mơ tả giao diện huấn luyện....................................................................35 Bảng 4.4: Kết quả huấn luyện.................................................................................35 Bảng 4.5: Mơ tả chức năng kiểm thử......................................................................36 Bảng 4.6: Kết quả kiểm thử....................................................................................37 Bảng 4.7: Kết quả gán nhãn....................................................................................38 Bảng 4.8: Chức năng giao diện chặn nội dung web...............................................42 Chương 1: Tổng quát Đặ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à: Nạ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]. 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 tố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 tố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 tố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 tố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 tốn IIS. 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ư: Nạ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 tố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 tố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 tốn phân loại văn bản). Để hiểu sâu sắc thuật tốn, luận văn đề ra mục tiêu xây dựng từ đầu thuật tố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. Chương 2: Các phương pháp phân loại văn bản 2.1 Cái nhìn tổng quát về các phương pháp phân loại văn bản Để phân loại văn bản người ta sử dụng nhiều cách tiếp cận khác nhau như dựa trên từ khĩa, dựa trên ngữ nghĩa các từ cĩ tần số xuất hiện cao, mơ hình cực đại entropy [Berger, 1996 và Della Pietra, 1997], tập thơ.... Tiếng Anh là ngơn ngữ được nghiên cứu sớm nhất và đạt được kết quả tốt. Rất nhiều phương pháp đã được áp dụng như: mơ hình hồi quy [Fuhr, 1991], k-nearest neighbors [Dasarathy, 1991], Nạve Bayes [Joachims, 1997], cây quyết định [Fuhr, 1991], học luật quy nạp [William & Yorm, 1996], Support vector Machine [Vapnik, 1995], mơ hình cực đại entropy [Berger, 1996 và Della Pietra, 1997]. Hiệu quả của các phương pháp là rất khác nhau. Việc đánh giá gặp nhiều khĩ khăn do thiếu các tập dữ liệu huấn luyện chuẩn. 2.2 Mơ tả bài tốn phân loại văn bản Cho văn bản cần phân loại và các chủ đề, cần dự đốn văn bản đĩ thuộc vào chủ đề nào trong số các chủ đề đã cho. Gọi X là tập các văn bản cần phân loại và Y là tập các chủ đề cĩ thể được gán cho các văn bản. Khi đĩ ta cần phải chi ra một văn bản x Ỵ X thuộc vào chủ đề y Ỵ Y nào. Trong đĩ, x bao gồm các từ, cụm từ, câu được dùng cho nhiệm vụ phân loại. Để rõ hơn ta xét ví dụ gồm 6 lớp cĩ thể được phân loại: kinh doanh, pháp luật, thể thao, văn hĩa, vi tính, xã hội. Và chúng ta cĩ ràng buộc, nếu một văn bản cĩ từ “bĩng đá” xuất hiện thì khả năng văn bản đĩ thuộc vào lớp “thể thao” là 30% và 70% là khả năng mà văn bản đĩ thược vào 5 lớp cịn lại. Với ví dụ này thì chúng ta cĩ thể dễ dàng tính được. Nhưng thực tế thì khơng phải chỉ một vài ràng buộc đơn giản như vậy, mà là hàng trăm hàng nghìn ràng buộc phức tạp hơn nhiều. Vì vậy, nhiệm vụ đầu tiên cần phải làm là biểu diễn văn bản dưới dạng các từ, cụm từ và các câu cĩ chọn lọc. Lọc bỏ những từ, cụm từ và câu khơng cĩ nghĩa hay khơng cĩ tác động tích cực tới việc phân loại. Bước tiếp theo là xác định các ràng buộc cho bài tốn phân loại. Các ràng buộc này sẽ được lấy ra từ tập dữ liệu huấn luyện. Mỗi ràng buộc thể hiện một đặc trưng của dữ liệu huấn luyện. Phương pháp cực đại entropy dựa vào các đặc trưng đĩ xây dựng các mơ hình cĩ giá trị kỳ vọng của các đặc trưng của dữ liệu huấn luyện là gần giống nhất với giá trị lý thuyết. Mỗi đặc trưng sẽ cĩ một trọng số ưu tiên nhất định gọi là λ. Các phương pháp huấn luyện mơ hình từ dữ liệu huấn luyện đã được giới thiệu ở trên. Trong luận văn này sử dụng thuật tốn IIS để tính tốn các tham số. 2.3 Biểu diễn văn bản Bước đầu tiên của các phương pháp phân loại văn bản là chuyển việc mơ tả văn bản dùng chuỗi ký tự thành dạng mơ tả khác phù hợp với các thuật tốn. Hầu hết các thuật tốn đều sử dụng cách biểu diễn theo vector đặc trưng, khác nhau chủ yếu ở việc lựa chọn khơng gian đặc trưng. Cụ thể với mơ hình cực đại entropy, thuật tốn IIS chỉ cĩ thể tính tốn được các tham số dựa trên các vector đặc trưng. Vậy vector đặc trưng là gì? Mỗi vector đặc trưng đại diện cho một văn bản tương ứng trong khơng gian các từ w: (TF(w1), TF(w2), ... , TF(wn)). Trong đĩ: TF(wi) là số lần xuất hiện của từ wi trong chính văn bản đĩ (); n là số chiều của khơng gian. Để khơng phụ thuộc vào chiều dài văn bản vector đặc trưng được chuẩn hĩa như sau: Trong thực tế để cải thiện tốc độ và kết quả người ta sử dụng IDF(wi) hay TFIDF(wi) thay cho TF(wi) (trong luận văn sử dụng TFIDF): Trong đĩ: m chính là số văn bản huấn luyện DF(wi) là số văn bản cĩ chứa từ wi Biểu diễn văn bản theo các vector đặc trưng sẽ nảy sinh các vấn đề như: cần phải lựa chọn bao nhiêu từ để biểu diễn cho văn bản đĩ? Và làm thế nào để lựa chọn được những từ đĩ? Ở đây xin giới thiệu hướng tiếp cận sử dụng Information Gain [Yang & Petersen, 1997]. Phương pháp sử dụng độ đo Mutual Information(MI) để chọn ra tập đặc trưng con f gồm những từ cĩ giá trị MI cao nhất. Các đặc trưng của văn bản khi biểu diễn dưới dạng vector: Số chiều khơng gian đặc trưng thường rất lớn Việc kết hợp những đặc trưng độc lập thường khơng mang lại kết quả. Vector cĩ nhiều giá trị 0 do khơng cĩ đặc trưng trong văn bản di. 2.4 Các phương pháp phân loại văn bản 2.4.1 Nạve Bayes (NB) 2.4.1.1 Ý tưởng Sử dụng xác suất cĩ điều kiện giữa các từ trong chủ đề để tính xác suất văn bản cần phân loại thuộc vào chủ đề đĩ. Phương pháp giả định sự xuất hiện của tất cả các từ trong văn bản là độc lập với nhau. Như vậy sẽ khơng đánh giá được sự phụ thuộc của cụm từ vào một chủ đề cụ thể. Điều đĩ giúp phương pháp tính tốn nhanh hơn các phương pháp khác với độ phức tập theo số mũ. 2.4.1.2 Cơng thức Gọi Pr(cj,d) là xác suất mà văn bản d’ thuộc vào chủ đề cj. Theo luật Bayes, chủ đề cj được gán cho văn bản d’ phải cĩ Pr(cj,d) lớn nhất. Pr(cj,d) được tính như sau: Do P(d)= const nên: P(Ci,d)= P(d|Ci)P(Ci) Phương pháp NB cĩ ưu điểm cài đặt đơn giản, tốc độ nhanh, dễ dàng cập nhập dữ liệu huấn luyện mới và cĩ tính độc lập với dữ liệu huấn luyện, cĩ thể kết hợp nhiều tập dữ liệu huấn luyện khác nhau. Tuy nhiên NB địi hỏi phải cĩ ngưỡng và giả định độc lập giữa các từ. Các phương pháp multiclass-boosting cĩ thể giúp cải thiện hiệu quả của phương pháp NB. 2.4.2 k-Nearest Neighbor (kNN) kNN được đánh giá là một trong những phương pháp tốt nhất được sử dụng trong giai đoạn đầu tiên của phân loại văn bản. 2.4.2.1 Ý tưởng Khi phân loại một văn bản, thuật tốn sẽ tính khoảng cách của tất cả các văn bản trong tập huấn luyện đến văn bản cần phân lớp để tìm ra k văn bản gần nhất, sau đĩ dùng các khoảng cách này đánh trọng số cho tất cả chủ đề. Trọng số của một chủ đề chính là tổng tất cả khoảng cách ở trên của các văn bản trong k láng giềng cĩ cùng chủ đề, chủ đề nào khơng xuất hiện trong k láng giềng thì trọng số bằng 0. Sau đĩ các chủ đề được sắp xếp theo trọng số giảm dần và các chủ đề cĩ trọng số cao sẽ được lựa chọn làm chủ đề của văn bản. 2.4.2.2 Cơng thức Trọng số chủ đề cj của văn bản sẽ được tính như sau: Trong đĩ: y(,cj) {0,1}, với y= 0: văn bản khơng thuộc chủ đề cj y= 1: văn bản thuộc chủ đề cj sim(,): mức độ giống nhau giữa văn bản cần phân loại và văn bản . Với: sim(, )= (. )/(||||.||||) bj là ngưỡng phân loại của chủ đề cj được tự động học sử dụng một tập văn bản hợp lệ được chọn ra từ tập huấn luyện. Để chọn được tham số k tốt nhất, thuật tốn phải được chạy thử nghiệm trên nhiều giá trị k khác nhau, giá trị k càng lớn thì thuật tốn càng ổ định. Giá trị k tốt nhất được sử dụng trên bộ dữ liệu Reuter và Oshumed là k= 45. 2.4.3 Linear Least Square Fit (LLSF) 2.4.3.1 Ý tưởng LLSF sử dụng phương pháp hồi quy để học từ tập dữ liệu huấn luyện. Tập dữ liệu huấn luyện được biểu diễn dưới dạng một cặp vector đầu vào và đầu ra như sau: Vector đầu vào là một văn bản gồm các từ và trọng số. Vector đầu ra gồm các chủ đề cùng trọng số nhị phân của văn bản ứng với vector đầu vào. Giải phương trình cặp vector đầu vào / đầu ra sẽ được ma trận đơng hiện của hệ số hồi quy của từ và chủ đề. 2.4.3.2 Cơng thức Trong đĩ: A, B là ma trận đại diện tập dữ liệu huấn luyện (các cột tương ứng với vector đầu vào và vector đầu ra) FLS là ma trận kết quả chỉ ra ánh xạ từ một văn bản vào vector của chủ đề đã gán trọng số Sắp xếp các chủ đề theo trọng số giảm dần kết hợp với ngưỡng cụ thể sẽ tìm được chủ đề thích hợp cho văn bản đầu vào. Các ngưỡng tối ưu cho từng chủ đề sẽ được học tự động. 2.4.4 Support Vector Machine (SVM) Là phương pháp được Vapnik giới thiệu vào năm 1995 nhằm giải quyết vấn đề nhận dạng mẫu 2 lớp sử dụng nguyên lý cực tiểu hĩa rủi ro cĩ cấu trúc. 2.4.4.1 Ý tưởng Cho trước tập huấn luyện được biểu diễn trong khơng gian vector trong đĩ mỗi văn bản là một điểm, phương pháp tìm ra một siêu mặt phẳng h quyết định tốt nhất cĩ thể chia các điểm trên khơng gian này thành 2 lớp riêng biệt tương ứng lớp + và lớp -. Hiệu quả xác định siêu mặt phẳng này được quyết định bởi khoảng cách của điểm gần mặt phẳng nhất của mỗi lớp. Khoảng cách càng lớn thì mặt phẳng quyết định càng tốt đồng nghĩa với việc phân loại càng chính xác và ngược lại. Mục đích cuối cùng của phương pháp là tìm được khoảng cách biên lớn nhất. Hình 2.1: Các điểm được khoanh trịn là các vector hỗ trợ (trích dẫn: support-vector-machines.org) 2.4.4.2 Cơng thức Phương trình siêu mặt phẳng chứa vector như sau: Đặt Như vậy h() biểu diễn sự phân lớp của vào 2 lớp + và lớp -. Gọi yi = {±1}, yi = +1 văn bản thuộc lớp +, yi = -1 văn bản thuộc lớp -. Để cĩ siêu mặt phẳng h ta đi giải bài tốn: Tính Min|| || với và b thoản mãn điều kiện: Bài tốn SVM cĩ thể được giải bằng tốn tử Lagrange để biến đổi thành dạng đẳng thức. Một điểm đặc biệt trong phương pháp SVM là siêu mặt phẳng h chỉ phụ thuộc vào các vector hỗ trợ. Khác so với các phương pháp khác vì các phương pháp khác cĩ kết quả phân loại phụ thuộc vào tồn bộ dữ liệu. Khi dữ liệu cĩ sự thay đổi thì kết quả cũng thay đổi. Chương 3: Mơ hình cực đại entropy Dựa trên tài liệu mơ hình cực đại entropy của [Adam L. Berger & Stephen A. Della Pietra & Vincent J. Della Pietra, 1996] và một số nguồn khác. Dưới đấy là những cơ sở lý thuyết cơ bản về mơ hình cực đại entropy. Về cách xây dựng mơ hình, nguyên lý cực đại entropy, cách tính các phân phối xác suất và thuật tốn tính trọng số cũng như lựa chọn các đặc trưng cho bài tốn phân loại văn bản. 3.1 Tổng quát mơ hình cực đại entropy Giả thiết rằng chúng ta muốn mơ hình hĩa một hệ thống dịch tự động bằng việc lựa chọn những từ thích hợp trong tiếng Pháp mà nĩ được dịch với nghĩa là “in” trong tiếng Anh. Xác suất mơ hình (p) của hệ thống dịch tự động cho mỗi từ hay cụm từ tiếng Pháp f là một ước lượng p(f) của xác suất mà hệ thống sẽ lựa chọn f được dịch với nghĩa là “in” trong tiếng Anh. Để ước lượng được giá trị của p, chúng ta tập hợp một số lượng lớn các mẫu điển hình của hệ thống. Mục đích cuối cùng là thu được tập các sự kiện tạo lên quyết định từ những mẫu ở trên (nhiệm vụ đầu tiên), tập các sự kiện đĩ sẽ giúp chúng ta xây dựng mơ hình cho bài tốn này (nhiệm vụ thứ hai). Chúng ta cĩ thể tập hợp được một danh sách các khả năng cĩ thể được dịch từ mẫu điển hình. Ví dụ như, chúng ta cĩ thể tìm ra được những từ (cụm từ) mà hệ thống dịch luơn luơn lựa chọn trong số 5 từ (cum từ) tiếng Pháp sau đây: dans, en, à, au cours de, pendant. Với những thơng tin này, chúng ta cĩ thể dùng làm ràng buộc đầu tiên trong xác suất mơ hình (p) của chúng ta: p(dans) + p(en) + p(à) + p(au cours de) + p(pendant) = 1 Phương trình này thể hiện tính thống kê đầu tiên trong bài tốn của chúng ta; bây giờ chúng ta đã cĩ thể xử lý để tìm ra mơ hình phù hợp mà nĩ tuân theo phương trình này. Tất nhiên, cĩ vơ số các xác suất mơ hình (p) mà nĩ thỏa mãn ràng buộc trên. Một mơ hình mà thỏa mãn ràng buộc trên cĩ thể là p(dans) = 1; nĩi cách khác, mơ hình luơn luơn dự đốn đĩ là “dans”. Mơ hình khác tuân theo ràng buộc này dự đốn “pendant” với xác suất là ½, và “à” với xác suất là ½. Nhưng theo cảm giác của chúng ta thì cả hai mơ hình này đều khơng ổn cho lắm: hệ thống dịch luơn luơn lựa chọn 1 trong số 5 từ (cụm từ) tiếng Pháp, và làm thế nào chúng ta cĩ thể chứng minh mỗi phân phối xác suất đĩ là đúng? Mỗi mơ hình mới chỉ dừng lại ở mức thừa nhận, mà khơng cĩ sự chứng minh bằng thực nghiệm rằng điều đĩ là đúng. Theo cách khác, cĩ 2 mơ hình cho rằng cĩ nhiều hơn so với những gì chúng ta thực sự biết về bài tốn tạo lên hệ thống dịch. Tất cả những gì chúng ta biết là cái mà hệ hệ thống lựa chọn loại trừ trong số 5 từ (cụm từ) tiếng Pháp; với cách này, tất cả những mơ hình mang tính trực giác là như sau: p(dans) = 1/5 p(en) = 1/5 p(à) = 1/5 p(au cours de) = 1/5 p(pendant) = 1/5 Với mơ hình này, nĩ phân bố tổng xác suất ngang bằng nhau trong số 5 từ (cụm từ) cĩ thể được lựa chọn để dịch, là mơ hình đều nhất phụ thuộc vào các hiểu biết của chúng ta. Tuy nhiên khơng phải là giống nhau hồn tồn; mà mơ hình sẽ cấp một xác suất ngang nhau cho mọi từ (cụm từ) tiếng Pháp cĩ thể được dịch. Chúng ta cĩ thể hy vọng rằng cĩ thể tổng hợp được nhiều hơn những thơng tin xung quanh hệ thống dịch từ mẫu điển hình của chúng ta. Giả thiết rằng chúng ta nhận thấy hệ thống dịch lựa chọn mỗi từ (cụm từ) “dans” hay “en” là 30% trong mỗi lần lựa chọn. Chúng ta cĩ thể sử dụng thơng tin này cho việc cập nhập mơ hình của chúng ta trong bài tốn dịch bằng cách yêu cầu xác suất mơ hình (p) thỏa mãn 2 ràng buộc sau: p(dans) + p(en) = 3/10 p(dans) + p(en) + p(à) + p(au cours de) + p(pendant) = 1 Một lần nữa cĩ nhiều phân phối xác suất phù hợp với 2 ràng buộc trên. Trong trường hợp khơng cĩ sự hiểu biết nào khác, một sự lựa chọn hợp lý cho xác suất mơ hình (p) là ngang bằng nhau nhất cĩ thể, sự phân phối mà nĩ phân bố các xác suất ngang bằng nhất cĩ thể, phụ thuộc vào các ràng buộc sau: p(dans) = 3/20 p(en) = 3/20 p(à) = 7/30 p(au cours de) = 7/30 p(pendant) = 7/30 Chúng ta kiểm tra lại dữ liệu nhiều lần, và lần này nhận thấy sự kiện sau: trong một nửa các trường hợp, hệ thống dịch lựa chọn cả hai từ (cụm từ) “dans” hay “à”. Chúng ta cĩ thể kết hợp thơng tin này vào mơ hình của chúng ta như một ràng buộc thứ 3: p(dans) + p(en) = 3/10 p(dans) + p(en) + p(à) + p(au cours de) + p(pendant) = 1 p(dans) + p(à) = ½ Chúng ta cĩ thể một lần nữa tìm ra các xác suất mơ hình (p) ngang bằng nhau hơn ứng với các ràng buộc trên, nhưng bây giờ việc lựa chọn khơng cịn là hiển nhiên nữa. Khi chúng ta thêm những ràng buộc phúc tạp, chúng ta gặp phải 2 khĩ khăn. Thứ nhất, điều đĩ thực sự là phép lấy trung bình bằng cách ngang bằng nhau, và làm thế nào mà cĩ thể đo được sự ngang bằng nhau của mơ hình? Thứ hai, phải xác định được những câu trả lời phù hợp với những câu hỏi, làm thế nào mà tìm được mơ hình ngang bằng nhau nhất phụ thuộc vào tập các ràng buộc giống như chúng ta đã miêu tả? Phương pháp cực đại entropy trả lời cho cả 2 câu hỏi trên, chúng ta sẽ chứng minh trong những phần sau. Bằng trực giác, nguyên lý rất đơn giản: tồn bộ mơ hình là đã biết và được thừa nhận khơng cĩ điều gì là chưa biết. Nĩi một cách khác, cho một tập các sự kiện, lựa chọn một mơ hình mà nĩ phù hợp với tất cả các sự kiện, mặt khác ngang bằng nhất cĩ thể. Điều này gần giống như việc chúng ta lựa chọn các xác suất mơ hình (p) tại mỗi bức như chúng ta đã làm trong ví dụ trên. ...sự kiện mà một phân phối xác suất nào đĩ làm tăng entropy phụ thuộc vào các ràng buộc nào đĩ đặc trưng cho thơng tin chưa đầy đủ của nĩ, là thuộc tính cơ bản mà nĩ chứng minh ích lợi của việc phân phối cho các suy luận là đúng; nĩ phù hợp với mọi thứ mà nĩ biết, nhưng tránh những suy luận mà nĩ khơng rõ. Nĩ là một sự sao chép thành các phép tốn học của những nguyên lý cổ xưa một cách khơn ngoan... 3.2 Mơ hình cực đại entropy Chúng ta xem xét một bài tốn bất kỳ nĩ cho ra một giá trị output y, là một thành phần của tập hữu hạn Y. Với ví dụ về hệ thống dịch, bài tốn sinh ra một khả năng cĩ thể được dịch của từ “in”, và output y cĩ thể là bất kỳ từ nào trong tập {dans, en, à, au cours de, pendant}. Với việc sinh ra y, bài tốn này cĩ thể bị tác động bởi thơng tin ngữ cảnh x, là một thành phần của tập hữu hạn X. Trong ví dụ, thơng tin này cĩ thể bao gồm những từ trong câu tiếng Anh xung quanh từ “in”. Nhiệm vụ của chúng ta là xây dựng mơ hình cĩ tính ngẫu nhiên thống kê mà nĩ miêu tả chính xác các hành vi của bài tốn bất kỳ. Vì vậy mơ hình là một phương thức của việc xác định xác suất cĩ điều kiện mà trong đĩ, cho ngữ cảnh x, với output là y. Chúng ta sẽ biểu diễn bằng xác suất p(y|x) mà mơ hình ấn định y trong ngữ cảnh x. Chúng ta cũng sẽ sử dụng p(y|x) để biểu diễn cho tồn bộ phân phối xác suất cĩ điều kiện bởi mơ hình. Việc giải thích chính xác sẽ được làm sáng tỏ từ ngữ cảnh. Chúng ta sẽ ký hiệu P là tập tồn bộ các phân phối xác suất cĩ điều kiện. Như vậy một xác suất mơ hình p(y|x) chính là một thành phần của P. 3.2.1 Dữ liệu huấn luyện Để nghiên cứu về bài tốn, chúng ta theo rõi cách xử lý của một bài tốn bất kỳ trong một vài lần, sẽ tập hợp được một số lượng lớn các mẫu (x1,y1), (x2,y2), (x3,y3),...., (xN,yN). Trong ví dụ, chúng ta đã thấy rằng, mỗi mẫu sẽ gồm cĩ một nhĩm x chứa các từ xung quanh “in”, cùng với một khả năng được dịch y của từ “in” mà bài tốn đưa ra. Bây giờ chúng ta cĩ thể tưởng tượng rằng những mẫu huấn luyện đĩ cĩ thể được sinh ra bởi một nhà chuyên gia người đã đưa ra con số ngẫu nhiên cho các cụm từ chứa “in” và câu trả lời cho lựa chọn dịch tốt nhất trong mỗi lần nghiên cứu. Chúng ta cĩ thể tổng hợp mẫu huấn luyện liên quan tới chính phân phối xác suất thực nghiệm của nĩ p̃, được định nghĩa như sau: (số luần xuất hiện của cặp (x,y) trong mẫu) Trường hợp đặc biệt là cặp (x,y) sẽ khơng xuất hiện trong tồn bộ mẫu, hay sẽ xuất hiện trong tồn bộ mẫu. 3.2.2 Thống kê, đặc trưng và ràng buộc Mục đích của chúng ta là xây dựng một mơ hình thống kê của bài tốn mà nĩ phát sinh xác suất p̃(x,y) mẫu huấn luyện. Khối kiến trúc của mơ hình này sẽ là một tập các thống kê của mẫu huấn luyện. Trong ví dụ, chúng ta đã dùng một số thống kê: tần số mà từ “in” được dịch thành “dans” hay “en” là 3/10; tần số mà nĩ được dịch thành “dans” hay “au cours de” là ½; vân vân. Những thống kê đặc biệt là thống kê độc lập với ngữ cảnh, nhưng chúng ta cũng cĩ thể coi như những thống kê đĩ là phụ thuộc vào thơng tin điều kiện x. Ví dụ, chúng ta cĩ thể nhận thấy rằng, trong mẫu huấn luyện, nếu “April” là từ đi sau “in”, thì việc dịch từ “in” là “en” sẽ cĩ tần số là 9/10. Để biểu diễn sự kiện mà “in” được dịch là “en” khi “April” là từ đi theo sau, chúng ta cĩ thể sử dụng hàm để biểu diễn như sau: nếu y = “en” và “April” theo sau “in” cịn lại Giá trị kỳ vọng của f liên quan tới phân phối thực nghiệm p̃(x,y) chính là thống kê mà chúng ta đã nhắc tới. Chúng ta biểu diễn giá trị kỳ vọng này bởi: với mọi cặp (x,y) (1) Chúng ta cĩ thể biểu diễn bất kỳ thống kê nào của mẫu huấn luyện như giá trị kỳ vọng của hàm nhị phân (f) thích hợp. Chúng ta gọi hàm đĩ là hàm đặc trưng hay đặc trưng. (Như vậy với các phân phối xác suất, chúng ta sẽ dùng ký hiệu và sử dụng hàm f(x,y) để biểu diễn giá trị của f với mỗi cặp (x,y) riêng biệt cũng như tồn bộ hàm f). Khi chúng ta tìm hiểu về thống kê sẽ thấy sự hữu ích của nĩ, chúng ta cĩ thể thấy được tầm quan trọng của nĩ bằng cách làm cho những gì cĩ trong mơ hình của chúng ta phù hợp với nĩ. Chúng ta làm điều này bằng các ràng buộc các giá trị kỳ vọng mà mơ hình ấn định cho các hàm đặc trưng (f) tương ứng. Giá trị kỳ vọng của f quan hệ với xác suất mơ hình p(y|x) như sau: với mọi cặp (x,y) (2) Trong đĩ: p̃(x) là phân phối thực nghiệm của x trong mẫu huấn luyện. Chúng ta ràng buộc giá trị kỳ vọng này bằng với giá trị kỳ vọng của f trong mẫu huấn luyện: (3) Từ (1), (2) và (3) ta cĩ: Chúng ta gọi (3) là phương trình ràng buộc hay đơn giản là ràng buộc. Bằng cách thu hẹp sự chú ý tới những xác suất mơ hình, p(y|x), như trong cơng thức (3), chúng ta loại trừ các mơ hình được xem xét mà nĩ khơng thích hợp với mẫu huấn luyện dựa vào cách thơng thường mà output của bài tốn sẽ đưa ra đặc trưng f. Tĩm lại, chúng ta cĩ được giá trị trung bình cho các thống kê tương ứng với các hiện tượng tồn tại trong dữ liệu mẫu, Ẽ(f), và cũng là giá trị trung bình yêu cầu mà mơ hình của bài tốn đưa ra các hiện tượng đĩ (E(f) = Ẽ(f)). Cần phân biệt rõ ràng 2 khái niệm về đặc trưng và ràng buộc: một đặc trưng là một hàm nhận giá trị nhị phân của cặp (x,y); một ràng buộc là một phương trình giữa giá trị kỳ vọng của hàm đặc trưng trong mơ hình và giá trị kỳ vọng của nĩ trong dữ liệu huấn luyện. 3.2.3 Nguyên lý cực đại entropy Giả thiết rằng chúng ta cĩ n hàm đặc trưng fi, nĩ quyết định những thống kê mà chúng ta cảm thấy là quan trọng trong quá trình mơ hình hĩa. Chúng ta muốn mơ hình của chúng ta phù hợp với những thống kê đĩ. Vì vậy, chúng ta sẽ muốn p hợp lệ trong tập con C của P được định nghĩa bởi: C = {p € P | E(fi) = Ẽ(fi) for i € {1,2,...,n}} (4) Trong số các mơ hình p € C, triết lý cực đại entropy yêu cầu rằng chúng ta lựa chọn phân phối mà ngang bằng nhau nhất. Nhưng hiện tại chúng ta đối diện với câu hỏi rằng: ngang bằng nhau ở đây cĩ nghĩa là gì? Trong phạm vi tốn học ngang bằng nhau của phân phối cĩ điều kiện p(y|x) được cung cấp bởi entropy cĩ điều kiện: (5) Entropy là bị chặn dưới bởi 0, entropy của mơ hình khơng cĩ sự khơng chắc chắn nào, và chặn trên bởi log|Y|, entropy của phân phối ngang bằng nhau trên tồn bộ các giá trị cĩ thể |Y| của y. Với định nghĩa này, chúng ta đã sẵn sàng để biểu diễn nguyên lý của cực đại entropy: Để lựa chọn mơ hình từ một tập C các phân phối xác suất được chấp nhận, lựa chọn mơ hình p* € C với cực đại entropy H(p): với p € C (6) Điều đĩ thể hiện rằng p* luơn luơn xác định; vì vậy, luơn luơn tồn tại một mơ hình duy nhất p* với cực đại entropy trong bất kỳ tập ràng buộc C nào. 3.2.4 Tham số hình thức Nguyên lý cực đại entropy đưa ra vấn đề tối ưu các ràng buộc: tìm p* € C mà nĩ cực đại H(p). Trường hợp đơn giản, chúng ta cĩ thể tìm được giải pháp cho vấn đề này theo phép phân tích. Điều này đúng cho ví dụ được nĩi đến trong phần 1 khi chúng ta áp dụng 2 ràng buộc đầu tiên lên p. Tiếc là, giải pháp này đối với bài tốn cực đại entropy tổng quát khơng thể viết ra được một cách rõ ràng, và chúng ta cần nhiều phép tính gần đúng gián tiếp. Để giải quyết vấn đề cho bài tốn tổng quát, chúng ta áp dụng phương pháp của đa thức Lagrange từ học thuyết tối ưu hĩa cưỡng chế. Chúng ta sẽ quy về bài tốn tối ưu hĩa các ràng buộc ban đầu, với p € C như bài tốn căn bản. Với mỗi đặc trưng fi chúng ta đưa ra một tham số λi (một đa thức Lagrange). Chúng ta định nghĩa Lagrangian (p,λ) bởi: (7) Giữ cho λ cố định, chúng ta tính cực đại khơng cĩ ràng buộc của đang thức Lagrangian (p,λ) trên tồn bộ p € P. Chúng ta biểu diễn pλ là xác suất (p) trong đĩ (p,λ) đạt được giá trị cực đại và ψ(λ) là giá trị cực đại đĩ. với p € P (8) (9) Chúng ta gọi ψ(λ) là hàm đỗi ngẫu. Hàm pλ và ψ(λ) cĩ thể được tính tốn cụ thể sử dụng các phép tính đơn giản. Chúng ta tìm được: (10) (11) Trong đĩ Zλ(x) là hằng số chuẩn hĩa được quyết định bởi yêu cầu Σypλ(y|x) = 1 cho tồn bộ x: (12) Cuối cùng, chúng ta đưa ra bài tốn tối ưu hĩa đối ngẫu khơng ràng buộc: Thống qua điều đĩ cĩ vẻ khơng đạt được những địi hỏi đã đề ra ban đầu. Tuy nhiên, nguyên lý cơ bản trong học thuyết đa thức Lagrange, được gọi là định lý Kuhn-Tucker tổng quát, khảng định rằng những thừa nhận dưới đây, những bài tốn nền tảng và đối ngẫu là cĩ liên quan chặt chẽ. Đây là cách trong hồn cảnh hiện tại. Giả thiết rằng λ* là giải pháp cho bài tốn đối ngẫu. Khi đĩ pλ* là giải pháp cho bài tốn nền tảng; đĩ là pλ* = p*. Nĩi cách khác, Mơ hình cực đại entropy đưa ra các ràng buộc C cĩ dạng tham số pλ* trong cơng thức (10), trong đĩ giá trị λ* cĩ thể được tính bằng cách cực đại hĩa hàm đối ngẫu ψ(λ). Hệ quả thực tế quan trọng nhất của kết quả này là thuật tốn cho việc tìm cực đại λ* của ψ(λ) cĩ thể được dùng để tìm ra cực đại p* của H(p) cho p € C. 3.2.5 Mối quan hệ với cực đại Likelihood Log-likelihood Lp̃(p) của phân phối thực nghiệm p̃ như được dự đốn trước bởi xác suất mơ hình p được định nghĩa như sau: (13) Dễ dang cĩ thể kiểm tra được rằng hàm đối ngẫu ψ(λ) của phần trước chính là log-likelihood hàm số mũ của xác suất mơ hình pλ: (14) Với cách giải thích này, kết quả của phần trước cĩ thể được viết lại như sau: Mơ hình p* € C với cực đại entropy là mơ hình trong đĩ họ tham số pλ(y|x) mà nĩ cực đại likelihood của xác suất mẫu huấn luyện p̃. Kết quả này giúp làm tăng thêm tính đúng đắn cho nguyên lý cực đại entropy: khi quan niệm việc lựa chọn xác suất mơ hình p* trên cơ sở cực đại entropy là khơng đủ sức thuyết phục, điêu xảy ra với cùng một xác suất p* là một mơ hình mà nĩ, trong số tồn bộ các mơ hình của cùng một dạng tham số (10), cĩ thể là sự miêu tả tốt nhất cho mẫu huấn luyện. 3.2.6 Tính các tham số Với tất cả những bài tốn kể cả đơn giản nhất, thì λ* mà cực đại ψ(λ) là khơng thể tính tốn được theo phép phân tích. Thay vào đĩ, chúng ta phải dùng đến một số các phương thức khác. Hàm ψ(λ) được xử lý tốt, khi làm mịn giá trị λ.Do đĩ, cĩ nhiều phương thức khác nhau cĩ thể được dùng để tính giá trị λ*. Một phương thức đơn giản là tăng phối hợp cĩ kinh nghiệm, trong cách này λ* được tính bằng cách lặp đi lặp lại cực đại ψ(λ) một cách phối hợp tại mỗi lần. Khi được áp dụng vào bài tốn cực đại entropy, kỹ thuật này sẽ mang lại thuật tốn tổng quát Brown (Brown 1959). Các phương thức tổng quát khác cĩ thể được dùng để cực đại ψ(λ) bào gồm chuẩn gradient và liên hợp gradient. Một phương thức tối ưu hĩa đặc trưng của tailor cho bài tốn cực đại entropy là thuật tốn “improved iterative scaling” của Darroch và Ratcliff (1972). Thuật tốn cĩ thể áp dụng được bất cứ khi nào miễn là các hàm đặc trưng fi(x,y) khơng âm: fi(x,y) >= 0 với mọi i, x và y (15) Điều này là luơn đúng bởi vì giá trị của hàm đặc trưng cĩ thể nhận chỉ là giá trị nhị phân (0, 1): Σifi(x,y) = 1 với mọi x,y Thuật tốn 1: Improved Iterative Scaling (IIS) Input: hàm đặc trưng f1, f2,..., fn; phân phối thực nghiệm p̅(x,y) Ouput: Giá trị tham số tối ưu λ*i; xác suất mơ hình tối ưu pλ* Bắt đầu với λi = 0 với mọi i € {1, 2,..., n} Với mọi i € {1, 2,..., n} Sử dụng ∆λi để tính: (16) Trong đĩ: (17) Cập nhập giá trị của λi: λi = λi + ∆λi Lặp lại bước 2 nếu tất cả λi chưa hội tụ Bước quan trọng nhất trong thuật tốn là bước 2.a, việc tính tốn độ chênh lệch ∆λi được sử dụng cho phương trình (16). Nếu f#(x,y) là hằng số (f#(x,y) = M với mội x,y) thì ∆λi được tính như sau: Nếu f#(x,y) khơng phải là hằng số, khi đĩ ∆λi phải được tính tốn số học. Cách đơn giản và hiệu quả của trường hợp này là phương thức của Newton. Phương thức này tính α* của phương trình g(α*) = 0 lặp đi lặp lại bằng phép truy hồi: (18) với sự lựa chọn thích hợp cho α0 và chú ý tới sự phù hợp với phạm vi của g. 3.3 Lựa chọn đặc trưng Từ những phần trước chúng ta đã chia bài tốn mơ hình hĩa thống kê thành 2 bước: bước thứ nhất là tìm các sự kiện thích hợp về dữ liệu; bước thứ hai là kết hợp chặt chẽ các sự kiện vào mơ hình. Tiếp theo chúng ta sẽ tìm cách để giải quyết bước thứ nhất bằng cách này hay cách khác. Với ví dụ đơn giản trong phần 2, chúng ta khơng cĩ phát biểu rõ ràng về cách chúng ta lựa chọn các ràng buộc đặc trưng. Vì vậy, tại sao sự kiện “dans” hay “à” được chọn bởi hệ thống dịch là 50% tại mỗi lần lựa chọn là quan trọng hơn sơ với tất cả các sự kiện khác trong dữ liệu? Thực vậy, nguyên lý của cực đại entropy khơng trực tiếp liên quan tới việc lựa chọn đặc trưng: nĩ chỉ đơn thuần cung cấp cơng thức cho việc kết hợp các ràng buộc vào mơ hình. Nhưng bài tốn lựa chọn đặc trưng lại cĩ vấn đề, khi các ràng buộc cĩ thể là các đặc trưng trong hàng nghìn hay hàng triệu các sự kiện. Trong phần này chúng tơi giới thiệu phương thức cho việc lựa chọn tự động các đặc trưng trong mơ hình cực đại entropy, việc lựa chọn đặc trưng được thực hiện tốt sẽ giúp giảm bớt gánh nặng cho việc tính tốn. 3.3.1 Ý nghĩa của việc lựa chọn đặc trưng Chúng ta bắt đầu bằng cách chỉ rõ bộ sưu tập lớn F các đặc trưng ứng cử. Chúng ta khơng yêu cầu bất ky một ưu tiên nào đối với các đặc trưng mà những đặc trưng đĩ đều được lựa chọn như là các đặc trưng ứng cử. Thay vào đĩ, chúng ta chia thành những tập dữ liệu cĩ độ lớn cĩ thể tính tốn được. Chỉ một tập con của tập các đặc trưng sẽ được sử dụng vào mơ hình cuối cùng của chúng ta. Nếu chúng ta cĩ mẫu huấn luyện cĩ kích thước vơ hạn, chúng ta cĩ thể quyết định giá trị kỳ vọng thích hợp cho mỗi đặc trưng ứng cử f € F bằng cách tính các sự kiện nhỏ trong mẫu mà nĩ cĩ f(x,y) = 1. Trong các ứng dụng thực tế, chúng ta được cung cấp với chỉ một mẫu nhỏ N sự kiện, nĩ khơng thể tin cậy để đặc trưng cho tồn bộ bài tốn và là đúng đắn. Rõ ràng, chúng ta khơng thể mong chờ rằng với mọi đặc trưng f € F, ước lượng Ẽ(f) chúng ta nhận được từ mẫu sẽ hạn chế giá trị của nĩ trong một giới hạn khi n tăng dần. Sử dụng một mẫu lớn dữ liệu với cùng một bài tốn cĩ thể dẫn đến các ước lượng Ẽ(f) khác nhau với các đặc trưng ứng cử. Một cách ngắn gọn, chúng ta muốn thêm vào mơ hình chỉ một tập con S của tồn bộ tập đặc trưng ứng cử F. Chúng ta sẽ gọi S là tập đặc trưng cĩ hiệu lực. Việc lựa chọn S phải lấy được thật nhiều thơng tin về bài tốn bất kỳ càng nhiều càng tốt, tuy nhiên chỉ thêm các giá trị kỳ vọng của các đặc trưng cĩ thể ước lượng đáng tin cậy. Để tìm tập S, chúng ta chọn gần đúng tăng dần cho việc lựa chọn đặc trưng, giống như chiến lược được áp dụng cho việc phát triển cây quyết định (Bahl et al 1989). Ý tưởng là xây dựng tập con S bằng cách thêm lần lượt các đặc trưng. Với mỗi lựa chọn đặc trưng được thêm vào tại mỗi bước được quyết định bởi dữ liệu huấn luyện. Bây giờ chúng ta biểu diễn tập mơ hình được xây dựng bởi các đặc trưng của tập S là C(S). Mỗi khi thêm một đặc trưng f phải thỏa mãn phương trình Ẽ(f) = E(f). Chỉ các thành phần của C(S) sẽ thỏa mãn phương trình này; những đặc trưng đĩ được biểu diễn bởi C(Sυf). Như vậy, mỗi lần một đặc trưng ứng cử được nối tiếp vào S, ràng buộc tuyến tính khác được áp dụng lên khơng gian C(S) của mơ hình được cho phép bởi các đặc trưng trong tập S. Như vậy kết quả là, C(S) được rút gọn lại; xác suất mơ hình p* trong C với entropy lớn nhất phản ánh sự hiểu biết tăng mãi mãi và vì vậy việc miêu tả bài tốn sẽ trở nên chính xác hơn.Điều này giúp cho khơng gian chấp nhận được của các mơ hình được thu hẹp hơn. Cĩ lẽ trực quan hơn, chúng ta cĩ thể miêu tả nĩ bằng một loạt các tập con được đạt vào P như hình sau: Hình 3.1: Lựa chọn đặc trưng (trích dẫn: trang 12 quyển A Maximum Entropy Approach to Natural Language Processing) 3.3.2 Cơ sở lựa chọn đặc trưng Cơ sở của thủ tục tăng dần cĩ thể được phác thảo như sau. Với mọi giai đoạn của bài tốn được xác định rõ đặc điểm bởi tập các đặc trưng cĩ hiệu lực S. Điều đĩ quyết định khơng gian của mơ hình: C(S) = {p € P | E(f) = Ẽ(f) với mọi f € S} (19) Mơ hình tối ưu trong khơng gian này, được biểu diễn bởi pS, là mơ hình với entropy lớn nhất: (20) Bằng cách thêm đặc trưng f̃ vào tập S, chúng ta thu được tập mới với các đặc trưng cĩ hiệu lực Sυf̃. Như cơng thức (19), tập đặc trưng này quyết định tập các mơ hình: C(S U f̃) = {p € P | E(f) = Ẽ(f) với mọi f € S U f̃} (21) Mơ hình tối ưu trong khơng gian mơ hình này là: (22) Thêm đặc trưng f̃ cho phép mơ hình psυf̃ tính tốn tốt hơn với mẫu huấn luyện; điều này dẫn đến việc thu được ∆L(S,f̃) từ log-likelihood của dữ liệu huấn luyện. (23) Tại mỗi giai đoạn của bài tốn xây dựng mơ hình, mục đích của chúng ta là lựa chọn được đặc trưng ứng cử f̃ € F mà nĩ giúp tăng ∆L(S,f̃); vì vậy, chúng ta lựa chọn đặc trưng ứng cử, khi nối tiếp vào tập đặc trưng cĩ hiệu lực S, nĩ giúp tăng đáng kể likelihood trong mẫu huấn luyện. Chiến lược này được thực thi trong thuật tốn sau: Thuật tốn 2: Input: tập hợp F của các đặc trưng ứng cử; phân phối thực nghiệm p̃(x,y) Output: tập S các đặc trưng cĩ hiệu lực; xác suất mơ hình pS hợp nhất các đặc trưng. Bắt đầu với S= Θ; vì vậy pS là giống nhau Với mỗi đặc trưng ứng cử f € F: Tính xác suất mơ hình PSυf sử dụng thuật tốn 1 Tính lượng gia tăng của log-likelihood từ những đặc trưng được thêm vào sử dụng cơng thức (23) Kiểm tra điều kiện kết thúc Lựa chọn đặc trưng f̃ với độ tăng tối đa ∆L(S,f̃) Nối liền f̃ vào tập S Tính xác suất pS sử dụng thuật tốn 1 Lặp lại bước 2 Cĩ thể thấy được, chúng ta sẽ muốn một điều kiện dừng giúp bài tốn dừng một cách chính xác khi tồn bộ các đặc trưng hữu ích đã được lựa chọn. 3.3.3 Giá trị gần đúng Thuật tốn 2 khơng phải là phương thức thực tế cho việc lựa chọn đặc trưng tăng dần. Với mỗi đặc trưng ứng cử f € F được xem xét trong bước 2, chúng phải tính xác suất mơ hình pSυf, đĩ là cơng việc rất tốn kém trong việc tính tốn ngay cả với thuật tốn iis. Bởi vậy chúng tơi giới thiệu một thuật tốn cải tiến, đĩ là thuật tốn tham ăn cĩ tính khả thi hơn. Chúng ta thay vì tính tốn độ gia tăng ∆L(S,f̃) của một đặc trưng f với phép tính xấp xỉ, thì chúng ta biểu diễn bằng ~∆L(S,f̃). Nhắc lại rằng một xác suất mơ hình pS cĩ tập các tham số λ, với mỗi đặc trưng trong tập S. Xác suất mơ hình pSυf chứa tập các tham số này, cộng với tham số mới α, tương ứng với f. Với cấu trúc này, chúng ta cĩ thể hy vọng rằng giá trị tối ưu của λ sẽ khơng thay đổi khi đặc trưng f được nối tếp vào tập S. Trường hợp này, khi sử dụng thêm ràng buộc sẽ yêu cầu tham số tối ưu α làm tăng liklihood. Thực vậy, khi một ràng buộc mới được sử dụng, các giá trị tối ưu của tồn bộ các tham số sẽ thay đổi. Tuy nhiên, để dễ dàng tính tốn được thứ hạng của các đặc trưng, chúng ta xấp xỉ chúng, những đặc trưng thêm vào f chỉ tác động tới α, những giá trị λ cịn lại được kết hợp với những đặc trưng khác khơng thay đổi. Vì vậy, khi quyết định độ gia tăng trên xác suất mơ hình pS, chúng ta ràng buộc rằng mơ hình tốt nhất chứa các đặc trưng Sυf phải cĩ dạng như sau: với các giá trị thật của α (24) Trong đĩ (25) Chỉ duy nhất tham số mà nĩ phân biệt được các mơ hình cĩ dạng (24) là α. Trong số các mơ hình đĩ, chúng ta quan tâm tới mơ hình mà nĩ làm tăng tính gần đúng. (26) Chúng ta sẽ biểu diễn sự tăng thêm của mơ hình này bởi: (27) và mơ hình tối ưu bởi: trên pαS,f (28) Tính tốn giá trị gần đúng trong likelihood từ việc thêm các đặc trưng f vào pS đã đưa bài tốn tối ưu về dạng 1 chiều đơn giản hơn với một tham số α, nĩ cĩ thể được giải quyết bởi bất kỳ kỹ thuật tìm kiếm tuyến tính thơng thường nào (chẳng hạn như phương thức của Newton). Điều đĩ giúp tránh được những phép tính phức tạp và tăng độ chính xác của bài tốn, một bài tốn tối ưu n chiều yêu cầu nhiều phương thức phức tạp hơn như gradient liên hợp. Nhưng việc tiết kiệm chi phí đĩ: với một đặc trưng riêng biệt f nào đĩ, chúng ta hầu như đánh giá thấp giá trị của nĩ, và điều đĩ giúp chúng ta lựa chọn đặc trưng f mà giá trị gần đúng ~∆L(S,f) của nĩ là cao nhất thơng qua đặc trưng f với việc tăng tối đa giá trị ∆L(S,f). Log-likelihood được biểu diễn như một hàm lồi tùy ý với 2 tham số (như hình vẽ): λ tương ứng với tham số cũ, và α ứng với tham số mới. Giữ cố định giá trị λ và thay đổi α để tăng log-likelihood bao gồm việc tìm kiếm trên tồn bộ khơng gian (λ,α). Hình 3.2: log-likelihood được biểu diễn như hàm lồi 2 tham số (trích dẫn: trang 15 quyển A Maximum Entropy Approach to Natural Language Processing) Chương 4: Thực nghiệm phân loại văn bản 4.1 Thống kê kết quả thực nghiệm Dữ liệu được sử dụng trong huấn luyện và kiểm thử là những bài báo được lọc ra từ trang web bao gồm 6 chủ đề: kinh doanh, pháp luật, thể thao, văn hĩa, vi tính và xã hội. Mỗi chủ đề tương ứng với một thư mục với tên: kinh_doanh, phap_luat, the_thao, van_hoa, vi_tinh và xa_hoi. Với dữ liệu huấn luyện: kinh_doanh cĩ 540 file, phap_luat cĩ 240 file, the_thao cĩ 660 file, van_hoa cĩ 360 file, vi_tinh cĩ 660 file và xa_hoi cĩ 300 file. Với dữ liệu kiểm thử: kinh_doanh cĩ 423 file, phap_luat cĩ 179 file, the_thao cĩ 450 file, van_hoa cĩ 294 file, vi_tinh cĩ 524 file và xa_hoi cĩ 219 file. Số lượng file của dữ liệu huấn luyện: Tên chủ đề Số lượng file kinh_doanh 540 phap_luat 240 the_thao 660 van_hoa 360 vi_tinh 660 xa_hoi 300 Bảng 4.1: Số lượng file của dữ liệu huấn luyện Số lượng file của dữ liệu kiểm thử: Tên chủ đề Số lượng file kinh_doanh 423 phap_luat 179 the_thao 450 van_hoa 294 vi_tinh 524 xa_hoi 219 Bảng 4.2: số lượng file của dữ liệu kiểm thử Từ tập dữ liệu huấn luyện và kiểm thử thơ ban đầu này, trước khi được sử dụng để huấn luyện và kiểm thử cần qua một số bước lọc bỏ các đặc trưng khơng tốt. Bước thứ nhất, lọc bỏ các từ vơ nghĩa (stop word), các ký tự đặc biệt như {‘!’ ‘@’ ‘,’ ‘.’ ‘:’ ‘;’ ....} và gom nhĩm các từ vào cùng một nhĩm cĩ tính chất giống nhau. Ví dụ như gom các giá trị số đếm, ngày tháng năm... vào nhĩm number. Trong bước này, danh sách từ vơ nghĩa được xác định bằng thuật tốn TFIDF dựa trên tập dữ liệu huấn luyện và danh sách từ vơ nghĩa mẫu. Bước tiếp theo là lọc bỏ các đặc trưng theo tần số. Những đặc trưng cĩ tần số xuất hiện trong dữ liệu huấn luyện thấp hơn một giá trị nào đĩ (mặc định là 10) sẽ bị loại bỏ. Bước cuối cùng được thực hiện sau khi đã gán các trọng số cho từng đặc trưng. Tại bước này, những đặc trưng nào khơng làm tăng entropy của mơ hình thì sẽ bị loại bỏ. Với chức năng huấn luyện của chương trình phân loại văn bản. Người dùng cĩ thể khởi tạo giá trị cho một số biến điều khiển như sau: lựa chọn feature (lọc bỏ những đặc trưng cĩ tần số nhỏ hơn giá trị được khởi tao), khởi tạo giá trị ban đầu cho λ, khởi tạo giá trị hội tụ Δλ trong thuật tốn IIS. Với cùng một tập dữ liệu huấn luyện và kiểm thử như trên, tiến hành thực nghiệm với các giá trị khởi tạo khác nhau ta thu được những thống kê sau: Với các giá trị khởi tao: lựa chọn feature = 10, khởi tạo lamda = 0, giá trị hội tụ = 0. Chương trình chạy chức năng huấn luyện với thời gian 6 phút 41 giây. Với chức năng kiểm thử, tỉ lệ gán nhãn đúng trung bình là 98.19%. Trong đĩ tương ứng với từng chủ đề tỷ lệ gán nhãn đúng được biểu diễn như trong biểu đồ sau: Với các giá trị khởi tao: lựa chọn feature = 20, khởi tạo lamda = 0, giá trị hội tụ = 0. Chương trình chạy chức năng huấn luyện với thời gian 2 phút 40 giây. Với chức năng kiểm thử, tỉ lệ gán nhãn đúng trung bình là 98.19%. Trong đĩ tương ứng với từng chủ đề tỷ lệ gán nhãn đúng được biểu diễn như trong biểu đồ sau: Với các giá trị khởi tao: lựa chọn feature = 10, khởi tạo lamda = 0.3, giá trị hội tụ = 0. Chương trình chạy chức năng huấn luyện với thời gian 7 phút 00 giây. Với chức năng kiểm thử, tỉ lệ gán nhãn đúng trung bình là 98.43%. Trong đĩ tương ứng với từng chủ đề tỷ lệ gán nhãn đúng được biểu diễn như trong biểu đồ sau: Qua đĩ rút ra nhận xét rằng, kết quả của việc huấn luyện phụ thuộc phần nào vào việc khởi tạo giá trị lựa chọn lamda (lọc bỏ những đặc trưng cĩ tần số nhỏ hơn mức tối thiểu), vào giá trị khởi tạo λ và gí trị hội tụ của Δλ. Cặp giá trị khởi tạo này cĩ thể tốt với tập dữ liệu huấn luyện này nhưng lại là khơng tốt với tập dữ liệu khác. Do đĩ làm thế nào cĩ thể tìm được những giá trị khởi tạo tốt nhất cho từng tập dữ liệu huấn luyện riêng là điều rất khĩ. Điều đĩ địi hỏi nhiều kinh nghiệm trong quá trình xử lý với những tập dữ liệu huấn luyện khác nhau. 4.2 Các thành phần và chức năng của chương trình Chương trình phân loại văn bản với mục đích kiểm nghiệm phương pháp phân loại văn bản cực đại entropy với tiếng Việt và đồng thời cũng là cơ sở để tích hợp vào hệ thống chặn nội dung web. Với tập dữ liệu huấn luyện tiếng Việt. Chương trình dựa vào phương pháp phân loại cực đại entropy để huấn luyện đưa ra tập dữ liệu đã được huấn luyện. Dữ liệu này sẽ được sử dụng cho việc kiểm thử, gán nhãn cho văn bản cần phân loại. Chương trình gồm 3 chức năng chính: chức năng huấn luyện, chức năng kiểm thử và chức năng gán nhán. 4.2.1 Chức năng huấn luyện Giao diện chính của chức năng như sau: Hình 4.1: Giao diện chức năng huấn luyện Bảng mơ tả các chức năng của giao diện huấn luyện: Stt Mơ tả 1 Trả lại giá trị mặc định của chức năng huấn luyện 2 Bắt đầu huấn luyện 3 Thốt khỏi chương trình 4 Lựa chọn đường dẫn thư mục 5 Chọn giá trị lọc feature (lọc bỏ các feature cĩ tần số <10) 6 Gán giá trị khởi tạo lamda cho thuật tốn iis 7 Gán giá trị hội tụ trong thuật tốn iis 8 Lựa chọn cĩ ghi file tần số hay khơng 9 Lựa chọn ngơn ngữ của tập dữ liệu huấn luyện Bảng 4.3: Mơ tả giao diện huấn luyện Mục Chọn đường dẫn cĩ 3 đường dẫn cần lựa chọn. Thứ nhât, đường dẫn tới nơi lưu dữ liệu huấn luyện cần huấn luyện. Thứ hai, là đường dẫn lưu dữ liệu sau khi được huấn luyện. Thứ ba, là đường dẫn lưu file tần số. Đường dẫn này chỉ được lựa chọn khi nút checkbox ghi file tần số được đánh dấu. Bảng thơng báo kết quả huấn luyện cĩ dạng như sau: Stt Tên nhãn Số lượng file Số lượng feature 1 kinh_doanh 540 1328 2 phap_luat 240 648 3 the_thao 660 1911 4 van_hoa 360 949 5 vi_tinh 660 1653 6 xa_hoi 300 1031 Bảng 4.4: Kết quả huấn luyện Với bài tốn phân loại văn bản, việc định nghĩa các đặc trưng được dựa trên các từ xuất hiện trong một chủ đề nào đĩ. Theo đĩ, nếu từ đĩ xuất hiện trong chủ đề thì đặc trưng đĩ được bật giá trị là 1 và ngược lại giá trị là 0. Ví dụ: xuất hiện từ “tiền” trong chủ đề là “kinh doanh” thì đặc trưng f(tiền, kinh_doanh) = 1 cịn f(đá_bĩng, kinh_doanh) = 0. 4.2.2 Chức năng kiểm thử Giao diện chính chức năng kiểm thử: Hình 4.2: Giao diện chức năng kiểm thử Bảng mơ tả các chức năng của giao diện kiểm thử: Stt Mơ tả 1 Trả lại giá trị mặc định của chức năng huấn luyện 2 Bắt đầu kiểm thử 3 Thốt khỏi chương trình 4 Lựa chọn đường dẫn thư mục 5 Danh sách cách nhãn cĩ thể được gán ứng với dữ liệu huấn luyện được chọn Bảng 4.5: Mơ tả chức năng kiểm thử Bảng thơng báo kết quả kiểm thử cĩ dạng như sau: Stt Tên nhãn Số lượng file Số lượng feature 1 kinh_doanh 423 0 2 phap_luat 197 13 3 the_thao 450 10 4 van_hoa 423 0 Bảng 4.6: Kết quả kiểm thử 4.2.3 Chức năng gán nhãn Giao diện chính chức năng gán nhãn Hình 4.3: Giao diện chức năng gán nhãn Các thành phần của chức năng gán nhãn tương tự như chức năng kiểm thử. Bảng thơng báo kết quả gán nhãn cĩ dạng như sau: Stt Tên file Gán nhãn 1 file1.txt kinh_doanh 2 file2.txt phap_luat 3 file3.txt kinh_doanh 4 file4.txt the_thao 5 file5.txt van_hoa 6 file6.txt the_thao Bảng 4.7: Kết quả gán nhãn Cuối cùng là giao diện giới thiệu về chương trình: Hình 4.4: Giao diện giới thiệu 4.3 Ứng dụng chặn nội dung web Nhiệm vụ của chương trình là kiểm sốt nội dung của những trang web được người dùng truy cập và mạng Internet thơng qua trình duyệt (Internet Explorer). Mỗi khi người dùng nhập một địa chỉ url của một trang web vào trình duyệt. Chương trình sẽ bắt url và sử dụng địa chỉ url đĩ để lấy nội dung của trang web đĩ về. Sau đĩ xử lý nội dung, lọc bỏ những đoạn mã HTML để lấy những nội text của trang web (chính là những dịng text hiển thị trên màn hình khi trang web được load về máy người dùng). Nội dung đĩ sẽ được qua xử lý lọc bỏ các ký tự vơ nghĩa và một số thao tác tiền xử lý. Dựa vào hệ thống phân loại văn bản đã được kiểm thử ở trên, nội dung của trang web được tải về sẽ được phân loại vào chủ đề cụ thể. Qua việc phân loại đĩ giúp ta quyết định được với địa chỉ trang web đĩ cĩ được cho phép hay bị chặn lại. 4.3.1 Kỹ thuật lọc web Blue Coat Kỹ thuật lọc web Blue Coat là một giải pháp lọc nội dung web thơng qua một “proxy”. Nĩ giúp cho các tổ chức kinh doanh cũng như các nhà cung cấp các dịch vụ mạng bảo vệ cho những người dùng và hệ thống của họ khỏi những mối đe dọa tới từ Internet. Những mối đe dọa cĩ thể là các phần mềm gián điệp (spyware), các vụ tấn cơng lừa đảo... Blue Coat bao gồm hơn 15 triệu các phạm trù, đại diện cho hàng tỉ các trang web, được sắp xếp theo các phạm trù hữu ích nhất. Để đảm bảo độ chính xác, mỗi trang web cĩ thể được phân thành nhiều phạm trù, nĩ cũng cho phép khách hàng xác định một số lượng khơng hạn chế các phạm trù được cho phép truy cập hay bị chặn để phù hợp với từng yêu cầu cụ thể (ví dụ như chặn các trang web được phân loại là thể thao hoặc vi tính). Đối với những trang web chưa được phân loại vào các phạm trù ở trên, thì việc cho phép hay chặn dựa trên kỹ thuật Dynamic Real-Time Rating (DRTR) là một kỹ thuật phân loại các trang web khi người dùng cố gắng truy cập. Độ bao phủ của cơ sở dữ liệu: Độ bao phủ của cơ sở dữ liệu là khả năng xác định trang web được phân loại vào một phạm trù nhất định. Để đánh giá độ bao phủ của cơ sở dữ liệu chúng ta xét ví dụ sau: Trong số 100 trang web thuộc phạm trù thể thao được sử dụng để đánh giá độ bao phủ của cơ sở dữ liệu. Với cơ sở dữ liệu đĩ, nĩ phân loại bao nhiêu trang web vào phạm trù thể thao. Khi đĩ số lượng những trang web được phân loại đúng càng cao thì độ bao phủ của cơ sở dữ liệu đĩ càng lớn. Để cĩ độ bao phủ của cơ sở dữ liệu, bộ lọc web phải cĩ khả năng sau: Đánh giá tên miền (thay vì url hay địa chỉ ip) khi thích hợp: Một tên miền cá nhân cĩ thể cĩ hàng ngàn các url. Url mới cĩ thể được thêm vào các phạm trù (trong cơ sở dữ liêu) hàng ngày. Đối với các tên miền đồng nhất, thì việc đánh giá theo tên miền sẽ cĩ nhiều lợi ích hơn so với url hay ip. Bằng cách đánh giá theo tên miền, tất cả những url mới được thêm vào tên miền trên ngay lập tức được kiểm sốt. Tỷ lệ các trang web tập hợp được chủ yếu từ yêu cầu của người sử dụng: Khơng nhà cung cấp nào cĩ thể đánh giá được tất cả 16 tỷ các trang web và cũng khơng cần thiết phải làm điều đĩ. Một tỷ lệ lớn các trang web này cĩ thể đã khơng cịn tồn tại. Blue Coat ưu tiên những trang web mà người dùng truy cập đã được phân loại trong cơ sở dữ liệu. Điều này được được thực hiện bởi kỹ thuật Dynamic Real-Time Rating (DRTR). Sau những lần truy cập và phân tích các trang web. Những thơng tin đĩ sẽ được cập nhập cho cơ sở dữ liệu. Cập nhập cơ sở dữ liệu: Như đã nĩi ở trên, để tăng hiệu quả về mặt thời gian thực Blue Coat sẽ tự động cập nhập những thơng tin đã được phân tích của các trang web sau khi người dùng truy cập. Những dữ liệu cập nhập này được gọi là cơ sở dữ liệu địa phương. Chúng được cập nhập thường xuyên để đảm bảo các trang web đĩ vẫn cịn hoạt động bình thường. Tính năng này giống như việc cập nhập giá cả. 4.3.2 Chức năng ứng dụng chặn nội dung web Giao diện chính chương trình chặn nội dung web: Hình 4.5: Giao diện chặn nội dung web Bảng mơ tả các chức năng của giao diện chặn nội dung web: Chức năng Mơ tả Stop Dừng việc phân tích url được nhập vào trình duyệt Start Bắt đầu phân tích bắt và phân tích url nhập vào trình duyệt Refresh Khởi tạo các giá trị mặc địch cho các textfield Close Thốt hồn tồn khởi chương trình Setting Cửa sổ cài đặt đối với dữ liệu phân lớp và chỉ ra những nội dung web bị chặn About Cửa sổ giới thiệu về chương trình Phân tích Thực hiện việc phân tích địa chỉ url được nhập vào textfield tương ứng để thực hiện việc cho phép hoặc chặn truy cập với url đĩ Cho phép Cho phép địa chỉ url được nhập vào text field tương ứng được truy cập Chặn Chặn địa chỉ url được nhậpvào text field tương ứng khơng được truy cập Danh sách url cho phép truy cập Một danh sách gồm những địa chỉ url đã được phân tích là thuộc vào những url được phép truy cập Danh sách url bị chặn truy cập Một danh sách gồm những địa chỉ url đã được phân tích là thuộc vào những url bị chặn khơng được truy cập Bảng 4.8: Chức năng giao diện chặn nội dung web Tại giao diện chính khi người dùng tắt cửa sổ bằng button close của cửa sổ cĩ hình x thì cửa sổ sẽ được thu nhỏ xuống thanh system tray. Nếu muốn hiển thị lại người dùng chỉ việc nhấp chuột phải vào biểu tượng chương trình tại thanh system tray rồi chọn show. Ngồi lựa chọn show bạn cĩ thể chọn start, stop hay exit. Tiếp theo là giao diện chắc năng setting dùng để cài đặt dữ liệu phân lớp như sau: Hình 4.6: Cửa sổ setting Chức năng setting rất đơn giản như sau: mặc định ban đầu khi bạn cài đặt chương trình chặn nội dung web đã cĩ dữ liệu phân lớp. Nếu như bạn muốn sử dụng dữ liệu phân lớp nào khác thì cĩ thể dùng button “...” để chỉ ra đường dẫn tới thư mục chứa dữ liệu phân lớp mới của bạn. Sau khi lựa chọn xong dữ liệu phân lớp, tất cả các chủ đề của dữ liệu được liệt kê trong Danh sách các chủ đề phân lớp như hình vẽ. Trong số các chủ đề đĩ, bạn cĩ thể chọn 1 hay nhiều chủ đề sẽ bị chặn truy cập và nhấp vào button “=>” để chuyển vào danh sách các chủ đề bị chặn. Sau khi đã cài đặt xong bạn nhấp vào button Lưu để lưu lại những thay đội hoặc Thốt để trở lại với cài đặt trước đấy. Và cuối cùng là cửa sổ About giới thiệu về chương trình: Hình 4.7: Cửa sổ giới thiệu Chương 5: Kết luận 5.1 Kết quả đạt được Thơng qua việc tìm hiểu và nghiên cứu một số phương pháp phân loại văn bản như: Nạve Bayes, k-Nearest Neighbor, Linear Least Squares Fit, Support Vector Machine, mơ hình cực đại Entropy giúp hiểu rõ về các phương pháp phân loại văn bản, những ưu nhược điểm của từng phương pháp. Qua việc phân tích ưu nhược điểm này giúp lựa chọn phương pháp phân loại văn bản tốt nhất cho bài tốn phân loại văn bản, phục vụ cho mục đích cuối cùng của luận văn. Với ưu điểm mềm dẻo và linh hoạt của mơ hình cực đại entropy, luận văn sử dụng mơ hình cực đại entropy để giải quyết bài tốn phân loại văn bản. Lý thuyết mơ hình cực đại entropy được trình bày chi tiết tại chương 3 với những khái niệm về dữ liệu huấn luyện, thống kê, đặc trưng và các ràng buộc. Nguyên lý hoạt động của mơ hình cực đại entropy với bài tốn phân loại văn bản. Cách tính các tham số với thuật tốn IIS và cơ sở lựa chọn các đặc trưng. Dựa trên những cơ sở lý thuyết của mơ hình cực đại entropy để phát triển chương trình phân loại văn bản. Chương trình được viết bằng ngơn ngữ lập trình Java với giao diện tiện dụng và đầy đủ các chức năng (huấn luyện, kiểm thử và gán nhãn). Chương trình chặn nội dung web là một ứng dụng của bài tốn phân loại văn bản. Chương trình dựa trên nội dung của trang web và chương trình phân loại văn bản ở trên để phân loại trang web theo các chủ đề. Bên cạnh tính năng phân loại, chương trình cĩ khả năng chặn truy cập những trang web theo một số chủ đề nào đĩ được chỉ ra bởi người quản trị. Điều đĩ giúp quản lý việc truy cập Internet cĩ hiệu quả hơn và tránh được những trang web cĩ nội dung khơng tốt. Tồn bộ mã nguồn của chương trình phân loại văn bản và chặn nội dung web được sử dụng trong luận văn đều được xây dựng và phát triển từ đầu. Về mặt thực nghiệm, những kết quả thực nghiệm của chương trình chặn nội dung web được thống kê chi tiết tại chương 4. Theo đĩ, về mặt thời gian huấn luyện cũng như tỷ lệ gán nhãn thành cơng trong kiểm thử của chương trình đạt kết quả rất tốt. Tỷ lệ gán nhãn đúng trong kiểm thử qua nhiều lần thực nghiệm hơn 98%. Kết quả này cịn được cải thiện tốt hơn với việc thay đổi các tham số điều khiển như: khởi tạo λ, lựa chọn đặc trưng và giá trị hội tụ của Δλ. Với chương trình chặn nội dung web, chương trình được kiểm tra với trình duyệt Internet Explorer. Chương trình tự động kiểm tra những địa chỉ url mà người dùng nhập vào trình duyệt. Sau đĩ phân tích nội dung của trang web đĩ. Nếu nội dung thuộc chủ đề được phép truy cập chương trình sẽ cập nhập địa chỉ url vào danh sách các địa chỉ url được phép truy cập trên giao diện chương trình. Điều đĩ tương ứng với địa chỉ url bị chặn, chỉ khác ở chỗ địa chỉ url bị chặn sẽ được đưa vào danh sách url bị chặn của ip-sec của window thơng qua các luật. Ngồi chức năng phân tích tự động thơng qua trình duyệt Internet Explorer, người quản trị cũng cĩ thể phân tích trực tiếp một địa chỉ url nào đĩ từ chương trình chặn nội dung web thơng qua giao diện cũng như trực tiếp cho phép truy cập hay chặn truy cập với một url nào đĩ. 5.2 Những hạn chế và hướng giải quyết Qua những thống kê thực nghiệm của chương trình phân loại văn bản. Một hướng giải quyết mới giúp nâng cao khả năng gán nhãn sẽ là việc thay đổi các tham số điều khiển (khởi tạo λ, lựa chọn đặc trưng và giá trị hội tụ của Δλ). Bằng việc thay đổi đĩ sẽ giúp tìm ra được mơ hình hồn thiện nhất ứng với những tập dữ liệu huấn luyện khác nhau. Do thời gian cĩ hạn nên trong khuơn khổ luận văn mới chỉ phát triển được những tính năng cở bản của chương trình chặn nội dung web nhằm ứng dụng bài tốn phân loại văn bản. Chương trình vẫn cịn nhiều hạn chế như: chương trình mới chỉ làm việc trên trình duyệt Internet Explorer và cơ chế chặn truy cập hoạt động chưa được tốt. Tài liệu tham khảo Tài liệu tiếng Anh [1] Adam Berger; The Improved Iterative Scaling Algorithm: A Gentle Introduction; 1997 [2] Adam L. Berger & Stephen A. Della Pietra & Vincent J. Della Pietra; A Maximum Entropy Approach to Natural Language Processing; 1996 [3] Adwait Ratnaparkhi; A Simple Introduction to Maximum Entropy Models for Natural Language Processing; 1997 [4] Adwait Ratnaparkhi; Maximum Entropy Models for Natural Language Ambiguity Resolution; 1998 [5] Blue Coat; Blue Coat WebFilterTMTechnology. [6] Christopher D. Manning & Hinrich Schutze; Foundations of Statistical Natural Language Processing; 1999; 612 - 645 [7] Jeffrey C. Reynar & Adwait Ratnaparkhi; A Maximum Entropy Approach to identifying sentence boundaries; 1997. [8] Jun’ichi Kazama & Jun’ichi Tsujii; Evaluation and Extension of Maximum Entropy Models with Inequality Constraints; 2003 [9] Kamal Nigam & John Lafferty & Andrew McCallum; Using Maximum Entropy for Text Classification [10] Radu Ioan Bot & Sorin Mihai Grad & Gert Wanka; Maximum Entropy Optimization for Textclassification problems; 1999 [11] RobertMalouf; A comparison of algorithms for maximum entropy parameter estimation [12] Ronald Rosenfeld; A Maximum Entropy Approach to Adaptive Statistical Language Modeling [13] Stanley F. Chen & Ranald Rosendfeld; A Gausan Prior for smoothing Maximum Entropy Models; 1999 [14] Thorsten Joachims; A probabilistic analysis of the Rocchio algorithm with TFIDF for text categorization; 1997 Tài liệu tiếng Việt [1] Hồ Quốc Bảo, Đơng Thị Bích Thủy; Ứng dụng xử lý ngơn ngữ tự nhiên trong tìm kiếm thơng tin trên văn bản tiếng việt; [2] Nguyễn Lính Gian, Nguyễn Mạnh Hiển; Phân loại văn bản tiếng việt với bộ phân loại vector hỗ trợ SVM; 2005 [3] Nguyễn Thị Ngọc Hợp; Phân loại văn bản sử dụng hạt nhân của chuỗi; [4] Vũ Thanh Nguyên, Trang Nhật Quang; Ứng dụng thuật tốn phân lớp rút trích thơng tin văn bản FSVM trên Internet; 2008 [5] Đỗ Phúc, Mai Xuân Hùng, Nguyễn Thị Kim Phụng; Gom cụm đồ thị và ứng dụng vào việc rút trích nội dung chính của khối thơng điệp trên diễn đàn thảo luận; 2008 [6] Phạm Thị Thơm; Ứng dụng phương pháp phân loại văn bản Naive Bayes vào việc xây dựng chương trình mail client với khả năng lọc thư rác tự động; 2006 Phụ lục Chức năng của các các lớp sử dụng trong chương trình phân loại văn bản: Tên lớp Mơ tả EmpiricalDistribution Lớp bao gồm các hàm: get_distribution_xy, get_distribution_x. Được dùng để tính xác suất thực nghiệm và xác suất ngữ cảnh Feature Lớp bao gồm các hàm: set_feature, get_c. Dùng để gán giá trị {0,1} cho các đặc trưng và tính giá trị C (giá trị tổng các đặc trưng của từng nhãn lớn nhất) IIS Lớp bao gồm các hàm: get_z, get_p_yx, get_empirical_expectation, get_model_expectation, delta_lamda, lamda, write_lamda, write_all. Dùng để cài đặt thuật tốn IIS cho việc tính tốn trọng số cho từng đặc trưng InputFile Lớp bao gồm các hàm: read_input, write_input, set_lamda, set_model_distribution. Dùng để tính trọng số của từng đặc trưng cho file cần gán nhãn và đưa ra tên nhãn được gán LamdaFile Lớp bao gồm các hàm: cut_tag_name, read_lamda_file, read_all. Dùng để đọc nội dung của các file đã được huấn luyện gồm các từ và trọng số vào các mảng NonsensicalWord Lớp bao gồm các hàm: read_nonsensical_word, nonsensical_word. Dùng để đọc vào nội dung file chứa các từ stop-word và kiểm tra một từ nào đĩ cĩ phải là stop-wrod hay khơng Test Lớp bao gồm các hàm: cut_tag_name, test_event, set_tag. Dùng để kiểm thử dữ liệu đã được huấn luyện và gán nhãn cho văn bản bất kỳ Training Dùng cho chức năng huấn luyện TrainingFile Lớp bao gồm các hàm: cut_tag_name, read_training, read_all, set_frequency, set_frequency_all_data, feature_selection, write_train, write_all, update_training. Dùng để đọc nội dung các file trong dữ liệu huấn luyện, gán tần số xuất hiện cho từng từ và lọc những từ cĩ tần số nhỏ hơn mức tối thiểu (mặc định là 10) Main Lớp là giao diện đồ họa của chương trình, xử lý các sự kiện ứng với từng chức năng của chương trình Chức năng các hàm cụ thể được sử dụng trong chương trình phân loại văn bản: Tên hàm Mơ tả double get_distribution_xy(int context_arg, int tag_arg) Tính xác suất thực nghiệm của cặp ngữ cảnh (context_arg, tag_arg) và kết quả trả lại kiểu double double get_distribution_x(int context_arg, int tag_arg) Tính xác suất ngữ cảnh của ngữ cảnh contex_arg void set_feature() Hàm gán giá trị cho mảng đặc trưng. Cĩ giá trị 1 nếu đặc trưng xuất hiện trong dữ liệu huấn luyện, 0 nếu ngược lại double get_c() Trả lại giá trị tổng các đặc trưng của từng nhãn lớn nhất double get_z() Trả lại giá trị Z trong cơng thức tính các giá trị tham số của thuật tốn IIS double get_p_yx(int tag) Trả lại giá trị xác suất p(y|x) double get_empirical_expectation(int tag, int context) Trả lại giá trị kỳ vọng thực nghiệm ứng của cặp đặc trưng với nhãn tag và ngữ cảnh context double get_model_expectation(int tag, int context) Trả lại giá trị kỳ vọng mơ hình của cặp đặc trưng với nhãn tag và ngữ cảnh context double delta_lamda(int tag, int context) Trả lại giá trị Δλ của cặp đặc trưng (tag, context) void lamda(double delta_lamda_init, int loop) Tính trọng số λ cho các cặp đặc trưng với giá trị hội tụ là delta_lamda_init và số lần lặp tối đa là loop void write_lamda(String path_lamda, ArrayList variable, ArrayList lamda_arg) Ghi 2 mảng variable (các từ) và mảng trọng số lamda_arg thành file với đường dẫn là path_lamda write_all(String path_lamda) Ghi tồn bộ các giá trị trọng số ứng với từng cặp đặc trưng thành file với đường dẫn path_lamda boolean read_input(String path_test_file, boolean tieng_viet) Đọc file đầu vào cần gán nhãn. Trong đĩ path_test_file là đường dẫn của file đầu vào và tieng_viet là biến điều khiển dữ liệu đầu vào là tiếng việt (nếu true) hay tiếng anh. Trả lại là true nếu tồn tại file và false nếu ngược lại void set_lamda(LamdaFile lamda_arg) Gán giá trị trọng số λ cho từng đặc trưng tương ứng của văn bản cần gán nhãn void set_model_distribution(LamdaFile lamda_arg) Tính xác suất mà file đầu vào cần gán nhãn thuộc vào các các nhãn tương ứng. Và đưa ra nhãn cĩ xác suất là lớn nhất. Nghĩa là nhãn được gán cho văn bản đĩ void cut_tag_name(String path) Từ đường dẫn path (chỉ ra các file đã được huấn luyện), hàm sẽ gán tên các nhãn cĩ thể được gán cho văn bản cần phân loại vào một mảng boolean read_lamda_file(String path_lamda_file, int tag_arg) Đọc file đã được huấn luyện với đường dẫn path_lamda_file và cĩ nhãn là tag_arg rồi lưu vào mảng void read_all() Đọc tất cả các file đã được huấn luyện với đường dẫn tới các file huấn luyện đã được chỉ ra boolean read_nonsensical_word(String fileName) Đọc file stop-word với đường dẫn file stop-word là fileName boolean nonsensical_word(String word) Kiểm tra xem từ word cĩ phải là stop-word khơng. Nếu đúng kết quả trả lại là true và false nếu ngược lại void test_event() Thực hiện chức năng kiểm thử void set_tag() Thực hiện chức năng gán nhãn boolean read_training(String path, ArrayList variable, boolean tieng_viet) Đọc file cĩ trong dữ liệu huấn luyện với đường dẫn path vào mảng variable void read_all(String path, boolean tieng_viet) Đọc tồn bộ các file cĩ trong dữ liệu huấn luyện với đường dẫn path. Biến tieng_viet để thơng báo dữ liệu huấn luyện là tiếng việt (true) hay tiếng Anh (false) void set_frequency(ArrayList tag_arg, ArrayList frequency_arg) Gán giá trị tần số cho từng từ trong dữ liệu huấn luyện void set_frequency_all_data() Gán giá trị tần số cho tồn bộ các nhãn trong tập dữ liệu huấn luyện void feature_selection(double feature_selection) Lọc bỏ những đặc trưng cĩ tần số xuất hiện nhỏ hơn feature_selection void write_all(String path_frequency) Ghi các giá trị tần số ứng với các đặc trưng ra file