Tâche 8

Contexte :
En traduction automatique statistique, un sous-problème courant est l’ordre des mots. On vous donne un « sac de mots » (un ensemble de mots mélangés) et vous devez reconstruire l’ordre original de la phrase afin de maximiser la probabilité de la séquence.

Soit \(W = \{w_1, w_2, \dots, w_N\}\) un ensemble de \(N\) mots uniques.
On vous donne un modèle de langage bigramme, \(P(w_j | w_i)\), qui fournit la probabilité que le mot \(w_j\) suive le mot \(w_i\).
Il existe deux tokens spéciaux : \(⟨\text{S}⟩\) (Début) et \(⟨\text{E}⟩\) (Fin). La phrase doit commencer par \(⟨\text{S}⟩\) et se terminer par \(⟨\text{E}⟩\).

Objectif :
Trouver une permutation \(\pi\) des mots de \(W\) qui maximise la probabilité de la phrase :
\[
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})
\]

Pour appliquer l’algorithme A*, nous transformons ce problème de maximisation en un problème de minimisation en définissant le coût d’une transition entre le mot \(u\) et le mot \(v\) comme le logarithme négatif de la probabilité :
\[
C(u, v) = -\ln(P(v | u))
\]

Partie A : Formalisation de l’espace d’états
Formalisez ce problème comme une recherche sur un graphe d’espace d’états adaptée à l’algorithme A*.
En particulier, définissez

    1. La structure d’un état \(n\).
    2. L’état initial et l’état objectif.
    3. La fonction successeur (comment les transitions sont générées) et le coût accumulé \(g(n)\).

[3 points]

Partie B : Conception de l’heuristique
La difficulté principale réside dans la structure factorielle de l’espace de recherche (\(N!\)), rendant une heuristique triviale (par ex., \(h=0\)) computationnellement intractable même pour des tailles d’entrée modestes (par ex., \(N > 15\)).
Concevez une heuristique non triviale \(h(n)\) qui estime le coût restant pour compléter la phrase. Votre heuristique doit satisfaire les critères suivants :

    1. Elle doit être admissible.
    2. Elle doit être monotone (cohérente).

Définissez votre heuristique mathématiquement. Vous n’avez pas encore besoin de prouver les propriétés, mais vous devez expliquer la logique derrière votre conception.

Indice : Considérez l’ensemble des mots qui n’ont pas encore été placés. Dans une phrase complète valide, chacun de ces mots doit avoir exactement une arête entrante.

[5 points]

Partie C : Preuves théoriques
En utilisant l’heuristique \(h(n)\) que vous avez définie en Partie B, fournissez des preuves formelles des propriétés suivantes :

    1. Admissibilité : Prouvez que \(h(n) \le h^*(n)\), où \(h^*(n)\) est le véritable coût minimal jusqu’à l’objectif.
    2. Monotonicité : Prouvez que \(h(n) \le cost(n, n') + h(n')\), où \(n'\) est un successeur de \(n\).

[5 points]
[Total 13 points]