CS Study Fun – Khoa học máy tính

Learn & Enjoy …

Phân lớp bằng siêu phẳng (4) – Máy phân lớp sử dụng véctơ hỗ trợ (Support Vector Machines) (1)

Posted by Trần Quốc Long on Tháng Tám 2, 2008

Ở bài đầu tiên, ta đã thấy rằng nếu tập mẫu học phân lớp tuyến tính được, thuật toán huấn luyện Perceptron sẽ tìm ra trọng số \displaystyle W=(w,b) phân tách tập mẫu học này. Đồng thời, nếu lề của siêu phẳng \displaystyle h lớn, thuật toán sẽ hội tụ rất nhanh. Một cách rất trực quan, ta thấy rằng nếu lề của siêu phẳng lớn, ta càng giảm được khả năng phân lớp nhầm (xem hình sau).

Lề của siêu phẳng phân lớp

Giáo sư Vapnik trong lý thuyết VC của mình đã tìm ra được quan hệ giữa lề \displaystyle h và ước lượng xác suất lỗi khi phân lớp bằng siêu phẳng. Theo đó, khi \displaystyle h lớn, xác suất lỗi càng gần với giá trị tối ưu (nhỏ nhất). Vì vậy, ông gợi ý tìm siêu phẳng phân lớp có lề lớn nhất.

Bài toán tìm siêu phẳng có lề lớn nhất:

Giả sử siêu phẳng \displaystyle \langle w,x\rangle-b = 0 phân chia tập mẫu học \displaystyle D=\{(x_i,y_i)\}_{i=1}^N, tức là

\displaystyle y_i(\langle w,x_i\rangle-b) > 0,\forall i (nhớ lại rằng \displaystyle y_i=\pm 1

Khoảng cách từ mỗi điểm trong tập mẫu đến siêu phẳng bằng

\displaystyle h_i = \frac{y_i(\langle w,x_i\rangle-b)}{\|w\|}

Suy ra, lề của siêu phẳng là

\displaystyle h = \min_i h_i = \min_i \frac{y_i(\langle w,x_i\rangle-b)}{\|w\|}

Bài toán tìm siêu phẳng có lề lớn nhất có thể phát biểu như một bài toán tối ưu hóa

\displaystyle \max_{w,b,h} ~ h với các ràng buộc \displaystyle y_i(\langle w,x_i\rangle-b) > 0,\forall i=1,\ldots,N\\y_i(\langle w,x_i\rangle-b) \geq h\|w\|,\forall i=1,\ldots,N

Để ý là giá trị tối ưu của bài toán không thay đổi nếu ta nhân \displaystyle W=(w,b) với một hằng số, do vậy, nếu ta chọn \displaystyle \|w\|=\frac{1}{h} thì bài toán trở thành

\displaystyle \min_{w,b}~\|w\| với các ràng buộc \displaystyle y_i(\langle w,x_i\rangle-b) \geq 1,\forall i=1,\ldots, N

Bài toán này khó giải nhưng nếu ta chuyển hàm mục tiêu từ \displaystyle \|w\| sang \displaystyle \frac{1}{2}\|w\|^2 thì bài toán trở thành bài toán quy hoạch lồi (hàm mục tiêu lồi, ràng buộc tuyến tính) có nghiệm tối ưu tương đương bài toán cũ. Vậy ta cần giải bài toán quy hoạch lồi sau:

\displaystyle \min_{w,b}~\frac{1}{2}\|w\|^2 với các ràng buộc \displaystyle y_i(\langle w,x_i\rangle-b) \geq 1,\forall i=1,\ldots, N

Bài toán này gọi là bài toán tối ưu gốc. Bây giờ ta tìm hiểu bài toán đối ngẫu Lagrange của bài toán gốc, ta có hàm Lagrange

\displaystyle L(w,b,\lambda) = \frac{1}{2}\|w\|^2-\sum_{i=1}^N \lambda_i [y_i (\langle w,x_i\rangle-b)-1]

Để tìm \displaystyle \underline{L}(\lambda) = \inf_{w,b}L(w,b,\lambda) ta tính đạo hàm của \displaystyle L(w,b,\lambda) theo \displaystyle w,b và đặt bằng 0:

\displaystyle \begin{cases}\displaystyle \frac{\partial L(w,b,\lambda)}{\partial w} = w - \sum_{i=1}^N \lambda_i y_i x_i = 0\\ \displaystyle \frac{\partial L(w,b,\lambda)}{\partial b} = \sum_{i=1}^N \lambda_i y_i = 0\end{cases} \displaystyle \Leftrightarrow \begin{cases} \displaystyle w = \sum_{i=1}^N \lambda_i y_i x_i\\ \displaystyle \sum_{i=1}^N \lambda_i y_i = 0\end{cases}

Thế vào \displaystyle L(w,b,\lambda) ta có

\displaystyle \underline{L}(\lambda) = \frac{1}{2}\left\|\sum_{i=1}^N \lambda_i y_i x_i\right\|^2 -\sum_{i=1}^N \lambda_i y_i \sum_{j=1}^N \lambda_j y_j \langle x_j,x_i\rangle + \sum_{i=1}^N \lambda_i\displaystyle =\sum_{i=1}^N \lambda_i -\frac{1}{2} \sum_{i,j=1}^N\lambda_i \lambda_j y_i y_j \langle x_i,x_j\rangle

Vậy bài toán đối ngẫu Lagrange là

\displaystyle \max_\lambda \sum_{i=1}^N \lambda_i -\frac{1}{2} \sum_{i,j=1}^N\lambda_i \lambda_j y_i y_j \langle x_i,x_j\rangle với các ràng buộc \displaystyle \lambda\geq 0\\ \sum_{i=1}^N \lambda_i y_i = 0

Nếu đặt \displaystyle K = [K_{ij}]_{N \times N} = [y_i y_j \langle x_i,x_j\rangle]\displaystyle 1_N = \left[\begin{array}{ccc}1 & \ldots & 1\end{array}\right]^T\in \mathbb{R}^n thì bài toán trên tương đương với

\displaystyle \max_\lambda~ \lambda^T 1_N - \frac{1}{2} \lambda^T K \lambda với các ràng buộc \displaystyle \lambda \geq 0\\ \lambda^Ty = 0

Bài toán này gọi là bài toán tối ưu bậc 2 (Quadratic Programming), một bài toán tối ưu có thể giải quyết bằng nhiều thuật toán khác nhau.

Điều kiện Karush-Kuhn-Tucker: Một trong hai điều kiện KKT ở nghiệm tối ưu của bài toán tối ưu trên là

\displaystyle \lambda_i[y_i(\langle w,x\rangle-b)-1] = 0

Có 2 trường hợp xảy ra

  1. Nếu \displaystyle \lambda_i = 0, do \displaystyle w = \sum_{i=1}^N \lambda_i y_i x_i, mẫu học \displaystyle x_i không tham gia vào việc tính \displaystyle w (và \displaystyle b).
  2. Nếu \displaystyle \lambda_i \neq 0, suy ra

    \displaystyle y_i(\langle w,x_i\rangle-b) = 1\displaystyle \Rightarrow b = \begin{cases}\langle w,x_i\rangle - 1&y_i=+1\\\langle w,x_i\rangle + 1&y_i=-1\end{cases}

    Nghĩa là mẫu học \displaystyle x_i nằm trên lề của siêu phẳng \displaystyle \langle w,x\rangle-b=0. Khi đó người ta gọi \displaystyle x_ivéctơ hỗ trợ (support vector) vì các véctơ này nằm dọc 2 bên lề của siêu phẳng, “đỡ” cho siêu phẳng này.

Như vậy, khi tập mẫu học phân tách tuyến tính được, chỉ một số mẫu học tham gia vào quá trình tính toán \displaystyle w hơn nữa

\displaystyle f(x) = \langle w,x\rangle-b = \sum_{i=1}^N \lambda_i y_i \langle x_i,x\rangle -b

tức là cũng chỉ có một số mẫu học (và \displaystyle \lambda_i tương ứng) tham gia vào việc tính hàm \displaystyle f(x). Trong ví dụ ở hình đầu bài, ta thấy chỉ có 3 vectơ hỗ trợ trong toàn bộ tập mẫu học.

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

 
%d bloggers like this: