Repositorio Institucional de Documentos

PROYECTO FIN DE CARRERA paralelización del algoritmo de búsqueda de un reconocedor automático de voz Autor Juan Vallés Martín Director Antonio Miguel Artiaga escuela de ingeniería y arquitectura 2014 Juan Vallés Martín: Paralelización del algoritmo de búsqueda de un reconocedor automático de voz, 2014 RESUMEN Paralelización del algoritmo de búsqueda de un reconocedor automático de voz Durante años, la velocidad de los procesadores ha aumentado debido al aumento de transistores en los circuitos integrados. Estas mejoras en la eficiencia no requerían cambios en el software: el mismo programa era más rápido en un ordenador con una frecuencia de reloj más alta. Sin embargo, la posibilidad de seguir mejorando la capacidad de los sistemas actuales puede ser acelerada a un ritmo mucho mayor si se consigue paralelizar el problema y tratarlo mediante arquitecturas de hardware paralelo disponibles, como procesadores multinúcleo, clústers o GPUs (Graphics Processing Units). El proyecto plantea el estudio de la viabilidad de un reconocedor de voz con funciones en paralelo mediante el desarrollo de un prototipo. Los objetivos principales son la paralelización de la búsqueda de la secuencia de estados (sonidos) más probable y el cálculo de las verosimilitudes de los datos de entrada (observaciones), explorando las posibilidades que este paralelismo ofrece y viendo el rendimiento que con él puede llegarse a obtener. El desarrollo se lleva a cabo en el lenguaje de programación C, mientras que las funciones paralelizadas se implementan en GPUs utilizando CUDA, un modelo de programación adaptado a esta arquitectura, y su extensión para C. En cada instante del proceso de reconocimiento hay un número determinado de tokens activos con una probabilidad y una secuencia de estados asociadas y que representan las hipótesis más probables hasta el momento. Cuando hay nuevos datos de entrada, estos tokens se propagan hacia los siguientes estados, cambiando su peso dependiendo de las probabilidades de transición entre estados y de las probabilidades de observación (cómo los datos se ajustan al sonido correspondiente a cada estado). Los tokens que acaban en el mismo estado que otro con mayor peso y los que no superan cierta probabilidad son desechados. El proceso acaba mostrando la secuencia asociada al token de mayor peso en el instante final. Hay partes de este proceso que son expresables como productos matriciales o vectoriales y que por tanto son fácilmente paralelizables. Cada estado lleva asociada una mezcla de Gaussianas de las mismas dimensiones que las de los datos de entrada. La parte más costosa del cálculo de las probabilidades de observación es una distancia entre vectores de muchas dimensiones. Desarrollándola como un polinomio de segundo grado y apilando los coeficientes de todos los polinomios en una matriz podemos convertir este cálculo en un producto matricial, susceptible también de ser paralelizado. iii ÍNDICE GENERAL 1 introducción 1 1.1Antecedentes y motivación 1 1.2Descripción y objetivos del proyecto 2 1.3Organización de la memoria 3 2 el proceso de reconocimiento 5 2.1Fundamento teórico 5 2.2Modelos Ocultos de Markov 6 2.3Algoritmo de Viterbi 9 2.4Búsqueda con tokens 11 3 implementación 15 3.1Introducción 15 3.2Consideraciones previas a la implementación 16 3.3Propagación 19 3.3.1Cálculo de tokens en el siguiente frame 19 3.3.2Purga 20 3.3.3Búsqueda del máximo por reducción 21 3.3.4Actualización de índices y número de tokens activos 23 3.4Cálculo de las probabilidades de observación 23 3.4.1Inicialización de gMask yfetch 24 3.4.2Multiplicación con máscara 24 3.4.3Suma y normalización 25 3.4.4Actualización de las probabilidades acumuladas 26 3.5Recuperación de resultados 26 3.5.1Actualización del buffer Φ26 3.5.2Algoritmo de bactracking 28 4 resultados 31 4.1Estudio de tiempos 31 4.1.1Comparación del rendimiento con otros reconocedores 32 4.1.2Distribución de tiempos 33 4.1.3Rendimiento del cálculo de probabilidades de observación 35 5 conclusiones 37 5.1Resumen del proyecto y análisis de objetivos 37 5.2Desarrollo en el futuro 38 a conceptos básicos de cuda 41 v vi índice general a.1Historia de la programación en paralelo 41 a.2Introducción a CUDA C 43 a.3Ejemplo: suma de vectores 44 b cálculo de las probabilidades de observación 47 b.1Introducción 47 b.2Expresión del cálculo como producto matricial 47 c algoritmo de reconocimiento 49 c.1Consideraciones previas 49 c.2Algoritmo 50 c.2.1Inicialización 50 c.2.2Bucle de reconocimiento 51 c.2.3Backtracking 52 d estructuras de datos 55 bibliografía 59 1 INTRODUCCIÓN 1.1 antecedentes y motivación La interacción entre personas y máquinas es más frecuente y diversa a medida que avanza la tecnología. Hoy podemos pedirle a un dispositivo que nos indique la ruta hacia nuestro destino o que reconozca una canción por nosotros. Dado que el habla es, en muchas situaciones, la forma de interacción más natural para el ser humano, es lógico que haya un interés especial en el desarrollo de sistemas capaces de reconocer y entender la voz humana. El Reconocimiento Automático del Habla (RAH) es el proceso de clasificación de secuencias de patrones extraídas de una señal de audio que contiene voz humana, de forma que el mensaje contenido en ella es reconocido. Entre sus aplicaciones pueden encontrarse sistemas de dictado de palabras o documentos, traducción entre lenguajes, sistemas de control por voz o subtitulado automático de documentos audiovisuales. Aunque la investigación en este campo comenzó hace décadas, y pese a los avances conseguidos en los últimos años, todavía son necesarias mejoras en la robustez y la velocidad de los sistemas de reconocimiento para poder hablar de un reconocedor de altas prestaciones, especialmente si se consideran aplicaciones de tiempo real. El proyecto plantea la programación de funciones en paralelo como medio para acelerar el software de reconocimiento del habla. Hasta hace algunos años la velocidad de los procesadores aumentaba principalmente debido al aumento del número de transistores en los circuitos integrados (aproximadamente el doble cada dos años), siguiendo la ley de Moore. De esta forma, el mismo programa era más rápido en un ordenador de prestaciones más altas sin requerir cambios en el software. Sin embargo, aunque el número de transistores continúa aumentando, la velocidad de reloj ha dejado de seguir esa tendencia, y recientemente han aparecido nuevas arquitecturas y modelos de programación que permiten aumentar la velocidad de los sistemas de una forma alternativa y, en ocasiones, a un ritmo mucho mayor. La programación en paralelo, y en particular la programación de GPUs (Graphic Processing Units), es un modelo que ha ganado popularidad en los últimos años. Dado que la mayoría de operaciones realizadas sobre un píxel en una imagen no dependen del resultado de dicha operación en otros píxeles, las tarjetas gráficas se compo1 2 introducción nen de varios procesadores (más simples que una CPU) capaces de realizar la misma tarea en paralelo, de forma que varios píxeles son tratados a la vez. Esta idea se ha aprovechado en aplicaciones tradicionalmente ejecutadas por CPUs consiguiendo mejoras en los tiempos de ejecución. En particular, aquellas funciones expresables como sumas o productos matriciales dan buenos resultados al programarse en paralelo. Actualmente el framework que predomina en la programación de GPUs es CUDA, perteneciente a nVidia1„ el cual proporciona una serie de herramientas de desarrollo para acceder a los sets de instrucciones de sus tarjetas gráficas. 1.2 descripción y objetivos del proyecto Como se mencionaba en el apartado anterior, el objetivo fundamental del proyecto es el estudio de la viabilidad de un reconocedor de voz con los distintos pasos del proceso de reconocimiento implementados como funciones en paralelo programadas en CUDA, observando las mejoras en los tiempos de ejecución que con éstas se pueden conseguir. Para ello, es necesario crear un prototipo programado en lenguaje C, capaz de reconocer secuencias de palabras a partir de ejemplos y modelos estadísticos del laboratorio de Tecnologías del Habla2del Grupo de Tecnologías de las Comunicaciones de la Universidad de Zaragoza. El primer objetivo del proyecto es, por tanto, expresar el algoritmo de reconocimiento (tradicionalmente implementado como una serie de bucles anidados) como una sucesión de operaciones matriciales y vectoriales, para así facilitar el desarrollo posterior de funciones en paralelo. Las estructuras de datos resultantes son matrices y vectores de gran tamaño pero con solamente unos pocos elementos distintos de cero, por lo que es necesario trabajar con estructuras de tipo sparse, las cuales guardan únicamente los índices y los valores de los elementos activos en un vector o en una matriz. Existen librerías que permiten trabajar con este tipo de estructuras en CUDA y realizar operaciones matriciales simples como sumas o multiplicaciones. Las funciones disponibles en esta librería son a priori más rápidas que cualquier versión "hecha a mano"de las mismas, aunque son funciones muy generales y optimizadas para la resolución de sistemas de ecuaciones. Por otra parte, no permiten trabajar en escala logarítmica, lo cual es un problema, ya que en el reconocimiento de voz los cálculos en escala lineal pueden salirse fácilmente de rango. El siguiente objetivo es, por tanto, la comparación de una solución basada en librerías con otra basada en funciones y estructuras hechas a medida para el problema. 1http://www.nvidia.com/object/cuda_home_new.html 2http://vivolab.es/ 1.3 organización de la memoria 3 Para facilitar el proceso de depurado también es conveniente tener una versión en Matlab del prototipo (sin funciones en paralelo, aunque con su equivalente matricial), ya que es más sencillo de programar aunque mucho menos eficiente. Asimismo, hace falta un programa, que también se implementa en Matlab, que lea los datos (los modelos acústicos y de lenguaje y las distintas secuencias de patrones) en el formato que utiliza HTK [6], un software de manejo de modelos de Markov utilizado habitualmente en RAH, y las transforme al formato adecuado para la versión en C del reconocedor. Entre las funciones programadas en paralelo se distinguen dos partes: el algoritmo de Viterbi y el cálculo de las probabilidades de observación. En el proceso de reconocimiento (explicado con detalle en el capítulo 2), la producción del habla se modela mediante Modelos Ocultos de Markov (HMM), y la búsqueda de la secuencia de palabras que mejor explica los datos observados se realiza mediante el algoritmo de Viterbi, aunque debido al tamaño de la red de estados (o sonidos posibles) que se maneja en un caso normal de reconocimiento es necesario incluir en él ciertas modificaciones. Hay pasos en este algoritmo claramente paralelizables, como la propagación de un estado hacia sus posibles estados destino. Otros, como la búsqueda de la hipótesis más probable entre las que consideramos en un momento dado, tienen una componente secuencial que dificulta su paralelización. Sin embargo, ya que la transferencia de datos entre CPU y GPU es costosa en tiempo, todos los pasos del algoritmo se intentarán programar con funciones en paralelo para mantener el tiempo dedicado a transferir datos en el mínimo necesario. La paralelización del cálculo de las probabilidades de observación es uno de los últimos objetivos que se incluyeron en el proyecto. Este cálculo se realiza en cada iteración de la fase de búsqueda del algoritmo de Viterbi, pero inicialmente se consideró calcularlo en CPU. Sin embargo, la carga computacional de esta operación hace que las mejoras en su eficiencia tengan un impacto importante en el rendimiento total del programa. La tarea de esta función consiste en el cálculo de la probabilidad de que unos datos de entrada correspondan a cada uno de los estados que consideramos posibles en un determinado momento. La parte más costosa de este cálculo es la distancia entre dos vectores de muchas dimensiones, la cual puede desarrollarse como un polinomio de segundo grado. Escribiendo los coeficientes de forma matricial, el cálculo puede realizarse como un producto, que como ya se ha mencionado es fácilmente paralelizable. 1.3 organización de la memoria Aparte del presente capítulo, que sirve como introducción y resumen del proyecto, la memoria se organiza en las siguientes secciones: 10 el proceso de reconocimiento Aprovechando la memoria finita de los HMMs usados en el problema, el algoritmo de Viterbi [5] permite reducir su complejidad resolviéndolo por partes. Éste recorre, a medida que van llegando nuevos datos de entrada, el diagrama de transiciones o diagrama de Trellis, calculando para cada estado la máxima verosimilitud y el estado desde el que se llega con ésta. Si un estado tiene dos o más transiciones de entrada, se puede mantener únicamente la secuencia que le llega con mayor probabilidad, ya que no hay forma de que las hipótesis descartadas superen en verosimilitud a la mantenida a partir de ese momento. A este proceso de eliminación de hipótesis se le llama purga. La máxima verosimilitud se obtiene a partir de la siguiente ecuación: Pt(j) = m´ ax i{Pt−1(i)aij bj(ot)}2⩽t⩽T;1⩽j⩽N(10) Esta ecuación indica que la probabilidad del mejor camino que termina en el instante ty estado jse obtiene a partir del camino que con mayor probabilidad se propaga desde cada uno de los Nestados en el instante t−1hacia el estado j, multiplicándose ésta por la verosimilitud del vector de características otpara el estado jen el instante t. Esta última verosimilitud es la misma para todos los caminos que confluyen en un mismo estado, por lo que la purga puede realizarse antes de este cálculo. En el instante t=1no puede aplicarse la ecuación (10), por lo que se multiplican las probabilidades iniciales πjpor las probabilidades de observación bj(o1). En general se parte de un único estado inicial con probabilidad 1, lo cual simplifica el proceso de búsqueda. La Figura 6muestra el algoritmo de Viterbi para el ejemplo de HMM tratado en el apartado anterior. Las probabilidades acumuladas se muestran normalizadas a la máxima en ese momento. Mientras hay datos de entrada los caminos se van propagando, repitiendo este cálculo iterativamente. Cuando llega la última observación, se calcula el estado final con mayor probabilidad acumulada y se recupera la secuencia de estados asociada a él buscando hacia atrás su estado de procedencia y el de los sucesivos estados recuperados. A esta búsqueda iterativa, ilustrada en la Figura 7, se la llama backtracking. Para reducir los problemas de desbordamiento puede expresarse la ecuación (10) como la suma de los logaritmos de cada término: Lt(j) = m´ ax i{Lt−1(i) + αij +βj(ot)}2⩽t⩽T;1⩽j⩽N(11) 2.4 búsqueda con tokens 11 Figura 6: Ejemplo del algoritmo de Viterbi 2.4 búsqueda con tokens Pese a que el algoritmo de Viterbi reduce la complejidad del problema de reconocer la secuencia de palabras más probable, en la mayoría de los casos el cálculo de la máxima probabilidad acumulada para todos los estados supone todavía una gran carga computacional. Las matrices de transiciones en RAH se caracterizan por tener un número de estados muy elevado con pocas transiciones de salida, por lo que calcular en cada frame temporal el camino hacia cada estado es costoso y en muchos casos innecesario. Una variación del algoritmo mantiene en cada momento un determinado número de hipótesis activas o tokens (testigos) y realiza los cálculos únicamente para los caminos considerados posibles en ese momento. En cada paso de propagación, cada token se clona tantas veces como su número de transiciones de salida, actualizando su probabilidad acumulada con la probabilidad de transición y la probabilidad de observación del estado de destino. Si más de un token coincide en el mismo estado, se elige aquél con mayor probabilidad acumulada. Si el número máximo de tokens Mes igual a Nlos resultados de este algoritmo son iguales a los del de Viterbi. Sin embargo, suelen introducirse dos aproximaciones para reducir el espacio en memoria y la carga computacional requeridos por este algoritmo. Un parámetro llamado beam determina cuántas veces más pequeña ha de ser la probabilidad acumulada de un token frente al de la hipótesis más fuerte para considerarse como despreciable. Así, en cada iteración se elimi- 12 el proceso de reconocimiento Figura 7: Búsqueda hacia atrás nan los tokens despreciables (paso de beam search). Por otra parte, se suele mantener un número máximo de tokens M<N. Si tras una propagación hace falta un número mayor de tokens, se mantienen los Mcon mayor probabilidad acumulada.El apéndice C profundiza en el algoritmo de búsqueda con tokens. La Figura 8ilustra el algoritmo con tokens, con un beam de 0,1. Figura 8: Ejemplo de búsqueda con tokens Esta variación permite, además, presentar resultados parciales a mitad del algoritmo. Si en un determinado instante ttodos los tokens provienen del mismo estado quiere decir que todas las hipótesis compartirán el mismo camino hasta t−1, por lo que los resultados hasta 2.4 búsqueda con tokens 13 ese instante pueden mostrarse ya. Los caminos asociados a los tokens se guardan en un buffer Φ, por lo que esta operación permite liberar espacio de él. La siguiente vez que se muestren resultados, se hará desde el momento t+1. En el caso de que el buffer se llene, se devuelve el camino asociado a la hipótesis más fuerte en ese momento, se limpia el buffer y se eliminan todos los tokens menos el de mayor peso. 3 IMPLEMENTACIÓN 3.1 introducción Un buen sistema de RAH no necesita únicamente ser preciso, sino que en la mayoría de los casos la eficiencia de un reconocedor se mide como el número de errores en el reconocimiento en función del tiempo de ejecución, como puede verse en la Figura 9. 12 13 14 15 16 17 18 19 20 01 2 3 4 5 6 7 8 WER RTF Comparación de reconocedores Configuración 1 Configuración 2 Figura 9: Número de errores frente a tiempo de ejecución[4] De esta forma, el proyecto plantea la implementación de funciones en paralelo empleando GPUs y CUDA C como medio para mejorar El Apéndice A incluye detalles y ejemplos de programación en CUDA. los tiempos de ejecución. Asimismo, las estructuras de datos empleadas en este tipo de sistemas se caracterizan por ser de gran tamaño, pero con pocos elementos útiles dentro de ellas (por ejemplo, la matriz de transiciones A, representada en la Figura 10). Por lo tanto, el ahorro de espacio en memoria mediante estructuras de tipo sparse y la gestión de éstas es otra de las características principales del prototipo implementado. La estructura de un reconocedor suele basarse en bucles anidados, como por ejemplo en el paso de propagación (ver Algoritmo 1). Transformando el algoritmo a uno equivalente basado en operaciones maEn el Apéndice C puede encontrarse el algoritmo de reconocimiento basado en matrices. triciales y vectoriales puede verse qué partes de éste son susceptibles de ser paralelizadas. 15 16 implementación Figura 10: Ejemplo de matriz de transición 1for i=1:ndo ;/*Para cada token activo */ 2 3for j=1:mdo ;/*Para cada estado de salida */ 4 5Calcular probabilidad acumulada Pa; 6if (Pa> Pj)then Pj=Pa; Algoritmo 1:Propagación por bucles anidados El ejemplo anterior puede expresarse como una suma matricial (se trabaja en escala logarítmica) y una búsqueda de máximos por columnas. La primera operación es claramente paralela, lo cual presenta gran oportunidad para mejorar los tiempos de ejecución, teniendo en cuenta que el número de tokens activos puede llegar a ser muy alto. Sin embargo, es más difícil implementar un algoritmo paralelo que realice la búsqueda de máximos, especialmente si se está trabajando con matrices sparse, en las cuales se incrementa la dependencia entre elementos. Este compromiso se verá prácticamente en todos los pasos del proceso de paralelización, lo cual no permite determinar a priori el impacto de la nueva implementación en los tiempos de ejecución. En consecuencia, lo que el proyecto plantea es el estudio de esta solución mediante un prototipo con funciones en paralelo. 3.2 consideraciones previas a la implementación Antes de comenzar a desarrollar el algoritmo es necesario decidir cómo trabajar con estructuras sparse. Existen librerías, como CUSP1 ocuSPARSE2que implementan diversas funciones para realizar ope1http://cusplibrary.github.io 2http://developer.nvidia.com/cuSPARSE 3.2 consideraciones previas a la implementación 17 raciones con matrices y vectores de este tipo. Pese a que éstas son probablemente más rápidas que una versión “hecha a mano” de las mismas, se trata de funciones generales optimizadas para el uso en resolución de sistemas de ecuaciones, por lo que el conocimiento del problema y la implementación de funciones a medida para éste puede resultar en una solución más eficiente que otra basada en el uso de librerías. Una de las primeras tareas del proyecto ha sido la comparación de la librería cuSPARSE con estructuras y funciones propias para las operaciones básicas que el problema requiere. Tras realizar este estudio, se ha optado por la segunda estrategia, en base a las siguientes razones: No existe una librería que permita trabajar con estructuras sparse en escala logarítmica, lo cual acarrea problemas de rango, especialmente en el cálculo de las probabilidades de observación. Una de las principales operaciones del algoritmo de reconocimiento, el paso de propagación, consiste en multiplicar la probabilidad de cada token (elementos de un vector) por una fila de la matriz de transiciones. Esta operación no existe en las librerías, ni tampoco la conversión de vector a matriz necesaria para expresar este paso como un producto matricial. Además, la librería advierte que el producto entre dos matrices sparse es muy poco eficiente. El conocimiento del problema permite, al realizar ciertos pasos del algoritmo, adelantar trabajo de las siguientes operaciones. La solución basada en librerías, al estar pensada para otro tipo de aplicaciones, implica un trabajo no despreciable en gestión de tipos de datos y conversión de formatos para adecuarse al problema de RAH. Tras definir las estructuras sparse a usar, se han agrupado distintas variables en estructuras y distintos pasos en funciones, de forma Las estructuras utilizadas en el proyecto están especificadas en el Apéndice D. que el programa principal queda legible y estructurado (la Figura 11 ilustra su funcionamiento básico). En él se distinguen las siguientes partes, algunas de las cuales se detallarán en los apartados siguientes: Declaración de variables y asignación de valores: Al comienzo del programa es necesario declarar las distintas variables que se van a usar y reservar espacio en memoria para ellas, en función de los parámetros del problema. Algunos de estos parámetros, como el tamaño del buffer o el beam, están definidos como macros, mientras que otros dependen del problema de reconocimiento concreto que se vaya a tratar. Los archivos que contienen 18 implementación Resultados Matlab Cuda C calcular p. obs. calcular p. obs. propagar actualizar phi backtracking Figura 11: Funcionamiento del reconocedor los datos de entrada al problema (la matriz de transiciones, las mezclas de Gaussianas, las observaciones y el diccionario), todos adecuados al problema mediante un programa escrito en Matlab, contienen el resto de parámetros necesarios, como el número de estados o el número máximo de transiciones desde un estado. Las distintas estructuras se inicializan mediante distintas funciones en el host o en la GPU según sea necesario, y se copian los operandos necesarios a la GPU. Tratamiento de la primera observación: Tras leer la primera observación, y con el vector de tokens inicializado con las probabilidades iniciales Π, se ponderan éstas con las probabilidades de observación de cada estado. Bucle de reconocimiento: Mientras hay nuevos datos de entrada con observaciones se ejecuta este bucle, que comienza con la propagación de los tokens (paso que incluye, además, la purga, el beam search y la normalización de éstos), cuyas probabilidades acumuladas se actualizan después con las probabilidades de observación. Finalmente, se actualiza la matriz Φa la vez que se comprueba si está llena o si todos los tokens provienen del mismo estado, en cuyo caso se llama a la función de backtracking, la cual recupera la secuencia asociada al token más probable desde el último frame recuperado hasta el actual y muestra por pantalla las palabras que ésta representa. Backtracking final: Cuando no hay más datos de entrada, se llama por última vez a la función de backtracking, la cual devuelve la secuencia asociada al token final más probable almacenada en el buffer desde la última llamada a la función. 3.3 propagación 19 3.3 propagación Esta parte del algoritmo, situada al comienzo del bucle de iteración, se encarga de calcular los tokens activos en el siguiente frame temporal. Se utilizan las estructuras tok, de tipo VSparse, para guardar los tokens activos, B, de tipo FSparse, para guardar los resultados de la generación de nuevos tokens, y A, de tipo Trans, la cual almacena las transiciones de salida de cada estado. 1B = repmat (tok, 1,N) + A; /*Cálculo de transiciones */ 2[tok, i_prev] = max (B, [], 1)’; /*Purga */ 3max_tok = max (tok); 4tok = tok - max_tok; /*Normalización */ 5tok(tok <beam) = −∞;/*Beam Search */ 6active = find (tok >−∞); /*Índices de tokens activos */ Algoritmo 2:Propagación de tokens 3.3.1Cálculo de tokens en el siguiente frame Figura 12: Cálculo de los nuevos tokens: resultado La primera operación que realiza esta función es la generación de tokens en el siguiente frame temporal, (primera línea del Algoritmo 2) donde cada hipótesis crea un nuevo token por cada una de las transiciones de salida del estado donde se encuentra. Como se ha explicado, este paso puede verse como la suma de la probabilidad acumulada de cada token activo a todos los elemento de su fila correspondiente en la matriz A, aunque en este caso en la matriz resultante, B, las filas 26 implementación float res = 0.; for(int j=jIni;j<jFin;j++) { res += exp(pExp[j] - *max); // Suma gMask[ii] = false;// Desactivación de flags } pExp[jIni] = log(res); Listing 1: Kernel con suma de resultados 3.4.4Actualización de las probabilidades acumuladas En el último kernel hay un hilo por cada token activo que recupera los resultados en pExp y los escribe en su posición correspondiente en pObs, de forma que al final los tok→nprimeros elementos de éste contienen las probabilidades de observación. Al finalizar la función get_pObs el programa principal llama a otro kernel que se ocupa de actualizar las probabilidades acumuladas de los tokens activos, sumándoles las probabilidades de observación (ver Figura 20). Figura 20: Actualización de los tokens con las probabilidades de observación 3.5 recuperación de resultados 3.5.1Actualización del buffer Φ Tras actualizar los tokens con las probabilidades de transición, se llama a la función update_phi, la cual registra los estados de procedencia de los tokens activos en ese frame en una matriz de índices, llamada Pen el código. En esta matriz cada fila corresponde a un fra- 3.5 recuperación de resultados 27 me temporal, la columna de un elemento representa el estado en el que está el token y el valor es su estado de procedencia. Se trata de un buffer circular (la primera fila es la siguiente a la última) donde dos punteros, tIni ytFin, indican la primera y la última fila efectivas. 1[tok, i_prev] = max (B, [], 1)’; /*Purga */ 2... 3active = find (tok >−∞); 4... 5Φ(active, t) = i_prev(active); /*Actualización de Φ*/ Algoritmo 4:Actualización de Φ Un kernel con un hilo por token activo se encarga de rellenar la fila número P→tFin, tras lo cual se incrementa este puntero circularmente. unsigned int j=blockIdx.x*blockDim.x+threadIdx.x; if (j>= nTok)return;// Un hilo por token activo int pos =colsPerRow *tFin +j; int col =iTok[j]; // Estado del token -> columna de P colIndP[pos] = col; int valpos =iPrevTok[col]; // Estado previo -> valor en P valP[pos] = valpos; if (i== 0) eprP[row]=n;// Número de elementos en la fila else { int col0 =tok->i[0]; // Comparación con el primer elemento if (valpos != tok->iPrev[col0]) *(P->eq) = false; } Listing 2: Kernel con actualización de P A continuación, otro kernel comprueba si todos los tokens provienen del mismo estado. Antes de su llamada, se inicializa una variable booleana, eq, a false. Cada hilo del kernel compara el estado previo de un token activo con el del primero. Si son distintos, desactiva el flag, de forma que éste al final indica si todos los estados son iguales. La función update_phi devuelve este flag al programa principal, el cual activa una llamada a la función backtracking. También se comprueba si al incrementar tFin éste ha alcanzado a tIni, en cuyo caso el buffer está lleno y hay que mostrar igualmente los resultados parciales para liberar espacio. En ambos casos, tras esta llamada se actualizan los punteros de P. 28 implementación 3.5.2Algoritmo de bactracking La función backtracking es llamada en los casos citados anteriormente y cuando no quedan más observaciones por leer. El algoritmo, que va recuperando la secuencia de estados más probable desde el más reciente hasta el más antiguo, varía ligeramente entre estos casos, por lo que una variable indica a la función en cuál de ellos se encuentra. La función comienza calculando el número de estados a recuperar, tras lo cual hay que guardar en seq[nPhi] el estado final más probable. int nPhi =P->tFin -P->tIni; if (nPhi <= 0) nPhi += seq->maxT; if (why == 0) nPhi --; Listing 3: Número de estados a recuperar Si todos los tokens provienen del mismo estado se decrementa nPhi ya que hay que recuperar la secuencia únicamente hasta el frame anterior. En éste se ha propagado un solo estado, cuyo índice está en el vector tok→iPrev en cualquiera de las posiciones guardadas en tok→i. Basta, por tanto, consultar el estado previo del primer token activo (por simplicidad) para conocer el estado final más probable en ese frame. En los otros dos casos se recupera la secuencia hasta el frame actual y hay que buscar el estado más probable en ese momento. La función max_value_ind realiza esta búsqueda por reducción devolviendo el estado final más probable, el cual se guarda en seq. Aunque el algoritmo de reducción es el mismo (se devuelve un resultado por bloque y se alterna entre dos vectores hasta tener un único resultado final), el kernel al que llama esta función trabaja con vectores de índices, los cuales sirven para consultar y comparar los valores de un un vector de tipo VSparse. A partir de este token se va extrayendo del buffer Psu secuencia de estados asociada. Un bucle iterativo se encarga de rellenar los elementos de seq desde nPhi −1hasta 0mediante la llamada a la función prev_state. El valor de Pen la posición correspondiente al último estado recuperado (la fila se corresponde con el frame y la columna con el estado), será su estado de procedencia (ver Figura 21). De esta forma, prev_state ejecuta un kernel en el cual cada hilo se ocupa de una columna de Pen esa fila o frame temporal. Si el último estado recuperado se corresponde con esa columna significa que forma parte del camino más probable, por lo que escribe el valor en esa posición en la secuencia. cudaMemcpy(seq->h_seq,seq->d_seq,n*sizeof(int), cudaMemcpyDeviceToHost); // Copia de seq a la CPU 3.5 recuperación de resultados 29 9 10 0 40 41 4041 39 3926 4113 410 410 39 4027 2614 131 41 4039394141 0 4140392613 39 4039 39 4140 seq 6 6 epr val colInd P 9 1 4041 39 3926 4113 410 410 39 4027 2614 131 41 40 3939 4141 0 41 4039 2613 39 4039 39 4140 seq 6 6 epr val colInd P Figura 21: Búsqueda del estado anterior en la secuencia int st,stPrev; stPrev =seq->stFin;// Último estado recuperado for (int j=0;j<n;j++) { st =seq->h_seq[j]; if(st == stPrev)continue;// Comprobar si cambia de estado if(strlen(dict[st])>0) // Si lleva palabra asociada printf(" %s ",dict[st]); stPrev =st; } fflush(0); seq->stFin =st;// Guardar último estado recuperado Listing 4: Número de estados a recuperar Finalmente, se imprime la secuencia de palabras. En el caso de buffer lleno no se tiene en cuenta el último estado, porque la siguiente vez que se haga backtracking será el primero. La función print_seq es una función secuencial que trabaja en CPU (los datos necesarios como la secuencia se copian antes desde la GPU). Ésta recorre la secuencia y, para cada estado, comprueba la tabla-diccionario dict y muestra por pantalla su palabra asociada, en caso de que la haya y si no es igual al estado anterior (un estado puede durar varios frames). Una variable de la estructura seq guarda el último estado aparecido entre distintas llamadas a la función print_seq, para evitar el error de sacar dos veces la misma palabra cuando no corresponde. 4 RESULTADOS A medida que se ha desarrollado el prototipo de reconocedor, éste se ha ido probando con distintos modelos estadísticos y datos de entrada para comprobar su correcto funcionamiento. Al no ser posible acceder a las tarjetas gráficas durante la ejecución, el proceso de depurado de las funciones en paralelo se ha realizado copiando los resultados al host e imprimiéndolos por pantalla. Para depurar las distintas funciones a nivel bajo se ha usado un modelo creado para tal propósito, con datos de entrada artificiales de una dimensión y cinco estados posibles que siguen una distribución Gaussiana. Un modelo tan simple dista mucho de una aplicación real, pero sirve para seguir el proceso de reconocimiento paso a paso y conocer los valores de las variables en todo momento, comprobando el funcionamiento básico del sistema. Un modelo simple pero real se ha usado para depurar los cálculos de las probabilidades de observación, lo cual requiere vectores de entrada multidimensionales, y el algoritmo de backtracking con diccionario, sacando palabras en vez de estados. Las secuencias de palabras de este modelo son series de dígitos en inglés, por lo que la gramática tiene un tamaño reducido y es posible todavía mostrar resultados intermedios y variables por pantalla, aunque es más difícil seguir su valor en todo momento. Este ejemplo también ha servido para comprobar el funcionamiento del programa que adapta el formato de datos de otros reconocedores, como el HTK, al usado por el prototipo. Finalmente, una gramática que modela preguntas de geografía se ha usado para comprobar el funcionamiento del prototipo con estructuras de grandes dimensiones (lo cual es útil para verificar la coordinación entre varios bloques de hilos para las distintas funciones en paralelo) y para comparar los resultados del prototipo con otros reconocedores. 4.1 estudio de tiempos Para el estudio de tiempos se ha reconocido una frase con el tercer modelo de los citados en el apartado anterior. La grabación dura 3,6 segundos, por lo que un tiempo de reconocimiento menor se considera como“reconocimiento en tiempo real”. Las simulaciones se han ejecutado en el un nodo, “voz08”, del clúster del Grupo de Tecnologías de las Comunicaciones de la Universidad de Zaragoza. Se ha utilizado una CPU Intel Xeon E5645 @2.40 GHz y una GPU nVidia GeForce GTX 660 Ti . 31 32 resultados 4.1.1Comparación del rendimiento con otros reconocedores Debido a que el prototipo ejecuta unas operaciones muy distintas de otros reconocedores secuenciales, es difícil comparar los tiempos de ejecución de manera justa. Asimismo, la falta de adaptación de los datos del prototipo al formato usado por otros reconocedores hace difícil una evaluación sistemática de la tasa de error frente al tiempo. Por tanto, se ha decidido comparar el tiempo de ejecución del prototipo con el de otros reconocedores en función del número medio de tokens activos por frame, lo cual indica cómo de eficiente es la gestión de tokens. En el tiempo de ejecución no se ha incluido la inicialización de las distintas variables y la carga de los modelos estadísticos. Los reconocedores utilizados para la comparación han sido el HTK, el cual es un software de RAH ampliamente utilizado, y el reconocedor del Laboratorio de Tecnologías del Habla de la Universidad de Zaragoza, en dos configuraciones distintas que aquí llamaremos KTree y WFST debido a los algoritmos que emplean. 01000 2000 3000 4000 5000 6000 0 2 4 6 8 10 12 14 X: 5695 Y: 3.6 Tiempo de ejecución del algoritmo de reconocimiento Tokens activos/frame Tiempo (s) X: 1785 Y: 1.477 Prototipo HTK WFST KTree Duración de la grabación Figura 22: Comparación de gestión de tokens Las Figuras 22 y23 muestran esta comparación, en la que puede observarse que, aunque para un número reducido de tokens HTK es más rápido, el prototipo consigue gestionar menos tokens reconociendo la frase sin errores, y más dentro del límite del reconocimiento en tiempo real. El otro reconocedor es más rápido en sus dos configuraciones, aunque también tiene fallos en el reconocimiento para un número de tokens reducido. Estos reconocedores tienen más parámetros que permiten optimizar su funcionamiento y usan distintas técnicas para reducir los tiempos de ejecución, alejándolos del algoritmo de Viterbi canónico. Por otra parte, el formato del modelo estadístico del prototipo es más compacto, lo cual agiliza su carga. La inicialización de variables del prototipo dura en torno a 0.6segundos, mientras que 4.1 estudio de tiempos 33 0 1000 2000 3000 4000 5000 6000 0 100 200 300 400 500 600 700 800 900 1000 Tiempo de ejecución respecto del resto de reconocedores Tokens activos/frame Tiempo prototipo/Tiempo reconocedor (%) HTK WFST KTree Figura 23: Comparación de gestión de tokens al resto de reconocedores les cuesta entre 5segundos (HTK) hasta superar la decena (KTree). 4.1.2Distribución de tiempos 500 1000 1500 2000 2500 3000 3500 4000 4500 0 0.5 1 1.5 2 2.5 Distribución total de tiempos del algoritmo Tokens activos/frame Tiempo (s) Backtracking Probabilidades de observación Inicialización Propagación Figura 24: Distribución de tiempos Las Figuras 24 y25 muestran la distribución de tiempos dentro del programa principal. El proceso más costoso de todas las operaciones es el de propagación, cuyo tiempo se ha desglosado en las Figuras 26. y 27 La actualización de los índices del vector tok tras la propagación se había diseñado inicialmente como un kernel de un solo hilo, el cual es más lento que la misma función en la CPU pero ahorra la transferencia de datos entre host y device. Tras comprobar el impacto 34 resultados 500 1000 1500 2000 2500 3000 3500 4000 4500 0 10 20 30 40 50 60 70 80 90 100 Distribución parcial de tiempos del algoritmo Tokens activos/frame Porcentaje del total Backtracking Probabilidades de observación Inicialización Propagación Figura 25: Distribución de tiempos de esta función en el tiempo de ejecución del programa, se ha implementado la misma función en la CPU, reduciendo considerablemente el tiempo de ejecución, por lo que se ha mantenido en el código final. 500 1000 1500 2000 2500 3000 3500 4000 4500 0 0.5 1 1.5 2 2.5 Distribución total de tiempos de la función de propagación Tokens activos/frame Tiempo (s) Normalización/Borrado Búsqueda del máximo Propagación Actualización de índices Purga Figura 26: Distribución de tiempos de la función de propagación La función que merece más la pena optimizar tras este cambio es la purga de tokens, la cual es una búsqueda del mejor token que ha llegado a cada estado y cuyo tiempo crece con el número de tokens activos. Aunque es hasta cierto punto paralelizable, el kernel tiene un bucle que termina con la sincronización de todos los hilos en cada iteración, lo cual ralentiza su funcionamiento. Podría estudiarse si el realizar la purga en la CPU (lo cual podría aprovecharse para realizar a la vez la búsqueda de la máxima probabilidad acumulada) aceleraría el proceso. 4.1 estudio de tiempos 35 Normalización/Borrado Búsqueda del máximo Propagación Actualización de índices Purga 500 1000 1500 2000 2500 3000 3500 4000 4500 0 10 20 30 40 50 60 70 80 90 100 Distribución parcial de tiempos de la función de propagación Tokens activos/frame Porcentaje del tota l Figura 27: Distribución de tiempos de la función de propagación 4.1.3Rendimiento del cálculo de probabilidades de observación El tiempo de ejecución del cálculo de las probabilidades de observación en el prototipo sí que puede compararse fácilmente con el de otros programas, ya que puede definirse el número de observaciones a calcular. El algoritmo del prototipo realiza una multiplicación con máscara por lo que el porcentaje de GMMs activas influye en los tiempos de ejecución de forma proporcional, como puede verse en la Figura 28. Ésta muestra el tiempo requerido para calcular las probabilidades de observación de distinto número de GMMs respecto del total en función del número de frames temporales para los que se calcula. 0 200 400 600 800 1000 0 0.5 1 1.5 2 2.5 Cálculo de las probabilidades de observación Número de frames Tiempo (s) Prototipo 25% Prototipo 50% Prototipo 75% Prototipo 100% Figura 28: Impacto del número de frames 42 conceptos básicos de cuda Year MIPS/CPU clock speed 1980 1985 1990 1995 2000 2005 2010 1 10 100 1000 Figura 32: Evolución de la frecuencia de reloj En contraposición, en la programación en paralelo se busca dividir las tareas a ejecutar en problemas independientes para poder resolverlos en varios procesos que se ejecutan a la vez. Aunque el paralelismo no es un concepto nuevo en la informática, los esfuerzos en avanzar en este modelo de programación se han aumentado en los últimos años con el objetivo de seguir consiguiendo mejoras en el rendimiento. Hay varios niveles donde puede explotarse el paralelismo, desde los bits (una ALU capaz de hacer sumas de 16 bits acabará antes determinadas tareas que una que solamente procese 8bits) o las instrucciones (segmentación de instrucciones en los microprocesadores) hasta llegar a otras soluciones como los procesadores multinúcleo, los clústers o los grids. El enfoque empleado por este proyecto ha sido el empleo de GPUs (Graphic Processing Units) consistentes en una serie de procesadores, lentos en comparación con una CPU, capaces de ejecutar el mismo código a la vez (ver Figura 33). Estas tarjetas surgieron con el propósito de optimizar el procesamiento digital de imágenes, en el cual la mayoría de las tareas tratan cada píxel de forma independiente. Debido a que las GPUs comenzaron a usarse para aplicaciones distintas de aquellas para las que se habían concebido, se crearon entornos de desarrollo como CUDA, los cuales permiten acceder a la memoria y al conjunto de instrucciones de las GPUs mediante extensiones de lenguajes de programación estándar como C, C++ o Fortran. A.2 introducción a cuda c 43 Figura 33: Arquitectura de una CPU y de una GPU En este proyecto se utiliza la extensión CUDA C/C++ para el desarrollo de las funciones en paralelo del reconocedor. a.2 introducción a cuda c Las aplicaciones desarrolladas en CUDA C están basadas en un modelo de programación host+device heterogéneo donde en un único programa las partes en serie se ejecutan en el host o CPU mientras que las partes en paralelo lo hacen en el device o GPU. A la GPU se accede mediante funciones o kernels cuya llamada crea un conjunto de hilos paralelos que ejecutan el código de la función. El conjunto de los hilos que se crean para ejecutar el kernel, llamado grid, se divide a su vez en bloques de hilos, todos del mismo tamaño (ver Figura 34). Tanto un grid como sus bloques pueden distribuirse en hasta 3 dimensiones, lo cual simplifica el direccionamiento de memoria en ciertas aplicaciones como el procesamiento digital de imágenes. Figura 34: Ejemplo de grid y bloque en un kernel Los tamaños de grid y bloque se definen antes de llamar a la función. Así, una llamada a un kernel quedaría de la siguiente manera: // Código en host ... // Llamada al kernel dim3 blockDim(bx,by, 1); dim3 gridDim(gx,gy, 1); 44 conceptos básicos de cuda kernel<<< gridDim,blockDim>>>(args); // Código en el host ... Listing 5: Número de estados a recuperar Cada hilo tiene unos índices mediante los cuales se puede conocer a qué bloque pertenece y qué posición dentro del mismo ocupa, lo cual sirve para calcular posiciones de memoria o gestionar diversas operaciones de control. int ix =blockIdx.x*blockDim.x+threadIdx.x; int iy =blockIdx.y*blockDim.y+threadIdx.y; Listing 6: Número de estados a recuperar Dentro de un bloque, los hilos pueden cooperar mediante el uso de memoria compartida o instrucciones de sincronización (ningún hilo dentro del bloque avanza hasta que todos hayan ejecutado dicha instrucción). a.3 ejemplo:suma de vectores Las operaciones matriciales tales como sumas o productos, donde el cada elemento del resultado es independiente del resto, suelen producir grandes mejoras en los tiempos de ejecución al implementarse como funciones en la GPU. El siguiente código muestra un kernel que toma sendos elementos de dos vectores, los suma y guarda el resultado en la misma posición de un tercer vector. __global__ void add(int *a,int *b,int *c) { int tid =blockIdx.x;// sumar los elementos en esta posición 3if (tid <N) c[tid]=a[tid]+b[tid]; } Listing 7: Número de estados a recuperar Este kernel es ejecutado cuando es llamado por una aplicación, la cual le pasa los argumentos a,bycy define las dimensiones de grid y de bloque. Los kernels pueden recibir argumentos por valor y por referencia, pero los argumentos por referencia tienen que ser direcciones de la memoria device. De esta forma, al principio del siguiente código se reserva memoria en la GPU para los vectores y se les da valor copiándolos desde la CPU. #define N 10 int main(void ) { int a[N], b[N], c[N]; // vectores en CPU int *dev_a,*dev_b,*dev_c;// vectores en GPU 5 A.3 ejemplo:suma de vectores 45 // reservar memoria en GPU cudaMalloc( (void**)&dev_a,N*sizeof(int) ); cudaMalloc( (void**)&dev_b,N*sizeof(int) ); cudaMalloc( (void**)&dev_c,N*sizeof(int) ); 10 // rellenar los vectores "a" y "b" en la CPU for (int i=0; i<N;i++) { a[i]=-i; b[i]=i*i; 15 } // copiar los operandos a la GPU cudaMemcpy(dev_a,a,N*sizeof(int), cudaMemcpyHostToDevice ); cudaMemcpy(dev_b,b,N*sizeof(int), cudaMemcpyHostToDevice ); 20 // sumar los operandos en GPU add<<<N,1>>>( dev_a,dev_b,dev_c); // copiar el resultado de GPU a CPU 25 HANDLE_ERROR(cudaMemcpy(c,dev_c,N*sizeof(int), cudaMemcpyDeviceToHost ) ); // mostrar los resultados for (int i=0; i<N;i++) { printf(" %d + %d = %d\n",a[i], b[i], c[i] ); } 30 // liberar la memoria reservada en GPU cudaFree(dev_a); cudaFree(dev_b); cudaFree(dev_c); 35 return 0; } Listing 8: Número de estados a recuperar B CÁLCULO DE LAS PROBABILIDADES DE OBSERVACIÓN b.1 introducción El proceso de reconocimiento se va realizando a medida que llegan nuevos datos de entrada al sistema. Éstos son vectores multidimensionales, resultado del proceso de características de un frame temporal de una señal de audio. A la secuencia de observaciones en el proceso de reconocimiento se la denomina con el nombre de O: O={o1,...,ot,...,oT}(13) El modelo acústico tiene un conjunto de posibles estados o unidades sonoras básicas, S, cada uno con una distribución estadística. S={s1,...,sj,sN}(14) Estos parámetros estadísticos permiten determinar la verosimilitud bj(ot) = P(ot|sj), es decir, que una observación se corresponda con un estado. En general en RAH se utilizan modelos de mezcla de Gaussianas o GMMs, cuyas funciones de densidad de probabilidad son sumas ponderadas de las de varias distribuciones normales. Así, la probabilidad de observación del vector otpara el estado sjquedaría: bj(ot) = C X c=1 wj,cN(ot;µj,c,Σj,c), (15) donde Ces el número de Gaussianas en la mezcla, wj,ces el peso de la Gaussiana cyµj,c,Σj,cson la media y la covarianza de la Gaussiana, respectivamente, y Nes la probabilidad de observación para una distribución normal. Para un vector de observación de D dimensiones, ésta se calcula habitualmente de la siguiente manera: N(x;µ,Σ) = 1 (2π)D/2 |Σ|1/2 e−1 2(x−µ)0Σ−1(x−µ)(16) b.2 expresión del cálculo como producto matricial En este proyecto, como ocurre habitualmente en RAH, se utilizan matrices de covarianza diagonales, lo cual permite expresar el exponente de la ecuación (16) como: 1 2 D X i=1 (xi−µi)2 σi = D X i=1 aix2 i+bixi+ci, (17) 47 48 cálculo de las probabilidades de observación lo cual es un producto escalar entre dos vectores, uno dependiente de la distribución y otro del vector de observaciones. ha b ci·     x2 x 1     =g·χ(18) Subiendo al exponente el peso de la Gaussiana en la mezcla y la parte lineal de (16) es posible calcular de esta manera, en escala logarítmica, cada uno de los elementos a sumar en (15). Apilando los coeficientes de las distintas Gaussianas en una matriz, pueden obtenerse todos estos elementos en una multiplicación matriz-vector Gχ=        g1 g2 . . . gC        ·     x2 x 1     =v(19) La suma de las exponenciales de cada uno de los elementos vcdel vector ves equivalente al resultado de (15). C X c=1 evc=b(x)(20) También es posible apilar las Gaussianas de más de una GMM para, posteriormente, elevar y sumar distintas partes del vector resultante para obtener las probabilidades de observación de distintos estados. Esta transformación, además de representar una reducción en el coste computacional del cálculo de las probabilidades de observación, lo expresa como una operación fundamentalmente matricial, lo cual abre la puerta a una posible ganancia todavía mayor mediante el uso de algoritmos paralelos. C ALGORITMO DE RECONOCIMIENTO El presente apéndice detalla el algoritmo de reconocimiento empleado en este proyecto, sin entrar en los detalles de su implementación ni en los del cálculo de las probabilidades de observación, ya detallados en el Apéndice B. c.1 consideraciones previas Generalmente, el algoritmo de reconocimiento de un RAH está basado en bucles iterativos. Como paso previo al planteamiento de la paralelización del algoritmo, éste se escribió en forma matricial en código Matlab, el cual es más sencillo de implementar que C y tiene múltiples opciones para representar los resultados gráficamente. Todos los cálculos del algoritmo están en escala logarítmica, ya que se trabaja con probabilidades muy pequeñas que podrían salirse de rango en escala lineal. Aunque las matrices y los vectores con los que se trabaja en la implementación son de tipo sparse (donde únicamente se guardan los índices y los valores de los elementos no nulos), aquí no se entrará en tales detalles de implementación. Los datos de entrada al algoritmo son los siguientes: X={X0,...,Xt,...,XT}: vectores D-dimensionales con las observaciones en cada frame temporal. A={αi,j}: probabilidades de transición, en escala logarítmica, entre cada pareja de estados, con 1⩽i⩽Ny1⩽j⩽N, de forma que, en un instante t,αi,j=log(P(st=si|st−1=sj)). Π={πi}: vector de N elementos con la probabilidad inicial de cada estado, con πi=log(P(s1=si)) G: conjunto de parámetros que define el modelo estadístico de cada estado, como la correspondencia entre un estado y una GMM o los parámetros de ésta. La función encargada de calcular las probabilidades de observación recibirá Gjunto con la observación en ese frame y los estados a calcular. Ω={ωi}: tabla que, para cada estado si, indica la cadena de caracteres que debe sacar en el proceso de backtracking o recuperación del camino correspondiente con la hipótesis final. Debido a la organización del vocabulario en forma de árbol para acelerar la búsqueda, el estado final de cada palabra es el que lleva asociada la cadena correspondiente a ésta. 49 50 algoritmo de reconocimiento Por otra parte, se define el beam como un parámetro del algoritmo. Éste indica el ratio entre dos verosimilitudes a partir del cual puede considerarse una despreciable frente a la otra. c.2 algoritmo c.2.1Inicialización El algoritmo comienza definiendo la matriz Φdonde se guardarán los caminos a medida que vayan recibiéndose observaciones, tras lo cual inicializa el vector de tokens con las probabilidades iniciales Π. Éste es un vector de Nelementos en los cuales se guarda la probabilidad acumulada, normalizada al máximo, del token en ese estado. En el caso de que no haya un token activo en ese estado se guarda −∞. La verosimilitud de los estados iniciales se pondera con las probabilidades de observación del primer vector de entrada X0. 1Φ=zeros (N,T); 2tok = Π;/*Inicialización de los tokens */ 3active = find (tok >−∞); 4b=eval_st (X0, active, G); /*Cálculo de p. obs. */ 5tok(active) = tok(active) + b; 6B = repmat (tok, 1,N); Algoritmo 5:Inicialización La función eval_st toma como argumentos las observaciones de ese instante X0, el modelo probabilístico Gy los índices de los tokens activos, y devuelve las probabilidades de observación para sus estados. La última línea expande el vector de tokens en una matriz, necesaria para el paso de propagación. Cada fila contiene el mismo elemento en todas sus columnas: la probabilidad acumulada del token en ese estado o, en su defecto, −∞(ver Figura 35). Figura 35: Líneas 11 y12 en el Algoritmo 5 C.2 algoritmo 51 c.2.2Bucle de reconocimiento La siguiente parte del reconocedor se repite en bucle mientras hay nuevas observaciones de entrada. En una aplicación real, el bucle de reconocimiento es una función llamada desde otro programa, pero aquí se asume que el número de observaciones Tes conocida de antemano. 1for t=1:T−1do 2B=B+A; /*Paso de propagación */ 3[tok, i_max] = max (B, [], 1)’; /*Purga */ 4max_tok = max (tok); 5tok(tok <max_tok - beam) = −∞;/*Beam Search */ 6tok = tok - max_tok; /*Normalización */ 7active = find (tok >−∞); 8Φ(active, t−1) = i_max(active); /*Actualización de Φ*/ 9b=eval_st (Xt, active, G); /*Cálculo de p. obs. */ 10 tok(active) = tok(active) + b; /*Actualización de tok */ 11 B = repmat (tok, 1,N); Algoritmo 6:Bucle de reconocimiento Tras el paso de propagación, la matriz B tiene, en cada elemento (i,j)distinto de −∞, la probabilidad acumulada del token que se ha propagado desde el estado sihasta el sj(Figura 36). Figura 36: Líneas 2y3en el Algoritmo 6 Posteriormente, se efectúa el paso de purga tomando el token con máxima probabilidad acumulada que ha llegado a un estado. La misma operación max, que recoge los máximos de cada columna de B en el vector tok, guarda en otro vector la filas o estados de los que provienen. Tras este paso se eliminan las hipótesis despreciables y 58 estructuras de datos P, de dimensiones maxT×maxTok. La fila de cada elemento en esta matriz indica el frame temporal, la columna indica el estado en el que se encuentra el token en ese momento y el valor, el estado desde el que se ha propagado. Las variables tIni ytFin, inicializadas a 0, son punteros a la posición inicial y final del buffer en un determinado momento. Con cada nuevo dato de entrada, tFin se incrementa (si llega al tamaño máximo de P, se pone a cero). Cuando se sacan resultados parciales, se actualiza tIni hasta la posición del último frame reconocido. Si tFin alcanza a tIni quiere decir que el buffer se ha llenado, en cuyo caso se llama a la función de backtracking, que busca la secuencia más probable hasta ese momento, tras lo cual puede vaciarse el buffer poniendo ambas variables a cero de nuevo. Figura 42: Estructura Phi Gauss: Parámetros estadísticos de los distintos estados, formados por nmezclas de Gaussianas apiladas en una matriz de tot×cols elementos (Gaussianas en total por parámetros de cada una). las tablas q2s eini indican la correspondencia entre cada estado y su mezcla de Gaussianas (algunos estados comparten GMM) y la Gaussiana inicial de cada mezcla, mientras que fetch guarda durante los cálculos la posición de la probabilidad de observación de cada token dentro del vector pExp. En xse almacenan las distintas observaciones y gMask es una máscara que indica qué Gaussianas van a emplearse en ese frame. Los resultados finales se guardan en pObs. Figura 43: Estructura Gauss BIBLIOGRAFÍA [1] A. P. Dempster, N. M. Laird, and D. B. Rubin. Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society,39(1):1–21,1977. [2] P. Dixon and S. Furui. Introduction to the use of WFSTs in speech and language processing. In APSIPA Conference,2009. [3] X. Huang, A. Acero, and H.-W. Hon. Spoken Language Processing: A Guide to Theory, Algorithm, and System Development. Prentice Hall PTR, Upper Saddle River, NJ, USA, 2001. [4] Stephan Kanthak, Hermann Ney, Michael Riley, and Mehryar Mohri. A comparison of two LVR search optimization techniques. In INTERSPEECH,2002. [5] L. R. Rabiner. A Tutorial on HMM and selected Applications in Speech Recognition, chapter 6.1, pages 267–295. Morgan Kaufmann, 1988. [6] S. Young, G. Evermann, D. Kershaw, G. Moore, J. Odell, D. Ollason, D. Povey, V. Valtchev, and P. Woodland. Htkbook (v3.3). Technical report, Cambridge University Engineering Department, 2005. 59