Cadenas de markov tiempo continuo

INTRODUCCION

Los modelos markovianos ocultos (HMM) asumen que el sistema estudiado sigue un proceso de markov con parámetros desconocidos.

La tarea fundamental consiste en determinar los parámetros ocultos a partir de parámetros observados. La diferencia fundamental respecto a un modelos de markov habitual consiste en que los estados no son directamente visibles para el observador, pero si lo son las variables influenciadas por el estado. Cada estado tiene una distribución de probabilidad asociada sobre el conjunto de posibles valores de salida. La secuencia de valores de salida generados a partir de un HMM son darán cierta información sobre la secuencia de estados.

MODELOS OCULTOS DE MARKOV

Un Modelo Oculto de Markov (Hidden Markov Model HMM) es un proceso estocástico que consta de un proceso de Markov no observado (oculto) q = {qt}t∈Ν y un proceso observado O = {ot}t∈Ν cuyos estados son dependientes estocásticamente de los estados ocultos, es decir, es un proceso bivariado (q,O). Los HMMs se pueden considerar también como sistemas generativos estocásticos, los cuales se emplean en la modelación de series de tiempo.

DEFINICION DE MODELOS OCULTOS DE MARKOV

Un modelo oculto de Markov es una cadena de q junto con un proceso estocástico que toma valores en un alfabeto Σ y el cual depende de q.

Estos sistemas evolucionan en el tiempo pasando aleatoriamente de estado a estado y emitiendo en cada momento al azar algún símbolo del alfabeto Σ. Cuando se encuentra en el estado qt-1 = i, tiene la probabilidad aij de moverse al estado qt = j en el siguiente instante y la probabilidad bj(k) de emitir el símbolo ot = vk en el tiempo t.

Solamente los símbolos emitidos por el proceso q son observables, pero no la ruta o secuencia de estados q, de ahí el calificativo de "oculto" de Markov, ya que el proceso de Markov q es no observado.

ARQUITECTURA DE UN MODELOS OCULTO DE MARKOV

El diagrama muestra la arquitectura general de un HMM. Cada ovalo representa una variable aleatoria que puede tomar determinados valores. La variable aleatoria x(t) es el valor de la variable oculta en el instante de tiempo t. La variable aleatoria y(t) es el valor de la variable observada en el mismo instante de tiempo t, las flechas indican dependencias condicionales.

TIPOS DE PROBLEMAS RELACIONADOS CON HMM

Dado el HMM ¿Cuál es la probabilidad de una secuencia de observables? Dado el HMM y una secuencia observable ¿Cuál es la secuencia de

estados mas probables que ha generado la secuencia observable? Dado un conjunto de estados y una colección de secuencias observables.

¿cuál es el HMM más probable que ha generado la secuencia

ALGORITMO DE FORWARD

Consideremos la función a t(i):

a t(i)=p (o1,o2…op .q t=siІ λ

Esta ecuación puede calcularse de forma recursiva

ALGORITMO DE VITERBI

El objetivo es saber cuál es la secuencia de estados que maximiza P(O l Q , λ):

Que puede calcularse recursivamente como:

La probabilidad de la secuencia óptima será:

ALGORITMO BAUM WELCH

Número de veces promedio que se pasa por un estado:

Número de veces que se usa un arco:

El nuevo HMM será:

Ejemplo:

El siguiente ejemplo ilustra un proceso q independiente del tiempo. Supóngase que en un salón se encuentra un número N muy grande de urnas de vidrio. Dentro de cada urna se tiene una cantidad M de bolas de colores. Un mago está en el salón y de acuerdo con algún procedimiento aleatorio elige una urna inicial. De ésta saca al azar una bola y registra su color como una observación. La bola es retornada a la urna de la cual fue seleccionada. A continuación selecciona una nueva urna de acuerdo con un procedimiento aleatorio que depende de la urna actual y la elección de alguna bola es repetida. Este proceso completo se realiza en un tiempo T y genera una secuencia de observación finita de colores O de longitud T, la cual puede modelarse como la salida observable de un HMM. Se asume que las urnas son seleccionadas independientemente.

Los siguientes son ejemplos de posibles secuencias de observación del modelo de las

Urnas y las bolas:

O1

= (amarillo, verde, azul, verde, rojo, amarillo, naranja, rojo, verde, azul, amarillo),

O2

= (amarillo, rojo, verde, rojo, azul, naranja, verde, rojo, azul, amarillo, rojo, verde),

O3

= (rojo, azul, amarillo, rojo, azul, vede, rojo, amarillo, naranja, naranja, verde, rojo),

O4

= (rojo, verde, naranja, rojo, rojo, azul, verde, amarillo, azul, rojo, verde, rojo).

El alfabeto es:

Σ = verde, azul, rojo, amarillo, naranja

Los estados ocultos son:

Q = {1,2,...,N}

Las probabilidades de obtener un color en cada urna son:

El primer problema consiste en decidir cual proceso es representado por los estados y después decidir cuantos estados pueden estar en el modelo. Como se ilustró antes, el HMM más simple que corresponda al comportamiento de este proceso es aquel en el cual cada estado representa una urna específica y cada color representa un posible símbolo de observación. Por cada estado se define una probabilidad de extraer una bola (color) y una probabilidad de pasar a la siguiente urna. Los colores de las bolas dentro de cada urna pueden o no ser los mismos y pueden existir números diferentes de bolas de cada color en cada urna. Por lo tanto, una observación aislada de un color en particular no dice inmediatamente de cuál urna procede.

APLICACIONES DE LOS HMM

Varios son los usos y aplicaciones de los HMM, en la era moderna; en distintas aplicaciones, ya que son de un gran interés para la realización de procesos complejos involucrados a problemas de gran envergadura, por tal razón como el área de aplicación es inmensa solo describiremos unos pocos usos con la finalidad de tener una visión clara del futuro de los HMM.

Reconocimiento Automático de la Voz.

La tarea que debe realizar un sistema automático de reconocimiento de voz es encontrar la cadena de palabras que satisfaga:

W=arg max P(A W)P(W)

Donde A son los datos acústicos y W= w1, w1,…, wn, con wi∈V, denota la cadena de n palabras de entre un vocabulario de tamaño fijo V.

En este caso una palabra queda definida por su pronunciación. Si una palabra tiene varias pronunciaciones se considerará que son

dos entidades diferentes. Los vocablos homófonos se considerarán una única palabra.

Imaginémonos que tenemos un amigo que vive lejos y con quien habla a diario por teléfono acerca de lo que hizo durante el día. A su amigo le interesan tres actividades: caminar por la plaza, salir de compras y limpiar su departamento. Lo que su amigo hace depende exclusivamente del estado del tiempo en ese día. Usted no tiene información clara acerca del estado del tiempo donde su amigo vive, pero conoce tendencias generales. Basándose en lo que su amigo le dice que hizo en el día, usted intenta adivinar el estado del tiempo.

Supóngase que el estado del tiempo se comporta como una cadena de Markov discreta. Existen dos estados, “Lluvioso” y “Soleado”, pero usted no los puede observar directamente, es decir, están ocultos. Existe también una cierta posibilidad de que su amigo haga una de sus actividades cada día, dependiendo del estado del tiempo: “caminar”, “comprar” o “limpiar”. Dado que su amigo le cuenta sus actividades del día, esas son las observaciones. El sistema completo es un modelo oculto de Markov.

Usted conoce las tendencias generales del tiempo en el área y lo que a su amigo le gusta hacer. En otras palabras, los parámetros del HMM son conocidos.

Estados = (‘Lluvioso’, ‘Soleado’)

Observaciones = (‘caminar’, ‘comprar’, ‘limpiar’)

Probabilidad inicial = {‘Lluvioso': 0.6, ‘Soleado': 0.4}

probabilidad transición = {‘Lluvioso’: {‘Lluvioso': 0.7, ‘Soleado': 0.3}, ‘Soleado’: {‘Lluvioso': 0.4, ‘Soleado': 0.6},}

probabilidad emisión = {‘Lluvioso’: {‘caminar': 0.1, ‘comprar': 0.4, ‘limpiar': 0.5},

‘Soleado’: {‘caminar': 0.6, ‘comprar': 0.3, ‘limpiar': 0.1}, }

En esta porción de código, probabilidad inicial representa el estado en el que usted cree que se encuentra el HMM la primera vez que su amigo lo llama (es decir, sabe que es un poco más probable que esté lluvioso). La distribución de probabilidades que se usó aquí no es la de equilibrio, que es (dadas las probabilidades de transición) aproximadamente {‘Lluvioso': 0.571, ‘Soleado': 0.429}.

La probabilidad transición representa el cambio del tiempo en la cadena de Markov por detrás del modelo. En este ejemplo, hay un 30% de probabilidad de que mañana esté soleado si hoy llovió. La probabilidad emisión representa con cuanta probabilidad su amigo realiza una actividad determinada cada día. Si llueve, hay un 50% de probabilidad de que esté limpiando su departamento; si hay sol, hay un 60% de probabilidades de que haya salido a caminar.

MODELIZACIÓN DE TRANSECTOS DE VEGETACIÓN MEDIANTE HMM

Veamos con un ejemplo cómo se aplican los conceptos anteriores; se tratará de modelizar transeptos de vegetación con datos de presencia-ausencia. Los datos consisten en transeptos realizados en una zona semiárida (Benidorm, Alicante, SE España), cada uno de 25 m de longitud con 250 puntos igualmente espaciados, en dos áreas contiguas (cuatro transeptos en cada una), una quemada y otra no quemada (véase Bautista, 1999; Bellot et al., 2000, para más detalles y discusión sobre los datos).

Resultaba evidente, a partir de la simple observación de campo, que, a la escala considerada, la vegetación definía manchas, o zonas más vegetadas, y claros, o zonas con escasa vegetación, con un cierto patrón de distribución, con diferencias entre la zona quemada y no quemada (tres años después del incendio). De hecho, un análisis descriptivo clásico de patrones en transectos de vegetación, de la familia del análisis de la varianza en bloques (Greig-Smith, 1952; Greig-Smith, 1979; Hill, 1973), mostraba un patrón complejo, con similitudes globales y diferencias en tamaño de grano e intensidad entre las dos zonas (Bautista y Vallejo, 2002).

Un primer tipo de HMM que podemos considerar constaría de dos estados ocultos, correspondientes a las manchas y claros, que son los elementos del sistema en los que estamos interesados y que deseamos describir de la forma más precisa posible. Estos elementos no son directamente observables, pues, aunque la probabilidad de encontrar vegetación en un punto del transecto correspondiente a una mancha es mayor que si estamos en un claro, es posible registrar ausencia de vegetación en el primer caso y presencia en el segundo. Los símbolos del modelo serían dos, correspondientes a presencia y ausencia de vegetación. El modelo tendría, por tanto, cuatro parámetros básicos independientes, dos probabilidades de transición y dos de emisión (el resto queda determinado por la condición de que la suma de las probabilidades de transición, y también de emisión, desde un cierto estado debe ser la unidad). Si para los estados escribimos 1 para mancha y 2 para claro, y para los símbolos 1 para presencia y 2 para ausencia de vegetación, podemos considerar como parámetros independientes las dos

probabilidades de transición entre diferentes estados (T12 y T21) y las dos probabilidades de observar presencia de vegetación en manchas (E11) y en claros (E21), teniéndose que T11=1-T12, T22=1-T21, E12=1-E11 y E22=1-E21

Este modelo puede ayudar a entender el sentido de considerar estados ocultos, que es la idea fundamental de los HMM. Sin embargo, conociendo el sistema que se trata de modelizar, no es esperable que este modelo sea muy apropiado, pues sería más adecuado en situaciones con patrones simples, con manchas y claros relativamente homogéneos, como podría esperarse, por ejemplo, en algunas comunidades herbáceas de pastizales, en donde HMM de este tipo han sido utilizados para detectar bordes de manchas (Ver Hoef & Cressie, 1997).

En el caso que estamos considerando, se tendrían plantas arbustivas agrupadas en ciertas zonas con áreas de escasa vegetación entre ellas, existiendo, por tanto, dos niveles de manchas, el de la agrupación y el de los propios arbustos, resultando en el patrón complejo exhibido por los análisis descriptivos clásicos. Una de las ventajas de los HMM es que esta información a priori sobre el sistema se puede introducir en el proceso de modelización, mediante la elección de la topología del modelo. Así, podemos considerar tres estados ocultos; un primer estado, correspondiente a los arbustos, que denominamos manchas (1), pequeños claros entre manchas (2) y claros (3), de modo que una sucesión de los dos primeros estados constituirían agrupaciones de manchas, separadas entre sí por los claros. En este modelo, las transiciones entre los estados 2 y 3 no tendrían sentido; por tanto, el modelo queda determinado por siete parámetros básicos independientes, cuatro probabilidades de transición (T12, T13, T21 y T31) y las tres probabilidades de observar presencia de vegetación en cada uno de los tres estados (E11, E21 y E31). En la Figura 2B se muestra un esquema de la topología del modelo.

La Tabla 1 muestra los valores de los parámetros, estimados mediante el algoritmo de Baum-Welch, aplicando los dos modelos descritos a los transectos en las zonas quemada y no quemada. Sin entrar en un análisis detallado, los parámetros muestran una estructura similar en las dos zonas, con valores algo mayores de las probabilidades de transición entre estados en la zona quemada, lo que implica un menor tamaño de las manchas y claros.

Una vez estimados los parámetros, la aplicación del algoritmo de Viterbi proporciona la sucesión de estados ocultos y, con ello, una descripción detallada de los tamaños de manchas y claros. En los transectos originales es difícil encontrar una sucesión de puntos con presencia o ausencia continua de vegetación; en la sucesión de estados ocultos estimada, sin embargo, se detectan series continuas de manchas y claros de mayor longitud, especialmente en el caso del modelo con tres estados.

Bibliografía

file:///C:/Users/kathe%20andrea/Downloads/dcart.pdf

http://es.slideshare.net/efcuencaq/modelos-ocultos-de-markov

http://www.virtual.unal.edu.co/cursos/ingenieria/2001832/lecturas/hmm.pdf