12.1. AdaBoosting¶

Giả định rằng bài toán phân loại nhị phân với biến mục tiêu gồm hai nhãn \(y \in \{-1, 1\}\). Giả định theo phương pháp tăng cường thì hàm dự báo đối với một biến đầu vào \(\mathbf{x}_i\) là \(\hat{f}(\mathbf{x_i}) \in \{-1, 1 \}\). Đồng thời biến mục tiêu \(\mathbf{y}\) nhận một trong hai giá trị \(\{-1, 1\}\). Khi đó sai số trên tập huấn luyện là:

\[r = \frac{1}{N}\sum_{i=1}^{N} \mathbf{1}(y_i \neq \hat{f}(\mathbf{x}_i))\]

Trong đó hàm \(\mathbf{1}(.)\) là một hàm logic nhận giá trị 1 nếu như điều kiện bên trong hàm trả về là đúng, trái lại thì nhận giá trị 0.

Một mô hình phân loại yếu (weak classifier) có tỷ lệ dự báo sai lớn và giả định nó chỉ tốt hơn so với phân loại ngẫu nhiên một chút. Mục tiêu của phương pháp tăng cường là áp dụng liên tiếp các mô hình phân loại yếu để điều chỉnh lại trọng số cho các quan sát, qua đó ở mô hình sau sẽ ưu tiên phân loại đúng những quan sát đã phân loại sai từ mô hình trước đó. Kết thúc ta thu được một mô hình dự báo được kết hợp từ các mô hình phân loại yếu trong chuỗi. Mô hình kết hợp này thường có hiệu suất cao.

Hình 1: Sơ đồ của mô hình AdaBoosting. Mỗi một mô hình con được huấn luyện từ bộ dữ liệu được đánh trọng số theo tính toán từ mô hình tiền nhiệm. Dữ liệu có trọng số sau đó được đưa vào huấn luyện mô hình tiếp theo. Đồng thời ta cũng tính ra một trọng số quyết định \(\alpha_p\) thể hiện vai trò của mỗi mô hình ở từng bước huấn luyện. Cứ tiếp tục như vậy cho tới khi số lượng mô hình đạt ngưỡng hoặc tập huấn luyện hoàn toàn được phân loại đúng thì dừng quá trình.

Kết quả dự báo từ mô hình cuối cùng là một kết hợp từ những mô hình với trọng số \(\alpha_i\):

\[\hat{f}(\mathbf{x}) = \text{sign} (\sum_{i=1}^{p} \alpha_i \hat{f}^{i}(\mathbf{x}))\]

Trong phương trình trên hàm \(\text{sign}(x)\) là hàm nhận giá trị \(1\) nếu dấu của \(x\) là dương và nhận giá trị \(-1\) nếu ngược lại.

Các hệ số \(\alpha_i\) được tính từ phương pháp tăng cường, chúng được sử dụng để đánh trọng số mức độ đóng góp từ mỗi một mô hình con \(\hat{f}^{i}\) trong chuỗi nhằm phân bổ vai trò quyết định trên từng mô hình khác nhau tuỳ thuộc vào mức độ chính xác của chúng. Điều này được phân tích kĩ hơn bên dưới.

Khi huấn luyện một mô hình con \(\hat{f}^{i}\) thì chúng ta áp dụng một trọng số \(w_j\) lên từng quan sát \((\mathbf{x}_j, y_j)\) sao cho đối với những quan sát bị dự báo sai thì trọng số của nó sẽ lớn hơn. Như vậy ở mô hình tiếp theo sẽ ưu tiên dự báo đúng những quan sát này hơn so với những quan sát đã được dự báo đúng. Ở thời điểm khởi đầu thì chúng ta gán \(w_j = \frac{1}{N}, ~~ \forall i = \overline{1, N}\).

12.1.1. Các bước của thuật toán AdaBoosting¶

1.- Khởi tạo trọng số quan sát \(w_i = \frac{1}{N}, \forall i = \overline{1, N}\).

2.- Lặp lại quá trình huấn luyện chuỗi mô hình ở mỗi bước \(b\), \(b = 1,2, \dots, B\) gồm các bước con:

a. Khớp mô hình \(\hat{f}^{b}\) cho tập huấn luyện sử dụng trọng số \(w_i\) cho mỗi quan sát \((\mathbf{x}_i, y_i)\).

b. Tính sai số huấn luyện:

\[r_b = \frac{\sum_{i=1}^{N} w_i \mathbf{1}(y_i \neq \hat{f}^{b}(\mathbf{x}_i))}{\sum_{i=1}^{N} w_i}\]

Ở đây \(\mathbf{1}(y_i \neq \hat{f}^{b}(\mathbf{x}_i))\) chính là những quan sát bị dự báo sai ở mô hình thứ \(b\). Giá trị \(r_b \in [0, 1]\).

c. Tính trọng số quyết định cho từng mô hình:

\[\alpha_b = \log(\frac{(1-r_b)}{r_b})\]

d. Cập nhật trọng số cho từng quan sát:

\[ w_i := w_i \exp[\alpha_b \mathbf{1}(y_i \neq \hat{f}^{b}(\mathbf{x}_i))] \]

với \(\forall i = \overline{1, N}\). Như vậy ta có thể nhận thấy rằng:

\[\begin{split} \begin{split} w_i := \left\{ \begin{matrix} w_i &\text{ if } y_i = \hat{f}^{b}(\mathbf{x}_i) \\ w_i \exp(\alpha_b) &\text{ if } y_i \neq \hat{f}^{b}(\mathbf{x}_i) \end{matrix} \right.\end{split} \end{split}\]

Sau khi tính xong các trọng số \(w_i\) thì giá trị của chúng sẽ được chuẩn hoá bằng cách chia cho tổng \(\sum_{i=1}^{N} w_i\).

3.- Cập nhật dự báo cuối cùng:

\[\hat{f}(\mathbf{x}) = \text{sign} (\sum_{i=1}^{p} \alpha_i \hat{f}^{i}(\mathbf{x})) \tag{1}\]

Trọng số \(\alpha_i\) được tính ở bước thứ 2 thể hiện vai trò quan trọng trong việc ra quyết định của mô hình thứ \(i\). Giá trị này được tính theo một hàm nghịch biến với sai số của mô hình. Chúng ta cùng phân tích hàm này bên dưới:

import numpy as np
import matplotlib.pyplot as plt

plt.figure(figsize = (9, 6))
r = np.linspace(0.01, 0.99, 100)

def alpha(z):
  return np.log((1-z)/z)

y = alpha(r)
plt.plot(r, y)
plt.xlabel(r'error rate $r_b$', fontsize=16)
plt.ylabel(r'$\alpha_b$', fontsize=16)
plt.axvline(0.5, linestyle='--')
plt.axhline(0, linestyle='--')
plt.title(r'$\alpha_b$ vs error rate', fontsize=16)
plt.show()

Hình 2: Giá trị của trọng số quyết định \(\alpha_b\) theo sai số \(r_b\). Đây là một hàm nghịch biến theo \(r_b\) và có giá trị từ \((-\infty, + \infty)\)

Bên dưới ta sẽ xét 3 trường hợp đối với sai số dự báo \(r_b\):

Khi \(r_b = 0.5\) tương ứng với kết quả từ một mô hình dự báo ngẫu nhiên. Trường hợp này có \(\alpha_b = 0\). Khi đó mô hình không có đóng góp gì vào hàm dự báo được thể hiện ở công thức \((1)\). Điều này là hợp lý vì một giá trị dự báo ngẫu nhiên thì không có ích cho việc phân loại. Đồng thời trọng số sau cập nhật \(w_i \exp(\alpha_b) = w_i\), tức là vai trò của các quan sát được giữ cố định.
Khi \(r_b\) tiến dần tới \(0\), chẳng hạn \(r_b = 0.1\), tương ứng với mô hình dự báo có tỷ lệ sai số thấp và đây là một mô hình khá mạnh. Khi đó \(\alpha_b = \log \frac{1-0.1}{0.1} = \log{9} = 2.197\) và \(\exp(\alpha_b) = 9\). Như vậy đối với những quan sát bị dự báo sai thì trọng số của nó được gấp lên 9 lần, điều này giúp cho những mô hình sau sẽ điều chỉnh lại cây quyết định sao cho tập trung vào dự báo đúng những quan sát này. Đồng thời \(\alpha_b \hat{f}^{b}(\mathbf{x}) = 2.197~\hat{f}^{b}(\mathbf{x})\) cho thấy các dự báo từ mô hình này được đánh giá rất cao và góp phần gia tăng điểm số dự báo cuối cùng theo như công thức \((1)\).
Khi \(r_b\) tiến dần tới \(1\), chẳng hạn \(r_b = 0.9\) cho thấy đây là một mô hình rất yếu vì có tỷ lệ sai số dự báo cao. Khi đó \(\alpha_b = \log \frac{1-0.9}{0.9} = \log \frac{1}{9} = -2.197\) là một giá trị âm tương đối nhỏ và \(\exp(\alpha_b) = \frac{1}{9}\) là một giá trị gần 0. Như vậy trọng số \(w_i \exp(\alpha_b)\) sẽ bị giảm gấp 9 lần so với \(w_i\). Lưu ý rằng trong trường hợp này mô hình đang dự báo hầu hết là sai nên nếu mô hình dự báo sai thì dường như những quan sát đó lại dễ được dự báo đúng và ít quan trọng. Điều này cũng giống như một người dự báo sai tới 90% thì khả năng ta lấy kết quả ngược lại của anh ta sẽ được mô hình dự báo đúng 90% và những trường hợp anh ta dự báo sai thường dễ dàng được phân loại đúng nhờ làm ngược lại. Do đó ta cần giảm trọng số \(w_i\) cho những quan sát mà mô hình dự báo sai, trong trường hợp này là giảm đi 9 lần. Đồng thời đóng góp từ kết quả dự báo vào mô hình là \(\alpha_b \hat{f}^{b}(\mathbf{x}) = -2.197~\hat{f}^{b}(\mathbf{x})\) cho thấy kết quả từ mô hình này sẽ được cập nhật ngược chiều vào điểm số cuối cùng. Điều này cũng giống như chúng ta làm ngược lại gợi ý của một người hay phán đoán sai để thu được phán đoán đúng.

Quá trình tăng cường mô hình sẽ tiếp tục như vậy cho đến khi mô hình đạt số lượng tối đa hoặc toàn bộ các quan sát trên tập kiểm tra được phân loại đúng. Một lưu ý đó là các mô hình cây quyết định con trong phương pháp tăng cường thường có độ sâu thấp, thông thường chỉ gồm 1 node gốc với hai node lá, trường hợp cây quyết định chỉ gồm một node gốc được gọi là mô hình gốc cây (stump). Sở dĩ chúng ta không cần yêu cầu các cây quyết định phải quá phức tạp là để ngăn ngừa hiện tượng quá khớp có thể xảy ra và đồng thời tăng khả năng giải thích cho mô hình.

Bên dưới chúng ta sẽ thực hành huấn luyện mô hình AdaBoosting trên sklearn.

12.1.2. Huấn luyện AdaBoosting trên sklearn¶

Trên sklearn thực tế đang sử dụng phiên bản dự báo đa lớp đối với thuật toán AdaBoost, được gọi là SAMME(là viết tắt của Stagewise Additive Modeling using a Multiclass Exponential loss function). Khi chỉ có hai lớp, SAMME tương đương với AdaBoost. Ngoài ra, để mô hình có thể ước lượng được xác suất của lớp (tức là có hàm predict_proba()), thì sklearn có thể sử dụng một biến thể của SAMME được gọi là SAMME.R (chữ R là viết tắt của với “Real”), dựa trên xác suất hơn là giá trị nhãn dự báo và nhìn chung chúng hoạt động tốt hơn. Đoạn mã sau giúp huấn luyện một mô hình AdaBoost dựa trên 200 mô hình gốc cây (stump) bằng cách sử dụng class AdaBoostClassifier của sklearn. Mô hình gốc cây thì có max_depth = 1 hay nói cách khác, đây là cây quyết định bao gồm một node quyết định duy nhất cộng với với hai node lá. Đây cũng chính là cấu hình mặc định cho class AdaBoostClassifier:

from sklearn.ensemble import AdaBoostClassifier
from sklearn.tree import DecisionTreeClassifier
from sklearn.datasets import load_iris
import numpy as np

# Load the dataset 
iris = load_iris()
X = iris.data
y = iris.target == 1

# Train/test split
idx = np.arange(X.shape[0])
np.random.seed(0)
np.random.shuffle(idx)

idx_train = idx[:100]
idx_test = idx[100:]

X_train, y_train = X[idx_train, :], y[idx_train]
X_test, y_test = X[idx_test, :], y[idx_test]

# Train model
ada_clf = AdaBoostClassifier(
  DecisionTreeClassifier(max_depth=1), n_estimators=20,
  algorithm="SAMME.R", learning_rate=0.5
)

ada_clf.fit(X_train, y_train)

# Evaluate model on train and test
y_pred_train = ada_clf.predict(X_train)
print('accuracy on train: ', np.sum((y_pred_train==y_train))/len(y_train))

y_pred_test = ada_clf.predict(X_test)
print('accuracy on test: ', np.sum((y_pred_test==y_test))/len(y_test))

accuracy on train:  1.0
accuracy on test:  0.96

Như vậy kết quả của mô hình đạt độ chính xác trên tập huấn luyện là 100% và tập kiểm tra là 96%. Kết quả này cao hơn so với mô hình được huấn luyện từ thuật toán rừng cây.

Deep AI KhanhBlog

12.1. AdaBoosting¶

12.1.1. Các bước của thuật toán AdaBoosting¶

12.1.2. Huấn luyện AdaBoosting trên sklearn¶

12.2. Gradient Boosting¶

12.2.1. Các bước của thuật toán Gradient Boosting¶

12.2.2 Huấn luyện Gradient Boosting trên sklearn¶

12.3. Tổng kết¶

12.4. Bài tập¶

12.5. Tài liệu tham khảo¶