XGBoost: thuật toán giành chiến thắng tại nhiều cuộc thi Kaggle

XGBoost là viết tắt của Extreme Gradient Boosting. Đây là thuật toán state-of-the-art nhằm giải quyết bài toán supervised learning cho độ chính xác khá cao bên cạnh mô hình Deep learning như chúng ta từng tìm hiểu.

Nếu Deep learning chỉ nhận đầu vào là raw data dạng numerical (ta thường phải chuyển đổi sang n-vector trong không gian số thực) thì XGBoost nhận đầu vào là tabular datasets với mọi kích thước và dạng dữ liệu bao gồm cả categorical mà dạng dữ liệu này thường được tìm thấy nhiều hơn trong business model, đây là lý do đầu tiên tại sao các cá nhân tham gia Kaggle thường sử dụng.

Bên cạnh đó, XGboost có tốc độ huấn luyện nhanh, có khả năng scale để tính toán song song trên nhiều server, có thể tăng tốc bằng cách sử dụng GPU, nhờ vậy mà Big Data không phải là vấn đề của mô hình này. Vì thế, XGBoost thường được sử dụng và đã giành được nhiều chiến thắng trong các cuộc thi tại Kaggle.

Phát biểu bài toán

là biến ngẫu nhiên “output” hay “response”.

là biến ngẫu nhiên “input” hay “explanatory”.

là mẫu dữ liệu “training”.

là hàm mục tiêu ánh xạ sang .

là loss function:

• Squared-error: .
• Absolute error: (regression).
• Negative binomial log-likelihood: (classification).

Mục tiêu của chúng ta tìm được hàm mục tiêu sao cho cực tiểu hoá kỳ vọng của hàm lỗi.

Tối ưu trong không gian tham số

Trong không gian tham số, thuộc lớp hàm là tập hữu hạn các tham số khi đó dạng “additive” của lớp hàm này sẽ là:

.

Bạn có thể thấy dạng biểu diễn này rất giống với ý tưởng của AdaBoost. Ta có thể hình dung là một regression tree thứ trong số tree build được từ dạng “addictive” này. Cụ thể, trong thuật toán học CART (Breiman, Friedman, Olshen, Stone 1983), là splitting variables, split locations, terminal node của từng cây. chính là trọng số tương ứng đối với mỗi cây.

Để chọn được tham số cho mô hình ta đi tính sao cho:

trong đó,

khi đó,

Để giải người ta thường biểu diễn tham số này dưới dạng sau:

trong đó, là tham số khởi tạo và là successive increments (“steps” hay “boosts”). Nghĩa là, mỗi tham số hiện tại sẽ được tính dựa vào kết quả của chuỗi tham số tính được trước đó. Ta có thể thấy mô hình này tương tự như Random Forest điểm khác biết duy nhất nằm ở chỗ training model như thế nào. Cũng như tất cả các thuật toán classification, ta sẽ định nghĩa hàm loss và đi optimize hàm này.

Lúc này, ta có thể sử dụng Steepest-descent để cực tiểu hoá bài toán tìm tham số này. Đầu tiên, ta sẽ tính gradient như sau:

trong đó,

.

Mỗi step được tính theo công thức:

trong đó,

.

Dấu trừ trước gradient cho biết đây là hướng “steepest-descent” mà thuật toán đang hướng tới để tìm điểm cực tiểu cục bộ.

Tối ưu trong không gian hàm số

Ở đây, ta áp dụng hướng tiếp cận “non-parametric” với phép tối tiểu hoá Steepest-descent cho không gian hàm số thay vì trong không gian tham số. Ta xem là “parameter” cần tìm để cực tiểu hoá:

,

tương đương với,

Với tập dữ liệu hữu hạn hàm cần tìm sẽ là:

trong đó, là hàm khởi tạo, và là incremental functions (“steps” hay “boosts”) được định nghĩa tại mỗi bước steepest-descent như sau:

với,

và,

.

Như vậy, sẽ là:

Trong thực nghiệm, ta sẽ chọn là learning rate tại bước boosting thứ .

Trước khi đi tiếp vào Gradient boosting, ta sẽ recap lại một chút phương pháp Boosting và Gradient descent để xem chúng được kết hợp như thế nào.

Boosting là gì?

Ý tưởng: thay vì xây dựng một mô hình dự đoán (chẳng hạn descision tree) có độ chính xác tương đối, ta đi xây dựng nhiều mô hình dự đoán có độ chính xác kém hơn (weak learner) khi đi riêng lẻ nhưng lại cho độ chính xác cao khi kết hợp lại.

Ta có thể hình dung mỗi weak learner gồm học sinh yếu, khá, giỏi và thầy giáo. Trong đó, trọng số uy tín về kiến thức của thầy giáo sẽ là cao nhất và học sinh yếu sẽ là thấp nhất. Khi bạn đặt câu hỏi nào đó và cần những người này đưa ra kết luận, nếu nhiều người cùng có chung kết luận hoặc uy tín của những người đưa ra kết luận cao hơn tập thể thì ta có thể tin kết luận này là đúng.

Ví dụ trong thuật toán AdaBoost, mỗi lần huấn luyện weak learner, mô hình sẽ tính lại trọng số cho các điểm dữ liệu đã bị phân lớp sai, để những lượt huấn luyện tiếp theo những điểm dữ liệu này sẽ có cơ hội nhiều hơn được phân lớp đúng. Dưới đây là mô hình dự đoán tổng quát:

Gradient descent là gì?

Mục tiêu: tìm vector các tham số sao cho tối ưu hoá hàm mục tiêu cụ thể nào đó:

Phương pháp Gradient descent:

• Gradient:
• Parameters:
• Learning rate:
• Target parameters:

Như vậy, kết quả của gradient descent là weighted combination của các gradient.

Kết hợp hai hướng tiếp cận

Như vậy, mục tiêu của chúng ta là đi xây dựng additive model:

Nhưng sẽ rất khó nếu ta huấn luyện trực tiếp để tìm tập parameters trong không gian tham số:

Vì vậy, ta sẽ dùng greedy-stagewise trong không gian hàm số để giải:

khi đó,

Thuật toán Gradient boosting tổng quát

Thuật toán này nhằm xấp xỉ gradient thông qua một hàm tham số hoá . Tại mỗi vòng lặp: ta tính gradient . Ta xem là tập training để huấn luyện hàm . Từ đó, ta có thể dự đoán từ .

Gradient_Boost()
 
 For m = 1 to M do:
  # gradient step
  
  
  
  # boosting step
  
  
 endFor
endAlgorithm

Như vậy, vừa là gradient của function space vừa là label của parameter space. là leanring rate để tìm tham số và là learning rate để boosting additive model .

Từ thuật toán cơ sở này, ta có thể mở rộng cho các mô hình khác thông qua loss function được định nghĩa trước.

Ứng dụng additive modeling trên các loss function khác nhau

Gradient boosting: Least-squares loss

Least-squares loss: . Lấy đạo hàm, ta được .  Ngoài ra, ta có khi thế đạo hàm vào thuật toán tổng quát. Khi đó, ta có:

LS_Boost()
 
 For m = 1 to M do:
  
  
  
 endFor
endAlgorithm

Gradient boosting: Least-absolute-deviation loss

Least-absolute-deviation loss: . Lấy đạo hàm, ta được . Khi đó:

.

Base learner: . Trong đó, là regression tree với J-terminal node, là disjoint regions, là hệ số cho từng quyết định. Nếu thì .

Như vậy gradient sẽ là: .

Hàm boosting sẽ là: . Trong đó, .

LAD_TreeBoost()
 
 For m = 1 to M do:
  
   terminal node 
  
  
 endFor
endAlgorithm

Gradient boosting: Binary classification

Negative binomial log-likelihood: . Lấy đạo hàm, ta được .

Line search sẽ là: .

Đối với base learner, được xấp xỉ thành dạng như bên dưới theo Newton-Raphson step.

.

_TreeBoost
 
 For m = 1 to M do:
  
   terminal node 
  
  
 endFor
endAlgorithm

Gradient boosting: regularization để tránh overfitting

Các tham số cần regularize: số lượng model M, độ phức tạp tính toán của từng model.

Sử dụng learning rate có giá trị nhỏ hơn 1:

Subsampling:

• Subsampling tập huấn luyện tại mỗi vòng lặp.
• Subsampling tập feature tại mỗi vòng lặp.
• Đối với tree-based learners, subsampling tập feature tại mỗi level của cây.

XGBoost

Đặt:

• : số lượng mẫu huấn luyện.
• : số lượng features.
• là tập dữ liệu với .
• : cấu trúc của một cây, ánh xạ mẫu dữ liệu vào nút lá tương ứng.
• : số lượng nút lá trên cây.
• : cấu trúc các cây độc lập của mô hình.
• : trọng số của nút lá thứ .
• : giá trị dự đoán của instance thứ tại vòng lặp thứ .
• : đạo hàm bậc 2 của hàm .
• : tập các giá trị tại nút lá
• : tập giá trị nút lá bên trái.
• : tập giá trị nút lá bên phải.
• .

Mô hình học:

. Trong đó, .

Hàm học:

. Trong đó,

Tiến trình học:

với, và .

.

Trọng số tối ưu tại mỗi nút lá:

Hàm lỗi tính trên toàn bộ cây:

Điều kiện rẽ nhánh:

XGBoost và Gradient boosting đều dựa trên cùng ý tưởng đó là boosting thông qua gradient descent trong không gian hàm số. Tuy nhiên, điều làm nên hiệu suất ấn tượng và khả năng tính toán của XGBoost nằm ở ba yếu tố:

• Engineering để tránh overfitting như: sub-sampling row, column, column per split levels, áp dụng regularized L1 và L2.
• Khả năng tận dụng tài nguyên hệ thống: tính toán song song trên CPU/GPU, tính toán phân tán trên nhiều server, tính toán khi tài nguyên bị giới hạn, cache optimization để tăng tốc training.
• Và cuối cùng là khả năng xử lý missing data value, tiếp tục training bằng mô hình đã được build trước đó để tiết kiệm thời gian.

Cuối cùng, tôi xin khép lại bài viết bằng câu phát biểu của Tianqi Chen (người sáng chế ra thuật toán XGBoost) giải thích tại sao mọi người đang sử dụng thuật toán này khá phổ biến.

The name xgboost, though, actually refers to the engineering goal to push the limit of computations resources for boosted tree algorithms. Which is the reason why many people use xgboost.

– Tianqi Chen, on Quora.com

Chương trình minh hoạ

from numpy import loadtxt 
from xgboost import XGBClassifier 
from sklearn.model_selection import train_test_split 
from sklearn.metrics import accuracy_score
from sklearn.datasets import load_breast_cancer

# load data
dataset = load_breast_cancer(return_X_y=True)

# split data into X and y 
X = dataset[0] 
Y = dataset[1]

# tvt split
seed = 7 
test_size = 0.33 
X_train, X_test, y_train, y_test = train_test_split(X, Y, test_size=test_size, random_state=seed)
eval_set = [(X_train, y_train), (X_test, y_test)]

# fit model no training data 
model = XGBClassifier() 
model.fit(X_train, y_train, eval_metric="auc", eval_set=eval_set, verbose=True)

print(model)

# make predictions for test data 
y_pred = model.predict(X_test) 
predictions = [round(value) for value in y_pred]

# evaluate predictions 
accuracy = accuracy_score(y_test, predictions) 
print("Accuracy: %.2f%%" % (accuracy * 100.0))

# tree plot
from xgboost import plot_tree
import matplotlib.pyplot as plt

plt.figure(figsize=(19, 5))
plot_tree(model)
plt.show()

# feature important plot
plt.bar(range(len(model.feature_importances_)), model.feature_importances_)
plt.show()

# default plot
from xgboost import plot_importance
plot_importance(model)
plt.show()

# evaluation plot
# retrieve performance metrics 
results = model.evals_result()
epochs = len(results['validation_0' ]['auc'])
x_axis = range(0, epochs)

fig, ax = plt.subplots()
ax.plot(x_axis, results['validation_0']['auc'], label='Train')
ax.plot(x_axis, results['validation_1']['auc'], label='Test')
ax.legend()
plt.ylabel('AUC')
plt.title('XGBoost AUC')
plt.show()

Nguồn tham khảo

• Greedy Function Approximation: A Gradient Boosting Machine
• Boosting algorithms as a gradient descent in function space
• Stochastic gradient boosting
• Xgboost: A Scalabale Tree Boosting System
• Xgboost with Python
• DataCamp: Extreme Gradient Boosting with XGBoost
• Gradient Boosting explained [demonstration]
• Unveiling Mathematics Behind XGBoost

 

Advertisement