Kernel SVM

on 17 Tháng 8 2021.

Tóm tắt:

Bài viết này nhằm mục đích giới thiệu về thuật toán học SVM. Tiếp theo, ta sẽ tìm hiểu về phương pháp Kernel trong việc đưa bài toán phức tạp về mặt hình học thành một bài toán giản đơn hơn để có thể áp dụng SVM, và cuối cùng ta sẽ tìm hiểu một số ứng dụng liên quan đến thuật toán này.

1. Bài toán phân lớp nhị phân:

Cho một bài toán phân lớp dữ liệu thành theo hai lớp, gọi là , với đầu vào là một đối tượng với là các đặc trưng của X. Để giải quyết bài toán này, ta có rất nhiều phương pháp. Một phương pháp đơn giản và hiệu quả là naives bayes, dựa trên ý tưởng tính toán và so sánh các xác suất X thuộc lớp và . Trong bài viết này, chúng ta tìm hiểu một phương pháp khác.

Để ý rằng các đối tượng X có thể được xem như là một điểm trên không gian Euclid n chiều. Cho một tập dữ liệu huấn luyện .Chia thành hai phần và , trong đó là các dữ liệu thuộc lớp 1 và là các dữ liệu thuộc lớp 2. Trên không gian n chiều gồm các điểm thuộc , ta sẽ tìm cách chia các điểm thuộc tách biệt với các điểm thuộc .

Nói cách khác, ta tìm cách cắt không gian n chiều ra làm đôi, một nửa chứa các điểm thuộc , nửa còn lại chứa . Để cho việc tìm không gian phân cách được đơn giản, ta sẽ chọn không gian con của xác định bởi phương trình tuyến tính . Ta gọi không gian con có dạng này là siêu phẳng tuyến tính ( linear hyperplane). Khi đó, ta sẽ xét xem thuộc vào nửa nào, nếu nó thuộc vào một nửa không gian chứa các điểm thuộc thì ta sẽ đưa X vào lớp 1, tương tự nếu X thuộc vào nửa còn lại. Bộ dữ liệu có thể tách được bằng cách trên sẽ được gọi là phân biệt tuyến tính.

Tất nhiên, không phải khi nào ta cũng có một bộ dữ liệu phân biệt tuyến tính, tuy nhiên ta vẫn có thể chấp nhận một số ít điểm bị lỗi. Vấn đề này sẽ được trình bày trong một phần khác. Ta chỉ sẽ tìm hiểu trường hợp bộ dữ liệu của chúng ta hoàn toàn phân biệt tuyến tính.

2. Support vector Machine (SVM):

Mục tiêu của SVM là tìm ra một siêu phẳng trong không gian N chiều (ứng với N đặc trưng) chia dữ liệu thành hai phần tương ứng với lớp của chúng. Nói theo ngôn ngữ của đại số tuyển tính, siêu phẳng này phải có lề cực đại và phân chia hai bao lồi và cách đều chúng.

Hình 1. ([2]) Sự phân ca các bao lồi bằng hai đường thẳng vuông góc.

Để phân chia hai lớp dữ liệu, rõ ràng là có rất nhiều siêu phẳng có thể làm được điều này. Mặc dù vậy, mục tiêu của chúng ta là tìm ra siêu phẳng có lề rộng nhất tức là có khoảng cách tới các điểm của hai lớp là lớn nhất. Ta có thể viết lại siêu phẳng cần tìm là H: , trong đó là vector pháp tuyến của siêu phẳng, với thuật toán SVM, ta có thể đánh nhãn một lớp là -1, lớp còn lại là 1. Các data có nhãn -1 sẽ nằm phía dưới H, gồm các điểm sao cho , ngược lại, các data có nhãn 1 sẽ thoả

Hình 2. ([4]) Mô tả thuật toán SVM bằng hình ảnh.

Theo hình 2, Margin là khoảng cách từ mặt phẳng phân tách( decision boundary) đến các điểm dữ liệu gần nó nhất. Các điểm dữ liệu gần nhất này hợp thành đường thẳng và được gọi là support vectors. Mục tiêu của thuật toán SVM là đi tìm mặt phẳng phân tách có margin lớn nhất . Vì vậy thuật toán này đôi khi còn được gọi là large margin classification. Bằng một vài biến đổi, ta có margin = .

Ta có thể tính khoảng cách đó bằng phép lấy độ rộng biên từ mặt biên gốc tới mặt phân tách cần tìm. Từ đây, bài toán trở thành xác định w và b sao cho đạt lớn nhất và các điểm dữ liệu , hay ||w|| đạt nhỏ nhất, nó chính là bài toán tối ưu hoá:

với ràng buộc

Có thể thấy đây là bài toán tối ưu hoá bình phương vì:

Sử dụng phương pháp nhân tử Lagrange, với mỗi ràng buộc , ta sẽ lấy nhân tử tương ứng là , bài toán tối ưu sẽ trở thành:

(1)

Từ (1), ta tìm gía trị nhỏ nhất thông qua:

(2)

(3)

Thay vào (1), ta được:

(4)

Từ đó, ta chuyển sang bài toán tối ưu:

với ràng buộc và

Sau khi tìm được , ta sẽ tìm được w và b. Khi đó ta tìm được mặt phân lớp .Từ mặt phân lớp trên, xét dữ liệu đầu vào , ta có phân lớp: .

3. Phương pháp kernel áp dụng cho Kernel SVM:

Trong một trường hợp rất tồi tệ (như hình dưới), bộ dữ liệu không những không phân biệt tuyến tính, và ta cũng không thể tìm ra cách để giảm nhẹ thiệt hại nhất có thể nếu cố gắng tìm cách phân chia bộ dữ liệu này thành hai lớp trên mặt phẳng. Trong trường hợp này, các điểm dữ liệu có vị trí quá sát nhau, thế nên ta cần tìm cách để các điểm dữ liệu này trở nên thưa hơn. Một ý tưởng đơn giản cho việc này là tìm một đơn ánh từ không gian ban đầu vào không gian có số chiều lớn hơn để tìm siêu phẳng phân chia các điểm dữ liệu trên. Đây được gọi là phương pháp kernel.

Nói tóm lại, Ý tưởng của phương pháp kernel nói chung là tìm một phép biến đổi sao cho dữ liệu ban đầu là không phân biệt tuyến tính được biến sang không gian mới. Ở không gian mới này, dữ liệu trở nên phân biệt tuyến tính. Ở đây, ta tìm hàm sao cho hàm này biến dữ liệu x trên không gian đầu thành (x) trong không gian mới.

Hình 3 ([1]). Dữ liệu trong không gian 2 chiều bị co cụm.

Hình 4.([1]) Dữ liệu sau khi được chuyển vào không gian mới và thoả

mãn điều kiên thuật toán SVM (mặt màu vàng phân chia hai nhóm dữ liệu)

Phát biểu toán học cho phương pháp kernel như sau:

Cho không gian vector A hai chiều bất kì và không gian vector B, gọi là hàm tuyến tính đi từ A vào B. Khi đó, hàm Kernel k sẽ được định nghĩa là:

Theo công thức (4), ta có:

Tác động hàm lên (4), ta được:

(6)

Đây chính là công thức cho SVM trên không gian mới. Tiếp theo, thay (5) vào biểu thức (6), ta được:

(7)

(7) chính là công thức thay thế cho công thức (4) ở phần 2. Như vậy phương pháp kernel đã giúp chúng ta giải quyết vấn đề trên.

Thực chất, ta hoàn toàn có thể coi các điểm dữ liệu ở không gian cũ là hình chiếu của các điểm dữ liệu nằm trên không gian mới. Hàm kernel làm nhiệm vụ kéo giãn khoảng cách của các điểm ra cho đến khi ở trên không gian mới, khoảng cách giữa các điểm là đủ rộng để tìm ra siêu phẳng phân chia chúng.

Một vài hàm kernel thông dụng:

Đây là trường hợp đơn giản với kernel chính tích vô hướng của hai vector:

, d là một số dương để chỉ bậc của đa thức. dd có thể không là số tự nhiên vì mục đích chính của ta không phải là bậc của đa thức mà là cách tính kernel. Polynomial kernel có thể dùng để mô tả hầu hết các đa thức có bậc không vượt quá d nếu d là một số tự nhiên.

. Đây cũng chính là sigmoid function.

4. Một số ứng dụng:

Ta sẽ tìm hiểu một vài ứng dụng của Kernel SVM. Ứng dụng đầu tiên là bài toán xử lí ảnh, phân loại ảnh nam nữ. Để sử dụng Kernel SVM, ta trước tiên phải vector hoá các ảnh. Một cách vector hoá như sau:

Hình 5. ([3]). Cách lấy các đặc trưng trên gương mặt.

Từ ảnh trên, Ta đặt 11 điểm feature trên gương mặt. Chọn ra 7 khoảng cách quan trọng giữa các điểm trên gương mặt đó, ta sẽ có một vector f thuộc không gian 7 chiều. Xây dựng một tập huấn luyện gồm các vector biểu diễn ảnh. Đánh nhãn các vector đó là 1 nếu là nam và -1 nếu là nữ. Và lúc này ta áp dụng được phương pháp SVM để xây dựng bộ phân lớp.

Một ứng dụng khác là cho bài toán lọc e-mail spam: Cho một bộ dữ liệu huấn luyện gồm các email spam và không spam. Ta muốn xây dựng một bộ phân lớp để lọc các mail spam. Trong bài toán này, mail spam sẽ được đánh dấu -1 và không spam được đánh dấu là 1.

Cho một tập n từ khoá được lấy ra từ cả spam mail lẫn unspam mail. Mỗi email trong tập huấn luyện sẽ được biểu diễn thành dạng vector n chiều m =, trong đó là số lần mà từ xuất hiện trong mail. Đến đây, ta hoàn toàn có thể áp dụng kernel SVM để giải quyết bài toán lọc spam.

5. Tài liệu tham khảo:

[1] Bài 19: support vector machine. https://machinelearningcoban.com/2017/04/09/smv/.
[2] Giới thiệu về thuật toán SVM. https://viblo.asia/p/gioi-thieu-ve-support-vector-machine-svm-6J3ZgPVElmB

[3] Support vector machine in gender recognition. ZOFIA STAWSKA, PIOTR MILCZARSKI.

[4] SVM Algorithm as Maximum Margin Classifier. Ajitesh Kumar. https://vitalflux.com/svm-algorithm-maximum-margin-classifier/ .