Lecture

En modelos de lenguajes se asignan a cadenas probabilidades. El problema
¿Cual es la pregunta mas probable? es NP-difícil para autómatas probabilistas
o modelos de Markov.
No obstante, el hecho que los modelos sean generativos nos permite utilizar
los mismos autómatas para desarrollar algoritmos probabilizados. Eso nos
permite presentar un algoritmo cuya complejidad es polinómica con 1/p donde
p es la probabilidad de la cadena mas probable. Prácticamente esto significa
que la cadena mas probable se puede calcular en casos concretos de interés,
o sea esos donde la cadena mas probable tiene un peso no despreciable.
Por ultimo, relacionaremos este resultado con el problema de encontrar la
traducción mas probable utilizando un transductor.