TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI

VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

—————*—————

Phạm Xuân Cường

PHƯƠNG THỨC HỌC MÁY TRỰC TUYẾN

DỰA TRÊN MÔ HÌNH BAYES

CHUYÊN NGÀNH: KHOA HỌC MÁY TÍNH

LUẬN VĂN THẠC SỸ KHOA HỌC

CHUYÊN NGÀNH KHOA HỌC MÁY TÍNH

NGƯỜI HƯỚNG DẪN KHOA HỌC

TS Đinh Viết Sang

HÀ NỘI 10-2017

SĐH.QT9.BM11 Ban hành lần 1 ngày 11/11/2014

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:

 Chỉnh sửa lại một số lỗi chính tả, công thức viết thiếu trong các

chương 1, 2, 3 và 5.

 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ỆP

1. Thông tin về học viên

Họ và tên sinh viên: Phạm Xuân Cường

Lớp: Khoa học máy tính Hệ đào tạo: Thạc sỹ Khoa học

Thời gian làm LVTN: Từ ngày 06 / 03 / 2017 đến 23 / 10 / 2017

2. Mục đích nội dung của LVTN

Nghiê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ệm

4. 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ẫn

củ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àn

vă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 2017

Tác giả Luận văn

Phạm Xuân Cường

5. Xác nhận của GVHD:

Hà Nội, ngày 23 tháng 10 năm 2017

Giáo viên hướng dẫn

TS Đinh Viết Sang

Học viên: Phạm Xuân Cường CB160558 Khóa 2016B Lớp CH KHMT 1

LỜI CẢM ƠN

Lờ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ên

và 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ới

kế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ều

trong con đường nghiên cứu học thuật. Bên cạnh đó tôi xin được gửi lời cảm ơn tới tất cả những người luôn tin

tưởng và hỗ trợ tôi dù là trực tiếp hay gián tiếp.

Cuối cùng, tôi xin bày tỏ sự cảm kích và tình yêu sâu sắc đối với bố mẹ, anh, chị, vợ và con gái tôi những

người luôn ủng hộ và hỗ trợ tôi vô điều kiện để tôi có thể đạt được thành công trong cuộc sống. Tôi xin đặc biệt

gử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ân

văn Thạc sỹ này.

Hà Nội, ngày 26 tháng 10 năm 2017

Tác giả luận văn

Phạm Xuân Cường

Họ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 ĐÂY

1. Thanh T. Nguyen, Phuong M. Nguyen, Cuong X. Pham and Alan W-C Liew, “Heterogeneous Classifier

Ensemble with Fuzzy Rule-based Meta Learner”, Information Sciences, 2017 (accepted)

2. Cuong X. Pham, Tr uong D. Manh, Sang D. Viet, Son Hoang, Thanh T. Nguyen, Alan W-C Liew, “Learn-

ing from data stream based on Random Projection and Hoeffding Tree classifier”, International Confer-

ence on Digital Image Computing: Techniques and Applications (DICTA), 2017 (accepted).

3. Thuy T. T. Nguyen, Thanh T. Nguyen, Cuong X. Pham, Alan W-C Liew,“A Novel Online Bayes Clas-

sifier”. 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ục

LỜI CẢM ƠN 3

DANH SÁCH BẢNG 7

DANH SÁCH HÌNH VẼ 8

DANH MỤC TỪ VIẾT TẮT 9

1 GIỚI THIỆU 10

1.1 Đặt vấn đề . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.2 Cấu trúc luận văn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.3 Các ký hiệu toán học . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2 TỔNG QUAN CÁC PHƯƠNG PHÁP HỌC TRỰC TUYẾN 15

2.1 Phương pháp học trực tuyến tuyến tính . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.2 Phương pháp học trực tuyến dựa trên cây phân loại . . . . . . . . . . . . . . . . . . . . . . . 20

2.3 Phương pháp học trực tuyến Bayes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.4 Phương pháp học trực tuyến tập hợp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

2.5 Phương pháp đánh giá và so sánh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

2.5.1 Các độ đo hiệu quả . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

2.5.1.1 Độ chính xác và sai số . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

2.5.1.2 Confusion Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

2.5.1.3 Độ đo Precision, Recall và F1 . . . . . . . . . . . . . . . . . . . . . . . . . 34

2.5.2 Kiểm định thống kê . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

2.6 Các nghiên cứu đề xuất . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

2.6.1 Câu hỏi nghiên cứu và mục tiêu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

2.6.2 Tầm quan trọng của nghiên cứu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

3 MÔ HÌNH HỌC ONLINE DỰA TRÊN LÝ THUYẾT BAYES 44

3.1 Các nghiên cứu liên quan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

Họ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 . . . . . . . . . . . . . . . . . . 45

3.2 Mô hình đề xuất . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

4 MÔ HÌNH HỌC ONLINE DỰA TRÊN CÂY HOEFFDING VÀ PHÉP CHIẾU NGẪU NHIÊN 54

4.1 Các nghiên cứu liên quan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

4.1.1 Bộ phân loại cây Hoeffding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

4.1.2 Các phép chiếu ngẫu nhiên . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

4.2 Mô hình đề xuất . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

5 THỬ NGHIỆM VÀ ĐÁNH GIÁ 66

5.1 Tập dữ liệu thử nghiệm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

5.2 Cấu hình thử nghiệm mô hình và phương pháp so sánh . . . . . . . . . . . . . . . . . . . . . 67

5.3 Kết quả thử nghiệm và so sánh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

5.4 Dữ liệu nhiễu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

KẾT LUẬN 77

TÀI LIỆU THAM KHẢO 79

Học viên: Phạm Xuân Cường CB160558 Khóa 2016B Lớp CH KHMT 5

Danh sách bảng

1.1 Các ký hiệu toán học . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2.1 Ví dụ ma trận Confusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

5.1 Thông tin về các tập dữ liệu dùng để đánh giá mô hình . . . . . . . . . . . . . . . . . . . . . 67

5.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 . . . . . 71

5.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 . . . . . . . 74

Họ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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.1 Phân loại các phương thức học trực tuyến . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.2 Quy trình hoạt động của thuật toán học trực tuyến . . . . . . . . . . . . . . . . . . . . . . . . 16

2.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 33

2.4 Đường cong P-R trong bài toán phân loại . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

3.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| = 1 . . . . . 53

4.1 Quy trình hoạt động của thuật toán RP Hoeffding . . . . . . . . . . . . . . . . . . . . . . . . 65

5.1 Quy trình thử nghiệm trong mô hình đề xuất . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

5.2 Thống kê độ hiệu quả của các thuật toán trên 25 tập dữ liệu . . . . . . . . . . . . . . . . . . . 72

5.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 25

tập dữ liệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

5.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ập

dữ liệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

5.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 76

Họ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 ắt

STT Từ viết tắt Ý nghĩa

1 VI Variational Inference

2 VIGO Variational Inference for Gaussian

3 PA Passive Aggressive learning

4 SOP Second-order Perceptron

5 GMM Gaussian Mixture Model

6 SCW Soft Confidence Weighted

7 ALMA Approximate Large Margin Algorithm

8 ROMMA Relaxed Online Maximum Margin Algorithms

9 OGD Online Gradient Descent

Học viên: Phạm Xuân Cường CB160558 Khóa 2016B Lớp CH KHMT 8

Chương 1

GIỚI THIỆU

1.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. Do đó, thuật ngữ

BigData được các công ty công nghệ nhắc tới nhiều trong khoảng một thập niên trở lại đây nhằm mô tả các tập

dữ liệu rất lớn không chỉ về số lượng, sự đa dạng mà còn cả về tốc độ tăng của nó. Hình sau mô tả chi tiết về

khái niệm BigData.

BigData

Số lượng

Sự đa dạng

Tốc độ phát triển

Độ tin cậy

Giá trị

Hình 1.1: Các đặc điểm của BigData

Trong 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 doanh

Họ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ác

quá 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 đang

tạo ra 1 quintillion (10

) 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áo

trê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 trong

nhữ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ương

phá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ột

khu 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ậm

chí 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áy

khi 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ểm

mà đế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ến

chú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ĩnh

vự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ột

kỹ 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ên

tụ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ảm

biế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, quy

trì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ăn

Nộ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ò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 tr iển tiếp theo trong Chương 5.

1.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)

(2)

,. ..,x

(D)

)

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

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(Λ)

,β

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à Γ(·) =

∞

t−1

−x

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

Mô hình phân lớp trực tuyến tại thời điểm t

Quan sát mới đến tại thời điểm t

Nhãn lớp thật của quan sát x

ˆy

Nhãn lớp dự đoán cho quan sát x

l(y

, ˆy

) 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

Vector trọng số tại thời điểm t của thuật toán tuyến tính

(·)

Thủ tục chuyển vị

k·k Chuẩn Euclide (Chuẩn L

)

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

Học máy trực tuyến tuyến tính

Học máy trực tuyến dựa trên Bayesian

Học máy trực tuyến dựa trên câyHọc máy trực tuyến kết hợp

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 x

mới tới, mô hình học hiện tại L

sẽ được dùng để dự đoán nhãn của x

, ký

hiệu là ˆy

• 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 x

có thể biết được ký hiệu

là y

, dựa trên cặp (y

, ˆy

), 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 (y

, ˆy

), mô hình học sẽ được cập nhật (L

→L

t+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 x

và nhãn thật của nó y

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 x

Học từ

quan sát x

Thu được

mô hình tại

thời điểm t

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:

ˆy

= sign( f

)) = sign(w

·x

) (2.1)

trong đó w

, x

là hai vector cột ∈ R

, w

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 f

t,i

) = w

t,i

·x

trong đó w

t,i

là vector trọng số ứng với class i(i = 1, .. ., K). 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:

ˆy

= arg max

i∈{1,...,K}

t,i

) = arg max

i∈{1,...,K}

t,i

·x

(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(y

, ˆy

) khác nhau và cơ chế

cập nhật mô hình L

→ L

t+1

, cụ thể là cách cập nhật vector trọng số w

→ 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:

l(y

, ˆy

) = I( ˆy

6= y

)











0 nếu y

) > 0

1 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 x

bởi mô hình hiện tại ˆy

khác với nhãn lớp đúng y

. 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(y

, ˆy

) = max(0,1 −y

)) = max(0,1 −y

·x

)) (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(y

, ˆy

) = max(0,1 −( f

t,y

) −max

i6=y

t,i

)))

= max(0,1 −(w

t,y

·x

−max

i6=y

t,i

·x

))

(2.5)

Hàm tổn thất Hinge được định nghĩa dựa trên biểu thức y

), được gọi là lề của quan sát (x

, y

) ứng với

hàm phân loại f

. Giá trị tuyệt đối của lề |y

·x

)| = |w

·x

| đượ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

t,y

·x

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ì max

i6=y

t,i

·x

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 y

·x

) ≤ 0 và thậm chí là dự đoán đúng y

) > 0. Hàm này quan tâm tới lề

của quan sát hiện tại, nếu lề đó y

) < 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ố w

→ 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 x

+ α

→ w (2.6)

trong đó α

là trọng số của quan sát hiện tại x

. 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