Support vector machine (SVM) hỏi gì đáp nấy

SVM classification

SVM classification

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.

Clip bên dưới sẽ minh họa cho thao tác trên của SVM

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

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.

Có thư viện nào cho SVM? Hiện tại có rất nhiều thư viện cài đặt SVM. Một vài thư viện phổ biến như scikit-learn, MATLAB và dĩ nhiên là libsvm.

Nguồn: http://www.kdnuggets.com/2015/05/top-10-data-mining-algorithms-explained.html

Tham khảo thêm:

Advertisements

49 thoughts on “Support vector machine (SVM) hỏi gì đáp nấy

  1. cho em hỏi bài toán này áp dụng với các dữ liệu liên tục ? thầy giải thích cụ thể hơn được không ạ. Em có một bài toán phân lớp mà dữ liệu đầu vào các feature có thể có mối liên hệ với nhau thì dùng giải thuật này được không ạ, em muốn dùng một giải thuật ANN, giải thuật nào của ANN thì phù hợp bài toán của em ạ.

    Like

  2. Em chào anh. Hiện tại em đang thực hiện đồ án tốt nghiệp với đề tài “Nhận dạng đối tượng dựa trên bộ tham số”. Cụ thể bài toán của em như sau:
    – Một đối tượng có thể có nhiều chế độ hoạt động khác nhau.
    – Các tham số của mỗi đối tượng là cố định (khoảng 7-8 tham số)
    – Bộ dữ liệu được cung cấp có 164 đối tượng khác nhau và 302 chế độ hoạt động của các đối tượng naỳ.
    – Khi hệ thống thu nhận được một bộ tham số, ta cần nhận dạng xem bộ tham số này là thuộc loại nào trong số các đối tượng đã biết.
    Em đọc về bài viết SVM của anh, em thấy bài toán của em có thể áp dụng được multi-class, tuy nhiên, trong trường hợp số lớp cần được phân lớp là khá lớn. Anh có bổ sung hay hướng đi nào khác để em có thể tham khảo không ạ.
    Em cám ơn anh!

    Like

    • Chào em, với bài toán multi-classification, em có thể áp dụng kỹ thuật one-vs-all (quy về bài toán binary-classification) hoặc mô hình Neural Network, Naive Bayes với đầu ra là số lớp cần phân lớp (có thể gán nhãn từ 0-k) hay áp dụng các thuật toán clustering với số k bằng số đối tượng của tập dữ liệu.

      Like

  3. Anh ơi, cho em hỏi chút ạ:
    Em đang đọc về SVM nhưng có vài điểm thắc mắc ạ, với những bài toán mà linear kernel của SVM không thể giải quyết thì SVM có Gaussian kernel giải quyết ( em đọc thì gaussian kernel không phải chỉ dùng mình trong SVM mà dùng chung cho ML) giúp giảm chiều của feature nhưng em không hiểu chính xác ý nghĩa của Gaussian kernel lắm, có một khái niệm nữa là kernel trick, giúp mở rộng chiều của feature giúp dễ dàng xác định mặt siêu phẳng trong SVM, em hỏi là 2 khái niệm kernel và kernel trick có khác hay liên quan không ạ, Em cảm ơn.

    Like

        • Anh có thể giúp em lấy ví dụ về sử dụng kernel như thế nào trong SVM không ạ, ví dụ em có feature 2 chiều [[1,2],[3,4]] thì khi đó nếu áp dụng kernel dạng tuyến tính thì K=u.v (em không hiểu lắm là khi này thì u là x1[1,2] thì v sẽ là gì ạ) mà khi đó K sẽ là một giá trịi hay sẽ là một tập feature mới có chiều nhiều hơn tập dữ liệu cũ ạ. ( em có tìm hiểu nhưng vẫn chưa hiểu rõ lắm). Thêm một khái niệm inner product và dot product anh có thể giải thích cho em hiểu không ja.
          em cảm ơn

          Like

          • Anh cho em ví dụ tổng quát để em dễ hình dung.
            Cho x = (x_1, x_2), z = (z_1, z_2)
            Polynomial Kernels
            K(x, z) = \prec x, z \succ ^2 = (x_1z_1 + x_2z_2)^2
            = x_1^2z_1^2 + x_2^2z_2^2 + 2x_1z_1x_2z_2
            = \prec (x_1^2, x_2^2, x_1x_2\sqrt 2),(z_1^2, z_2^2, z_1z_2\sqrt 2) \succ
            = \prec \phi(x), \phi(z) \succ

            v sẽ là [3,4]. Ở đây, em chỉ có 2 feature vector nên K sẽ trả về 1 giá trị. Nếu em có nhiều hơn 2 feature, ta sẽ tính kernel K cho từng cặp vector để trả về một ma trận vuông với số chiều bằng số lượng vector hay còn gọi là Gram matrix.

            Mục tiêu của chúng ta khi cho trước vector x\in R^(n+1), ta đi tính feature mới f \in R^(m + 1). Trong đó, n là số thành phần trong vector xm là số lượng vector có trong tập dữ liệu. Lúc này, thay vì giải bài toán ban đầu y = \theta^T x ta đi giải y = \theta^T f. Gram matrix được sử dụng tại đây, do f = (f_1, f_2, ..., f_m), i \in [1, m], f_i = K(x, x^i). Tức là Gram matrix sẽ là đầu vào cho bài toán mới của chúng ta.

            Dot product (tích vô hướng): là tổng của tích các thành phần giữa 2 vector. Ý nghĩa dùng làm phép biến đổi nâng chiều trong Kernel.

            Inner product (tích có hướng): cho biết mối tương quan giữa 2 vector. Tích 2 vector càng gần 1 thì 2 vector càng giống nhau ngược lại càng gần 0 thì 2 vector khác nhau. Ý nghĩa giảm bớt số chiều của Gram matrix khi ta quan sát thấy các vector trùng hoặc gần giống nhau.

            Like

  4. Thầy cho em hỏi chút. SVM phân 2 lớp thì input đầu vào dạng:
    -1 1:1 6:1 14:1 22:1 36:1 42:1 49:1 64:1 67:1 72:1 74:1 77:1 80:1 83:1
    -1 1:1 6:1 17:1 19:1 39:1 42:1 53:1 64:1 67:1 73:1 74:1 76:1 80:1 83:1
    -1 2:1 6:1 18:1 20:1 37:1 42:1 48:1 64:1 71:1 73:1 74:1 76:1 81:1 83:1
    +1 5:1 11:1 15:1 32:1 39:1 40:1 52:1 63:1 67:1 73:1 74:1 76:1 78:1 83:1
    -1 5:1 16:1 30:1 35:1 41:1 64:1 67:1 73:1 74:1 76:1 80:1 83:1
    -1 5:1 6:1 15:1 20:1 37:1 40:1 50:1 63:1 67:1 73:1 75:1 76:1 80:1 83:1
    -1 5:1 7:1 16:1 29:1 39:1 40:1 48:1 63:1 67:1 73:1 74:1 76:1 78:1 83:1
    -1 1:1 11:1 18:1 20:1 37:1 42:1 59:1 62:1 71:1 72:1 74:1 76:1 80:1 83:1
    +1 5:1 18:1 19:1 39:1 40:1 63:1 67:1 73:1 74:1 76:1 80:1 83:1
    Trong đố: +1, -1 là nhãn.
    Nếu phân đa lớp cụ thể là 4 lớp thì cách input đầu vào như thế nào Thầy? Khi chạy vẫn chạy như 2 lớp hả Thầy. Em cảm ơn Thầy. Mong Thầy giải đáp

    Like

        • em đọc tài liệụ có một số chiến lược phân đa lớp với SVM: như OAR, OAO, Fuzzy OAO. Nhưng em không hiểu cách input dữ liệu để đưa vào chạy SVM. Phân đa lớp chạy giống phân 2 lớp đúng không Thầy.

          Like

            • Thầy! Em có mẫu dữ liệu trên web: http://www.cs.colorado.edu/~jbg/teaching/CSCI_5622/rank.train
              Thầy có thể giải thích các thông số cho em chút được không?
              1 qid:1 1:0.057239 2:0.000439 3:0.320218 4:1.000000 5:0.000000 6:0.000000 7:0.000000 # Terminator 3: Rise of the Machines
              2 qid:1 1:-0.059483 2:0.051360 3:1.159401 4:0.000000 5:0.000000 6:0.000000 7:0.000000 # Sleuth
              3 qid:1 1:-0.074544 2:-0.017120 3:0.669877 4:0.000000 5:1.000000 6:0.000000 7:0.000000 # Party, The
              4 qid:1 1:0.034648 2:0.032045 3:0.809741 4:0.000000 5:0.000000 6:0.000000 7:1.000000 # Donnie Brasco
              5 qid:1 1:-0.093370 2:0.098768 3:0.879673 4:0.000000 5:0.000000 6:0.000000 7:1.000000 # Gattopardo, Il
              1 qid:2 1:0.012057 2:0.003951 3:-0.309169 4:1.000000 5:1.000000 6:0.000000 7:0.000000 # Hard Way, The
              2 qid:2 1:-0.149849 2:-0.013608 3:0.949605 4:0.000000 5:0.000000 6:0.000000 7:1.000000 # Key Largo
              3 qid:2 1:0.023352 2:0.025022 3:0.809741 4:0.000000 5:1.000000 6:0.000000 7:1.000000 # Yin shi nan nu
              4 qid:2 1:-0.018065 2:0.039069 3:0.460082 4:0.000000 5:0.000000 6:0.000000 7:1.000000 # Silkwood
              5 qid:2 1:0.023352 2:-0.001317 3:-0.588897 4:0.000000 5:1.000000 6:0.000000 7:1.000000 # Love Affair
              1 qid:3 1:-0.006770 2:0.000439 3:0.040490 4:1.000000 5:0.000000 6:0.000000 7:0.000000 # F/X
              2 qid:3 1:0.057239 2:0.002195 3:-0.728761 4:1.000000 5:0.000000 6:0.000000 7:0.000000 # League of Extraordinary Gentlemen, The
              3 qid:3 1:0.019587 2:0.005707 3:-0.379101 4:1.000000 5:0.000000 6:0.000000 7:1.000000 # Program, The
              4 qid:3 1:0.015822 2:-0.024143 3:-0.588897 4:1.000000 5:0.000000 6:0.000000 7:1.000000 # Rapid Fire
              5 qid:3 1:0.049709 2:0.026777 3:0.250286 4:0.000000 5:0.000000 6:0.000000 7:1.000000 # Score, The
              Em cảm ơn Thầy.

              Like

                • Thầy! Theo em đọc thì em hiểu: Nếu phân 3 lớp: a, b, c ta sẽ chia theo công thức n*(n-1)/2 lớp con: (a,b), (b,c)(c,a). Nếu phân làm 4 lớp a, b, c, d ta chia làm 6 cặp theo công thức trên (a,b), (a,c), (a,d), (b,c), (b,d), (c,d). Nếu em có tập véc tơ đại diện cho 4 lớp (0 – 3) ví dụ như:
                  0 1:1 6:1 14:1 22:1 36:1 42:1 49:1 64:1 67:1 72:1 74:1 77:1 80:1 83:1
                  1 1:1 6:1 17:1 19:1 39:1 42:1 53:1 64:1 67:1 73:1 74:1 76:1 80:1 83:1
                  2 2:1 6:1 18:1 20:1 37:1 42:1 48:1 64:1 71:1 73:1 74:1 76:1 81:1 83:1
                  3 5:1 11:1 15:1 32:1 39:1 40:1 52:1 63:1 67:1 73:1 74:1 76:1 78:1 83:1
                  1 5:1 16:1 30:1 35:1 41:1 64:1 67:1 73:1 74:1 76:1 80:1 83:1
                  3 5:1 6:1 15:1 20:1 37:1 40:1 50:1 63:1 67:1 73:1 75:1 76:1 80:1 83:1
                  0 5:1 7:1 16:1 29:1 39:1 40:1 48:1 63:1 67:1 73:1 74:1 76:1 78:1 83:1
                  1 1:1 11:1 18:1 20:1 37:1 42:1 59:1 62:1 71:1 72:1 74:1 76:1 80:1 83:1
                  thì em sẽ chuyển như thế nào để đưa vào SVM chạy được Thầy. Em Cảm ơn Thầy. Rất mong Thầy giải thích giúp em.

                  Like

                  • Em cần transform label sang dạng true/false hoặc 1/0 như bên dưới

                    0 vs all
                    1 1:1 6:1 14:1 22:1 36:1 42:1 49:1 64:1 67:1 72:1 74:1 77:1 80:1 83:1
                    0 1:1 6:1 17:1 19:1 39:1 42:1 53:1 64:1 67:1 73:1 74:1 76:1 80:1 83:1
                    0 2:1 6:1 18:1 20:1 37:1 42:1 48:1 64:1 71:1 73:1 74:1 76:1 81:1 83:1
                    0 5:1 11:1 15:1 32:1 39:1 40:1 52:1 63:1 67:1 73:1 74:1 76:1 78:1 83:1
                    0 5:1 16:1 30:1 35:1 41:1 64:1 67:1 73:1 74:1 76:1 80:1 83:1
                    0 5:1 6:1 15:1 20:1 37:1 40:1 50:1 63:1 67:1 73:1 75:1 76:1 80:1 83:1
                    1 5:1 7:1 16:1 29:1 39:1 40:1 48:1 63:1 67:1 73:1 74:1 76:1 78:1 83:1
                    0 1:1 11:1 18:1 20:1 37:1 42:1 59:1 62:1 71:1 72:1 74:1 76:1 80:1 83:1

                    1 vs all
                    0 1:1 6:1 14:1 22:1 36:1 42:1 49:1 64:1 67:1 72:1 74:1 77:1 80:1 83:1
                    1 1:1 6:1 17:1 19:1 39:1 42:1 53:1 64:1 67:1 73:1 74:1 76:1 80:1 83:1
                    0 2:1 6:1 18:1 20:1 37:1 42:1 48:1 64:1 71:1 73:1 74:1 76:1 81:1 83:1
                    0 5:1 11:1 15:1 32:1 39:1 40:1 52:1 63:1 67:1 73:1 74:1 76:1 78:1 83:1
                    1 5:1 16:1 30:1 35:1 41:1 64:1 67:1 73:1 74:1 76:1 80:1 83:1
                    0 5:1 6:1 15:1 20:1 37:1 40:1 50:1 63:1 67:1 73:1 75:1 76:1 80:1 83:1
                    0 5:1 7:1 16:1 29:1 39:1 40:1 48:1 63:1 67:1 73:1 74:1 76:1 78:1 83:1
                    1 1:1 11:1 18:1 20:1 37:1 42:1 59:1 62:1 71:1 72:1 74:1 76:1 80:1 83:1

                    2 vs all
                    0 1:1 6:1 14:1 22:1 36:1 42:1 49:1 64:1 67:1 72:1 74:1 77:1 80:1 83:1
                    0 1:1 6:1 17:1 19:1 39:1 42:1 53:1 64:1 67:1 73:1 74:1 76:1 80:1 83:1
                    1 2:1 6:1 18:1 20:1 37:1 42:1 48:1 64:1 71:1 73:1 74:1 76:1 81:1 83:1
                    0 5:1 11:1 15:1 32:1 39:1 40:1 52:1 63:1 67:1 73:1 74:1 76:1 78:1 83:1
                    0 5:1 16:1 30:1 35:1 41:1 64:1 67:1 73:1 74:1 76:1 80:1 83:1
                    0 5:1 6:1 15:1 20:1 37:1 40:1 50:1 63:1 67:1 73:1 75:1 76:1 80:1 83:1
                    0 5:1 7:1 16:1 29:1 39:1 40:1 48:1 63:1 67:1 73:1 74:1 76:1 78:1 83:1
                    0 1:1 11:1 18:1 20:1 37:1 42:1 59:1 62:1 71:1 72:1 74:1 76:1 80:1 83:1

                    3 vs all
                    0 1:1 6:1 14:1 22:1 36:1 42:1 49:1 64:1 67:1 72:1 74:1 77:1 80:1 83:1
                    0 1:1 6:1 17:1 19:1 39:1 42:1 53:1 64:1 67:1 73:1 74:1 76:1 80:1 83:1
                    0 2:1 6:1 18:1 20:1 37:1 42:1 48:1 64:1 71:1 73:1 74:1 76:1 81:1 83:1
                    1 5:1 11:1 15:1 32:1 39:1 40:1 52:1 63:1 67:1 73:1 74:1 76:1 78:1 83:1
                    0 5:1 16:1 30:1 35:1 41:1 64:1 67:1 73:1 74:1 76:1 80:1 83:1
                    1 5:1 6:1 15:1 20:1 37:1 40:1 50:1 63:1 67:1 73:1 75:1 76:1 80:1 83:1
                    0 5:1 7:1 16:1 29:1 39:1 40:1 48:1 63:1 67:1 73:1 74:1 76:1 78:1 83:1
                    0 1:1 11:1 18:1 20:1 37:1 42:1 59:1 62:1 71:1 72:1 74:1 76:1 80:1 83:1

                    Like

  5. Em đang làm đồ án nhận dạng số dựa vào thuật toán SVM. Em dùng đặc trưng haar để nhận dạng, nhưng em vẫn chưa hiểu làm sao để từ một cái hình có số đưa vào mà nó dựa vào SVM để nhận dạng. Xin thầy hãy giáp đáp tường tận giúp em với ạ. Em cảm ơn thầy!

    Like

  6. Em chào thầy! Em đang làm phân lớp văn bản dùng: gSpan + SVM. Em đã có tập đồ thị phổ biến. Nhưng em vẫn chưa hiểu làm sao để chuyển dữ liệu sang dạng vector để đưa vào SVM để huấn luyện và phân lớp. Xin thầy hãy giải đáp giúp em với ạ. Em cảm ơn thầy!

    Like

  7. Chào thầy . Em đang làm đồ án về nhận diện cảm xúc . Ban đầu em chỉ trích những đặc trưng từ mắt và miệng rồi gắn nhãn cho nó như mặt buồn, vui , ngạc nhiên rồi đưa vào train trong libsvm . Nhưng em không biết tạo dữ liệu như thế nào để đưa những đặc trưng (mắt + miệng) từ 1 hình mới vào để lấy nghiệm là 1 label (buồn or vui or …) . Em cảm ơn , mong thầy giúp đỡ.

    Like

Trả lờ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