Zadanie 8

Kontekst:
W statystycznym tłumaczeniu maszynowym (Statistical Machine Translation) częstym podproblemem jest porządkowanie słów (Word Ordering). Otrzymujesz „worek słów” (zbiór przemieszanych słów) i musisz odtworzyć oryginalną kolejność zdania tak, aby zmaksymalizować prawdopodobieństwo sekwencji.

Niech \(W = \{w_1, w_2, \dots, w_N\}\) będzie zbiorem \(N\) unikalnych słów.
Dany jest bigramowy model językowy (Bigram Language Model), \(P(w_j \mid w_i)\), który określa prawdopodobieństwo wystąpienia słowa \(w_j\) po słowie \(w_i\).
Istnieją dwa specjalne tokeny: \(⟨\text{S}⟩\) (Start) oraz \(⟨\text{E}⟩\) (End). Zdanie musi rozpoczynać się od \(⟨\text{S}⟩\) i kończyć na \(⟨\text{E}⟩\).

Cel:
Znajdź permutację \(\pi\) słów ze zbioru \(W\), która maksymalizuje prawdopodobieństwo zdania:
\[ P(\pi) = P(w_{\pi_1} \mid ⟨\text{S}⟩) \times \left( \prod_{i=1}^{N-1} P(w_{\pi_{i+1}} \mid w_{\pi_i}) \right) \times P(⟨\text{E}⟩ \mid w_{\pi_N}) \]

Aby zastosować algorytm A*, przekształcamy problem maksymalizacji w problem minimalizacji, definiując koszt przejścia między słowem \(u\) a słowem \(v\) jako ujemny logarytm prawdopodobieństwa:
\[ C(u, v) = -\ln(P(v \mid u)) \]

Część A: Formalizacja przestrzeni stanów
 Sformalizuj ten problem jako przeszukiwanie grafu przestrzeni stanów odpowiednie dla algorytmu A*.
W szczególności zdefiniuj:

    1. Strukturę stanu \(n\).
    2. Stan początkowy oraz stan docelowy.
    3. Funkcję następnika (w jaki sposób generowane są przejścia) oraz skumulowany koszt \(g(n)\).

[3 punkty]

Część B: Projekt heurystyki
 Główna trudność wynika z silniowej struktury przestrzeni przeszukiwania (\(N!\)), co sprawia, że trywialna heurystyka (np. \(h=0\)) jest obliczeniowo niepraktyczna nawet dla umiarkowanych rozmiarów wejścia (np. \(N > 15\)).
Zaprojektuj nietrywialną heurystykę \(h(n)\), która oszacowuje pozostały koszt ukończenia zdania. Twoja heurystyka musi spełniać następujące warunki:

    1. Musi być dopuszczalna (admissible).
    2. Musi być monotoniczna (spójna, consistent).

Zdefiniuj swoją heurystykę matematycznie. Nie musisz jeszcze dowodzić jej własności, ale musisz wyjaśnić logikę stojącą za jej konstrukcją.

Wskazówka: Rozważ zbiór słów, które nie zostały jeszcze umieszczone. W poprawnie ukończonym zdaniu każde z tych słów musi mieć dokładnie jedną krawędź wchodzącą.

[5 punktów]

Część C: Dowody teoretyczne
 Korzystając z heurystyki \(h(n)\) zdefiniowanej w Części B, przedstaw formalne dowody następujących własności:

    1. Dopuszczalność: Udowodnij, że \(h(n) \le h^*(n)\), gdzie \(h^*(n)\) oznacza rzeczywisty minimalny koszt dojścia do celu.
    2. Monotoniczność: Udowodnij, że \(h(n) \le cost(n, n') + h(n')\), gdzie \(n'\) jest następnikiem stanu \(n\).

[5 punktów]
[Łącznie 13 punktów]