Задача 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. Мора да биде монотона (конзистентна).

Дефинирајте ја вашата хевристика математички. Засега не треба да ги докажувате својствата, но мора да ја објасните логиката зад дизајнот.

Насока: Разгледајте го множеството зборови што сè уште не се поставени. Во валидна завршена реченица, секој од овие зборови мора да има точно една влезна гранка.

[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 поени]