Thuật toán cực đại hóa kỳ vọng

Thuật toán cực đại hóa kỳ vọng (tiếng Anh hay được gọi là EM viết tắt của Expectation-Maximization) là một kỹ thuật được dùng rộng rãi trong thống kê và học máy để giải bài toán tìm hợp lý cực đại (MLE) hoặc hậu nghiệm cực đại (MAP) của một mô hình xác suất có các biến ẩn. EM sở dĩ được gọi vậy một phần do thuật toán này bao gồm việc thực hiện liên tiếp tại mỗi vòng lặp 2 quá trình (E): tính kỳ vọng của hàm hợp lý của giá trị các ẩn biến dựa theo ước lượng đang có về các tham số của mô hình và (M): ước lượng tham số của mô hình để cực đại hóa giá trị của hàm tính được ở (E). Các giá trị tìm được ở (E) và (M) tại mỗi vòng lặp sẽ được dùng cho việc tính toán ở vòng lặp kế tiếp.

Lịch sử

Năm 1977, ba nhà khoa học máy tính Arthur Dempster, Nan Laird, and Donald Rubin viết một bài báo giới thiệu về thuật toán EM và các tính chất và áp dụng của nó trong bài toán hợp lý cực đại trong trường hợp dữ liệu không đầy đủ (thiếu dữ liệu hoặc có chứa biến ẩn) qua đó phổ biến tên gọi trên. Dù sao, các tác giả có ghi lưu ý rằng ý tưởng trên đã xuất hiện ở một số công trình của nhiều ngành khác nhau từ trước đó.

Giới thiệu

Trong thống kê học, nếu một mô hình xác suất có chứa các biến ẩn hoặc thiếu dữ liệu thì việc tính toán ước lượng của các tham số trở nên khó khăn hoặc không thực hiện được. Thật vậy, thông thường ta cần một trong 2 đại lượng trên (biến ẩn và tham số) để ước lượng giá trị của cái còn lại.

Giải thuật EM cho ta một phương pháp giải quyết bài toán trên một lớp bài toán tương đối rộng. Nguyên lý của nó là tại mỗi bước (E) ta giả thiết rằng tham số đã biết và cố gắng ước lượng giá trị của biến ẩn này và dùng giá trị tìm được này ở bước (M) để tìm giá trị của các tham số. Ta có thể chứng minh được rằng tại mỗi vòng lặp, ta luôn tìm được kết quả tốt hơn của vòng lặp trước đó, vì thế EM luôn hội tụ về giá trị tối ưu (địa phương).

Phát biểu bài toán

Xét một mô hình thống kê bao gồm 1 tập dữ liệu quan sát được $\mathbf {X}$, 1 tập dữ liệu bị thiếu hoặc ẩn biến $\mathbf {Z}$ và 1 vector tham số ${\boldsymbol {\theta }}$, cùng hàm số hợp lý (likelihood) $L({\boldsymbol {\theta }};\mathbf {X} ,\mathbf {Z} )=p(\mathbf {X} ,\mathbf {Z} |{\boldsymbol {\theta }})$.

Đầu tiên giải thuật EM sẽ gán ${\boldsymbol {\theta }}$ với một bộ giá trị khởi điểm. Sau đó, EM sẽ tuần tự thực hiện các vòng lặp bằng cách áp dụng tại mỗi vòng 2 bước sau: Tại vòng lặp thứ $t+1,t\geq 0$:

• (E): Tính kỳ vọng của log hàm hợp lý (log-likelihood) của phân phối có điều kiện của $\mathbf {Z}$ cho trước giá trị của $\mathbf {X}$ và ước lượng của ${\boldsymbol {\theta }}^{(t)}$ có được ở vòng sát trước: $Q({\boldsymbol {\theta }}|{\boldsymbol {\theta }}^{(t)})=\operatorname {E} _{\mathbf {Z} |\mathbf {X} ,{\boldsymbol {\theta }}^{(t)}}\left[\log L({\boldsymbol {\theta }};\mathbf {X} ,\mathbf {Z} )\right]\$
• (M): Ước lượng giá trị tham số để cực đại hoá đại lượng ở (E): ${\boldsymbol {\theta }}^{(t+1)}={\underset {\boldsymbol {\theta }}{\operatorname {arg\,max} }}\ Q({\boldsymbol {\theta }}|{\boldsymbol {\theta }}^{(t)})$

Thuật toán lặp lại (E) và (M) liên tiếp cho đến khi điều kiện dừng được thoả mãn.

Ứng dụng

EM được dùng rộng rãi trong thống kê, học máy, Xử lý ngôn ngữ tự nhiên v.v. Thuật toán K-Means phổ biến trong phân cụm dữ liệu có thể xem là một trường hợp riêng của EM.