Tuyển tập Hội nghị Khoa học thường niên năm 2015. ISBN : 978-604-82-1710-5
112
XÂY DỰNG MỘT PHƯƠNG PHÁP HỌC TẬP THỂ MỚI
DỰA TRÊN PHÉP CHIẾU NGẪU NHIÊN
Phạm Xuân Cường
1Đại học Thủy lợi Hà Nội, email: cuongpx@tlu.edu.vn
1. GIỚI THIỆU CHUNG
Phương pháp học tập thể (ensemble
method) hiện nay đang nhận được nhiều sự
quan tâm của công đồng học máy bởi ưu
điểm của phương pháp trong việc cải thiện
hiệu quả phân lớp so với từng phân lớp thành
phần của nó [1]. Dựa trên phân loại trong [1],
học tập thể được chia làm hai loại:
• Học tập thể không thuần nhất;
• Học tập thể thuần nhất.
Trong bài báo này, tác giả tập trung nghiên
cứu mô hình học tập thể thuần nhất. Đó là mô
hình học tập thể trong đó sử dụng chỉ một
giải thuật học (learning algorithm) nhưng làm
việc trên các lược đồ dữ liệu (training set
schemes) khác nhau được sinh ra từ tập
luyện. Một giải thuật kết hợp sẽ kết hợp kết
quả của các phân lớp để đưa ra mô hình phân
loại. Một số phương pháp học tập thể thuần
nhất được biết đến rộng rãi gồm có AdaBoost
[2], Bagging [3], Random Forest [4] và
Random Subspace [5]. Mặc dù các giải thuật
này đạt được hiệu quả phân lớp tốt trong các
ứng dụng thực tế nhưng chúng vẫn còn tồn
tại một số nhược điểm. Đầu tiên là khả năng
làm việc với dữ liệu số chiều lớn trong thực
tế ứng dụng. Tiếp đó là hạn chế trong việc sử
dụng các giải thuật học để xây dựng các phân
lớp. Ví dụ như Bagging chỉ làm việc với các
giải thuật học không ổn định (unstable
learning algorithms) như cây quyết định
(Decision Tree, kí hiệu bởi DT) xuất phát từ
việc sử dụng thủ tục Bootstrap trong việc
sinh ra các lược đồ dữ liệu. Trong bài báo
này tác giả giới thiệu một phương pháp học
tập thể mới làm việc tốt với dữ liệu số chiều
cao đồng thời làm việc với nhiều hơn các giải
thuật học đã có. Phương pháp mới xuất phát
từ một định lý nổi tiếng được Jonhson và
Lindenstrauss công bố vào năm 1984 [6].
Định lý chỉ ra với một xác suất cho trước, tồn
tại một ánh xạ tuyến tính ánh xạ dữ liệu từ
không gian ban đầu vào không gian đích mà
bảo toàn khoảng cách giữa các cặp điểm với
độ biến dạng (distort level)1 ± 𝜀 (0 < 𝜀 <
1 cho trước). Hơn nữa số chiều giới hạn 𝑞0
để đạt được tính chất trên chỉ phụ thuộc vào
số quan sát mà không phụ thuộc vào số chiều
của không gian gốc. Dựa vào tính chất này ta
có thể làm giảm số chiều dữ liệu gốc mà vẫn
bảo tồn khoảng cách giữa các cặp điểm với
độ sai lệch nào đó. Việc thực hiện nhiều ánh
xạ tuyến tính khác nhau trên tập dữ liệu gốc
sẽ giúp tạo ra các lược đồ dữ liệu và từ đó có
thể xây dựng một mô hình học tập thể bằng
phương pháp này.
2. PHƯƠNG PHÁP NGHIÊN CỨU
Trong bài báo này tác giả sử dụng kết quả
từ định lý JL để xây dựng một phương pháp
học tập thể mới. Dựa vào kết quả trong [7],
ánh xạ tuyến tính T có thể được xây dựng từ
các ma trận ngẫu nhiên 𝐑. Một trong các
phương pháp đó là 𝐑 = 1 √𝑞
⁄{𝑟𝑖𝑗}(𝑝 × 𝑞)
trong đó 𝑟𝑖𝑗 có phân phối chuẩn 𝒩(0,1). Từ
kết quả này, tác giả tạo ra 𝐾 ma trận ngẫu
nhiên 𝐑𝑘(𝑘 = 1,…,𝐾) rồi tạo ra các lược đồ
dữ liệu từ tập luyện (training set) 𝒟(𝑛 × 𝑝)
ban đầu: 𝐘𝑘= 𝒟𝐑𝑘. Các 𝐘𝑘(𝑛 × 𝑞) với giá trị
𝑛 phù hợp sẽ có số chiều 𝑞 thấp hơn số chiều
của tập luyện 𝒟. Và khi thỏa mãn điều kiện
của Định lý JL, khoảng cách giữa các phần tử
Tuyển tập Hội nghị Khoa học thường niên năm 2015. ISBN: 978-604-82-1710-5
113
được bảo tồn với độ sai lệch cho trước. Tác giả
lựa chọn số chiều giới hạn 𝑞0 từ nghiên cứu
trong [7] trong đó giá trị này nhỏ hơn giá trị
trong Định lý JL đồng thời tính chất khoảng
cách giữa các cặp phần tử vẫn đúng:
𝑞 ≥ 𝑞0=[2×ln(𝑛)
𝜀2] (1)
Một giải thuật học có giám sát sẽ học các
phân lớp (classifier) 𝐶𝑘 trên 𝐾 lược đồ dữ
liệu mới. Đầu ra của quá trình luyện (training
process) chính là 𝐾 phân lớp và 𝐾 phép chiếu
ngẫu nhiên 𝐑𝑘.
Để gán nhãn cho một quan sát 𝐱, đầu tiên x
được chiếu xuống các không gian số chiều
thấp hơn dựa trên các phép chiếu ngẫu nhiên
𝐑𝑘: 𝐲𝑘= 𝐱𝐑𝑘. Các 𝐲𝑘 sau đó lần lượt được
phân lớp với các 𝐶𝑘 tương ứng với phép
chiếu 𝐑𝑘. Kết quả thu được là véc tơ xác suất
hậu nghiệm.
{P𝑘(𝑐𝑙𝑎𝑠𝑠1|𝐱),…,P𝑘(𝑐𝑙𝑎𝑠𝑠𝑀|𝐱)} (2)
Trong đó P𝑘(𝑐𝑙𝑎𝑠𝑠𝑖|𝐱) là xác suất để
𝐱 thuộc vào lớp thứ 𝑖 cho bởi phân lớp 𝐶𝑘.
Trong bài báo này tác giả sử dụng phương
pháp kết hợp tổng (Sum Rule) [8] để kết hợp
kết quả của các phân lớp 𝐶𝑘. Cụ thể:
𝑥 ∈ 𝑐𝑙𝑎𝑠𝑠𝑗 nếu
𝑗 = argmax𝑚=1,…,𝑀 ∑P𝑘(𝑐𝑙𝑎𝑠𝑠𝑚|𝐱)
𝐾
𝑘=1 (3)
3. KẾT QUẢ NGHIÊN CỨU
Vì giới hạn về nội dung trình bày nên trong
khuôn khổ bài báo này tác giả chỉ tiến hành thử
nghiệm phương pháp đề xuất trên một dữ liệu
được sinh ra từ mô hình phân phối chuẩn hỗn
hợp (Gaussian mixture model). Dữ liệu bao
gồm 1000 quan sát được sinh ra từ mô hình
phân phối chuẩn hỗn hợp gồmba thành phần
với tỷ lệ các thành phần bằng nhau. Véc tơ
trung bình của các thành phần lần lượt là
{1 2
⁄,…,1 2
⁄ }1000;{0,…,0}1000, và
{−1 2
⁄,…,−1 2
⁄ }1000 trong khi đó các ma
trận hiệp phương sai tương ứng là các ma
trận đường chéo có dạng:
diag{1,…,1}1000,diag{2,…,2}1000,
và diag{3,…,3}1000.
Để đánh giá hiệu quả của phương pháp đề
xuất, tác giả tiến hành thực nghiệm và so
sánh với các phương pháp phân lớp phổ biến
khác. Vì mô hình đề xuất là một mô hình học
tập thể thuần nhất nên mô hình này cần được
so sánh với các mô hình thuần nhất khác. Tác
giả lựa chọn 4 mô hình học tập thể thuần nhất
tiêu biểu là Bagging [3], Adaboost [2],
Random Forest [4] và Random Subspace [5]
để so sánh với mô hình đề xuất. Tác giả tham
khảo từ [1] và lựa chọn DT là giải thuật học
để từ đó học 200 phân lớp cho mô hình học
tập thể kể trên. Việc lựa chọn DT xuất phát
từ nhận xét trong [1], trong đó các tác giả chỉ
ra đây là giải thuật học phổ biến được dùng
cho các phương pháp học tập thể ở trên. Bên
cạnh đó, mô hình đề xuất cũng được so sánh
với các phương pháp học có giám sát khác
như Discriminative Restricted Boltzmann
Machine [9] (kí hiệu bởi DRBM), DT và
Linear Discriminative Analysis (kí hiệu
bởi LDA).
Bảng 1. Trung bình sai số và phương sai
các phân lớp trong thử nghiệm
Phương pháp
Trung bình
Phương sai
Bagging
0.0798
6.50E-04
Adaboost
0.2502
1.25E-03
Random Forest
0.3149
2.07E-03
Random Subspace
0.6293
6.51E-06
DRBM
0.0095
1.31E-04
DT
0.3992
2.36E-03
LDA
0.0516
4.29E-04
Phương pháp đề xuất
0.0000
0.00E+00
Tác giả lựa chọn số chiều đích bằng với
giá trị ⌈𝑞0⌉= 222 (1) đồng thời cố định số
phép chiếu là 200 tương tự như thử nghiệm
với các phương pháp học tập thể khác. Tác
giả thực hiện thủ tục 10-fold cross validation
và lặp lại quá trình kiểm tra 10 lần để từ đó
thu được 100 kết quả thử nghiệm. Để so sánh
kết quả giữa các phương pháp, tác giả sử dụng
kiểm định Student dựa trên 2 mẫu (two-sample
t-test) với mức ý nghĩa 0.05. Kết quả thử
nghiệm bao gồm giá trị trung bình và phương
sai của sai số phân lớp tính trên 100 kết quả
thử nghiệm được minh họa trong bảng 1.
Tuyển tập Hội nghị Khoa học thường niên năm 2015. ISBN : 978-604-82-1710-5
114
Kết quả kiểm định cho thấy phương pháp
học tập thể dựa trên phép chiếu ngẫu nhiên
đạt được độ chính xác cao hơn tất cả các
phương pháp học khác. Cụ thể phương pháp
đề xuất tốt hơn các phương pháp học tập thể
thuần nhất như Bagging hay tốt hơn rất nhiều
so với AdaBoost, Random Forest và Random
Subspace. Cũng tương tự như trên, mô hình
đề xuất cũng tốt hơn so với các giải thuật học
có giám sát khác như DRBM, DT và LDA.
Đó là do trong khi các phương pháp khác làm
việc trực tiếp trên dữ liệu đầu vào số chiều
lớn thì phương pháp đề xuất tạo ra những
lược đồ dữ liệu mới từ tập luyện ban đầu với
số chiều ⌈𝑞0⌉=222 nhỏ hơn so với số chiều
của dữ liệu gốc.
4. KẾT LUẬN
Trong bài báo này, tác giả đã giới thiệu
một mô hình học tập thể mới sử dụng các
phép chiếu ngẫu nhiên. Kết quả kiểm định
thống kê dựa trên kết quả thử nghiệm trên
một dữ liệu mô phỏng cho thấy mô hình học
tập thể thuần nhất mới này tốt hơn so các mô
hình học tập thể phổ biến cũng như các
phương pháp học có giám sát khác. Tuy
nhiên vì số chiều giới hạn 𝑞0 phụ thuộc vào
số quan sát 𝑛 nên với giá trị 𝑛 lớn, 𝑞0 có thể
vượt quá số chiều của không gian gốc. Điều
này dẫn đến hạn chế khi áp dụng với các loại
dữ liệu khác nhau. Nghiên cứu về phép chiếu
ngẫu nhiên với bài toán phân lớp trong
trường hợp số chiều nhỏ hơn 𝑞0 vẫn còn là
vấn đề mở. Bên cạnh đó phương pháp đề
xuất kết hợp với các thuật toán lựa chọn đặc
trưng sẽ cho hiệu quả phân lớp tốt hơn.
5. TÀI LIỆU THAM KHẢO
[1] T.T. Nguyen, T.T.T. Nguyen, X.C. Pham,
A.W-C. Liew, 2015, A Novel Combining
Classifier Method based on Variational
Inference, Pattern Recognition.
[2] Y. Freund, R.E. Schapire, 1996,
Experiments with a new boosting algorithm,
in: Proceedings of International Conference
on Machine Learning (ICML), pp. 148-156.
[3] L. Breiman, 1996, Bagging Predictors,
Machine Learning. 24, 123-140.
[4] L. Breiman, 2001, Random Forest, Machine
Learning. 45, 5-32.
[5] T.K. Ho, 1998, The random subspace
method for constructing decision forests,
IEEE Transactions on Pattern Analysis and
Machine Intelligence. 20(8), 832-844.
[6] W. Johnson, J. Lindenstrauss, 1984
Extensions of Lipshitz mapping into Hilbert
space, Conference in modern analysis and
probability. 26, pp. 189-206
[7] S. Venkatasubramanian, Q. Wang, 2011,
The Johnson-Lindenstrauss transform: An
empirical study, in Proc. ALENEX, SIAM,
pp. 164-173.
[8] J. Kittler, M. Hatef, R.P.W. Duin, J. Matas,
1998, On Combining Classifiers, IEEE
Transactions on Pattern Analysis and
Machine Intelligence. 20(3), 226-239.
[9] H. Larochelle, Y. Bengio,2008,
Classification using Discriminative
Restricted Boltzmann Machines, in:
Proceedings of the 25th International
Conference on Machine Learning (ICML),
pp. 536-543.