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

Learn & Enjoy …

Máy phân lớp sử dụng véctơ hỗ trợ (Support Vector Machines) (2) – Trường hợp không phân tách tuyến tính được

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

Trong bài trước, ta đã tìm hiểu cách SVM chọn siêu phẳng với lề lớn nhất. Tuy nhiên, bài toán tối ưu chỉ giải được (có nghiệm) nếu tập mẫu học phân tách tuyến tính được. Vì thế, cách tìm lề lớn nhất như trong bài trước còn gọi là lề cứng (hard margin). Vậy còn trường hợp không phân tách tuyến tính được thì sao? Rõ ràng, nếu ta vẫn dùng siêu phẳng thì phải chấp nhận có một số mẫu học không thể phân lớp được. Trường hợp này, giáo sư Vapnik gợi ý ta “mềm hóa” các ràng buộc của lề (phương pháp này gọi là lề mềm (soft margin)). Cụ thể bài toán tối ưu (gốc) chuyển thành như sau

\displaystyle \min_{w,b,\xi}~\frac{1}{2}\|w\|^2+\frac{1}{2} C\left(\sum_{i=1}^N\xi_i\right)^2 với các ràng buộc \displaystyle \begin{array}{l} y_i(\langle w,x_i\rangle-b) \geq 1-\xi_i\\\xi_i\geq 0\end{array},\forall i=1,\ldots, N

Như vậy các ràng buộc cứng \displaystyle y_i(\langle w,x_i\rangle-b) \geq 1 được cho phép vi phạm (mềm hóa). Đồng thời, độ “mềm” của ràng buộc bị giới hạn vì hàm mục tiêu chứa đại lượng \displaystyle C\left(\sum_{i=1}^N\xi_i\right)^2. Bây giờ ta tìm bài toán đối ngẫu Lagrange:

\displaystyle L(w,b,\xi,\lambda,\gamma)=\frac{1}{2}\|w\|^2+ \frac{1}{2}C\left(\sum_{i=1}^N\xi_i\right)^2 \displaystyle -\sum_{i=1}^N \lambda_i [y_i(\langle w,x_i\rangle-b)-1+\xi_i]-\sum_{i=1}^N\gamma_i\xi_i

Lấy đạo hàm theo \displaystyle w,b,\xi ta có

\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\\ \displaystyle \frac{\partial L(w,b,\lambda)}{\partial \xi_i} = C\left(\sum_{j=1}^N \xi_j\right) - \lambda_i - \gamma_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 \\ \displaystyle \lambda_i+\gamma_i = C\sum_{j=1}^N \xi_j = \delta\end{cases}

Thay vào ta được

\displaystyle \underline{L}(\lambda,\gamma,\delta) = \inf_{w,b,\xi} L(w,b,\xi,\lambda,\gamma) = \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-\frac{\delta^2}{2C}

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

\displaystyle \max_{\lambda,\gamma,\delta} \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-\frac{\delta^2}{2C} với các ràng buộc \displaystyle \sum_{i=1}^N \lambda_i y_i = 0 \\ \lambda_i + \gamma_i = \delta \\ \lambda_i,\gamma_i \geq 0

Loại bỏ biến \displaystyle \gamma, bài toán trên tương đương với

\displaystyle \max_{\lambda,\delta} \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-\frac{\delta^2}{2C} với các ràng buộc \displaystyle\sum_{i=1}^N \lambda_i y_i = 0\\\lambda_i\leq\delta \\\lambda_i,\delta\geq 0

Đây cũng là bài toán tối ưu hóa bậc 2 (Quadratic Programming) giống như trong trường hợp sử dụng lề cứng.

Nhận xét:

  1. Bằng việc mềm hóa các ràng buộc và thay đổi hàm mục tiêu, bài toán tối ưu vẫn là bài toán quy hoạch bậc 2. Tuy nhiên, các véctơ hỗ trợ lúc này sẽ bao gồm:
    • Các véctơ nằm trên lề \displaystyle y_i(\langle w,x_i\rangle-b) = 1 (khi \displaystyle \xi_i = 0)
    • Các véctơ nằm bên trong lề \displaystyle y_i(\langle w,x_i\rangle-b) = 1 - \xi_i < 1 khi \displaystyle \xi_i > 0. Lưu ý là các véctơ này có thể bị phân lớp sai nếu \displaystyle \xi_i \geq 1
  2. Có nhiều cách để mềm hóa ràng buộc, thay vì dùng hoảng cách Euclid \displaystyle C\left(\sum_{i=1}^N \xi_i\right)^2 ta có thể dùng khoảng cách \displaystyle L_1 và thêm vào hàm mục tiêu đại lượng \displaystyle C\sum_{i=1}^N \xi_i. Nói chung, ta có thể thêm vào hàm mục tiêu một lượng bằng

    \displaystyle C F\left(\sum_{i=1}^N \xi_i^\sigma\right)

    trong đó \displaystyle F là một hàm lồi đơn điệu tăng, còn \displaystyle \sigma\geq 1.

  3. Khi thêm đại lượng \displaystyle C\sum_{i=1}^N \xi_i vào hàm mục tiêu, bài toán tối ưu hóa chuyển thành

    \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\sum_{i=1}^N \lambda_i y_i = 0\\ 0\leq\lambda_i\leq C

    Đây có lẽ là cách sử dụng SVM thông dụng nhất. Tại nghiệm tối ưu \displaystyle \lambda, một mẫu học là véctơ hỗ trợ khi và chỉ khi

    \displaystyle 0< \lambda_i \leq C

  4. Tại sao người ta lại muốn giải bài toán tối ưu ở dạng đối ngẫu? Lý do là
    • Các ràng buộc tuyến tính ở bài toán gốc khá phức tạp, trong khi đó, ràng buộc ở bài toán đối ngẫu lại ở dạng hộp \displaystyle 0\leq\lambda_i\leq C.
    • Các thuật toán tối ưu có thể tận dụng sự đơn giản của ràng buộc dạng hộp để đơn giản hóa và tăng tốc độ quá trình tối ưu hóa.
    • Khi đã biết \displaystyle \lambda_i,i=1,\ldots,N có thể dễ dàng tinh \displaystyle w,b,\xi như sau:

      \displaystyle w = \sum_{i=1}^N \lambda_i y_i x_i

      Để tính \displaystyle b, chọn một \displaystyle i nào đó để \displaystyle 0<\lambda_i < C suy ra

      \displaystyle \gamma_i > 0 \Rightarrow \xi_i = 0
      \displaystyle y_i(\langle w,x_i\rangle-b)=1-\xi_i = 1\Rightarrow b = \langle w,x_i\rangle - y_i

      Để tính \displaystyle \xi, ta có

      \displaystyle \lambda_i < C \Rightarrow \gamma_i > 0 \Rightarrow \xi_i = 0
      \displaystyle \lambda_i = C \Rightarrow y_i(\langle w,x_i\rangle-b)=1-\xi_i \Rightarrow \xi_i = 1- y_i(\langle w,x_i\rangle-b).

  5. Để ý là tích vô hướng \displaystyle \langle w,x\rangle có thể thay bằng

    \displaystyle \langle w,x\rangle=\sum_{i=1}^N \lambda_i y_i \langle x_i,x\rangle

    Nghĩa là ta không cần phải tính véctơ \displaystyle w mà chỉ cần ngầm hiểu ta có tính tích vô hướng \displaystyle \langle w,x\rangle với mọi vectơ \displaystyle x. Lưu ý, ở biểu thức trên ta chỉ cần tính với các \displaystyle \lambda_i>0, tức là chỉ cần tính toán với các véctơ hỗ trợ mà thôi.

3 phản hồi to “Máy phân lớp sử dụng véctơ hỗ trợ (Support Vector Machines) (2) – Trường hợp không phân tách tuyến tính được”

  1. Học said

    Mong tác giả nói thêm về ý nghĩa của việc thêm đại lượng C và cờ-si.

    Tôi có nghe về việc khi không phân chia tuyến tính được thì bằng cách tăng số chiều của vector để đưa về bài toán chia lề tuyến tính, tuy nhiên chưa hiểu cụ thể về vấn đề này.
    Nếu có thể mong tác giả chỉ giúp.

    Xin cảm ơn!

  2. Học said

    Tôi có một phân vân là với tập dữ liệu huấn luyện (Positive examples và Negative Examples) làm sao mình biết được là không thể phân tách tuyến tính?

    Rất mong tác giả chỉ giúp.

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: