Lỗi bộ khởi tạo dự kiến trước ttree năm 2024
Xin chào các bạn, sau 1 thời gian vắng bóng vì cạn ý tưởng viết bài và cũng cảm thấy bản thân chưa làm được điều gì nên hồn để chia sẻ, mình đã quay trở lại với Viblo để viết về một chủ đề không mới, về một thuật toán không mới, tuy nhiên không phải ai cũng hoàn toàn hiểu được và vận dụng được nó : Gradient Boosting. Show Ý tưởng để gợi lên mình viết bài viết này có lẽ bắt nguồn từ bài viết Ensemble learning và các biến thể (P1) của tác giả Phạm Minh Hoàng. Đây là một bài viết khá hay và phần giải thích dễ hiểu về các thuật toán ensemble, tuy nhiên có 1 điều khá đáng tiếc là sau hơn 1 năm chờ đợi, tác giả đã viết rất nhiều bài viết chất lượng khác, nhưng tuyệt nhiên lại không có bài viết nào liên quan đến "Ensemble learning và các biến thể (P2)", làm các fan comment chờ đợi trong vô vọng. Thế nên là "Tự túc là hạnh phúc", hôm nay mình viết bài này, xin phép nối tiếp nội dung mà tác giả đang chia sẻ dở, một bài viết về thuật toán Ensemble tiếp theo, sau Bagging, chính là về Boosting. Các bạn có thể gọi bài viết này với một tiêu đề khác là "Ensemble learning và các biến thể (P2)" cũng được Oke, bắt đầu vào nội dung chính của bài viết nào ! 1. Nhắc lại 1 chút về Ensemble MethodsEnsemble Method hay gọi một cách Việt hóa là Học Kết Hợp, là một phương pháp với tư tưởng là Thay vì cố gắng xây dựng một mô hình tốt duy nhất, chúng ta sẽ xây dựng một họ các mô hình yếu hơn một chút, nhưng khi kết hợp các mô hình lại, (nếu có thể kết hợp một cách chính xác) sẽ thu được một mô hình còn vượt trội hơn cả. 1.1 Single weak learnerNếu tiếp xúc đủ lâu với Machine Learning, các bạn chắc hẳn đều đã biết đến những giải thuật, những mô hình kinh điển trong lĩnh vực này :
Khi gặp một bài toán bất kì, dù là phân lớp (classification) hay hồi quy (regression) thì việc chọn ra một mô hình đủ tốt luôn là một quyết định quan trọng và khó khăn nhất. Khác với Deep Learning, việc tìm ra mô hình tốt là việc cố gắng thay đổi số layer hay thay đổi cấu trúc mạng, ở Machine Learning, việc lựa chọn mô hình là việc tối ưu tham số, quan sát các đặc điểm về số chiều của không gian dữ liệu, đặt ra các giả thiết về phân phối dữ liệu, ... Có thể mô tả một quá trình giải quyết bài toán machine learning như sau :
Tất cả các thao tác trên bản chất là xoay quanh để giải quyết vấn đề giữa bias và variance (bias-variance trade off). Hiểu đơn giản về bias-variance trade off tức là "chúng ta mong muốn mô hình khi fit vào dữ liệu sẽ có bias thấp và variance thấp, tuy nhiên, bias và variance thường có xu hướng nghịch đảo với nhau. - bias thấp nhưng variance cao hoặc variance thấp nhưng bias cao, và chúng ta chỉ có thể lựa chọn tăng cái này và chấp nhận giảm cái kia". Một điều đặc biệt là, khi chúng ta chỉ sử dụng single model hay single learner (tức là chỉ dùng đúng duy nhất một model để fit vào dữ liệu), bias-variance trade off là điều không thể tránh khỏi - Single weak learner . 1.2 Combine weak learnersĐể giải quyết được vấn đề bias-variance trade off, một hướng giải quyết được đề xuất là : "Nếu 1 model không thể tự giải quyết được, hãy để nhiều model cùng nhau giải quyết". Tất nhiên, nhiều model ở đây có thể là cùng một loại nhưng áp dụng trên những phần dữ liệu khác nhau (kì vọng là độc lập với nhau) hoặc những model hoàn toàn khác loại được kết hợp lại. Mỗi kiểu kết hợp model lại được áp dụng tùy theo mục đích nhất định, chứ không phải là kết hợp tùy tiện. Dựa vào tính chất này, chúng ta chia các thuật toán ensemble thành các nhóm chính sau (phần này mình xin trích lại từ Part1 nha):
2. Bỏ qua Bagging, chúng ta đến với Boosting2.1 Ý tưởng của BoostingQua Part 1, chúng ta đã biết được Bagging được kết hợp từ các model được fit trên các tập dữ liệu con (được lấy theo boostrap sample để các tập con được kì vọng là độc lập), từ đó kết hợp các kết quả từ các model này để đưa ra kết quả cuối cùng. Tuy nhiên, có 1 số điều chúng ta có thể để ý ở đây
Boosting ra đời dựa trên việc mong muốn cải thiện những hạn chế trên. Ý tưởng cơ bản là Boosting sẽ tạo ra một loạt các model yếu, học bổ sung lẫn nhau. Nói cách khác, trong Boosting, các model sau sẽ cố gắng học để hạn chế lỗi lầm của các model trước. Vậy làm thể nào để hạn chế được sai lầm từ các model trước ? Boosting tiến hành đánh trọng số cho các mô hình mới được thêm vào dựa trên các cách tối ưu khác nhau. Tùy theo cách đánh trọng số (cách để các model được fit một cách tuần tự) và cách tổng hợp lại các model, từ đó hình thành nên 2 loại Boosting :
Chúng ta sẽ phân tích sâu hơn về 2 dạng Boosting này ở phần sau. Để kết thúc phần này, có một vài nhận xét về Boosting như sau:
2.2 AdaBoost - Gradient BoostingCả AdaBoost và Gradient Boosting đều xây dựng thuật toán nhằm giải quyết bài toán tối ưu sau : mincn=1:N,wn=1:NL(y,∑n=1Ncnwn))\text{min}_{c_n=1:N, w_n=1:N} L(y, \sum^N_{n=1} c_n w_n)) Trong đó :
Thoạt nhìn, công thức trên có vẻ khá giống với Bagging, thế nhưng cách tính ra các giá trị confidence score kia lại làm nên sự khác biệt về hướng giải quyết của Boosting. Thay vì cố gằng quét tìm tất cả các giá trị cn,wnc_n, w_n để tìm nghiệm tối ưu toàn cục - một công việc tốn nhiều thời gian và tài nguyên, chúng ta sẽ cố gắng tìm các giá trị nghiệm cục bộ sau khi thêm mỗi một mô hình mới vào chuỗi mô hình với mong muốn dần đi đến nghiệm toàn cục. mincn,wnL(y,Wn−1+cnwn))\text{min}_{c_n, w_n} L(y, W_{n-1} + c_n w_n)) với Wn−1=∑n=1N−1cnwnW_{n-1} = \sum^{N-1}_{n=1} c_n w_n Adaptive BoostingAdaBoost tiến hành train các mô hình mới dựa trên việc đánh lại trọng số cho các điểm dữ liệu hiện tại, nhằm giúp các mô hình mới có thể tập trung hơn vào các mẫu dữ liệu đang bị học sai, từ đó làm giảm giá trị loss của mô hình. Cụ thể, các bước triển khai thuật toán như sau :
Chi tiết về cách thuật toán hoạt động, bạn có thể đọc thêm example tại A Step by Step Adaboost Example FYI: AdaBoost có thể được áp dụng mà không cần dựa vào việc đánh trọng số lại các điểm dữ liệu, thay vào đó, chúng ta có thể re-sample để lấy dữ liệu train cho các model tiếp theo dựa vào xác suất được xác định bới các trọng số. Gradient BoostingGradient Boosting là một dạng tổng quát hóa của AdaBoost. Cụ thể như sau, vẫn vấn đề tối ưu ban đầu mincn,wnL(y,Wn−1+cnwn))\text{min}_{c_n, w_n} L(y, W_{n-1} + c_n w_n)) Trước tiên mình xin nhắc lại một chút lí thuyết mà các bạn đã khá quen trong neural network: Gradient Descent θn=θn−1−η∂∂θL(θn−1)\theta_n = \theta_{n-1} - \eta \frac{\partial}{\partial \theta}L(\theta_{n-1}) Phía trên là công thức cập nhật tham số mô hình theo hướng giảm của đạo hàm (Gradient Descent). Công thức này được sử dụng không gian tham số, tuy nhiên, để liên hệ với bài toán chúng ta đang xét, mình chuyển công thức sang góc nhìn của không gian hàm số. Khá đơn giản thôi, nếu chúng ta coi chuỗi các model boosting là một hàm số WW, thì mỗi hàm learner có thể coi là một tham số ww. Đến đây, để cực tiểu hóa hàm loss L(y,W)L(y, W), chúng ta áp dụng Gradient Descent Wn=Wn−1−η∂∂wL(Wn−1)W_n = W_{n-1} - \eta \frac{\partial}{\partial w}L(W_{n-1}) Đến đây, ta có thể thấy mối quan hệ liên quan sau cnwn≈−η∂∂wL(Wn−1)c_n w_n \approx - \eta \frac{\partial}{\partial w}L(W_{n-1}) với wnw_n là model được thêm vào tiếp theo. Khi đó, model mới cần học để fit để vào giá trị −η∂∂wL(Wn−1)- \eta \frac{\partial}{\partial w}L(W_{n-1}). (Giá trị −η∂∂wL(Wn−1)- \eta \frac{\partial}{\partial w}L(W_{n-1}) còn có 1 tên gọi khác là pseudo-residuals) Tóm lại, chúng ta có thể tóm tắt quá trình triển khai thuật toán như sau:
Nếu bạn để ý thì phương pháp cập nhật lại trọng số của điểm dữ liệu của AdaBoost cũng là 1 trong các case của Gradient Boosting. Do đó, Gradient Boosting bao quát được nhiều trường hợp hơn. 3. LightGBM và XGBOOSTCác phần trên là lí thuyết tổng quát về Ensemble Learning, Boosting và Gradient Boosting cho tất cả các loại model. Tuy nhiên, dù Bagging hay Boosting thì base model mà chúng ta biết đển nhiều nhất là dựa trên Decision Tree. Lí do là việc ensemble với các thuật toán Tree base cho kết quả cải thiện rõ ràng nhất, cũng là những thuật toán tốt nhất hiện nay đối với dạng dữ liệu có cấu trúc. Với Gradient Boosting có base model là Decision Tree, ta biết đến 2 framework phổ biến nhất là XGBoost và LightGBM 3.1 XGBOOSTXGBoost (Extreme Gradient Boosting) là một giải thuật được base trên gradient boosting, tuy nhiên kèm theo đó là những cải tiến to lớn về mặt tối ưu thuật toán, về sự kết hợp hoàn hảo giữa sức mạnh phần mềm và phần cứng, giúp đạt được những kết quả vượt trội cả về thời gian training cũng như bộ nhớ sử dụng. Mã nguồn mở với ~350 contributors và ~3,600 commits trên Gihub, XGBoost cho thấy những khả năng ứng dụng đáng kinh ngạc của mình như :
Kể từ lần đầu ra mắt năm 2014, XGBoost nhanh chóng được đón nhận và là giải thuật được sử dụng chính, tạo ra nhiều kết quả vượt trội, giành giải cao trong các cuộc thi trên kaggle do tính đơn giản và hiểu quả của nó. 3.2 LightGBMMặc dù đạt được những kết quả vượt trội, XGBoost gặp một vấn đề là thời gian training khá lâu, đặc biệt với những bộ dữ liệu lớn. Đến tháng 1 năm 2016, Microsoft lần đầu realease phiên bản thử nghiệm LightGBM, và LightGBM nhanh chóng thay thế vị trí của XGBoost, trở thành thuật toán ensemble được ưa chuộng nhất. LightGBM có những cải tiến gì? Chúng ta sẽ điểm qua một vài điểm chính sau đây:
Note: Leaf-wise tuy tốt, nhưng với những bộ dữ liệu nhỏ, các tree xây dựng dựa trên leaf-wise thường dẫn đến overfit khá sớm. Do đó, lightgbm sử dụng thêm 1 hyperparameter là maxdepth nhằm cố gắng hạn chế điều này. Dù vậy, LightGBM vẫn được khuyến khích sử dụng khi bộ dữ liệu là đủ to. Chi tiết hơn về các cải tiến của LightGBM, các bạn có thể đọc thêm tại: https://github.com/Microsoft/LightGBM/blob/master/docs/Features.rst Kết luậnBài cũng đã dài, mình định thêm 1 phần code minh họa nữa nhưng chắc sẽ các bạn cũng có thể tìm thấy rất nhiều đoạn code sử dụng LightGBM trên Kaggle nên mình không nếu thêm ra nữa. Hi vọng qua bài viết này, các bạn hiểu thêm về lí thuyết, tư tưởng của thuật toán Gradient Boosting, cũng như vận dụng tốt hơn 2 framework mạnh mẽ XGBoost và LightGBM để giải quyết các bài toán của bản thân. Nếu các bạn cần tham khảo thêm về tham số của 2 thư viện này, các bạn có thể đọc thêm tại https://towardsdatascience.com/lightgbm-vs-xgboost-which-algorithm-win-the-race-1ff7dd4917d hoặc tại chính docs của 2 framework này để nắm vững hơn. |