Taak 8

Context:
In Statistical Machine Translation is een veelvoorkomend deelprobleem Word Ordering. Je krijgt een “bag of words” (een set door elkaar gehusselde woorden) en moet de oorspronkelijke zinsvolgorde reconstrueren om de kans van de sequentie te maximaliseren.

Laat \(W = \{w_1, w_2, \dots, w_N\}\) een verzameling van \(N\) unieke woorden zijn.
Je krijgt een Bigram Language Model, \(P(w_j | w_i)\), dat de kans geeft dat woord \(w_j\) volgt op woord \(w_i\).
Er zijn twee speciale tokens: \(⟨\text{S}⟩\) (Start) en \(⟨\text{E}⟩\) (Einde). De zin moet beginnen met \(⟨\text{S}⟩\) en eindigen met \(⟨\text{E}⟩\).

Doel:
Vind een permutatie \(\pi\) van de woorden in \(W\) die de zinskans maximaliseert:
\[
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})
\]

Om het A*-algoritme toe te passen, zetten we dit maximalisatieprobleem om in een minimalisatieprobleem door de kosten van een overgang tussen woord \(u\) en woord \(v\) te definiëren als de negatieve log-kans:
\[
C(u, v) = -\ln(P(v | u))
\]

Deel A: Formele specificatie van de toestandsruimte
 Formaliseer dit probleem als een State Space Graph-zoekprobleem geschikt voor A*.
Definieer specifiek

    1. De structuur van een toestand \(n\).
    2. De starttoestand en de doeltoestand.
    3. De successorfunctie (hoe overgangen worden gegenereerd) en de geaccumuleerde kost \(g(n)\).

[3 punten]

Deel B: Heuristiekontwerp
De kernmoeilijkheid zit in de factoriële structuur van de zoekruimte (\(N!\)), waardoor een triviale heuristiek (bv. \(h=0\)) computationeel onhaalbaar is, zelfs voor bescheiden invoergroottes (bv. \(N > 15\)).
Ontwerp een niet-triviale heuristiek \(h(n)\) die de resterende kost om de zin te voltooien schat. Je heuristiek moet voldoen aan:

    1. Ze moet admissible zijn.
    2. Ze moet monotone (consistent) zijn.

Definieer je heuristiek wiskundig. Je hoeft de eigenschappen nog niet te bewijzen, maar je moet de logica achter je ontwerp uitleggen.

Hint: Beschouw de verzameling woorden die nog niet zijn geplaatst. In een geldige, voltooide zin moet elk van deze woorden precies één inkomende rand hebben.

[5 punten]

Deel C: Theoretische bewijzen
Gebruikmakend van de heuristiek \(h(n)\) die je in Deel B definieerde, geef formele bewijzen voor de volgende eigenschappen:

    1. Admissibiliteit: Bewijs dat \(h(n) \le h^*(n)\), waarbij \(h^*(n)\) de werkelijke minimale kost tot het doel is.
    2. Monotoniciteit: Bewijs dat \(h(n) \le cost(n, n') + h(n')\), waarbij \(n'\) een successor van \(n\) is.

[5 punten]
[Totaal 13 punten]