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}) là hàm mục tiêu ánh xạ \mathbf{x} sang y.

L(y, F(\mathbf{x})) là loss function:

  • Squared-error: (y - F)^2.
  • Absolute error: |y - F|, y \in R^1 (regression).
  • Negative binomial log-likelihood: log(1 + e^{-2yF}), y \in \{-1, 1\} (classification).

Mục tiêu của chúng ta tìm được hàm mục tiêu F^* 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

Trong không gian tham số, F(\mathbf{x}) thuộc lớp hàm F(\mathbf{x}; \mathbf{P}), \mathbf{P} = \{P_1, P_2, ...\} 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).

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 h(\mathbf{x}; \mathbf{a}_m) là một regression tree thứ m trong số M tree build được từ dạng “addictive” này. Cụ thể, trong thuật toán học CART (Breiman, Friedman, Olshen, Stone 1983), \mathbf{a}_m là splitting variables, split locations, terminal node của từng cây. \beta_m 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 F(\mathbf{x};\mathbf{P}) ta đi tính \mathbf{P^*} 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^*})

Để giải \mathbf{P^*} 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

trong đó, \mathbf{p}_0 là tham số khởi tạo và \{\mathbf{p}_m\}_1^M 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 \mathbf{g}_m 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).

Dấu trừ trước gradient -\mathbf{g}_m 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

Ở đâ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 F(\mathbf{x}) 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

Với tập dữ liệu hữu hạn \{F(\mathbf{x}_i)\}_1^N hàm cần tìm sẽ là:

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

trong đó, f_0(\mathbf{x}) là hàm khởi tạo, và \{f_m(\mathbf{x})\}_1^M 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}).

Như vậy, \rho_m sẽ là:

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

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

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: \mathbf{g}_m = \{g_{jm}\} = \{\lbrack \frac{\partial \Phi(\mathbf{P})}{\partial P_j} \rbrack_{\mathbf{P}=\mathbf{P}_{m-1}}\}
  • Parameters: \mathbf{p}_m = -\rho_m \mathbf{g}_m
  • Learning rate: \rho_m = argmin_\rho \Phi(\mathbf{P}_{m-1} - \rho \mathbf{g}_m)
  • Target parameters: \mathbf{P^*} = \Sigma_{m=0}^M \mathbf{p}_m

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

Thuật toán này nhằm xấp xỉ gradient thông qua một hàm tham số hoá h(\mathbf{x}; \mathbf{a}_m). Tại mỗi vòng lặp: ta tính gradient \tilde{y}_m. Ta xem\{-\tilde{y}_i, \mathbf{x}_i\}_1^N là tập training để huấn luyện hàm h(\mathbf{x}; \mathbf{a}_m). Từ đó, ta có thể dự đoán -\tilde{y}_m từ \mathbf{x}.

Gradient_Boost()
 F_0(\mathbf{x}) = argmin_\rho \Sigma_{i=1}^N L(y_i, \rho)
 For m = 1 to M do:
  # gradient step
  \tilde{y} = -\lbrack \frac{\partial L(y_i, F(\mathbf{x_i}))}{\partial F(\mathbf{x_i})} \rbrack_{F(\mathbf{x}) = F_{m-1}(\mathbf{x})}, i = 1, N
  a_m = argmin_{a, \beta} \Sigma_{i=1}^N \lbrack \tilde{y} - \beta h(x_i; a) \rbrack
  
  # boosting step
  \rho_m = argmin_\rho \Sigma_{i=1}^N L(y_i, F_{m-1}(x_i) + \rho h(x_i; \mathbf{a_m})
  F_m(\mathbf{x}) = F_{m-1}(\mathbf{x}) + \rho_m h(x; \mathbf{a_m})
 endFor
endAlgorithm

Như vậy, \tilde{y}_i vừa là gradient của function space vừa là label của parameter space. \beta là leanring rate để tìm tham số \mathbf{a}_m\rho_m là learning rate để boosting additive model F_m(\mathbf{x}).

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,F) = \frac{(y-F)^2}{2}. Lấy đạo hàm, ta được \bar{y}_i = y_i - F_{m-1}(\mathbf{x}_i).  Ngoài ra, ta có \rho_m = \beta_m khi thế đạo hàm vào thuật toán tổng quát. Khi đó, ta có:

LS_Boost()
 F_0(\mathbf{x}) = \bar{y}
 For m = 1 to M do:
  \tilde{y} = y_i - F_{m-1}(x_i), i = 1, N
  (\rho_m, \mathbf{a_m}) = argmin_{a, \rho} \Sigma_{i=1}^N \lbrack \tilde{y_i} - \rho h(x_i; a) \rbrack
  F_m(\mathbf{x}) = F_{m-1}(\mathbf{x}) + \rho_m h(x; \mathbf{a_m})
 endFor
endAlgorithm

Gradient boosting: Least-absolute-deviation loss

Least-absolute-deviation loss: L(y,F) = |y - F|. Lấy đạo hàm, ta được sign(y_i - F_{m-1}(\mathbf{x}_i)). 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)|.

Base learner: h(\mathbf{x}; \{b_j, R_j\}) = \Sigma_{j=1}^J b_j\mathbf{1}(\mathbf{x} \in R_j). Trong đó, R_j là regression tree với J-terminal node, \{R_j\}_1^J là disjoint regions, \{b_j\}_1^J là hệ số cho từng quyết định. Nếu \mathbf{x} \in R_j thì h(\mathbf{x}) = b_j.

Như vậy gradient sẽ là: b_{jm} = ave_{x_i \in R_{jm}} \tilde{y_i}.

Hàm boosting sẽ là: F_m(\mathbf{x}) = F_{m-1}(\mathbf{x}) + \Sigma_{j=1}^J \gamma_{jm}\mathbf{1} (\mathbf{x} \in R_{jm}). Trong đó, \gamma_{jm} = \rho_m b_{jm}.

LAD_TreeBoost()
 F_0(\mathbf{x}) = median\{y_i\}_1^N
 For m = 1 to M do:
  \tilde{y_i} = sign(y_i - F_{m-1}(x_i)), i = 1, N
  \{R_{jm}\}_1^J = J- terminal node tree(\{\tilde{y_i}, x_i\}_1^N)
  \gamma_{jm} = median_{x_i \in R_{jm}}\{y_i - F_{m-1}(x_i)\}, j = 1, J
  F_m(\mathbf{x}) = F_{m-1}(\mathbf{x}) + \Sigma_{j=1}^J \gamma_{jm} 1(x \in R_{jm})
 endFor
endAlgorithm

Gradient boosting: Binary classification

Negative binomial log-likelihood: L(y,F) = log\lbrack 1+exp(-2yF)\rbrack, y = \{-1,1\}. Lấy đạo hàm, ta được 2y_i/(1 + exp(2y_iF_{m-1}(\mathbf{x}_i))).

Line search sẽ là: \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)))).

Đối với base learner, \gamma_{jm} = argmin_\gamma \Sigma_{\mathbf{x}_j \in R_{jm}} log(1 + exp(-2y_i(F_{m-1}(\mathbf{x}_i) + \gamma))) đượ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|).

L_2_TreeBoost
 F_0(\mathbf{x}) = \frac{1}{2} log \frac{1 + \bar{y}}{1 - \bar{y}}
 For m = 1 to M do:
  \tilde{y_i} = 2 \frac{y_i}{1 + exp(2 y_i F_{m-1}(x_i))}, i = 1, N
  \{R_{jm}\}_1^J = J- terminal node tree(\{\tilde{y_i}, x_i\}_1^N)
  \gamma_{jm} = \Sigma_{x_i \in R_{jm}} \frac{\tilde{y_i}}{\Sigma_{x_i \in R_{jm}} |\tilde{y_i}| (2 - |\tilde{y_i}|)}, j = 1, J
  F_m(\mathbf{x}) = F_{m-1}(\mathbf{x}) + \Sigma_{j=1}^J \gamma_{jm} 1(x \in R_{jm})
 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: F_m(\mathbf{x}) = F_{m-1}(\mathbf{x}) + \nu \cdot \rho_m h(\mathbf{x}; \mathbf{a}_m), 0 < \nu \le 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:

  • n: số lượng mẫu huấn luyện.
  • m: số lượng features.
  • \mathcal{D} = \{(\mathbf{x}_i, y_i)\} là tập dữ liệu với |\mathcal{D}| = n,\mathbf{x}_i \in \mathbb{R}^m, y_i \in \mathbb{R}.
  • q: 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.
  • T: số lượng nút lá trên cây.
  • f_k: cấu trúc các cây k độc lập của mô hình.
  • w_i: trọng số của nút lá thứ i.
  • \hat{y}_i^{(t)}: giá trị dự đoán của instance thứ i tại vòng lặp thứ t.
  • f_t^2(\mathbf{x}_i): đạo hàm bậc 2 của hàm f.
  • I_j = \{i|q(\mathbf{x}_i) = j\}: tập các giá trị tại nút lá j
  • I_L: tập giá trị nút lá bên trái.
  • I_R: tập giá trị nút lá bên phải.
  • I = I_L \cup I_R.

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}. Trong đó, \mathcal{F} = \{f(\mathbf{x}) = w_{q(\mathbf{x})}\} (q : \mathbb{R}^m) \rightarrow T, w \in \mathbb{R}^T.

Hàm học:

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

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)

với, 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)}).

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

Trọng số tối ưu tại mỗi nút lá: w_j^* = -\frac{\Sigma_{i\in I_j} g_i}{\Sigma_{i\in I_j} h_i + \lambda}

Hàm lỗi tính trên toàn bộ cây: \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

Đ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

Nguồn tham khảo

 

Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Đăng xuất /  Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Đă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 )

w

Connecting to %s