Bài giảng Học máy - Bài 6: Các phương pháp học máy kết hợp - Nguyễn Thanh Tùng

Các phương pháp học máy
kết hợp
Boosting, Bagging, và Random Forests
Bài giảng có sử dụng hình vẽ trong cuốn sách “An Introduction to Statistical Learning with Applications in R” với sự
cho phép của tác giả, có sử dụng slides các khóa học CME250 của ĐH Stanford và IOM530 của ĐH Southern California
Nguyễn Thanh Tùng
Khoa Công nghệ thông tin – Đại học Thủy Lợi
tungnt@tlu.edu.vn
Website môn học: https://sites.google.com/a/wru.vn/cse445fall2016
CSE 445: Học máy | Học kỳ 1, 2016-2017 1
Bootstrap là gì?
2CSE 445: Học máy | Học kỳ 1, 2016-2017
• Giả sử ta có 5 quả bóng gắn nhãn A,B,C,D, E và bỏ tất cả chúng vào trong 1 
cái giỏ.
• Lấy ra ngẫu nhiên 1 quả từ giỏ và ghi lại nhãn, sau đó bỏ lại quả bóng vừa 
bốc được vào giỏ.
• Tiếp tục lấy ra ngẫu nhiên một quả bóng và lặp lại quá trình trên cho đến khi
việc lấy mẫu kết thúc. Việc lấy mẫu này gọi là lấy mẫu có hoàn lại. 
• Kết quả của việc lấy mẫu như trên có thể như sau (giả sử kích thước mẫu là 
10):
C, D, E, E, A, B, C, B, A, E
Nguồn: bis.net.vn/forums
Bootstrap là gì?
CSE 445: Học máy | Học kỳ 1, 2016-2017 3
• Bootstrap là phương 
pháp lấy mẫu có hoàn lại 
(sampling with 
replacement)-> một 
mẫu có thể xuất hiện 
nhiều lần trong một lần 
lấy mẫu
Bootstrap là gì?
• Là kỹ thuật rất quan trọng trong thống kê
• Lấy mẫu có hoàn lại từ tập dữ liệu ban 
đầu để tạo ra các tập dữ liệu mới
CSE 445: Học máy | Học kỳ 1, 2016-2017 4
Các phương pháp kết hợp
Ensemble Methods
CSE 445: Học máy | Học kỳ 1, 2016-2017 5
Sức mạnh của các bộ phân lớp yếu
CSE 445: Học máy | Học kỳ 1, 2016-2017 6
Condorcet’s Jury Theorem – Nếu p lớn
hơn 1/2 (mỗi cử tri bỏ phiếu đúng mong muốn của họ), càng
thêm nhiều cử tri sẽ tăng xác suất theo quyết định số đông sẽ
chính xác. Trong giới hạn, xác suất bầu chọn theo số đông tiến
đến 1 khi số cử tri tăng lên.
Sức mạnh của các bộ phân lớp yếu
CSE 445: Học máy | Học kỳ 1, 2016-2017 7
Condorcet’s Jury Theorem – Nếu p lớn
hơn 1/2 (mỗi cử tri bỏ phiếu đúng mong muốn của họ), càng
thêm nhiều cử tri sẽ tăng xác suất theo quyết định số đông sẽ
chính xác. Trong giới hạn, xác suất bầu chọn theo số đông tiến
đến 1 khi số cử tri tăng lên.
Sức mạnh của các bộ phân lớp yếu
• Việc lấy trung bình làm giảm phương sai và không làm tăng bias (bias vẫn
được giữ nguyên) Var[Ȳ] = σ2/n
CSE 445: Học máy | Học kỳ 1, 2016-2017 8
Sức mạnh của các bộ phân lớp yếu
• Việc lấy trung bình làm giảm phương sai và không làm tăng bias (bias vẫn
được giữ nguyên) Var[Ȳ] = σ2/n
• Các phiếu bầu của các bộ phân lớp tương quan không trợ giúp được
nhiều
CSE 445: Học máy | Học kỳ 1, 2016-2017 9
Sức mạnh của các bộ phân lớp yếu
• Việc lấy trung bình làm giảm phương sai và không làm tăng bias (bias vẫn
được giữ nguyên) Var[Ȳ] = σ2/n
• Các phiếu bầu của các bộ phân lớp tương quan không trợ giúp được
nhiều Var[Ȳ] = σ2/n + (ρσ2)(n-1)/n
CSE 445: Học máy | Học kỳ 1, 2016-2017 10
Kết hợp các bộ phân lớp
α×{CART}+ (1−α)×{LinearModel}
CSE 445: Học máy | Học kỳ 1, 2016-2017 11
Các phương pháp kết hợp: Bagging
CSE 445: Học máy | Học kỳ 1, 2016-2017 12
+ +
Bagging là gì?
“Bootstrap Aggregation”
CSE 445: Học máy | Học kỳ 1, 2016-2017 13
Bagging là gì?
“Bootstrap Aggregation”
CSE 445: Học máy | Học kỳ 1, 2016-2017 14
+ +
Bagging
Giải quyết được tính thiếu ổn
định của CART
CSE 445: Học máy | Học kỳ 1, 2016-2017 15
• Lấy mẫu tập dữ liệu huấn
luyện theo Bootstrap để tạo ra
tập hợp các dự đoán.
Bagging
CSE 445: Học máy | Học kỳ 1, 2016-2017 16
• Lấy mẫu tập dữ liệu huấn luyện theo Bootstrap để tạo ra tập hợp các dự đoán.
Hastie, Trevor, et al. The elements of statistical learning. Vol. 2. No. 1. New 
York: Springer, 2009.
• Lấy trung bình (hoặc bình chọn theo số đông- majority vote) các bộ dự đoán
độc lập.
• Bagging giảm phương sai (variance) và giữ bias.
Bagging
CSE 445: Học máy | Học kỳ 1, 2016-2017 17
Bagging
Hastie, Trevor, et al. The 
elements of statistical 
learning. Vol. 2. No. 1. New
York: Springer,2009.
CSE 445: Học máy | Học kỳ 1, 2016-2017 18
Bagging
• Lấy mẫu có hoàn lại
• Xây dựng bộ phân lớp trên mỗi mẫu bootstrap 
• Mỗi mẫu bootstrap chứa xấp xỉ 63.2% số lượng mẫu trong
tập dữ liệu ban đầu
• Số lượng mẫu còn lại (36.8%) được dùng để kiểm thử
Original Data 1 2 3 4 5 6 7 8 9 10
Bagging (Round 1) 7 8 10 8 2 5 10 10 5 9
Bagging (Round 2) 1 4 9 1 2 3 2 7 3 2
Bagging (Round 3) 1 8 5 10 5 5 9 6 3 7
CSE 445: Học máy | Học kỳ 1, 2016-2017 19
Bagging
CSE 445: Học máy | Học kỳ 1, 2016-2017 20
Bonus! Out-of-bag cross-validation
CSE 445: Học máy | Học kỳ 1, 2016-2017 21
Các mẫu Out-of-bag (OOB)
• Mỗi cây chỉ sử dụng một tập con các mẫu huấn
luyện (trung bình số mẫu ~2/3).
• Số mẫu cho OOB khoảng ~1/3 của cây quyết định.
• Quá trình Bootstrapping:
CSE 445: Học máy | Học kỳ 1, 2016-2017 22
• Với mỗi mẫu, tìm các cây mà nó là OOB.
• Dự đoán giá trị của chúng từ các cây này.
• Ước lượng lỗi dự đoán của cây (bagged trees) dùng tất cả
các dự đoán OOB.
• Tương tự như kỹ thuật kiểm tra chéo (cross-validation).
CSE 445: Học máy | Học kỳ 1, 2016-2017 23
Dự đoán mẫu OOB
Các phương pháp kết hợp: Boosting
CSE 445: Học máy | Học kỳ 1, 2016-2017 24
Boosting là gì?
• Boosting là kỹ thuật mới nâng cao hiệu suất của mô hình
phân lớp
• Các thí nghiệm cho thấy boosting có thể tăng thêm độ
chính xác của mô hình phân lớp lên 15%
• Tất cả các mô hình phân lớp học có giám sát đều có thể
dùng kỹ thuật boosting để nâng cao độ chính xác
CSE 445: Học máy | Học kỳ 1, 2016-2017 25
Boosting là gì?
• Boosting xây dựng bộ phân loại kết hợp với các mẫu huấn luyện có trọng số
khác nhau. Sau mỗi bước lặp, các mẫu huấn luyện bị dự đoán sai sẽ được
đánh trọng số tăng lên, các mẫu đã dự đoán đúng sẽ được đánh trọng số
nhỏ hơn
• Điều này giúp cho Boosting tập trung vào cải thiện độ chính xác cho các mẫu
bị dự đoán sai sau mỗi bước lặp
CSE 445: Học máy | Học kỳ 1, 2016-2017 26
Độ quan trọng của tỷ lệ lỗi học, λ.
Mô hình 1 Mô hình
thứ b
Mô hình 2
Lấy mẫu Lấy mẫu Lấy mẫu
Boosting
CSE 445: Học máy | Học kỳ 1, 2016-2017 27
AdaBoost with trees has been called the
“best off-the-shelf classifier in the world”
-Leo Breiman
Boosting
Tham số đầu vào,
λ “learning rate”
B # of trees
d “interaction depth”
CSE 445: Học máy | Học kỳ 1, 2016-2017 28
Boosting vs. Bagging
Hastie, Trevor, et al. The elements of statistical learning. Vol. 2. No. 1. New York: Springer,2009.
CSE 445: Học máy | Học kỳ 1, 2016-2017 29
Câu hỏi?
CSE 445: Học máy | Học kỳ 1, 2016-2017 30
Phương pháp Rừng ngẫu nhiên
Random Forests (RF)
CSE 445: Học máy | Học kỳ 1, 2016-2017 31
• Mô hình dựa trên cây phân loại và hồi quy (CART).
• Các mô hình cây có lỗi bias thấp, tuy nhiên phương sai lại
cao (high variance).
• Phương pháp Bagging dùng để giảm phương sai.
CSE 445: Học máy | Học kỳ 1, 2016-2017 32
Động lực để có Random forest
• Lấy mẫu tập dữ liệu huấn luyện theo Bootstrap để tạo ra tập hợp
các dự đoán.
Hastie, Trevor, et al. The elements of statistical 
learning. Vol. 2. No. 1. New York: Springer, 2009.
• Lấy trung bình (hoặc bình chọn theo số đông-
majority vote) các bộ dự đoán độc lập.
• Bagging giảm phương sai (variance) và giữ bias.
CSE 445: Học máy | Học kỳ 1, 2016-2017 33
Nhắc lại: Bagging
• Phương pháp Bagging biểu thị sự biến thiên (variability) giữa
các cây bởi việc chọn mẫu ngẫu nhiên từ dữ liệu huấn luyện.
• Cây được sinh ra từ phương pháp Bagging vẫn có tương
quan lẫn nhau, do đó hạn chế trong việc giảm phương sai.
Random forests đưa ra thêm tính ngẫu nhiên (randomness):
• Làm giảm mối tương quan giữa các cây bằng cách lấy ngẫu
nhiên các biến khi tách nút của cây.
CSE 445: Học máy | Học kỳ 1, 2016-2017 34
Bagged trees vs. random forests
Số lượng biến dùng để tách nút (khả tách)
Lấy thuộc tính ngẫu nhiên
CSE 445: Học máy | Học kỳ 1, 2016-2017 35
Các biến dùng cho tách nút
Hastie, Trevor, et al. The elements of statistical 
learning. Vol. 2. No. 1. New York: Springer, 2009.
CSE 445: Học máy | Học kỳ 1, 2016-2017 36
Các biến dùng cho tách nút
Rừng ngẫu nhiên
Tập dữ liệu huấn luyện
....D1 D2 DK-1 D K
D
Bước 2:
Sử dụng các tập con dữ liệu
lấy mẫu ngẫu nhiên để xây
dựng cây TK-1 TK
T *
Bước 3:
Kết hợp các cây
Lấy ngẫu
nhiên
Bước 1:
Tạo dữ liệu ngẫu nhiên
(mẫu bootstrap)
T1 T2
D =(Xi, Yi), i=1..p
p: #chiều, N: #mẫu
Introduction to Data Mining – Tan, Steinbach, Kumar
•Phân lớp: Bình chọn theo số đông
•Hồi quy: Lấy trung bình giá trị dự
đoán từ các cây Ti (i=1..K)
CSE 445: Học máy | Học kỳ 1, 2016-2017 37
Rừng ngẫu nhiên
38CSE 445: Học máy | Học kỳ 1, 2016-2017
Các tham số quan trọng của Rừng ngẫu nhiên:
• Số lượng biến khả tách tại mỗi nút ( )
• Độ sâu của từng cây trong rừng (số lượng mẫu tối thiểu
tại mỗi nút của cây-minimum node size)
• Số lượng cây trong rừng
CSE 445: Học máy | Học kỳ 1, 2016-2017 39
Các tham số chính
Bài toán phân lớp
Bài toán hồi quy
Giá trị mặc định
=
=
CSE 445: Học máy | Học kỳ 1, 2016-2017 40
Số lượng biến khả tách
gói randomForest trong R dùng mtry
Hastie, Trevor, et al. The elements of statistical 
learning. Vol. 2. No. 1. New York: Springer, 2009.
CSE 445: Học máy | Học kỳ 1, 2016-2017 41
Độ sâu của từng cây 
(số lượng mẫu tối thiểu tại mỗi nút của cây)
15
CSE 445: Học máy | Học kỳ 1, 2016-2017 42
Bài toán phân lớp
Bài toán hồi quy
Giá trị mặc định
Độ sâu của cây
Hastie, Trevor, et al. The elements of statistical 
learning. Vol. 2. No. 1. New York: Springer, 2009.
• Thêm nhiều cây không gây ra overfitting.
CSE 445: Học máy | Học kỳ 1, 2016-2017 43
Số lượng cây trong rừng
• Các mẫu Out-of-bag (OOB)
• Độ quan trọng của biến (Variable 
importance measurements)
CSE 445: Học máy | Học kỳ 1, 2016-2017 44
Các tính năng khác của RF
Dạng 1:
Độ giảm của lỗi dự đoán hoặc impurity từ các điểm tách nút
liên quan đến các biến đó, cuối cùng lấy trung bình trên các
cây trong rừng.
CSE 445: Học máy | Học kỳ 1, 2016-2017 45
Độ quan trọng của biến
Dạng 2:
Độ tăng lỗi dự đoán tổng thể khi các giá trị của biến được
hoán vị ngẫu nhiên giữa các mẫu.
CSE 445: Học máy | Học kỳ 1, 2016-2017 46
Độ quan trọng của biến
Hastie, Trevor, et al. The elements of statistical learning. Vol. 2. No. 1. New York: Springer, 2009.
• Cả 2 dạng biểu thị gần giống nhau, tuy nhiên có sự
khác biệt về xếp hạng các biến:
Dạng 1 Dạng 2
CSE 445: Học máy | Học kỳ 1, 2016-2017 47
Ví dụ về độ quan trọng của biến
Tương tự như CART:
• Tương đối mạnh trong việc xử lý biến rác
(non-informative variable)
(Việc lựa chọn biến tích hợp sẵn khi xây
dựng mô hình, built-in variable selection)
CSE 445: Học máy | Học kỳ 1, 2016-2017 48
Ưu điểm của RF
Hastie, Trevor, et al. The elements of statistical 
learning. Vol. 2. No. 1. New York: Springer, 2009.
CSE 445: Học máy | Học kỳ 1, 2016-2017 49
Ảnh hưởng của biến rác
Tương tự như CART:
• Tương đối mạnh trong việc xử lý biến rác (non-informative variable)
• Xử lý (nắm bắt) được độ tương tác bậc cao giữa các biến (Capture 
high-order interactions between variables)
• Có lỗi bias thấp
• Dễ xử lý các biến hỗn hợp (biến rời rạc, phân loại)
CSE 445: Học máy | Học kỳ 1, 2016-2017 50
Ưu điểm của RF
Ưu điểm vượt trội CART:
• Lỗi phương sai thấp hơn (mạnh hơn vì sử dụng phương pháp
bootstrapping lấy mẫu từ tập huấn luyện)
• Ít bị overfitting hơn
• Không cần tỉa cây (No need for pruning)
• Kiểm tra chéo được tích hợp sẵn trong mô hình (dùng các mẫu
OOB)
CSE 445: Học máy | Học kỳ 1, 2016-2017 51
Ưu điểm của RF
Tương tự như CART:
• Khó nắm bắt độ cộng tính
Nhược điểm so với CART:
• Khó diễn giải/giải thích mô hình dự đoán
CSE 445: Học máy | Học kỳ 1, 2016-2017 52
Nhược điểm của RF
CSE 445: Học máy | Học kỳ 1, 2016-2017 53
Câu hỏi?