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 phần 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 hàm cơ sở bán kính (mô hình RBF) là mô hình cơ bản đã đượ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 X f (x; w) = wi ϕi (x) + b.1) i=1 Ở đây, thường dùng hàm cơ sở bán kính (Radial Basis Function - RBF) ϕi (x) = exp(−γ||x − ci ||2 ), i = 1, ., M chỉ phụ thuộc vào khoảng cách từ đối số x đến một điểm cho trước ci (gọi là tâm) với độ rộng γ và M là số hàm cơ sở bán kính ϕi của mô hình sử dụng để tính hàm f. 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ả 7 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ó khả 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 ảnh [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 gần đây [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ở ϕi (x), i = 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 f. Rút gọn mô hình RBF có ý nghĩa thực tế quan trọng 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 đại 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 Rn sang một không gian mở rộng Rd có số chiều lớn hơn. Điểm khác biệt là trong không gian Rd 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 Rn và xác định được lớp của đối tượng đầu vào.1: Siêu phẳng phân tách tập mẫu trong không gian Rd 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 Đâ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 9 Hình 1.2: Siêu phẳng phân chia hai tập mẫu Giả sử tập mẫu gồm N phần tử là: (x1 , y1 ), (x2 , y2 ), .2) trong đó xi ∈ Rn và yi là phân lớp của xi.
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 phân 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 vectơ 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 đó w là vectơ pháp tuyến của siêu phẳng, w ∈ Rn. Ta có hai bất phương trình sau: wxi + b ≤ −1 với ∀xi ∈ Rn , yi = −1 (1.3) n wxi + b ≥ +1 với ∀xi ∈ R , yi = +1 Kết hợp hai bất phương trình trên, ta có: yi (wxi + b) − 1 ≥ 0 (1.4) Khi đó, các vectơ hỗ trợ xi thỏa mãn phương trình wxi + b = −1 thì nằm trên siêu phẳng H1 , còn các vectơ hỗ trợ xi thỏa mãn phương trình wxi + b = 1 thì 10 nằm trên siêu phẳng H2. Phương án cực tiểu 12 ||w||2 Bài toán: Tìm cực tiểu của 12 ||w||2 theo w và b với ràng buộc yi (wxi + b) − 1 ≥ 0 với 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 θ(u) với u ∈ RN , u ≥ 0, trong đó: ( N ) 1 2 X θ (u) = inf ∥w∥ − ui [yi (w.5) w,b 2 i=1 Để 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 X L (w, b) = ∥w∥2 − ui [yi (w. Vì L là hàm hai biến w, b bậc 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 ∂L (w, b) X X =w− ui y i x i = 0 ⇒ w = u i y i xi ∂w i=1 i=1 N (1.xi + b) − 1] = ui − ui uj yi yj xi xj (1.8) 2 2 i=1 i=1 i=1 j=1 Như vậy bài toán đối ngẫu được viết lại thành: Tìm cực đại của: N N N X 1 XX θ(u) = ui − ui uj yi yj xi xj (1.9) 2 i=1 i=1 j=1 N P dựa trên ui ≥ 0, i = 1, 2, ., N , ui y i = 0 i=1 Giải bài toán này ta tìm được u và từ đó tính được w theo công thức (1.
Để tính b, vận dụng điều kiện Karush-Kuhn-Tucker cho bài toán gốc, ta có được: ui [yi (w.10) Do đó, đối với mỗi i thì có hai trường hợp: + ui = 0: trong trường hợp này yi (w.xi + b) − 1 > 0 ⇒ xi không nằm trên siêu phẳng biên H1 hay H2. Vì ui = 0 nên xi không cần thiết và có thể được bỏ đi mà không ảnh hưởng đến w. + ui > 0: lúc này yi (w.xi + b) − 1 = 0 ⇒ xi nằm trên siêu phẳng biên H1 hay H2. Khi đó xi đượ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 xi có ui > 0, lúc đó: yi (w.3: Tập 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. Giai đoạn phân lớp Giả sử có một mẫu dữ liệu cần phân lớp x∗ nào đó, hàm phân lớp y ∗ của x∗ (-1 hay 1) được xác định thông qua công thức: N ! X y ∗ = f (x∗ ) = sign (wx∗ + b) = sign ui yi xi x∗ + b (1. SVM với tập mẫu 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. Vấn đề đặ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 xi một sai số ξi để “xem như có thể phân tách tuyến tính” [11]. wxi + b ≥ +1 − ξi với yi = +1 wxi + b ≤ −1 + ξi với yi = −1 (1., 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: N 1 X w2 + C ξi (1.15) 2 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: N Cực tiểu: f (w, b, ξ) = 12 w2 + C P ξi i=1 với yi (wxi + b) − 1 + ξi ≥ 0; y = 1, 2, .16) ξi ≥ 0 Bài toán đối ngẫu của bài toán trên sẽ là: Cực đại: θ(u, v) với u ∈ RN , v ∈ RN , u ≥ 0, v ≥ 0, ở đây: ( N N N ) 1 2 X X X θ(u, v) = inf ∥w∥ + C ξi − ui [yi (w.