Luận văn Thạc sĩ Máy tính: Nghiên cứu mô hình Relevance Vector Machine (RVM) áp dụng giải một số bài toán thực tế

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:76

Thêm vào BST

Báo xấu

29
lượt xem 5
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Luận văn này đánh giá mô hình phân rã và đánh giá kết quả của dự báo. Đánh giá mô hình phân rã, luận văn đánh giá thành phần sai số là chuỗi gần với nhiễu trắng và dựa vào tiêu chí trung bình (mean), độ lệch chuẩn (standard deviation). Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Máy tính: Nghiên cứu mô hình Relevance Vector Machine (RVM) áp dụng giải một số bài toán thực tế

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM TP. HỒ CHÍ MINH Lê Quốc Vương NGHIÊN CỨU MÔ HÌNH RELEVANCE VECTOR MACHINE (RVM) ÁP DỤNG GIẢI MỘT SỐ BÀI TOÁN THỰC TẾ LUẬN VĂN THẠC SĨ MÁY TÍNH Thành phố Hồ Chí Minh - 2018
BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM TP. HỒ CHÍ MINH Lê Quốc Vương NGHIÊN CỨU MÔ HÌNH RELEVANCE VECTOR MACHINE (RVM) ÁP DỤNG GIẢI MỘT SỐ BÀI TOÁN THỰC TẾ Chuyên ngành: Khoa học máy tính Mã số: 60 48 01 01 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. HUỲNH VĂN ĐỨC Thành phố Hồ Chí Minh - 2018
LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu của bản thân tôi dưới sự hướng dẫn khoa học của TS. Huỳnh Văn Đức. Các thông tin và số liệu của luận văn có nguồn gốc rõ ràng, cụ thể, có trích dẫn theo đúng quy định. Kết quả nghiên cứu của luận văn hoàn toàn trung thực, khách quan và chưa từng được sử dụng hay công bố trong bất kỳ công trình nghiên cứu nào khác. TP. Hồ Chí Minh, tháng 03 năm 2018. Học viên Lê Quốc Vương
LỜI CẢM ƠN Lời đầu tiên, tôi xin bày tỏ lòng biết ơn chân thành và sâu sắc nhất đến thầy Huỳnh Văn Đức - giảng viên hướng dẫn luận văn. Trong quá trình tìm hiểu và nghiên cứu đề tài, tôi đã gặp rất nhiều khó khăn, nhưng nhờ Thầy luôn động viên, hết lòng hướng dẫn và giúp đỡ nên tôi đã hoàn thành luận văn này. Tôi cũng xin gửi lời cảm ơn chân thành đến quý Thầy/Cô Trường Đại học Sư phạm Thành phố Hồ Chí Minh đã tận tâm dạy dỗ và truyền đạt những kiến thức quý báu trong quá trình học tập. Đồng thời, tôi cũng xin cảm ơn Ban chủ nhiệm khoa Công nghệ thông tin và phòng Sau đại học đã hỗ trợ và tạo điều kiện cho tôi trong thời gian qua. Cuối cùng, tôi xin bày tỏ lòng biết ơn sâu sắc đến gia đình đã luôn động viên và giúp đỡ tôi trong suốt quá trình học tập cũng như thực hiện luận văn. TP. Hồ Chí Minh, tháng 03 năm 2018. Học viên thực hiện Lê Quốc Vương
MỤC LỤC Trang Trang phụ bìa Lời cam đoan Lời cảm ơn Mục lục Danh mục thuật ngữ và viết tắt Danh mục các bảng Danh mục các hình vẽ Chương 1. MỞ ĐẦU......................................................................................................1 1.1. Đặt vấn đề ............................................................................................................1 1.2. Mục tiêu luận văn .................................................................................................3 1.3. Nội dung thực hiện ...............................................................................................3 1.4. Bố cục luận văn ....................................................................................................4 Chương 2. CƠ SỞ LÝ THUYẾT .................................................................................5 2.1. Mô hình Support Vector Machine (SVM) ...........................................................5 2.1.1. Ý tưởng của SVM .........................................................................................5 2.1.2. SVM đối với bài toán phân loại ....................................................................6 2.1.2.1. SVM với lề cứng (hard margin) ............................................................7 2.1.2.2. SVM với lề mềm (soft margin) .............................................................9 2.1.3. Hàm hạt nhân (kernel function) ..................................................................11 2.1.4. SVM đối với bài toán hồi quy ....................................................................12 2.2. Mô hình Relevance Vector Machine (RVM).....................................................16 2.2.1. RVM đối với bài toán hồi quy ....................................................................16 2.2.2. RVM đối với bài toán phân loại .................................................................18 2.2.3. Một số hàm cơ sở (basis functions) ............................................................20 2.3. Chuỗi thời gian (Time Series) ............................................................................21 2.3.1. Ví dụ và các khái niệm về chuỗi thời gian .................................................21
2.3.2. Các nguyên lý phân rã (decompositions)....................................................23 2.3.3. Dữ liệu tách mùa (seasonally adjusted data) ..............................................24 2.3.4. Trung bình di động (Moving average)........................................................24 2.3.5. Phương pháp phân rã cổ điển (classical decomposition)............................26 2.3.6. Phương pháp phân rã X-12-ARIMA ..........................................................27 2.3.7. Phương pháp phân rã STL ..........................................................................29 2.4. Chuỗi ARIMA ....................................................................................................30 2.4.1. Nhiễu trắng (white noise) ...........................................................................30 2.4.2. Phép toán quay lui (Backshift) và sai phân (Difference)............................30 2.4.3. Tính dừng (stationarity) của chuỗi thời gian ..............................................31 2.4.4. Mô hình ARIMA ........................................................................................31 2.4.4.1. Mô hình tự hồi quy (AR – Auto Regressive) ......................................32 2.4.4.2. Mô hình trung bình di động (MA - Moving Average) ........................32 2.4.4.3. Mô hình ARMA (Auto Regressive Moving Average) ........................33 2.4.4.5. Mô hình ARIMA (Auto Regressive Integrated Moving Average) .....33 2.4.5. Mô hình SARIMA (Seasonal ARIMA) ......................................................33 2.4.6. Phương pháp luận Box - Jenkins ................................................................34 Chương 3. PHƯƠNG PHÁP ĐỀ XUẤT ...................................................................36 3.1. Hạn chế của trung bình di động và đề xuất phương pháp khắc phục ................36 3.1.1. Hạn chế của trung bình di động ..................................................................36 3.1.2. Ứng dụng RVM/SVM vào các thuật toán phân rã chuỗi thời gian ............37 3.1.3. Đề xuất hướng khắc phục hạn chế của trung bình di động ........................38 3.2. Đề xuất thuật toán phân rã chuỗi thời gian ........................................................38 3.2.1. Ý tưởng .......................................................................................................38 3.2.2. Thuật toán ...................................................................................................39 Chương 4. THỰC NGHIỆM ......................................................................................48 4.1. Quy trình thực nghiệm .......................................................................................48 4.1.1. Dữ liệu ........................................................................................................48 4.1.2. Phương pháp thực hiện ...............................................................................49 4.1.3. Độ đo sử dụng để so sánh tính hiệu quả của thuật toán..............................50
4.2. Kết quả thực nghiệm và đánh giá.......................................................................50 4.2.1. Thuật toán phân rã chuỗi thời gian .............................................................51 4.2.2. Dự báo của thuật toán phân rã ....................................................................54 Chương 5. TỔNG KẾT ...............................................................................................61 5.1. Kết luận ..............................................................................................................61 5.2. Hướng phát triển ................................................................................................63 TÀI LIỆU THAM KHẢO...........................................................................................64
DANH MỤC THUẬT NGỮ VÀ VIẾT TẮT ACF Auto Correlation Function AR Auto Regressive ARMA Auto Regressive Moving Average ARIMA Auto Regressive Integrated Moving Average KKT Karush Kuhn Tucker RVM Relevance Vector Machine MA Moving Average PACF Partial Auto Correlation Function SARIMA Seasonal Auto Regressive Integrated Moving Average SVM Support Vector Machine
DANH MỤC CÁC BẢNG Bảng 3.1. Hệ bất đối xứng của 3x3 MA ........................................................................37 Bảng 3.2. Minh họa tính 3x3 MA có sử dụng hệ bất đối xứng .....................................37 Bảng 3.3. Sai số của thuật toán 1...................................................................................40 Bảng 3.4. Sai số của thuật toán 2...................................................................................43 Bảng 3.5. Sai số của thuật toán 3...................................................................................44 Bảng 3.6. Sai số của thuật toán 4...................................................................................47 Bảng 4.1. Số lượng mẫu của dữ liệu .............................................................................49 Bảng 4.2. Kết quả sai số của thuật toán phân rã 03 dữ liệu đầu ....................................51 Bảng 4.3. Kết quả sai số của thuật toán phân rã 03 dữ liệu sau ....................................52 Bảng 4.4. Sai số (RMSE) huấn luyện và sai số (RMSE) dự báo 3 dữ liệu đầu ............55 Bảng 4.5. Sai số (RMSE) huấn luyện và sai số (RMSE) dự báo 3 dữ liệu sau .............56
DANH MỤC CÁC HÌNH VẼ Hình 2.1. Mô tả dữ liệu tách được tuyến tính trong không gian đặc trưng Z .................5 Hình 2.2. Mô tả lề của siêu phẳng ...................................................................................6 Hình 2.3. Mô tả biến nới lỏng ξ .......................................................................................9 Hình 2.4. Mô tả ε - tube .................................................................................................13 Hình 2.5. GDP (USD) của Kenya từ năm 1960 ............................................................21 Hình 2.6. Tỷ lệ thất nghiệp của lao động Mỹ ................................................................21 Hình 2.7. Dữ liệu tách mùa của đơn hàng thiết bị điện (màu đỏ) .................................24 Hình 2.8. Biểu đồ phương pháp luận Box – Jenkins .....................................................35 Hình 3.1. Biểu đồ mô hình RVM/SVM thuật toán 1 ....................................................40 Hình 3.2. Biểu đồ thành phần sai số của thuật toán 1 mô hình SVM ...........................41 Hình 3.3. Biểu đồ của học thuật toán 2 .........................................................................42 Hình 3.4. Biểu đồ thành phần sai số của mô hình SVM ...............................................43 Hình 3.5. Biểu đồ của thuật toán 3 ................................................................................44 Hình 3.6. Biểu đồ thành phần sai số của mô hình SVM ...............................................45 Hình 3.7. Biểu đồ của thuật toán 4 ................................................................................47 Hình 3.8. Biểu đồ thành phần sai số của mô hình SVM ...............................................47 Hình 4.1. Độ lệch chuẩn của các thuật toán phân rã bộ dữ liệu 1 và 2 .........................53 Hình 4.2. Độ lệch chuẩn của các thuật toán phân rã bộ dữ liệu 3 và 5 .........................53 Hình 4.3. Độ lệch chuẩn của các thuật toán phân rã bộ dữ liệu 4 và 6 .........................54 Hình 4.4. Biểu đồ sai số huấn luyện và dự báo bộ dữ liệu 1, 2, 4 của các thuật toán SVM/RVM, S-SVM/RVM, STL-SVM/RVM ..............................................57 Hình 4.5. Biểu đồ sai số huấn luyện và dự báo bộ dữ liệu 3 và 5 của thuật toán SVM/RVM, S-SVM/RVM, STL-SVM/RVM ..............................................58 Hình 4.6. Biểu đồ sai số huấn luyện và dự báo bộ dữ liệu 1, 2, 4 của hai thuật toán X12-SVM và X12-RVM ..............................................................................59 Hình 4.7. Biểu đồ sai số huấn luyện và dự báo bộ dữ liệu 3 và 5 của hai thuật toán X12-SVM và X12-RVM ..............................................................................59
1 Chương 1. MỞ ĐẦU Chương 1 sẽ trình bày một số vấn đề đã thúc đẩy việc tìm hiểu và tiến hành nghiên cứu bài toán chuỗi thời gian. Tiếp theo đó, chương mở đầu này cũng sẽ giới thiệu những mục tiêu, nội dung nghiên cứu và bố cục trình bày của luận văn. 1.1. Đặt vấn đề Thông thường, có một độ lệch thời gian giữa nhận thức của con người về thời điểm một sự kiện sắp xảy ra hoặc nhu cầu của con người và sự kiện đó thực sự xuất hiện, khoảng thời gian này gọi thời gian trễ (time lag) và nó là lý do để chúng ta lên kế hoạch và dự báo. Nếu thời gian trễ rất nhỏ hoặc bằng không thì không cần lên kế hoạch, nếu thời gian trễ lớn và kết quả của sự kiện đó là điều kiện để xác định các nhân tố khác thì việc lên kế hoạch đóng vai trò quan trọng. Trong trường hợp này, dự báo là cần thiết để xác định thời điểm một sự kiện xảy ra hoặc nhu cầu phát sinh để chúng ta có những hành động thích hợp [19]. Luận văn giới thiệu hai mô hình chính để dự báo: mô hình chuỗi thời gian (time series models) và mô hình giải thích (explanatory models) [19]. Mô hình giải thích giả định rằng biến dự báo có quan hệ với một hay nhiều biến độc lập (biến giải thích), ví dụ: GNP = f(chính sách tiền tệ và tài khóa, lạm phát, chi tiêu vốn, nhập khẩu, xuất khẩu và sai số). Trong đó: GNP (Gross National Product) là tổng sản phẩm quốc gia. Khác với mô hình giải thích, mô hình chuỗi thời gian dự báo tương lai dựa trên các giá trị và sai số trong quá khứ. Mục tiêu của mô hình chuỗi thời gian là xây dựng mô hình dữ liệu trong lịch sử và từ đó dự báo giá trị trong tương lai. GNPt+1 = f(GNPt, GNPt-1, GNPt-2, GNPt-3, …, nhiễu).
2 Trong đó: t là tháng hiện tại, t+1 tháng kế tiếp, t-1 tháng trước, t-2 hai tháng trước, … Cả hai mô hình giải thích và chuỗi thời gian đều có những thuận lợi riêng trong những tình huống nhất định. Mô hình chuỗi thời gian thường được sử dụng dễ dàng hơn để dự báo [19]. Luận văn giới thiệu các hướng tiếp cận mô hình chuỗi thời gian dưới đây: - Sử dụng phương pháp phân rã chuỗi thời gian thành các thành phần T (xu thế), S (mùa), E (sai số). Đây là hướng tiếp cận mà luận văn quan tâm; - Hướng tiếp cận phổ biến sử dụng mô hình tự hồi quy (Auto Regressive Model – AR); - Hướng tiếp cận phổ biến khác sử dụng mô hình trung bình di động (Moving Average Model – MA); - Hướng tiếp cận Box – Jenkins là kết hợp hai mô hình AR và MA. Thời gian gần đây, phương pháp phân rã chuỗi thời gian cũng được các nhà nghiên cứu quan tâm, áp dụng mô hình này trong các lĩnh vực như chứng khoán [22], năng lượng (gió) [12] … Ngoài ra, sử dụng SVM và RVM trong dự báo chuỗi thời gian là một hướng tiếp cận khác cũng đang được các nhà nghiên cứu quan tâm. Mô hình SVM dựa trên lý thuyết học thông kê (statistical learning theory) được Vapnik và cộng sự đề xuất năm 1995 [14] và [17]. RVM là mô hình xác suất (probabilistic model) được Tipping đề xuất năm 2001. Cả hai mô hình này sau khi đề xuất được phổ biến rộng rãi. Khác với SVM, mô hình RVM huấn luyện dựa trên lý thuyết Bayes và dự báo dựa trên phân phối xác suất còn SVM dựa trên ước lượng điểm [11]. Hướng tiếp cận SVM đối với chuỗi thời gian đã có các công trình nghiên cứu nhưng kết quả rất khả quan có nhiều tiềm năng, cần có nhiều nghiên cứu về hướng tiếp cận này [17], [10]. Trong khi đó RVM chưa có nhiều nghiên cứu ứng dụng trong dự báo chuỗi thời gian: công trình [20] đã ứng dụng mô hình RVM để dự báo chuỗi thời gian, còn công trình [11] nghiên cứu cải tiến RVM để so sánh với kết quả của các mô hình khác.
3 RVM được kế thừa từ SVM, nên thuận của cả RVM/SVM là khả năng học phi tuyến rất tối ưu [4], đồng thời khi áp dụng hai mô hình này không cần quan tâm đến tính dừng của chuỗi thời gian giống như các hướng tiếp cận cổ điển. Những điều nêu trên đã thúc đẩy luận văn nghiên cứu ứng dụng mô hình RVM/SVM vào bài toán dự báo chuỗi thời gian bằng hướng tiếp cận phân rã chuỗi thời gian về kinh tế. Để đánh giá phương pháp phân rã chuỗi thời gian, luận văn đánh giá mô hình phân rã và đánh giá kết quả của dự báo. Đánh giá mô hình phân rã, luận văn đánh giá thành phần sai số là chuỗi gần với nhiễu trắng và dựa vào tiêu chí trung bình (mean), độ lệch chuẩn (standard deviation). Đánh giá kết quả dự báo của mô hình phân rã dựa trên tiêu chí Root Mean Square Error (RMSE) độ lệch của chuỗi dữ liệu quan sát và kết quả dự báo [22]. 1.2. Mục tiêu luận văn - Nghiên cứu mô hình RVM, sau đó áp dụng mô hình RVM để phân rã chuỗi thời gian lĩnh vực kinh tế. - Dự báo chuỗi thời gian kinh tế dựa trên mô hình đã phân rã. 1.3. Nội dung thực hiện Nhằm đạt được những mục tiêu nêu trên, về mặt lý thuyết luận văn tiến hành nghiên cứu những công trình liên quan chuỗi thời gian, mô hình RVM/SVM. Những công việc cụ thể bao gồm:  Tìm hiểu mô hình RVM/SVM và các ứng dụng.  Tìm hiểu chuỗi thời gian và chuỗi ARIMA.  Các hướng tiếp cận giải bài toán chuỗi thời gian.  Tìm cách đưa mô hình RVM/SVM để giải bài toán chuỗi thời gian, đề xuất thuật toán giải bài toán chuỗi thời gian. Về mặt thực nghiệm, các thuật toán do luận văn đề xuất sẽ được thực nghiệm trên các bộ dữ liệu mẫu của chuỗi thời gian, ví dụ như chuỗi thời gian công trình [6] đã để minh họa và dữ liệu chuỗi thời gian của thư viện ngôn ngữ R.
4 Quá trình thử nghiệm của luận văn sẽ được tiến hành các bước chính sau:  Chuẩn bị dữ liệu  Xây dựng quy trình thử nghiệm  Tiến hành thử nghiệm  Phân tích và đánh giá kết quả. 1.4. Bố cục luận văn Bố cục luận văn được tổ chức thành năm chương như sau: Chương 1 giới thiệu tổng quan về bài toán chuỗi thời gian, nêu lên mục tiêu, nội dung nghiên cứu và bố cục luận văn. Chương 2 trình bày cơ sở lý thuyết gồm: mô hình RVM/SVM, chuỗi thời gian và chuỗi ARIMA. Chương 3 phương pháp đề xuất: nêu hạn chế của trung bình di động và đề xuất hướng khắc phục, ứng dụng của mô hình RVM/SVM vào phương pháp phân rã chuỗi thời gian và đề xuất thuật toán phân rã chuỗi thời gian. Chương 4 thực nghiệm: nêu quy trình thực nghiệm và phân tích đánh giá kết quả thực nghiệm. Chương 5 là phần tổng kết và phát thảo một số hướng phát triển trong tương lai của luận văn.
5 Chương 2. CƠ SỞ LÝ THUYẾT Chương 2 sẽ trình bày cở sở lý thuyết gồm: mô hình SVM, mô hình RVM, chuỗi thời gian tổng quát và chuỗi ARIMA. 2.1. Mô hình Support Vector Machine (SVM) SVM là một trong phương pháp tiêu biểu nhất của nhánh phương pháp kernel. SVM được sử dụng rất phổ biến áp dụng được cho bài toán phân loại, bài toán hồi quy và bài toán dò bất thường. 2.1.1. Ý tưởng của SVM Trong không gian dữ liệu 𝒟 ban đầu không tách được, sử dụng một ánh xạ Φ để biến không gian dữ liệu 𝒟 ∈ ℝ𝑑 ban đầu (input space) vào không gian đặc trưng ℋ (feature space). Không gian đặc trưng có số chiều lớn hơn nhiều so với không gian dữ liệu ban đầu khả năng dữ liệu tách được tuyến tính, khi ánh xạ ngược trở lại không gian dữ liệu ban đầu có thể tạo ra các biên quyết định phi tuyến (Hình 2.1). X2 Biến đổi dữ liệu Z2 vào không gian đặc trưng 𝑧 = 𝚽(𝑥) X1 Dữ liệu tách được tuyến tính Z1 Dữ liệu không tách được tuyến tính trong không gian đặc trưng Hình 2.1. Mô tả dữ liệu tách được tuyến tính trong không gian đặc trưng Z
6 2.1.2. SVM đối với bài toán phân loại Phương pháp này áp dụng được cho bài toán phân loại hai lớp. Nếu muốn áp dụng cho bài toán nhiều lớp, chúng ta cần sử dụng phiên bản SVM mở rộng hoặc kết hợp nhiều bài toán phân loại hai lớp lại với nhau [1]. Cho trước tập dữ liệu huấn luyện 𝒟 = {(𝑥1 , 𝑡1 ), … , (𝑥𝑁 , 𝑡𝑁 )} với N là số điểm dữ liệu, 𝑥𝑖 ∈ ℝ𝑑 với d là số chiều của dữ liệu, 𝑦𝑖 là nhãn của điểm dữ liệu và 𝑡𝑖 ∈ {−1, +1}. Khi đó, tập huấn luyện trong ℋ có dạng 𝒟Φ = {(Φ(𝑥1 ), 𝑡1 ), … , (Φ(𝑥𝑁 ), 𝑡𝑁 )}. Giả sử tập huấn luyện 𝒟Φ tách được tuyến tính (linearly separate) trong không gian đặc trưng. Cần tìm siêu phẳng tối ưu để tách tập huấn luyện 𝒟Φ trong không gian đặc trưng. Support vectors lề Hình 2.2. Mô tả lề của siêu phẳng Có nhiều siêu phẳng tách được 𝒟Φ , vậy siêu phẳng nào là siêu phẳng tối ưu? Trong SVM đưa ra khái niệm lề của siêu phẳng (Hình 2.2), được hiểu là khoảng cách từ điểm gần nhất của tập dữ liệu 𝒟Φ đến siêu phẳng. Vapnik và cộng sự đã sử dụng lý thuyết học thống kê (statistical learning) để chứng minh rằng siêu phẳng tối ưu là siêu phẳng có lề cực đại (maximum margin) [1] và [21]. Từ kết quả này dẫn đến bài toán SVM chính là bài toán tìm siêu phẳng (H) tách được tập huấn luyện 𝒟Φ mà có lề cực đại. Siêu phẳng (H) có dạng: 𝑦(𝑥 ) = 𝑤 𝑇 Φ(𝑥) + 𝑏 (2.1.1) trong đó: Φ(𝑥) là không gian đặc trưng, 𝑤 và 𝑏 là tham số.
7 Như vậy, khoảng cách tập 𝒟Φ tới siêu phẳng (H) có thể được định nghĩa: |𝑤 𝑇 Φ(𝑥𝑖 ) + 𝑏| 𝑑 (𝒟Φ , 𝐻) = min 1≤𝑖≤𝑁 ‖𝑤 ‖ Khi đó, bài toán SVM là bài toán học siêu phẳng tối ưu: 𝑡𝑖 (𝑤 𝑇 Φ(𝑥𝑖 ) + 𝑏) max min (2.1.2) 𝑤,𝑏 1≤𝑖≤𝑁 ‖𝑤 ‖ Điều kiện: 𝑡𝑖 (𝑤 𝑇 Φ(𝑥𝑖 ) + 𝑏) ≥ 0, ∀𝑖 = 1, … , 𝑁 2.1.2.1. SVM với lề cứng (hard margin) Theo phân tích ở trên, để tìm siêu phẳng có lề cực đại chúng ta cần giải bài toán tối ưu: 𝑡𝑖 (𝑤 𝑇 Φ(𝑥𝑖 ) + 𝑏) max min (2.1.3) 𝑤,𝑏 1≤𝑖≤𝑁 ‖𝑤 ‖ Ràng buộc: 𝑡𝑖 (𝑤 𝑇 Φ(𝑥𝑖 ) + 𝑏) ≥ 0, ∀𝑖 = 1, … , 𝑁 Nếu thay đổi 𝑤 → 𝑘𝑤 và b→ 𝑘𝑏 với 𝑘 là hằng số dương, thì khoảng cách từ một điểm bất kỳ 𝑥𝑖 đến siêu phẳng sẽ không đổi. Chúng ta có thể giả sử rằng: 𝑡𝑖 (𝑤 𝑇 Φ(𝑥𝑖 ) + 𝑏) = 1 (2.1.3) trở thành: 1 𝑎𝑟𝑔 𝑚𝑖𝑛 ( ‖𝑤‖2 ) 𝑤,𝑏 2 Ràng buộc: 1 − 𝑡𝑖 (𝑤 𝑇 Φ(𝑥 ) + 𝑏) ≤ 0, ∀𝑖 = 1, … , 𝑁 Dùng điều kiện KKT1 để xác định các quan hệ giữa 𝒘, 𝒃, 𝝀: Hàm Lagrange: 𝑁 1 𝐿(𝑤, 𝑏, 𝜆) = ‖𝑤‖2 + ∑ 𝜆𝑖 [1 − 𝑡𝑖 (𝑤 𝑇 ϕ(𝑥𝑖 ) + 𝑏)] (2.1.4) 2 𝑖=1 𝜆𝑖 ≥ 0, 𝜆 = (𝜆1 , … , 𝜆𝑁 )𝑇 Hàm đối ngẫu: 𝑔(𝜆) = min 𝐿(𝑤, 𝑏, 𝜆) với 𝜆𝑖 ≥ 0 𝑤,𝑏 1 KKT là điều kiện tối ưu của bài toán tối ưu có ràng buộc được đặt tên theo tên của 03 tác giả: Karush, 1939; Kuhn và Tucker, 1951 (Chi tiết xem [4]).
8 Tính đạo hàm 𝐿(𝑤, 𝑏, 𝜆) theo 𝑤 và 𝑏 và cho bằng không [4], ta thu được: 𝑁 𝑤 = ∑ 𝜆𝑖 𝑡𝑖 Φ(𝑥𝑖 ) (2.1.5) 𝑖=1 𝑁 0 = ∑ 𝜆𝑖 𝑡𝑖 (2.1.6) 𝑖=1 Thế (2.1.5) và (2.1.6) vào (2.1.4) ta thu được 𝑔(𝜆) : 𝑁 𝑁 𝑁 1 𝑔(𝜆) = ∑ 𝜆𝑖 − ∑ ∑ 𝜆𝑖 𝜆𝑗 𝑡𝑖 𝑡𝑗 𝑘(𝑥𝑖 , 𝑥𝑗 ) 2 𝑖=1 𝑖=1 𝑗=1 Với 𝑘(𝑥𝑖 , 𝑥𝑗 ) = Φ𝑇 (𝑥𝑖 )Φ(𝑥𝑗 ) gọi là hàm hạt nhân. Bài toán đối ngẫu: 𝑎𝑔𝑟 max 𝑔(𝜆) 𝜆 Ràng buộc: 𝜆𝑖 ≥ 0 ∑𝑁 𝑖=1 𝜆𝑖 𝑡𝑖 = 0 Để phân lớp cho các điểm dữ liệu mới, ta cần xác định dấu của 𝑦(𝑥) được định nghĩa bởi công thức (2.1.1). Thế (2.1.5) vào biểu thức này ta thu được: 𝑁 𝑦(𝑥 ) = ∑ 𝜆𝑖 𝑡𝑖 𝑘(𝑥, 𝑥𝑖 ) + 𝑏 (2.1.7) 𝑖=1 Ta thấy các ràng buộc tối ưu thỏa hệ điều kiện KKT: 1 − 𝑡𝑖 (𝑤 𝑇 ϕ(𝑥𝑖 ) + 𝑏) ≤ 0, ∀𝑖 = 1, … , 𝑁 𝜆𝑖 ≥ 0, ∀𝑖 = 1, … , 𝑁 𝜆𝑖 (1 − 𝑡𝑖 (𝑤 𝑇 ϕ(𝑥𝑖 ) + 𝑏)) = 0, ∀𝑖 = 1, … , 𝑁 Thế thì tất cả điểm dữ liệu hoặc 𝜆𝑖 = 0, 𝑡𝑖 𝑦(𝑥𝑖 ) = 1. Những điểm dữ liệu mà 𝜆𝑖 = 0 thì không thể hiện trong tổng (2.1.7) nên nó không đóng vai trò trong việc dự đoán dữ liệu mới. Những điểm còn lại gọi là vector hỗ trợ (support vector) bởi vì thỏa mãn 𝑡𝑖 𝑦(𝑥𝑖 ) = 1, những điểm dữ liệu này nằm trên lề cực đại của siêu phẳng trong không gian đặc trưng, các điểm khoanh tròn nằm trên đường màu xanh của Hình 2.2. Tính chất này là trọng tâm trong ứng dụng thực tế của SVM. Một mô hình huấn luyện,
9 một tỷ lệ đáng kể các điểm dữ liệu có thể bị loại bỏ và chỉ giữ lại các vector hỗ trợ (số lượng ít) [4]. Các vector hỗ trợ 𝑥𝑖 thỏa 𝑡𝑖 𝑦(𝑥𝑖 ) = 1 và điều kiện KKT, khi 𝜆𝑖 ≠ 0 thu được b. Để dự đoán một điểm x thuộc lớp nào, ta xác định dấu của biểu thức: 𝑁 𝑤 𝑇 Φ(𝑥) + b = ∑ 𝜆𝑖 𝑡𝑖 Φ(𝑥𝑖 )𝑇 Φ(𝑥) + 𝑏 𝑖=1 Với giả thiết tập huấn luyện tách được tuyến tính trong không gian đặc trưng Φ(𝑥), mô hình SVM với lề cứng sẽ cho ra kết quả tách chính xác trên không gian ban đầu (input space), tương ứng biên quyết định là phi tuyến. Tuy nhiên trong thực tế, các lớp dữ liệu có phân bố chồng lên nhau, trường hợp này SVM (với lề cứng) có thể không giải được hoặc kết quả không tốt [4]. Do đó, người ta đã cải tiến SVM với lề mềm. 2.1.2.2. SVM với lề mềm (soft margin) Để cải tiến SVM với lề cứng, người ta đưa thêm biến nới lỏng (slack) 𝜉𝑖 ≥ 0 tương ứng với mỗi điểm dữ liệu. Những điểm dữ liệu phân lớp đúng nằm về hai phía của biên thì 𝜉𝑖 = 0, ngược lại thì 𝜉𝑖 = |𝑡𝑖 − 𝑦(𝑥𝑖 )|. Nghĩa là những điểm nằm trên lề và ở bên phía phân lớp đúng của siêu phẳng thì 0 < 𝜉𝑖 ≤ 1, như 𝑥2 ; những điểm phân lớp sai thì 𝜉𝑖 > 1, như 𝑥1 , 𝑥3 (Hình 2.3) 𝑥3 𝜉3 𝜉2 𝜉1 𝑥1 𝑥2 Hình 2.3. Mô tả biến nới lỏng 𝜉
10 Bài toán tối ưu SVM với lề mềm: 𝑁 1 𝑎𝑟𝑔 𝑚𝑖𝑛 ( ‖𝑤‖2 + 𝐶 ∑ 𝜉𝑖 ) (2.1.8) 𝑤,𝑏,𝜉 2 𝑖=1 Ràng buộc: 1 − 𝜉𝑖 − 𝑡𝑖 (𝑤 𝑇 ϕ(𝑥𝑖 ) + 𝑏) ≤ 0, ∀𝑖 = 1, … , 𝑁 −𝜉𝑖 ≤ 0, ∀𝑖 = 1, … , 𝑁 Với điều kiện 𝐶 ≥ 0 gọi là tham số bù trừ (trade – off parameter), cân bằng giữa sự chấp nhận hy sinh các điểm lỗi và lề. Dùng điều kiện KKT để xác định các quan hệ giữa 𝒘, 𝒃, 𝝀: Hàm Lagrange tương ứng của bài toán: 𝑁 𝑁 𝑁 1 𝐿(𝑤, 𝑏, 𝜉, 𝜆, 𝜇) = ‖𝑤‖2 + 𝐶 ∑ 𝜉𝑖 + ∑ 𝜆𝑖 (1 − 𝜉𝑖 − 𝑡𝑖 𝑦(𝑥𝑖 )) − ∑ 𝜇𝑖 𝜉𝑖 (2.1.9) 2 𝑖=1 𝑖=1 𝑖=1 Trong đó 𝜆𝑖 và 𝜇𝑖 là các nhân tử Lagrange và: 𝜆𝑖 ≥ 0, 𝑡𝑖 𝑦(𝑥𝑖 ) ≥ 1 − 𝜉𝑖 , 𝜆𝑖 (𝑡𝑖 𝑦(𝑥𝑖 ) − 1 + 𝜉𝑖 ) = 0 (2.1.10) 𝜇𝑖 ≥ 0, 𝜉𝑖 ≥ 0, 𝜇𝑖 𝜉𝑖 = 0 (2.1.11) là các điều kiện KKT. Hàm đối ngẫu: 𝑔(𝜆, 𝜇) = min 𝐿(𝑤, 𝑏, 𝜉, 𝜆, 𝜇) 𝑤,𝑏 Thiết lập đạo hàm của hàm Lagrange theo các biến chính 𝑤, 𝑏, 𝜉 và cho bằng không [4], ta thu được: 𝑁 𝑁 0 = ∇𝑤 𝐿 = 𝑤 − ∑ 𝑡𝑖 𝜆𝑖 Φ(𝑥𝑖 ) ⇒ 𝑤 = ∑ 𝑡𝑖 𝜆𝑖 Φ(𝑥𝑖 ) (2.1.12) 𝑖=1 𝑖=1 𝑁 0 = ∇𝑤 𝐿 = ∑ 𝑡𝑖 𝜆𝑖 (2.1.13) 𝑖=1 0 = ∇𝜉𝑖 𝐿 = 𝐶 − 𝜆𝑖 − 𝜇𝑖 ⟹ 𝜆𝑖 = 𝐶 − 𝜇𝑖 , ∀𝑖 = 1, … , 𝑁 (2.1.14)