Bài 8

Bối cảnh:
Trong Dịch Máy Thống kê (Statistical Machine Translation), một bài toán con phổ biến là Sắp xếp Từ (Word Ordering). Bạn được cung cấp một “túi từ” (một tập hợp các từ bị xáo trộn) và phải tái tạo lại thứ tự câu ban đầu sao cho xác suất của chuỗi là lớn nhất.

Gọi \(W = \{w_1, w_2, \dots, w_N\}\) là một tập gồm \(N\) từ phân biệt.
Bạn được cung cấp một Mô hình Ngôn ngữ Bigram, \(P(w_j | w_i)\), cung cấp xác suất để từ \(w_j\) xuất hiện sau từ \(w_i\).
Có hai ký hiệu đặc biệt: \(⟨\text{S}⟩\) (Bắt đầu) và \(⟨\text{E}⟩\) (Kết thúc). Câu phải bắt đầu bằng \(⟨\text{S}⟩\) và kết thúc bằng \(⟨\text{E}⟩\).

Mục tiêu:
Tìm một hoán vị \(\pi\) của các từ trong \(W\) sao cho tối đa hóa xác suất của câu:
\[
P(\pi) = P(w_{\pi_1} | ⟨\text{S}⟩) \times \left( \prod_{i=1}^{N-1} P(w_{\pi_{i+1}} | w_{\pi_i}) \right) \times P(⟨\text{E}⟩ | w_{\pi_N})
\]

Để áp dụng thuật toán A*, ta chuyển bài toán cực đại hóa này thành bài toán cực tiểu hóa bằng cách định nghĩa chi phí của một chuyển tiếp giữa từ \(u\) và từ \(v\) là log âm của xác suất:
\[
C(u, v) = -\ln(P(v | u))
\]

Phần A: Hình thức hóa Không gian Trạng thái
 Hình thức hóa bài toán này như một bài toán tìm kiếm trên đồ thị không gian trạng thái phù hợp với thuật toán A*.
Cụ thể, hãy định nghĩa:

    1. Cấu trúc của một Trạng thái \(n\).
    2. Trạng thái Bắt đầu và Trạng thái Đích.
    3. Hàm Kế tiếp (cách sinh các chuyển tiếp) và chi phí tích lũy \(g(n)\).

[3 điểm]

Phần B: Thiết kế Heuristic
 Khó khăn cốt lõi nằm ở cấu trúc giai thừa của không gian tìm kiếm (\(N!\)), khiến heuristic tầm thường (ví dụ: \(h=0\)) trở nên không khả thi về mặt tính toán ngay cả với kích thước đầu vào vừa phải (ví dụ: \(N > 15\)).
Hãy thiết kế một heuristic không tầm thường \(h(n)\) để ước lượng chi phí còn lại nhằm hoàn thành câu. Heuristic của bạn phải thỏa mãn các tiêu chí sau:

    1. Phải chấp nhận được (admissible).
    2. Phải đơn điệu (monotonic / consistent).

Hãy định nghĩa heuristic của bạn dưới dạng toán học. Bạn chưa cần chứng minh các tính chất này, nhưng phải giải thích logic thiết kế của mình.

Gợi ý: Xét tập các từ chưa được đặt vào câu. Trong một câu hoàn chỉnh hợp lệ, mỗi từ này phải có đúng một cạnh đi vào.

[5 điểm]

Phần C: Chứng minh Lý thuyết
 Sử dụng heuristic \(h(n)\) đã định nghĩa ở Phần B, hãy đưa ra các chứng minh hình thức cho các tính chất sau:

    1. Tính chấp nhận được: Chứng minh rằng \(h(n) \le h^*(n)\), trong đó \(h^*(n)\) là chi phí tối thiểu thực sự đến đích.
    2. Tính đơn điệu: Chứng minh rằng \(h(n) \le cost(n, n') + h(n')\), trong đó \(n'\) là trạng thái kế tiếp của \(n\).

[5 điểm]
[Tổng 13 điểm]