Diferencia entre revisiones de «Algoritmo de avance-retroceso»
Contenido eliminado Contenido añadido
mSin resumen de edición |
|||
Línea 1:
== Introducción ==
Uno de los problemas básicos de los [[Modelo oculto de
'''Probabilidad de una secuencia <math>S</math> de estados'''
Línea 31:
El cálculo de <math>P(O|\mu)</math> tal y como se muestra es impracticable; sólo para <math>10</math> estados y <math>10</math> observaciones sería necesario realizar del orden de <math>10^{11}</math> operaciones. Para reducir esta [[Complejidad_computacional|complejidad]] se emplean estrategias de [[programación dinámica]] como los '''algoritmos ''forward'' y ''backward'''''.
Se recomienda revisar la [[
== Procedimiento hacia adelante ==
Línea 111:
Tanto el procedimiento hacia adelante como el algoritmo backward, requieren del orden de <math>N^{2}T</math> operaciones; muy inferior a <math>2TN^{T}-1</math> operaciones (<math>N</math> es el número de estados y <math>T</math> es la longitud de la secuencia de observaciones) que son necesarias si se calcula <math>P(O,S|\mu)</math> para todas las posibles secuencias <math>S</math> del modelo.
El cálculo de los <math>\beta_{t}(i)</math> servirán - junto a los <math>\alpha_{t}(i)</math> - para contestar las otras dos preguntas fundamentales de los Modelos Ocultos de
* ¿Cuál es la '''secuencia óptima <math>S</math> de estados''' dado una secuencia de observaciones <math>O</math>? ([[algoritmo de Viterbi]])
Línea 117:
== Véase también ==
* [[Modelo oculto de
* [[Algoritmo de Viterbi|Algoritmo de Viterbi]]
* [[Algoritmo de Baum-Welch|Algoritmo de Baum-Welch]]
| |||