Naloga 8

Kontekst:
V statističnem strojnem prevajanju je pogosta podnaloga urejanje besed. Podana je »vreča besed« (množica premešanih besed) in rekonstruirati morate prvotni vrstni red stavka tako, da maksimizirate verjetnost zaporedja.

Naj bo \(W = \{w_1, w_2, \dots, w_N\}\) množica \(N\) različnih besed.
Podan je bigramni jezikovni model, \(P(w_j \mid w_i)\), ki podaja verjetnost, da beseda \(w_j\) sledi besedi \(w_i\).
Obstajata dva posebna simbola: \(⟨\text{S}⟩\) (Začetek) in \(⟨\text{E}⟩\) (Konec). Stavek se mora začeti z \(⟨\text{S}⟩\) in končati z \(⟨\text{E}⟩\).

Cilj:
Najti permutacijo \(\pi\) besed v množici \(W\), ki maksimizira verjetnost stavka:
\[
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})
\]

Za uporabo algoritma A* ta problem maksimizacije pretvorimo v problem minimizacije tako, da definiramo ceno prehoda med besedama \(u\) in \(v\) kot negativni logaritem verjetnosti:
\[
C(u, v) = -\ln(P(v \mid u))
\]

Del A: Formalizacija prostora stanj
Formalizirajte ta problem kot iskanje po grafu prostora stanj, primerno za algoritem A*.
Natančneje, definirajte

    1. Strukturo stanja \(n\).
    2. Začetno stanje in ciljno stanje.
    3. Funkcijo naslednikov (kako se generirajo prehodi) ter akumulirano ceno \(g(n)\).

[3 točke]

Del B: Načrtovanje hevristike
Osrednja težava je v faktorski strukturi prostora iskanja (\(N!\)), zaradi česar je trivialna hevristika (npr. \(h=0\)) računsko neobvladljiva že pri zmernih velikostih vhodnih podatkov (npr. \(N > 15\)).
Načrtujte netrivialno hevristiko \(h(n)\), ki oceni preostalo ceno za dokončanje stavka. Vaša hevristika mora izpolnjevati naslednja pogoja:

    1. Biti mora dopustna.
    2. Biti mora monotona (konsistentna).

Definirajte svojo hevristiko matematično. Lastnosti vam še ni treba dokazati, vendar morate pojasniti logiko svoje zasnove.

Namig: Upoštevajte množico besed, ki še niso bile postavljene. V veljavnem dokončanem stavku mora imeti vsaka od teh besed natanko eno vhodno povezavo.

[5 točk]

Del C: Teoretični dokazi
Z uporabo hevristike \(h(n)\), ki ste jo definirali v Delu B, podajte formalne dokaze za naslednji lastnosti:

    1. Dopustnost: Dokažite, da \(h(n) \le h^*(n)\), kjer \(h^*(n)\) predstavlja resnično minimalno ceno do cilja.
    2. Monotonost: Dokažite, da \(h(n) \le cost(n, n') + h(n')\), kjer je \(n'\) naslednik stanja \(n\).

[5 točk]
[Skupaj 13 točk]