Random Forest: Khi nhiều cây quyết định cùng bỏ phiếu

Một cây quyết định (Decision Tree) có cách suy luận dễ theo dõi: đặt một câu hỏi về dữ liệu, chia các quan sát thành hai nhóm, rồi lặp lại. Tuy nhiên, cây có thể khá nhạy với dữ liệu huấn luyện. Chỉ vài quan sát thay đổi cũng có thể làm phép chia gần gốc đổi chỗ, kéo theo một cấu trúc cây khác.

Rừng ngẫu nhiên (Random Forest) xử lý điểm yếu ấy bằng một ý tưởng đơn giản: tạo nhiều cây hơi khác nhau rồi gộp dự đoán của chúng. Mỗi cây được huấn luyện trên một mẫu bootstrap, đồng thời chỉ được xét một tập con ngẫu nhiên của các đặc trưng tại mỗi nút. Với bài toán phân loại, các cây bỏ phiếu; với bài toán hồi quy, ta lấy trung bình các dự đoán.

Điều quan trọng không chỉ là có nhiều cây. Các cây còn phải đủ khác nhau để sai số của chúng không cùng xuất hiện theo một kiểu.

1. Nhắc lại từ một cây quyết định

Giả sử cần phân loại một quan sát từ hai đặc trưng $x_1,x_2$. Ở mỗi nút, cây thử những câu hỏi dạng

$$ x_j \le s, $$

trong đó $j$ là đặc trưng được xét và $s$ là ngưỡng chia. Với bài toán hai lớp, một thước đo thường dùng cho độ hỗn tạp của nút $t$ là chỉ số Gini (Gini Impurity)

$$ G(t)=1-p_0(t)^2-p_1(t)^2, $$

với $p_k(t)$ là tỷ lệ quan sát thuộc lớp $k$ trong nút. Một phép chia tạo hai nút con $L,R$ được đánh giá qua

$$ \frac{n_L}{n_t}G(L)+\frac{n_R}{n_t}G(R). $$

Cây chọn phép chia làm đại lượng này nhỏ nhất trong số các ứng viên đang được xét. Quá trình tiếp tục cho đến khi gặp điều kiện dừng như độ sâu tối đa, số quan sát tối thiểu ở nút lá, hoặc nút đã đủ thuần nhất.

Cách chia theo từng trục tạo ra các miền dự đoán hình chữ nhật. Một cây sâu có thể bám rất sát mẫu huấn luyện, kể cả những dao động ngẫu nhiên. Đây là một biểu hiện của quá khớp, nhưng không có nghĩa mọi cây sâu đều cho dự đoán ngoài mẫu kém; kết quả còn phụ thuộc dữ liệu và cách chính quy hóa cây.

Phần này chỉ nhắc nhanh viên gạch cơ sở. Bài Cây quyết định: Một câu hỏi chia đôi dữ liệu trình bày trực giác, cách chọn ngưỡng bằng chỉ số Gini và hoạt ảnh cây lớn dần trước khi đi tiếp tới cơ chế của rừng.

2. Hai lớp ngẫu nhiên tạo nên “rừng”

Với tập huấn luyện gồm $n$ quan sát và $p$ đặc trưng, một phiên bản Random Forest cho bài toán phân loại được xây dựng như sau:

1. Rút ngẫu nhiên có hoàn lại $n$ quan sát để tạo một mẫu bootstrap. Một quan sát có thể xuất hiện nhiều lần, còn một số quan sát không xuất hiện.
2. Trồng một cây quyết định trên mẫu đó. Tại mỗi nút, chỉ chọn ngẫu nhiên $m_{\text{try}}$ trong số $p$ đặc trưng, rồi tìm phép chia tốt nhất trong tập con này.
3. Lặp lại hai bước trên để có $B$ cây.
4. Khi gặp quan sát mới $x$, cho cả $B$ cây dự đoán và lấy lớp nhận nhiều phiếu nhất:

$$ \widehat y(x)=\operatorname{mode}\{T_1(x),\ldots,T_B(x)\}. $$

Trong hồi quy, phép gộp thường là trung bình

$$ \widehat f(x)=\frac{1}{B}\sum_{b=1}^{B}T_b(x). $$

Bước lấy mẫu có hoàn lại chính là ý tưởng Bootstrap dùng trong Bagging (bootstrap aggregating). Lớp ngẫu nhiên thứ hai — giới hạn đặc trưng được xét tại từng nút — làm các cây bớt giống nhau. Nếu một đặc trưng rất mạnh luôn được phép tham gia, nhiều cây có thể chọn cùng một phép chia gần gốc; khi ấy việc lấy trung bình nhiều cây tương quan cao đem lại ít lợi ích hơn.

3. Vì sao trung bình hóa có thể ổn định hơn?

Giả sử sai số của $B$ cây có cùng phương sai $\sigma^2$ và tương quan cặp xấp xỉ $\rho$. Khi đó, phương sai của trung bình có dạng gợi ý

$$ \operatorname{Var}\!\left(\frac{1}{B}\sum_{b=1}^{B}T_b\right) =\rho\sigma^2+\frac{1-\rho}{B}\sigma^2. $$

Số cây $B$ lớn làm giảm hạng thứ hai, nhưng không xóa được hạng $\rho\sigma^2$. Vì vậy Random Forest theo đuổi đồng thời hai mục tiêu:

• mỗi cây vẫn phải có năng lực dự đoán đủ tốt;
• các cây không nên mắc sai số quá giống nhau.

Chọn ít đặc trưng hơn tại mỗi nút thường giảm tương quan giữa các cây, nhưng nếu chọn quá ít thì từng cây có thể yếu đi. $m_{\text{try}}$, độ sâu, số quan sát tối thiểu ở lá và số cây đều là tham số cần đánh giá trên dữ liệu ngoài mẫu hoặc bằng một quy trình kiểm định phù hợp; không có một cấu hình tốt nhất cho mọi tập dữ liệu.

4. Sai số out-of-bag đến từ đâu?

Trong một mẫu bootstrap kích thước $n$, xác suất một quan sát cụ thể không được rút lần nào là

$$ \left(1-\frac{1}{n}\right)^n \longrightarrow e^{-1}\approx 36{,}8\%. $$

Các quan sát không xuất hiện trong mẫu huấn luyện của cây $b$ được gọi là out-of-bag (OOB) đối với cây đó. Để dự đoán OOB cho quan sát $i$, ta chỉ gộp phiếu từ những cây chưa dùng $i$ khi huấn luyện. So sánh các dự đoán này với nhãn thật cho ta một ước lượng nội bộ về sai số ngoài mẫu.

OOB hữu ích vì tận dụng ngay dữ liệu huấn luyện, nhưng không phải là phép bảo đảm cho dữ liệu tương lai. Nếu ta thử rất nhiều cách tiền xử lý hoặc siêu tham số rồi chọn cấu hình tốt nhất bằng cùng một sai số OOB, ước lượng cuối có thể trở nên lạc quan. Với quyết định quan trọng, vẫn nên giữ một tập kiểm tra độc lập hoặc dùng kiểm định lồng nhau.

5. Đọc kết quả mà không đòi hỏi quá nhiều từ mô hình

Random Forest thường là một mô hình cơ sở mạnh cho dữ liệu dạng bảng vì nó mô tả được quan hệ phi tuyến và tương tác giữa các đặc trưng mà không cần chỉ định sẵn công thức. Tuy nhiên, một vài giới hạn cần được giữ gần kết luận:

• Không ngoại suy tốt trong hồi quy: dự đoán của rừng là trung bình các giá trị ở nút lá, nên khó kéo dài một xu hướng vượt xa miền giá trị đã quan sát.
• Xác suất bỏ phiếu chưa chắc đã được hiệu chỉnh: tỷ lệ 80% số cây bỏ phiếu cho lớp B không tự động có nghĩa biến cố B xảy ra với xác suất đúng 80%.
• Độ quan trọng của đặc trưng cần được diễn giải thận trọng: các thước đo dựa trên mức giảm độ hỗn tạp có thể thiên lệch; permutation importance cũng bị ảnh hưởng khi các đặc trưng tương quan mạnh.
• Dữ liệu mất cân bằng cần thước đo phù hợp: độ chính xác tổng thể có thể che khuất việc mô hình bỏ sót lớp hiếm.
• Nhiều cây hơn chủ yếu làm phép trung bình ổn định hơn: sai số tổng quát hóa có xu hướng tiến tới một giới hạn với quy trình sinh cây cố định, chứ không được bảo đảm giảm sau mỗi cây mới.

So với hồi quy Logistic, Random Forest linh hoạt hơn về hình dạng biên quyết định nhưng khó tóm tắt bằng một bộ hệ số ngắn gọn. Lựa chọn hợp lý phụ thuộc mục tiêu: diễn giải tác động theo một cấu trúc tham số, hay dự đoán quan hệ phi tuyến với ít giả định hơn về dạng hàm.

6. Tóm tắt

Random Forest có thể được nhớ bằng ba động tác:

1. Đổi dữ liệu: mỗi cây nhận một mẫu bootstrap khác nhau.
2. Đổi góc nhìn: tại mỗi nút, cây chỉ xét một tập con ngẫu nhiên của các đặc trưng.
3. Gộp dự đoán: bỏ phiếu cho phân loại, lấy trung bình cho hồi quy.

Nguồn ngẫu nhiên thứ nhất tạo nhiều phiên bản của tập huấn luyện; nguồn thứ hai làm các cây bớt tương quan. Việc gộp dự đoán có thể giảm phương sai, nhưng hiệu quả thực tế vẫn phải được đánh giá trên dữ liệu phù hợp với mục tiêu sử dụng.

Tài liệu tham khảo

• Leo Breiman (1996), Bagging Predictors.
• Tin Kam Ho (1998), The Random Subspace Method for Constructing Decision Forests.
• Leo Breiman (2001), Random Forests.