Phân loại ảnh dùng SVM

Classification image USE Support Vector Machines

Phân lớp hình ảnh dùng BOW (USE Support Vector Machines (SVMs) train

Trình tự: Vector hóa hình ảnh => train => Phân lớp.

Dùng để làm gì? Support vector machine (SVM) xây dựng (learn) một siêu phẳng (hyperplane) để phân lớp (classify) tập dữ liệu thành 2 lớp riêng biệt.

Siêu phẳng là cái gì? Một siêu 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 cần phân lớp tập dữ liệu chỉ gồm 2 feature, siêu phẳng lúc này chính là một đường thẳng.

Về ý tưởng thì SVM sử dụng thủ thuật để ánh xạ tập dữ liệu ban đầu vào không gian nhiều chiều hơn. Khi đã ánh xạ sang không gian nhiều chiều, SVM sẽ xem xét và chọn ra siêu phẳng phù hợp nhất để phân lớp tập dữ liệu đó.

Có ví dụ đơn giản nào không? Ta lấy ví dụ đơn giản về phân chia tập các quả bóng xanh và đỏ đặt trên một cái bàn. Nếu các quả bóng phân bố không quá đan xen vào nhau, ta có thể dùng một cây que dài để chia các quả bóng thành hai tập xanh và đỏ mà không động đến các quả bóng.

Lúc này, khi đưa một quả bóng mới đặt lên mặt bàn, bằng cách xác định nó nằm bên phía nào của cây que, ta có thể dự đoán màu sắc của quả bóng đó.

Vậy các quả bóng, cái bàn và cây que tượng trưng cho cái gì? Các quả bóng tượng trưng cho các điểm dữ liệu, màu xanh và đỏ tượng trưng cho 2 lớp. Cái bàn tượng trưng cho một mặt phẳng. Cây que tượng trưng cho một siêu phẳng đơn giản đó là một đường thẳng.

Điểm hấp dẫn ở đây đó là SVM có thể hình dung ra được đâu là siêu phẳng phù hợp nhất.

Đối với trường hợp phức tạp hơn thì sao? Thật ra dữ liệu ngoài thực tế rất phức tạp. Nếu các quả bóng xen lẫn vào nhau thì một cây que khó có thể phân lớp được.

Ta sử dụng thủ thuật: nhấc bổng cái bàn lên, nhanh chóng hất các quả bóng lên trời. Trong khi các quả bóng đang lơ lửng và nằm ở các vị trí thích hợp, ta dùng một mảnh giấy lớn để phân lớp các quả bóng đang lơ lửng này.

Nghe có vẻ gian dối? Không đâu, việc hất các quả bóng lên trời tương đương với việc ánh xạ tập dữ liệu ban đầu vào không gian nhiều chiều hơn. Trong trường hợp này, ta đi từ không gian 2 chiều đó là cái bàn vào không gian 3 chiều đó các quả bóng đang lơ lửng trên trời.

Làm sao SVM thực hiện được điều này? Bằng cách sử dụng một kernel, ta có thể đơn giản nâng dữ liệu ban đầu vào không gian nhiều chiều hơn. Mảnh giấy lớn lúc này cũng được gọi là một siêu phẳng, chỉ có điều đây là phương trình mặt phẳng chứ không phải phương trình đường thẳng.

Việc ánh xạ này trong thực tế được thực hiện như thế nào? Quả bóng nằm trên mặt bàn có một vị trí cụ thể, ta dùng trục tọa độ để xác định vị trí này. Ví dụ, quả bóng nằm cách mép trái 20cm và cách mép dưới 50cm được thể hiện trên trục tọa độ (x, y) tương ứng là (20, 50). x và y chính là không gian hai chiều của quả bóng. Khi đưa lên chiều thứ 3 là z(x, y), ta có thể tính được tọa độ của z trong không gian 3 chiều dựa vào tọa độ x,y ban đầu.

Margin SVM

Thuật ngữ margin trong SVM có nghĩa là gì? Margin là khoảng cách giữa siêu phẳng đến 2 điểm dữ liệu gần nhất tương ứng với các phân lớp. Trong ví dụ quả bóng và cái bàn, đó là khoảng cách giữa cây que và hai quả bóng xanh và đỏ gần nó nhất.

Điểm mấu chốt ở đây đó là SVM cố gắng maximize margin này, từ đó thu được một siêu phẳng tạo khoảng cách xa nhất so với 2 quả bóng xanh và đỏ. Nhờ vậy, SVM có thể giảm thiểu việc phân lớp sai (misclassification) đối với điểm dữ liệu mới đưa vào.

Tên gọi SVM xuất phát từ đâu? Trong ví dụ cái bàn và quả bóng, siêu phẳng cách đều với bóng xanh và bóng đỏ. Các quả bóng này chính là các điểm dữ liệu gọi là support vectors, vì chúng hỗ trợ (support) để dựng lên siêu phẳng.

Tại sao sử dụng SVM? SVM cho độ chính xác cao đối với tập dữ liệu có kiểu dữ liệu liên tục (continuous value), cùng với thuật toán cây quyết định là hai phương pháp thường được dùng để phân lớp dữ liệu. Tuy nhiên, không có mô hình phân lớp (classifier) nào là tốt nhất theo No Free Lunch Theorem. Thêm vào đó, việc lựa chọn kernel và diễn giải cho người dùng hiểu là một điểm trừ của SVM.