Máy vectơ hỗ trợ

Máy vectơ hỗ trợ (SVM - viết tắt tên tiếng Anh support vector machine) là một khái niệm trong thống kê và khoa học máy tính cho một tập hợp các phương pháp học có giám sát liên quan đến nhau để phân loại và phân tích hồi quy. SVM dạng chuẩn nhận dữ liệu vào và phân loại chúng vào hai lớp khác nhau. Do đó SVM là một thuật toán phân loại nhị phân. Với một bộ các ví dụ luyện tập thuộc hai thể loại cho trước, thuật toán luyện tập SVM xây dựng một mô hình SVM để phân loại các ví dụ khác vào hai thể loại đó. Một mô hình SVM là một cách biểu diễn các điểm trong không gian và lựa chọn ranh giới giữa hai thể loại sao cho khoảng cách từ các ví dụ luyện tập tới ranh giới là xa nhất có thể. Các ví dụ mới cũng được biểu diễn trong cùng một không gian và được thuật toán dự đoán thuộc một trong hai thể loại tùy vào ví dụ đó nằm ở phía nào của ranh giới.

Tổng quan về máy vectơ hỗ trợ

Một máy vectơ hỗ trợ xây dựng một siêu phẳng hoặc một tập hợp các siêu phẳng trong một không gian nhiều chiều hoặc vô hạn chiều, có thể được sử dụng cho phân loại, hồi quy, hoặc các nhiệm vụ khác. Một cách trực giác, để phân loại tốt nhất thì các siêu phẳng nằm ở càng xa các điểm dữ liệu của tất cả các lớp (gọi là hàm Biên) càng tốt, vì nói chung Biên càng lớn thì sai số tổng quát hóa của thuật toán phân loại càng bé.

Trong nhiều trường hợp, không thể phân chia các lớp dữ liệu một cách tuyến tính trong một không gian ban đầu được dùng để mô tả một vấn đề. Vì vậy, nhiều khi cần phải ánh xạ các điểm dữ liệu trong không gian ban đầu vào một không gian mới nhiều chiều hơn, để việc phân tách chúng trở nên dễ dàng hơn trong không gian mới. Để việc tính toán được hiệu quả, ánh xạ sử dụng trong thuật toán SVM chỉ đòi hỏi tích vô hướng của các vectơ dữ liệu trong không gian mới có thể được tính dễ dàng từ các tọa độ trong không gian cũ. Tích vô hướng này được xác định bằng một hàm hạt nhân K(x,y) phù hợp. Một siêu phẳng trong không gian mới được định nghĩa là tập hợp các điểm có tích vô hướng với một vectơ cố định trong không gian đó là một hằng số. Vectơ xác định một siêu phẳng sử dụng trong SVM là một tổ hợp tuyến tính của các vectơ dữ liệu luyện tập trong không gian mới với các hệ số α_i. Với siêu phẳng lựa chọn như trên, các điểm x trong không gian đặc trưng được ánh xạ vào một siêu mặt phẳng là các điểm thỏa mãn:

Σ_i α_i K(x_i,x) = hằng số.

Ghi chú rằng nếu K(x,y) nhận giá trị ngày càng nhỏ khi y xa dần khỏi x thì mỗi số hạng của tổng trên được dùng để đo độ tương tự giữa x với điểm x_i tương ứng trong dữ liệu luyện tập. Như vậy, tác dụng của tổng trên chính là so sánh khoảng cách giữa điểm cần dự đoán với các điểm dữ liệu đã biết. Lưu ý là tập hợp các điểm x được ánh xạ vào một siêu phẳng có thể có độ phức tạp tùy ý trong không gian ban đầu, nên có thể phân tách các tập hợp thậm chí không lồi trong không gian ban đầu.

Lịch sử

Thuật toán SVM ban đầu được tìm ra bởi Vladimir N. Vapnik và dạng chuẩn hiện nay sử dụng Biên mềm được tìm ra bởi Vapnik và Corinna Cortes năm 1995.

Đặt vấn đề

H3 (màu xanh lá cây) không chia tách hai lớp dữ liệu. H1 (màu xanh lơ) phân tách hai lớp với Biên nhỏ và H2 (màu đỏ) phân tách với Biên cực đại.

Phân loại thống kê là một nhiệm vụ phổ biến trong học máy. Trong mô hình học có giám sát, thuật toán được cho trước một số điểm dữ liệu cùng với nhãn của chúng thuộc một trong hai lớp cho trước. Mục tiêu của thuật toán là xác định xem một điểm dữ liệu mới sẽ được thuộc về lớp nào. Mỗi điểm dữ liệu được biểu diễn dưới dạng một vector p-chiều, và ta muốn biết liệu có thể chia tách hai lớp dữ liệu bằng một siêu phẳng p − 1 chiều. Đây gọi là phân loại tuyến tính. Có nhiều siêu phẳng có thể phân loại được dữ liệu. Một lựa chọn hợp lý trong chúng là siêu phẳng có Biên lớn nhất giữa hai lớp.

SVM tuyến tính

Ta có một tập huấn luyện ${\mathcal {D}}$ gồm n điểm có dạng

${\mathcal {D}}=\left\{(\mathbf {x} _{i},y_{i})\mid \mathbf {x} _{i}\in \mathbb {R} ^{p},\,y_{i}\in \{-1,1\}\right\}_{i=1}^{n}$

với y_i mang giá trị 1 hoặc −1, xác định lớp của điểm $\mathbf {x} _{i}$. Mỗi $\mathbf {x} _{i}$ là một vectơ thực p-chiều. Ta cần tìm siêu phẳng có Biên lớn nhất chia tách các điểm có $y_{i}=1$ và các điểm có $y_{i}=-1$. Mỗi siêu phẳng đều có thể được viết dưới dạng một tập hợp các điểm $\mathbf {x}$ thỏa mãn

Siêu phẳng với Biên cực đại cho một SVM phân tách dữ liệu thuộc hai lớp. Các ví dụ nằm trên Biên được gọi là các vectơ hỗ trợ.

$\mathbf {w} \cdot \mathbf {x} -b=0,\,$

với $\cdot$ ký hiệu cho tích vô hướng và ${\mathbf {w} }$ là một vectơ pháp tuyến của siêu phẳng. Tham số ${\tfrac {b}{\|\mathbf {w} \|}}$ xác định khoảng cách giữa gốc tọa độ và siêu phẳng theo hướng vectơ pháp tuyến ${\mathbf {w} }$.

Chúng ta cần chọn ${\mathbf {w} }$ và $b$ để cực đại hóa Biên, hay khoảng cách giữa hai siêu mặt song song ở xa nhau nhất có thể trong khi vẫn phân chia được dữ liệu. Các siêu mặt ấy được xác định bằng

$\mathbf {w} \cdot \mathbf {x} -b=1\,$

và

$\mathbf {w} \cdot \mathbf {x} -b=-1.\,$

Để ý rằng nếu dữ liệu huấn luyện có thể được chia tách một cách tuyến tính, thì ta có thể chọn hai siêu phẳng của Biên sao cho không có điểm nào ở giữa chúng và sau đó tăng khoảng cách giữa chúng đến tối đa có thể. Bằng hình học, ta tìm được khoảng cách giữa hai siêu phẳng là ${\tfrac {2}{\|\mathbf {w} \|}}$. Vì vậy ta muốn cực tiểu hóa giá trị $\|\mathbf {w} \|$. Để đảm bảo không có điểm dữ liệu nào trong Biên, ta thêm vào các điều kiện sau:

Với mỗi $i$ ta có

$\mathbf {w} \cdot \mathbf {x} _{i}-b\geq 1\qquad {\text{ cho }}\mathbf {x} _{i}$ thuộc lớp thứ nhất

hoặc

$\mathbf {w} \cdot \mathbf {x} _{i}-b\leq -1\qquad {\text{ cho }}\mathbf {x} _{i}$ thuộc lớp thứ hai

Có thể viết gọn lại như sau với mọi $1\leq i\leq n$:

$y_{i}(\mathbf {w} \cdot \mathbf {x} _{i}-b)\geq 1,\qquad \qquad (1)$

Tóm lại, ta có bài toán tối ưu hóa sau:

Cực tiểu hóa (theo ${\mathbf {w} ,b}$)

$\|\mathbf {w} \|$

với điều kiện (với mọi $i=1,\dots ,n$)

$y_{i}(\mathbf {w} \cdot \mathbf {x_{i}} -b)\geq 1.\,$

Dạng ban đầu

Bài toán tối ưu ở mục trên tương đối khó giải vì hàm mục tiêu phụ thuộc vào ||w||, là một hàm có khai căn. Tuy nhiên có thể thay ||w|| bằng hàm mục tiêu ${\tfrac {1}{2}}\|\mathbf {w} \|^{2}$ (hệ số 1/2 để tiện cho các biến đổi toán học sau này) mà không làm thay đổi lời giải (lời giải của bài toán mới và bài toán ban đầu có cùng w và b). Đây là một bài toán quy hoạch toàn phương. Cụ thể hơn:

Cực tiểu hóa (theo ${\mathbf {w} ,b}$)

${\frac {1}{2}}\|\mathbf {w} \|^{2}$

với điều kiện (với mọi $i=1,\dots ,n$)

$y_{i}(\mathbf {w} \cdot \mathbf {x_{i}} -b)\geq 1.$

Bằng cách thêm các nhân tử Lagrange ${\boldsymbol {\alpha }}$, bài toán trên trở thành

$\min _{\mathbf {w} ,b}\max _{{\boldsymbol {\alpha }}\geq 0}\left\{{\frac {1}{2}}\|\mathbf {w} \|^{2}-\sum _{i=1}^{n}{\alpha _{i}[y_{i}(\mathbf {w} \cdot \mathbf {x_{i}} -b)-1]}\right\}$

nghĩa là ta cần tìm một điểm yên ngựa. Khi đó, tất cả các điểm không nằm trên Biên, nghĩa là $y_{i}(\mathbf {w} \cdot \mathbf {x_{i}} -b)-1>0$ đều không ảnh hưởng đến giá trị hàm mục tiêu vì ta có thể chọn $\alpha _{i}$ bằng không.

Có thể giải bài toán này bằng các kĩ thuật thông thường cho quy hoạch toàn phương. Theo điều kiện Karush–Kuhn–Tucker, lời giải có thể được viết dưới dạng tổ hợp tuyến tính của các vectơ luyện tập

$\mathbf {w} =\sum _{i=1}^{n}{\alpha _{i}y_{i}\mathbf {x_{i}} }.$

Chỉ có một vài $\alpha _{i}$ nhận giá trị lớn hơn 0. Các điểm $\mathbf {x_{i}}$ tương ứng là các vectơ hỗ trợ nằm trên Biên và thỏa mãn $y_{i}(\mathbf {w} \cdot \mathbf {x_{i}} -b)=1$. Từ điều kiện này, ta nhận thấy

$\mathbf {w} \cdot \mathbf {x_{i}} -b=1/y_{i}=y_{i}\iff b=\mathbf {w} \cdot \mathbf {x_{i}} -y_{i}$

từ đó ta suy ra được giá trị $b$. Trên thực tế, một cách thức tốt hơn để tính $b$ là tính giá trị trung bình từ tất cả $N_{SV}$ vectơ hỗ trợ:

$b={\frac {1}{N_{SV}}}\sum _{i=1}^{N_{SV}}{(\mathbf {w} \cdot \mathbf {x_{i}} -y_{i})}$

Dạng đối ngẫu

Nếu viết điều kiện phân loại dưới dạng đối ngẫu không điều kiện thì sẽ dễ dàng nhận thấy siêu phẳng với Biên lớn nhất, và do đó nhiệm vụ phân loại, chỉ phụ thuộc vào các điểm luyện tập nằm trên Biên, còn gọi là các vectơ hỗ trợ.

Vì $\|\mathbf {w} \|^{2}=w\cdot w$ và $\mathbf {w} =\sum _{i=1}^{n}{\alpha _{i}y_{i}\mathbf {x_{i}} }$, ta nhận thấy bài toán đối ngẫu của SVM là chính là bài toán tối ưu hóa sau:

Cực đại hóa (theo $\alpha _{i}$)

${\tilde {L}}(\mathbf {\alpha } )=\sum _{i=1}^{n}\alpha _{i}-{\frac {1}{2}}\sum _{i,j}\alpha _{i}\alpha _{j}y_{i}y_{j}\mathbf {x} _{i}^{T}\mathbf {x} _{j}=\sum _{i=1}^{n}\alpha _{i}-{\frac {1}{2}}\sum _{i,j}\alpha _{i}\alpha _{j}y_{i}y_{j}k(\mathbf {x} _{i},\mathbf {x} _{j})$

với điều kiện (với mọi $i=1,\dots ,n$)

$\alpha _{i}\geq 0,\,$

và điều kiện sau ứng với việc cực tiểu hóa theo $b$

$\sum _{i=1}^{n}\alpha _{i}y_{i}=0.$

Ở đây hàm hạt nhân được định nghĩa là $k(\mathbf {x} _{i},\mathbf {x} _{j})=\mathbf {x} _{i}\cdot \mathbf {x} _{j}$.

Sau khi giải xong, có thể tính $\mathbf {w}$ từ các giá trị $\alpha$ tìm được như sau:

$\mathbf {w} =\sum _{i}\alpha _{i}y_{i}\mathbf {x} _{i}.$

Biên mềm

Năm 1995, Corinna Cortes và Vladimir N. Vapnik đề xuất một ý tưởng mới cho phép thuật toán gán nhãn sai cho một số ví dụ luyện tập. Nếu không tồn tại siêu phẳng nào phân tách được hai lớp dữ liệu, thì thuật toán Biên mềm sẽ chọn một siêu phẳng phân tách các ví dụ luyện tập tốt nhất có thể, và đồng thời cực đại hóa khoảng cách giữa siêu phẳng với các ví dụ được gán đúng nhãn. Phương pháp này sử dụng các biến bù $\xi _{i}$, dùng để đo độ sai lệch của ví dụ $x_{i}$

$y_{i}(\mathbf {w} \cdot \mathbf {x_{i}} -b)\geq 1-\xi _{i}\quad 1\leq i\leq n.\quad \quad (2)$

Hàm mục tiêu có thêm một số hạng mới để phạt thuật toán khi $\xi _{i}$ khác không, và bài toán tối ưu hóa trở thành việc trao đổi giữa Biên lớn và mức phạt nhỏ. Nếu hàm phạt là tuyến tính thì bài toán trở thành:

$\min _{\mathbf {w} ,\mathbf {\xi } ,b}\left\{{\frac {1}{2}}\|\mathbf {w} \|^{2}+C\sum _{i=1}^{n}\xi _{i}\right\}$

với điều kiện (với mọi $i=1,\dots n$)

$y_{i}(\mathbf {w} \cdot \mathbf {x_{i}} -b)\geq 1-\xi _{i},~~~~\xi _{i}\geq 0$

Có thể giải bài toán trên bằng nhân tử Lagrange tương tự như trường hợp cơ bản ở trên. Bài toán cần giải trở thành:

$\min _{\mathbf {w} ,\mathbf {\xi } ,b}\max _{{\boldsymbol {\alpha }},{\boldsymbol {\beta }}}\left\{{\frac {1}{2}}\|\mathbf {w} \|^{2}+C\sum _{i=1}^{n}\xi _{i}-\sum _{i=1}^{n}{\alpha _{i}[y_{i}(\mathbf {w} \cdot \mathbf {x_{i}} -b)-1+\xi _{i}]}-\sum _{i=1}^{n}\beta _{i}\xi _{i}\right\}$

với $\alpha _{i},\beta _{i}\geq 0$.

Dạng đối ngẫu

Cực đại hóa (theo $\alpha _{i}$)

${\tilde {L}}(\mathbf {\alpha } )=\sum _{i=1}^{n}\alpha _{i}-{\frac {1}{2}}\sum _{i,j}\alpha _{i}\alpha _{j}y_{i}y_{j}k(\mathbf {x} _{i},\mathbf {x} _{j})$

với điều kiện (với mọi $i=1,\dots ,n$)

$0\leq \alpha _{i}\leq C,\,$

và

$\sum _{i=1}^{n}\alpha _{i}y_{i}=0.$

Ưu điểm của việc dùng hàm phạt tuyến tính là các biến bù biến mất khỏi bài toán đối ngẫu, và hằng số C chỉ xuất hiện dưới dạng một chặn trên cho các nhân tử Lagrange. Cách đặt vấn đề trên đã mang lại nhiều thành quả trong thực tiễn, và Cortes và Vapnik đã nhận được giải Paris Kanellakis của ACM năm 2008 cho đóng góp này. Các hàm phạt phi tuyến cũng được sử dụng, đặc biệt là để giảm ảnh hưởng của các trường hợp ngoại lệ, tuy nhiên nếu không lựa chọn hàm phạt cẩn thận thì bài toán trở thành không lồi, và việc tìm lời giải tối ưu toàn cục thường là rất khó.

Xem thêm

• In situ adaptive tabulation
• Máy hạt nhân
• Predictive analytics
• Relevance vector machine, Một mô hình máy hạt nhân thưa xác suất có dạnghàm số giống như SVM.
• Tối ưu hóa nhỏ nhất tuần tự

Liên kết ngoài

• Burges, Christopher J.C. (1998), “A Tutorial on Support Vector Machines for Pattern Recognition” (PDF), Data Mining and Knowledge Discovery, 2: 121–167 * www.kernel-machines.org (thông tin tổng quan và danh sách các bài báo nghiên cứu)
• www.support-vector-machines.org (Bài báo nghiên cứu, đánh giá,, phần mềm, liên kết có liên quan đến máy vectơ hỗ trợ)
• videolectures.net (Video bài giảng về SVM)
• Phim ngắn: Minh họa SVM sử dụng hàm hạt nhân đa thức.
• Một hướng dẫn sử dụng SVM cho người mới học bởi Tristan Fletcher [1] Lưu trữ 2011-10-05 tại Wayback Machine.
• www.shogun-toolbox.org Lưu trữ 2011-02-22 tại Wayback Machine (Shogun (hộp công cụ) gồm khoảng 20 thư viện lập trình SVM)
• libsvm libsvm là một thư viện lập trình SVM
• liblinear liblinear là một thư viện lập trình gồm nhiều thuật toán phân loại tuyến tính, trong đó có SVM
• flssvm Lưu trữ 2010-10-10 tại Wayback Machine flssvm là một thư viện lập trình svm bình phương nhỏ nhất viết bằng fortran
• Shark Lưu trữ 2010-02-27 tại Wayback Machine Shark là một thư viện học máy viết bằng C++ có chứa nhiều loại SVM
• dlib dlib là một thư viện C++ cho máy hạt nhân và SVM
• SVM light là một bộ phần mềm cho học máy và phân loại bằng SVM.

Tham khảo

• Sergios Theodoridis and Konstantinos Koutroumbas "Pattern Recognition", 4th Edition, Academic Press, 2009, ISBN 978-1-59749-272-0
• Nello Cristianini and John Shawe-Taylor. An Introduction to Support Vector Machines and other kernel-based learning methods. Cambridge University Press, 2000. ISBN 0-521-78019-5 ([2] Lưu trữ 2018-06-27 tại Wayback Machine SVM Book)
• Huang T.-M., Kecman V., Kopriva I. (2006), Kernel Based Algorithms for Mining Huge Data Sets, Supervised, Semi-supervised, and Unsupervised Learning, Springer-Verlag, Berlin, Heidelberg, 260 pp. 96 illus., Hardcover, ISBN 3-540-31681-7 [3]
• Vojislav Kecman: "Learning and Soft Computing — Support Vector Machines, Neural Networks, Fuzzy Logic Systems", The MIT Press, Cambridge, MA, 2001.[4]
• Bernhard Schölkopf and A. J. Smola: Learning with Kernels. MIT Press, Cambridge, MA, 2002. (Partly available on line: [5].) ISBN 0-262-19475-9
• Bernhard Schölkopf, Christopher J.C. Burges, and Alexander J. Smola (editors). "Advances in Kernel Methods: Support Vector Learning". MIT Press, Cambridge, MA, 1999. ISBN 0-262-19416-3. [6] Lưu trữ 2007-10-17 tại Wayback Machine
• John Shawe-Taylor and Nello Cristianini. Kernel Methods for Pattern Analysis. Cambridge University Press, 2004. ISBN 0-521-81397-2 ([7] Kernel Methods Book)
• Ingo Steinwart and Andreas Christmann. Support Vector Machines. Springer-Verlag, New York, 2008. ISBN 978-0-387-77241-7 ([8] Lưu trữ 2012-02-20 tại Wayback Machine SVM Book)
• P.J. Tan and D.L. Dowe (2004), MML Inference of Oblique Decision Trees, Lecture Notes in Artificial Intelligence (LNAI) 3339, Springer-Verlag, pp1082-1088. (This paper uses minimum message length (MML) and actually incorporates probabilistic support vector machines in the leaves of decision trees.)
• Vladimir Vapnik. The Nature of Statistical Learning Theory. Springer-Verlag, 1995. ISBN 0-387-98780-0
• Vladimir Vapnik, S.Kotz "Estimation of Dependences Based on Empirical Data" Springer, 2006. ISBN 0-387-30865-2, 510 pages [this is a reprint of Vapnik's early book describing philosophy behind SVM approach. The 2006 Appendix describes recent development].
• Dmitriy Fradkin and Ilya Muchnik "Support Vector Machines for Classification" in J. Abello and G. Carmode (Eds) "Discrete Methods in Epidemiology", DIMACS Series in Discrete Mathematics and Theoretical Computer Science, volume 70, pp. 13–20, 2006. [9] Lưu trữ 2016-10-19 tại Wayback Machine. Succinctly describes theoretical ideas behind SVM.
• Kristin P. Bennett and Colin Campbell, "Support Vector Machines: Hype or Hallelujah?", SIGKDD Explorations, 2,2, 2000, 1–13. [10]. Excellent introduction to SVMs with helpful figures.
• Ovidiu Ivanciuc, "Applications of Support Vector Machines in Chemistry", In: Reviews in Computational Chemistry, Volume 23, 2007, pp. 291–400. Reprint available: [11]
• Catanzaro, Sundaram, Keutzer, "Fast Support Vector Machine Training and Classification on Graphics Processors", In: International Conference on Machine Learning, 2008 [12] Lưu trữ 2012-03-02 tại Wayback Machine