5.3.2 Estrategia de Recorte de Caminos (Beam-Search): Eficiencia

Los algoritmos de reconocimiento de habla basados en Programación Dinámica realizan una búsqueda en anchura dentro de un espacio de estados definido por :

• la gramática, al imponer el número de copias necesario de cada palabra para mantener las restricciones gramaticales
• el diccionario, dependiendo de cómo está compilado (árbol de alófonos, lineal, etc.), de si se consideran múltiples entradas para una misma palabra al incluir múltiples pronunciaciones para algunas de ellas, etc.
• los modelos HMM utilizados, en concreto de su topología, de la unidad que modelan (alófono independiente del contexto, dependiente del contexto, de dialófonos, de palabras, etc.)

Es muy importante que el espacio de estados sea el adecuado para que el algoritmo de búsqueda pueda encontrar la solución óptima según el Principio de Optimalidad de Bellman.

Una de las implementaciones del algoritmo de búsqueda para habla continua más conocidas por su eficiencia es el algoritmo de Un Paso. Es el que menos restricciones impone comparado con el algoritmo Constructor de Niveles o el de Dos Pasos, y el que menos memoria y cálculos necesita. Sin embargo, es inevitable que muchas de las operaciones que se llevan a cabo durante el proceso de búsqueda no sirvan para encontrar la solución o camino óptimo pues son operaciones realizadas en caminos muy alejados del óptimo, es decir, caminos que en su mayor parte, no aportan información al proceso de búsqueda y que acabarán desapareciendo.

Para solucionar este problema de exceso de cálculo innecesario, se incorporan estrategias o técnicas de recorte de los caminos alejados del camino óptimo, con el objetivo de optimizar el proceso de búsqueda manteniendo la posibilidad de encontrar la solución óptima en el fragmento del espacio de búsqueda que sí se procesa.

En este trabajo de tesis se ha incorporado en el algoritmo de búsqueda (Un Paso) la técnica más conocida para llevar a cabo este recorte o poda de caminos (reducción de puntos de cálculo), con el fin de evaluarla y poder obtener una salida del Módulo Acústico en casi tiempo real, ya que nos permitirá mantener el tamaño del espacio de estados activo (búsqueda) dentro de unos límites razonables. Esta técnica se conoce como: Recorte basado en un Ancho de Haz Constante.

El nombre de la misma proviene del hecho de que el proceso de búsqueda de una solución óptima supone calcular las distancias (el coste) acumuladas a lo largo de los múltiples posibles caminos que nacen en cada punto de decisión local. Todos esos caminos, que parten de cualquier punto de decisión, constituyen un haz de caminos (beam), de ahí el nombre anglosajón de la técnica Beam Search (Búsqueda en Haz). La idea básica es podar o recortar esos caminos del haz y la forma más sencilla de hacerlo es aplicar un umbral de poda o recorte a esos caminos. El umbral es un umbral de distancias, y los caminos que superen el umbral, serán recortados.

Anterior   I  Siguiente   I  Índice capítulo 5   I  Índice General