Archivo para mayo, 2008

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.

Anuncios

Red Bayesiana

Una red bayesiana se la utiliza para representar el conocimiento y el razonamiento probabilístico de una forma grafica. Una red bayesiana esta representada por grafos los que están formados por dos elementos un nodo y un arco, los nodos representan las variables y los arcos son las relaciones probabilísticas entre los nodos.

Grafos

Un grafo es un par de conjuntos G =(X, L) donde X es un conjunto finito de elementos (nodos) y L es un conjunto de arcos, es decir, un subconjunto de pares ordenados de elementos distintos de X.

Los grafos son utilizados para representar modelos probabilísticos, las relaciones entre las variables, donde cada variable representa un nodo y la relación entre ellas por medios de arcos.

Una red Bayesiana se la puede representar como un conjunto de variables X= {X1,.., Xn}, y se la puede representar como un grafo acíclico dirigido, donde los nodos están en relación uno a uno con las variables.

imagen4

Estructura de una red bayesiana

Búsqueda –score.- Permite medir la estructura de la red y el conocimiento que se puede adquirir, un procedimiento de búsqueda para determinar el mejor modelo de datos.

Análisis de dependencia.- Permite determinar el grado de dependencia usando pruebas estadísticas.

Tipos de aprendizajes redes bayesianas

Aprendizaje paramétrico.- Aprende las probabilidades de la red en base a casos dados.

Aprendizaje estructural.- Estos algoritmos son capaces de aprender enlaces.

Modelos Canónicos

E1 Análisis Canónico introducido por H. Hotelling (1935, 1936) como método de deterrninación del grado de asociación existente entre dos grupcas de variables, ha sido desarrollado desde entonces en dos direcciones: el Análisis Canónico Generalizado y el Análisis Canónico Parcial. Podemos representar las medidas de probabilidad condicional asociados a los nodos de la red. El tamaño de las tablas de probabilidad aumenta exponencialmente con el número de padres de un nodo, es necesario utilizar modelos para reducir el número de parámetros necesarios. Para reducirlos utilizamos los modelos canónicos:

  • Modelo de interacción conjuntiva (Noisy AND).
  • Compuerta Max (Noisy Max gate).
  • Compuerta Min (Noisy Min gate).
  • Modelo de interacción disyuntiva (Noisy OR).

Estos modelos se los pueden aplicar depende a un caso dado, dependen fundamentalmente de las relaciones entre los dominios. El mas importante es el Noisy OR, es utilizado cuando varias causas ocasión un efecto cada una independiente por si mismo.

.Modelo de interacción disyuntiva (Noisy OR)

Este modelo se lo utiliza para representar representaciones de n…1, cuando existen algunas causas y ocasionan un efecto cada una por si sola, y la causa de la probabilidad del efecto no se decrementa si existen varias causas.

Este modelo utiliza variables binarias.

Ejemplo: Se emplea el modelo noisy OR cuando varias acciones producen el mismo efecto.

Estructura

imagen5

Propiedades:

· Responsabilidad.- El efecto causa por una o varias causas es falso si todas sus posibles causas son falsas

· Independencia de excepciones.- Los efectos son manifestaciones de varias causas.

Si bien es cierto que muchas de las cosas que observamos en películas futuristas son simplemente el producto de la imaginación de los productores, también tienen una contraparte realista pues existen muchas entidades, organizaciones, departamentos gubernamentales (especialmente de países desarrollados) que basándose en este tipo de ideas, invierten mucho tiempo y dinero en construir prototipos de robots y/o máquinas con características de ordenadores con la finalidad de superar la frontera de simples máquinas programables, a máquinas pensantes.

Cuando era pequeño me preguntaba ¿Cómo harán los robots? ¿Las computadoras lo saben todo? ¿Algún día podremos tener como un amigo a un robot, o al menos una computadora con la cual se pueda conversar? ¿Cómo lo harán?

Bueno para responder a la mayoría de preguntas aunque sea de una forma rápida, sencilla y quizá un poco imprecisa utilizaré algún navegador web y alguno de los diferentes buscadores disponibles, pero específicamente para la última pregunta responderé con algunos elementos que se nos ha indicado en la materia de Inteligencia Artificial Avanzada.

CLASIFICACIÓN:

1. Reconocimiento de formas

1.1. Aproximaciones paramétricas: Se tienen un conocimiento a priori acerca de la forma funcional de las distribuciones de probabilidad de cada clase sobre el espacio de representación.

1.2. Aproximaciones no paramétricas: No supone ninguna forma de las distribuciones de probabilidad sobre el espacio de representación, de modo que el único conocimiento a priori será el correspondiente a la información inducida a partir del conjunto de muestras.

2. Reconocimiento de patrones

2.1. Clasificación supervisada: Parte de un conjunto de objetos descritos por un vector de características y la clase a la que pertenece cada uno de ellos; a este conjunto de objetos de los que conocemos la clase a la que pertenecen se los denomina “conjunto de entrenamiento” o “conjunto de aprendizaje”.

2.2. Clasificación no supervisada: Enfoca la clasificación como el descubrimiento de clases del problema. Los objetos únicamente vienen descritos por un vector de características.

3. Situaciones dentro del problema clasificatorio

3.1. Clases que definen el problema son separables: Cuando todos los objetos con las mismas características pertenecen a la misma clase.

3.2. Clases que definen el problema no son separables: Cuando dos o más objetos con las mismas características pertenecen a diferentes clases.

Seguir leyendo »

INTRODUCCION.- El problema de clasificación consiste en la construcción de un modelo a partir de un conjunto de datos preclasificados que permita clasificar nuevas observaciones.

El conjunto de datos debe tener un conjunto de variables explicativas así:

[X1; X2; : : : ;Xk], denominadas atributos en el lenguaje de la Inteligencia Artificial, y una variable respuesta cualitativa Y que indica la clase a la que pertenece cada observación.

 

 

 

 

 

 

 

 

 

 

 

 

Comentarios:

  • i indexa ejemplos, mientras que t indexa clasificadores (débiles)
  • Dt depende de la complejidad de los ejemplos. ¿Cómo usarla?
  • αt depende del error εt asociado a la ht
  • Zt es una constante de normalización.

 

  • Conjunto de validación:
  • Aleatoriamente se parte el conjunto inicial de ejemplos en dos grupos.
  • Uno se usa como conjunto de entrenamiento, para ajustar los
  • parámetros de aprendizaje del clasificador.
  • El otro es el conjunto de validación y se usa para estimar el error de
  • generalización.
  • Se entrena hasta alcanzar el error de validación mínimo.

CLASIFICACION Y VALIDACIÓN CRUZADA

 

La validación cruzada es un método de estimación predictiva de error, la cual separa el conjunto de datos en K grupos de igual tamaño, k modelos predictivos son construidos, cada uno probado sobre un distinto grupo después de haber sido entrenado sobre los restantes grupos, este proceso puede ser repetido varias veces para incrementar la confiabilidad de la estimación.

 

CONCLUSION:

  • Se puede aplicar la validación de clasificadores a sistemas inteligentes para elaborar clasificadores a partir de los datos ya clasificados, ya que a partir de las características de los datos, el sistema diseña un método de clasificación apropiado al problema