Sarcina 8

Context:
În traducerea automată statistică (Statistical Machine Translation), o sub-problemă frecventă este ordonarea cuvintelor (Word Ordering). Vi se oferă un „sac de cuvinte” (un set de cuvinte amestecate) și trebuie să reconstruiți ordinea originală a propoziziției pentru a maximiza probabilitatea secvenței.

Fie \(W = \{w_1, w_2, \dots, w_N\}\) un set de \(N\) cuvinte distincte.
Vi se oferă un model de limbaj bigram, \(P(w_j | w_i)\), care furnizează probabilitatea ca cuvântul \(w_j\) să urmeze după cuvântul \(w_i\).
Există doi tokeni speciali: \(⟨\text{S}⟩\) (Start) și \(⟨\text{E}⟩\) (End). Propoziția trebuie să înceapă cu \(⟨\text{S}⟩\) și să se termine cu \(⟨\text{E}⟩\).

Obiectiv:
Găsiți o permutare \(\pi\) a cuvintelor din \(W\) care maximizează probabilitatea propoziției:
\[ 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}) \]

Pentru a aplica algoritmul A*, transformăm această problemă de maximizare într-una de minimizare definind costul unei tranziții între cuvântul \(u\) și cuvântul \(v\) ca fiind logaritmul negativ al probabilității:
\[ C(u, v) = -\ln(P(v | u)) \]

Partea A: Formalizarea spațiului stărilor
 Formulați această problemă ca o căutare într-un graf al spațiului stărilor potrivit pentru algoritmul A*.
În mod specific, definiți:

    1. Structura unei Stări \(n\).
    2. Starea inițială și Starea scop.
    3. Funcția succesor (modul în care sunt generate tranzițiile) și costul acumulat \(g(n)\).

[3 puncte]

Partea B: Proiectarea euristicii
 Dificultatea principală constă în structura factorială a spațiului de căutare (\(N!\)), ceea ce face ca o euristică trivială (de exemplu, \(h=0\)) să fie computațional impracticabilă chiar și pentru dimensiuni moderate ale intrării (de exemplu, \(N > 15\)).
Proiectați o euristică netrivială \(h(n)\) care estimează costul rămas pentru a completa propoziția. Euristica trebuie să îndeplinească următoarele criterii:

    1. Să fie admisibilă.
    2. Să fie monotonă (consistentă).

Definiți euristica matematic. Nu este necesar să demonstrați încă proprietățile, dar trebuie să explicați logica din spatele proiectării.

Indiciu: Luați în considerare setul de cuvinte care nu au fost încă plasate. Într-o propoziție validă completă, fiecare dintre aceste cuvinte trebuie să aibă exact o muchie de intrare.

[5 puncte]

Partea C: Demonstrații teoretice
 Folosind euristica \(h(n)\) definită în Partea B, oferiți demonstrații formale pentru următoarele proprietăți:

    1. Admisibilitate: Demonstrați că \(h(n) \le h^*(n)\), unde \(h^*(n)\) este costul minim real până la scop.
    2. Monotonicitate: Demonstrați că \(h(n) \le cost(n, n') + h(n')\), unde \(n'\) este un succesor al lui \(n\).

[5 puncte]
[Total 13 puncte]