Posted in Khác

Support Vector Machine

 

  1. Giới thiệu

Một số phương pháp phân loại state-of-the-art : SVM , boosted decision trees, regularized logistic regresstion , neural network , random forests . Và SVMs là một “baseline method” cho bài toán phân loại . Support Vector Machines (SVMs) là 1 kĩ thuật học máy thống kê được giới thiệu bởi Vapnik et al [1] [2]

Sẽ chọn một hyperplane phân biệt các mãu trong bài toán classification .  SVMs sử dụng một chiến lược tối đa hoá margin giữa tập dữ liệu huấn luyện . Trong trường hợp không thể phân biệt dữ liệu huấn luyện một cách tuyến tính ( bởi vì một số noises trong tập dữ liệu huấn luyện ……… ) , chúng ta sẽ tìm một hyperplane chấp nhận một số phân loại sai . Trong trường hợp này chúng ta sẽ xây một optimal hyperplane bằng cách thêm vào một soft margin parameter , nó sẽ cân đối giữa training error và độ lớn của margin [2] . Parameter C này sẽ kiểm soát overfitting

1

Một hyperplane sẽ được định nghĩa bởi một intercept term b và một normal vector w mà vuông góc với hyperplane . Phương trình phân loại tuyến tính sẽ là :

2

Margin giữa 2 lớp sẽ là 2/độ lớn của w . Nên bài toán quy về tìm vector w và b sao cho

3

4

  1. Mở rộng của SVM model

Soft margin classification

16

Nếu tập dữ liệu trainning không phân biệt tuyến tính , phương pháp cơ bản là cho pháp một “fat decision margin” mà có một số lỗi – nằm trong hoặc sai bên của margin . Chung ta sẽ trả giá cho mỗi example mà phân loại sai , phụ thuộc vào độ xa cho tới margin . Bài toán trở thành

6

Multiclass

OnevsRest : Xây dựng một tập phân loại one-versus-rest , chọn class mà bộ phân loại tạo ra margin lớn nhất với dữ liệu test .

OnevsOne :Xây dựng một tập phân loại one-versus-one , và chọn class nào mà được lựa chọn nhiều nhất bởi các bộ phân loại . Sẽ có k(k-1)/2 bộ phân loại , thời gian huấn luyện có thể tăng nhưng dataset của mỗi bộ phân loại thì nhỏ hơn nhiều .

LibSVM sử dụng OnevsOne [4]

Dùng chung tham số cho k (k-1) /2 models [7]

Các method multi-class như :

  • One vs. One multi-class classification using a bound-constrained formulation
  • Multi-class classification by solving a single optimization problem (again, a bounded formulation). See Section 3 of our comparison paper.
  • Multi-class classification using Crammer and Singer’s formulation.
  • Regression using a bound-constrained formulation
  • Multi-class classification using Crammer and Singer’s formulation with squared hinge (L2) loss

đều được hỗ trợ ở [5]

  • Nonlinear SVMs7

Nếu dữ liệu không cho phép chúng ta phân loại theo linear classifier , chúng ta có thể map data lên một không gian có số chiều lớn hơn và sử dụng liner classifier trong không gian lớn hơn đó .

SVMs , cũng như các linear classifiers khác , cũng cấp một cách thuận tiện để mapping tới không gian có số chiều lớn hơn , thường được gọi là “the kernel trick” . SVM linear classifiers dựa vào dot product giữa các điểm dữ liệu .  Một kernel function K sẽ là một function chịu trách nhiệm tính toán dot product trong không gian vừa được mở rộng .

  1. Feature set

Words : all words in the sentence (== bag of word ??)

Important words : Main words in the sentence , including proper-nouns , common nouns , verbs , adjectives , adverbs , and subordinating conjunctions

N-grams of words : Uni , bi , tri hoặc kết hợp 3 thằng hay 2 thằng lại . Kết quả khá ổn [3]

Naïve Bayes feature [3]

Word2vec

Doc2vec

Glove

Tf-idf

Có thể chọn tay các features

Có thể dùng LDA để giảm số chiều của features

  1. NaiveBayes SVMs

Multiclass thì tính

Ví dụ với bài toán Sentiment classification có 3 lớp Positive , Neutral , Negative tương ứng với tập nhãn {-1,0,1} [5]

Capture

α là smoothing parameter (=1 theo [3] )

p là tổng tất cả binarization vectors của positive samples

q là tổng tất cả các binarization vectors của các samples khác (negative and neutral)

Log-ratio của positive samples sẽ tính như sau :

8

x mang nhãn 1 sẽ thay thế bằng r . x (elementwise product)

  1. Sử dụng LibSVM

Không cho kết quả tốt nhất , chỉ cho ra kết quả chấp nhận được

Là một thư viện dễ dùng

Data format

<label> <index1>:<value1> <index2>:<value2> …

.

.

.

Scaling

Scaling trước khi áp dụng SVM là rất quan trọng [8]

Bước này thu hẹp giá trị các feature về ở trong khoảng [-1..1] hoặc [0..1]

Model Selection

Có 4 loại kernels cơ bản :

9

Khi nào dùng Kernel nào : Khi số features là rất lớn , chúng ra có thể không cần map data tới không gian có số chiều nhiều hơn . Như thế , nonlinear mapping không cải thiện hiệu năng . Sử dụng linear kernel là đủ tốt và nó chỉ cần tìm tham số C nên rất nhanh .

Khi số mẫu << số features nên dùng Linear Kernel

Kho số mẫu và số features đều rất lớn dùng LIBLINEAR (chạy nhanh hơn LIBSVM)

Khi số mẫu >> số features nên dùng : Nên sử dụng nonlinear kernels , vì thường xuyên maps data tới không gian có chiều lớn hơn . Nếu muốn dùng linear kernel thì cũng được .

Nói chung nên thử hết mọi loại Kernel

Các tham số

Các tham số khi train model

10

Các tham số khi scaling dữ liệu

11

Chú ý : Phải scaling dữ liệu huấn luyện và dữ liệu test cùng 1 range để ra keets quả chính xác nhất

Các tham số khi dự đoán

12

Có thể sử dụng file checkdata.py để kiểm tra dataset đã đúng định dạng dữ liệu chưa

Tối ưu hoá tìm ra các tham số tối ưu

13

Grid.py là tool lựa chọn tham số cho C-SVM classification sử dụng Kernel RBF

Tự động hoá quá trình tối ưu

14

Chia dữ liệu có thể dùng :

15

Cách tối ưu

Ví dụ :

Sử dụng tham số mặc định
$ ./svm-train svmguide1

$ ./svm-predict svmguide1.t svmguide1.model svmguide1.t.predict

→ Accuracy = 66.925%

Scaling data với tham số mặc định

$ ./svm-scale -l -1 -u 1 -s range1 svmguide1 > svmguide1.scale

$ ./svm-scale -r range1 svmguide1.t > svmguide1.t.scale

$ ./svm-train svmguide1.scale

$ ./svm-predict svmguide1.t.scale svmguide1.scale.model svmguide1.t.predict

→ Accuracy = 96.15%

Scaling data với tham số được lựa chọn

$ python grid.py svmguide1.scale

  • · · 2.0 2.0 96.8922

(Best C=2.0, γ=2.0 with five-fold cross-validation rate=96.8922%)

$ ./svm-train -c 2 -g 2 svmguide1.scale

$ ./svm-predict svmguide1.t.scale svmguide1.scale.model svmguide1.t.predict

→ Accuracy = 96.875%

Sử dụng script tự động

$ python easy.py svmguide1 svmguide1.t

Scaling training data…

Cross validation…

Best c=2.0, g=2.0

Training…

Scaling testing data…

Testing…

Accuracy = 96.875% (3875/4000) (classification)

[1] C. Cortes and V. Vapnik. Support-Vector Networks. Machine Learning, 20(3):273–297,1995.

[2]V.N. Vapnik. Statistical Learning Theory. Wiley-Interscience, 1998.

[3] S.Wang and CD.Manning , Baselines and Bigrams: Simple, Good Sentiment and Topic Classification , 2012

[4] http://www.csie.ntu.edu.tw/~cjlin/libsvm/faq.html#f419

[5]  Remi Lebret and Ronan Collobert , N-GRAM-BASED LOW-DIMENSIONAL REPRESENTA – TION FOR DOCUMENT CLASSIFICATION , Accepted as a workshop contribution at ICLR 2015l

 

[6] https://www.csie.ntu.edu.tw/~cjlin/bsvm/

[7] http://www.csie.ntu.edu.tw/~cjlin/libsvm/faq.html#f507

[8] ftp://ftp.sas.com/pub/neural/FAQ.html

Advertisements

One thought on “Support Vector Machine

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 Đăng xuất / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Đăng xuất / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Đăng xuất / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Đăng xuất / Thay đổi )

Connecting to %s