Завдання 8

Контекст:
У статистичному машинному перекладі поширеною підзадачею є упорядкування слів. Вам дають «мішок слів» (набір перемішаних слів), і потрібно відновити початковий порядок речення, щоб максимізувати ймовірність послідовності.

Нехай \(W = \{w_1, w_2, \dots, w_N\}\) — множина з \(N\) унікальних слів.
Вам задано біграмну мовну модель, \(P(w_j | w_i)\), яка задає ймовірність того, що слово \(w_j\) іде після слова \(w_i\).
Є два спеціальні токени: \(⟨\text{S}⟩\) (Початок) і \(⟨\text{E}⟩\) (Кінець). Речення має починатися з \(⟨\text{S}⟩\) і завершуватися \(⟨\text{E}⟩\).

Мета:
Знайдіть перестановку \(\pi\) слів із \(W\), яка максимізує ймовірність речення:
\[
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})
\]

Щоб застосувати алгоритм A*, ми перетворюємо задачу максимізації на задачу мінімізації, визначивши вартість переходу між словами \(u\) та \(v\) як від’ємний логарифм ймовірності:
\[
C(u, v) = -\ln(P(v | u))
\]

Частина A: Формалізація простору станів
Сформалізуйте цю задачу як пошук у графі простору станів, придатний для алгоритму A*.
Зокрема, визначте

    1. Структуру стану \(n\).
    2. Початковий стан і Цільовий стан.
    3. Функцію наступників (як генеруються переходи) та накопичену вартість \(g(n)\).

[3 бали]

Частина B: Проєктування евристики
Основна складність полягає у факторіальній структурі простору пошуку (\(N!\)), що робить тривіальну евристику (наприклад, \(h=0\)) обчислювально неприйнятною навіть для помірних розмірів вхідних даних (наприклад, \(N > 15\)).
Запроєктуйте нетривіальну евристику \(h(n)\), яка оцінює залишкову вартість завершення речення. Ваша евристика має відповідати таким критеріям:

    1. Вона має бути допустимою (admissible).
    2. Вона має бути монотонною (узгодженою, consistent).

Задайте вашу евристику математично. Доводити властивості поки не потрібно, але необхідно пояснити логіку вашого вибору.

Підказка: Розгляньте множину слів, які ще не розміщені. У коректно завершеному реченні кожне з цих слів повинно мати рівно одне вхідне ребро.

[5 балів]

Частина C: Теоретичні доведення
Використовуючи евристику \(h(n)\), яку ви визначили в Частині B, наведіть формальні доведення таких властивостей:

    1. Допустимість: Доведіть, що \(h(n) \le h^*(n)\), де \(h^*(n)\) — істинна мінімальна вартість до цілі.
    2. Монотонність: Доведіть, що \(h(n) \le cost(n, n') + h(n')\), де \(n'\) — наступник стану \(n\).

[5 балів]
[Усього 13 балів]