Ý nghĩa tham số epsilon của class TermCriteria định nghĩa điều kiện dừng khi thuật toán học bị lặp trong SVM sử dụng Opencv

hell6w9rld · April 11, 2018, 8:29am

Hello
Mình sử dụng svm trong opencv để kiểm nghiệm thuật toán. Khi train model phải định nghĩa điều kiện dừng khi thuật toán học bị lặp bằng lớp TermCriteria. Ví dụ như sau

Ptr<SVM> svm = SVM::create();
svm->setType(SVM::C_SVC);
svm->setC(0.1);
svm->setKernel(SVM::LINEAR);
svm->setTermCriteria(TermCriteria(TermCriteria::MAX_ITER, 1, 1e-6));

Trong dòng này svm->setTermCriteria(TermCriteria(TermCriteria::MAX_ITER, 1, 1e-6));
TermCriteria::MAX_ITER là kiểu điều kiện dừng, trường hợp này là đạt đến 1 số lần lặp = số mình truyền vào thì dừng
1 là số lần lặp tối đa cho phép
1e-6 độ chính xác của model khi đạt được sẽ không lặp nữa

Tài liệu đặc tả lớp TermCriteria ở đây
https://docs.opencv.org/3.4.1/d9/d5d/classcv_1_1TermCriteria.html

Ở điều kiện lặp đạt đến 1 số n truyền vào sẽ dừng thì mình hiểu, nhưng điều kiện model đạt đến 1 độ chính xác epsilon thì dừng thì mình k hiểu. Độ chính xác của model tính như thế nào, bàng công thức nào. Làm sao để kiểm soát giá trị epsilon này khi huấn luyện

Mình đã hiểu cách kiểm soát tham số C, nhưng vì nó còn liên quan đến điều kiện dừng epsilon và số lần lặp lại. Nên tóm lại với dữ liệu đầu vào mình vẫn chưa thể kiểm soát được các tham số của model để cho ra siêu phẳng tối ưu như ý muốn. Help me
Gồm có các tham số C, số lần lặp lại tối đa, độ chính xác mong muốn

Thankyou

hungaya · April 11, 2018, 8:48am

Mỗi bước iteration của Gradient Descent di chuyển cost function L đạt minimum. Nếu cố định learning rate alpha, vì khoảng cách ||L(t) - L(t+1)|| càng ngày càng nhỏ. Khi L xấp xỉ convergence thì ||L(t) - L(t+1)|| vô cùng bé, không có hiệu quả nếu tiếp tục các bước iteration.

Vì vậy đa số điều kiện dừng của Gradient Descent là ||L(t) - L(t+1)|| >= epsilon, epsilon là 1 số vô cùng nhỏ, là hyperparameter do user chọn.

The loss function of SVM

hell6w9rld · April 11, 2018, 8:55am

Sao lại có max ở đây nhỉ
Mình đọc tài liệu thấy

hàm mục tiêu của svm hardmargin

có thể đảo ngược phân số chuyển về đạt min, và đưa 1/2 ra ngoài như bạn làm ở trên
hàm mục tiêu của svm softmargin và khi dùng kernel (chỉ khác nhau ở ràng buộc)

tương tự có thể đưa về đạt min bằng cách đảo ngược phân số, đưa 1/2 ra ngoài như trên

mình chưa biết hàm mục tiêu trên sao lại có max

hell6w9rld · April 11, 2018, 8:57am

Hình như bạn đạng nói đến giải bài toán tối ưu có ràng buộc của softmargin bằng cách chuyển về bài toán tối ưu không ràng buộc để giải bằng Gradient Descent à?

hell6w9rld · April 11, 2018, 9:04am

Mình chưa tìm hiểu đến giải các bài toán tối ưu hàm số bằng cách giải bài đối ngẫu của nó. Nên chưa rõ lý thuyết phần bạn nói trên. Thông qua ví dụ này bạn có thể chỉ cho mình cách xác định các tham số như C, số lần lặp lại, epsilon không
dữ liệu huấn luyện

int labels[6] = {1, -1, 1, -1, -1, 1};
    float trainingData[6][2] = 
    { 
        {501, 10 }, 
        {255, 10 }, 
        {501, 255}, 
        {10 , 501}, 
        {310, 300}, // nonlinear
        {300, 320}  // nonlinear
    };

sẽ được biểu diễn như sau

cấu hình tham số

Ptr<SVM> svm = SVM::create();
svm->setType(SVM::C_SVC);
svm->setC(0.1);
svm->setKernel(SVM::LINEAR);
svm->setTermCriteria(TermCriteria(TermCriteria::MAX_ITER, 1, 1e-1));

Mình đã hiểu tham số C. C càng lớn thì lề càng nhỏ, và điểm nhiễu bị bỏ đi càng ít, C rất lớn thì siêu phẳng tìm được có lề là hardmargin, không có điểm nhiễu nào bị bỏ. C càng nhỏ thì lề càng rộng, và điểm nhiễu bị bỏ đi càng nhiều
Tuy nhiên tham số số lần lặp lại và epsilon mình chưa kiểm soát được. Mình chỉ thấy nếu phần dữ liệu nolinear nhiều thì số lần lặp lại có xu hướng tăng để cải thiện độ chính xác của model. còn ít thì số lần lặp lại có xu hướng giảm

hungaya · April 11, 2018, 9:29am

Công thức loss function của SVM đa số không có max, phần này do mình copy 1 công thức cho tiện. Mình search lại thì cách đó là hinge loss function, có thể tham khảo thêm.

GD là 1 phần của ML project. GD là 1 cách để làm cho cost function đạt minimum, cost function có thể là cost function của bất kì ML methods (SVM, Softmax, NN,…), chứ không riêng gì SVM.

Phần đối ngẫu thì mình không biết nên cũng không có ý kiến gì.

Về phần chọn hyperparameter C, epsilon như thế nào thì thuộc về bên ứng dụng. Bạn có thể xem khóa ML của Andrew Ng có chỉ cách triển khai 1 ML project. Phần thiết lập project cho ML mình chỉ thấy Andrew dạy thôi, sách không có đề cập. Cá nhân mình thấy nó dễ học nhất, nhưng lại quan trọng nhất.

hell6w9rld · April 11, 2018, 9:31am

Mình tiếp cận theo hướng tìm hiểu tổng quan rồi kiểm nghiệm bằng thư viện để thấy nó chạy như thế nào. Sau đó mới đào sâu vào từng phần . SVM mình tìm hiểu còn bài toán đối ngẫu của svm tuyến tính, bài toán đối ngẫu của svm softmargin hoặc giải bằng chuyển về bài toán tối ưu không ràng buộc sử dụng Gradient Descent để giải, bài toán đối ngẫu của svm phi tuyến. Túm lại là mình trừ phần đối ngẫu lại vì thấy nó hơi sâu và chưa cần thiết đào sâu lúc này.
Hiện tại mình đang thư chạy chương trình để xem kết quả và hiểu các tham số, cách cấu hình thôi, còn cách giải ntn bên trong, bạn nói mình chưa hiểu được :3 chưa đọc đến

hitman17528 · April 11, 2018, 10:08am

Hiểu đơn giản thế này đi em: Tất cả các giải thuật lặp (iterative) đều cần 1 sự kết thúc, và đó chính là epsilon, chính là sai số mà chúng ta mong muốn, vd độ chính xác 95% thì có sai số là 5% -> epsilon = 0.05.
Vì sao có sai số? Vì trong thực tế ko thể có lời giải chính xác (exact solution) như em học trên đại học, là tính đạo hàm, lấy tích phân! Máy tính ko thông minh như thế, nên chúng cần các phương pháp số, để tính gần đúng nghiệm của các hệ phương trình!

Nếu em muốn viết từ đầu hoặc nghiên cứu sâu hơn, hãy đọc 1 cuốn sách về Numerical algorithm để hiểu các ý tưởng trong đó để xem em có phù hợp và đủ kiên nhẫn hay ko Anh recommend cuốn này

hell6w9rld · April 11, 2018, 10:16am

Trước mắt em cần hiểu để có thể cấu hình được tham số cho model hoạt động đã ạ. mà em chưa biết kiểm soát các tham số này, vì được dùng cùng 1 lúc nên sinh ra nhiều trường hợp để test.
Với svm softmargin cần dùng tham số C, số lần lặp lại, epsilon. Em test ra được 1 bảng tham số đi kèm kết quả mà chưa nhìn được quy luật và hiểu được ý nghĩa. Với dữ liệu cụ thể như trên em chưa biết chọn tham số ntn để cho ra siêu phẳng tối ưu T.T

hitman17528 · April 11, 2018, 10:19am

Có 1 số thuật toán chỉ phù hợp với 1 loại bài toán nhất định, vd đối với bài toán này thì cho kết quả hội tụ (gần với kết quả) nhưng với bài khác thì lại cho kết quả phân kỳ (xa với kết quả). Cho nên thuật toán hay model nào mà số lần lặp quá lớn mà sai số vẫn rất lớn thì em nên chọn model và thuật toán khác! Cái này em test nhiều lần sẽ hiểu!

hungaya · April 11, 2018, 11:25am

Việc tìm maximum của objective function hay minimum của cost function đều có 2 cách tiếp cận:

hướng machine learning: chủ yếu sử dụng GD để đạt giá trị xấp xỉ, có nhiều variations của GD như Batch GD, Stochastics GD, GD with momentum.
hướng statistics: giải bằng phương trình toán học - equation. Giải phương trình được giá trị chính xác. Tuy nhiên nó chỉ phù hợp với data từ 10.000 feature trở xuống.

Do đó mà hướng machine learning dễ tiếp cận hơn so với thống kê truyền thống. SVM dù linear, kernel, hay softmargin đều có thể áp dụng theo cả 2 hướng ML và thống kê.

Mối giải thuật, SVM nói riêng, đều có các hyperparameter cần phải tuning để cost function L đạt giá trị nhỏ nhất có thể, hoặc L giảm liên tục sau mỗi lần lặp, L có đồ thị có dạng 1/ exp(x).

Ví dụ hyperparameter là learning rate alpha. Nếu alpha nhỏ thì giải thuật chạy lâu, không có kết quả tốt. Nếu alpha quá lớn thì cost function tăng sau mỗi lần lặp.

Chiến lược chung để chỉnh là giảm bias trên cross-validation set, sau đó giảm variance trên test set.

Thư viện sklearn hay OpenCV cho phép user chỉnh các hyperparameter. Nếu em không hiểu rõ từng công thức của SVM thì không thể chỉnh các hyperparameter được.