Phần 1: Tổng quan về mô hình SVMPermalink

Giới thiệuPermalink

Mô hình Support Vector Machine - SVM là một mô hình máy học thuộc nhóm Supervised Learning được sử dụng cho các bài toán Classification (Phân lớp) và Regression (Hồi quy).

Ta còn có thể phân loại mô hình này vào loại mô hình Tuyến tính (Linear Model), loại này bao gồm các thuật toán có chung một dạng hypothesis function (có thể gọi là Hàm giả định, tóm lại là cách nó đưa ra một dự đoán - prediction) có dạng là những đường thẳng (trong không gian 2 chiều), mặt phẳng, siêu phẳng (trong không gian nhiều chiều). Chúng ta cùng nhau thử nói sơ lược lại các mô hình Tuyến tính này.

Sơ lược các mô hình tuyến tính khácPermalink

Mô hình tuyến tính quan trọng nhất mà ai học qua Machine Learning đều biết là Linear Regression (Hồi quy tuyến tính). Sơ lược về mô hình này là tìm một đường thẳng khớp nhất với các điểm dữ liệu, để nắm bắt được xu hướng, mỗi tương quan, … của dữ liệu.

Mô hình Linear Regression

Như trong hình trên, hypothesis function của Linear Regression là một đường thẳng có dạng y=wTx+b.

Một mô hình tuyến tính khác dùng cho bài toán Classification nổi tiếng là Logistic Regression (Hồi quy logistic). Mặc dù dạng hypothesis function của nó là một đường cong, sau khi biến đổi bằng hàm phi tuyến sigmoid, nhưng bản chất của nó vẫn là một mô hình tuyến tính, hàm sigmoid là một hàm phi tuyến mang ý nghĩa biến đổi các giá trị liên tục thành những giá trị xác suất. Mô hình Logistic Regression có hypothesis function dạng y=sigmoid(wTx+b).

Mô hình Logistic Regression

Nền tảng của mô hình SVMPermalink

Mô hình SVM đặt ra vấn đề giải quyết 1 bài toán đơn giản nhất là phân lớp 2 lớp dữ liệu. Với một tập dữ liệu sơ khởi nhất gồm 2 lớp được tách rõ rệt với nhau, vậy ta nên chọn đường nào có khả năng tổng quát cao nhất ?

Tập các hypothesis của SVM

Tác giả của mô hình SVM là Vladimir Vapnik cho rằng “đường thẳng phân tách 2 lớp dữ liệu cách đều lớn nhất sẽ cho ra khả năng tổng quát tốt nhất”. Chúng ta gọi khoảng cách đều đó là margin (lề). Như trong ví dụ trên, đường thẳng H2 sẽ là đường thẳng tốt nhất mà ta có thể chọn được để phân tách 2 lớp. Vậy nên mô hình SVM chỉ có ý tưởng cơ bản như vậy tìm đường thẳng margin lớn nhất.

Tiêp theo, nếu mọi người tự tin vào việc đọc những công thức toán học, hãy tiếp tục phần 2, nếu không hãy tìm xuống phần kết luận cuối cùng về mô hình SVM :^)

Phát biểu bài toán cho mô hình SVMPermalink

Input: Bộ dữ liệu gồm 2 lớp

Output: Một đường thẳng phân cách 2 lớp với khoảng cách từ đường thẳng đó tới điểm gần nhất của từng lớp, là lớn nhất có thể.

Lý thuyết toán họcPermalink

Đây là phần mình sẽ tóm tắt lại lý thuyết toán để tìm ra đường thẳng tối ưu của SVM. Các bạn nếu ngại đọc các phần chứng minh toán có thể kéo thẳng xuống phần Kết luận tóm tắt giải thuật.

Tập Hypothesis của SVM:Permalink

Tập Hypothesis của SVM có dạng:

y=h(x)=sign(wTx+b)    (1)

Với xRd,wRd,bR, ta có x là bộ dữ liệu trong không gian d chiều và w,b là các tham số về siêu phẳng trong không gian để phân tách.

Ngoài ra sign(x) là một hàm xác định dấu, nếu x>=0 sign(x)=1) ngược lại nếu x<0 sign(x)=1. Đây là cách phân lớp của từng điểm dữ liệu y1,+1.

Hypothesis Test cho SVM

Bài toán tối ưu của SVMPermalink

Mục tiêu chính của SVM là tìm ra một mặt phẳng, chia tách 2 phần dữ liệu với “lề” (margin) lớn nhất.

Ta có bài toán tối ưu:

Gọi những xn là những điểm dữ liệu gần nhất với mặt phẳng wTx+b. Với kiến thức hình học cấp 3, ta dễ dàng tính được khoảng cách từ xn tới mặt phẳng là:

|wTxn+b|||w||2    (2)

Với

||w||2=i=1dwi2

Để thuận tiện cho việc tính toán, sẽ normalize lại vector w sao cho:

|wTxn+b|=1    (3)

Normalize lại w

Từ đây ta có 2 nhận xét:

  • Những điểm xn được phân vào lớp +1 đều có giá trị wTx+b1, tương tự nếu được phân vào lớp 1, giá trị wTx+b1. Đây chính là cách phân lớp cho các điểm dữ liệu sau khi normalize w. Đặt N là số lượng điểm dữ liệu, ta có yn(wTxn+b)>=1 n=1,2,3N

  • Độ lớn của “lề” lớn nhất cho một mặt phẳng wTx+b

2||w||2

Ta phát biểu bài toán tối ưu cho SVM như sau:

maximize 2||w||2 subject to yn(wTxn+b)>=1n=1,2,3...N

Hay ta có thể viết lại bài toán trên thành:

minimize 12wTw                                                                          (4) subject to yn(wTxn+b)>=1 n=1,2,3...N

Phương pháp tối ưu cho SVM:Permalink

Từ đây chúng ta thấy áp dụng phương pháp nhân tử Lagrange (đã được học trong Giải tích 1) (đọc lại phương pháp nhân tử Lagrange để tìm cực trị ở đây) với ràng buộc bất đẳng thức:

L(w,b,α)=12wTwn=1Nαn(yn(wTxn+b)1) (4)Minimize with w,b;Maximize with α:αn0 L(w,b,α)    ()

Nhìn chung đây là bài toán tối ưu từ dạng primal form cho bài toán (4) thành dạng dual form (đối ngẫu với min, max) của bài toán (*).

Để giải bài toán (*), ta có thể giải lần lượt từ Maximize cho w,b khi coi các αn là hằng số; tiếp theo là giải Minimize với αn0 coi w,b là hằng số. Mặc dù cách giải này sẽ cần một số điều kiện để tối ưu, nhưng trong phạm vi bài giới thiệu chúng sẽ tạm thời được lược bỏ (nếu mọi người vẫn muốn đọc các phần chứng minh và điều kiện tối ưu tham khảo tại đây).

Minimize with w,bPermalink

Minimize L(w,b,α)=12wTwn=1Nαn(yn(wTxn+b)1) with w,b

Lấy đạo hàm của w,b và đặt đạo hàm bằng 0, ta có:

Lw=wn=1Nαnynxn=0w=n=1Nαnynxn    (5) Lb=n=1Nαnyn=0n=1Nαnyn=0    (6)

Thay thế (5) và (6) vào L(w,b,α) và rút gọn, ta có:

L(α)=n=1Nαn12n=1Nm=1MynymαnαmxnTxm

Vậy bài toán tối ưu ta chỉ còn lại:

Maximize L(α)=n=1Nαn12n=1Nm=1MynymαnαmxnTxm   ()

Với các αn0 với mọi n=1,2,N, cộng thêm ràng buộc từ (6) n=1Nαnyn=0

Vậy từ một dạng primal form (4), ta đã chuyển về dạng dual form như bài toán (*), và cuối cùng ta chỉ cần tìm ra các nghiệm αn để hoàn thành quá trình tối ưu cho SVM.

Việc tìm ra các αn sẽ sử dụng Quadratic Programming (QP - dịch là quy hoạch toàn phương) để giải ra. Vậy nên ta có thể tóm tắt lại các bước của việc tối ưu cho SVM như sau:

  1. Giải các nghiệm αn thoả:
αn=argminα12n=1Nm=1NynymαnαmxnTxmn=1Nαn

Với các αn0n=1Nαnyn=0

  1. Từ các αn, ta tính được w theo (5):
w=n=1Nαnynxn    (5)

Một chú ý khi giải các αn, thực tế khi giải ra bằng QP chỉ có một số αn>0, nên ta có thể viết lại: w=αn>0αnynxn

Mặt khác, với những αn>0, ta lại có αn(yn(wT+b)1)=0 (Từ một trong những điều kiện Karush-Kuhn-Tucker - KKT để chuyển từ dạng primal form thành dual form), suy ra: yn(wT+b)=1.

Từ nhận xét này, ta có thể khẳng định những điểm xn có các αn>0 tương ứng là những điểm nằm gần nhất với mặt phẳng wTx+b và có khoảng cách tới mặt phẳng

1||w||2

Chúng đóng góp vào việc tính toán ra vector pháp tuyến w của mặt phẳng, vậy nên ta gọi những điểm xn đó là những support vector.

  1. Tìm hệ số b. Ta có thể tìm hệ số b bằng cách dùng bất kì support vector nào vì yn(wTxn+b)=1.

Kết luận chung bài toán SVMPermalink

  • Vì sao gọi là Support Vector Machine ? Vì mô hình này được xây dựng dựa trên việc tìm ra các điểm xn đóng góp vào việc tìm ra mặt phẳng phân tách dữ liệu bài toán, cụ thể hoá bằng việc giải ra bài toán tối ưu với những αn tương ứng xn ta đã chứng minh ở trên.

  • Khả năng tổng quát của mô hình SVM như thế nào ? Đây chính là một kết quả được đánh giá từ những phân tích thực tế. Người ta thấy rằng mô hình càng cho ra ít support vector thì khả năng tổng quát càng tốt. Kết quả tổng quát được tóm tắt với biểu thức sau:

    E[Errorout]E[\#SV]N1

    Nhìn chung người ta luôn kì vọng vào việc tìm ra thật ít Support Vector để làm giảm cận trên của độ lỗi trong thực tế (Errorout). Nếu có dữ liệu 1000 điểm, bạn tìm ra được khoảng 10 support vector, thì mô hình của bạn khá là tốt :)

  • Ưu điểm của SVM: Nhìn chung đây là một mô hình có ý tưởng đơn giản, có khả năng giải thích bằng toán học và tìm ra tính tổng quát của mô hình rất thuận lợi. Tính tổng quát của mô hình có thể được áp dụng trong thực tế với dữ liệu nhiều chiều và phức tạp. Những cách tối ưu này sẽ được giới thiệu trong phần sau.

  • Nhược điểm của SVM: Mô hình SVM dựa trên bài toán tối ưu bằng Quadratic Programming, nhìn chung đây là bài toán tối ưu với chi phí rất tốn kém, trong trường hợp các vector xn càng nhiều chiều, hoặc số điểm dữ liệu N càng lớn cũng tốn rất nhiều thời gian.

Leave a comment