Задача 8

Контекст:
В статистическом машинном переводе (Statistical Machine Translation) одной из распространённых подзадач является упорядочивание слов (Word Ordering). Вам дан «мешок слов» (набор перемешанных слов), и требуется восстановить исходный порядок предложения так, чтобы максимизировать вероятность последовательности.

Пусть \(W = \{w_1, w_2, \dots, w_N\}\) — множество из \(N\) уникальных слов.
Вам дана биграммная языковая модель \(P(w_j | w_i)\), которая задаёт вероятность того, что слово \(w_j\) следует за словом \(w_i\).
Существуют два специальных токена: \(⟨\text{S}⟩\) (Start, начало) и \(⟨\text{E}⟩\) (End, конец). Предложение должно начинаться с \(⟨\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 баллов]