Support vector machine (SVM) dùng để xây dựng một siêu mặt phẳng (hyperplane) để phân lớp (classify) tập dữ liệu thành hai lớp riêng biệt. Một siêu mặt phẳng là một hàm tương tự như phương trình đường thẳng y = ax + b. Trong thực tế, nếu ta chỉ cần phân lớp tập dữ liệu gồm hai feature siêu phẳng lúc này chính là một đường thẳng.
Về ý tưởng ban đầu thì SVM sử dụng thuật toán để ánh xạ dữ liệu ban đầu vào không gian nhiều chiều hơn. Khi ánh xạ tập dữ liệu sang nhiều chiều không gian từ đó SVM sẽ xem xét và chọn ra một siêu mặt phẳng phù hợp nhất để phân chia dữ liệu đó.
Các bài viết liên quan:
Trong không gian hai chiều, ta biết rằng khoảng cách từ một điểm có tọa độ (x0, y0) tới một đường thẳng có phương trình w1x + w2y + b = 0 được xác định bởi công thức.
Hình 3-2. Công thức tính khoảng cách từ một điểm đến đường thẳng
Trong không gian ba chiều, khoảng cách từ một điểm có tọa độ (x0, y0, z0) tới một mặt phẳng có phương trình w1x + w2y + w3z + b = 0 được xác định bởi công thức
Hình 3-3. Công thức tính khoảng cách từ một điểm đến mặt phẳng
Nếu ta bỏ dấu giá trị tuyệt đối ở tử số, chúng ta có thể xác định điểm đó nằm về phía nào của đường thẳng hay mặt phẳng đang xét. Những điểm làm cho biểu thức trong dấu giá trị tuyệt đối mang dấu dương nằm về cùng một phía (gọi tạm đây là phía dương), những điểm làm cho biểu thức trong dấu giá trị tuyệt đối mang giá trị âm nằm về phía còn lại (gọi là phía âm). Những điểm nằm trên đường thẳng hoặc mặt phẳng sẽ làm cho tử số có giá trị bằng 0, tức khoảng cách từ điểm đang xét đến đường thẳng hoặc mặt phẳng bằng 0.
Xem thêm Kiểm tra lỗ hổng bảo mật HTTP Incoming Requests
Từ đây chúng ta có thể tổng quát lên không gian nhiều chiều. Khoảng cách từ một điểm (vector) có tọa độ x0 đến một siêu mặt phẳng có phương trình wTx + b = 0 được xác định bởi công thức.
Hình 3-4. Công thức tính khoảng cách từ một điểm đến siêu mặt phẳng
với d là số chiều không gian. Giả sử chúng ta có hai lớp khác nhau được mô tả bởi các điểm trong không gian nhiều chiều, bây giờ chúng ta cần tìm một mặt phẳng phân chia chính xác hai classes đó. Tức là tất cả các điểm thuộc một lớp sẽ nằm về cùng một phía của siêu mặt phẳng đó và ngược phía với toàn bộ các điểm thuộc class còn lại. Ta hãy xem xét hình dưới đây
Hình 3-5. Các mặt phân chia hai lớp
Xem thêm Training model & testing SVM trong R
Trong các mặt phẳng đó đâu là mặt phẳng được phân chia tốt nhất, trong hình 3.5 ta thấy có hai mặt phẳng lệch về phía lớp có các điểm màu đỏ. Điều này sẽ gây ra việc lớp có các điểm màu đỏ sẽ cảm thấy bị hạn chế các điểm dữ liệu trên không gian so với lớp có các điểm màu xanh.
Hình 3-6. Phân chia các lớp
Nếu ta định nghĩa mức độ hạnh phúc của một lớp tỉ lệ thuận với khoảng cách gần nhất từ một điểm của lớp đó đến đường thẳng hoặc mặt phẳng thì lớp màu đỏ ở phía bên trái hình 3.6 sẽ không được hạnh phúc cho lắm vì khoảng cách từ điểm gần nhất của mỗi lớp đến đường hoặc mặt phẳng phân chia thì không đồng đều.
Vì vậy chúng ta cần tìm một đường hoặc mặt phẳng phân chia làm sao cho các điểm (vector) của hai lớp đến mặt phẳng là đồng đều. Tức là khoảng các điểm (vector) của lớp màu đỏ và lớp màu xanh gần nhất với đường thẳng hoặc mặt phẳng và cách đều các điểm (vector). Khoảng cách này được gọi mà margin.
Chúng ta nhìn khung bên phải hình 3.6 xét hai cách phân chia bởi đường nét liền màu đen và đường nét đứt màu xanh, rõ ràng ta thấy đường nét liền phân chia tốt hơn vì nó tạo ra margin rộng hơn đường nét màu xanh.
Việc margin rộng hơn sẽ mang lại hiệu ứng phân lớp tốt hơn vì việc phân chia giữa các lớp là rạch ròi hơn. Bài toán tối ưu trong SVM chính là bài toán đi tìm đường phân chia sao cho margin lớn nhất.
Xem thêm 2021 và 21 Trang Web Bạn Nên Chia sẻ Nội dung của mình
Giả sử ta có các cặp dữ liệu training set là (x1, y1), (x2, y2),…(xN, yN), với , và yi là nhãn của dữ liệu đó, d là số chiều của dữ liệu, N là số điểm dữ liệu, mỗi điểm dữ liệu được xác định bởi yi = 1 (lớp 1) và yi = -1 (lớp 2). Để dễ hình dung ta nhìn hình phía dưới đây.
Hình 3-7. Phân chia hai lớp
Các điểm (vector) ô vuông xanh thuộc lớp 1, các điểm tròn đỏ thuộc lớp 2 và mặt phân chia hai lớp ta có là là mặt phẳng phân chia giữa hai lớp, lớp 1 nằm về phía dương và lớp 2 nằm về phía âm của mặt phân chia. Ta quan sát thấy một điểm quan trọng như sau với cặp dữ liệu (xn, yn) bất kỳ, khoảng cách từ điểm đó tới mặt phân chia là
Hình 3-8. Công thức tính khoảng cách tổng quát
Ta có thể thấy nó gần giống công thức tính khoảng cách ở hình 3.8, thật chắc chúng như nhau. Khi ta định nghĩa lớp 1 là phía dương thì ta có ngược lại ta có lớp 2 định nghĩa là phía âm nên có do đó suy ra công thức chung đối với tất cả các điểm (vector) là . Từ đó ta suy ra công thức đối với hình 3.9, ta nhìn hình dưới đây sẽ dễ hiểu hơn.
Hình 3-9. Mặt phẳng phân chia lớp
Đối với mỗi điểm dữ liệu ta có từ đó ta có thể tính được margin bằng cách tính khoảng cách gần nhất từ một điểm đến mặt phẳng phân chia . Bài toán SVM chính là bài toán tìm w và b sao cho margin này đạt giá trị lớn nhất.
Xem thêm Clustering- phân cụm trong R
