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

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 ^[1] 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 đó.

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).

Xét một mô hình thống kê bao gồm 1 tập dữ liệu quan sát được ${\displaystyle \mathbf {X} }$ , 1 tập dữ liệu bị thiếu hoặc ẩn biến ${\displaystyle \mathbf {Z} }$  và 1 vector tham số ${\displaystyle {\boldsymbol {\theta }}}$ , cùng hàm số hợp lý (likelihood) ${\displaystyle 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 ${\displaystyle {\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ứ ${\displaystyle 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 ${\displaystyle \mathbf {Z} }$  cho trước giá trị của ${\displaystyle \mathbf {X} }$  và ước lượng của ${\displaystyle {\boldsymbol {\theta }}^{(t)}}$  có được ở vòng sát trước: ${\displaystyle 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): ${\displaystyle {\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.

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.