LUẬN VĂN: MÔ HÌNH MAXIMUM ENTROPY

Chia sẻ: Lan Lan | Ngày: | Loại File: PDF | Số trang:60

Thêm vào BST

Báo xấu

112
lượt xem 38
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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,

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: LUẬN VĂN: MÔ HÌNH MAXIMUM ENTROPY

ĐẠ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 KHOÁ 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 KHOÁ 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 soá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 soá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. i
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 hoà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 ii
Mục lục Chương 1: Tổng quát ..................................................................................................... 1 1.1 Đặt vấn đề .......................................................................................................................1 1.2 Giới thiệu mô hình cực đại entropy .................................................................................2 1.3 Mục tiêu của luận văn .....................................................................................................3 Chương 2: Các phương pháp phân loại văn bản ........................................................ 5 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 ...............................................5 2.2 Mô tả bài toán phân loại văn bản ........................................................................................5 2.3 Biểu diễn văn bản ...............................................................................................................6 2.4 Các phương pháp phân loại văn bản...................................................................................7 2.4.1 Naïve Bayes (NB).........................................................................................................7 2.4.2 k-Nearest Neighbor (kNN) ............................................................................................8 2.4.3 Linear Least Square Fit (LLSF) ....................................................................................9 2.4.4 Support Vector Machine (SVM)..................................................................................10 Chương 3: Mô hình cực đại entropy .......................................................................... 12 3.1 Tổng quát mô hình cực đại entropy ...................................................................................12 3.2 Mô hình cực đại entropy ....................................................................................................15 3.2.1 Dữ liệu huấn luyện ......................................................................................................15 3.2.2 Thống kê, đặc trưng và ràng buộc ..............................................................................16 3.2.3 Nguyên lý cực đại entropy...........................................................................................17 3.2.4 Tham số hình thức ......................................................................................................18 3.2.5 Mối quan hệ với cực đại Likelihood.............................................................................20 3.2.6 Tính các tham số .........................................................................................................20 3.3 Lựa chọn đặc trưng............................................................................................................22 3.3.1 Ý nghĩa của việc lựa chọn đặc trưng...........................................................................22 3.3.2 Cơ sở lựa chọn đặc trưng ...........................................................................................24 3.3.3 Giá trị gần đúng...............................................................................................................26 Chương 4: Thực nghiệm phân loại văn bản .............................................................. 29 4.1 Thống kê kết quả thực nghiệm ..........................................................................................29 iii
4.2 Các thành phần và chức năng của chương trình ..............................................................33 4.2.1 Chức năng huấn luyện ................................................................................................34 4.2.2 Chức năng kiểm thử ....................................................................................................36 4.2.3 Chức năng gán nhãn...................................................................................................37 4.3 Ứng dụng chặn nội dung web ............................................................................................39 4.3.1 Kỹ thuật lọc web Blue Coat .........................................................................................39 4.3.2 Chức năng ứng dụng chặn nội dung web ...................................................................40 Chương 5: Kết luận ...................................................................................................... 44 5.1 Kết quả đạt được ...............................................................................................................44 5.2 Những hạn chế và hướng giải quyết .................................................................................45 Tài liệu tham khảo......................................................................................................... 46 Phụ lục ........................................................................................................................... 48 iv
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 v
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 vi
Chương 1: Tổng quát 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ụ 1
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 2
đầ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 3
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. 4
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], Naï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 toá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ự đoá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 toá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ữ 5
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 toán IIS để tính toá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 toán. Hầu hết các thuật toá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 toán IIS chỉ có thể tính toá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 di đại diện cho một văn bản tương ứng trong không gian các từ w: di (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 đó ( di ); 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: TF ( w n ) TF ( w1 ) TF ( w 2 ) di( , ,..., ) ∑ TF ( w i ) ∑ TF ( w i ) ∑ TF 2 ( w i ) 2 2 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): m IDF(wi ) = log( ) DF(wi ) TFIDF ( wi ) = TF ( wi ).IDF ( wi ) Trong đó: o m chính là số văn bản huấn luyện o DF(wi) là số văn bản có chứa từ wi 6
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 di 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 Naï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 toá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: P ( d | C i ) P (C i ) P (C i | d ) = P (d ) 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 7
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 toá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 x sẽ được tính như sau: ∑ sim ( x, d ). y (d , c W ( x, c j ) = ) − bj i i j d i ∈{ kNN } Trong đó: o y( d i ,cj) ∈ {0,1}, với • y= 0: văn bản d i không thuộc chủ đề cj • y= 1: văn bản d i thuộc chủ đề cj o sim( x , d i ): mức độ giống nhau giữa văn bản x cần phân loại và văn bản d i . Với: • sim( x , d i )= ( x . d i )/(|| x ||.|| d i ||) 8
o 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 toá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 toá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 FLS = argmin || FA− B ||2 F Trong đó: o 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) o 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. 9
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 d i như sau: di *w+b = 0 Đặt ⎧ + 1, d i .w + b > 0 h ( d i ) = sign ( d i .w + b ) = ⎨ ⎩ − 1, d i .w + b < 0 10
Như vậy h( d i ) biểu diễn sự phân lớp của d i vào 2 lớp + và lớp -. Gọi yi = {±1}, yi = +1 văn bản d i thuộc lớp +, yi = -1 văn bản d i thuộc lớp -. Để có siêu mặt phẳng h ta đi giải bài toán: Tính Min|| w || với w và b thoản mãn điều kiện: ∀i ∈ 1, n : y i ( sign ( d i .w + b)) ≥ 1 Bài toán SVM có thể được giải bằng toá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 toàn bộ dữ liệu. Khi dữ liệu có sự thay đổi thì kết quả cũng thay đổi. 11
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 toán tính trọng số cũng như lựa chọn các đặc trưng cho bài toá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 toá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 toá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ự đoán đó là “dans”. Mô hình khác tuân theo ràng buộc này dự đoá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 12