Các chiến lược combine nhiều learner

(Tóm tắt chương 15 cuốn “Introduction to Machine Learning”)

1. Cơ sở

Không có thuật toán học nào có thể đảm bảo là luôn cho performance cao nhất cho mọi ứng dụng và trên mọi tập dữ liệu, vì các thuật toán học khác nhau thường dựa trên một tập các tham số nào đó (hyperparameter) hoặc dựa trên một giả thiết nào đó về phân bố dữ liệu.

Ý tưởng của việc combine các learner xuất phát từ một suy nghĩ hợp lý là: các learner khác nhau có khả năng khác nhau, có thể thực hiện tốt nhất các loại công việc khác nhau (subtasks), khi kết hợp các learner này với nhau một cách hợp lý thì sẽ tạo thành một combined model mạnh và improve overall performance so với việc chỉ dùng các learner một cách đơn lẻ.

* Cách chọn các base-learner có thể:

(1) Sử dụng các thuật toán học khác nhau (learning algorithm) để train các base-learner khác nhau.

(2) Sử dụng cùng một thuật toán học nhưng với các tham số khác nhau. Ví dụ số tầng khác nhau trong multi-layer perceptron, số k khác nhau trong k-nearest neighbor,…

(3) Sử dụng các biểu diễn (representation) khác nhau của cùng một đối tượng đầu vào. Chẳng hạn các base-learner sử dụng các feature set (tập đặc trưng) khác nhau.

(4) Sử dụng các tập dữ liệu huấn luyện khác nhau để train các base-learner.

* Các chiến lược combine các learner có thể:

(1) Multiexpert combination kết  hợp các base-learner bằng cách cho các base-learner thực hiện song song. Cho một đối tượng đầu vào, các base-learner sẽ đưa ra quyết định và một bộ combiner riêng biệt sẽ kết hợp các đầu ra này để cho quyết định cuối cùng. Phương pháp này giống như việc lấy ý kiến của nhiều chuyên gia trong một buổi họp.
Trong chiến lược này có các phương pháp: Voting, mixture of experts, và stacked generalization.

(2) Multistage combination: Ý tưởng của chiến lược này là dùng một chuỗi các base-learner trong đó learner tiếp theo chỉ được huấn luyện hoặc test trên các instances mà learner trước dự đoán với độ tin cậy chưa cao.

Có thể diễn nôm như sau: Ta có N chuyên gia với trình độ và năng lực khác nhau và được xếp theo thứ tự tăng dần về cat-sê mà ta phải trả. Giả sử có 3 chuyên gia A, B, C trong đó giá thuê A là rẻ nhất, sau đến B, và giá thuê C là đắt nhất. Tôi cần thuê A, B, C làm một tập các vấn đề nào đó, ví dụ giải toán. Đầu tiên tôi thuê A giải toán. A chỉ giải được một số bài toán loại nào đó với độ chính xác đủ tin cậy, vì thế với các bài toán A chưa chắc lắm, tôi thuê B, và với các dạng toán B làm không tốt, tôi để cho C giải.

Ví dụ về chiến lược này là phương pháp Cascading.

2. Voting

Ý tưởng của voting là kết hợp các đầu ra của base-learner bằng một linear combination của các learner. Mỗi learner có một trọng số (vote). Chẳng hạn với bài toán phân lớp đa lớp, với một đầu vào, lớp nào nhận được nhiều vote nhất sẽ chiến thắng.

3. Error-Correcting Output Code

Chưa hiểu lắm

4. Bagging

Ý tưởng của chiến lược Bagging là train các bộ base-learner với các tập dữ liệu huấn luyện khác nhau một chút.

5. Boosting

Ý tưởng của Boosting là kết hợp nhiều bộ learner thành một bộ learner mạnh bằng cách train bộ learner sau trên những mistakes của bộ learner trước (các dữ liệu mà bộ learner trước dự đoán sai). Nhược điểm của chiến lược này là yêu cầu dữ liệu huấn luyện phải rất lớn.

Một phương pháp boosting khác khắc phục được điều này là AdaBoost (bài báo: Freund and Schapire. 1996. Experiments with a New Boosting Algorithm.)

6. Mixture of Experts Revisited

Chưa hiểu lắm

7. Stacked Generalization

Ý tưởng khá giống với voting nhưng hàm combine không nhất thiết phải là linear và combined function cũng được học từ dữ liệu.

8. Cascading

Ý tưởng như đã trình bày trong phần multistage combination

Các phương pháp ensemble đã được dùng thành công trong shared-task (ví dụ như đội The Ensemble trong Netflix Prize đã xếp thứ 2)

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: