chương 1 nhằm giới thiệu về bài toán, các vấn đề còn tồ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ện nay 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ết quả 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ết luận và hướng phát triển tiếp theo trong Chương 5.3 Các ký hiệu toán học Trướ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ĩa X Tập dữ liệu quan sát (Tập huấn luyện) x = (x(1),x(2) ,.
,x (D))T Quan sát x được biểu diễn dưới dạng vector, x(i) là đặc trưng thứ i của quan sát p(r) Xác suất của biến ngẫu nhiên r. 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 r M Số nhãn lớp của tập dữ liệu N Số quan sát trong tập dữ liệu Y 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ặc Y = {1, 2, ., 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 Λ = Σ −1 D Số chiều của dữ liệu W0,v 0 Giá 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 ,β0 Giá 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(Λ) = W (Λ|W,v) Tr(·) Vết của ma trận (Tổng các thành phần trên đường chéo chính) Hàm gamma được định nghĩa là Γ(·) = 0∞ xt−1 e−x dx R Γ(·) L(q) Cận dưới của suy diễn biến thiên (Variational Inference) |·| Lực lượng (cardinality) tương đối của một tập hợp Lt Mô hình phân lớp trực tuyến tại thời điểm t xt Quan sát mới đến tại thời điểm t yt Nhãn lớp thật của quan sát x t ŷt Nhãn lớp dự đoán cho quan sát x t l (yt , ŷt ) Hàm mất mát sign(·) Hàm dấu, nhận giá trị {−1, 0, 1} tương ứng với các trường hợp >, = và < 0 I 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ác wt Vector trọng số tại thời điểm t của thuật toán tuyến tính (·)T Thủ tục chuyển vị k·k Chuẩn Euclide (Chuẩn L 2 ) Bảng 1.1: Các ký hiệu toán học Học viên: Phạm Xuân Cường CB160558 Khóa 2016B Lớp CH KHMT 11 Chương 2 TỔNG QUAN CÁC PHƯƠNG PHÁP HỌC TRỰC TUYẾN Chươ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ật toán được chia làm 4 nhóm như minh họa trong hình sau: Học máy trực tuyến dựa trên Bayesian Học máy trực tuyến kết hợp Học máy trực tuyến Học máy trực tuyến dựa trên cây Học máy trực tuyến tuyến tính Hình 2.1: Phân loại các phương thức học trực tuyến Cá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 xt mới tới, mô hình học hiện tại Lt sẽ được dùng để dự đoán nhãn của xt , ký hiệu là ŷt. • 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 xt có thể biết được ký hiệu là yt , dựa trên cặp (yt , ŷt ), 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 , ŷ t ), mô hình học sẽ được cập nhật (Lt → Lt+1 ) sử dụng quan Học viên: Phạm Xuân Cường CB160558 Khóa 2016B Lớp CH KHMT 12 sát xt và 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ạng hà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 quan cho 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 quan sát mới xt Thu được mô hình tại thời điểm t Học từ quan sát xt Hình 2.2: Quy trình hoạt động của thuật toán học trực tuyến 2.1 Phương pháp học trực tuyến tuyến tính Phươ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 = {−1, +1}, hàm phân loại có dạng: ŷt = sign( ft (xt )) = sign(wTt · xt) (2.1) trong đó wt , xt là hai vector cột ∈ RD , wt là vector trọng số cần xác định, sign là hàm dấu trả về hai giá trị -1 và 1. 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 ) = wTt,i · xt , trong đó wt ,i là vector trọng số ứng với class i(i = 1,. Nhãn lớp dự đoán dựa trên cực đại hàm phân loại trên toàn bộ tập nhãn: ŷt = arg max ft ,i(x t ) = arg max wTt,i · x t (2.,K } 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 , ŷ t ) 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 → w t+1 khác nhau. Hai dạng hàm tổn thấ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: 0 nếu yt ft(xt ) > 0 l (y t , ŷ t ) = I(ŷt 6= yt ) (2.3) 1 nếu ngược lại 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 xt bởi mô hình hiện tại ŷt khá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ới Họ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án Perceptron 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ĩa như sau: l (yt , ŷt ) = max(0, 1 − yt f t (xt )) = max(0, 1 − yt (wTt · x t )) (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 , ŷt ) = max(0, 1 − ( ft ,yt (xt ) − max f t ,i(xt ))) i6=yt (2.5) = max(0, 1 − (wTt,yt · xt − max wTt,i · xt)) i6=yt 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 (x t , yt ) ứng với hàm phân loại f t. Giá trị tuyệt đối của lề |yt (wTt · x t )| = |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 w tT,yt · xt cà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=yt wTt,i · xt dự đ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ẽ được cập nhật cả khi dự đoán sai yt (wTt · xt ) ≤ 0 và thậm chí là dự đoán đúng yt f t (xt ) > 0. Hàm này quan tâm tới lề của quan sát hiện tại, nếu lề đó yt ft (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ọng số wt → w t+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 xt w t + αt xt → w (2.6) trong đó αt là 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ật giả 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ồm có: • 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 • Adaptive Regularization of Weights (AROW) [12, 13] • New variant of Adaptive Regularization (NAROW) [14] • Normal Herding method via Gaussian Herding (NHERD) [15] • Soft Confidence Weighted (SCW) [16] Các giải thuật trực tuyến bậc nhất hiệu quả trong việc sử dụng bộ nhớ và tốc độ tính toán vì chỉ cần lưu trữ vector trọng số. Các giải thuật bậc hai phức tạp hơn so với bậc nhất nhưng hiệu quả tính toán cũng rất đáng kể.
So với các giải thuật trong các nhóm khác như Bayesian hay cây phân loại, thời gian tính toán của các giải thuật tuyến tính là thấp hơn. Bên cạnh đó các giải thuật tuyến tính, đặc biệt là bậc nhất có thể áp dụng cho dữ liệu số chiều lớn một cách hiệu quả. Tuy nhiên các giải thuật tuyến tính cũng có một số nhược điểm. Việc mở rộng các giải thuật học trực tuyến tuyến tính cho trường hợp nhiều lớp thường không phải hệ quả trực tiếp, một số được tiến hành bằng chiến thuật 1-vs-all.