Luận văn Mô hình Maximum entropy và ứng 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
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
Đặt vấn đề.......................................................................................................................1
Giới thiệu mô hình cực đại entropy.................................................................................2
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
1.1
1.2
1.3
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 (w1 )
TF (w2 )
TF (wn )
di(
,
,...,
)
2
2
2
∑ TF (wi ) ∑ TF (wi )
∑ TF (wi )
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(w ) = log(
)
i
DF(w )
i
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 | Ci )P(Ci )
P(Ci | 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:
W (x,c j ) =
sim(x,d ).y(d ,c ) − b
∑
i
i
j
j
di∈{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:
d i * w + b = 0
Đặt
⎧
⎨
⎩
+ 1, d i .w + b > 0
−1, d i .w + b < 0
h(d i ) = sign (d i .w + b) =
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 : yi (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
đó 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 toá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 hoàn toà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 toá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
13
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: toà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 toán học của những nguyên lý cổ xưa một
cách khôn ngoan...
14
3.2 Mô hình cực đại entropy
Chúng ta xem xét một bài toá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 toá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 toá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 toá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 toà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 toà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 toán, chúng ta theo rõi cách xử lý của một bài toá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
toá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:
̃
1
~
p(x, y) =
×
(số luần xuất hiện của cặp (x,y) trong mẫu)
N
Trường hợp đặc biệt là cặp (x,y) sẽ không xuất hiện trong toàn bộ mẫu, hay sẽ xuất
hiện trong toàn bộ mẫu.
15
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 toá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
1
0
⎧
⎨
⎩
f (x, y) =
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:
~
~
E(f) = p(x,y).f(x,y)
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ư toà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:
~
E(f ) = p(x).p(y| x).f (x,y)
với mọi cặp (x,y) (2)
∑
16
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:
~
E( f ) = E( f )
(3)
Từ (1), (2) và (3) ta có:
~
~
p(x).p(y | x). f (x, y) =
p(x, y). f (x, y)
x, y
∑
∑
x, y
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 toá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 toá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 toá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:
17
~
H ( p) = −
p(x).p(y | x).log( p(y | x))
(5)
∑
x, y
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 toà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):
p* = arg max 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 toá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 toá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 toán tối ưu hóa các ràng buộc ban đầu,
find p * = arg max H ( p)
như bài toán căn bản.
với p € C
¾ 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:
~
Λ( p,λ) = H ( p) + λ (E( f ) − E( f )
(7)
∑
i
i
i
18
¾ 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 toà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 đó.
Pλ = arg max Λ( p, λ )
Ψ (λ ) = Λ ( p, λ )
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
toán cụ thể sử dụng các phép tính đơn giản. Chúng ta tìm được:
1
pλ (y | x) = (
exp( λ . f (x, y)))
∑
i
i
(10)
i
Zλ (x)
~
~
Ψ(λ) = − p(x).logZ (x)+ λ E( f )
(11)
∑
∑
λ
i
i
x
i
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 toàn bộ x:
Z (x) =
exp(
∑y ∑i
λ f (x, y))
(12)
λ
i
i
¾ Cuối cùng, chúng ta đưa ra bài toán tối ưu hóa đối ngẫu không ràng buộc:
find λ* = argmaxλ Ψ(λ)
Thoá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 toán nền tảng
và đối ngẫu là có liên quan chặt chẽ. Đây là cách trong hoàn cảnh hiện tại. Giả thiết rằng
λ* là giải pháp cho bài toán đối ngẫu. Khi đó pλ* là giải pháp cho bài toá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 toá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.
19
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ự đoán trước bởi xác
̃
̃
suất mô hình p được định nghĩa như sau:
~
L (p)=log p(y|x)p(x,y) = x,y p(x,y).logp(y|x)
~
~
∑
∏
p
(13)
x,y
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λ:
Ψ(λ) = L~ (pλ )
(14)
p
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ố toà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 toán kể cả đơn giản nhất, thì λ* mà cực đại ψ(λ) là không thể
tính toá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 toán cực đại
entropy, kỹ thuật này sẽ mang lại thuật toá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 toán cực đại entropy là
thuật toán “improved iterative scaling” của Darroch và Ratcliff (1972).
20
Thuật toá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 toán 1: Improved Iterative Scaling (IIS)
Input: hàm đặc trưng f , f ,..., f ; phân phối thực nghiệm p(x,y)
̅
1
2
n
Ouput: Giá trị tham số tối ưu λ*i; xác suất mô hình tối ưu pλ*
1. Bắt đầu với λi = 0 với mọi i € {1, 2,..., n}
2. Với mọi i € {1, 2,..., n}
a) Sử dụng ∆λi để tính:
~
#
~
x,y p(x)p(y | x) fi (x, y)exp(Δλi f (x, y)) = E( fi )
(16)
∑
#
Trong đó: f ( x, y ) =
f i ( x, y )
(17)
∑
i =1
b) Cập nhập giá trị của λi: λi = λi + ∆λi
3. 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 toán là bước 2.a, việc tính toá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:
~
p( fi )
1
Δλi =
log(
)
M
pλ ( fi )
Nếu f#(x,y) không phải là hằng số, khi đó ∆λi phải được tính toá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:
21
g(an )
αn+1 =αn −
(18)
′
g (an )
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 toá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 toá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 toá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 toá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 toàn bộ bài toá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
22
Tải về để xem bản đầy đủ
60 trang
15/04/2025
120
Bạn đang xem 30 trang mẫu của tài liệu "Luận văn Mô hình Maximum entropy và ứng dụng", để tải tài liệu gốc về máy hãy click vào nút Download ở trên.
File đính kèm:
- luan_van_mo_hinh_maximum_entropy_va_ung_dung.pdf
