Trong loạt bài viết này, chúng ta sẽ khám phá một trong những thuật toán phân loại (classification) phổ biến nhất, bên cạnh hồi quy Softmax (softmax regression): Support Vector Machine (SVM). Phần này bao gồm nhiều kiến thức toán học đòi hỏi bạn đọc có kiến thức về đối ngẫu (Duality) và tối ưu lồi. Bạn nên đọc các Bài 16, 17 và 18 trước khi tiếp tục.
Nếu bạn không quan tâm đến các chi tiết toán học, bạn có thể bỏ qua mục 3.
Nội dung chính:
-
- Giới thiệu
- 1.1. Khoảng cách từ một điểm đến siêu phẳng
- 1.2. Ôn lại bài toán phân loại hai lớp
-
- Xây dựng bài toán tối ưu cho SVM
-
- Bài toán đối ngẫu cho SVM
- 3.1. Kiểm tra điều kiện Slater
- 3.2. Lagrangian của bài toán SVM
- 3.3. Hàm đối ngẫu Lagrange
- 3.4. Bài toán đối ngẫu Lagrange
- 3.5. Điều kiện Karush-Kuhn-Tucker (KKT)
-
- Lập trình tìm nghiệm cho SVM
- 4.1. Tìm nghiệm theo công thức
- 4.2. Tìm nghiệm bằng thư viện
-
- Tổng kết và thảo luận
-
- Tài liệu tham khảo
Mục Lục
1. Giới thiệu
Trước khi đi sâu vào ý tưởng cốt lõi của Support Vector Machine, chúng ta sẽ cùng nhau ôn lại kiến thức về hình học giải tích quen thuộc từ thời trung học.
1.1. Khoảng cách từ một điểm đến siêu phẳng
Trong không gian hai chiều, khoảng cách từ một điểm có tọa độ ((x_0, y_0)) đến đường thẳng có phương trình (w_1x + w_2y + b = 0) được tính bằng công thức:
[ frac{|w_1x_0 + w_2y_0 + b|}{sqrt{w_1^2 + w_2^2}} ]Tương tự, trong không gian ba chiều, khoảng cách từ một điểm có tọa độ ((x_0, y_0, z_0)) đến mặt phẳng có phương trình (w_1x + w_2y + w_3 z + b = 0) là:
[ frac{|w_1x_0 + w_2y_0 + w_3z_0 + b |}{sqrt{w_1^2 + w_2^2 + w_3^2}} ]Nếu bỏ dấu giá trị tuyệt đối ở tử số, ta có thể xác định vị trí tương đối của điểm so với đường thẳng hoặc mặt phẳng. Những điểm làm cho biểu thức trong dấu giá trị tuyệt đối dương nằm về một phía (phía dương), trong khi những điểm làm cho biểu thức âm nằm về phía còn lại (phía âm). Các điểm nằm trên đường thẳng/mặt phẳng làm cho tử số bằng 0, tức khoảng cách bằng 0.
Tổng quát hóa lên không gian nhiều chiều: Khoảng cách từ một điểm (vector) có tọa độ (mathbf{x}_0) đến siêu phẳng (hyperplane) có phương trình (mathbf{w}^Tmathbf{x} + b = 0) được xác định bởi:
[ frac{|mathbf{w}^Tmathbf{x}_0 + b|}{||mathbf{w}||_2} ]Trong đó, (||mathbf{w}||_2 = sqrt{sum_{i=1}^d w_i^2}), với (d) là số chiều của không gian.
1.2. Nhắc lại bài toán phân loại hai lớp
Quay trở lại bài toán trong Perceptron Learning Algorithm (PLA). Giả sử có hai lớp (class) khác nhau, được biểu diễn bằng các điểm trong không gian nhiều chiều. Hai lớp này được gọi là linearly separable nếu tồn tại một siêu phẳng có thể phân chia chính xác chúng, sao cho tất cả các điểm thuộc một lớp nằm về một phía của siêu phẳng, và các điểm thuộc lớp còn lại nằm về phía đối diện. Thuật toán PLA có thể tìm được một siêu phẳng như vậy, nhưng có thể có vô số nghiệm, như Hình 1:
Câu hỏi đặt ra là: trong vô số các siêu phẳng phân chia đó, siêu phẳng nào là tốt nhất theo một tiêu chí nào đó? Trong Hình 1, có hai đường thẳng có vẻ hơi “thiên vị” lớp hình tròn đỏ. Liệu có cách nào để tìm được một đường phân chia “công bằng” và “hạnh phúc” cho cả hai lớp hay không?
Chúng ta cần một tiêu chí để đánh giá “mức độ hạnh phúc” của mỗi lớp. Xem xét Hình 2:
Nếu “mức độ hạnh phúc” của một lớp tỷ lệ thuận với khoảng cách ngắn nhất từ một điểm của lớp đó đến đường/mặt phân chia, thì ở Hình 2 bên trái, lớp tròn đỏ có vẻ không được “hạnh phúc” lắm, vì đường phân chia quá gần nó so với lớp vuông xanh. Chúng ta cần một đường phân chia sao cho khoảng cách từ điểm gần nhất của mỗi lớp (các điểm được khoanh tròn) đến đường phân chia là bằng nhau, như vậy mới “công bằng”. Khoảng cách bằng nhau này được gọi là margin (lề).
Đã có “công bằng”, chúng ta cần thêm “văn minh”. “Công bằng” mà cả hai lớp đều kém “hạnh phúc” như nhau thì chưa phải là “văn minh” cho lắm.
Xét Hình 2 bên phải, khi khoảng cách từ đường phân chia đến các điểm gần nhất của mỗi lớp là như nhau. Trong hai cách phân chia bởi đường nét liền màu đen và đường nét đứt màu lục, đường nào sẽ làm cho cả hai lớp “hạnh phúc” hơn? Rõ ràng, đó phải là đường nét liền màu đen, vì nó tạo ra một margin rộng hơn.
Margin rộng hơn sẽ giúp phân loại tốt hơn, vì sự phân chia giữa hai lớp trở nên rõ ràng hơn. Đây là một yếu tố quan trọng giúp Support Vector Machine đạt được kết quả phân loại tốt hơn so với Neural Network một lớp (Perceptron Learning Algorithm).
Bài toán tối ưu trong Support Vector Machine (SVM) chính là tìm đường phân chia sao cho margin là lớn nhất. Đây là lý do tại sao SVM còn được gọi là Maximum Margin Classifier (bộ phân loại với margin lớn nhất). Nguồn gốc của tên gọi Support Vector Machine sẽ được giải thích sau.
2. Xây dựng bài toán tối ưu cho SVM
Giả sử chúng ta có một tập huấn luyện (training set) gồm các cặp dữ liệu ((mathbf{x}_1, y_1), (mathbf{x}_2, y_2), dots, (mathbf{x}_N, y_N)), trong đó vector (mathbf{x}_i in mathbb{R}^d) biểu diễn đầu vào của một điểm dữ liệu và (y_i) là nhãn của điểm dữ liệu đó. (d) là số chiều của dữ liệu và (N) là số điểm dữ liệu. Nhãn của mỗi điểm dữ liệu được xác định là (y_i = 1) (lớp 1) hoặc (y_i = -1) (lớp 2), tương tự như trong PLA.
Để dễ hình dung, hãy xem xét trường hợp trong không gian hai chiều (Hình 3). Các phép toán hoàn toàn có thể được tổng quát hóa lên không gian nhiều chiều.
Giả sử các điểm vuông xanh thuộc lớp 1, các điểm tròn đỏ thuộc lớp -1 và đường thẳng (mathbf{w}^Tmathbf{x} + b = w_1x_1 + w_2x_2 + b = 0) là đường phân chia giữa hai lớp. Hơn nữa, lớp 1 nằm về phía dương và lớp -1 nằm về phía âm của đường phân chia. Nếu ngược lại, ta chỉ cần đổi dấu của (mathbf{w}) và (b). Chú ý rằng chúng ta cần tìm các hệ số (mathbf{w}) và (b).
Một điểm quan trọng: với cặp dữ liệu ((mathbf{x}_n, y_n)) bất kỳ, khoảng cách từ điểm đó đến đường phân chia là:
[ frac{y_n(mathbf{w}^Tmathbf{x}_n + b)}{||mathbf{w}||_2} ]Điều này là do (y_n) luôn cùng dấu với phía của (mathbf{x}_n), suy ra (y_n) cùng dấu với ((mathbf{w}^Tmathbf{x}_n + b)), và tử số luôn là một số không âm.
Với đường phân chia như trên, margin được tính là khoảng cách gần nhất từ một điểm đến đường đó (bất kể điểm nào trong hai lớp):
[ text{margin} = min_{n} frac{y_n(mathbf{w}^Tmathbf{x}_n + b)}{||mathbf{w}||_2} ]Bài toán tối ưu trong SVM là tìm (mathbf{w}) và (b) sao cho margin này đạt giá trị lớn nhất:
[ (mathbf{w}, b) = argmax_{mathbf{w}, b} left{ min_{n} frac{y_n(mathbf{w}^Tmathbf{x}_n + b)}{||mathbf{w}||_2} right} = argmax_{mathbf{w}, b}left{ frac{1}{||mathbf{w}||_2} min_{n} y_n(mathbf{w}^Tmathbf{x}_n + b) right} qquad (1) ]Giải trực tiếp bài toán này rất phức tạp, nhưng chúng ta có thể đơn giản hóa nó.
Nhận xét quan trọng: nếu thay vector hệ số (mathbf{w}) bằng (kmathbf{w}) và (b) bằng (kb), trong đó (k) là một hằng số dương, thì đường phân chia không thay đổi, tức khoảng cách từ từng điểm đến đường phân chia không đổi, do đó margin cũng không đổi. Dựa trên tính chất này, ta có thể giả sử:
[ y_n(mathbf{w}^Tmathbf{x}_n + b) = 1 ]với những điểm nằm gần đường phân chia nhất (Hình 4):
Như vậy, với mọi (n), ta có:
[ y_n(mathbf{w}^Tmathbf{x}_n + b) geq 1 ]Bài toán tối ưu ((1)) có thể được viết lại thành bài toán tối ưu có ràng buộc sau:
[begin{aligned}
(mathbf{w}, b) &= arg max_{mathbf{w}, b} frac{1}{||mathbf{w}||_2}
text{subject to:} quad & y_n(mathbf{w}^Tmathbf{x}_n + b) geq 1, quad forall n = 1, 2, dots, N
end{aligned}
qquad (2)
]
Bằng một biến đổi đơn giản, ta có thể đưa bài toán này về dạng:
[begin{aligned}
(mathbf{w}, b) &= arg min_{mathbf{w}, b} frac{1}{2}||mathbf{w}||_2^2
text{subject to:} quad & 1 – y_n(mathbf{w}^Tmathbf{x}_n + b) leq 0, quad forall n = 1, 2, dots, N
end{aligned}
qquad (3)
]
Ở đây, chúng ta đã lấy nghịch đảo hàm mục tiêu, bình phương nó để được một hàm khả vi, và nhân với (frac{1}{2}) để biểu thức đạo hàm đơn giản hơn.
Quan sát quan trọng: Trong bài toán ((3)), hàm mục tiêu là một chuẩn (norm), nên là một hàm lồi. Các hàm bất đẳng thức ràng buộc là các hàm tuyến tính theo (mathbf{w}) và (b), nên chúng cũng là các hàm lồi. Vậy bài toán tối ưu ((3)) có hàm mục tiêu là lồi và các hàm ràng buộc cũng là lồi, nên nó là một bài toán lồi. Hơn nữa, nó là một Quadratic Programming (QP). Thậm chí, hàm mục tiêu là strictly convex vì (||mathbf{w}||_2^2 = mathbf{w}^Tmathbf{I}mathbf{w}) và (mathbf{I}) là ma trận đơn vị – là một ma trận xác định dương. Từ đó suy ra nghiệm cho SVM là duy nhất.
Đến đây, bài toán này có thể được giải bằng các công cụ hỗ trợ tìm nghiệm cho Quadratic Programming, ví dụ như CVXOPT.
Tuy nhiên, việc giải bài toán này trở nên phức tạp khi số chiều (d) của không gian dữ liệu và số điểm dữ liệu (N) tăng lên.
Thông thường, người ta giải bài toán đối ngẫu của bài toán này. Thứ nhất, bài toán đối ngẫu có những tính chất thú vị hơn khiến nó được giải hiệu quả hơn. Thứ hai, trong quá trình xây dựng bài toán đối ngẫu, người ta nhận thấy SVM có thể được áp dụng cho những bài toán mà dữ liệu không linearly separable, tức các đường phân chia không phải là một mặt phẳng mà có thể là các mặt có hình thù phức tạp hơn.
Đến đây, bạn đọc có thể hiểu tại sao chúng ta cần tìm hiểu về đối ngẫu trước khi học về SVM. Nếu bạn muốn hiểu sâu hơn về SVM, hãy đọc Mục 3. Nếu không, bạn có thể chuyển sang Mục 4 để xem ví dụ về cách sử dụng SVM trong lập trình.
Xác định lớp cho một điểm dữ liệu mới: Sau khi tìm được đường phân cách (mathbf{w}^Tmathbf{x} + b = 0), lớp của bất kỳ một điểm nào sẽ được xác định đơn giản bằng cách:
[ text{class}(mathbf{x}) = text{sgn} (mathbf{w}^Tmathbf{x} + b ) ]Trong đó, hàm (text{sgn}) là hàm xác định dấu, nhận giá trị 1 nếu đối số không âm và -1 nếu ngược lại.
3. Bài toán đối ngẫu cho SVM
Nhắc lại rằng bài toán tối ưu ((3)) là một bài toán lồi. Chúng ta biết rằng: nếu một bài toán lồi thỏa mãn điều kiện Slater thì strong duality được thỏa mãn. Và nếu strong duality được thỏa mãn, nghiệm của bài toán chính là nghiệm của hệ điều kiện KKT.
3.1. Kiểm tra điều kiện Slater
Chúng ta sẽ chứng minh bài toán tối ưu ((3)) thỏa mãn điều kiện Slater. Điều kiện Slater nói rằng, nếu tồn tại (mathbf{w}, b) thỏa mãn:
[ 1 – y_n(mathbf{w}^Tmathbf{x}_n + b) < 0, quad forall n = 1, 2, dots, N ]thì strong duality được thỏa mãn.
Việc kiểm tra này tương đối đơn giản. Vì chúng ta biết rằng luôn tồn tại một (siêu) mặt phẳng phân chia hai lớp nếu hai lớp đó là linearly separable, tức bài toán có nghiệm, nên tập khả thi (feasible set) của bài toán tối ưu ((3)) phải khác rỗng. Tức là luôn tồn tại cặp ((mathbf{w}_0, b_0)) sao cho:
[begin{aligned}
1 – y_n(mathbf{w}_0^Tmathbf{x}_n + b_0) &leq 0, quad forall n = 1, 2, dots, N
Leftrightarrow quad 2 – y_n(2mathbf{w}_0^Tmathbf{x}_n + 2b_0) &leq 0, quad forall n = 1, 2, dots, N
end{aligned}
]
Vậy chỉ cần chọn (mathbf{w}_1 = 2mathbf{w}_0) và (b_1 = 2b_0), ta sẽ có:
[ 1 – y_n(mathbf{w}_1^Tmathbf{x}_n + b_1) leq -1 < 0, quad forall n = 1, 2, dots, N ]Từ đó suy ra điều kiện Slater được thỏa mãn.
3.2. Lagrangian của bài toán SVM
Lagrangian của bài toán ((3)) là:
[ mathcal{L}(mathbf{w}, b, lambda) = frac{1}{2} ||mathbf{w}||2^2 + sum{n=1}^N lambda_n(1 – y_n(mathbf{w}^Tmathbf{x}_n + b) ) qquad (4) ]với (lambda = [lambda_1, lambda_2, dots, lambda_N]^T) và (lambda_n geq 0, quad forall n = 1, 2, dots, N).
3.3. Hàm đối ngẫu Lagrange
Hàm đối ngẫu Lagrange được định nghĩa là:
[ g(lambda) = min_{mathbf{w}, b} mathcal{L}(mathbf{w}, b, lambda) ]với (lambda succeq 0).
Giá trị nhỏ nhất của hàm này theo (mathbf{w}) và (b) có thể được tìm bằng cách giải hệ phương trình đạo hàm của (mathcal{L}(mathbf{w}, b, lambda)) theo (mathbf{w}) và (b) bằng 0:
[begin{aligned}
frac{partial mathcal{L}(mathbf{w}, b, lambda)}{partial mathbf{w}} &= mathbf{w} – sum_{n=1}^N lambda_n yn mathbf{x}_n = 0
Rightarrow quad mathbf{w} &= sum{n=1}^N lambda_n yn mathbf{x}_n qquad (5)
frac{partial mathcal{L}(mathbf{w}, b, lambda)}{partial b} &= -sum{n=1}^N lambda_ny_n = 0 qquad (6)
end{aligned}
]
Thay ((5)) và ((6)) vào ((4)), ta thu được (g(lambda)) (phần này được rút gọn):
[ g(lambda) = sum_{n=1}^N lambdan -frac{1}{2}sum{n=1}^N sum_{m=1}^N lambda_nlambda_m y_n y_m mathbf{x}_n^Tmathbf{x}_m qquad (7) ]Đây là hàm số quan trọng nhất trong SVM, chúng ta sẽ thấy rõ hơn ở bài sau.
Xét ma trận:
[ mathbf{V} = left[y_1 mathbf{x}_1, y_2 mathbf{x}_2, dots, y_N mathbf{x}_N right] ]và vector (mathbf{1} = [1, 1, dots, 1]^T), ta có thể viết lại (g(lambda)) dưới dạng:
[ g(lambda) = -frac{1}{2}lambda^Tmathbf{V}^Tmathbf{V}mathbf{lambda} + mathbf{1}^Tlambda qquad (8) ]Đặt (mathbf{K} = mathbf{V}^Tmathbf{V}), ta có một quan sát quan trọng: (mathbf{K}) là một ma trận nửa xác định dương. Thật vậy, với mọi vector (lambda), ta có:
[ lambda^Tmathbf{K}mathbf{lambda} = lambda^Tmathbf{V}^Tmathbf{V}mathbf{lambda} = ||mathbf{V}lambda||_2^2 geq 0. ]Vậy (g(lambda) = -frac{1}{2}lambda^Tmathbf{K}mathbf{lambda} + mathbf{1}^Tlambda) là một hàm concave.
3.4. Bài toán đối ngẫu Lagrange
Kết hợp hàm đối ngẫu Lagrange và các điều kiện ràng buộc của (lambda), ta thu được bài toán đối ngẫu Lagrange:
[begin{aligned}
lambda &= arg max{lambda} g(lambda)
text{subject to:} quad & lambda succeq 0
& sum{n=1}^N lambda_ny_n = 0
end{aligned}
qquad (9)
]
Ràng buộc thứ hai được lấy từ ((6)).
Đây là một bài toán lồi vì ta đang tìm giá trị lớn nhất của một hàm mục tiêu là concave trên một polyhedron.
Bài toán này cũng là một Quadratic Programming và có thể được giải bằng các thư viện như CVXOPT.
Trong bài toán đối ngẫu này, số tham số (parameters) cần tìm là (N), là chiều của (lambda), tức số điểm dữ liệu. Trong khi đó, với bài toán gốc ((3)), số tham số cần tìm là (d + 1), là tổng số chiều của (mathbf{w}) và (b), tức số chiều của mỗi điểm dữ liệu cộng với 1. Trong nhiều trường hợp, số điểm dữ liệu có được trong training set lớn hơn số chiều dữ liệu. Nếu giải trực tiếp bằng các công cụ giải Quadratic Programming, bài toán đối ngẫu có thể phức tạp hơn (tốn thời gian hơn) so với bài toán gốc. Tuy nhiên, điều hấp dẫn của bài toán đối ngẫu này đến từ Kernel Support Vector Machine (Kernel SVM), tức cho các bài toán mà dữ liệu không linearly separable hoặc gần linearly separable. Kernel SVM sẽ được trình bày sau. Ngoài ra, dựa vào tính chất đặc biệt của hệ điều kiện KKT, SVM có thể được giải bằng nhiều phương pháp hiệu quả hơn.
3.5. Điều kiện KKT
Vì đây là một bài toán lồi và strong duality được thỏa mãn, nghiệm của bài toán sẽ thỏa mãn hệ điều kiện KKT sau với biến số là (mathbf{w}, b) và (lambda):
[begin{aligned}
1 – y_n(mathbf{w}^Tmathbf{x}_n + b) &leq 0, quad forall n = 1, 2, dots, N qquad (10)
lambda_n &geq 0, quad forall n = 1, 2, dots, N
lambda_n (1 – yn(mathbf{w}^Tmathbf{x}_n + b)) &= 0, quad forall n = 1, 2, dots, N qquad (11)
mathbf{w} &= sum{n=1}^N lambda_n yn mathbf{x}_n qquad (12)
sum{n=1}^N lambda_ny_n &= 0 qquad (13)
end{aligned}
]
Trong những điều kiện trên, điều kiện ((11)) là thú vị nhất. Từ đó, với (n) bất kỳ, hoặc (lambda_n =0) hoặc (1 – y_n(mathbf{w}^Tmathbf{x}_n + b) = 0). Trường hợp thứ hai chính là:
[ mathbf{w}^Tmathbf{x}_n + b = y_n qquad (14) ]với chú ý rằng (y_n^2 = 1, quad forall n).
Những điểm thỏa mãn ((14)) chính là những điểm nằm gần đường phân chia nhất, là những điểm được khoanh tròn trong Hình 4. Hai đường thẳng (mathbf{w}^Tmathbf{x}_n + b = pm 1) tựa lên các điểm thỏa mãn ((14)). Vậy nên những điểm (vectors) thỏa mãn ((14)) còn được gọi là Support Vectors. Và từ đó, cái tên Support Vector Machine ra đời.
Một quan sát khác, số lượng những điểm thỏa mãn ((14)) thường chiếm số lượng rất nhỏ trong số (N) điểm. Chỉ cần dựa trên những support vectors này, chúng ta hoàn toàn có thể xác định được đường phân cách cần tìm. Nhìn theo một cách khác, hầu hết các (lambda_n) bằng 0. Vậy là mặc dù vector (lambda in mathbb{R}^N) có số chiều lớn, số lượng các phần tử khác 0 của nó rất ít. Nói cách khác, vector (lambda) là một sparse vector. Support Vector Machine vì vậy còn được xếp vào Sparse Models. Các Sparse Models thường có cách giải hiệu quả (nhanh) hơn các mô hình tương tự với nghiệm là dense (hầu hết khác 0). Đây chính là lý do thứ hai khiến bài toán đối ngẫu SVM được quan tâm nhiều hơn bài toán gốc.
Với những bài toán có số điểm dữ liệu (N) nhỏ, ta có thể giải hệ điều kiện KKT bằng cách xét các trường hợp (lambda_n = 0) hoặc (lambda_n neq 0). Tổng số trường hợp phải xét là (2^N). Với (N > 50), đây là một con số rất lớn, và việc giải bằng cách này sẽ không khả thi. Thay vào đó, chúng ta sẽ giải bài toán tối ưu ((9)) bằng CVXOPT và thư viện scikit-learn.
Sau khi tìm được (lambda) từ bài toán ((9)), ta có thể suy ra (mathbf{w}) dựa vào ((12)) và (b) dựa vào ((11)) và ((13)). Rõ ràng ta chỉ cần quan tâm tới (lambda_n neq 0).
Gọi tập hợp (mathcal{S} = {n: lambdan neq 0}) và (N{mathcal{S}}) là số phần tử của tập (mathcal{S}). Với mỗi (n in mathcal{S}), ta có:
[ 1 = y_n(mathbf{w}^Tmathbf{x}_n + b) Leftrightarrow b + mathbf{w}^Tmathbf{x}_n = y_n ]Mặc dù từ một cặp ((mathbf{x}_n, y_n)), ta có thể suy ra ngay được (b) nếu đã biết (mathbf{w}), một phiên bản khác để tính (b) thường được sử dụng và được cho là ổn định hơn trong tính toán là:
[ b = frac{1}{N{mathcal{S}}} sum{n in mathcal{S}}(yn – mathbf{w}^Tmathbf{x}_n) = frac{1}{N{mathcal{S}}} sum_{n in mathcal{S}} left(yn – sum{m in mathcal{S}} lambda_m y_m mathbf{x}_m^T mathbf{x}_nright) qquad (15) ]tức trung bình cộng của mọi cách tính (b).
Trước đó, (mathbf{w}) đã được tính bằng:
[ mathbf{w} = sum_{m in mathcal{S}} lambda_m y_m mathbf{x}_m qquad (16) ]theo ((12)).
Quan sát quan trọng: Để xác định một điểm (mathbf{x}) mới thuộc vào lớp nào, ta cần xác định dấu của biểu thức:
[ mathbf{w}^Tmathbf{x} + b = sum_{m in mathcal{S}} lambda_m ym mathbf{x}_m^T mathbf{x} + frac{1}{N{mathcal{S}}} sum_{n in mathcal{S}} left(yn – sum{m in mathcal{S}} lambda_m y_m mathbf{x}_m^T mathbf{x}_nright) ]Biểu thức này phụ thuộc vào cách tính tích vô hướng giữa các cặp vector (mathbf{x}) và từng (mathbf{x}_n in mathcal{S}). Nhận xét quan trọng này sẽ giúp ích cho chúng ta trong Kernel SVM.
4. Lập trình tìm nghiệm cho SVM
Trong mục này, chúng ta sẽ tìm nghiệm cho SVM bằng hai cách:
- Cách 1: Sử dụng bài toán ((9)) và các công thức ((15)) và ((16)).
- Cách 2: Sử dụng trực tiếp thư viện scikit-learn (sklearn).
Cách thứ nhất giúp minh họa các kết quả tính toán và so sánh với nghiệm tìm được bằng cách thứ hai.
4.1. Tìm nghiệm theo công thức
Đầu tiên, chúng ta cần import các thư viện cần thiết và tạo dữ liệu giả (dữ liệu này giống như dữ liệu đã dùng trong các hình trên, nên chúng ta biết chắc rằng hai lớp là linearly separable):
(Code mẫu trong bài viết gốc)
Tiếp theo, giải bài toán ((9)) bằng CVXOPT:
(Code mẫu trong bài viết gốc)
Kết quả cho thấy hầu hết các giá trị của lambda đều rất nhỏ, cỡ (10^{-9}) hoặc (10^{-10}). Đây là các giá trị bằng 0, nhưng do sai số tính toán nên khác 0 một chút. Chỉ có 3 giá trị khác 0, dự đoán sẽ có 3 support vectors.
Tìm support set (mathcal{S}) rồi tìm nghiệm của bài toán:
(Code mẫu trong bài viết gốc)
Minh họa kết quả:
(Code mẫu trong bài viết gốc)
Đường màu đen đậm ở giữa chính là đường phân cách tìm được bằng SVM. Điều này cho thấy các tính toán có khả năng chính xác. Để kiểm tra lại, chúng ta sẽ tìm nghiệm bằng các công cụ có sẵn, ví dụ như scikit-learn.
4.2. Tìm nghiệm bằng thư viện
Sử dụng hàm sentayho.com.vn. Các bài toán thực tế thường dùng thư viện libsvm, được viết bằng ngôn ngữ C, với API cho Python và Matlab.
(Code mẫu trong bài viết gốc)
Kết quả này khá giống với kết quả tìm được ở phần trên. Có nhiều tùy chọn cho SVM, chúng ta sẽ dần tìm hiểu trong các bài sau.
5. Tổng kết và thảo luận
- Với bài toán phân loại nhị phân (binary classification) mà hai lớp là linearly separable, có vô số các siêu phẳng giúp phân biệt hai lớp. Với mỗi đường phân cách, ta có một classifier. Khoảng cách gần nhất từ một điểm dữ liệu đến đường phân cách ấy được gọi là margin của classifier đó.
- Support Vector Machine là bài toán tìm đường phân cách sao cho margin tìm được là lớn nhất, đồng nghĩa với việc các điểm dữ liệu “an toàn” nhất so với đường phân cách.
- Bài toán tối ưu trong SVM là một bài toán lồi với hàm mục tiêu strictly convex, và nghiệm là duy nhất. Hơn nữa, bài toán tối ưu đó là một Quadratic Programming (QP).
- Mặc dù có thể trực tiếp giải SVM qua bài toán tối ưu gốc này, thông thường người ta giải bài toán đối ngẫu. Bài toán đối ngẫu cũng là một QP, nhưng nghiệm là sparse, nên có những phương pháp giải hiệu quả hơn.
- Với các bài toán mà dữ liệu gần linearly separable hoặc nonlinear separable, có những cải tiến khác của SVM để thích nghi với dữ liệu đó.
- Mã nguồn tham khảo.