AdaBoost hỏi gì đáp nấy

Algorithms 6 Minutes
AdaBoost
AdaBoost

Dùng để làm gì? AdaBoost là một thuật toán boosting dùng để xây dựng bộ phân lớp (classifier).

Như chúng ta đã biết, một classifier nhận vào một tập dữ liệu để học và cố gắng dự đoán hay phân lớp mẫu dữ liệu mới thuộc về phân lớp nào.

Boosting là gì? boosting là thuật toán học quần thể bằng cách xây dựng nhiều thuật toán học cùng lúc (ví dụ như cây quyết định) và kết hợp chúng lại. Mục đích là để có một cụm hoặc một nhóm các weak learner sau đó kết hợp chúng lại để tạo ra một strong learner duy nhất.

Sự khác nhau giữa strong và weak leaner là gì? weak learner phân loại với độ chính xác hầu như không cao. Một ví dụ phổ biến của weak learner là cây quyết định một cấp (decision stump). Ngược lại, strong leaner có độ chính xác cao hơn nhiều.

Ví dụ của AdaBoost là gì? bắt đầu với 3 weak learners. Ta sẽ training chúng 10 hiệp trên tập dữ liệu bệnh nhân. Tập dữ liệu này chứa thông tin chi tiết về hồ sơ y tế của bệnh nhân.

Câu hỏi đặt ra là, làm thế nào ta có thể dự đoán người bệnh có bị ung thư hay không? Đây là câu trả lời của AdaBoost.

Trong hiệp 1: AdaBoost lấy mẫu trên tập huấn luyện và kiểm tra độ chính xác của mỗi learner là bao nhiêu. Kết quả cuối cùng trả về là learner có độ chính xác cao nhất.

Ngoài ra, các mẫu dữ liệu bị phân loại sai sẽ được đánh trọng số lớn để có cơ hội cao hơn trong việc lấy mẫu ở hiệp tiếp theo.

Một điều nữa, learner tốt nhất cũng được đánh trọng số dựa vào độ chính xác và sự kết hợp của nó vào toàn bộ các learner (hiện tại chỉ có 1 learner).

Trong hiệp 2: AdaBoost một lần nữa cố gắng tìm được learner có độ chính xác cao nhất.

Điểm đáng lưu ý ở đây đó là mẫu dữ liệu của tập huấn luyện hiện đang bị ảnh hưởng nhiều hơn bởi các trọng số phân lớp sai (misclassified weights). Nói cách khác, bệnh nhân bị phân lớp sai trước đó sẽ có cơ hội cao hơn để xuất hiện ở lượt tiếp theo.

Tại sao? giống như bước sang level 2 của video game, ta không phải bắt đầu lại từ đầu khi nhân vật của mình bị chết. Thay vào đó, ta bắt đầu ở level 2 và tập trung mọi nỗ lực để tiến đến level 3.

Tương tự như vậy, learner đầu tiên có khả năng phân loại một nhóm bệnh nhân chính xác. Thay vì cố gắng phân lớp những bệnh nhân này một lần nữa, ta sẽ tập trung mọi nỗ lực vào phân lớp các bệnh nhân bị phân lớp sai (misclassified patients).

Learner tốt nhất một lần nữa được đánh trọng số và tích hợp vào quần thể classifier, bệnh nhân bị phân lớp sai được đánh trọng số để họ có cơ hội cao hơn trong việc lấy mẫu tiếp theo.

Sau 10 hiệp: ta còn lại một quần thể các learner được đánh trọng số sau nhiều lần được huấn luyện lặp đi lặp lại ở các hiệp trước trên các mẫu dữ liệu bị phân lớp sai.

Tại sao sử dụng AdaBoost? đây là thuật toán đơn giản và dễ dàng cài đặt. Thêm vào đó, tốc độ học rất nhanh. Các weak learner đơn giản hơn rất nhiều các strong learner, nhờ vậy thuật toán chạy nhanh hơn.

Một điều nữa, AdaBoost là phương pháp có khả năng điều chỉnh các classifier rất tinh tế. Vì mỗi hiệp AdaBoost lại tinh chỉnh lại các trọng số cho các learner tốt nhất. Điều bạn cần làm đó là xác định số hiệp để lặp.

Cuối cùng, đây là thuật toán linh hoạt và đa năng. AdaBoost có thể kết hợp với bất kỳ thuật toán học máy nào và nó có thể làm việc với một lượng lớn dữ liệu khác nhau.

Nó được sử dụng ở đâu? AdaBoost có nhiều cách cài đặt và biến thể. Dưới đây là một vài ví dụ:

Adaboost algorithm

Cho tập dữ liệu được gán nhãn S=((x_1, y_1), ..., (x_m, y_m)), trong đó (x_i, y_i) \in X \times \{-1, +1\}, \forall i \in \lbrack 1, m \rbrack. Phân phối (distribution) vòng lặp thứ t \in \lbrack 1, T \rbrack là D_t với D_1 là phân phối đều. Và base classifier h_t \in H được chọn để minimize độ lỗi trên tập huấn luyện được tính lại trọng số (re-weighted) như sau:

h_t \in argmin_{h \in H} Pr_{i \sim D_t} \lbrack h_t(x_i) \ne y_i \rbrack = argmin_{h \in H} \Sigma_{i = 1}^m D_t(i) 1_{h(x_i) \ne y_i}

Z_t là thừa số để chuẩn hoá sao cho tổng các trọng số trên phân phối D_{t+1}(i) bằng 1.

ADABOOST(S=((x_1, y_1), ..., (x_m, y_m)))
 for i \leftarrow 1 to m do
  D_1 (i) \leftarrow \frac{1}{m}
 for t \leftarrow 1 to T do
  h_t \leftarrow  base classifier in H with small error \epsilon_t =Pr_{i \sim D_t}\lbrack h_t(x_i) \ne y_i \rbrack
  \alpha_t \leftarrow \frac{1}{2} log \frac{1 - \epsilon_t}{\epsilon_n}
  Z_t \leftarrow 2\lbrack \epsilon_t(1 - \epsilon_t) \rbrack^\frac{1}{2}
  for i \leftarrow 1 to m do
   D_{t+1}(i) \leftarrow \frac{D_t(i) exp(-\alpha_t y_i h_t(x_i))}{Z_t}
 g \leftarrow \Sigma_{t=1}^T \alpha_t h_t
 return h = sgn(g)

Nguồn tham khảo: 

Advertisement

Đăng bởi Hong Ong

I'm passionate about applying state-of-the-art Big Data architectures and Machine Learning methods for solving challenging problems related to Digital marketing, Fin-tech, Digital transformation in F&B, Retailer, and Engineering. I'm working as Machine Learning Engineer for more than 7 years in the field of AI, Machine Learning and Big Data using new technologies, optimized DataOps, and MLOps so that the Data Products roll out in an efficient way on cloud data platform. I hope my skills and experiences could share addition to the Data science community.

Đã đăng

Một suy nghĩ 7 thoughts on “AdaBoost hỏi gì đáp nấy”

  1. Em chào anh,
    Adaboost là một thuật toán riêng biệt với J4.8 hay là một hiệu ứng thêm vào sau khi mình thực hiện J4.8 ạ?
    Nếu thực hiện trên weka thì em sẽ thực hiện adaboost thế nào ạ?
    Em cám ơn anh nhiều.

    Thích

    Trả lời

    1. anh vừa cập nhật thêm thuật toán Adaboost. Việc phát sinh cây diễn ra bình thường, chỉ có điều các điểm dữ liệu đã được cập nhật lại trọng số nên mỗi lần lặp sẽ cho ra các cây khác nhau, mỗi cây này khi hợp lại sẽ cố gắng tối tiểu hoá độ lỗi huấn luyện.

      Thích

      Trả lời
  3. Pingback: XGBoost: thuật toán giành chiến thắng tại nhiều cuộc thi Kaggle – Ông Xuân Hồng
  4. Pingback: XGBoost: thuật toán giành chiến thắng tại nhiều cuộc thi Kaggle - Movan.vn

Trả lời

Điền thông tin vào ô dưới đây hoặc nhấn vào một biểu tượng để đăng nhập:

Gravatar
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 )

Hủy bỏ

Connecting to %s