Tarea 8

Contexto:
En la Traducción Automática Estadística, un subproblema común es el ordenamiento de palabras. Se le da un ``bolsa de palabras'' (un conjunto de palabras desordenadas) y debe reconstruir el orden original de la oración para maximizar la probabilidad de la secuencia.

Sea \(W = \{w_1, w_2, \dots, w_N\}\) un conjunto de \(N\) palabras únicas.
Se le proporciona un modelo de lenguaje bigrama, \(P(w_j | w_i)\), que ofrece la probabilidad de que la palabra \(w_j\) siga a la palabra \(w_i\).
Hay dos tokens especiales: \(⟨\text{S}⟩\) (Inicio) y \(⟨\text{E}⟩\) (Fin). La oración debe comenzar con \(⟨\text{S}⟩\) y terminar con \(⟨\text{E}⟩\).

Objetivo:
Encontrar una permutación \(\pi\) de las palabras en \(W\) que maximice la probabilidad de la oración:
\[
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})
\]

Para aplicar el algoritmo A*, transformamos este problema de maximización en un problema de minimización definiendo el coste de una transición entre la palabra \(u\) y la palabra \(v\) como el logaritmo negativo de la probabilidad:
\[
C(u, v) = -\ln(P(v | u))
\]

Parte A: Formalización del espacio de estados
Formalice este problema como una búsqueda en un grafo de espacio de estados adecuada para el algoritmo A*.
En particular, defina

    1. La estructura de un estado \(n\).
    2. El estado inicial y el estado objetivo.
    3. La función sucesora (cómo se generan las transiciones) y el coste acumulado \(g(n)\).

[3 puntos]

Parte B: Diseño de la heurística
La dificultad principal radica en la estructura factorial del espacio de búsqueda (\(N!\)), lo que hace que una heurística trivial (p. ej., \(h=0\)) sea computacionalmente intratable incluso para tamaños de entrada modestos (p. ej., \(N > 15\)).
Diseñe una heurística no trivial \(h(n)\) que estime el coste restante para completar la oración. Su heurística debe cumplir los siguientes criterios:

    1. Debe ser admisible.
    2. Debe ser monótona (consistente).

Defina su heurística matemáticamente. Aún no necesita demostrar las propiedades, pero debe explicar la lógica detrás de su diseño.

Pista: Considere el conjunto de palabras que aún no se han colocado. En una oración completa válida, cada una de estas palabras debe tener exactamente una arista entrante.

[5 puntos]

Parte C: Demostraciones teóricas
Usando la heurística \(h(n)\) que definió en la Parte B, proporcione demostraciones formales de las siguientes propiedades:

    1. Admisibilidad: Demuestre que \(h(n) \le h^*(n)\), donde \(h^*(n)\) es el verdadero coste mínimo hasta el objetivo.
    2. Monotonicidad: Demuestre que \(h(n) \le cost(n, n') + h(n')\), donde \(n'\) es un sucesor de \(n\).

[5 puntos]
[Total 13 puntos]