Contents
Tổng quan
Support Vector Machine (SVM) là một trong những thuật toán mạnh mẽ và phổ biến nhất trong Machine Learning. Ý tưởng chính của SVM là xây dựng một bộ phân lớp với mục tiêu tối đa hoặc tối thiểu khoảng cách từ mỗi điểm dữ liệu tới siêu phẳng phân chia. Tuy nhiên, để hiểu rõ hơn về phương pháp tối ưu cho SVM, ta cần nắm vững kiến thức về hình học, tối ưu lồi, hàm đối ngẫu Lagrange và giải bài toán tối ưu ràng buộc tuyến tính. Trong bài viết này, tôi sẽ giới thiệu về thuật toán SVM để phân loại một bộ dữ liệu tuyến tính và giải thích phương pháp tối ưu cho SVM.
READ MORE:
Nhắc lại về Logistic Regression:
Có thể có một câu hỏi là tại sao chúng ta lại sử dụng Logistic Regression thay vì một thuật toán phân lớp nào khác? Câu trả lời là vì ý tưởng của Logistic Regression có nhiều điểm chung với SVM. Logistic Regression xây dựng một phân bố xác suất cho mỗi lớp. Với một tập dữ liệu S={x(i),y(i)},i=1…m trong đó x(i)∈ℜn+1,x0(i)=1 và y(i)∈{0,1}, ta có xác suất để một điểm thuộc class 1 là p(y(i)=1∣x(i),θ)=σ(θTx(i)) với σ(z)=11+e−z∈(0,1). Điều kiện để quyết định liệu một điểm dữ liệu thuộc class 1 hay class 0 là p(y(i)=1∣x(i),θ)≥0.5. Tương tự như Logistic Regression, SVM cũng tìm kiếm một đường phân tách sao cho các điểm thuộc cùng một lớp sẽ nằm về cùng một phía và khoảng cách từ điểm gần nhất đến đường phân tách đó là lớn nhất có thể. Do đó, SVM có thể được coi là một phiên bản phức tạp hơn của Logistic Regression.
Bạn đang xem: Support Vector Machine
Khoảng cách từ một điểm tới một siêu phẳng
Xem thêm : Bộ đề thi ứng dụng cntt cơ bản lý thuyết và thực hành đầy đủ nhất 2023
Khoảng cách từ một điểm đến một siêu phẳng được định nghĩa như sau: d(A,(P))=∣a×x0+b×y0+c×z0+d∣a2+b2+c2. Trong SVM, chúng ta muốn các điểm thuộc lớp 1 (y(i)=1) nằm về phía dương của siêu phẳng và các điểm thuộc lớp -1 (y(i)=-1) nằm về phía âm của siêu phẳng. Mục tiêu của SVM là tìm một siêu phẳng sao cho khoảng cách từ các điểm gần nhất của mỗi lớp tới siêu phẳng đó là lớn nhất có thể.
Margin
Margin trong SVM là khoảng cách từ điểm gần nhất (support vector) tới siêu phẳng phân chia. Margin càng lớn thì khả năng phân lớp của SVM càng tốt. Đối với dữ liệu tuyến tính, Margin cực đại sẽ đạt được bằng cách tối ưu bài toán tối ưu cho SVM.
Bài toán tối ưu Margin
Bài toán tối ưu Margin có dạng sau:
minw,b12∥w∥22
s.t: y(i)(wTx(i)+b)≥1, i=1….m
Trong đó w và b là các biến tối ưu, m là số lượng điểm dữ liệu, y(i) là nhãn của điểm dữ liệu x(i) (y(i) = 1 or -1). Bài toán này có thể được giải bằng phương pháp tối ưu lồi (Convex Optimization).
Lagrange duality
Xem thêm : Không trồng 4 loại cây này trước cửa nhà, kẻo vận xui ập đến, của cải tiêu tan
Để giải bài toán tối ưu, chúng ta có thể sử dụng phương pháp nhân tử Lagrange để biến đổi bài toán ban đầu thành bài toán đối ngẫu. Đối ngẫu có những tính chất đẹp và ứng dụng rộng. Sử dụng phương pháp đối ngẫu, chúng ta có thể giải bài toán tối ưu cho SVM dễ dàng hơn. Tiêu chuẩn KKT là một trong các tiêu chuẩn quan trọng phải thỏa mãn để nghiệm của bài toán đối ngẫu cũng là nghiệm của bài toán ban đầu.
Giải bài toán tối ưu cho SVM
Bằng cách giải bài toán đối ngẫu, ta có thể tìm ra các hệ số αi (i=1…m) cho bài toán SVM. Sử dụng các hệ số αi này, ta có thể tính được vector w của siêu phẳng phân chia. Để phân loại một điểm dữ liệu mới, ta chỉ cần tính wTx+b, nếu kết quả là dương thì điểm dữ liệu thuộc lớp 1, ngược lại kết quả là âm thì điểm dữ liệu thuộc lớp -1. Từ các hệ số αi và các điểm dữ liệu huấn luyện, ta cũng có thể xác định giá trị b của siêu phẳng phân chia. Phần quan trọng của SVM nằm ở việc tính toán và lựa chọn support vectors, các điểm có ảnh hưởng lớn đến việc phân lớp và tính toán. Các hệ số αi của các support vectors là những giá trị khác 0.
READ MORE:
Kết luận
SVM là một thuật toán phân loại mạnh mẽ và hiệu quả cho các bài toán phân loại tuyến tính. Nó có thể được áp dụng cho các bài toán có dữ liệu tuyến tính, hoặc thông qua việc sử dụng Kernel Method, cũng có thể xử lý được các bài toán có dữ liệu không tuyến tính. SVM đã được chứng minh hiệu quả trong nhiều ứng dụng thực tế và là một công cụ hữu ích cho các nhà nghiên cứu và chuyên gia Machine Learning.
Nguồn: https://ispacedanang.edu.vn
Danh mục: Học tập
