Thuật_toán cực_đại_hoá kỳ_vọng Thuật_toán cực_đại_hoá 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 hoá 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 formula _ 1 1 tập dữ_liệu bị thiếu hoặc ẩn biến formula _ 2 và 1 vector tham_số formula _ 3 cùng hàm_số hợp_lý likelihood formula _ 4 Đầu_tiên giải_thuật EM sẽ gán formula _ 3 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ứ formula _ 6 BULLET 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 formula _ 7 cho trước giá_trị của formula _ 1 và ước_lượng của formula _ 9 có được ở vòng sát trước formula _ 10 BULLET M Ước_lượng giá_trị tham_số để cực_đại_hoá đại_lượng ở E formula _ 11 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
Thuật_toán cực_đại_hoá kỳ_vọng