En ingeniería eléctrica , informática , computación estadística y bioinformática , el algoritmo de Baum-Welch es un caso especial del algoritmo EM utilizado para encontrar los parámetros desconocidos de un modelo de Markov oculto (HMM). Utiliza el algoritmo hacia adelante y hacia atrás para calcular las estadísticas del paso de expectativa.
Historia
El algoritmo de Baum-Welch lleva el nombre de sus inventores Leonard E. Baum y Lloyd R. Welch . El algoritmo y los modelos de Hidden Markov se describieron por primera vez en una serie de artículos de Baum y sus colegas del Instituto de Análisis de Defensa a fines de la década de 1960 y principios de la de 1970. [1] Una de las primeras aplicaciones importantes de los HMM fue el campo del procesamiento de voz . [2] En la década de 1980, los HMM surgieron como una herramienta útil en el análisis de información y sistemas biológicos y, en particular, de la información genética . [3] Desde entonces se han convertido en una herramienta importante en el modelado probabilístico de secuencias genómicas. [4]
Descripción
Un modelo de Markov oculto describe la probabilidad conjunta de una colección de variables aleatorias discretas " ocultas " y observadas. Se basa en el supuesto de que la i -ésima variable oculta dada la ( i - 1) -ésima variable oculta es independiente de las variables ocultas anteriores, y las variables de observación actuales dependen solo del estado oculto actual.
El algoritmo de Baum-Welch utiliza el conocido algoritmo EM para encontrar la estimación de máxima verosimilitud de los parámetros de un modelo de Markov oculto dado un conjunto de vectores de características observados.
Dejar ser una variable aleatoria oculta discreta con valores posibles (es decir, asumimos que hay estados en total). Asumimos el es independiente del tiempo , que conduce a la definición de la matriz de transición estocástica independiente del tiempo
La distribución del estado inicial (es decir, cuando ) es dado por
Las variables de observación puede tomar uno de valores posibles. También asumimos que la observación dada el estado "oculto" es independiente del tiempo. La probabilidad de una determinada observación. en el momento para el estado es dado por
Teniendo en cuenta todos los posibles valores de y , obtenemos el matriz dónde pertenece a todos los estados posibles y pertenece a todas las observaciones.
Una secuencia de observación viene dada por .
Por tanto, podemos describir una cadena de Markov oculta por . El algoritmo de Baum-Welch encuentra un máximo local para (es decir, los parámetros HMM que maximizan la probabilidad de la observación). [5]
Algoritmo
Colocar con condiciones iniciales aleatorias. También se pueden configurar utilizando información previa sobre los parámetros si está disponible; esto puede acelerar el algoritmo y también dirigirlo hacia el máximo local deseado.
Procedimiento de reenvío
Dejar , la probabilidad de ver las observaciones y estar en estado en el momento . Esto se encuentra de forma recursiva:
Dado que esta serie converge exponencialmente a cero, el algoritmo se subdesbordará numéricamente para secuencias más largas. [6] Sin embargo, esto se puede evitar en un algoritmo ligeramente modificado escalando en el delantero y en el procedimiento hacia atrás a continuación.
Procedimiento hacia atrás
Dejar esa es la probabilidad de la secuencia parcial final dado el estado inicial en el momento . Calculamos como,
Actualizar
Ahora podemos calcular las variables temporales, según el teorema de Bayes:
cual es la probabilidad de estar en estado en el momento dada la secuencia observada y los parámetros
cual es la probabilidad de estar en estado y a veces y respectivamente dada la secuencia observada y parámetros .
Los denominadores de y son lo mismo ; representan la probabilidad de hacer la observación dados los parámetros .
Los parámetros del modelo oculto de Markov. ahora se puede actualizar:
que es la frecuencia esperada gastada en el estado en el momento .
que es el número esperado de transiciones del estado i al estado j en comparación con el número total esperado de transiciones fuera del estado i . Para aclarar, el número de transiciones desde el estado i no significa transiciones a un estado diferente j , sino a cualquier estado, incluido él mismo. Esto es equivalente al número de veces que se observa el estado i en la secuencia de t = 1 a t = T - 1.
dónde
es una función indicadora, y es el número esperado de veces que las observaciones de salida han sido iguales a mientras está en el estado sobre el número total esperado de veces en el estado .
Estos pasos ahora se repiten iterativamente hasta un nivel deseado de convergencia.
Nota: Es posible sobreajustar un conjunto de datos en particular. Es decir,. El algoritmo también hace no garantiza un máximo global.
Varias secuencias
El algoritmo descrito hasta ahora asume una única secuencia observada . Sin embargo, en muchas situaciones, se observan varias secuencias:. En este caso, la información de todas las secuencias observadas debe utilizarse en la actualización de los parámetros., , y . Suponiendo que ha calculado y para cada secuencia , los parámetros ahora se pueden actualizar:
dónde
es una función indicadora
Ejemplo
Supongamos que tenemos una gallina de la que recolectamos huevos al mediodía todos los días. Ahora bien, si la gallina ha puesto huevos para la recolección o no depende de algunos factores desconocidos que están ocultos. Sin embargo, podemos (para simplificar) suponer que solo hay dos estados que determinan si la gallina pone huevos. Ahora no conocemos el estado en el punto de partida inicial, no conocemos las probabilidades de transición entre los dos estados y no conocemos la probabilidad de que la gallina ponga un huevo dado un estado en particular. [7] [8] Para empezar, primero adivinamos las matrices de transición y emisión.
|
|
|
Luego tomamos un conjunto de observaciones (E = huevos, N = sin huevos): N, N, N, N, N, E, E, N, N, N
Esto nos da un conjunto de transiciones observadas entre días: NN, NN, NN, NN, NE, EE, EN, NN, NN
El siguiente paso es estimar una nueva matriz de transición. Por ejemplo, la probabilidad de que la secuencia NN y el estado sean luego viene dado por lo siguiente,
Secuencia observada | Mayor probabilidad de observar esa secuencia si el estado es luego | Mayor probabilidad de observar esa secuencia | |
---|---|---|---|
NN | 0,024 = 0,2 * 0,3 * 0,5 * 0,8 | 0.3584 | , |
NN | 0,024 = 0,2 * 0,3 * 0,5 * 0,8 | 0.3584 | , |
NN | 0,024 = 0,2 * 0,3 * 0,5 * 0,8 | 0.3584 | , |
NN | 0,024 = 0,2 * 0,3 * 0,5 * 0,8 | 0.3584 | , |
nordeste | 0,006 = 0,2 * 0,3 * 0,5 * 0,2 | 0.1344 | , |
EE | 0,014 = 0,2 * 0,7 * 0,5 * 0,2 | 0.0490 | , |
ES | 0,056 = 0,2 * 0,7 * 0,5 * 0,8 | 0.0896 | , |
NN | 0,024 = 0,2 * 0,3 * 0,5 * 0,8 | 0.3584 | , |
NN | 0,024 = 0,2 * 0,3 * 0,5 * 0,8 | 0.3584 | , |
Total | 0,22 | 2,4234 |
Así, la nueva estimación de la a la transición es ahora (denominado "Pseudoprobabilidades" en las siguientes tablas). Luego calculamos el a , a y a probabilidades de transición y normalizar para que se sumen a 1. Esto nos da la matriz de transición actualizada:
|
|
|
A continuación, queremos estimar una nueva matriz de emisiones,
Secuencia observada | La probabilidad más alta de observar esa secuencia si se supone que E proviene de | Mayor probabilidad de observar esa secuencia | ||
---|---|---|---|---|
nordeste | 0.1344 | , | 0.1344 | , |
EE | 0.0490 | , | 0.0490 | , |
ES | 0.0560 | , | 0.0896 | , |
Total | 0.2394 | 0.2730 |
La nueva estimación de la E procedente de la emisión es ahora .
Esto nos permite calcular la matriz de emisión como se describe arriba en el algoritmo, sumando las probabilidades para las respectivas secuencias observadas. Luego repetimos porque si N vino de y porque si N y E vinieran de y normalizar.
|
|
|
Para estimar las probabilidades iniciales asumimos que todas las secuencias comienzan con el estado oculto y calcular la probabilidad más alta y luego repetir para . Nuevamente, luego normalizamos para dar un vector inicial actualizado.
Finalmente repetimos estos pasos hasta que las probabilidades resultantes converjan satisfactoriamente.
Aplicaciones
Reconocimiento de voz
Los modelos ocultos de Markov fueron aplicados por primera vez al reconocimiento de voz por James K. Baker en 1975. [9] El reconocimiento de voz continuo se produce mediante los siguientes pasos, modelados por un HMM. El análisis de características se realiza primero en características temporales y / o espectrales de la señal de voz. Esto produce un vector de observación. A continuación, la característica se compara con todas las secuencias de las unidades de reconocimiento de voz. Estas unidades pueden ser fonemas , sílabas o unidades de palabras completas. Se aplica un sistema de decodificación de léxico para restringir las rutas investigadas, por lo que solo se investigan las palabras del léxico del sistema (diccionario de palabras). De manera similar a la decodificación del léxico, la ruta del sistema está aún más limitada por las reglas de la gramática y la sintaxis. Finalmente, se aplica el análisis semántico y el sistema genera el enunciado reconocido. Una limitación de muchas aplicaciones HMM para el reconocimiento de voz es que el estado actual solo depende del estado en el paso de tiempo anterior, lo cual no es realista para el habla ya que las dependencias a menudo tienen varios pasos de tiempo de duración. [10] El algoritmo de Baum-Welch también tiene amplias aplicaciones en la resolución de HMM utilizados en el campo de la síntesis de voz. [11]
Criptoanálisis
El algoritmo de Baum-Welch se usa a menudo para estimar los parámetros de HMM para descifrar información oculta o ruidosa y, por lo tanto, se usa a menudo en criptoanálisis . En seguridad de datos, a un observador le gustaría extraer información de un flujo de datos sin conocer todos los parámetros de la transmisión. Esto puede implicar la ingeniería inversa de un codificador de canal . [12] Los HMM y, como consecuencia, el algoritmo de Baum-Welch también se han utilizado para identificar frases habladas en llamadas VoIP cifradas. [13] Además, el criptoanálisis HMM es una herramienta importante para las investigaciones automatizadas de datos de tiempo de caché. Permite el descubrimiento automático del estado crítico del algoritmo, por ejemplo, valores clave. [14]
Aplicaciones en bioinformática
Encontrar genes
Procariota
El software GLIMMER (Gene Locator and Interpolated Markov ModelER) fue uno de los primeros programas de búsqueda de genes que se utilizó para la identificación de regiones codificantes en el ADN procariota . [15] [16] GLIMMER utiliza modelos de Markov interpolados (IMM) para identificar las regiones codificantes y distinguirlas del ADN no codificante . Se ha demostrado que la última versión (GLIMMER3) tiene una mayor especificidad y precisión en comparación con sus predecesores con respecto a la predicción de los sitios de inicio de la traducción, demostrando una precisión promedio del 99% en la localización de ubicaciones 3 'en comparación con genes confirmados en procariotas. [17]
Eucariota
El servidor web GENSCAN es un localizador de genes capaz de analizar secuencias eucariotas de hasta un millón de pares de bases (1 Mbp) de longitud. [18] GENSCAN utiliza un modelo de Markov de quinto orden de tres períodos periódicos no homogéneos de regiones codificantes de ADN. Además, este modelo explica las diferencias en la densidad y estructura de genes (como las longitudes de los intrones) que ocurren en diferentes isocoros . Si bien la mayoría del software integrado de búsqueda de genes (en el momento del lanzamiento de GENSCAN) asumía que las secuencias de entrada contenían exactamente un gen, GENSCAN resuelve un caso general en el que hay genes parciales, completos o múltiples (o incluso ningún gen). [19] Se demostró que GENSCAN predice exactamente la ubicación del exón con un 90% de precisión y un 80% de especificidad en comparación con una base de datos anotada. [20]
Detección de variación de número de copias
Las variaciones en el número de copias (CNV) son una forma abundante de variación de la estructura del genoma en los seres humanos. Se utilizó un HMM bivariado de valor discreto (dbHMM) que asigna regiones cromosómicas a siete estados distintos: regiones no afectadas, deleciones, duplicaciones y cuatro estados de transición. La resolución de este modelo utilizando Baum-Welch demostró la capacidad de predecir la ubicación del punto de ruptura de la CNV a aproximadamente 300 pb a partir de experimentos de microarreglos . [21] Esta magnitud de resolución permite correlaciones más precisas entre diferentes CNV y entre poblaciones de lo que era posible anteriormente, lo que permite el estudio de las frecuencias de la población de CNV. También demostró un patrón de herencia directo para una NVC en particular .
Implementaciones
- Accord.NET en C #
- Biblioteca ghmm C con enlaces de Python que admite emisiones tanto discretas como continuas.
- Paquete HMMBase para Julia .
- HMMFit función en el RHmm paquete para R .
- hmmtrain en MATLAB
Ver también
- Algoritmo de Viterbi
- Modelo de Markov oculto
- Algoritmo EM
- Máxima verosimilitud
- Reconocimiento de voz
- Bioinformática
- Criptoanálisis
Referencias
- ^ Rabiner, Lawrence. "Primera mano: el modelo oculto de Markov" . Red de historia global IEEE . Consultado el 2 de octubre de 2013 .
- ^ Jelinek, Frederick; Bahl, Lalit R .; Mercer, Robert L. (mayo de 1975). "Diseño de un decodificador estadístico lingüístico para el reconocimiento de habla continua". Transacciones IEEE sobre teoría de la información . 21 (3): 250–6. doi : 10.1109 / tit.1975.1055384 .
- ^ Obispo, Martin J .; Thompson, Elizabeth A. (20 de julio de 1986). "Alineación de máxima probabilidad de secuencias de ADN". Revista de Biología Molecular . 190 (2): 159–65. doi : 10.1016 / 0022-2836 (86) 90289-5 . PMID 3641921 .
- ^ Durbin, Richard (23 de abril de 1998). Análisis de secuencia biológica: modelos probabilísticos de proteínas y ácidos nucleicos . Prensa de la Universidad de Cambridge. ISBN 978-0-521-62041-3.
- ^ Bilmes, Jeff A. (1998). Un suave tutorial del algoritmo EM y su aplicación a la estimación de parámetros para la mezcla gaussiana y modelos de Markov ocultos . Berkeley, CA: Instituto Internacional de Ciencias de la Computación. págs. 7-13.
- ^ Rabiner, Lawrence (febrero de 1989). "Un tutorial sobre modelos ocultos de Markov y aplicaciones seleccionadas en el reconocimiento de voz" (PDF) . Actas del IEEE . Consultado el 29 de noviembre de 2019 .
- ^ "Aplicaciones de Baum-Welch y HMM" (PDF) . Escuela de Salud Pública Johns Hopkins Bloomberg . Consultado el 11 de octubre de 2019 .
- ^ Frazzoli, Emilio. "Introducción a los modelos ocultos de Markov: el algoritmo de Baum-Welch" (PDF) . Aeronáutica y Astronáutica, Instituto de Tecnología de Massachusetts . Consultado el 2 de octubre de 2013 .
- ^ Baker, James K. (1975). "El sistema DRAGON: una descripción general". Transacciones IEEE sobre acústica, habla y procesamiento de señales . 23 : 24-29. doi : 10.1109 / TASSP.1975.1162650 .
- ^ Rabiner, Lawrence (febrero de 1989). "Un tutorial sobre modelos ocultos de Markov y aplicaciones seleccionadas en el reconocimiento de voz". Actas del IEEE . 77 (2): 257–286. CiteSeerX 10.1.1.381.3454 . doi : 10.1109 / 5.18626 .
- ^ Tokuda, Keiichi; Yoshimura, Takayoshi; Masuko, Takashi; Kobayashi, Takao; Kitamura, Tadashi (2000). "Algoritmos de generación de parámetros de voz para síntesis de voz basada en HMM". Conferencia internacional IEEE sobre acústica, habla y procesamiento de señales . 3 .
- ^ Dingel, Janis; Hagenauer, Joachim (24 de junio de 2007). "Estimación de parámetros de un codificador convolucional a partir de observaciones ruidosas". Simposio internacional de IEEE sobre teoría de la información .
- ^ Wright, Charles; Ballard, Lucas; Coull, Scott; Monrose, Fabian; Masson, Gerald (2008). "Avísame si puedes: descubriendo frases habladas en conversaciones VoIP cifradas". Simposio internacional de IEEE sobre seguridad y privacidad .
- ^ Brumley, Bob; Hakala, Risto (2009). Ataques de plantillas de tiempo de caché . Avances en criptografía . Apuntes de conferencias en informática. 5912 . págs. 667–684. doi : 10.1007 / 978-3-642-10366-7_39 . ISBN 978-3-642-10365-0.
- ^ Salzberg, Steven; Delcher, Arthur L .; Kasif, Simon; White, Owen (1998). "Identificación de genes microbianos utilizando modelos de Markov interpolados" . Investigación de ácidos nucleicos . 26 (2): 544–548. doi : 10.1093 / nar / 26.2.544 . PMC 147303 . PMID 9421513 .
- ^ "Glimmer: sistema de búsqueda de genes microbianos" . Universidad Johns Hopkins - Centro de Biología Computacional.
- ^ Delcher, Arthur; Bratke, Kirsten A .; Powers, Edwin C .; Salzberg, Steven L. (2007). "Identificación de genes bacterianos y ADN endosimbionte con Glimmer" . Bioinformática . 23 (6): 673–679. doi : 10.1093 / bioinformatics / btm009 . PMC 2387122 . PMID 17237039 .
- ^ Burge, Christopher. "El servidor web GENSCAN en el MIT" . Archivado desde el original el 6 de septiembre de 2013 . Consultado el 2 de octubre de 2013 .
- ^ Burge, Chris; Karlin, Samuel (1997). "Predicción de estructuras génicas completas en el ADN genómico humano". Revista de Biología Molecular . 268 (1): 78–94. CiteSeerX 10.1.1.115.3107 . doi : 10.1006 / jmbi.1997.0951 . PMID 9149143 .
- ^ Burge, Christopher; Karlin, Samuel (1998). "Encontrar los genes en el ADN genómico". Opinión actual en biología estructural . 8 (3): 346–354. doi : 10.1016 / s0959-440x (98) 80069-9 . PMID 9666331 .
- ^ Korbel, Jan ; Urbano, Alejandro; Grubert, Fabien; Du, Jiang; Royce, Thomas; Starr, Peter; Zhong, Guoneng; Emanuel, Beverly; Weissman, Sherman; Snyder, Michael; Gerstein, Marg (12 de junio de 2007). "Predicción sistemática y validación de puntos de corte asociados con variaciones en el número de copias en el genoma humano" . Actas de la Academia Nacional de Ciencias de los Estados Unidos de América . 104 (24): 10110–5. Código bibliográfico : 2007PNAS..10410110K . doi : 10.1073 / pnas.0703834104 . PMC 1891248 . PMID 17551006 .
enlaces externos
- Una revisión completa de los métodos y el software de HMM en bioinformática - Profile Hidden Markov Models
- Publicaciones tempranas de HMM por Baum:
- Una técnica de maximización que ocurre en el análisis estadístico de funciones probabilísticas de cadenas de Markov
- Una desigualdad con aplicaciones a la estimación estadística para funciones probabilísticas de los procesos de Markov y a un modelo para la ecología
- Inferencia estadística para funciones probabilísticas de cadenas de Markov de estado finito
- La conferencia Shannon de Welch, que habla de cómo se puede implementar el algoritmo de manera eficiente:
- Modelos ocultos de Markov y el algoritmo de Baum-Welch , IEEE Information Theory Society Newsletter, diciembre de 2003.
- Una alternativa al algoritmo de Baum-Welch, el algoritmo de recuento de rutas de Viterbi:
- Davis, Richard IA; Lovell, Brian C .; "Comparación y evaluación de algoritmos de entrenamiento de conjuntos HMM utilizando criterios de número de condición y de prueba y de tren" , Análisis de patrones y aplicaciones, vol. 6, no. 4, págs. 327–336, 2003.
- Una hoja de cálculo interactiva para enseñar el algoritmo hacia adelante y hacia atrás (hoja de cálculo y artículo con un tutorial paso a paso)
- Derivación formal del algoritmo de Baum-Welch
- Implementación del algoritmo de Baum-Welch