Dùng để làm gì? Trong khai thác dữ liệu, phương pháp tối đa hóa kì vọng (EM) là thuật toán gom nhóm (clustering) dữ liệu (như k-means) được dùng trong tác vụ khám phá tri thức (knowledge discovery).
Trong thống kê, thuật toán EM lặp (iterate) và tối ưu hóa (optimize) khả năng (likelihood) nhìn thấy dữ liệu quan sát (seeing observed data) thông qua việc ước lượng tham số (parameters estimation) cho mô hình thống kê (statistical model) cho các biến không quan sát được (unobserved variables).
Mô hình thống kê là gì? một mô hình đơn giản là cách mô tả dữ liệu quan sát được tạo ra (generate) như thế nào. Ví dụ, điểm số của một học phần có dạng hình chuông nên ta giả định biến điểm số này được tạo ra từ phương trình hình chuông hay còn gọi là mô hình phân phối chuẩn (normal distribution).
Nghĩa là, nếu cho biết một điểm số, ta có thể sử dụng phân phối chuẩn này để xác định số lượng học viên đạt được cùng điểm số trên.
Tham số của mô hình là gì? tham số là đại lượng mô tả một phân phối mà ta gọi là mô hình. Ví dụ, mô hình dạng chuông có thể được mô tả bởi trung bình (mean) và phương sai (variance).
Ví dụ, phân phối điểm số có dạng hình chuông với hai tham số mean bằng 85 và variance bằng 100.
Thế likelihood là gì? trở lại ví dụ mô hình dạng chuông ban nãy, ta có một tập các điểm số và giả sử các điểm số này có phân phối chuẩn. Tuy nhiên, ta không thu thập hết điểm số của toàn trường mà chỉ lấy mẫu một số lớp.
Do đó, ta không biết chính xác hai tham số mean và variance của mô hình này nhưng ta có thể ước lượng chúng dựa vào mẫu dữ liệu cho trước. Likelihood là xác suất mà phương trình hình chuông với ước lượng mean và variance từ mẫu dữ liệu cho trước.
Nói cách khác, cho trước các mẫu dữ liệu quan sát, ta ước lượng các tham số của mô hình. Sử dụng các tham số ước lượng được để giả định phân phối của mô hình được gọi là likelihood.
Dữ liệu quan sát được (observed data) và dữ liệu không quan sát được (unobserved data) khác nhau chỗ nào? dữ liệu quan sát được là dữ liệu ta nhìn thấy hay thu thập được. Dữ liệu không quan sát được là dữ liệu đang thiếu. Có nhiều lý do dữ liệu bị thiếu (không thu thập được, bị bỏ qua, …).
Trong khai thác và gom nhóm dữ liệu, điều quan trong là chúng ta có thể dự đoán được các điểm dữ liệu bị thiếu. Ta không biết nhóm dữ liệu này ra sao, do đó việc dự đoán được các điểm dữ liệu bị thiếu là vai trò của thuật toán EM dành cho tác vụ gom nhóm.
Nhắc lại: thuật toán EM lặp (iterate) và tối ưu hóa (optimize) khả năng (likelihood) nhìn thấy dữ liệu quan sát (seeing observed data) thông qua việc ước lượng tham số (parameters estimation) cho mô hình thống kê (statistical model) cho các biến không quan sát được (unobserved variables).
Bằng việc tối ưu hóa likelihood, EM tạo ra một mô hình có thể gán nhãn lớp (class labels) cho các điểm dữ liệu, nghe có vẻ giống phương pháp gom nhóm phải không nào.
EM làm gì trong quá trình gom nhóm? EM bắt đầu bằng các tham số cho mô hình dự đoán. Sau đó thực hiện vòng lặp 3 tiến trình sau:
- E-step: dựa trên các tham số của mô hình, tính toán các xác suất gán nhãn các điểm dữ liệu vào một nhóm.
- M-step: cập nhật các tham số của mô hình dựa trên các nhóm gom được từ E-step.
- Lặp cho đến khi các tham số của mô hình và các nhóm gom được ổn định hay hội tụ.
Tại sao dùng EM? điểm then chốt của EM đó là sự dễ hiểu và cài đặt dễ dàng. Thêm vào đó, không chỉ tối ưu hóa được các tham số của mô hình, nó còn có thể dự đoán cho các dữ liệu bị thiếu xuyên suốt quá trình lặp.
Phương pháp này hữu ích cho tác vụ gom nhóm và hình thành mô hình qua các tham số. Khi biết được các nhóm và tham số của mô hình, ta có thể suy luận ra điểm dữ liệu mới thuộc về nhóm nào.
EM cũng có một vài điểm hạn chế
- Thứ nhất, EM chạy nhanh ở các vòng lặp ban đầu nhưng chậm hơn ở các vòng lặp sau.
- Thứ hai, EM không phải lúc nào cũng tìm được tham số tối ưu và bị mắc kẹt ở điểm tối ưu cục bộ (local optima) thay vì toàn cục (global optima).
Các thư viên nào cho EM? Ta có thể áp dụng thuật toán EM thông qua Weka. R cũng có thư viện cài đặt EM là mclust package. scikit-learn cũng cài đặt thư viện gmm module.
Nguồn tham khảo:
Ông Xuân Hồng 