BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
BÙI THỊ THANH XUÂN
MỘT SỐ PHƯƠNG PHÁP NGẪU NHIÊN CHO
BÀI TOÁN CỰC ĐẠI HÓA XÁC SUẤT HẬU NGHIỆM
KHÔNG LỒI TRONG HỌC MÁY
LUẬN ÁN TIẾN SĨ HỆ THỐNG THÔNG TIN
HÀ NỘI−2020
BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
BÙI THỊ THANH XUÂN
MỘT SỐ PHƯƠNG PHÁP NGẪU NHIÊN CHO
BÀI TOÁN CỰC ĐẠI HÓA XÁC SUẤT HẬU NGHIỆM
KHÔNG LỒI TRONG HỌC MÁY
Ngành: Hệ thống thông tin
Mã số: 9480104
LUẬN ÁN TIẾN SĨ HỆ THỐNG THÔNG TIN
TẬP THỂ HƯỚNG DẪN KHOA HỌC:
1. PGS.TS. THÂN QUANG KHOÁT
2. TS. NGUYỄN THỊ OANH
HÀ NỘI−2020
LỜI CAM ĐOAN
Tôi xin cam đoan các kết quả trình bày trong luận án là công trình nghiên
cứu của bản thân nghiên cứu sinh trong thời gian học tập và nghiên cứu tại
Đại học Bách khoa Hà Nội dưới sự hướng dẫn của tập thể hướng dẫn khoa
học. Các số liệu, kết quả trình bày trong luận án là hoàn toàn trung thực.
Các kết quả sử dụng tham khảo đều đã được trích dẫn đầy đủ và theo đúng
quy định.
Hà Nội, ngày tháng 02 năm 2020
Nghiên cứu sinh
Bùi Thị Thanh Xuân
TẬP THỂ HƯỚNG DẪN KHOA HỌC
LỜI CẢM ƠN
Trong quá trình nghiên cứu và hoàn thành luận án này, nghiên cứu sinh
đã nhận được nhiều sự giúp đỡ và đóng góp quý báu. Đầu tiên, nghiên cứu
sinh xin được bày tỏ lòng biết ơn sâu sắc tới tập thể hướng dẫn: PGS.TS.
Thân Quang Khoát và TS. Nguyễn Thị Oanh. Các thầy cô đã tận tình hướng
dẫn, giúp đỡ nghiên cứu sinh trong suốt quá trình nghiên cứu và hoàn thành
luận án. Nghiên cứu sinh xin chân thành cảm ơn Bộ môn Hệ thống thông tin
và Phòng thí nghiệm Khoa học dữ liệu, Viện Công nghệ thông tin và truyền
thông - Trường Đại học Bách khoa Hà Nội, nơi nghiên cứu sinh học tập đã
tạo điều kiện, cho phép nghiên cứu sinh có thể tham gia nghiên cứu trong
suốt thời gian học tập. Nghiên cứu sinh xin chân thành cảm ơn Phòng Đào
tạo - Trường Đại học Bách Khoa Hà Nội đã tạo điều kiện để nghiên cứu sinh
có thể hoàn thành các thủ tục bảo vệ luận án tiến sĩ. Cuối cùng, nghiên cứu
sinh xin gửi lời cảm ơn sâu sắc tới gia đình, bạn bè đồng nghiệp đã luôn động
viên, giúp đỡ nghiên cứu sinh vượt qua khó khăn để đạt được những kết quả
nghiên cứu như hôm nay.
MỤC LỤC
DANH MỤC CÁC TỪ VIẾT TẮT VÀ THUẬT NGỮ . . . . . . . . . . iv
DANH MỤC HÌNH VẼ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi
DANH MỤC BẢNG. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . x
DANH MỤC KÝ HIỆU TOÁN HỌC . . . . . . . . . . . . . . . . . . . . . . . . . . xi
MỞ ĐẦU . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
CHƯƠNG 1. MỘT SỐ KIẾN THỨC NỀN TẢNG. . . . . . . . . . . . . . 9
1.1. Tối ưu không lồi ........................ .......... ......... ......... 9
1.1.1. Bài toán tối ưu tổng quát. . . . . . . . . . . . . ........................ . . 9
1.1.2. Tối ưu ngẫu nhiên . . . . . . . . . . ........................ . . . . . . . . . . . 10
1.2. Mô hình đồ thị xác suất .......................... . . . . . . . . . . . . . . . . . 14
1.2.1. Giới thiệu ... .. . . . . . . . . . . . . . . . . . . . . . ....................... . . . . 14
1.2.2. Một số phương pháp suy diễn.......... . . . . . . . . . . . . . . . . . . . . .... 15
1.3. Bài toán cực đại hóa xác suất hậu nghiệm ......................... 18
1.3.1. Giới thiệu bài toán MAP .... . . . . . . . . . . . . . . . . . . . . . . . ........... 18
1.3.2. Một số phương pháp tiếp cận ......................... ......... 19
1.4. Mô hình chủ đề.. . . . . . . . . . . ......................... . . . . . . . . . . . . . . . 21
1.4.1. Giới thiệu về mô hình chủ đề ........................ . . . . . . . . . . 21
1.4.2. Mô hình Latent Dirichlet Allocation ............... . . . . . . . . . . . . 22
1.4.3. Suy diễn hậu nghiệm trong mô hình chủ đề ................. .. . 25
1.5. Thuật toán OPE .................................. . . . . . . . . . . . . . . . . 28
1.6. Một số thuật toán ngẫu nhiên học LDA........................ . . . . 32
1.7. Kết luận chương 1 . . . . . . . . . . . . . . . . . . . . ..................... .. . . . . . . 33
CHƯƠNG 2. NGẪU NHIÊN HÓA THUẬT TOÁN TỐI ƯU
GIẢI BÀI TOÁN SUY DIỄN HẬU NGHIỆM
TRONG MÔ HÌNH CHỦ ĐỀ. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.1. Giới thiệu .. .. . . . . . . . . . . . . . . . . . . . . . ....................... . . . . . . . . . 35
2.2. Đề xuất mới giải bài toán MAP trong mô hình chủ đề ............. 36
2.3. Các thuật toán học ngẫu nhiên cho mô hình LDA...... . . . . . . . . . . . . 40
2.4. Đánh giá thực nghiệm . . . . . . . . . . . . . . ....................... . . . . . . . . 41
2.4.1. Các bộ dữ liệu thực nghiệm. . . . . ....................... . . . . . . . . 42
i