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

Learn & Enjoy …

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)

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

\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ợ.

5 phản hồi to “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)”

  1. thtu said

    Chào anh.
    Em có đọc qua một số tài liệu về phương pháp phân loại dữ liệu SVM nhưng em vẫn chưa rõ tham số C được đưa vào nhằm mục đích gì và có tiêu chuẩn gì để chọn nó không khi xây dựng chương trình trên máy tính ?
    Cám ơn.

  2. tqlong said

    Tùy từng bài toán có một số C tối ưu. C điều chỉnh mối quan hệ giữa lề (margin) và số lỗi. Thường chọn C bằng phương pháp cross-validation.

  3. Học said

    Chào Anh,
    Anh có thể nói thêm về phương pháp chọn C được không?

    • tqlong said

      Chọn C bằng kỹ thuật cross-validation, chia tập mẫu ra 1 phần train, 1 phần test. Thử luyện bằng các giá trị C khác nhau trên tập train, rồi thử xem có đạt kết quả tốt hơn trên tập test hay không.

  4. Học said

    Cảm ơn anh rất nhiều!
    Như thế nghĩa là phải chọn thủ công (theo kinh nghiệm) và đánh giá chéo.

    Mong nói thêm về ý nghĩa của việc thêm đại lượng C và cờ-si khi xử lý soft-margin.

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: