Zadatak 8

Kontekst:
U statističkom mašinskom prevođenju, čest pod-problem je redosled reči (Word Ordering). Dat vam je „skup reči” (neuređen skup izmešanih reči) i potrebno je rekonstruisati originalni redosled rečenice tako da se maksimizuje verovatnoća sekvence.

Neka je \(W = \{w_1, w_2, \dots, w_N\}\) skup od \(N\) jedinstvenih reči.
Dat je bigram jezički model, \(P(w_j | w_i)\), koji daje verovatnoću da reč \(w_j\) sledi nakon reči \(w_i\).
Postoje dva specijalna tokena: \(⟨\text{S}⟩\) (početak) i \(⟨\text{E}⟩\) (kraj). Rečenica mora početi sa \(⟨\text{S}⟩\) i završiti se sa \(⟨\text{E}⟩\).

Cilj:
Pronaći permutaciju \(\pi\) reči iz skupa \(W\) koja maksimizuje verovatnoću rečenice:
\[
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})
\]

Da bismo primenili A* algoritam, ovaj problem maksimizacije transformišemo u problem minimizacije tako što definišemo cenu prelaza između reči \(u\) i reči \(v\) kao negativni logaritam verovatnoće:
\[
C(u, v) = -\ln(P(v | u))
\]

Deo A: Formalizacija prostora stanja
 Formalizujte ovaj problem kao pretragu grafa prostora stanja pogodnu za A* algoritam.
Konkretno, definišite:

    1. Strukturu jednog stanja \(n\).
    2. Početno stanje i ciljno stanje.
    3. Funkciju naslednika (kako se generišu prelazi) i akumulisani trošak \(g(n)\).

[3 poena]

Deo B: Dizajn heuristike
 Osnovna teškoća leži u faktorijelnoj strukturi prostora pretrage (\(N!\)), što trivijalnu heuristiku (npr. \(h=0\)) čini računarski neizvodljivom čak i za umerene veličine ulaza (npr. \(N > 15\)).
Osmislite netrivijalnu heuristiku \(h(n)\) koja procenjuje preostali trošak do završetka rečenice. Vaša heuristika mora ispuniti sledeće uslove:

    1. Mora biti admisibilna.
    2. Mora biti monotona (konzistentna).

Definišite heuristiku matematički. Nije potrebno da još dokazujete ova svojstva, ali morate objasniti logiku svog dizajna.

Savet: Razmotrite skup reči koje još nisu postavljene. U svakoj validnoj kompletnoj rečenici, svaka od tih reči mora imati tačno jednu dolaznu ivicu.

[5 poena]

Deo C: Teorijski dokazi
 Koristeći heuristiku \(h(n)\) definisanu u delu B, dajte formalne dokaze sledećih svojstava:

    1. Admisibilnost: Dokažite da važi \(h(n) \le h^*(n)\), gde je \(h^*(n)\) stvarni minimalni trošak do cilja.
    2. Monotonost: Dokažite da važi \(h(n) \le cost(n, n') + h(n')\), gde je \(n'\) naslednik stanja \(n\).

[5 poena]
[Ukupno 13 poena]