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

Learn & Enjoy …

Archive for Tháng tám, 2008

« Những bài viết trước

Máy phân lớp sử dụng vectơ hỗ trợ (Support Vector Machines) (4) – Thuật toán tối thiểu tuần tự (Sequential Minimal Optimization)

Đăng bởi tqlong on Tháng tám 10, 2008

Ta biết rằng bài toán tối ưu tìm siêu phẳng có lề “mềm” lớn nhất là

\displaystyle \min_{w,b,\xi}~\frac{1}{2}\|w\|^2+C\sum_{i=1}^N\xi_i 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

với bài toán đối ngẫu Lagrange:

\displaystyle \max_{\lambda} \lambda^T 1_N-\frac{1}{2}\lambda^TK\lambda với các ràng buộc \displaystyle\sum_{i=1}^N\lambda_i y_i = 0\\ 0\leq\lambda_i\leq C,

trong đó \displaystyle K = [y_iy_j \langle x_i,x_j\rangle ]_{i,j=1}^N\in \mathbb{R}^{N\times N}.

Cả hai bài toán gốc và đối ngẫu đều là bài toán tối ưu bậc 2 (Quadratic Programming). Cả 2 bài toán đều có thể giải bằng phương pháp điểm trong (interior-point methods). Trong đó, bài toán đối ngẫu có các ràng buộc đơn giản dạng hộp nên dễ cài đặt hơn. Tuy nhiên, khi số lượng mẫu học \displaystyle N lớn, ma trận \displaystyle K cũng lớn theo bậc 2 của \displaystyle N. Vì vậy, ngay cả các phương pháp điểm trong cũng có thời gian chạy rất lâu (cỡ \displaystyle N^3). May mắn là trong trường hợp của SVM, ta có những phương pháp chuyên biệt, lợi dụng được cấu trúc của riêng bài toán tối ưu này để tăng tốc độ tối ưu hóa.

Thuật toán tối thiểu tuần tự (Sequential Minimal Optimization – SMO): Đây là thuật toán tối ưu dành riêng cho phương pháp SVM do J. Platt đưa ra vào năm 1998. Xem chi tiết bài báo của Platt ở đây. Ý tưởng chính của thuật toán này là:

  1. Thay vì khống chế tất cả các ràng buộc, ta cố định phần lớn các biến \displaystyle \lambda_i và chỉ tối ưu hóa một cặp \displaystyle (\lambda_i,\lambda_j) nào đó.
  2. Giá trị tối ưu của cặp \displaystyle (\lambda_i,\lambda_j) có thể viết dưới dạng công thức (của dữ liệu và các biến \displaystyle \lambda_i khác) chứ không cần chạy một thuật toán tối ưu nào cả.
  3. Lần lượt chọn các cặp \displaystyle (\lambda_i,\lambda_j) theo một tiêu chí (heuristics) nào đó để thuật toán nhanh chóng hội tụ về nghiệm tối ưu.

Cho đến nay, các ý tưởng của thuật toán SMO vẫn là các ý tưởng chính khi thiết kế và cài đặt các thuật toán học máy sử dụng véctơ hỗ trợ.

Đăng trong Lý thuyết học máy | Tagged: , , , , , | 2 phản hồi »

Máy phân lớp sử dụng véctơ hỗ trợ (Support Vector Machines) (3) – Cận trên của xác suất lỗi

Đăng bởi tqlong on Tháng tám 3, 2008

Trong bài trước, ta đã tìm hiểu quá trình mềm hóa các ràng buộc của bài toán tìm siêu phẳng có lề lớn nhất. Ở một cách nhìn khác, việc đưa vào hàm mục tiêu các đại lượng \displaystyle \left(\sum_{i=1}^N \xi_i\right)^2 hoặc \displaystyle \sum_{i=1}^N \xi_i còn có một ý nghĩa khác. Các đại lượng này còn là cận trên của số mẫu học bị phân lớp nhầm. Như vậy, khi tối thiểu hóa hàm mục tiêu, cùng lúc ta tối thiểu hóa cận trên của số mẫu học bị phân lớp nhầm. Đây là một kĩ thuật tối ưu hóa rất hay được sử dụng khi hàm mục tiêu không liên tục (số lỗi phân lớp không liên tục), người ta tạo một cận trên của hàm mục tiêu và tối thiểu hóa cận trên này (còn gọi là kỹ thuật nới lỏng các ràng buộc nguyên – relaxation).

Để ý rằng, khi tìm được nghiệm tối ưu \displaystyle \lambda,\xi, theo điều kiện KKT, xảy ra những trường hợp sau:

  • \displaystyle \lambda_i = 0 hay \displaystyle x_i không là véctơ hỗ trợ. Khi đó \displaystyle \gamma_i = \delta - \lambda_i > 0, tức là \displaystyle \xi_i = 0 và \displaystyle y_i(\langle w,x_i\rangle-b)\geq 1, mẫu học \displaystyle x_i đã được phân lớp đúng.
  • \displaystyle \lambda_i > 0 suy ra \displaystyle y_i(\langle w,x_i\rangle-b)=1-\xi_i. Có 3 trường hợp con:
    • \displaystyle \xi_i = 0, suy ra \displaystyle y_i(\langle w,x_i\rangle-b)=1 hay mẫu học \displaystyle x_i vẫn được phân lớp đúng (nằm trên lề của siêu phẳng.
    • \displaystyle 0 < \xi_i < 1 , suy ra \displaystyle y_i(\langle w,x_i\rangle-b)=1-\xi_i > 0 hay mẫu học \displaystyle x_i vẫn được phân lớp đúng (mặc dù nằm ở bên trong lề).
    • \displaystyle \xi_i \geq 1, suy ra \displaystyle y_i(\langle w,x_i\rangle-b)=1-\xi_i \leq 0 và mẫu học bị phân lớp sai.

Tổng kết lại:

  • \displaystyle 0\leq \xi_i < 1: phân lớp đúng (không có lỗi).
  • \displaystyle \xi_i \geq 1: phân lớp sai (có lỗi).

Để ý là, tại mỗi mẫu học \displaystyle x_i, chỉ có thể có khả năng có \displaystyle 1  lỗi hoặc \displaystyle {0} lỗi (còn gọi là hàm lỗi 0-1 – 0-1 loss). Nói cách khác \displaystyle \xi_i là cận trên của số lỗi phân lớp tại mẫu học \displaystyle x_i. Vậy số lỗi trên toàn bộ tập mẫu học có cận trên là

\displaystyle N\{error\} \leq \sum_{i=1}^N \xi_i

Dễ thấy, nếu \displaystyle \sigma \geq 1 thì

\displaystyle N\{error\} \leq \sum_{i=1}^N \xi_i^\sigma

Cận trên của số lỗi

Đồng thời, do tối thiểu hóa \displaystyle \sum_{i=1}^N \xi_i^\sigma tương đương với việc tối thiểu hóa \displaystyle F\left(\sum_{i=1}^N \xi_i^\sigma\right) với \displaystyle F là hàm đơn điệu tăng, người ta có thể chọn một hàm \displaystyle F lồi và đơn điệu tăng bất kì để đưa vào hàm mục tiêu

\displaystyle \frac{1}{2}\|w\|^2 + C F\left(\sum_{i=1}^N \xi_i^\sigma\right)

Như vậy, bài toán quy hoạch với hàm mục tiêu trên vẫn là bài toán quy hoạch lồi với hàm mục tiêu lồi và các ràng buộc tuyến tính. Phương pháp SVM với lề mềm không những tìm siêu phẳng có lề lớn nhất mà còn hướng tới việc tối thiểu hóa xác suất lỗi trên tập mẫu học.

Đăng trong Lý thuyết học máy | Tagged: , , , , , , , , , , | Leave a Comment »

« Những bài viết trước