Detyra 8

Konteksti:
Në Përkthimin Statistik të Makinerive, një nën-problem i zakonshëm është Renditja e Fjalëve. Ju jepet një “thes fjalësh” (një grup fjalësh të përziera) dhe duhet të rindërtoni renditjen origjinale të fjalisë në mënyrë që të maksimizoni probabilitetin e vargut.

Le të jetë \(W = \{w_1, w_2, \dots, w_N\}\) një grup prej \(N\) fjalësh unike.
Ju jepet një Model Gjuhe Bigram, \(P(w_j | w_i)\), i cili jep probabilitetin që fjala \(w_j\) të vijë pas fjalës \(w_i\).
Ekzistojnë dy simbole të veçanta: \(⟨\text{S}⟩\) (Fillimi) dhe \(⟨\text{E}⟩\) (Fundi). Fjalia duhet të fillojë me \(⟨\text{S}⟩\) dhe të përfundojë me \(⟨\text{E}⟩\).

Objektivi:
Gjeni një permutacion \(\pi\) të fjalëve në \(W\) që maksimizon probabilitetin e fjalise:
\[
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})
\]

Për të aplikuar algoritmin A*, e shndërrojmë këtë problem maksimizimi në një problem minimizimi duke përcaktuar koston e një kalimi midis fjalës \(u\) dhe fjalës \(v\) si logaritmin natyror negativ të probabilitetit:
\[
C(u, v) = -\ln(P(v | u))
\]

Pjesa A: Formalizimi i Hapësirës së Gjendjeve
Formalizoni këtë problem si një kërkim në Grafik të Hapësirës së Gjendjeve të përshtatshëm për algoritmin A*.
Specifikisht, përcaktoni

    1. Strukturën e një Gjendjeje \(n\).
    2. Gjendjen Fillestare dhe Gjendjen Qëllim.
    3. Funksionin e Pasardhësit (si gjenerohen kalimet) dhe koston e akumuluar \(g(n)\).

[3 pikë]

Pjesa B: Projektimi i Heuristikës
Vështirësia kryesore qëndron te struktura faktoriale e hapësirës së kërkimit (\(N!\)), duke e bërë një heuristikë triviale (p.sh., \(h=0\)) llogaritërisht të papërballueshme edhe për madhësi modeste të inputit (p.sh., \(N > 15\)).
Projekttoni një heuristikë jo-triviale \(h(n)\) që vlerëson koston e mbetur për të përfunduar fjalinë. Heuristika juaj duhet të plotësojë kriteret në vijim:

    1. Duhet të jetë e pranueshme (admissible).
    2. Duhet të jetë monotonike (konsistente).

Përcaktoni heuristikën tuaj matematikisht. Nuk keni nevojë të provoni ende vetitë, por duhet të shpjegoni logjikën pas projektimit tuaj.

Ndihmë: Merrni parasysh grupin e fjalëve që ende nuk janë vendosur. Në një fjali të plotë të vlefshme, secila prej këtyre fjalëve duhet të ketë saktësisht një hark hyrës.

[5 pikë]

Pjesa C: Provat Teorike
Duke përdorur heuristikën \(h(n)\) që keni përcaktuar në Pjesën B, jepni prova formale për vetitë e mëposhtme:

    1. Pranueshmëria: Vërtetoni që \(h(n) \le h^*(n)\), ku \(h^*(n)\) është kostoja e vërtetë minimale deri te qëllimi.
    2. Monotonikësia: Vërtetoni që \(h(n) \le cost(n, n') + h(n')\), ku \(n'\) është një pasardhës i \(n\).

[5 pikë]
[Gjithsej 13 pikë]