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

0356.000.123

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

xgboost_illustrate

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

y

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

\mathbf{x} = \{x_1, ..., x_n\}

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

\{y_i, \mathbf{x}_i\}

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

F^*(\mathbf{x})
\mathbf{x}
y

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

L(y, F(\mathbf{x}))

 là loss function:

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

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.

F^* = argmin_F E_{y, \mathbf{x}} L(y, F(\mathbf{x})) = argmin_F E_\mathbf{x} \lbrack E_y(L(y, F(\mathbf{x}))) | \mathbf{x} \rbrack

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

AdaBoost
F(\mathbf{x})
F(\mathbf{x}; \mathbf{P}), \mathbf{P} = \{P_1, P_2, ...\}

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à:

F(\mathbf{x}; \{\beta_m, \mathbf{a}_m\}_1^M) = \Sigma_{m=1}^M \beta_m h(\mathbf{x}; \mathbf{a}_m)

.

h(\mathbf{x}; \mathbf{a}_m)
m
M
\mathbf{a}_m
\beta_m

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.

F(\mathbf{x};\mathbf{P})
\mathbf{P^*}

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

\mathbf{P^*} = argmin_\mathbf{P} \Phi(\mathbf{P})

trong đó,

\Phi(\mathbf{P}) = E_{y, \mathbf{x}} L(y, F(\mathbf{x};\mathbf{P}))

khi đó,

F^*(\mathbf{x}) = F(\mathbf{x};\mathbf{P^*})
\mathbf{P^*}

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

\mathbf{P^*} = \Sigma_{m=0} \mathbf{p}_m
\mathbf{p}_0
\{\mathbf{p}_m\}_1^M

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.

\mathbf{g}_m

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:

\mathbf{g}_m = \{g_{jm}\} = \{\lbrack \frac{\partial \Phi(\mathbf{P})}{\partial P_j} \rbrack_{\mathbf{P} = \mathbf{P}_{m-1}}\}

trong đó,

\mathbf{P}_{m-1} = \Sigma_{i=0}^{m-1} \mathbf{p}_i

.

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

\mathbf{p}_m = -\rho_m \mathbf{g}_m

trong đó,

\rho_m = argmin_\rho \Phi(\mathbf{P}_{m-1} - \rho \mathbf{g}_m)

.

-\mathbf{g}_m

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ố

gradient-descent
F(\mathbf{x})

Ở đâ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á:

\Phi(F) = E_{y, \mathbf{x}} L(y, F(\mathbf{x})) = E_\mathbf{x}\lbrack E_y(L(y, F(\mathbf{x}))) | \mathbf{x}\rbrack

,

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

\phi(F(\mathbf{x})) = E_y\lbrack L(y, F(\mathbf{x})) |\mathbf{x}\rbrack
\{F(\mathbf{x}_i)\}_1^N

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

F^*(\mathbf{x}) = \Sigma_{m=0}^M f_m(\mathbf{x})
f_0(\mathbf{x})
\{f_m(\mathbf{x})\}_1^M

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:

f_m(\mathbf{x}) = -\rho_m g_m(\mathbf{x})

với,

g_m(\mathbf{x}) = \lbrack \frac{\partial \Phi(F(\mathbf{x}))}{\partial F(\mathbf{x})} \rbrack_{F(\mathbf{x}) = F_{m-1}(\mathbf{x})} = \lbrack \frac{\partial E_y\lbrack L(y, F(\mathbf{x})) |\mathbf{x}\rbrack}{\partial F(\mathbf{x})}  \rbrack_{F(\mathbf{x}) = F_{m-1}(\mathbf{x})}

và,

F_{m-1}(\mathbf{x}) = \Sigma_{i=0}^{m-1} f_i(\mathbf{x})

.

\rho_m

Như vậy,  sẽ là:

\rho_m = argmin_\rho E_{y,\mathbf{x}} L(y, F_{m-1}(\mathbf{x}) - \rho g_m(\mathbf{x}))
\rho_m
m

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:

H(\mathbf{x}) = sign(\alpha_1 h_1(\mathbf{x}) + \alpha_2 h_2(\mathbf{x}) + ... + \alpha_k h_k(\mathbf{x}))

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 đó:

\mathbf{P^*} = argmin_\mathbf{P} \Phi(\mathbf{P})

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:

F(\mathbf{x};\{\beta_m, \mathbf{a}_m\}_1^M = \Sigma_{m=1}^M \beta_m h(x; \mathbf{a}_m))

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ố:

\{\beta_m, \mathbf{a}_m\}_1^M = argmin_{\{\beta_m', \mathbf{a}_m'\}}\Sigma_{i=1}^N L (y_i, \Sigma_{m=1}^M \beta_m' h(\mathbf{x}_i, \mathbf{a}_m'))

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

(\beta_m, \mathbf{a}_m) = argmin_{\beta, a} \Sigma_{i=1}^N L(y_i, F_{m-1}(\mathbf{x}_i) + \beta h(\mathbf{x}_i;a))

khi đó,

F_m(\mathbf{x}) = F_{m-1}(\mathbf{x}) + \beta_m h(\mathbf{x};\mathbf{a}_m)

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

h(\mathbf{x}; \mathbf{a}_m)
\tilde{y}_m
\{-\tilde{y}_i, \mathbf{x}_i\}_1^N
h(\mathbf{x}; \mathbf{a}_m)
-\tilde{y}_m
\mathbf{x}

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
\tilde{y}_i
\beta
\mathbf{a}_m
\rho_m
F_m(\mathbf{x})

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

L(y,F) = \frac{(y-F)^2}{2}
\bar{y}_i = y_i - F_{m-1}(\mathbf{x}_i)
\rho_m = \beta_m

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

L(y,F) = |y - F|
sign(y_i - F_{m-1}(\mathbf{x}_i))

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

\rho_m = argmin_\rho \Sigma_{i=1}^N |y_i - F_{m-1}(\mathbf{x}_i) - \rho h(\mathbf{x}_i; \mathbf{a}_m)|
\rho_m = argmin_\rho \Sigma_{i=1}^N |h(\mathbf{x}_i; \mathbf{a}_m)| \cdot |\frac{y_i - F_{m-1}(\mathbf{x}_i)}{h(\mathbf{x}_i; \mathbf{a}_m)} - \rho|
\rho_m = median_w \{\frac{y_i - F_{m-1}(\mathbf{x}_i)}{h(\mathbf{x}_i; \mathbf{a}_m)}\}_1^N, w_i = |h(\mathbf{x}_i; \mathbf{a}_m)|



.

h(\mathbf{x}; \{b_j, R_j\}) = \Sigma_{j=1}^J b_j\mathbf{1}(\mathbf{x} \in R_j)
R_j
\{R_j\}_1^J
\{b_j\}_1^J
\mathbf{x} \in R_j
h(\mathbf{x}) = b_j

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ì .

b_{jm} = ave_{x_i \in R_{jm}} \tilde{y_i}

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

F_m(\mathbf{x}) = F_{m-1}(\mathbf{x}) + \Sigma_{j=1}^J \gamma_{jm}\mathbf{1} (\mathbf{x} \in R_{jm})
\gamma_{jm} = \rho_m b_{jm}

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

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

Gradient boosting: Binary classification

L(y,F) = log\lbrack 1+exp(-2yF)\rbrack, y = \{-1,1\}
2y_i/(1 + exp(2y_iF_{m-1}(\mathbf{x}_i)))

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

\rho_m = argmin_\rho \Sigma_{i=1}^N log(1 + exp(-2y_i(F_{m-1}(\mathbf{x}_i) + \rho h(\mathbf{x}_i; \mathbf{a}_m))))

Line search sẽ là: .

\gamma_{jm} = argmin_\gamma \Sigma_{\mathbf{x}_j \in R_{jm}} log(1 + exp(-2y_i(F_{m-1}(\mathbf{x}_i) + \gamma)))

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

\gamma_{jm} = \Sigma_{\mathbf{x}_j \in R_{jm}} \tilde{y}_i / \Sigma_{\mathbf{x}_j \in R_{jm}} |\tilde{y}_i| (2 - |\tilde{y}_i|)

.

_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.

F_m(\mathbf{x}) = F_{m-1}(\mathbf{x}) + \nu \cdot \rho_m h(\mathbf{x}; \mathbf{a}_m), 0 < \nu \le 1

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

gradient_boosting_explained

Đặ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:

\hat{y}_i = \phi(\mathbf{x}_i) = \Sigma_{k=1}^K f_k(\mathbf{x}_i), f_k \in \mathcal{F}
\mathcal{F} = \{f(\mathbf{x}) = w_{q(\mathbf{x})}\} (q : \mathbb{R}^m) \rightarrow T, w \in \mathbb{R}^T

. Trong đó, .

Hàm học:

\mathcal{L}(\phi) = \Sigma_i l(\hat{y}_i, y_i) + \Sigma_k \Omega(f_k)
\Omega(f) = \gamma T + \frac{1}{2} \lambda ||w||^2

. Trong đó, 

Tiến trình học:

\mathcal{L}^{(t)} = \Sigma_{i=1}^n l(y_i, \hat{y}_i^{(t-1)} + f_t(\mathbf{x}_i)) + \Omega(f_t)
\mathcal{L}^{(t)} \sim \Sigma_{i=1}^n \lbrack l(y_i, \hat{y}^{(t-1)}) + g_i f_t(\mathbf{x}_i) + \frac{1}{2} h_i f_t^2(\mathbf{x}_i) \rbrack + \Omega(f_t)
g_i = \partial_{\hat{y}^{(t-1)}} l(y_i, \hat{y}^{(t-1)})
h_i = \partial_{\hat{y}^{(t-1)}}^2 l(y_i, \hat{y}^{(t-1)})

với,  và .

\mathcal{L}^{(t)} = \Sigma_{i=1}^n \lbrack g_i f_t(\mathbf{x}_i) + \frac{1}{2} h_i f_t^2(\mathbf{x}_i) \rbrack + \gamma T + \frac{1}{2} \lambda \Sigma_{j=1}^T w_j^2
\mathcal{L}^{(t)} = \Sigma_{j=1}^T \lbrack (\Sigma_{i \in I_j} g_i)w_j + \frac{1}{2} (h_i + \gamma)w_j^2 \rbrack + \gamma T


.

w_j^* = -\frac{\Sigma_{i\in I_j} g_i}{\Sigma_{i\in I_j} h_i + \lambda}

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

\mathcal{\tilde{L}}^{(t)} (q) = -\frac{1}{2} \Sigma_{j=1}^T \frac{(\Sigma_{i\in I_j} g_i)^2}{\Sigma_{i \in I_j} h_i + \lambda} + \gamma T

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

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

\mathcal{L}_{split} = \frac{1}{2} \lbrack \frac{\Sigma_{i\in I_L} g_i)^2}{\Sigma_{i \in I_L} h_i + \lambda} + \frac{\Sigma_{i\in I_R} g_i)^2}{\Sigma_{i \in I_R} h_i + \lambda} - \frac{\Sigma_{i\in I} g_i)^2}{\Sigma_{i \in I} h_i + \lambda} \rbrack - \gamma

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

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

Tham khảo:

Tác giả: Ông Hồng

Tags: đạo hàm, tăng cường độ dốc

About the Author Hoàng Hùng Movan

Tôi là một chuyên gia về phát triển và phân tích hệ thống. Tôi yêu công việc sáng tạo và làm ra những sản phẩm hữu ích về công nghệ thông tin

  • Rajan vishwakarma viết:

    The demand for Big Data is ever increasing in both domestic and international job market. Its Indian market is expected to shoot up to INR 28000 Crores by the end of 2019. This makes it the best time to make a career in this field.

  • by Movan
    >