Esercizio 8

Contesto:
Nella Traduzione Automatica Statistica, un sottoproblema comune è l’ordinamento delle parole. Ti viene dato un ``sacco di parole'' (un insieme di parole in ordine sparso) e devi ricostruire l’ordine originale della frase in modo da massimizzare la probabilità della sequenza.

Sia \(W = \{w_1, w_2, \dots, w_N\}\) un insieme di \(N\) parole uniche.
Ti viene fornito un modello di linguaggio bigramma, \(P(w_j | w_i)\), che fornisce la probabilità che la parola \(w_j\) segua la parola \(w_i\).
Ci sono due token speciali: \(⟨\text{S}⟩\) (Inizio) e \(⟨\text{E}⟩\) (Fine). La frase deve iniziare con \(⟨\text{S}⟩\) e terminare con \(⟨\text{E}⟩\).

Obiettivo:
Trovare una permutazione \(\pi\) delle parole in \(W\) che massimizza la probabilità della frase:
\[
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})
\]

Per applicare l’algoritmo A*, trasformiamo questo problema di massimizzazione in un problema di minimizzazione definendo il costo di una transizione tra la parola \(u\) e la parola \(v\) come il logaritmo negativo della probabilità:
\[
C(u, v) = -\ln(P(v | u))
\]

Parte A: Formalizzazione dello spazio degli stati
Formalizzare questo problema come una ricerca su grafo nello spazio degli stati adatta all’algoritmo A*.
In particolare, definire

    1. La struttura di uno stato \(n\).
    2. Lo stato iniziale e lo stato obiettivo.
    3. La funzione dei successori (come vengono generate le transizioni) e il costo accumulato \(g(n)\).

[3 punti]

Parte B: Progettazione dell’euristica
La difficoltà principale risiede nella struttura fattoriale dello spazio di ricerca (\(N!\)), che rende un’euristica banale (ad es., \(h=0\)) computazionalmente intrattabile anche per dimensioni di input moderate (ad es., \(N > 15\)).
Progettare un’euristica non banale \(h(n)\) che stimi il costo rimanente per completare la frase. La tua euristica deve soddisfare i seguenti criteri:

    1. Deve essere ammissibile.
    2. Deve essere monotona (consistente).

Definire matematicamente la tua euristica. Non è necessario dimostrare ancora le proprietà, ma devi spiegare la logica alla base della progettazione.

Suggerimento: considera l’insieme delle parole che non sono ancora state posizionate. In una frase completa valida, ognuna di queste parole deve avere esattamente un arco entrante.

[5 punti]

Parte C: Dimostrazioni teoriche
Usando l’euristica \(h(n)\) che hai definito nella Parte B, fornire dimostrazioni formali delle seguenti proprietà:

    1. Ammissibilità: dimostrare che \(h(n) \le h^*(n)\), dove \(h^*(n)\) è il vero costo minimo per raggiungere l’obiettivo.
    2. Monotonicità: dimostrare che \(h(n) \le cost(n, n') + h(n')\), dove \(n'\) è un successore di \(n\).

[5 punti]
[Totale 13 punti]