Xem mã nguồn của 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 [[Ước lượng hậu nghiệm cực đại|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 P. Dempster|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 <ref name="Dempster1977">
{{chú thích tạp chí
 |last1=Dempster |first1=A.P. |authorlink1=Arthur P. Dempster
 |last2=Laird |first2=N.M. |authorlink2=Nan Laird |last3=Rubin
 |first3=D.B. |authorlink3=Donald Rubin
 |title=Maximum Likelihood from Incomplete Data via the EM Algorithm
 |journal=[[Journal of the Royal Statistical Society, Series B]]
 |year=1977 |volume=39 |issue=1 |pages=1–38
 |jstor=2984875 | mr = 0501537
}}
</ref> và các tính chất và áp dụng của nó trong bài toán [[Ước lượng hợp lý cực đại|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 <math>\mathbf{X}</math>, 1 tập dữ liệu bị thiếu hoặc ẩn biến <math> \mathbf{Z}</math> và 1 vector tham số <math>\boldsymbol\theta</math>, cùng hàm số hợp lý (likelihood) <math>L(\boldsymbol\theta; \mathbf{X}, \mathbf{Z}) = p(\mathbf{X}, \mathbf{Z}|\boldsymbol\theta) </math>.

Đầu tiên giải thuật EM sẽ gán <math>\boldsymbol\theta</math> 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ứ <math>t+1, t\geq 0</math>:
* (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 <math>\mathbf{Z}</math> cho trước giá trị của <math>\mathbf{X}</math> và ước lượng của <math>\boldsymbol\theta^{(t)}</math> có được ở vòng sát trước: <math>
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] \ </math>
*(M): Ước lượng giá trị tham số để cực đại hoá đại lượng ở (E): <math>\boldsymbol\theta^{(t+1)} = \underset{\boldsymbol\theta}{\operatorname{arg\,max}} \ Q(\boldsymbol\theta|\boldsymbol\theta^{(t)}) </math>

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.

 
==Chú thích ==
{{Tham khảo}}

==Liên kết ngoài==

[[Thể loại:Thuật toán tối ưu hóa]]