Popular Tree model types

--- title: 'Popular Tree model types' tags: ML , VTB, BigData --- [TOC] # Decision Tree Nhắc lại về Decision Tree > :bookmark: Thuật ngữ - Tinh khiết: purity - Vẩn đục: impurity > :high_brightness: Ý tưởng: Từ một dataset, liên tục chia thành các subset nhỏ hơn bằng các câu hỏi đúng sai. Quá trình huấn luyện được fit khi các mẫu dữ liệu được phân chia đúng vào các lá. ![image alt](https://aiaspirant.com/wp-content/uploads/2020/02/dt_struct.png "title") 1. Đo độ tinh khiết - Entropy: $\mathbf{H}(\mathbf{p}) = -\sum_{i=1}^{C}p_i \log p_i$ - Gini: $\mathbf{Gini} = 1-\sum_{i=1}^{C} p_i^2$ 2. Một số hyper-parameter cần lưu ý Một số hyper-parameter cần lưu ý khi triển khai Decision Tree function ```python= from sklearn.tree import DecisionTreeClassifier DecisionTreeClassifier( criterion='gini', max_depth=None, min_samples_split=2, min_samples_leaf=1, max_features=None, max_leaf_nodes=None, min_impurity_decrease=0.0, min_impurity_split=None ) ``` :spiral_note_pad: Diễn giải > criterion: Là hàm số để đo lường chất lượng phân chia ở mỗi node. Có hai lựa chọn là gini và entropy. > max_depth: Độ sâu tối đa cho một cây quyết định. Đối với mô hình bị quá khớp thì chúng ta cần giảm độ sâu và vị khớp thì gia tăng độ sâu. > min_samples_split: Kích thước mẫu tối thiểu được yêu cầu để tiếp tục phân chia đối với node quyết định. Được sử dụng để tránh kích thước của node lá quá nhỏ nhằm giảm thiểu hiện tượng quá khớp. > max_features: Số lượng các biến được lựa chọn để tìm kiếm ra biến phân chia tốt nhất ở mỗi lượt phân chia. > max_leaf_nodes: Số lượng các node lá tối đa của cây quyết định. Thường được thiết lập khi muốn kiểm soát hiện tượng quá khớp. > min_impurity_decrease: Chúng ta sẽ tiếp tục phân chia một node nếu như sự suy giảm của độ tinh khiết nếu phân chia lớn hơn ngưỡng này. im > min_impurity_split: Ngưỡng dừng sớm để kiểm soát sự gia tăng của cây quyết định. Thường được sử dụng để tránh hiện tượng quá khớp. Chúng ta sẽ tiếp tục chia node nếu độ tinh khiết cao hơn ngưỡng này. Thử giải bài tập với Decision Tree ![image alt](https://aiaspirant.com/wp-content/uploads/2020/02/dataset_dt.png "title" =500x300) # Essemble Tree ![image alt](https://quantdare.com/wp-content/uploads/2016/04/bb3-800x307.png) > **Intution** > *"một cây làm chẳng nên non ba cây chụm lại nên hòn núi cao"*. Hay nhiều mô hình yếu(weak learner) được kết hợp thành một mô hình duy nhất mạnh mẽ hơn. :point_right: Types - **Single**: Decision Tree đơn lẻ - **Bagging**: **Xây dựng một lượng lớn các model** (thường là cùng loại) trên những **subsamples khác nhau** từ tập training dataset (random sample trong 1 dataset để tạo 1 dataset mới). Những model này sẽ được train độc lập và song song với nhau nhưng đầu ra của chúng sẽ được **trung bình cộng/ argmax để cho ra kết quả cuối cùng**. - **Boosting**: ***Xây dựng một lượng lớn các model*** (thường là cùng loại). Mỗi model sau sẽ học cách **sửa những errors của model trước** (dữ liệu mà model trước dự đoán sai) -> tạo thành một chuỗi các model mà **model sau sẽ tốt hơn model trước** bởi trọng số được update qua mỗi model ## Bagging Random Forest > :bookmark:Thuật ngữ - Học kết hợp: ensemble learning - Phương pháp bỏ túi: bagging - Lấy mẫu tái lập: Boostrapping - Mẫu nằm ngoài túi: out of bag ### Boostrapping - Lấy mẫu tái lập (Boostrapping) - Tập dữ liệu $\mathcal{D} = \{(x_1, y_1), (x_2, y_2), \dots, (x_N, y_N)\}$ với $N$ quan sát - RF sử dụng bootstrapping để tạo thành $B$ tập dữ liệu con (gọi là bagging) - Thực hiện $M$ lượt nhặt dữ liệu và bỏ vào tập $\mathcal{B}_i=\{(x_1^{(i)}, y_1^{(i)}), (x_2^{(i)}, y_2^{(i)}), \dots, (x_M^{(i)}, y_M^{(i)})\}$ - $Bi$ cho phép phần tử lặp lại - Tồn tại những quan sát thuộc $B$ nhưng không thuộc $D$, chúng ta gọi chúng là nằm ngoài túi (out of bag). ![image alt](https://imgur.com/XdXbFfs.jpeg "Image of RF") ### Voting Với mỗi tập dữ liệu $\mathcal{B}_i$ chúng ta xây dựng một mô hình _cây quyết định_ và trả về kết quả dự báo là $\hat{y}_j^{(i)} = f_i(\mathbf{x}_j)$. Trong đó $\hat{y}_j^{(i)}$ là dự báo của quan sát thứ $j$ từ mô hình thứ $(i)$, $\mathbf{x}_j$ là giá trị véc tơ đầu vào, $f_i(.)$ là hàm dự báo của mô hình thứ $i$. Mô hình dự báo từ cây quyết định là giá trị trung bình hoặc bầu cử của $B$ cây quyết định. - Đối với mô hình regression: Chúng ta tính giá trị trung bình của các dự báo từ mô hình con. $$\hat{y}_j = \frac{1}{B} \sum_{i=1}^{B} \hat{y}_j^{(i)}$$ - Đối với mô hình classification: Chúng ta thực hiện _bầu cử_ từ các mô hình con để chọn ra nhãn dự báo có tần suất lớn nhất. $$\hat{y}_j = \arg \max_{c} \sum_{i=1}^{B} p(\hat{y_j}^{(i)} = c)$$ ### Hyper parameter ```python from sklearn.essemble import RandomForestClassifier RandomForestClassifier( n_estimators=100, criterion='gini', max_depth=None, min_samples_split=2, min_samples_leaf=1, max_features=None, max_leaf_nodes=None, min_impurity_decrease=0.0, min_impurity_split=None, bootstrap=True, oob_score=False, max_samples=None ) ``` > n_estimators là số lượng các cây quyết định được sử dụng trong mô hình rừng cây. > bootstrap=True tương ứng với sử dụng phương pháp lấy mẫu tái lập khi xây dựng các cây quyết định. Trái lại thì chúng ta sử dụng toàn bộ dữ liệu. Lưu ý rằng ở đây do chúng ta đã lựa chọn ngẫu nhiên ra biến khi xây dựng cây quyết định nên dù sử dụng chung một tập dữ liệu thì các cây quyết định vẫn khác nhau. > oob_score chỉ có hiệu lực khi sử dụng khi sử dụng boostrap. Nếu oob_score=True thì sẽ tính toán thêm điểm số trên các mẫu nằm ngoài túi. > max_samples là số lượng mẫu được sử dụng để huấn luyện mô hình cây quyết định. Mặc định max_samples=None thì chúng ta lấy ra các mẫu con có kích thước bằng với tập huấn luyện. --- :spiral_note_pad: **Feature importance** Những biến càng quan trọng thì càng gần node gốc trong mô hình cây quyết định. Như vậy tính trung bình giá trị vị trí độ sâu của các biến xuất hiện trong toàn bộ các cây quyết định của mô hình rừng cây chúng ta hoàn toàn có thể xếp hạng được khá chuẩn xác biến nào có mức độ quan trọng hơn. ```python rdf_clf = RandomForestClassifier(**kwargs) rdf_clf.fit(X_train,Y_train) rdf_clf.feature_importances_ pd.DataFrame({'features': iris.feature_names, 'importance':rdf_clf.feature_importances_}).sort_values('importance', ascending=False) ``` ## Boosting ### Adaptive Boosting 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. ![](https://imgur.com/KjfD7mj.png) **Fig:** 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. **Triển khai** ```python from sklearn.ensemble import AdaBoostClassifier from sklearn.tree import DecisionTreeClassifier # Train model ada_clf = AdaBoostClassifier( DecisionTreeClassifier(max_depth=2), n_estimators=20 ) ada_clf.fit(X_train, y_train) ``` ### Gradient Boosting Thay vì cố gắng khớp giá trị biến mục tiêu là $y$ thì chúng ta sẽ tìm cách khớp giá trị sai số của mô hình trước đó. Sau đó chúng ta sẽ đưa thêm mô hình huấn luyện vào hàm dự báo để cập nhật dần dần ***phần dư*** (pseudo-residuals). ![image alt](https://i.imgur.com/ZE8bBTA.png "title") Ta đặt 1) Số lượng cây $B$. 2) _Hệ số co_ (_shrinkage parameter_) $\lambda$ là một số dương nhỏ. Hệ số này cũng gần giống như _learning rate_ có tác dụng kiểm soát tỷ lệ mà _phương pháp tăng cường_ cập nhật số dư. Các giá trị của _hệ số co_ thường là 0.01 hoặc 0.001 3) Độ sâu $d$ của cây quyết định đại diện cho số lần phân chia tối đa trong mỗi cây quyết định. Thường thì trong _phương pháp tăng cường_ thì chúng ta không cần yêu cầu $d$ quá lớn. Điều này nhằm kiểm soát mức độ phức tạp của mô hình và tránh hiện tượng _quá khớp_. #### **Thuật toán** ![image alt](https://imgur.com/YzvCJ6g.png "title") Giả định $\hat{f}(x)$ là hàm dự báo từ _phương pháp tăng cường_ được áp dụng trên một tác vụ dự báo với ma trận đầu vào $\mathbf{X}$ và biến mục tiêu là véc tơ $\mathbf{y}$. Tại mô hình thứ $b$ trong chuỗi mô hình dự báo, kí hiệu là $\hat{f}^{b}$, ta tìm cách khớp một giá trị phần dư $\mathbf{r}_i$ từ cây quyết định tiền nhiệm $\hat{f}^{b-1}$. Các bước trong quá trình huấn luyện mô hình theo _phương pháp tăng cường_ được tóm tắt như sau: 1.- Ban đầu ta thiết lập hàm dự báo $\hat{f}(\mathbf{x}) = 0$ và số dư $\mathbf{r}_0 = \mathbf{y}$ cho toàn bộ quan sát trong tập huấn luyện. 2.- Lặp lại quá trình huấn luyện cây quyết định theo chuỗi tương ứng với $b = 1,2, \dots, B$. Với một lượt huấn luyện gồm các bước con sau đây: a. Khớp một cây quyết định $\hat{f}^{b}$ có độ sâu là $d$ trên tập huấn luyện $(\mathbf{X}, \mathbf{r}_b)$. b. Cập nhật $\hat{f}$ bằng cách cộng thêm vào giá trị dự báo của một cây quyết đinh, giá trị này được nhân với hệ số co $\lambda$: $$\hat{f}(\mathbf{x}) = \hat{f}(\mathbf{x})+\lambda \hat{f}^{b}(\mathbf{x})$$ c. Cập nhật phần dư cho mô hình: $$\mathbf{r}_{b+1} := \mathbf{r}_b - \lambda \hat{f}^{b}(\mathbf{x})$$ Thuật toán sẽ dừng cập nhật khi số lượng cây quyết định đạt ngưỡng tối đa $B$ hoặc toàn bộ các quan sát trên tập huấn luyện được dự báo đúng. 3.- Kết quả dự báo từ chuỗi mô hình sẽ là kết hợp của các mô hình con: $$\hat{f}(\mathbf{x}) = \sum_{b=1}^{B} \lambda \hat{f}^{b}(\mathbf{x})$$ #### Hyper-parameter ```python from sklearn.ensemble import GradientBoostingRegressor GradientBoostingRegressor( learning_rate=0.1, n_estimators=100, min_samples_split=2, min_samples_leaf=1, max_depth=3, max_features=None, max_leaf_nodes=None, tol=0.0001 ) ``` * max_depth: Độ sâu tối đa của một _cây quyết định_, tương ứng với tham số $d$. * min_samples_leaf: Số mẫu tối đa được phép của một node lá. * n_estimators: Số lượng tối đa các cây quyết định trong mô hình, tương ứng với tham số $B$. * learning_rate: Hệ số co trong quá trình cập nhật phần dư, tương ứng với $\lambda$. #### XGBoost vs LGBM 1. XGBoost (Extreme Gradient Boosting) ![image alt](https://i.imgur.com/BqaYk2z.png "title") OpenSource 2014 2. LightGBM ![image alt](https://i.imgur.com/qSBQiE0.png "title") Microsoft 2016 https://github.com/Microsoft/LightGBM/blob/master/docs/Features.rst # Thảo luận 1. Sự khác biệt cơ bản giữa Bagging & Boosting 2. Làm sao để tránh Overfitting trên các thuật toán? Tại sao Bagging làm việc tốt với dataset có Outliers? 3. Outcome trong bài toán Classification của Boosting là gì? Gợi ý: https://blog.paperspace.com/gradient-boosting-for-classification/ 4. Điều gì làm LightLBM nhanh? # Reference https://www.section.io/engineering-education/entropy-information-gain-machine-learning/#information-gain https://affine.ai/gradient-boosting-trees-for-classification-a-beginners-guide/ https://jerryfriedman.su.domains/ftp/trebst.pdf https://sefiks.com/2018/11/02/a-step-by-step-adaboost-example/ phamdinhkhanh.github.io https://towardsdatascience.com/what-makes-lightgbm-lightning-fast-a27cf0d9785e https://towardsdatascience.com/lightgbm-vs-xgboost-which-algorithm-win-the-race-1ff7dd4917d https://papers.nips.cc/paper/2017/hash/6449f44a102fde848669bdd9eb6b76fa-Abstract.html https://towardsdatascience.com/all-you-need-to-know-about-gradient-boosting-algorithm-part-1-regression-2520a34a502 https://towardsdatascience.com/all-you-need-to-know-about-gradient-boosting-algorithm-part-2-classification-d3ed8f56541e