Uppgift 8

Kontext:
Inom statistisk maskinöversättning är ett vanligt delproblem ordföljd. Du får en ”påse med ord” (en mängd omkastade ord) och måste rekonstruera den ursprungliga meningsordningen för att maximera sekvensens sannolikhet.

Låt \(W = \{w_1, w_2, \dots, w_N\}\) vara en mängd av \(N\) unika ord.
Du ges en bigram-språkmodell, \(P(w_j | w_i)\), som anger sannolikheten att ordet \(w_j\) följer på ordet \(w_i\).
Det finns två speciella symboler: \(⟨\text{S}⟩\) (Start) och \(⟨\text{E}⟩\) (Slut). Meningen måste börja med \(⟨\text{S}⟩\) och sluta med \(⟨\text{E}⟩\).

Mål:
Hitta en permutation \(\pi\) av orden i \(W\) som maximerar meningssannolikheten:
\[
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})
\]

För att tillämpa A*-algoritmen omvandlar vi detta maximeringsproblem till ett minimeringsproblem genom att definiera kostnaden för en övergång mellan ord \(u\) och ord \(v\) som den negativa log-sannolikheten:
\[
C(u, v) = -\ln(P(v | u))
\]

Del A: Formulering av tillståndsrum
Formalisera detta problem som en grafbaserad sökning i ett tillståndsrum som lämpar sig för A*-algoritmen.
Specificera

    1. Strukturen för ett tillstånd \(n\).
    2. Starttillstånd och måltillstånd.
    3. Efterföljandefunktionen (hur övergångar genereras) samt den ackumulerade kostnaden \(g(n)\).

[3 poäng]

Del B: Heuristikdesign
Den centrala svårigheten ligger i sökrymdens fakultetsstruktur (\(N!\)), vilket gör en trivial heuristik (t.ex. \(h=0\)) beräkningsmässigt ohanterlig även för måttliga indata (t.ex. \(N > 15\)).
Utforma en icke-trivial heuristik \(h(n)\) som uppskattar den återstående kostnaden för att slutföra meningen. Din heuristik måste uppfylla följande kriterier:

    1. Den måste vara admissibel.
    2. Den måste vara monoton (konsistent).

Definiera din heuristik matematiskt. Du behöver ännu inte bevisa egenskaperna, men du måste förklara logiken bakom din konstruktion.

Tips: Betrakta mängden ord som ännu inte har placerats. I en giltig fullständig mening måste vart och ett av dessa ord ha exakt en inkommande kant.

[5 poäng]

Del C: Teoretiska bevis
Med hjälp av heuristiken \(h(n)\) som du definierade i Del B, ge formella bevis för följande egenskaper:

    1. Admissibilitet: Bevisa att \(h(n) \le h^*(n)\), där \(h^*(n)\) är den sanna minimala kostnaden till målet.
    2. Monotonicitet: Bevisa att \(h(n) \le cost(n, n') + h(n')\), där \(n'\) är en efterföljare till \(n\).

[5 poäng]
[Totalt 13 poäng]