Chương 1 của luận án giới thiệu tổng quan về mô hình RBF trong bài toán phân lớp. Phần đầu tập trung vào giới thiệu mô hình RBF. Các phan sau của chương trình bày hai mô hình RBF: mô hình RBF dựa trên cách tiếp cận hàm quyết định với lề cực đại (tiêu biểu là Support Vector Machine - SVM) và mô hình RBF dựa trên suy luận xác suất Bayes (tiêu biểu là Relevance Vector Machine - RVM). Phần cuối phân tích về độ phức tạp tính toán của các thuật toán SVM và RVM.
Giới thiệu mô hình RBF Mô hình ham cơ sở bán kính (mô hình RBF) là mô hình cơ ban đã được sử dụng trong giải quyết nhiều vấn đề khác nhau và đang tiếp tục được ứng dụng rộng rãi trong nhiều ứng dụng thực tế khác nhau như phân lớp, xấp xỉ hàm, dự đoán dữ liệu theo thời gian [4, 69]. Mô hình RBF có cấu trúc đơn giản, dưới dạng tổ hợp tuyến tính của các hàm cơ sở: M Ji) = À ` widi(x) +0.1) i=l O đây, thường dùng hàm cơ sở bán kính (Radial Basis Function - RBF) ø¿(z) = exp(—y||2 — «||?),¡ = 1,.,M chỉ phụ thuộc vào khoảng cách từ đối số z đến một điểm cho trước c; (gọi là tâm) với độ rộng + và M là số hàm cơ sở bán kính ¢; của mô hình sử dụng để tính hàm ƒ. Về mặt lý thuyết, hàm quyết định dạng (1.1) có nhiều lợi thế. Thứ nhất, khả năng khái quát hóa của mô hình RBF cao.
Có thể điều chỉnh không giới hạn số chiều VC (Vapnik-Chervonenkis) trong phân lớp. Do đó, có kha năng phân tách bất kỳ một tập dữ liệu mẫu nào cũng như xấp xỉ các hàm biến số thực với độ chính xác tùy ý [7, 55]. Thứ hai, cấu trúc tính toán của mô hình RBF không phức tạp bằng cấu trúc tính toán của mạng nơ-ron. Trong thực tế, mô hình RBF đạt hiệu quả phân lớp tốt trong các ứng dụng nhận dạng hình anh [42], nhận dạng giọng nói [3] và nhận dạng cử chỉ của con người [40].
Mục tiêu chung của những nghiên cứu về mô hình RBF trong thời gian gan day [71] là tìm kiếm các mô hình RBF có cấu trúc đơn giản, với số ít hàm cơ sở @¡(#),¡ = 1,., M để giảm khối lượng tính toán trong (1.1), giúp tăng tốc độ tính toán hàm ƒ. Rút gọn mô hình RBF có ý nghĩa thực tế quan trong trong các ứng dụng đòi hỏi đáp ứng yêu cầu xử lý thông tin nhanh như xử lý dữ liệu truyền từ các cảm biến, xử lý tín hiện video, hình ảnh, an toàn và bảo mật thông tin. Để tìm được hàm quyết định dạng (1.1), có nhiều cách tiếp cận thể hiện qua các hàm mục tiêu khác nhau, trong mỗi cách tiếp cận có nhiều cách giải khác nhau. Các phần tiếp theo sẽ trình bày hai cách tiếp cận xây dựng và sử dụng mô hình RBF trong bài toán phân lớp là SVM và RVM.
SVM: mô hình phân lớp RBF dựa trên lề cực dai Máy vectơ hỗ trợ (Support Vector Machine - SVM) do Cortes, Vapnik đưa ra [11] là phương pháp học máy cho phép giải quyết hiệu quả bài toán phân lớp và bài toán hồi quy. Thuật toán này dựa trên nền tảng toán học chặt chẽ của lý thuyết tối ưu. Ý tưởng chính của SVM là chuyển tập mẫu từ không gian biểu diễn ban đầu R” sang một không gian mở rộng R“ có số chiều lớn hơn. Điểm khác biệt là trong không gian R¢ có thể tìm một siêu phẳng tối ưu phân tách tập mẫu, nghĩa là tìm được miền phân bố của các lớp trong không gian biểu diễn R” và xác định được lớp của đối tượng đầu vào.
ø siêu phẳng phân tách mặt phân tách Hình 1.1: Siêu phẳng phan tách tập mẫu trong không gian R¢ Cũng như mạng nơ-ron, phương pháp SVM có tính tổng quát cao, có thể áp dụng cho nhiều bài toán phân lớp khác nhau. Phương pháp SVM gồm hai pha cơ bản: pha huấn luyện và pha kiểm thử. Có hai trường hợp đối với tập mẫu: thứ nhất, tập mẫu có thể phân tách tuyến tính được và thứ hai, tập mẫu không thể phân tách tuyến tính được. Ứng với hai trường hợp tập mẫu, ta có hai loại SVM.
SVM tuyén tính Khi tập mẫu có thể phân tách tuyến tính được, có hai trường hợp cần xem xét: tập mẫu không có nhiễu, tập mẫu có nhiễu. SVM với tập mẫu phân tách tuyến tính không có nhiễu Dây là trường hợp đơn giản nhất. Trong trường hợp này, tập mẫu được phân tách tuyến tính bằng một siêu phẳng nào đó, không có nhiễu theo nghĩa tất cả các điểm được gán nhãn 1 thuộc về phía dương của siêu phẳng và tất cả các điểm được gán nhãn -1 thuộc về phía âm của siêu phẳng. Giai đoạn huấn luyện trong phương pháp SVM sẽ tìm siêu phẳng này.
Giai đoạn huấn luyện SVM Hình 1.2: Siêu phẳng phân chia hai tập mẫu Giả sử tập mẫu gồm X phần tử là: (21, 01), (Z2, 9),.2) trong đó x; € #” và y là phân lớp của z;. Không mất tính tổng quát, ta coi rằng yi € {-1, 1}. Ta cần xác định siêu phẳng phan tách hai lớp tương ứng với nhãn -1 và 1. Tồn tại nhiều siêu phẳng như vậy.
Vấn đề đặt ra là xác định được siêu phẳng sao cho khoảng cách Euclid giữa hai lớp là lớn nhất (Hình 1. Ta gọi các vecto thuộc tập mẫu gần siêu phẳng nhất là vectơ hỗ trợ (Support Vector - SV). Giả sử phương trình siêu phẳng cần tìm là wx + b = 0, trong đó œ là vecto pháp tuyến của siêu phẳng, w € #“. Ta có hai bất phương trình sau: waj +b < —1 với Va; € R“,ị = —1 (1.3) +0; + b > +1 với Vr; € R",y, = +] Kết hợp hai bất phương trình trên, ta có: yi(wa; + b)-1>0 (1.4) Khi đó, các vectơ hỗ trợ x; thỏa mãn phương trình wa; + b = —1 thì nằm trên siêu phẳng Hj, còn các vectơ hỗ trợ x; thỏa mãn phương trình wa; + b = 1 thì 10 nằm trên siêu phẳng Hy.
Phuong an cực tiểu 3||u|| Bài toán: Tìm cực tiểu của $||w||? theo w và b với ràng buộc (+; + b) — 1 > 0 VỚI ¡ = 1,2,. Đây là một bài toán tối ưu có ràng buộc, trong đó hàm mục tiêu là một hàm lồi và miền ràng buộc cũng là một tập lồi. Do có tính lồi nên để giải bài toán trên, có thể chuyển qua giải bài toán đối ngẫu tương ứng. Bài toán đối ngẫu [11] là: Tìm cực đại của 6(u) với u € RN, u > 0, trong đó: 0 (u) = inf {i — d [ys (w.5) N Để giải bài toán đối ngẫu, trước tiên ta cần tìm cực tiểu của N 1 L(w,b) = Binh — À 1 [ys (t0.
Vì L là ham hai biến +», b bac hai không ràng buộc nên theo điều kiện Fermat, cực tiểu của L xảy ra tại w và b [11] sao cho: N N ma) =w- So wiyiri =0>w= ».8) 1 N ioe 2 i= i=l i=1 j=l Như vay bài toán đối ngẫu được viết lai thành: Tìm cực đại của: N dựa trên u; > 0, ¡ = 1,2,.,N, 3) uiyi =0 jz Giải bài toán nay ta tìm được u va từ đó tính được w theo công thức (1. Để tính b, van dụng điều kiện Karush-Kuhn-Tucker cho bài toán gốc, ta có được: Do đó, đối với mỗi i thì có hai trường hợp: + u; = 0: trong trường hợp này y;(w.2; +b) — 1 > 0 => 2; không nằm trên siêu phẳng biên ¡ hay Ho. Vì wu = 0 nên 2; không cần thiết và có thể được bỏ di mà không ảnh hưởng đến w. +b) — 1 = 0 = 2; nằm trên siêu phẳng biên Hị hay Hạ.
Khi đó x; được gọi là vectơ hỗ trợ và tham gia vào việc tính w. Thông thường, số lượng vectơ hỗ trợ nhỏ hơn nhiều so với số lượng mẫu. Do đó, để tính b chỉ cần chọn một 2; có uj > 0, lúc đó: yi(w.3: Tap mẫu không thể phân hoạch bằng một siêu phẳng Vậy ta đã tính được w và b nên xác định được siêu phẳng phân tách. phén lớp Giả sử có một mẫu dữ liệu cần phân lớp z* nào đó, hàm phân lớp y* của z* (-1 hay 1) được xác định thông qua công thức: y* = ƒ (+) = sign (wa* +b) = sign (> tia” + ) (1.
SVM uới tập mau phân tách tuyến tính có nhiễu Tập mẫu có thể phân tách tuyến tính nhưng có nhiễu (lỗi) được biểu diễn trong Hình 1. Trong trường hợp này, hầu hết các điểm trong tập dữ liệu được phân chia bởi siêu phẳng tuyến tính. Tuy nhiên, có một số ít điểm nhiễu, nghĩa là điểm có nhãn dương nhưng lại thuộc về phía âm của siêu phẳng hoặc điểm có nhãn âm lại thuộc về phía dương của siêu phẳng. Van đề đặt ra làm thé nào có thể tận dụng siêu phẳng phân tách tập mẫu này? Để có thể áp dụng phương pháp trong phần trước, ta gán cho mỗi mẫu z; một sai số £¡ để “xem như có thể phân tách tuyến tính” [11].,N 13 Cũng tương tự như phần trước, ta phải đi tìm cực tiểu của biểu thức sau: 1 N 5 lle] + Odo & (1.15) i=1 trong đó C là một hằng số dương tự chọn.
Có thể phát biểu lại bài toán như sau: Cực tiểu: f(w,b,€) = 4 ||w?||+ C » € VỚI " ¡(0 + Ù) — 1+§i 20; =1,2,.16) & > 0Ú Bài toán đối ngẫu của bài toán trên sẽ là: Cực đại: 0(u,u) với uc RN, ve RŸ,u>0,u>0, 6 day: (u,v) = inf, {i + cs — >>.17) N N N i=l Cũng theo điều kiện Fermat, cực tiểu của: N N N 1 L(w,b,§) = sIl»|Í +Ơ 6T 2|; À +b) =1+ 6] — ø@ — (1.18) i=l i=l i=l xay ra tai w, b, € sao cho: N N OL(w,b,€) — _ _ Dw =w Dwi =0>w= Dwi OL(w,b,é) — xế (1.19) ee mí — =CŒ—tt; — 0¡ =0 > 0< u¿ < CƠ 14 Lúc đó, giá trị cực tiểu của 7 là: N N N 1 Lo(w,b, €) = sll” + CỒ `& — ». +b)-1+&] - So iG N i=1 =1 1 N WN (1. m i=1 j=l Nhu vậy bài toán đối ngẫu được viết lai thành: Tìm cực đại của: N pea F(u) = So ui -5 » ».22) Bài toán này giống bài toán (1.9), chi có thêm điều kiện u; < C. Giải bai toán này ta tìm được u và từ đó tính được w theo công thức (1.19) tức w = > UiYiLis trong đó 2; là các vectơ hỗ trợ va các vectơ lỗi (ứng với 0 < uj; < C) và Ai, là số lượng vectơ hỗ trợ và vectơ lỗi.
Dé tìm b, sử dụng điều kiện Karush-Kuhn-Tucker cho bài toán gốc ta có: 0[U;(t00.