- Là cấu trúc phân chia lặp đi lặp lại không gian đặc trưng để phân loại dữ liệu, trong đó ở mỗi bước sẽ chọn phép chia mang lại mức tăng thông tin lớn nhất
- Sử dụng entropy để đo độ thuần khiết (purity) của dữ liệu, và từ đó tính mức tăng thông tin (Information Gain)
- Thuật toán ID3 tìm điểm phân chia tối ưu bằng cách tính chênh lệch entropy giữa nút cha và nút con, rồi mở rộng cây theo cách đệ quy
- Ngoài entropy, cũng có thể dùng độ bất thuần Gini (Gini impurity); hai cách này thường cho kết quả tương tự nhau nhưng khác về hiệu quả tính toán
- Việc phân chia quá mức có thể gây ra quá khớp (overfitting) và tính bất ổn, nên thường được giảm nhẹ bằng cắt tỉa (pruning) hoặc rừng ngẫu nhiên (Random Forest)
Khái niệm cơ bản về cây quyết định
- Cây quyết định phân chia dữ liệu từ trên xuống dưới, áp dụng quy tắc điều kiện ở mỗi bước để chia dữ liệu thành các vùng được phân biệt rõ hơn
- Mỗi lần phân chia được quyết định theo một đặc trưng (feature) cụ thể và một ngưỡng (cutoff value)
- Mục tiêu là tạo ra các nút thuần khiết, nơi các lớp được tách biệt rõ ràng trong bài toán phân loại
Định nghĩa và tính chất của entropy
- Entropy là chỉ số đo độ bất định của thông tin, được định nghĩa với xác suất (p_i) là (H = -\sum p_i \log_2(p_i))
- Các tính chất chính
- Khi chỉ có một sự kiện có xác suất 1 và các sự kiện còn lại là 0 thì (H=0), tức là không có bất định
- Khi xác suất của mọi sự kiện bằng nhau thì entropy đạt cực đại, biểu thị trạng thái bất thuần nhất
- Xác suất càng tiến gần đến phân bố đều thì entropy càng tăng
- Vì vậy, nút thuần khiết có entropy bằng 0, còn nút pha trộn sẽ có giá trị entropy cao
Mức tăng thông tin và thuật toán ID3
- Mức tăng thông tin được tính bằng chênh lệch entropy trước và sau khi phân chia, thể hiện hiệu quả của việc phân chia dữ liệu
- Công thức: (\Delta IG = H_{\text{parent}} - \frac{1}{N}\sum N_{\text{child}} \cdot H_{\text{child}})
- Các bước của thuật toán ID3
- Tính entropy của từng đặc trưng
- Chia tập dữ liệu theo nhiều tiêu chí phân chia khác nhau và tính mức tăng thông tin
- Chọn phép chia có mức tăng thông tin lớn nhất để tạo nút quyết định
- Tạo nút lá khi không thể phân chia thêm nữa
- Thực hiện đệ quy với mọi tập con, nhưng dừng lại nếu mọi phần tử đều thuộc cùng một lớp
- Ví dụ, điều kiện Diameter ≤ 0.45 có mức tăng thông tin là 0.574, lớn nhất nên được chọn làm lần phân chia đầu tiên
Độ bất thuần Gini và thước đo thay thế
- Độ bất thuần Gini (Gini impurity) là một lựa chọn thay thế cho entropy, là một cách khác để đo mức độ bất thuần của thông tin
- Không cần tính log nên tốc độ tính toán nhanh hơn
- Với tập dữ liệu mất cân bằng, entropy có thể là lựa chọn thận trọng hơn
- Cả hai phương pháp nhìn chung đều cho ra kết quả tương tự nhau
Vấn đề quá khớp và tính bất ổn
- Thuật toán ID3 tiếp tục phân chia để giảm entropy xuống mức tối thiểu, nên cây có thể trở nên quá sâu
- Điều này gây ra quá khớp (overfitting), làm giảm khả năng khái quát hóa đối với dữ liệu mới
- Ngoài ra còn tồn tại vấn đề tính bất ổn (high variance), khi những thay đổi nhỏ trong dữ liệu cũng có thể làm cấu trúc cây thay đổi đáng kể
- Ví dụ: chỉ cần thêm nhiễu Gaussian nhỏ vào 5% dữ liệu huấn luyện cũng có thể tạo ra một cây hoàn toàn khác
- Để khắc phục, có thể dùng cắt tỉa (pruning) để giới hạn độ sâu của cây, số lá, số mẫu tối thiểu, v.v.
Mở rộng sang Random Forest
- Để giảm tính bất ổn của một cây quyết định đơn lẻ, người ta dùng cách huấn luyện nhiều cây trên các mẫu dữ liệu khác nhau rồi kết hợp dự đoán của chúng
- Cách tiếp cận này chính là Random Forest, mang lại độ ổn định và khả năng khái quát hóa cao
- Phương pháp này bù đắp các nhược điểm của cây quyết định và đến nay vẫn được đánh giá là một trong những thuật toán machine learning thành công nhất
Kết luận và học thêm
- Cây quyết định là mô hình dễ diễn giải, học nhanh và yêu cầu tiền xử lý đơn giản
- Tuy nhiên, để giải quyết vấn đề quá khớp và tính bất ổn, cần đến cắt tỉa hoặc kỹ thuật ensemble
- Bài viết không đề cập đến cây hồi quy, end-cut preference, hyperparameter, v.v.; người đọc được khuyến nghị học thêm qua các tài liệu liên quan
1 bình luận
Ý kiến trên Hacker News
“Vũ khí bí mật” đã rất hiệu quả với tôi khi học bộ phân loại là trước tiên huấn luyện một bộ phân loại tuyến tính tốt
Sau đó dùng giá trị đầu ra chưa ngưỡng hóa của bộ phân loại tuyến tính đó như một chiều đặc trưng bổ sung để huấn luyện cây quyết định, rồi bọc nó trong một hệ thống cây tăng cường
Làm vậy thì mô hình tuyến tính bù cho điểm yếu của cây quyết định, còn cây thì xử lý những phần mà mô hình tuyến tính gặp khó
Cũng có thể cân nhắc xoay dữ liệu hoặc chuẩn hóa theo trục, nhưng phần lớn là không cần
Tuy vậy, khi đặc trưng quá thưa thì cây sẽ khó tìm điểm phân tách
Ta thêm tính toán vào trạng thái gốc để tạo thành trạng thái quan sát được (observed state) rồi mới học
Ví dụ trong trò Snake, ngoài tọa độ của con rắn còn tính thêm các đặc trưng suy diễn như số đường thoát
Nếu không làm sạch dữ liệu và thiết kế đặc trưng tốt, kết quả sẽ tệ hơn nhiều so với các mô hình hộp đen như mạng nơ-ron
Trớ trêu là mạng nơ-ron tự tìm ra các đặc trưng tiềm ẩn này, nhưng lại khó giải thích vì sao nó hoạt động như vậy
Oblique Decision Tree, Model Tree (M5), Logistic Model Tree (LMT), Hierarchical Mixture of Experts (HME) là một vài ví dụ
Hồi khoảng năm 2010 khi làm ở CERN, Boosted Decision Tree là bộ phân loại phổ biến nhất
Lý do là nó cân bằng tốt giữa khả năng giải thích và năng lực biểu diễn, và thời đó về mặt văn hóa người ta còn ngại dùng mạng nơ-ron trong phân tích vật lý
Giờ thì thời thế đã thay đổi rất nhiều
Trong vật lý, điều quan trọng là hiểu được cơ chế nhân quả, chứ không chỉ đơn giản là khớp đường cong tốt
Cũng như hệ vòng tròn phụ (epicycle) của Ptolemy khớp chuyển động thiên thể tốt hơn nhưng không giải thích được nguyên nhân
Chỉ cần sâu thêm một chút là nó gần như biến thành một khu rừng không thể diễn giải nổi
Mạng nơ-ron cũng vậy, bạn có thể lần theo các phép toán bên trong, nhưng cuối cùng vẫn không biết vì sao nó đưa ra quyết định đó
Cùng trang đó cũng có phần giải thích về Random Forest → mlu-explain/random-forest
Một sự thật thú vị: mạng nơ-ron 1-bit (single-bit neural network) về bản chất chính là cây quyết định
Về mặt lý thuyết, phần lớn mạng nơ-ron có thể được “biên dịch” thành chuỗi if-else, nhưng khi nào cách đó hoạt động tốt thì vẫn chưa rõ
Nó giống như một sự mở rộng khái niệm hơn là ánh xạ trực tiếp
Vì vậy sẽ tốt hơn nếu được giải thích rõ hơn là câu đó được nói theo nghĩa cụ thể nào
Ưu điểm lớn nhất của cây quyết định là tốc độ
Trong môi trường độ trễ thấp, tôi từng thử thay bộ phân loại dựa trên cây bằng một mạng nơ-ron nhỏ, nhưng dù mạng nơ-ron chính xác hơn một chút thì độ trễ suy luận (latency) lại cao hơn hơn 100 lần
Trong khi đó, cây tăng cường hay bagging thì phức tạp hơn, còn các thuật toán ML cổ điển khác cũng kém linh hoạt hơn về khả năng triển khai
Trong một giáo trình ML nào đó (có lẽ là ESL), cây quyết định được mô tả như sau
“Có thể diễn giải, nhanh, hoạt động ổn với nhiều loại dữ liệu, không nhạy với scaling, ít tham số cần tinh chỉnh, nhưng... không hoạt động tốt”
Dĩ nhiên có thể khắc phục nhược điểm này bằng bagging hoặc boosting, nhưng trong quá trình đó lại đánh mất một phần ưu điểm ban đầu
Tôi thực sự rất thích cây quyết định. Đây là thuật toán ML cổ điển tôi ưa thích nhất
Tôi từng làm một bản cài đặt song song thuần hàm bằng GNU Guile → liên kết mã nguồn
Tuy nhiên Guile không có thứ như NumPy hay DataFrame, nên việc biểu diễn dữ liệu kém hiệu quả
Guile phù hợp với thao tác trên cây nên có vẻ khá tự nhiên để cài đặt cây quyết định
Tuy vậy, nếu biên dịch sang mã máy thì có lẽ sẽ hiệu quả hơn
Nhân tiện, cũng đáng xem qua Lush(https://lush.sourceforge.net/) và aiscm(https://wedesoft.github.io/aiscm/)
Ra quyết định mơ hồ của chuyên gia cũng thường có thể được mô hình hóa bằng cây quyết định đơn giản hoặc chuỗi quyết định
Bản thân chuyên gia nghĩ rằng mình rất phức tạp, nhưng trên thực tế một cây đơn giản lại giải thích tốt hơn trong nhiều trường hợp
Trước đây hồi quy hay phân cụm dựa trên khoảng cách trông có vẻ tinh vi hơn, nhưng cây lại hiệu quả hơn nhiều
Nội dung liên quan được trình bày khá kỹ trong chương 7 của Oxford Handbook of Expertise
Xét cho cùng, cây quyết định là cấu trúc chia không gian khả năng như kD-Tree rồi gán hành động cho từng vùng
Sự tinh tế trong phán đoán của chuyên gia đến từ độ chi tiết của các bề mặt ranh giới, nhưng cây vẫn cho một phép xấp xỉ khá tốt
Trang web này khá thú vị và phần trình bày cũng tốt
Tuy nhiên độ tương phản màu của một số đoạn chữ thấp nên hơi khó đọc
Khả năng tiếp cận không chỉ dành cho người khuyết tật mà còn là yếu tố cơ bản để tăng độ dễ đọc
Trong thời đại deep learning hiện nay, cây quyết định đang bị đánh giá thấp
Nhưng chúng vẫn dễ diễn giải, nhanh và đủ thực dụng
Tôi đã xây dựng một hệ thống chấm điểm phân tích website dựa trên cây,
đánh giá các điều kiện như “có meta description không?”, “tải trong vòng 3 giây không?”, “có tương thích di động không?”
Người dùng có thể hiểu ngay vì sao họ nhận số điểm đó
Không thể giải thích vì sao mạng nơ-ron cho 73 điểm, nhưng với cây thì điều đó rất dễ
Cây chẩn đoán của Esagil-kin-apli từ khoảng năm 1000 TCN chính là khởi đầu của truyền thống đó