8. feladat

Kontextus:
A statisztikai gépi fordításban egy gyakori részprobléma a szórend. Adott egy „szózsák” (összekevert szavak halmaza), és az eredeti mondatsorrendet kell rekonstruálnod úgy, hogy a szekvencia valószínűsége maximális legyen.

Legyen \(W = \{w_1, w_2, \dots, w_N\}\) \(N\) darab különböző szó halmaza.
Adott egy bigram nyelvi modell, \(P(w_j | w_i)\), amely megadja annak valószínűségét, hogy a \(w_j\) szó a \(w_i\) szó után következik.
Két speciális token van: \(⟨\text{S}⟩\) (Kezdet) és \(⟨\text{E}⟩\) (Vége). A mondatnak \(⟨\text{S}⟩\)-sel kell kezdődnie és \(⟨\text{E}⟩\)-vel kell végződnie.

Cél:
Találj egy \(\pi\) permutációt a \(W\) szavaira, amely maximalizálja a mondat valószínűségét:
\[
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})
\]

Az A* algoritmus alkalmazásához ezt a maximalizálási problémát minimalizálási problémává alakítjuk úgy, hogy az \(u\) és \(v\) szó közötti átmenet költségét a negatív log-valószínűségként definiáljuk:
\[
C(u, v) = -\ln(P(v | u))
\]

A rész: Állapottér formalizálása
Formalizáld ezt a problémát egy A* algoritmushoz alkalmas állapottér-gráfkeresésként.
Különösen, definiáld

    1. Egy állapot \(n\) szerkezetét.
    2. A kezdőállapotot és a célállapotot.
    3. A szukcesszorfüggvényt (hogyan generálódnak az átmenetek) és a felhalmozott költséget, \(g(n)\)-t.

[3 pont]

B rész: Heurisztika tervezése
A fő nehézséget a keresési tér faktoriális szerkezete (\(N!\)) okozza, ami miatt egy triviális heurisztika (pl. \(h=0\)) már mérsékelt bemeneti méreteknél is számításilag kezelhetetlen (pl. \(N > 15\)).
Tervezd meg egy nem triviális \(h(n)\) heurisztikát, amely megbecsüli a mondat befejezéséhez hátralévő költséget. A heurisztikádnak a következő kritériumoknak kell megfelelnie:

    1. Megengedőnek (admissible) kell lennie.
    2. Monoton (konzisztens) kell lennie.

Definiáld a heurisztikádat matematikailag. A tulajdonságokat még nem kell bizonyítanod, de el kell magyaráznod a tervezés mögötti logikát.

Tipp: Tekintsd azon szavak halmazát, amelyek még nem kerültek a helyükre. Egy érvényes, befejezett mondatban mindegyik ilyen szónak pontosan egy bejövő éle kell legyen.

[5 pont]

C rész: Elméleti bizonyítások
A B részben definiált \(h(n)\) heurisztikát használva adj formális bizonyításokat az alábbi tulajdonságokra:

    1. Megengedőség: Bizonyítsd be, hogy \(h(n) \le h^*(n)\), ahol \(h^*(n)\) a célig vezető valódi minimális költség.
    2. Monotonitás: Bizonyítsd be, hogy \(h(n) \le cost(n, n') + h(n')\), ahol \(n'\) \(n\) egy szukcesszora.

[5 pont]
[Összesen 13 pont]