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

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

Xét một tập dữ liệu gồm m ví dụ X = {x1, x2, …xm}, trong đó mỗi ví dụ có một phần (một tập các thuộc tính) quan sát được và một phần không quan sát được.

• Phần quan sát được: Y = {y1, …ym}
• Phần không quan sát được: Z = {z1, …zm}
• Đối với mỗi ví dụ xi: xi= yi + zi

Tập dữ liệu X được sinh ra bởi một hàm phân phối xác suất , và hàm phân phối xác suất này phụ thuộc vào một tập các tham số chưa biết (và sẽ được ước lượng). Phần dữ liệu không quan sát được Z được xem như một biến ngẫu nhiên mà hàm phân bố xác suất của nó phụ thuộc vào: các tham số chưa biết giá trị và phần dữ liệu quan sát được Y. Thuật toán EM lặp lại hai bước sau đây

• Bước tính toán giá trị kỳ vọng (Expectation Step): Với các giá trị được ước lượng hiện tại của các tham số , tính toán các giá trị kỳ vọng của các biến không quan sát được.
• Bước cực đại hóa (Maximization Step): Với các giá trị kỳ vọng được gán cho các biến không quan sát được (tính ở bước kỳ vọng – E step), tính toán lại các ước lượng khả năng lớn nhất của các tham số .

Bài toán cực đại hóa kỳ vọng trong Dịch máy thống kê

Thuật toán EM:

• E-step: áp dụng mô hình vào dữ liệu: một phần của dữ liệu là không quan sát được (trong bài toán Dịch máy thống kê chính là các gióng hàng). E-step sử dụng mô hình để tính toán xác suất của các giá trị quan sát được từ đó đưa ra giá trị kỳ vọng cho các giá trị không quan sát được (các gióng hàng).
• M-step: ước lượng mô hình từ dữ liệu thu được trong bước Tính toán giá trị kỳ vọng.