Sistemas de Reconocimiento de Patronesbibing.us.es/proyectos/abreproy/3851/fichero/PFC-3.pdfSistemas de Reconocimiento de Patrones 3.1. Introducci´on La senal˜ del habla tal y como

Capıtulo 3

Sistemas de Reconocimiento de

Patrones

3.1. Introduccion

La senal del habla tal y como ha sido analizada en el capıtulo anterior posee carac-terısticas comunes para las distintas muestras de las misma unidades linguısticas. Estascaracterısticas comunes en el caso de los vectores de coeficientes cepstrales son las zonasdel espacio de estos vectores en los que se localiza la pronunciacion de cada fonema. Lasecuencia de vectores extraıda del analisis de una pronunciacion sigue un patron carac-terıstico en cada caso. Se estudiaran en este capıtulos algunos de los medios que se conocenpara analizar y reconocer dichos patrones de modo que se pueda proceder a la clasificacionde las muestras de audio de entrada.

Los medios analizados en este capıtulo se basan en sistemas de aprendizaje y valida-cion. Es decir son modelos que adaptan sus parametros en funcion de los datos que lesson proporcionados como validos. De los datos de entrenamiento tendran que extraer lospatrones necesarios para validar los datos que se introduzcan posteriormente y que sepodran identificar al intentar validarlos sobre cada modelo entrenado.

3.2. Redes Neuronales

Las redes neuronales son sistemas compuestos por un elevado numero de unidadessimples interconectadas que simulan la actividad del cerebro. Cada una de estas unidades,

55

56 CAPITULO 3. SISTEMAS DE RECONOCIMIENTO DE PATRONES

equivalentes a las neuronas en una simulacion biologica, es parte de una estructura porcapas, y produce una salida que es funcion no lineal de las entradas. La salida de cadacapa de unidades esta conectada a las unidades de la capa superior con conexiones directasy equivalentes a la sinapsis del cerebro. Esta es basicamente la actividad de un cerebrobiologico y es interesante verificar como se pueden resolver problemas complejos de formaeficiente con un sistema de procesamiento sustancialmente simple.

Las redes neuronales han encontrado aplicacion en campos muy diversos debido a laflexibilidad de la topologıa de red, a que se pueden iniciar experimentos sin realizar muchashipotesis sobre el fenomeno modelado y a los resultados satisfactorios que se obtienen enproblemas de clasificacion.

3.2.1. La Neurona o Unidad Logica con Umbral (ULU)

Cada una de las unidades simples de las que se compone una red neuronal se denominaunidad logica con umbral (ULU). Esta unidad realiza una suma ponderada de las entradas,compara esa suma con un umbral y, si dicha suma supera un umbral, devuelve como salidaun uno; en cualquier otro caso produce un 0.

Las funciones booleanas que pueden ser implementadas mediante una ULU se deno-minan funciones linealmente separables. Este nombre se debe a que una ULU separa elespacio de los vectores de entrada en dos regiones, la de los vectores que quedan por encimadel umbral y la de aquellos que quedan por debajo, mediante una superficie lineal deno-minada hiperplano de n dimensiones. Muchas funciones booleanas, aunque, por supuesto,no todas son linealmente separables. En la Figura 3.1 se muestra una ULU que representaun monomio. Los pesos de las entradas se colocan junto a las correspondientes lıneas deentrada y el umbral se coloca dentro del cırculo que representa a la ULU. Un ejemplo defuncion booleana no separable es la funcion XOR (f = x1x2 + x1x2). Como ejemplo en laFigura3.2 se puede ver la ULU que implementa la funcion f = (x1 + x2)(x3 + x4).

En aplicaciones donde solo existen dos resultados posibles en el proceso de clasificacion,eleccion o reconocimiento, puede ocurrir que con una sola ULU se pueda implementar lafuncion de seleccion, siempre y cuando se tenga como entrada una representacion codificadadel vector de caracterısticas. Sin embargo, para problemas mas complejos seguramentesera necesaria una red de ULU.

3.2. REDES NEURONALES 57

Figura 3.1: Unidad logica con umbral (ULU).

Figura 3.2: Implementacion de una funcion mediante una ULU.

3.2.1.1. Entrenamiento de una ULU

Para que la ULU responda de manera adecuada a determinados conjuntos de entre-namiento se deben ajustar o entrenar los pesos de la ULU. Para la clasificacion de vec-tores de caracterısticas las entradas de la ULU son valores numericos y, por tanto, si elprocesamiento perceptual produce caracterısticas categorizadas, estas se deben codificarnumericamente. Por supuesto, un sistema de clasificacion que emplee una sola ULU solopodra clasificar las entradas en dos grupos, uno por cada salida posible de la ULU. Unared neuronal compuesta de una unica ULU tambien recibe el nombre de perceptron oadaline (del ingles adaptive linear element [16], [20]). El entrenamiento de una ULU serealizara ajustando los pesos variables hasta que se consigan las salidas deseadas.

Una forma de abordar el problema del entrenamiento de una ULU para que esta res-ponda apropiadamente a los vectores del conjunto de entrenamiento consiste en definir


una funcion de error que debe minimizarse ajustando el valor de los pesos. Una de lasfunciones de error mas usadas es la funcion de error cuadratico ε:

ε =∑

Xi∈Ξ

(di − fi)2, (3.1)

donde fi es la respuesta de la ULU al vector de entrada Xi, di es la respuesta deseaday el sumatorio se extiende a todos los vectores del conjunto de entrenamiento. Se puedeencontrar el mınimo de ε aplicando el metodo del gradiente conjugado. Para poder aplicareste metodo primero es necesario calcular el gradiente de varepsilon en el espacio de lospesos y luego desplazar el vector de pesos en el sentido negativo del gradiente (es decir,pendiente abajo). Uno de los problemas que se encuentran al calcular el gradiente de ε esque el error depende de todos los vectores del conjunto de entrenamiento Ξ. Para solventareste problema, es preferible aplicar un unico vector a la ULU realizar los ajustes necesariosy repetir el proceso con el siguiente vector del conjunto de entrenamiento. Este metodosecuencial se aproxima de forma bastante efectiva a los metodos equivalentes de procesopor lotes.

Para un unico vector de entrada X, el error cuadratico que se comete al obtener comosalida el valor f se define como ε = (d − f)2 siendo d el valor deseado a la salida. Elgradiente de ε respecto a los pesos es:

∂ε

∂W=

[∂ε

∂W0, . . . ,

∂ε

∂Wi, . . . ,

∂ε

∂Wn

](3.2)

Como ε depende de W a traves del producto escalar s = X ·W , aplicando la regla dela derivacion en cadena se tiene:

∂ε

∂W=

∂ε

∂s

∂s

∂W(3.3)

Entonces, dado que ∂s/∂W = X y teniendo en cuenta que ∂ε/∂s = −2(d− f)∂f/∂s sepuede escribir:

∂ε

∂W= −2(d− f)

∂f

∂sX (3.4)

Sin embargo todavıa existe un problema para el calculo de la derivada de f con respectoa s. Dado que la salida f es una funcion umbral, no es continuamente diferenciable respectoa s. La mayor parte de las pequenas variaciones que se producen en el producto escalar noafectan a f y cuando f cambia lo hace de manera abrupta pasando de 0 a 1 o viceversa.A continuacion se presentan varias formas de solventar esta dificultad:


Procedimiento de Widrow-Hoff. Con este procedimiento se intentan ajustarlos pesos de tal forma que cada vector del conjunto de entrenamiento etiquetadocon un 1 produzca un producto escalar que sea exactamente igual a 1, mientrasque los etiquetados con un 0 tengan un producto escalar igual a -1. Se ignora lafuncion umbral y se asume f = s. El procedimiento resulta en la siguiente regla:W ← W + c(d− f)X ([21]). Siempre que la diferencia (d− f) sea positiva se anadeal vector de pesos una fraccion del vector de entrada; en caso contrario se resta.

Procedimiento delta generalizado. Este procedimiento ([19] y [17]) consiste ensustituir la funcion umbral por una funcion derivable llamada sigmoide (denominadaası por tener forma de s, ver Fig.3.3). La sigmoide mas empleada es la funcion

f(s) =1

1 + e−s, (3.5)

con la que resulta:∂ε

∂W= −2(d− f)f(1− f)X, (3.6)

de la que se puede deducir la regla que determina la forma en que cambian los pesos.

W ← W + c(d− f)f(1− f)X (3.7)

Procedimiento de correccion del error. En este metodo se emplea la mismaregla de ajuste de los pesos que en el metodo de Widrow-Hoff con la diferencia deque ahora, para la correccion del error, tanto d como f solo admiten los valores 0o 1.

Se puede demostrar que, si existe un vector de pesos W para el que todos los vectoresdel conjunto Ξ producen una salida correcta, entonces el procedimiento de correccion delerror encontrara dicho vector despues de presentar un numero finito de vectores a la ULUy, ademas, una vez encontrado dicho valor, este no volvera a ser modificado. Para conjuntosde vectores de entrada que no sean linealmente separables, el procedimiento de correcciondel error, ademas de no finalizar, no podra ser utilizado para encontrar el mejor vector depesos de acuerdo con algun criterio definido sobre el error. Sin embargo los metodos deWidrow-Hoff y delta generalizado siempre encontraran una solucion que minimize el errorcuadratico, aunque dicho error mınimo no sea nulo.


Figura 3.3: Representacion de la funcion sigmoide.

3.2.2. Redes Neuronales, Motivacion

Algunas veces se encuentran conjuntos de estımulos y respuestas que no se puedenaprender con una sola ULU (es decir, conjuntos de entrenamiento que no son linealmenteseparables). En estos casos, para conseguir una respuesta correcta, es necesario construiruna red de ULUs. La funcion que se calcula mediante este tipo de redes depende tantode la topologıa de la misma como del peso que tiene cada una de las ULUs. Las redes dealimentacion directa o simplemente redes directas, no poseen ciclos, es decir, las entradasde una ULU no dependen (ni directa ni indirectamente) de la salida de dicha ULU (lasque no son directas se denominan redes recurrentes).

Una red directa por capas es una red directa cuyas ULUs se disponen por capas enlas que las entradas de los elementos de la capa j solo dependen de las salidas de loselementos de la capa j−1. La red de la Figura 3.4, que calcula la funcion f = x1x2 +x1x2

(denominada funcion de paridad par), es una red directa por capas con dos capas. Algunosautores consideran la entrada como una capa adicional y, por consiguiente, dirıan que lared del ejemplo tiene tres capas.

En las secciones siguientes se describira un procedimiento general para entrenar una red


Figura 3.4: Red de ULU que calcula la funcion de paridad par.

directa multicapa. El procedimiento que se va a analizar se denomina retropropagacion y sebasa en el procedimiento del gradiente descendente. Debido a que se necesitara calcular lasderivadas parciales de la funcion de error respecto a los vectores de pesos, se reemplazarantodas las funciones umbral por funciones sigmoide (una vez concluido el entrenamiento,se pueden volver a sustituir por las funciones umbral).

3.2.2.1. Notacion

En la figura Fig.3.5 se puede apreciar una red directa generica de k capas compuestapor unidades sigmoidales. Todas las unidades sigmoidales, exceptuando las de la ultimacapa, se denominan unidades ocultas, ya que sus salidas solo contribuyen indirectamentea la salida final. Como se puede apreciar en la figura, esta red tiene solo una unidad desalida; sin embargo en otras ocasiones se podra emplear mas de una unidad de salida.En este caso, una vez se haya obtenido la salida es necesario realizar un paso adicionalconsistente en un esquema de decodificacion para transformar los vectores de salida en suscorrespondientes categorıas. Para este fin Brain ([3]) uso codigos basados en las secuenciasde registros de desplazamientos maximales, mientras que Dietterich y Bakiri (en [5] y [6])se basaron en los codigos correctores del error.

Se utilizara la Figura 3.5 para introducir la notacion que se va a utilizar en los parrafossiguientes. Se considerara que las salidas de cada capa de unidades sigmoidales son compo-nentes de un vector, de la misma forma que las caracterısticas se consideraran componentesdel vector de entrada. Cada capa j de unidades sigmoidales (1 ≤ j ≤ k) tendra como salidael vector X(j) que a su vez sera el vector de entrada de la capa j + 1. Siguiendo con estanotacion el vector de entrada sera X(0) y la salida de la red (es decir, la salida de la capa k)sera f . De la misma forma W

(j)i sera el vector de pesos de la unidad sigmoidal i de la capa

j. Al igual que en secciones anteriores se considerara la existencia de un peso umbral comoultimo componente del vector de pesos. Por ultimo, la suma ponderada de la entrada de la


Figura 3.5: Red de unidades sigmoidales con k capas.

unidad sigmoidal i de la capa j sera s(j)i . Se utilizara el termino activacion para referirse

a la entrada de una unidad sigmoidal y se puede obtener mediante la expresion:

s(j)i = X(j−1) ·W (j)

i (3.8)

El numero de unidades sigmoidales de la capa j viene dado por mj . Por tanto, el vectorW

(j)i tendra como componentes w

(j)l,i con l = 1, . . . ,m(j−1) + 1

3.2.2.2. El Metodo de la Retropropagacion

Al igual que en el caso de la ULU se calculara el gradiente del error cuadratico ε =(d−f)2. En este caso, el vector de pesos sobre el que se calcula el gradiente tiene que estarcompuesto por todos los pesos de la red. Sin embargo, se suelen calcular las derivadasparciales de ε respecto a los vectores de pesos de cada unidad sigmoidal. De esta forma,la derivada parcial de ε respecto al vector de pesos W

(j)i es:

∂ε

∂W(j)i

≡ ∂ε

∂w(j)1,i

, . . . ,∂ε

∂w(j)l,i

, . . . ,∂ε

∂w(j)mj−1+1,i

(3.9)


Se puede utilizar la regla de derivacion de la cadena para calcular la derivada parcial,ya que la dependencia de ε sobre W

(j)i se debe a s

(j)i , con lo que se puede escribir:

∂ε

∂W(j)i

=∂ε

∂s(j)i

∂s(j)i

∂W(j)i

(3.10)

De nuevo, debido a que

s(j)i = X(j−1) ·W (j)

i ,∂s

(j)i

∂W(j)i

= X(j−1), (3.11)

sustituyendo se obtiene que:∂ε

∂W(j)i

=∂ε

∂s(j)i

X(j−1) (3.12)

Teniendo en cuenta que

∂ε

∂s(j)i

=∂(d− f)2

∂s(j)i

= −2(d− f)∂f

∂s(j)i

, (3.13)

se obtiene finalmente:∂ε

∂W(j)i

= −2(d− f)∂f

∂s(j)i

X(j−1) (3.14)

La cantidad (d − f) ∂f

∂s(j)i

= −12

∂ε

∂s(j)i

desempena un papel muy importante en estos

calculos. Para simplificar, se expresara como δ(j)i . La cantidad δ

(j)i indica la sensibilidad

del error cuadratico de la salida de la red respecto a los cambios en la entrada de lacorrespondiente funcion sigmoide. De esta forma, el gradiente de ε se puede escribir como:

∂ε

∂W(j)i

= −2δ(j)i X(j−1) (3.15)

Puesto que se deben modificar los vectores de pesos en el sentido negativo del gradiente,la regla que indica como cambian dichos pesos se puede escribir como:

W(j)i ← W

(j)i + c

(j)i δ

(j)i X(j+1), (3.16)

donde c(j)i es el factor de aprendizaje para el correspondiente vector de pesos (normalmente,

el factor de aprendizaje es el mismo para todos los vectores de pesos). Como se puede ver, laregla obtenida es bastante parecida a la que se obtuvo para entrenar la ULU independiente,


es decir, los cambios que se producen en el vector de pesos son proporcionales a fraccionesdel vector de entrada.

3.2.2.3. Calculos del Cambio de los Pesos de la Ultima Capa

En esta seccion se tratara el calculo de las δ(j)i . Usando las definiciones de la seccion

anterior se tiene que:

δ(j)i = (d− f)

∂f

∂s(j)i

(3.17)

Para calcular el cambio de los pesos en la ultima capa sigmoidal, se necesita calcularδ(k) que se puede obtener mediante la expresion:

δ(k) = (d− f)∂f

∂s(k)(3.18)

Debido a que f es una funcion sigmoide y s(k) es su entrada se tiene que

∂f

∂s(k)= f(1− f) (3.19)

Por tanto:δ(k) = (d− f)f(1− f), (3.20)

con lo que el ajuste de los pesos para el unico elemento de la ultima capa por el procedi-miento de la retropropagacion se puede escribir como:

w(k) ← W (k) + c(k)(d− f)f(1− f)X(k−1), (3.21)

que, como se puede apreciar, es la misma regla que se obtendrıa aplicando el procedimientodelta generalizado (pagina 59) si la ultima unidad sigmoidal fuese unica en la red y siX(k−1) = X.

3.2.2.4. Calculo del Cambio de los Pesos en las Capas Intermedias

Usando la expresion para el calculo de δ, se puede obtener la regla que indica como setienen que modificar los vectores de pesos de la red. Recuerdese que:

δ(j)i = (d− f)

∂f

∂s(j)i

(3.22)


Usando otra vez la regla de la derivacion de la cadena y teniendo en cuenta que la salidade la red, f , depende de s

(j)i a traves de la suma de las entradas a las unidades sigmoidales

de la capa j + 1, se tiene que:

δ(j)i = (d− f)

[∂f

∂s(j+1)1

∂s(j+1)1

∂sji

+ · · ·+ ∂f

∂s(j+1)l

∂s(j+1)l

∂sji

+ · · ·+ ∂f

∂s(j+1)mj+1

∂s(j+1)mj+1

∂sji

]

=mj−1∑

l=1

(d− f)∂f

∂s(j+1)l

∂s(j+1)l

∂s(j)i

=mj−1∑

l=1

δ(j+1)l

∂s(j+1)l

∂s(j)i

, (3.23)

y, si se tiene en cuenta que los pesos no dependen de s entonces:

∂s(j+1)l

∂s(j)i

=∂

[∑mj+1v=1 f

(j)v w

(j+1)v,l

]

∂s(j)i

=mj+1∑

v=1

w(j+1)v,l

∂f(j)v

∂s(j)i

(3.24)

Observese que ∂f(j)v

∂s(j)i

= 0, excepto cuando v = i, en cuyo caso ∂f(j)v

∂s(j)v

= f(j)v (1− f

(j)v ). Por

tanto se puede escribir:∂s

(j+1)l

∂s(j)i

= w(j+1)i,l f

(j)i (1− f

(j)i ) (3.25)

Si se introduce este resultado en la expresion para el calculo de δ(j)i , se obtiene que:

δ(j)i = f

(j)i (1− f

(j)i )

mj+1∑

l=1

δ(j+1)l w

(j+1)i,l (3.26)

Como se puede apreciar, la ecuacion es recursiva (resulta interesante resaltar que laexpresion anterior no depende de la funcion de error, que solo afecta explıcitamente alcalculo de δ(k)). Una vez que se ha calculado δ

(j+1)i para la capa j + 1, se puede utilizar

este resultado para calcular δ(j)i . La base de esta recurrencia es δ(k) que puede ser calculada

por medio de la expresion:δ(k) = (d− f)f(1− f) (3.27)

Usando la expresion que se ha obtenido para el calculo de δ, la regla generica para elcambio de los pesos se puede escribir de la forma:

W(j)i ← W

(j)i + c

(j)i δ

(j)i X(j−1) (3.28)

Aunque pueda parecer compleja, esta expresion tiene una explicacion bastante intuitiva.


Por medio de la cantidad δ(k) = (d− f)f(1− f) se controlan la magnitud y el signo de losajustes que hay que realizar en los vectores pesos (la magnitud de los ajustes disminuyea medida que f se aproxima a 1 o a 0, ya que entonces el efecto que producen sobre f

tiende a desaparecer). Como se puede deducir de la expresion recursiva para el calculo deδ, el ajuste de los pesos en una unidad sigmoidal de la capa j es proporcional a los efectosque tiene dicho ajuste sobre la salida de dicha unidad sigmoidal (el factor f (j)(1− f (j))).Estos ajustes tambien son proporcionales al promedio del efecto que, sobre la salida finalde la red, provocan los cambios en la unidad sigmoidal. Este promediado depende de lospesos que son aplicados a la unidad sigmoidal de la capa j (si los pesos son pequenos, estasalida contribuira poco en las siguientes etapas de la red) y a los efectos que los cambiosen las salidas de la etapa (j + 1) tienen sobre la salida final (y que se obtiene por mediode las δ

(j+1)i ). Estos calculos pueden ser facilmente implementados ya que solo harıa falta

propagar los valores δ por todos los pesos en sentido inverso a los calculos realizados en lared (de ahı el nombre de retropropagacion).

Como ejemplo del proceso de retropropagacion, se mostrara como se realizarıa un pasode este tipo de entrenamiento en la red de la Figura 3.6 (los pesos iniciales mostrados enla figura son aleatorios). Se usara la notacion introducida en las secciones anteriores parafacilitar el seguimiento del ejemplo. La funcion objetivo es la funcion paridad par aplicadaa dos variables binarias. Las entradas a esta red (incluyendo la componente umbral) y lasetiquetas que les corresponden son:

1. x(0)1 = 1, x

(0)2 = 0, x

(0)3 = 1, d = 0

2. x(0)1 = 0, x

(0)2 = 0, x

(0)3 = 1, d = 1

3. x(0)1 = 0, x

(0)2 = 1, x

(0)3 = 1, d = 0

4. x(0)1 = 1, x

(0)2 = 1, x

(0)3 = 1, d = 0

El primer vector de entrada es (1, 0, 1), que produce las salidas f(1)1 = 0, 881 y f

(1)2 = 0, 5

en la primera capa y la salida f = 0, 665 como salida final. Si se usa la ecuacion que sededujo para el caso base, se obtiene δ(2) = −0, 148. Propagando hacia atras a traves delos pesos de la segunda capa, se obtiene δ

(1)1 = −0, 047 y δ

(1)2 = 0, 074. Si ahora se utiliza

la regla para ajustar los pesos (con un factor de aprendizaje c = 1), los nuevos pesos que


se obtienen son:

W(1)1 = (1, 953, −2, 000, −0, 047)

W(1)2 = (1, 074, 3, 000, −0, 926)

W (2) = (2, 870, −2, 074, −1, 148) (3.29)

Figura 3.6: Red sobre la que se aplica la retropropagacion en el ejemplo.

Hay que tener en cuenta que no se produce ningun ajuste en W(1)2,2 y W

(1)1,2 ya que x

(0)2 = 0

(aunque f(1)2 = 0, 500, valor que representa la maxima sensibilidad para que se produzca

el ajuste). Los ajustes realizados en los pesos de la segunda capa, hacen decrecer f y elerror que se comete con el correspondiente vector de entrada.

3.2.2.5. Generalizacion, Precision y Sobreajuste

El ejemplo de entrenamiento de redes neuronales que se acaba de presentar es bastanteatıpico ya que, debido a la baja dimensionalidad de los vectores, se puede efectuar elentrenamiento con todos los vectores de entrada (que son solo cuatro). Como se puedever en la Figura 3.4, existe un conjunto de pesos que clasifica de forma correcta todoslos posibles vectores. Sin embargo, en la mayorıa de las aplicaciones la dimension de losvectores de entrada es mucho mayor, estando normalmente alrededor de 100 o incluso mas.Si se tiene en cuenta que con 100 componentes binarias existen 2100 vectores de entradaposibles, es obvio que solo se puede utilizar una pequena porcion de todos estos vectorespara realizar el entrenamiento. Ademas, incluso si la red llega a clasificar correctamentetodos los vectores de entrada introducidos (cosa poco probable), no se podrıa garantizar


que clasifique de forma correcta los posibles vectores de entrada que no esten en el conjuntode entrenamiento. En este sentido, se dira que una red ha generalizado cuando clasifiquede forma correcta vectores que no estaban en el conjunto de entrenamiento. La capacidadde generalizacion se puede medir por la precision con la que realiza dichas clasificaciones.En los siguientes parrafos se explicara como estimar la precision de la clasificacion.

Respecto a esto, se podrıa cuestionar cual es la base para considerar que una red neuro-nal generaliza. Esta situacion es muy parecida a la que se produce en el ajuste funcional.Cuando se intenta ajustar una recta o un polinomio de grado pequeno a un determinadoconjunto de datos, se puede tener la seguridad de que se ha detectado alguna relacionoculta en dichos datos, si el ajuste es lo suficientemente bueno y el conjunto de datos eslo suficientemente grande. De esta forma, la funcion obtenida se puede se puede utilizarpara estimar (con una fiabilidad razonable) valores correspondientes a datos que no sehan utilizado en el proceso de ajuste. Si el ajuste por una recta no es lo suficientementebueno, se puede probar con un polinomio de segundo grado y seguir aumentando el gradodel polinomio hasta que se obtengan los resultados esperados. Terminos similares puedenusarse en las redes neuronales.

Una red neuronal implementa una funcion no lineal de los vectores de entrada. Si se tieneen cuenta que el proceso de clasificacion es una funcion, proxima a alguna de las posiblesfunciones que la red puede implementar, y se supone que el ajuste a realizado sobre losdatos del conjunto de entrenamiento es lo suficientemente bueno (para un numero bastantegrande de vectores de entrada), entonces se puede afirmar que es muy probable que se hayaencontrado una relacion, en principio oculta, entre las entradas y la clasificacion de lasmismas. En este supuesto, la generalizacion para los vectores de entrada que no formanparte del conjunto de entrenamiento deberıa ser optima.

A la hora de realizar el entrenamiento de la red es importante que el numero de vectoresde entrenamiento sea mayor que el numero de grados de libertad de la misma (es decir, delnumero de pesos que tienen que ser entrenados). El sımil del ajuste funcional ayudara acomprender esta afirmacion.

Para un conjunto con m puntos, se sabe con toda seguridad que existe un polinomiode grado m − 1 que se ajusta perfectamente a esos puntos, es decir, que pasa por todosellos. Pero, aunque siempre se puede realizar este tipo de ajuste, independientemente de ladisposicion de los puntos, no servira para establecer algun tipo de relacion en el conjuntode puntos utilizados. En estos casos se dira que se han sobreajustado dichos datos. Si,ademas, los datos se ven afectados por algun tipo de ruido (casos en los que el ajuste auna recta puede ser suficiente), el polinomio de grado m− 1 se habrıa ajustado de manera


exacta a los datos con ruido. Para evitar este tipo de problema, a la hora de realizar unajuste, el numero de puntos a utilizar tiene que ser sensiblemente mayor que el grado delpolinomio que se va a utilizar. Y, dado un conjunto lo suficientemente grande, de entretodos los posibles ajustes el de grado menor sera la mejor opcion.

Supongase una red directa de dos capas con n entradas, h unidades ocultas y con unaunica salida. Esta red tendra aproximadamente (sin contar los pesos umbrales) nh + h =(n+1)h pesos variables. Dada la dimension de la entrada, el numero de grados de libertadqueda determinado por el numero de unidades ocultas. Se podrıa esperar que el error declasificacion cometido sobre el conjunto de entrenamiento disminuyera a medida que seaumentase el numero de unidades ocultas. Sin embargo, y teniendo en cuenta lo que se hadicho en el parrafo anterior, para evitar el sobreajuste de la red, el aumento del numerode unidades ocultas no debe provocar que el factor (n + 1)h se aproxime al numero devectores que contiene el conjunto de entrenamiento.

Tambien se puede dar el caso de que, a pesar de que se obtenga un porcentaje pequenode error para el conjunto de entrenamiento, la generalizacion no sea buena.

Existen varios metodos para estimar cual va a ser el porcentaje de error para las entradasque no estan en el conjunto de entrenamiento, seleccionadas estas siguiendo la mismadistribucion con la que se formo el conjunto de entrenamiento. En estadısticas, este errorse denomina error fuera de muestra. La tecnica mas simple para evaluar este error consisteen dividir el conjunto de entrenamiento en dos conjuntos disjuntos. Uno de estos conjuntoslo se utilizara como conjunto de entrenamiento y el otro, que se denominara conjunto devalidacion, sera utilizado para calcular el error fuera de muestra. Para que la estimaciondel error fuera de muestra sea significativa, el numero de vectores en ambos conjuntosdebe ser grande (obviamente, hay que tener cuidado ya que se puede sobrestimar dichoerror). Los disenadores experimentados colocan dos tercios de los vectores disponibles enel conjunto de entrenamiento y el resto en el conjunto de validacion.

Otro metodo bastante utilizado el estimacion de la precision de la generalizacion esel denominado metodo de validacion cruzada. En este caso, los vectores disponibles parael proceso de entrenamiento se dividen en k conjuntos disjuntos (normalmente 10). Seselecciona uno de estos conjuntos como conjunto de validacion, y los k − 1 restantes secombinan para formar el conjunto entrenamiento. Este proceso se repite hasta que todoslos conjuntos se han seleccionado como conjunto de validacion. Para cada conjunto devalidacion se calcula el error correspondiente (despues de realizar el entrenamiento conel resto de conjuntos), siendo la media de estos errores la estimacion del error fuera demuestra. En el caso especial de que k = m, siendo m el numero de vectores etiquetados


disponibles, el metodo recibe el nombre de validacion cruzada por descarte de elementos.Los resultados experimentales han demostrado que con 10 conjuntos se consiguen buenasestimaciones del error (aunque un poco pesimistas).

En la Figura 3.7 se puede ver como varıa la estimacion del error en el conjunto devalidacion en funcion del numero de unidades ocultas en un problema de clasificaciontıpico. Se fue observar como el error cometido en el conjunto de validacion empieza acrecer con el aumento del numero de unidades ocultas debido al sobreajuste.

Figura 3.7: Estimacion del error de generalizacion frente al numero de unidades ocultas.

3.3. Redes Bayesianas

Las redes bayesianas o probabilısticas son una representacion grafica de dependenciaspara razonamiento probabilıstico en sistemas expertos, en la cual los nodos y arcos repre-sentan:

Nodo: Variable proposicional.

Arcos: Dependencia probabilıstica.

3.3.1. Definicion

Una red probabilıstica es un grafo acıclico dirigido en el que cada nodo representa unavariable y cada arco una dependencia probabilıstica en la que se especifica la probabilidadcondicional de cada variable dados sus padres.

3.3. REDES BAYESIANAS 71

La variable a la que apunta el arco es dependiente (causa-efecto) de la que esta en elorigen de este.

Se puede interpretar una red probabilıstica de dos formas:

1. Distribucion de probabilidad: Representa la distribucion de probabilidad conjuntade las variables representadas en la red. Por ejemplo para la red de la Figura 3.8:

P (A,B, C, D, E, F, G) = P (G|D)P (F |C, D)P (E|B)P (D|A, B)P (C|A)P (B)P (A)(3.30)

2. Base de reglas: Cada arco representa un conjunto de reglas que asocian las variablesinvolucradas. Por ejemplo:

Si C, D entonces F .

Dichas reglas estan cuantificadas por las probabilidades respectivas. La topologıa oestructura de la red nos da informacion sobre las dependencias probabilısticas entre lasvariables.

La red tambien representa las independencias condicionales de una variable (o conjuntode variables) dada otra u otras variables. En el caso de la Figura 3.8, por ejemplo, E

es condicion independiente de A,C,D, F,G dado B. Esto es: P (E|A, B,C, D, F, G) =P (E|B). Esto esta representado graficamente por el nodo B separando al nodo E delresto de las variables.

En general, un conjunto de variables X es independiente de un conjunto de variables Y

dado Z si al eliminar Z se desconectan X e Y . Es decir, no existe una trayectoria entreX e Y en que las siguientes condiciones sean verdaderas:

1. Todos los nodos con flechas convergentes estan o tienen descendientes en Z.

2. Todos los demas nodos estan fuera de Z.

Esto se conoce como Separacion-D.

En una red probabilıstica todas las relaciones de independencia condicional represen-tadas en el grafo corresponden a relaciones de independencia en la distribucion de pro-babilidad. Dichas independencias simplifican la representacion del conocimiento (menosparametros) y el razonamiento (propagacion de las probabilidades).


Figura 3.8: Ejemplo de red de Bayes.

3.3.2. Propagacion de Probabilidades

El razonamiento probabilıstico o propagacion de probabilidades consiste en propagarlos efectos de la evidencia a traves de la red para conocer la probabilidad a posterioride las variables. La propagacion consiste en darle valores a ciertas variables (evidencia)y obtener la probabilidad posterior de las demas variables dadas las variables conocidas(instanciadas).

Los algoritmos de propagacion dependen de la estructura de la red:

Arboles

Poliarboles

Redes multiconexas

3.3.2.1. Propagacion en Arboles

Cada nodo corresponde a una variable discreta, A = {A0, A1, . . . , An−1}, con su res-pectiva matriz de probabilidad condicional, P (B|A) = P (Bj |Ai). Dada cierta evidenciaE (representada por la instanciacion de ciertas variables) la probabilidad posterior de


cualquier variable B por el teorema de Bayes es:

P (Bi|E) =P (Bi)P (E|Bi)

P (E)(3.31)

Ya que la estructura de la red es un arbol el Nodo B la separa en dos subarboles, porlo que se puede dividir la evidencia en dos grupos:

1. E−:Datos en el arbol cuya raız es B

2. E+:Datos en el resto del arbol

Entonces:P (Bi|E) =

P (Bi)P (E−, E+|Bi)P (E)

(3.32)

Pero dado que ambos son independientes y aplicando de nuevo el teorema de Bayes:

P (Bi|E) = αP (Bi|E+)P (E−|Bi), (3.33)

donde α es una constante de normalizacion.

Esto separa la evidencia para actualizar la probabilidad de B. Ademas se ve que no serequiere de la probabilidad a priori, excepto en el caso de la raız donde:

P (Ai|E+) = P (Ai) (3.34)

Si se definen los siguientes terminos:

λ(Bi) = P (E−|Bi) (3.35)

π(Bi) = P (Bi|E+), (3.36)

entonces:P (Bi|E) = απ(Bi)λ(Bi) (3.37)

Dado que los hijos son condicionalmente independientes dado el padre:

λ(Bi) =∏

k

P (E−k |Bi) =

∏

k

λk(Bi), (3.38)

donde E−k corresponde a la evidencia que proviene del hijo k de B, denotado por Sk.


Condicionando cada termino en la ecuacion anterior respecto a todos los posibles valoresde cada nodo hijo, se obtiene:

λ(Bi) =∏

k

∑

j

P (E−k |Bi, S

kj )P (Sk

j |Bi)

(3.39)

Dado que B es condicionalmente dependiente de la evidencia bajo cada hijo dado estey usando la definicion de λ:

λ(Bi) =∏

k

∑

j

P (Skj |Bi)λ(Sk

j )

(3.40)

En forma analoga se obtiene una ecuacion para π. Primero se condiciona sobre todoslos posibles valores del padre:

π(Bi) =∑

j

P (Bi|E+, Aj)P (Aj |E+) (3.41)

Se puede eliminar E+ del primer termino dada independencia condicional. El segundotermino representa la probabilidad posterior de A sin contar la evidencia de subarbol deB, por lo que se puede expresar usando la ecuacion para P (Bi|E) y la descomposicion deλ.

π(Bi) =∑

j

P (Bi|Aj)

[απ(Aj)

∏

k

λk(Aj)

], (3.42)

donde k incluye a todos los hijos de A excepto B.

Mediante estas ecuaciones se integra un algoritmo de propagacion de probabilidadesen arboles. Cada nodo guarda los valores de los vectores π y λ, ası como las matrices deprobabilidad P . La propagacion se hace por un mecanismo de paso de mensajes, en dondecada nodo envıa los mensajes correspondientes a sus padres e hijos:

Mensaje al padre (hacia arriba), del nodo B a su padre A:

λB(Ai) =∑

j

P (Bj |Ai)λ(Bj) (3.43)


Mensaje a los hijos (hacia abajo), del nodo B a sus hijos Sk:

πk(Bi) = απ(Bj)∏

l 6=k

λl(Bj) (3.44)

Al instanciarse ciertos nodos, estos envıan mensajes a sus padres e hijos, y se propaganhasta llegar a la raız u hojas, o hasta encontrar un nodo instanciado. Ası la propagacionse hace en un solo paso en un tiempo proporcional al diametro de la red.

Esto se puede hacer en forma iterativa, instanciando ciertas variables y propagando suefecto y luego instanciando otras y propagando la nueva informacion, combinando ambasevidencias.

3.3.2.2. Propagacion en Poliarboles

Un poliarbol es una red en la que un nodo puede tener varios padres, pero sin existirmultiples trayectorias entre nodos (red conectada de forma sencilla, SGC). El algoritmode propagacion es muy similar al de arboles. La principal diferencia es que se requiere dela probabilidad conjunta de cada nodo dados todos sus padres:

P (Bi|A0, . . . , An−1) (3.45)

En forma analoga al inciso anterior, se puede deducir una expresion de la probabilidaden un nodo cualquiera B en terminos de sus padres e hijos:

P (Bi|E) = αP (Bi|E+0 , . . . , E+

n−1)P (E−0 |Bi) · · ·P (E−

n−1|Bi) (3.46)

A partir de esta ecuacion se puede tambien obtener un mecanismo de propagacionsimilar al de arboles con el mismo orden de complejidad.

3.3.2.3. Propagacion en Redes Multiconectadas

Una red multiconectada es un grafo no conectado en forma sencilla, es decir, en el quehay multiples trayectorias entre nodos (MCG). En este tipo de redes probabilısticas losmetodos anteriores ya no se aplican, pero existen otras tecnicas alternativas:

Condicionamiento: Se instancia una variable, esta bloquea las trayectorias de pro-pagacion. Entonces asumiendo valores para un grupo seleccionado de variables de


puede descomponer la grafica en un conjunto de redes conectadas de forma sencilla(SCG). Se propagan para cada valor posible de dichas variables y luego se promedianlas probabilidades ponderadas.

Simulacion Estocastica: se asignan valores aleatorios a las variables no instancia-das, se calcula la distribucion de probabilidad y se obtienen valores de cada variabledando una muestra. Se repite el procedimiento para obtener un numero aprecia-ble de muestras y en base al numero de ocurrencias de cada valor se determina laprobabilidad de dicha variable.

Agrupamiento: El metodo de agrupamiento consiste en transformar la estructurade la red para obtener un arbol, mediante agrupacion de nodos usando la teorıa degrafos ([11]).

Para ello se parte de la grafica original y se siguen los siguientes pasos:

1. Se triangulariza el grafo agregando los arcos adicionales necesarios.

2. Se identifican todos los conjuntos de nodos totalmente conectados (cliques).

3. Se ordenan los cliques de forma que todos los nodos comunes estan en un soloclique anterior (su padre).

4. Se construye un nuevo grafo en el que cada clique es un nodo formando unarbol de cliques.

La propagacion de probabilidades se realiza en este arbol de macronodos, obtenien-do la probabilidad conjunta de cada clique. A partir de esta se puede obtener laprobabilidad individual de cada variable en el clique.

En general, la propagacion en una red probabilıstica con una estructura compleja es unproblema de complejidad NP-duro ([4]). Sin embargo, en muchas aplicaciones practicas laestructura de la red no es tan compleja y los tiempos de propagacion son razonables.

3.4. Modelo Oculto de Markov

Considerese un sistema que puede ser descrito en cualquier instante tiempo por estaren uno de los N estados distintos de un conjunto (como el de la Figura 3.9). A intervalosregulares se produce un cambio de estado en el sistema (con la posibilidad de permanecer enel mismo) de acuerdo a un conjunto de probabilidades de transicion asociado cada estado.Se designan los instantes de tiempo asociados al cambio de estado como t = 0, 1, . . . y

3.4. MODELO OCULTO DE MARKOV 77

el estado en el instante actual t como it. Una descripcion probabilıstica completa de estesistema requerirıa la especificacion del estado actual ası como de los estados anteriores.Para el caso especial de una cadena de Markov de primer orden esta descripcion no llegamas que hasta el estado actual y el estado precedente, es decir P (it = Sj |it−1 = Si, qt−2 =Sk, . . .) = P (it = Sj |it−1 = Si). Se consideraran unicamente aquellos procesos en los queel segundo termino sea independientemente. Se consideraran entonces las probabilidadesde transicion entre estados aij = P (it = Sj |it−1 = Si).

Figura 3.9: Modelo Oculto de Markov con cinco estados y las transiciones entre algunosde ellos.

El proceso estocastico anterior podrıa llamarse modelo de Markov observable dado quela salida del proceso es el conjunto de estados en cada instante de tiempo, donde cadaestado corresponde a un evento fısico observable.

3.4.1. Ejemplos Ilustrativos

Modelo Meteorologico

Para fijar ideas, considerese un modelo de Markov simple de tres estados para estudiarel tiempo meteorologico. Se asume que una vez al dıa (por ejemplo al mediodıa), el tiempose observa en uno de los siguientes estados:

1. lluvia o nieve

2. nublado

3. soleado

Se postula el tiempo en un dıa esta caracterizado por uno solo de los tres estados anteriores


y la matriz A de probabilidad de transicion entre estados es:

A = {aij} =

0,4 0,3 0,30,2 0,6 0,20,1 0,1 0,8

(3.47)

Suponiendo que el primer dıa (t = 0) en el cielo esta soleado (estado 3), se puede hacerla siguiente pregunta: ¿cual es la probabilidad (de acuerdo al modelo) de que el tiempolos proximos siete dıas sea ”sol-sol-lluvia-lluvia-sol-lluvia-sol”? De una manera mas formalse define secuencia de observacion O como O = {S2, S2, S2, S0, S0, S3, S2, S3} y se pide laprobabilidad de O para el modelo dado esta probabilidad se puede expresar y puede serevaluada como:

P (O|Modelo) = P [S2, S2, S2, S0, S0, S2, S1, S2|Modelo]

= P [S2] · P [S2|S2] · P [S2|S2] · P [S0|S2]

·P [S0|S0] · P [S2|S0] · P [S1|S2] · P [S2|S1]

= π2 · a22 · a22 · a20 · a00 · a02 · a21 · a12

= 1 · (0,8)(0,8)(0,1)(0,4)(0,3)(0,1)(0,2)

= 1,536 · 10−4 (3.48)

donde se emplea la notacion πi = P (i0 = Si) para la probabilidad del estado inicial.

Otra cuestion interesante sobre el modelo es: supuesto modelo en un estado conocido,¿cual es la probabilidad de que permanezca en ese estado exactamente d dıas? Esta proba-bilidad se puede evaluar como la probabilidad de la secuencia observacion O = {O0 = Si,

O1 = Si, O2 = Si, . . . , Od−1 = Si, Od = Sj} dado el modelo que es:

P (O|modelo, q0 = Si) = (aii)d−1(1− aii) = pi(d) (3.49)

La cantidad pi(d) es la funcion de densidad de probabilidad discreta de duracion d delestado i. Asimismo se puede calcular el numero esperado de observaciones en un estadocomo:

di =∞∑

d=0

dpi(d) =∞∑

d=0

d(aii)d−1(1− aii) =1

1− aii(3.50)

Ası el numero esperado de dıas soleados consecutivos de acuerdo a este modelo es 1/(0,2) =5; para la niebla es 2.5; y para la lluvia es 1.67.


Hasta ahora se han considerado modelos de Markov en los que cada estado correspondea un evento fısico observable. Este modelo es demasiado restrictivo para ser aplicadoa muchos problemas de interes. Aquı se extendera el concepto de modelos de Markovpara incluir el caso en el que la observacion es una funcion probabilıstica dependientedel estado. Es decir, el modelo resultante (llamado modelo oculto de Markov, en inglesHidden Markov Model, HMM) incluye dos modelos estocasticos; uno subyacente que no esobservable (esta oculto) y otro que produce la secuencia observacion a partir de la cual seestudia el sistema. Para fijar ideas considerese el siguiente modelo sobre un experimentosimple de lanzamiento de monedas.

Experimento de Lanzamiento de Monedas

Un sujeto (A) se encuentra a un lado de una cortina opaca. Al otro lado, otro sujeto (B)realiza un experimento de lanzamiento de monedas. El sujeto B no le cuenta a A lo queesta haciendo exactamente; solo le va diciendo el resultado de cada lanzamiento. Ası serealiza un experimento de lanzamiento de monedas oculto, con la secuencia de observacionconsistente en una secuencia de resultados de cara o cruz. Por ejemplo una secuencia deobservacion tıpica podrıa resultar:

O = {O0, O1, . . . , On} = {OXXOXOOXXXOXOXO · · ·X} (3.51)

donde O son caras y X cruces.

Dado el entorno anterior el problema que se plantea es como se puede construir unmodelo de Markov que explique la secuencia observada. En primer lugar hay que decidira que corresponde cada estado en el problema y entonces decidir cuantos estados debehaber en el modelo. Una eleccion puede ser asumir que se ha lanzado una sola monedano equilibrada (con distinta probabilidad de obtener cara o cruz). Bajo este supuesto sepuede aplicar un modelo de dos estados, uno por cada cara de la moneda. Este modeloesta ilustrado en la Figura 3.10. En este caso el modelo de Markov es observable y lounico que hay que hacer para completar el modelo es decidir el valor mas adecuado dela probabilidad de obtener cara o cruz. Un modelo equivalente al anterior podrıa serun modelo degenerado de un solo estado correspondiente a la moneda y con parametrodesconocido la probabilidad de obtener cara o cruz.

Otra forma de modelo oculto de Markov para explicar la secuencia observada de resul-tados de lanzamiento de monedas es el mostrado en la Figura 3.11. En este caso hay dosestados en el modelo y cada uno corresponde a una moneda distinta con distinto desequili-brio. Cada estado se caracteriza por una distribucion de probabilidad de caras o cruces, y


Figura 3.10: Modelo de Markov con 2 estados, uno por cada lado de la moneda.

la transicion entre estados (cambio de moneda) se caracteriza por una matriz de transicionde estados. El medio por el que se decide que moneda se emplea puede ser tambien unconjunto independiente de lanzamiento de monedas o cualquier otro evento probabilıstico.

Figura 3.11: Modelo de Markov con 2 estados, uno por cada moneda.

Otra posible forma de explicar la secuencia observada se da en la Figura 3.12 y corres-ponde a la suposicion de que se emplean tres monedas distintas.

Figura 3.12: Modelo de Markov con 3 estados, uno por cada moneda.

Una vez planteados los tres modelos anteriores la siguiente cuestion a plantearse es cualde ellos se ajusta mejor al experimento observado. El modelo de la Figura 3.10 tiene ununico parametro desconocido el de la Figura 3.11 tiene 4 y el de la Figura 3.12 tiene 9. Altener un mayor numero de grados de libertad el modelo mayor parece ser mas capaz demodelar este experimento y de incluir incluso experimentos menores. Aunque esto es ciertoen teorıa se vera mas delante que por cuestiones practicas se imponen fuertes limitacionesa los tamanos de los modelos. Ademas, podrıa darse el caso de que se estuviese lanzando


una unica moneda y entonces serıa inapropiado el uso del modelo de tres monedas.

El Modelo de Urnas y Bolas

Para extender las ideas obtenidas sobre el uso de los modelos ocultos de Markov a unasituacion mas complicada considerese el sistema de urnas y bolas de la Figura 3.13. Seasume que hay N urnas en una habitacion. Cada una de estas urnas contiene un grannumero de bolas de M colores diferentes. El proceso de obtencion de la secuencia deobservacion es el siguiente: Por algun proceso aleatorio se escoge una urna inicial. De estaurna se extrae una bola al azar y su color se registra como una observacion. La bola esdevuelta a su urna y se selecciona una nueva urna de acuerdo al proceso aleatorio deseleccion asociado a la urna actual. Se procede entonces de forma analoga con la nuevaurna. Ası se obtiene una secuencia de observacion finita dada por los colores de las bolasextraıdas. Esta secuencia se podrıa modelar como la salida observable de un modelo ocultode Markov.

Figura 3.13: Modelo de urnas y bolas de N estados que ilustra el caso general de losModelos Ocultos de Markov.

Puede resultar obvio que el modelo mas simple que se corresponde con este proceso esuno con un estado por cada urna, con una probabilidad de color definida para cada urnay con la eleccion de urna definida por la matriz de transicion entre estados del modelo.

3.4.2. Notacion

Se define la siguiente notacion para el modelo:

N es el numero de estados en el modelo.

M es el numero total de elementos del vocabulario de observacion.

T es la longitud de la secuencia de observacion.

it se refiere al estado en que se encuentra el sistema en el instante t de la secuenciade observacion.


V = {v0, ..., vM−1} es el conjunto discreto de posibles sımbolos de observacion.

π = {πi}, πi = P (i0 = i), es la probabilidad de que la evolucion del modelo comienceen el estado i.

A = {aij}, donde aij = P (it+1 = j|it = i) es la probabilidad de que se produzcauna transicion desde el estado i al estado j al pasar del instante de tiempo t al t + 1siendo t cualquiera. Es decir, se asume que aij no depende del tiempo.

B = {bj(k)}, bj(k) = P (Ot = vk|it = j) es la probabilidad de que se observe elsımbolo vk estando en el estado j.

Ot se refiere al sımbolo de observacion producido en el instante t.

λ = (A,B, π) es una notacion compacta para referirse modelo oculto de Markov apartir de sus parametros caracterısticos.

A partir del modelo, entonces, una secuencia de observacion O = O0, O1, ..., OT−1 segenera de la siguiente manera: Se comienza el experimento eligiendo uno de los estadoscomo estado inicial i0 (de acuerdo con la distribucion de probabilidades iniciales π). Esteestado emite un sımbolo, O0, segun la distribucion de probabilidades de emision B y elsistema pasa al instante 1 y segun la distribucion de probabilidades de transicion A pasaal estado i1. A partir de aquı se continua la secuencia hasta que t = T − 1, instante en elque se emite el ultimo sımbolo de la secuencia.

3.4.3. Los Tres Problemas Principales de los Modelos Ocultos de Mar-

kov

La mayorıa de las aplicaciones de los modelos de Markov se reducen a la solucion dealguno de los tres problemas siguientes:

1. Dado el modelo λ = (A,B, π) calcular P (O|λ), es decir, la probabilidad de la ocurren-cia de la secuencia de observacion O = O0, O1, ..., OT−1.

2. Dado el modelo λ = (A,B, π) obtener la secuencias de estados I = {i0, i2, ..., iT−1}tal que P (O, I|λ), la probabilidad de la secuencia de observacion O = O0, O1, ...,

OT−1 en dicha secuencia de estados sea maxima.

3. Dada una secuencia de observacion O = O0, O1, ..., OT−1 ajustar los parametros delmodelo HMM, λ = (A, B, π), de modo que se maximice P (O|λ) (o P (O, I|λ)).


El primer y el segundo problema lo son de analisis mientras que el tercero es un tıpicoproblema de sıntesis (o de identificacion o entrenamiento del modelo).

3.4.4. Solucion al Primer Problema: Procedimiento de Avance-retroceso

La forma conceptualmente mas sencilla de determinar P (O|λ) es encontrar P (O|I, λ)para una secuencia de estados fija I = {i0, i2, ..., iT−1}, entonces se multiplica por P (I|λ)y se suma para todas las posibles secuencias de estado. Se tiene:

P (O|I, λ) = bi0(O0)bi1(O1) · · · biT−1(OT−1) (3.52)

P (I|λ) = πi0ai0i1ai1i2 · · · aiT−2iT−1 (3.53)

Por lo tanto:

P (O|λ) =∑

I

P (O|I, λ)P (I|λ) = (3.54)

=∑

I

πi0bi0(O0)ai0i1bi1(O1) · · · aiT−2iT−1biT−1(OT−1) (3.55)

En la ecuacion Eq.3.55 se puede observar cada sumando incluye 2T−1 multiplicaciones yexisten NT posibles secuencias de estados de longitud T . Un calculo directo de la expresionen Eq.3.55 implica del orden de 2TNT multiplicaciones. Incluso para valores relativamentepequenos como N = 5 y T = 100, esto significa aproximadamente 1072 multiplicaciones.Por supuesto se requiere un procedimiento mas eficiente para el calculo de P (O|λ), seemplea el procedimiento de avance-retroceso.

Se considera la variable da avance αt(i) ([7]) definida como:

αt(i) = P (O0, O1, ..., Ot, it = i|λ), (3.56)

es decir, la probabilidad de la secuencia de observacion parcial hasta el instante t siendoi el estado en dicho instante dado el modelo λ. αt(i) se puede calcular de forma inductivacomo sigue:

1.α0(i) = πibi(O0), 0 ≤ i ≤ N − 1 (3.57)


2. para t = 0, 2, ..., T − 2 y 0 ≤ j ≤ N − 1

αt+1(j) =

[N−1∑

i=0

αt(i)aij

]bj(Ot+1) (3.58)

3. entonces:

P (O|λ) =N−1∑

i=0

αT−1(i) (3.59)

En el segundo paso se calcula la probabilidad de la secuencia de observacion parcialhasta el instante t + 1 y estando en el estado j en dicho instante. El estado j puede seralcanzado (con probabilidad aij) independientemente desde alguno de los N estados en elinstante t. El sumatorio en la ecuacion Eq.3.58 se refiere a este hecho. Ademas los sumandosproporcionan la secuencia de observacion hasta el instante t, de ahı la multiplicacion porbj(Ot+1) no incluida en los corchetes. En el ultimo paso se suman todos los modos posiblese independientes de obtener la secuencia de observacion dada. Se aprecia claramente en elcaso de:

α1(j) = P (O0, O1, i1 = j|λ), (3.60)

la secuencia O0, O1 con i1 = j se concluye con la emision del sımbolo O1 desde el estado i1.Pero la emision de O0 puede haber sido, en principio, desde cualquiera de los N estados delos que se compone el sistema. Se sabe que si {Si} es un conjunto de eventos excluyentesy exhaustivos para cualquier evento E se tiene:

P (E) =∑

i

P (E|Si)P (Si) (3.61)

Ası pues, usando la ecuacion Eq.3.57, se puede escribir

α1(j) = P (O0, O1, i1 = j)

=∑

i

P (O1, i1 = j)|O0 emitido por i)P (O0 emitido por i)

=∑

i

([P (O1|i1 = j, O0 emitido por i)P (i1 = j|O0 emitido por i)]

[P (O0|i0 = i)P (i0 = i)])


=∑

i

([P (O1|i1 = j)p(i1 = j|i0 = i)] [p(O0|i0 = i)p(i0 = i)])

=∑

i

([bj(O1)aij ] [bi(O0)πi])

=

[∑

i

(πibi(O0))aij

]bj(O1)

=

[∑

i

α0(i)aij

]bj(O1) (3.62)

que resulta en la ecuacion Eq.3.58 vista antes. Ası, este simple ejemplo muestra la justifi-cacion matematica de Eq.3.58

Para la ecuacion Eq.3.59 usando Eq.3.61 se puede escribir:

P (O) =∑

i

P (O|iT = i)P (iT = i) =∑

i

P (O, iT = i) =∑

i

αT (i) (3.63)

usando la definicion dada en Eq.3.56. Y ası queda probado.

Ahora se puede ver el numero de operaciones que implica este algoritmo. En el paso1 se dan N multiplicaciones. En el paso 2 el sumatorio contiene N multiplicaciones masuna que no se incluye en los corchetes. Estas se tienen que realizar desde j = 0 a N − 1y para t = 0 a T − 2. Lo que hace el numero total de multiplicaciones en el paso 2 de(N − 1)N(T − 1). En total supone N + N(N + 1)(T − 1), es decir, del orden de N2T encomparacion a 2T ·NT que requerıa el metodo de fuerza bruta. Para el ejemplo expuestoanteriormente con N = 5 y T = 100 resultan en aproximadamente 3000 operaciones frentea las 1072 del caso anterior.

De un modo similar se puede definir la variable de retroceso ([7]) βt(i) como:

βt(i) = P (Ot+1, Ot+2, ..., OT−1|it = i, λ), (3.64)

es decir, la probabilidad de observacion de la secuencia desde t + 1 a T − 1 dado el estadoi en el instante t y el modelo λ. Notese que el estado it = i se da a priori, al contrarioque en la variable de avance. Esta diferencia se hace para poder combinar las variablesde avance y retroceso para obtener resultados utiles. Tal y como se hizo con αt(i) βt(i) sepuede resolver facilmente:

1.βT−1(i) = 1, 0 ≤ i ≤ N − 1 (3.65)


2. para t = T − 2, T − 3, ..., 0 y 0 ≤ i ≤ N − 1

βt(i) =N−1∑

i=0

aijbj(Ot+1)βt+1(j) (3.66)

3.

P (O|λ) =N−1∑

i=0

N−1∑

i=0

πibi(O0)β0(i) (3.67)

La demostracion de la Eq.3.66 y la Eq.3.67 es similar a la de la Eq.3.58 y Eq.3.59. Elcalculo de P (O|λ) usando la variable de retroceso βt(i) requiere tambien el empleo delorden de N2T operaciones y resulta tan eficiente como el uso de la variable de avanceαt(i).

De este modo queda resuelto el primer problema.

3.4.5. Solucion al Segundo Problema: Algoritmo de Viterbi

Se debe encontrar una secuencia de estados I = i0, i1, ..., iT−1 tal que la probabilidad deocurrencia de la secuencia de observacion O = O0, O1, ..., OT−1 a partir de esta secuenciade estados sea mayor que desde cualquier otra. En otras palabras, el problema consiste enencontrar I que maximice P (O, I|λ). Para este fin existe un conocido algoritmo llamadoAlgoritmo de Viterbi ([9] y [7]) que es un procedimiento inductivo en el que en cada instantese mantiene la mejor secuencia de estados posible (es decir, la de mayor probabilidad deocurrencia de la secuencia de observacion) para cada uno de los N estados como estadointermedio de la secuencia de observacion deseada. De este modo se obtiene el mejorcamino para cada uno de los N estados como ultimo estado de la secuencia. De ellos seescoge el de mayor probabilidad.

Para ver la aplicacion del algoritmo de Viterbi en la estimacion de la secuencia deestados optima sera util una simple reformulacion del problema.

Considerando la expresion para P (O, I|λ) de Eq.3.52 y Eq.3.53 se tiene:

P (O, I|λ) = P (O|I, λ)P (I|λ) = πi0bi0(O0)ai0i1bi2(O2) · · · aiT−2iT−1biT−1(OT−1) (3.68)

Ahora se define:

U(i0, i1, ..., iT−1) = −[ln (πi0bi0(O0)) +

T−1∑

t=1

ln(ait−1bit(Ot)

)]

, (3.69)


entonces se observa facilmente que:

P (O, I|λ) = exp (−U(i0, i1, ..., iT−1)) , (3.70)

en consecuencia el problema de estimacion de la forma

max{it}T−1

t=0

P (O, i0 · · · iT−1|λ), (3.71)

resulta equivalente a:mın{it}T−1

t=0

U(i0, i1, ..., iT−1) (3.72)

Esta sustitucion permite asociar los terminos como − ln(aijikbik(Ot)) al coste asociado apasar del estado ij al estado ik en el instante t.

El algoritmo de Viterbi para encontrar la secuencia final de estados se puede describirde la siguiente manera: Supongase el sistema en el estado i y considerese una transicional estado j en el siguiente paso. Se podrıa decir que el coste en el camino del estado i

al j es − ln(aijikbik(Ot)) (es decir, el negativo del logaritmo de la probabilidad de pasardel estado i al j y la seleccion del sımbolo observacion Ot en el estado j) donde Ot esel sımbolo observacion seleccionado despues de visitar el estado j; el mismo sımbolo queaparece en la secuencia de observacion dada O = O0, O1, ..., OT−1. Cuando el estado i

el seleccionado como estan iniciando el coste correspondiente es − ln(πibi(O0)), que puedeser llamado es inicial. Se define el coste de una secuencia de estados como la suma delos costes de estados adyacentes. Notese que esto equivale a multiplicar las probabilidadescorrespondientes. Ahora buscar la secuencia optima es simplemente buscar el camino demınimo coste a traves del cual ocurre la secuencia de observacion dada.

Observese que el Algoritmo de Viterbi es esencialmente una forma de programaciondinamica para minimizar U(i0, i1, ..., iT−1).

A continuacion se ilustra con un ejemplo como se hace la minimizacion. Considerese unmodelo oculto de Markov de tres estados. Fig.3.14 en las lıneas que unen los estados entresı se muestran los costes asignados a estos caminos como se ha descrito antes. Los numerosen los cırculos muestran los costes iniciales asignados a los estados correspondientes. Parafacilitar el entendimiento del algoritmo se asume que los costes son simetricos (es decir, elcoste para pasar del estado i al j es el mismo que el correspondiente para pasar del estadoj al i) tambien se ha asumido que los costes no cambian con el tiempo lo que no suele sercierto pero una vez sea entendido el caso simplificado la extension a aquel es directa.


Figura 3.14: Modelo de tres estados con los pesos de transicion y entrada.

Considerese la Fig.3.15. Se toma una secuencia de observacion O0, ..., O3 de longitudcuatro. En el instante t = 1 el estado 0 puede ser visitado desde alguno de los tres estadosposibles en el instante t = 0. Se averiguan los costes de cada uno de sus caminos y sele anaden los costes iniciales (a este costo acumulativo en el estado 0 se le puede llamarcoste del estado 0 en el instante t = 2). Ası, yendo del estado 0 al estado 0 el coste en esteestado es 3 + 6 = 9. De forma similar el coste en el estado 0 yendo desde el estado 1 es3 + 4 = 7 y el correspondiente yendo desde el estado 2 es 2 + 3 = 5. De todos estos 5 es elcosto mınimo. De este modo se refiere este coste en el estado 1 para calculos posteriores.Los caminos de coste acumulado mınimo se muestran en la figura por lıneas acabadas enflecha. Los costes acumulativos se muestran en negrita a lo largo de cada estado e instantede tiempo. Se repite el mismo procedimiento para los estados 1 y 2. Se ve que los costesmınimos en el estado 1 y en el estado 2 son 6 (desde el estado 2) y 6 (desde el estado 0)respectivamente.

Se repite el procedimiento anterior de nuevo para t = 2 pero ahora usando los costesacumulados por cada estado en lugar de los costes iniciales. Y el mismo procedimiento serepite para t = 3. Ahora se selecciona aquel estado con menor coste. Se ve que el estado0 es el estado requerido con un coste de 11. Volviendo atras en la secuencia de estados atraves de los cuales se llega al estado 0 en t = 3 se tiene la secuencia de estados a travesde la cual la secuencia de observacion dada tiene la mayor probabilidad de ocurrir. Comose puede ver en la figura esta secuencia de estados es 3, 1, 3, 1 que se muestra en negritaen la figura.


Figura 3.15: Obtencion del itinerario de coste mınimo.

Para demostrarlo supongase que se tiene como longitud de la secuencia de observacion2 y como ultimo estado el 2. ¿Que camino se deberıa elegir para minimizar el coste? Elprocedimiento explicado antes muestra claramente que se podrıa escoger el camino quecomienza en el estado 0 y termina en el estado 2 (en t = 2) ya que da el mınimo coste enel estado 2. Todos los demas caminos tienen un costo mayor. Si algun otro estado debeser el ultimo se aplican argumentos similares. Analogamente si la secuencia de observaciontuviese que ser de longitud tres y terminar en el estado 0 se podrıa escoger el camino0, 2, 0. Esto representa para un instante dado que el camino trazado hasta algun estadopor el procedimiento anterior es el de mınimo coste si se debe parar en ese instante enese estado. Avanzando hasta t = 3 se observa que se tienen los caminos de mınimo costecorrespondientes a parar en los estados 0, 1 y 2 respectivamente.

Llegados a este punto se procedera a la implementacion del algoritmo de Viterbi ([13]y [22]):

Nota: δt(i) representa el coste acumulado en el estado i en el instante t a medida queavanzada el algoritmo y ψt(j) representa el estado en el instante t − 1 que tiene mınimocoste correspondiente a una transicion desde el estado j e instante t. Por ejemplo en laFigura 3.15 se tiene:

δ2(0) = 9, δ2(1) = 9, δ2(2) = 8 (3.73)

yψ3(0) = 3, δ3(1) = 3, δ3(2) = 1 (3.74)


1. InicializacionPara 0 ≤ i ≤ N − 1

δ0(i) = − ln(πi)− ln(bi(O0)) (3.75)

ψ0(i) = 0 (3.76)

2. Calculo recursivoPara 1 ≤ t ≤ T − 1 y 0 ≤ j ≤ N − 1:

δt(j) = mın0≤i≤N−1

[δt−1(i)− ln(aij ]− ln(bj(Ot)) (3.77)

ψt(j) = arg mın0≤i≤N−1

[δt−1(i)− ln(aij)] (3.78)

3. Para terminar

P ∗ = mın0≤i≤N−1

[δT−1(i)] (3.79)

q∗T−1 = arg mın0≤i≤N−1

[δT−1(i)] (3.80)

4. Se obtiene, volviendo atras, la secuencia de estados optimaPara t = T − 2, T − 3, ..., 0:

q∗t = ψt−1(q∗t+1) (3.81)

Ası exp(−P ∗) da la probabilidad requerida para la optimizacion y Q∗ = {q∗0, q∗1, ..., q∗T−1}es la secuencia de estados optima.

El analisis de este proceso muestra que respecto al computo en Algoritmo de Viterbies similar a los procesos de avance y retroceso exceptuando las comparaciones necesariaspara encontrar el valor maximo. Ası su complejidad es tambien del orden de N2T . Estoresuelve el segundo problema.

3.4.6. Soluciones al Tercer Problema: Algoritmo de Segmentacion

K-means y Reestimacion de Baum-Welch

Este problema afecta directamente al entrenamiento de los Modelos Ocultos de Markovpues codifica las secuencias observacion de modo que si una secuencia tiene varias carac-terısticas similares a la dada y se ecuentra mas tarde podrıa ser capaz de identificarla.Existen dos metodos a los que se puede acudir dependiendo de que probabilidad se elija


para la identificacion:

Algoritmo de Segmentacion K-means: En este metodo los parametros del mo-delo λ = (A,B, π) se ajustan para maximizar P (O, I|λ) donde I es la secuenciaoptima dada en la solucion del problema 2.

Metodo de Reestimacion de Baum-Welch: En este metodo los parametros delmodelo λ = (A,B, π) se ajustan para incrementar P (O|I) hasta que se alcance unvalor maximo ([13]). Como se ha visto antes, el calculo de P (O|I) supone la sumade P (O, I|λ) para todas las posibles secuencias de estados I. Por lo tanto este casoel objetivo no esta en una secuencia de estados particular.

3.4.6.1. Metodo de Reestimacion de Baum-Welch

Este metodo parte de un modelo inicial obtenido usando las formulas (dadas anterior-mente) para maximizar P (O|λ). El modelo inicial se puede construir de muchas maneraspero aquı se usaran los cinco primeros pasos del Algoritmo de Segmentacion K-meansdescrito antes para dar una estimacion inicial razonable del modelo oculto de Markov.A partir de ahora se asume como conocido el modelo inicial. Este algoritmo maximizaP (O|λ) ajustando los parametros de λ. A este criterio de optimizacion se le denominacriterio de maxima verosimilitud y a la funcion P (O|λ) funcion de verosimilitud.

Antes de pasar a la formulacion del algoritmo se introduciran algunos conceptos ydefiniciones que seran necesarios en las expresiones finales. Considerese γt(i) definido como:

γt(i) = P (it = i|O, λ), (3.82)

es decir, la probabilidad de estar en el estado i en el instante t dada la secuencia deobservacion O = O0, O1, ..., OT−1 y el modelo λ = (A,B, π). Por la ley de Bayes se tiene:

γt(i) =P (it = i,= |λ)

P (O|λ)=

αt(i)βt(i)P (O|λ)

, (3.83)

donde αt(i) y βt(i) estan definidos por las ecuaciones Eq.3.56 y Eq.3.64 respectivamente.La variable αt(i) considera O0, ..., Ot y el estado i en el instante t, la variable βt(i)considera Ot+1, ..., OT−1 dado el estado i en el instante t.

Ademas de γt(i) se define tambien ξt(i, j) como:

ξt(i, j) = P (it = i, it+1 = j|O, λ) (3.84)


es decir, la probabilidad de estar en el estado i en el instante t y hacer una transicion alestado j en el instante t + 1, dada la secuencia de observacion O = O0, O1, ..., OT−1 y elmodelo λ = (A,B, π). Usando la ley de Bayes se ve que:

ξt(i, j) =P (it = i, it+1 = j, O|λ)

P (O|λ)(3.85)

Como O = O0, O1, ..., OT−1 entonces el numerador es igual a:

P (it = i, O0, ..., Ot, Ot+1, OT−1, it+1 = j|λ) =

= P (it = i, O0, ..., Ot, Ot+1|λ)P (Ot+1, OT−1, it+1 = j|λ) (3.86)

Considerese el segundo termino. El sımbolo observacion en el instante t + 1 es Ot+1 y elsistema debe estar en el estado j; esto quiere decir que el sımbolo de observacion Ot+1

debe ser emitido por el estado j. Entonces se tiene:

P (Ot+1, ..., OT−1, it+1 = j|λ) = P (it+1 = j, Ot+1|λ)P (Ot+1, ..., OT+1|it+1 = j, λ) (3.87)

= aijbj(Ot+1)βt+1(j) (3.88)

Por lo tanto combinando Eq.3.56, Eq.3.84, Eq.3.86 y Eq.3.88 se tiene:

ξt(i, j) =αt(i)aijbj(Ot+1βt+1(j))

P (O|λ)(3.89)

Aquı αt(i) considera la secuencia de observacion parcial O0, ..., Ot, aij considera la transi-cion del estado i al j, bj(Ot+1) la emision del sımbolo Ot+1 por parte del estado j y βt+1(j)considera la secuencia parcial restante Ot+1, ..., OT−1.

Si se suman los valores de γt(i) desde t = 0 a T − 1 se tiene una cantidad que se puedever como el numero de veces que se espera que el estado i sea visitado y si se suma solohasta T −2 entonces se tendrıa el numero de transmisiones esperadas desde el estado i (alno haber transicion en t = T ). De forma analoga, si se suma ξt(i, j) desde t = 0 a T − 2,se obtiene el numero de transiciones esperadas desde el estado i al estado j. Se tiene pues:

T−2∑

t=0

γt(i) ≡ numero esperado de transiciones desde el estado i

T−2∑

t=0

ξt(i, j) ≡ numero esperado de transiciones desde el estado i al estado j


Despues de estas definiciones previas se pueden presentar las formulas del Metodo deReestimacion de Baum-Welch:

πi = γ0(i)

/N−1∑

i=0

γ0(i), 0 ≤ i ≤ N − 1 (3.90)

aij =T−2∑

t=0

ξt(i, j)

/T−2∑

t=0

γt(i) (3.91)

bj(k) =

(T−1∑

t=0

γt(j)|Ot = k

)/T−1∑

t=0

γt(j) (3.92)

La formula de reestimacion para πi es simplemente la probabilidad de estar en el estadoi en el instante t. La expresion para aij es la razon entre el numero esperado transicionesdel estado i al j y el numero esperado de transiciones desde el estado i. La expresion parabk(i) es la razon entre el numero que se espera que estando en el estado j se emita elsımbolo Ok y el numero de veces que se espera que el modelo este en el estado j. Noteseque el sumatorio en la ultima expresion llega hasta t = T − 1.

Si se identifica el modelo inicial como λ y el modelo estimado como λ obtenido de losparametros estimados anteriormente, entonces se observa para ambos que:

1. El modelo inicial λ es un punto crıtico de la funcion de verosimilitud en cuyo casoλ = λ, o

2. P (O|λ) > P (O|λ), es decir, se ha encontrado un modelo mejor para el cual lasecuencia de observacion Ot+1, ..., OT−1 es mas probable que se produzca.

De este modo se sigue calculando iterativamente hasta que la probabilidad P (O|λ) semaximice. Esto resuelve el tercer problema.

En el proceso anterior se asume que los parametros del modelo de Markov se ajustanpara maximizar la probabilidad de ocurrencia de una unica secuencia de observacion. Enel caso mas general la cantidad de secuencias de observacion obtenidas para la definiciondel modelo no esta determinada.

3.4.7. Tipos de Modelos Ocultos de Markov

Un metodo de clasificar los modelos ocultos de Markov es atendiendo a la estructurade la matriz de transicion.


3.4.7.1. Modelo Ergodico o Completamente Conectado

En el que se podrıa alcanzar cada estado del modelo, en un solo paso desde cualquierotro estado. Estrictamente hablando, un modelo ergodico tiene la propiedad de que cadaestado puede alcanzarse desde cualquier otro estado en numero finito de pasos. Ası, paraun modelo de cuatro estados, este tipo de modelo tiene la propiedad de que cada coeficientees distinto de cero.

3.4.7.2. Modelos de Izquierda-derecha

Existen otros modelos que representan mejor las propiedades observables de la senal,como el modelo izquierda-derecha o modelo Bakis. Se denomina ası porque la secuenciade estados subyacente asociada con el modelo tienen la propiedad de que a medida que eltiempo avanza, el ındice de estado tambien se incrementa (o a lo sumo permanece igual).Este tipo de modelo oculto de Markov puede modelar facilmente senales cuyas propiedadescambian a lo largo del tiempo, por ejemplo la voz. Expresado en los coeficientes del modelose tiene:

aij = 0 ∀i < j

πi = 0 ∀i 6= 0

π0 = 1

3.5. Modelo de Markov frente a Redes Neuronales y de Ba-

yes

Los modelos de Markov se pueden incluir en una clase de modelos mas general: lasredes probabilısticas o modelos graficos probabilısticos que incluyen a las redes de Bayes yaquellas redes neuronales que incluyen modelos probabilısticos. Estas tecnicas se empleanpara construir modelos complejos a partir de componentes simples. Estas redes tienen encomun el uso de informacion previa, obtenida en la fase de aprendizaje.

La transformacion de redes neuronales realimentadas en redes de Bayes se ha propuesto.Se han analizado equivalencias similares entre redes de Bayes y modelos ocultos de Mar-kov. Aun ası, dado que el modelo oculto de Markov es el modelo de un proceso dinamicomientras que la red de Bayes es la representacion estatica de la union o de las probabili-dades condicionales entre algunas variables, la red resultante es un conjunto de unidades

3.5. MODELO DE MARKOV FRENTE A REDES NEURONALES Y DE BAYES 95

repetidas que se expanden en el tiempo. Visto esto, la sustitucion de los modelos de Mar-kov por esta representacion alternativa no parece adecuada. Ademas, los modelos ocultosde Markov tienen un conjunto de algoritmos de inferencia, aprendizaje y reconocimientomuy bien optimizados para manejar grandes cantidades de datos.

Es interesante, ademas, que muchos de los algoritmos desarrollados para redes de Bayesson aplicables a mas modelos generales que los usados por los modelos de Markov. Esteen principio puede crear herramientas mas capaces de producir nuevos tipos de modelosocultos de Markov mas potentes. Por ejemplo, se ha probado que los algoritmos de in-ferencia para redes de inferencia probabilıstica (PIN, Probabilistic Inference Network), elJLO y el algoritmo de Dawid son generalizaciones de los algoritmos de avance-retrocesoy de Viterbi. Ademas los algoritmos de entrenamiento de Baum-Welch, MLE y MAP sonbasicamente procedimientos de estimacion-maximizacion para el aprendizaje de parame-tros en modelos con datos ocultos o perdidos y se usan tambien para el aprendizaje deparametros en redes de Bayes.

Los modelos ocultos de Markov se pueden extender presentando modelos con represen-tacion de estado distribuido (HMM factorial). Estos se basan en la idea de que codificar laevolucion en el tiempo en una unica variable de estado limita en gran medida su capacidadde representacion, dado que pueden necesitarse demasiados estados diferentes en un HMMpara almacenar pocos bits de informacion.

En particular, la representacion de estado distribuido puede ayudar en el modelado dedatos temporales generados por la superposicion de procesos independientes, por ejemplo,la senal producida por dos hablantes simultaneos, dividiendo un unico flujo de entrada enun par de secuencias de estado. Muchos problemas de union de sensores pueden beneficiarsede este procedimiento, como la union de senales de audio y video, en sıntesis del movimientolabial.

Otra extension del modelo se basa en considerar el vector p + 1 formado por la salidaen los instantes t a t − p como una observacion multidimensional en el instante t. Estaestrategia permite tener en cuenta una mayor historia del proceso y sustituye la necesidadde una cadena de orden mayor que uno en el HMM. Pero la elevada complejidad compu-tacional puede hacer el problema intratable. Esta extension se ha propuesto para manejarla coarticulacion de fonemas en el habla que tiene efecto sobre un amplio intervalo detiempo.

Una modificacion interesante de los modelos ocultos de Markov que es basicamente unamodificacion de las redes neuronales en lugar de las redes de Bayes es el modelo oculto deMarkov generalizado (GHMM). Los GHMM surgen de la conveniencia de permitir a los


elementos de la matriz del HMM tomar valores negativos e incluso mayores que la unidad.Por lo tanto, no se consideran probabilidades. De todos modos los valores se restringende modo que el GHMM asigna probabilidades a las secuencias de sımbolos. Por tanto elGHMM sigue definiendo distribuciones de probabilidad reales en sus secuencias de saliday es posible emplear el entrenamiento MLE, maximizando la semejanza.

Las probabilidades de las secuencias de sımbolos de salida se pueden calcular mediantealgebra lineal, y los estados del proceso pueden representarse como vectores en el espaciode los estados del modelo oculto de Markov. Si las matrices del HMM estan limitadas a serestocasticas, esto restringe las clases de transformaciones lineales que pueden producirsey los estados del proceso se limitan a un pequeno subconjunto del espacio vectorial. Si seeliminan las restricciones estocasticas, entonces, es util emplear todas las transformacio-nes lineales y expandir el espacio vectorial. Ası, la interpretacion de los parametros delmodelo pueden ser menos importantes que la parsimoniosa representacion de los procesosestocasticos.

Bibliografıa

[1] German Alonso Gomez Rojas, Juan Carlos Henao Lopez y Harold Salazar Isaza,Entrenamiento de una red neuronal artificial usando el algoritmo ”Simu-

lated Annealing”, Universidad Tecnologica de Pereira Grupo de Planeamiento enSistemas Electricos (2002)

[2] Sumit Basu, A Linked-HMM Model for Robust Voicing and Speech Detec-

tion, IEEE Conference on Acoustics, Speech, and Sigal Processing 2003 (ICASSP2003).

[3] Brain, A. E. et al., Graphical Data Processing Research Study and ExperimentalInvestigation, Report no. 8, pp. 9-13 y no. 9, pp. 3-10, Contract DA 36-039 SC-78343,SRI International, Menlo Park, CA (Junio y Septiembre 1962)

[4] Cooper, G., Computational Complexity of Probabilistic Inference Using Ba-

yesian Belief Networks (Research Note), Artificial Intelligence, 42(2/3):393-405(1990).

[5] Dietterich, T. y Bakiri, G., Error-Correcting Output Codes: A General Met-

hod for Improving Multiclass Inductive Learning Programs, Proceeding ofthe Ninth National Conference on Artificial Inteligence (AAAI-91), pp 572-577, Men-ko Park, CA: AAAI Press (1991).

[6] Dietterich, T. y Bakiri, G., Solving Multiclass Learning Problems via Error-CorrectingOutput Codes, Journal of Artificial Inteligence Research, 2:236-286 (1995).

[7] Rakesh Dugad y U. B. Desai, A Tutorial on Hidden Markov Models, SignalProcessing and Arificial Neural Networks Laboratory, Department of Electrical En-ginneering, Indian Institute of Technology - Bombay (Mayo 1996).

97

98 BIBLIOGRAFIA

[8] Marianna Espinosa Martınez y Benjamın Serridge, Comparacion entre redes neu-

ronales y modelos oculos de Markov para el reconocimiento de voz, utili-

zando el CSLU Toolkit, Universidad de las Americas-Puebla.

[9] G. D. Forney Jr., The Viterbi Algorithm, Proc. IEEE, vol 61, no. 3, pp 263-278(Marzo 1973).

[10] Donald R. Fredkin y John A. Rice, Fast Evaluation of the Likelihood of an

HMM: Ion Channel Currents with Filtering and Colored Noise, IEEE Tran-sactions on Signal Processing, vol.49, no.3 (Marzo 2001).

[11] Lauritzen, S. y Spiegelhalter, D., Local Computations with Probabilities on

Graphical Estructures and Their Application to Experts Systems, Journalof the Royal Statistical Society, B 50(2):157-224 (1988).

[12] Nils J. Nilsson, Inteligencia Artificial, Una nueva sıntesis, Ed. McGraw Hill.

[13] Lawrence R. Rabiner y Bing-Hwang Juang, An Introduction to Hidden Markov

Models IEEE ASSP Magazine (Enero 1986).

[14] Lawrence R. Rabiner, A Tutorial on Hidden Markov Models and Selected Ap-

plications in Speech Recognition, Proceedings of the IEEE, vol.77, no.2 (Febrero1989).

[15] Lawrence R. Rabiner y Bing-Hwang Juang, The Segmental K-Means Algorithm

for Estimating Parameters on Hidden Markov Models, IEEE Transactionson Acoustics, Speech, and Signal Processing, vol.38, no.9 (Septiembre 1990).

[16] Rosenblatt, F., Principles of Neurodynamics, Washington DC: Spartan Books(1962).

[17] Rumelhart, D. E.; Hinton, G. E. y Williams, R. J., Learning Internal Representataionsby Error Propagation, Rumelhart, D. E. y McClelland, J. L. (eds),Parallel DistributedProcessing, vol. 1, pp. 318-362 (1986).

[18] Haykin Symon, Neural Network. A Comprehensive Foundation, 2aedicion,Prentice-Hall 1999.

[19] Werbos, P., Beyond Regressions: New Tools for Prediction and Analysis in

the Behavioral Sciences, Ph.D. Thesis, Harvard University (1974).

BIBLIOGRAFIA 99

[20] Widrow, B., Generalization and Information Storage in Networks of Adaline

”Neurons”, Yovitz, M.; Jacobi, G. y Goldstein, G. (eds.), Self Organizing Systems,1962, pp. 435-461, Washington DC: Spartan Books (1962).

[21] Widrow, B. y Hoff, M. E., Adaptative Switching Circuits, 1960 IRE WESCONConvention Record, pp 96-104, Newe York.

[22] Yang He y Amlan Kundu, 2D Shape Classification Using HMMs, IEEE Trans. Patt.Anal. Machine Intell., vol. 13, no.11, pp. 1172-1184, (Noviembre 1991).

[23] Steve Young, Talking to Machines (Statistically Speaking), Cambridge Univer-sity Engineering Department.

[24] ChengXiang Zhai, A Brief Note on the Hidden Markov Models (HMMs), De-partment of Computer Science, University of Illinoids at Urbana-Champaign (Marzo2003).

100 BIBLIOGRAFIA

Documents

Sistemas de Reconocimiento de Patronesbibing.us.es/proyectos/abreproy/3851/fichero/PFC-3.pdfSistemas de Reconocimiento de Patrones 3.1. Introducci´on La senal˜ del habla tal y como