Random forest

Vì sao trung bình giúp ích

Bài 2.5 kết luận cây có variance cao: đổi dữ liệu một chút là cây đổi hẳn. Giả sử có $B$ mô hình, mỗi cái có phương sai $\sigma^2$, và hai mô hình bất kỳ có hệ số tương quan $\rho$. Phương sai của trung bình là

Khi $B \to \infty$, số hạng thứ hai biến mất nhưng số hạng đầu thì còn nguyên. Nhiều cây hơn chỉ giúp đến một mức; muốn giảm tiếp thì phải làm các cây ít giống nhau hơn, tức giảm $\rho$.

Với $\sigma^2 = 1$ và $B = 100$: nếu $\rho = 0.5$ thì phương sai còn $0.505$; nếu $\rho = 0.1$ thì còn $0.109$. Giảm tương quan có lợi hơn nhiều so với thêm cây. Khi $\rho = 0$ thì phương sai chia đều cho $B$: chụp 8 tấm cùng một cảnh tối rồi lấy trung bình từng điểm ảnh, nhiễu ngẫu nhiên triệt tiêu bớt còn cảnh đứng yên được giữ nguyên.

Hai nguồn ngẫu nhiên

Random forest (Breiman, 2001) làm các cây khác nhau bằng hai cách:

1. Bagging (bootstrap aggregating): mỗi cây học trên một tập bootstrap, tức $n$ mẫu rút có hoàn lại từ $n$ mẫu gốc.
2. Chọn ngẫu nhiên đặc trưng ở mỗi nút: chỉ xét một tập con ngẫu nhiên gồm max_features đặc trưng khi tìm phép chia tốt nhất. Nếu có một đặc trưng rất mạnh, bagging thuần túy vẫn cho mọi cây chia ở gốc bằng đặc trưng đó và các cây vẫn giống nhau. Che bớt đặc trưng buộc các cây phải tìm đường khác.

Mỗi cây được mọc sâu, gần như không cắt tỉa: bias thấp, variance cao, rồi trung bình hóa để kéo variance xuống. Phân loại thì lấy trung bình xác suất (hoặc bỏ phiếu); hồi quy thì lấy trung bình giá trị, $\frac1B\sum_b T_b(\mathbf{x})$. Các cây học độc lập, có thể học song song; boosting ở bài 2.7 thì dựng cây nối tiếp, cây sau sửa lỗi cây trước.

Hai cách gộp không luôn đồng ý. Ba cây cho xác suất lớp 1 của cùng một mẫu là $0.9$, $0.4$, $0.4$. Trung bình xác suất là $(0.9 + 0.4 + 0.4)/3 \approx 0.57$, dự đoán lớp 1; bỏ phiếu thì chỉ 1 trên 3 cây chọn lớp 1, dự đoán lớp 0. Một cây rất chắc chắn thắng hai cây lưỡng lự. scikit-learn dùng cách thứ nhất, và khi cần xác suất để tính log loss hay AUC thì đó cũng là cách nên dùng.

Out-of-bag: validation miễn phí

Xác suất một mẫu không được chọn lần nào trong $n$ lần rút có hoàn lại là

Vậy mỗi cây “chưa thấy” khoảng 37% dữ liệu. Dự đoán mỗi mẫu bằng các cây không dùng nó, ta được điểm out-of-bag (OOB): một ước lượng gần như cross-validation mà không tốn thêm lần huấn luyện nào. Mỗi mẫu nhận phiếu đa số của riêng các cây không thấy nó; lỗi OOB là tỉ lệ mẫu bị đoán sai, tính theo mẫu chứ không theo từng phiếu.

Ví dụ 5 mẫu, đánh số 1 đến 5, rừng có 3 cây:

Điểm OOB của mẫu 1 chỉ do cây 2 chấm, mẫu 3 chỉ do cây 3 chấm, và cứ thế. Với $n = 5$, xác suất một mẫu nằm ngoài một tập bootstrap là $(4/5)^5 \approx 0.33$, đã khá gần $0.368$.

Các tham số

Biến thể Extra Trees (extremely randomized trees) chọn luôn ngưỡng ngẫu nhiên thay vì tìm ngưỡng tốt nhất: nhanh hơn, cây còn khác nhau hơn nữa, đôi khi tốt hơn trên dữ liệu nhiễu.

Tự nhìn một lần bootstrap

Đừng hiểu bootstrap là lấy một tập con không lặp. Với $n$ mẫu, mỗi cây rút $n$ lần có hoàn lại: một mẫu có thể xuất hiện nhiều lần, mẫu khác không xuất hiện lần nào. Ta nhìn ngay một lượt rút nhỏ trước khi dùng cả rừng.

import numpy as np

rng_boot = np.random.default_rng(7)
draw = rng_boot.integers(0, 5, size=5)
seen = np.unique(draw)
oob = np.setdiff1d(np.arange(5), seen)
print("rút:", draw.tolist())
print("đã thấy:", seen.tolist(), "OOB:", oob.tolist())
probabilities = np.array([0.9, 0.4, 0.4])
print("trung bình:", round(float(probabilities.mean()), 3))
print("phiếu lớp 1:", int(np.sum(probabilities > 0.5)))

Kết quảrút: [4, 3, 3, 4, 2]
đã thấy: [2, 3, 4] OOB: [0, 1]
trung bình: 0.567
phiếu lớp 1: 1

Đọc dòng “đã thấy”: số mẫu phân biệt có thể nhỏ hơn 5 dù đã rút đủ 5 lần. Với nhiều cây, mẫu 0 chỉ được chấm OOB bằng những cây không thấy mẫu 0. Có một cây không dùng nó không đủ để điểm OOB ổn định; cần nhiều cây và phải kiểm cảnh báo mẫu thiếu dự đoán OOB.

Trung bình giảm nhiễu có điều kiện

Công thức phương sai ở trên giả sử các dự đoán có cùng phương sai $\sigma^2$ và mọi cặp có cùng tương quan $\rho$. Nó là một mô hình để thấy tác dụng của sự đa dạng, không phải cách dự đoán chính xác metric của bất kỳ rừng nào. Với các dự đoán thật, ta không được tự gán $\rho=0$ chỉ vì các cây được train bằng seed khác nhau: chúng vẫn dùng chung một nguồn dữ liệu và cùng những đặc trưng mạnh.

Random forest bớt biến động nhờ trung bình hóa, nhưng không chữa được việc toàn bộ dữ liệu train sai phân phối hay một cột rò rỉ target. Tăng số cây chủ yếu làm dự đoán ổn định hơn; validation có thể dao động và một rừng lớn vẫn overfit. Tăng min_samples_leaf hoặc hạn chế độ sâu làm từng cây mượt hơn, còn giảm max_features làm các cây đa dạng hơn nhưng cũng có thể làm từng cây yếu đi. Ta chọn cân bằng bằng validation.

OOB rất tiện với các mẫu độc lập cùng phân phối. Nếu cùng một học sinh có nhiều bản ghi, cây không thấy một bản ghi nhưng có thể thấy các bản ghi khác của người đó. OOB theo hàng lúc này không thay thế group split. Với dự báo tương lai, bootstrap cũng không thay thế validation theo thời gian. Một lần chạy có OOB score cao chưa chứng minh mô hình dùng được ngoài lớp học.

Dùng thư viện

from sklearn.datasets import load_breast_cancer
from sklearn.ensemble import RandomForestClassifier
from sklearn.model_selection import cross_val_score
from sklearn.tree import DecisionTreeClassifier

X, y = load_breast_cancer(return_X_y=True)
tree = DecisionTreeClassifier(random_state=0)
forest = RandomForestClassifier(n_estimators=80, oob_score=True, n_jobs=1, random_state=0)
print("một cây:", round(cross_val_score(tree, X, y, cv=5).mean(), 3))
print("rừng:   ", round(cross_val_score(forest, X, y, cv=5).mean(), 3))
print("OOB:    ", round(forest.fit(X, y).oob_score_, 3))

Kết quảmột cây: 0.917
rừng:    0.963
OOB:     0.968

Rừng hơn một cây khoảng 4.6 điểm CV. OOB $0.968$ và CV $0.963$ là hai ước lượng khác nhau của cùng một thứ, và ở đây chúng gần nhau.