Phương thức học máy trực tuyến dựa trên mô hình Bayes

- TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘIVIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG—————*—————Phạm Xuân CườngPHƯƠNG THỨC HỌC MÁY TRỰC TUYẾNDỰA TRÊN MÔ HÌNH BAYESCHUYÊN NGÀNH: KHOA HỌC MÁY TÍNHLUẬN VĂN THẠC SỸ KHOA HỌCCHUYÊN NGÀNH KHOA HỌC MÁY TÍNHNGƯỜI HƯỚNG DẪN KHOA HỌCTS Đinh Viết SangHÀ NỘI 10-2017 SĐH.QT9.BM11 Ban hành lần 1 ngày CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM Độc lập – Tự do – Hạnh phúc BẢN XÁC NHẬN CHỈNH SỬA LUẬN VĂN THẠC SĨ Họ và tên tác giả luận văn : Phạm Xuân Cường Đề tài luận văn: Phương thức học máy trực tuyến dựa trên Bayes Chuyên ngành: Khoa học máy tính Mã số SV: CB160558 Tác giả, Người hướng dẫn khoa học và Hội đồng chấm luận văn xác nhận tác giả đã sửa chữa, bổ sung luận văn theo biên bản họp Hội đồng ngày.
- với các nội dung sau.
- Bổ sung thêm mô tả về cách đặt tên thuật toán do tác giả đề xuất trước khi đưa ra bảng kết quả thử nghiệm.
- Bổ sung thêm thông tin về thời gian thực hiện, độ phức tạp của thuật toán mà tác giả đề xuất.
- Ngày 09 tháng 11 năm 2017 Giáo viên hướng dẫn Tác giả luận văn CHỦ TỊCH HỘI ĐỒNG PHIẾU GIAO NHIỆM VỤ LUẬN VĂN TỐT NGHIỆP1.
- Thông tin về học viênHọ và tên sinh viên: Phạm Xuân CườngLớp: Khoa học máy tính Hệ đào tạo: Thạc sỹ Khoa họcThời gian làm LVTN: Từ ngày đến .
- Mục đích nội dung của LVTNNghiên cứu và đề xuất giải thuật học máy trực tuyến mới dựa trên Bayes.3.
- Các nhiệm vụ cụ thể của Luận văn:• Nghiên cứu phương thức học máy trực tuyến.• Đề xuất giải thuật học máy mới dựa trên Bayes.• Đề xuất giải thuật học máy mới dựa trên cây Hoeffding và ma trận ngẫu nhiên.• So sánh và đánh giá các kết quả thử nghiệm4.
- Lời cam đoan của học viên:Tôi Phạm Xuân Cường cam kết Luận văn là công trình nghiên cứu của bản thân tôi dưới sự hướng dẫncủa Tiến sỹ Đinh Viết Sang.
- Các kết quả nêu trong luận văn là trung thực, không phải là sao chép toànvăn của bất kỳ công trình nào khác.Hà Nội, ngày 23 tháng 10 năm 2017Tác giả Luận vănPhạm Xuân Cường5.
- Xác nhận của GVHD:Hà Nội, ngày 23 tháng 10 năm 2017Giáo viên hướng dẫnTS Đinh Viết SangHọc viên: Phạm Xuân Cường CB160558 Khóa 2016B Lớp CH KHMT 1 LỜI CẢM ƠNLời đầu tiên tôi xin chân thành bày tỏ lòng biết ơn sâu sắc tới giảng viên Tiến sỹ Đinh Viết Sang, người đãđào tạo, định hướng và chỉ bảo tôi tận tình trong quá trình thực hiện luận văn tốt nghiệp này.
- Những lời khuyênvà phản biện của thầy đã giúp tôi nhận ra những thiếu sót trong quá trình nghiên cứu để hoàn thiện luận văn vớikết quả tốt nhất.Tôi cũng xin gửi lời cảm ơn sâu sắc tới các thành viên trong nhóm nghiên cứu tại Đại học Griffith, Australia:giáo sư Alan Wee-chung Liew, anh Nguyễn Tiến Thành, chị Nguyễn Thị Thu Thủy đã giúp đỡ tôi rất nhiềutrong con đường nghiên cứu học thuật.
- Tôi xin đặc biệtgửi lời cảm ơn tới vợ tôi, người luôn thấu hiểu, cảm thông và liên tục hỗ trợ tôi trong quá trình thực hiện luânvăn Thạc sỹ này.Hà Nội, ngày 26 tháng 10 năm 2017Tác giả luận vănPhạm Xuân CườngHọc viên: Phạm Xuân Cường CB160558 Khóa 2016B Lớp CH KHMT 2 DANH SÁCH CÁC BÀI BÁO XUẤT BẢN GẦN ĐÂY1.
- International Conference on Digital Image Computing: Techniques and Applications (DICTA),2016.Học viên: Phạm Xuân Cường CB160558 Khóa 2016B Lớp CH KHMT 3 Mục lụcLỜI CẢM ƠN 3DANH SÁCH BẢNG 7DANH SÁCH HÌNH VẼ 8DANH MỤC TỪ VIẾT TẮT 91 GIỚI THIỆU 101.1 Đặt vấn đề.
- 101.2 Cấu trúc luận văn.
- 121.3 Các ký hiệu toán học.
- 132 TỔNG QUAN CÁC PHƯƠNG PHÁP HỌC TRỰC TUYẾN 152.1 Phương pháp học trực tuyến tuyến tính.
- 172.2 Phương pháp học trực tuyến dựa trên cây phân loại.
- 202.3 Phương pháp học trực tuyến Bayes.
- 222.4 Phương pháp học trực tuyến tập hợp.
- 242.5 Phương pháp đánh giá và so sánh.
- 302.5.1 Các độ đo hiệu quả.
- 362.6 Các nghiên cứu đề xuất.
- 412.6.1 Câu hỏi nghiên cứu và mục tiêu.
- 412.6.2 Tầm quan trọng của nghiên cứu.
- 423 MÔ HÌNH HỌC ONLINE DỰA TRÊN LÝ THUYẾT BAYES 443.1 Các nghiên cứu liên quan.
- 45Học viên: Phạm Xuân Cường CB160558 Khóa 2016B Lớp CH KHMT 4 3.1.1 Suy diễn biến thiên cho phân phối chuẩn nhiều chiều.
- 453.2 Mô hình đề xuất.
- 494 MÔ HÌNH HỌC ONLINE DỰA TRÊN CÂY HOEFFDING VÀ PHÉP CHIẾU NGẪU NHIÊN 544.1 Các nghiên cứu liên quan.
- 554.1.1 Bộ phân loại cây Hoeffding.
- 554.1.2 Các phép chiếu ngẫu nhiên.
- 584.2 Mô hình đề xuất.
- 605 THỬ NGHIỆM VÀ ĐÁNH GIÁ 665.1 Tập dữ liệu thử nghiệm.
- 665.2 Cấu hình thử nghiệm mô hình và phương pháp so sánh.
- 675.3 Kết quả thử nghiệm và so sánh.
- 705.4 Dữ liệu nhiễu.
- 76KẾT LUẬN 77TÀI LIỆU THAM KHẢO 79Học viên: Phạm Xuân Cường CB160558 Khóa 2016B Lớp CH KHMT 5 Danh sách bảng1.1 Các ký hiệu toán học.
- 142.1 Ví dụ ma trận Confusion.
- 325.1 Thông tin về các tập dữ liệu dùng để đánh giá mô hình.
- 675.2 Trung bình và phương sai theo sai số của thuật toán đề xuất và các thuật toán so sánh.
- 715.3 Trung bình và phương sai theo F1 của thuật toán đề xuất và các thuật toán so sánh.
- 74Học viên: Phạm Xuân Cường CB160558 Khóa 2016B Lớp CH KHMT 6 Danh sách hình vẽ1.1 Các đặc điểm của BigData.
- 112.1 Phân loại các phương thức học trực tuyến.
- 152.2 Quy trình hoạt động của thuật toán học trực tuyến.
- 162.3 Minh họa bằng màu sắc cho confusion matrix chưa chuẩn hóa và confusion matrix đã chuẩn hóa 332.4 Đường cong P-R trong bài toán phân loại.
- 353.1 Mô tả trực quan quy trình hoạt động của thuật toán VIGO với kích thước lô là |B.
- 534.1 Quy trình hoạt động của thuật toán RP Hoeffding.
- 655.1 Quy trình thử nghiệm trong mô hình đề xuất.
- 695.2 Thống kê độ hiệu quả của các thuật toán trên 25 tập dữ liệu.
- 725.3 Kết quả kiểm định thống kê sai số của thuật toán RP Hoeffding với các thuật toán khác trên 25tập dữ liệu.
- 745.4 Kết quả kiểm định thống kê F1 của thuật toán RP Hoeffding và các thuật toán khác trên 25 tậpdữ liệu.
- 755.5 Trung bình sai số của thuật toán VIGO và 3 thuật toán PA, SCW, AROW trên 25 tập dữ liệu nhiễu 76Học viên: Phạm Xuân Cường CB160558 Khóa 2016B Lớp CH KHMT 7 Danh mục từ viết t ắtSTT Từ viết tắt Ý nghĩa1 VI Variational Inference2 VIGO Variational Inference for Gaussian3 PA Passive Aggressive learning4 SOP Second-order Perceptron5 GMM Gaussian Mixture Model6 SCW Soft Confidence Weighted7 ALMA Approximate Large Margin Algorithm8 ROMMA Relaxed Online Maximum Margin Algorithms9 OGD Online Gradient DescentHọc viên: Phạm Xuân Cường CB160558 Khóa 2016B Lớp CH KHMT 8 Chương 1GIỚI THIỆU1.1 Đặt vấn đềSự phát triển nhanh chóng của công nghệ lưu trữ cũng như các công cụ xử lý dữ liệu tiên tiến hiện nay làtiền đề để giúp các hệ thống thông tin có thể thu thập được một khối lượng rất lớn dữ liệu.
- Hình sau mô tả chi tiết vềkhái niệm BigData.BigDataSố lượngSự đa dạngTốc độ phát triểnĐộ tin cậyGiá trịHình 1.1: Các đặc điểm của BigDataTrong thời đại bùng nổ công nghệ thông tin hiện nay, việc nắm trong tay lượng dữ liệu lớn sẽ giúp các doanhHọc viên: Phạm Xuân Cường CB160558 Khóa 2016B Lớp CH KHMT 9 nghiệp hiểu biết hơn về khách hàng của họ để đưa ra các chiến lược kinh doanh hiệu quả hoặc tự động hóa cácquá trình làm việc giúp tăng năng suất lao động.
- Cụ thể hơn, theo báo cáo của trung tâm BCS [1] chúng ta đangtạo ra 1 quintillion (1018) byte dữ liệu mỗi ngày và con số này sẽ tăng gấp đôi mỗi năm.
- Cũng trong báo cáotrên, việc áp dụng các kỹ thuật phân tích dữ liệu giúp các công ty tăng 33% lợi nhuận.
- Học máy là một trongnhững kỹ thuật phân tích dữ liệu được áp dụng để khai phá các mẫu ẩn trong dữ liệu đã thu thập được.
- Phươngpháp này được sử dụng phổ biến trong các bài toàn phân loại như phân loại bệnh nhân dựa vào cấu trúc gen,phân loại ý định câu hỏi của khách hàng trong ứng dụng Chatbot hay các bài toán dự đoán giá nhà đất của mộtkhu vực.
- Tuy nhiên, các thuật toán học máy truyền thống hiện nay đang gặp vấn đề là khó thích nghi hoặc thậmchí là không hoạt động được đối với BigData.
- Một số thuật toán cần phải lưu trữ dữ liệu trong bộ nh ớ của máykhi huấn luyện, điều này là không khả thi trong thực tế khi dữ liệu rất lớn hoặc không có sẵn tại một thời điểmmà đến liên tục (streaming data).
- Một số khác mặc dù có hiệu quả tốt nhưng thời gian huấn luyện rất lâu khiếnchúng không khả thi trong các hệ thống thời gian thực (real-time) khi liên tục phải huấn luyện lại mô hình.Để giải quyết những vấn đề kể trên của học máy, các nhà nghiên cứu đã giành nhiều sự quan tâm cho lĩnhvực có tên gọi là học máy trực tuyến (Online Learning) trong những năm gần đây.
- Học máy trực tuyến là mộtkỹ thuật học quan trọng, trong đó các mô hình học có thể được cập nhật theo thời gian khi dữ liệu mới đến màkhông cần phải học lại toàn bộ tập dữ liệu cũ.
- Đặc tính này rất phù hợp cho các ứng dụng mà dữ liệu đến liêntục theo luồng như các giao dịch trong hệ thống chứng khoán hoặc các bộ phân tích dữ liệu nhận được từ cảmbiến môi trường.Trong luận văn này, tác giả sẽ tập trung giới thiệu về học máy trực tuyến cho bài toán học có giám sát, quytrình thực hiện của một thuật toán học trực tuyến, phân loại và một số thuật toán học trực tuyến nổi bật đã đượcđề xuất.
- Ngoài ra, tác giả cũng sẽ giới thiệu về hai thuật toán học trực tuyến mới (dựa trên lý thuyết Bayes vàthuật toán phân loại cây Hoeffding) là công tr ình nghiên cứu của tác giả và đồng nghiệp.
- Hai thuật toán này đãđạt được các kết quả rất tốt khi so sánh với các thuật toán học trực tuyến hiện có.1.2 Cấu trúc luận vănNội dung luận văn được chia làm 5 chương, trong đó chương 1 nhằm giới thiệu về bài toán, các vấn đề còntồn tại.
- Sau đó, tác giả tiến hành mô tả tổng quan về học máy trực tuyến cùng với các phương pháp nổi bật hiệnnay trong Chương 2.
- Chương 3 và Chương 4 tác giả mô tả 2 phương pháp học trực tuyến mới mà tác giả vàđồng nghiệp đề xuất (đã được công bố tại hội nghị DICTA 2016 và 2017).
- Cuối cùng, tác giả sẽ mô tả các kếtquả thử nghiệm và đánh giá của hai mô hình với các thuật toán học máy trực tuyến hiện nay cùng với các kếtluận và hướng phát tr iển tiếp theo trong Chương 5.1.3 Các ký hiệu toán họcTrước khi đi sâu vào phân tích các thuật toán học máy trực tuyến trong Chương 2, tác giả định nghĩa các kýhiệu toán học trong các công thức theo bảng sau:Học viên: Phạm Xuân Cường CB160558 Khóa 2016B Lớp CH KHMT 10 Ký hiệu Ý nghĩaX Tập dữ liệu quan sát (Tập huấn luyện)x = (x(1),x(2.
- Trong trường hợp r là biến ngẫu nhiên rời rạc thì p(r)được hiểu là mật độ xác suất của rM Số nhãn lớp của tập dữ liệuN Số quan sát trong tập dữ liệuY Tập nhãn lớp của dữ liệu.
- Y = {−1,1} trong trường hợp phân lớp nhị phân hoặcY M} trong trường hợp nhiều lớp.µ, Σ Trung bình và ma trận hiệp phương sai của phân phối chuẩn nhiều chiềuΛ Ma trận nghịch đảo của ma trận hiệp phương sai Λ = Σ−1D Số chiều của dữ liệuW0,v0Giá trị khởi tạo của ma trận mở rộng và bậc tự do của phân phối Whilshart q(Λ)m0,β0Giá trị khởi tạo của vector trung bình và độ mở rộng của phân phối chuẩn q(µ)m,H vector trung bình và ma trận precision của phân phối chuẩn q(µ.
- N(µ|m,H−1)W,v Ma trận mở rộng và bậc tự do của phân phối Wilshart q(Λ.
- Vết của ma trận (Tổng các thành phần trên đường chéo chính)Γ.
- Hàm dấu, nhận giá trị {−1, 0,1} tương ứng với các trường hợp.
- và < 0I Hàm chỉ thị cho kết quả là 1 nếu thỏa mãn điều kiện, 0 trong các trường hợp khácwtVector trọng số tại thời điểm t của thuật toán tuyến tính(·)TThủ tục chuyển vịk·k Chuẩn Euclide (Chuẩn L2)Bảng 1.1: Các ký hiệu toán họcHọc viên: Phạm Xuân Cường CB160558 Khóa 2016B Lớp CH KHMT 11 Chương 2TỔNG QUAN CÁC PHƯƠNG PHÁPHỌC TRỰC TUYẾNChương 2 của luận văn sẽ giới thiệu tổng quan về một số thuật toán học trực tuyến phổ biến và nổi bật đãđược công bố.
- Để thuận tiện cho việc giải thích ý tưởng cũng như phân tích ưu điểm và nhược điểm, các thuậttoán được chia làm 4 nhóm như minh họa trong hình sau:Học máy trực tuyếnHọc máy trực tuyến tuyến tínhHọc máy trực tuyến dựa trên BayesianHọc máy trực tuyến dựa trên câyHọc máy trực tuyến kết hợpHình 2.1: Phân loại các phương thức học trực tuyếnCác thuật toán học trực tuyến đều có chung một quy trình tổng quát bao gồm 3 bước như sau:• Dự đoán: Khi một quan sát xtmới tới, mô hình học hiện tại Ltsẽ được dùng để dự đoán nhãn của xt, kýhiệu là ˆyt.• Tính hàm tổn thất: Do bài toán là học trực tuyến có giám sát, nhãn đúng của xtcó thể biết được ký hiệulà yt, dựa trên cặp (yt, ˆyt), ta tính hàm tổn thất để đo sự khác biệt giữa nhãn dự đoán và nhãn thật.• Cập nhật: Nếu có tổn thất xảy ra trên cặp (yt, ˆyt), mô hình học sẽ được cập nhật (Lt→Lt+1) sử dụng quanHọc viên: Phạm Xuân Cường CB160558 Khóa 2016B Lớp CH KHMT 12 sát xtvà nhãn thật của nó yt.Tùy từng cách tiếp cận mà mỗi bước trong quy trình tổng quát sẽ có những khác biệt ví dụ như dùng các dạnghàm tổn thất khác nhau hoặc mô hình phân lớp khác nhau.
- Tác giả luận văn sẽ tiến hành giới thiệu tổng quancho các tiếp cận dựa trên quy trình này.Quy trình hoạt động của các thuật toán học trực tuyến được khái quát theo hình sau:Nhận quansát mới xtHọc từquan sát xtThu đượcmô hình tạithời điểm tHình 2.2: Quy trình hoạt động của thuật toán học trực tuyến2.1 Phương pháp học trực tuyến tuyến tínhPhương pháp học trực tuyến tuyến tính sử dụng hàm phân loại tuyến tính để phân lớp cho các quan sát.Trong trường hợp phân lớp nhị phân tức là tập nhãn gồm 2 giá tr ị Y hàm phân loại có dạng:ˆyt= sign( ft(xt.
- Trong trường hợp phân loại cho tập nhiều lớp Y = {1.
- ,K} hàm phân loại có dạng ft,i(xt.
- Nhãn lớp dự đoán dựa trên cực đại hàm phân loạitrên toàn bộ tập nhãn:ˆyt= arg maxi∈{1,...,K}ft,i(xt.
- arg maxi∈{1,...,K}wTt,i·xt(2.2)Các thuật toán học trực tuyến tuyến tính khác nhau sử dụng các hàm tổn thất l(yt, ˆyt) khác nhau và cơ chếcập nhật mô hình Lt→ Lt+1, cụ thể là cách cập nhật vector trọng số wt→ wt+1khác nhau.
- Hai dạng hàm tổnthất phổ biến được sử dụng trong các phương pháp học trực tuyến tuyến tính là hàm tổn thất 0-1 (Zero-One) vàhàm tổn thất Hinge.
- Hàm tổn thất 0-1 được định nghĩa như sau:l(yt, ˆyt.
- 01 nếu ngược lại(2.3)Khi sử dụng hàm tổn thất 0-1, mô hình sẽ được cập nhật nếu nhãn dự đoán cho xtbởi mô hình hiện tại ˆytkhác với nhãn lớp đúng yt.
- Perceptron [2] là giải thuật học trực tuyến lâu đời nhất dựa trên tiếp cận này vớiHọc viên: Phạm Xuân Cường CB160558 Khóa 2016B Lớp CH KHMT 13 phiên bản ban đầu được phát triển cho phân lớp nhị phân.
- Crammer and Singer [3] sau đó mở rộng thuật toánPerceptron cho trường hợp nhiều lớp.
- Hàm tổn thất Hinge cho trường hợp phân loại nhị phân được định nghĩanhư sau:l(yt, ˆyt.
- max(0,1 −yt(wTt·xt)) (2.4)Trong trường hợp phân loại nhiều lớp, hàm tổn thất Hinge được định nghĩ như sau:l(yt, ˆyt.
- max(0,1 −(wTt,yt·xt−maxi6=ytwTt,i·xt))(2.5)Hàm tổn thất Hinge được định nghĩa dựa trên biểu thức yt(xt), được gọi là lề của quan sát (xt, yt) ứng vớihàm phân loại ft.
- |wTt·xt| được gọi là độ tin cậy của dự đoán trong đógiá trị này dương và càng lớn có nghĩa là độ tin cậy dự đoán đúng càng cao.
- Trong trường hợp cho nhiều lớp,giá trị dự đoán wTt,yt·xtcàng lớn hơn giá trị lớn nhất ứng với các nhãn lớp còn lại thì maxi6=ytwTt,i·xtdự đoán làcàng tin cậy.
- Không giống như hàm tổn thất 0-1, khi sử dụng hàm tổn thất Hinge mô hình học có thể sẽ đượccập nhật cả khi dự đoán sai yt(wTt·xt.
- 0 và thậm chí là dự đoán đúng ytft(xt.
- 1 mô hình học sẽ được cập nhật.
- Dựa trên cách cập nhật vector trọngsố wt→ wt+1, các thuật toán học có thể được chia làm hai nhóm là nhóm các giải thuật bậc nhất và bậc hai.Các giải thuật bậc nhất hay còn gọi là các giải thuật cộng tính là các giải thuật trong đó vector trọng số wđược cập nhật dựa tính cộng theo hướng của xtwt+ αtxt→ w (2.6)trong đó αtlà trọng số của quan sát hiện tại xt.
- Một số giải thuật tuyến tính bậc nhất tiêu biểu gồm có:• Perceptron [2, 3]• Approximate Large Margin Algorithm (ALMA) [4]• Relaxed Online Maximum Margin Algorithms (ROMMA) [5]• Online Gradient Descent (OGD) [6]• Passive Aggressive learning (PA) [7, 8]Các giải thuật bậc hai dựa trên giải thiết về phân phối của vector trọng số w trong đó hầu hết các giải thuậtgiả thiết vector trọng số có phân phối Gaussian w ∼ (µ,Σ).
- Một số giải thuật tuyến tính bậc hai tiêu biểu gồmcó:• Second-order Perceptron (SOP) [9]• Confidence Weighted Learning (CW) [10]• Improved Ellipsoid Method for Online Learning (IELLIP) [11]Học viên: Phạm Xuân Cường CB160558 Khóa 2016B Lớp CH KHMT 14

Xem thử không khả dụng, vui lòng xem tại trang nguồn
hoặc xem Tóm tắt