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) (3) – Cận trên của xác suất lỗi

Posted by Trần Quốc Long 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ênrelaxation).

Để ý 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\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-10-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.

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: