Aplicaciones de los modelos de Markov

Aplicaciones de los modelos de Markov

Junior Ulises Sinche – Marvin Alonso Agila.

jusinche@utpl.edu.ecmaagila@utpl.edu.ec

Universidad Técnica Particular de la Loja

Escuela de Ciencias de la Computación

1. Resumen

Los modelos ocultos de Markov (HMM) constituyen una herramienta de modelización altamente flexible, inicialmente utilizada en el campo del reconocimiento automático del habla, que ha encontrado

en los últimos años numerosas aplicaciones en áreas científico-técnicas muy diversas, aunque su utilización en ecología es aún escasa. En este paper se describen los elementos esenciales de los HMM, se presentan algunos de los algoritmos básicos que facilitan su estimación y se indican algunas aplicaciones recientes, pues permiten incorporar en el proceso de modelización información a priori sobre el sistema analizado.

2. Introducción

Los modelos ocultos de Markov (que escribiremos, en adelante, HMM, tanto en singular como en plural), son una técnica de modelización de datos secuenciales aplicada inicialmente en el campo del reconocimiento automático del habla, donde actualmente es una herramienta casi imprescindible, que ha encontrado aplicación en disciplinas diversas, como el análisis de imágenes o la psicología, destacando su uso creciente en bioinformática, donde los HMM están ya bien establecidos y en el análisis de electroencefalogramas y otras bioseñales

Palabras clave: HMM, estados ocultos, patrones complejos,

3. Usos y Aplicaciones de los Modelos Ocultos de Markov 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.

Reconocimiento de Gestos.

Seguimiento de la mano en una secuencia de imágenes:

Características.

Observaciones:

cambio en X (DX)

cambio en Y (DY)

cambio en área (DA)

cambio en razón X-Y (DR)

Cada una se codifica en 3 valores: (+, 0, -)

Se utiliza HMM para cada gesto (5 gestos):

3 estados: gestos simples

5 estados: gestos complejos.

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. Pueden escribirse usando Phyton:

<source lang=”python”> estados = (‘Lluvioso’, ‘Soleado’)

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

probabilidad_inicial = {‘Lluvioso’: 0.6, ‘Soleado’: 0.4}

probabilidad_transicion = {‘Lluvioso’ : {‘Lluvioso’: 0.7, ‘Soleado’: 0.3}, ‘Soleado’: {‘Lluvioso’: 0.4, ‘Soleado’: 0.6},}

probabilidad_emision = { ‘Lluvioso’ : {‘caminar’: 0.1, ‘comprar’: 0.4, ‘limpiar’: 0.5},

‘Soleado’ : {‘caminar’: 0.6, ‘comprar’: 0.3, ‘limpiar’: 0.1}, } </source>

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_transicion 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_emision 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.

Criptoanálisis.

Criptoanálisis (del griego kryptós, “escondido” y analýein, “desatar”) es el estudio de los métodos para obtener el sentido de una información cifrada, sin acceso a la información secreta requerida para obtener este sentido normalmente. Típicamente, esto se traduce en conseguir la clave secreta.

Firma Manuscrita On-Line.

La biometría basada en firma manuscrita dinámica (‘on-line’) hace uso de la información instantánea proporcionada por la tableta de firma. Por contraposición, se habla de firma estática (‘off-line’) cuando no se tienen acceso al acto de firma, y sólo se dispone de su forma como imagen

Retos de la Biometría de Firma On-Line

ü Alta variabilidad intra-clase

ü Variabilidad temporal entre sesiones

ü Los impostores pueden producir falsificaciones entrenadas (‘skilled forgeries’)

ü Baja compatibilidad con imágenes estáticas de firma

Líneas del Futuro.

ü Análisis exhaustivo del poder discriminante (frente a falsificaciones e imitaciones casuales) de combinaciones de parámetros globales

ü Estudio de la estructura y complejidad de las firmas, y su relación con la variabilidad y rendimiento dependiente de usuario

ü Desarrollo de criptosistemas biométricos basados en firma dinámica, p.ej., generación de claves criptográficas

ü Estudio de posibles ataques a sistemas de verificación de firma dinámica, como ataques de fuerza bruta o tipo ‘hill-climbing’, y contramedidas

ü Aplicación de las técnicas desarrolladas a diferentes escenarios de firma dinámica, como Tablet PC, o PDA (NoE Biosecure)

ü Nuevas BBDD multi-sensor (tableta, Tablet PC, PDA, …), multi-sesión a largo plazo (años), con diferentes grados de imitación (esfuerzos en NoE Biosecure)

ü Estudio de interoperabilidad de sensores y seguimiento de los esfuerzos de estandarización.

4. Conclusiones

El aspecto que consideramos fundamental en la aplicación de HMM es la utilización de un modelo explícito de la estructura del patrón, a través de la selección de la topología del HMM. De esta forma, el conocimiento que se tenga a priori sobre el sistema, o que se derive de otro tipo de análisis descriptivos previos, puede incorporarse en el proceso de modelización, permitiendo un estudio más profundo y detallado.

En las áreas en las que los HMM están más extendidos, se utilizan, en general, con un enfoque de aprendizaje automático, en problemas en los que se dispone de una abundante base de datos (denominados de entrenamiento) con los que es posible seleccionar y estimar el HMM más apropiado (a veces, con un gran número de estados ocultos), obteniéndose modelos con una alta capacidad de predicción, pues el problema típico es clasificar o identificar nuevos datos. Aunque una situación similar puede darse en algunos problemas de interés en ecología (e.g., modelización de series de precipitaciones o de datos de teledetección), es más habitual que se disponga de un conjunto reducido de datos y que el enfoque sea más de tipo estadístico, en el sentido de que se desee poder obtener intervalos de confianza para las estimaciones de los parámetros y poder contrastar tanto los valores de ajuste de un cierto modelo como distintos modelos alternativos.

Por último, aunque los algoritmos necesarios para los HMM discretos son fácilmente implementables, la complejidad aumenta en el caso continuo y en las extensiones a los modelos básicos. Afortunadamente, existen distintas herramientas para el trabajo con HMM disponibles, muchas de ellas de uso libre, para diferentes entornos de computación. Entre otras opciones, el programa comercial MATLAB (http://www.mathworks.com/products/matlab/), en su paquete (toolbox) de estadística, ofrece las funciones básicas para construir, simular y analizar HMM discretos.

5. Referencias

A. M. Derouault and B. Merialdo, “Natural Language Modeling for Phoneme-to-Text

Transcription”, IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol.

PAMI-8, Nº. 6, noviembre 1986, pp. 742-749.

U. Essen and V. Steinbiss, “Cooccurrence Smoothing for Stochastic Language Modeling”,

Proc. of ICASSP’92, San Francisco, Estados Unidos, 23-26 marzo 1992, Vol. I, pp. 161-164.

D. Goddeau and V. Zue, “Integrating Probabilistic LR Parsing Into Speech Understanding

Systems”, Proc. of ICASSP’92, San Francisco, Estados Unidos, 23-26 marzo 1992, Vol. I,

pp. 181-184.

I. J. Good, “The Population Frequencies of Species and the Estimation of Population

Parameters”, Biometrika, Vol. 40, Partes 3 y 4, diciembre 1953, pp. 237-264.

M. Jardino, “Multilingual Stochastic N-Gram Class Language Models”, Proc. of ICASSP’96, Atlanta, Estados Unidos, 7-10 mayo 1996, pp. 161-163.

F. Jelinek, “The Development of an Experimental Discrete Dictation Recognizer”,

Proceedings of the IEEE, Vol. 73, Nº. 11, noviembre 1985, pp. 1616-1623.


  1. Luis

    Es interesante tu trabajo , voy a hacer una implementacion en lisp asi ke me ayudarias mucho si me ayudaras a ver donde es recursivo los algoritmos de HMM




Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s



A %d blogueros les gusta esto: