§ 1. Метод динамического программирования

С общими идеями динамического программирования (ДП) можно познакомиться по работам [13,30]. Здесь мы опишем его применительно к распознаванию слов по последовательности коротких отрезков речевого сигнала (сегментов), как это впервые было предложено в [134] и опробовано в [28,32].

Каждый сегмент описывается вектором своих (например, спектральных) характеристик. Через евклидово расстояние между сегментами мы можем найти меры  близости (сходства) каждого -го сегмента со всеми  остальными. Пусть одно слово состоит из  сегментов, а второе — из . Расположим последовательность сегментов первого слова по вертикали, а второго по горизонтали, как показано на рис. 41, а. Начала слов находятся в точке . Сформируем матрицу размером , элементами которой служат меры  сходства между -м сегментом первого слова и -м сегментом второго слова. Сходство между первыми сегментами равно , сходство между последними равно . Обработка этой матрицы состоит из последовательного выполнения простой базовой процедуры над каждой ее ячейкой. Поясним эту процедуру с помощью рис. 41, б.

Пусть нам известны значения некоторой функции  во всех вершинах ячейки, кроме вершины . Тогда значение функции  принимается равной максимальному значению из трех следующих величин:  и , т. е. соседу справа, соседу снизу или соседу по диагонали, но с добавкой меры сходства, записанной в этой ячейке.

Примем, что значение функции у всех самых правых и всех самых нижних вершин матрицы равно нулю, а значения  во всех других вершинах нужно найти. Три вершины из четырех известны пока только для одной ячейки — самой правой и самой нижней. В нашем примере это ячейка (4,6). При выполнении базовой процедуры мы найдем, что наибольшей из трех соседних является диагональная величина, и потому функция . Отметим этот факт пунктирной диагональю, пересекающей ячейку (4,6). Теперь появились условия для выполнения базовой процедуры для двух соседних ячеек: (3,6) и (4,5). В ходе выполнения процедуры над вершиной (4,5) обнаружим, что максимальное значение функции  имеет ее правый сосед. Присвоим ей значение  и отметим этот факт горизонтальной пунктирной линией (4,5)-(4,6). Аналогичная процедура над вершиной (2, 5) даст результат в виде  и диагональной пунктирной линии через ячейку (3,6). После этого появляется возможность обрабатывать уже три соседних ячейки. И так до последней ячейки (1,1), для которой в нашем примере получаем значение функции .

Рис. 41

Легко видеть, что это значение является суммой мер сходства из тех ячеек, которые перечеркнуты пунктирными диагоналями. Движение от конечной вершины к начальной (1,1) проходит по маршруту, обозначенному непрерывной линией. При этом движение по горизонтали и по вертикали величины  не меняет, она растет только за счет ячеек, пересекаемых по диагонали. Переход по горизонтали означает, что мы как будто игнорируем соответствующий сегмент горизонтального слова, сокращаем его длительность на этом участке. Вертикальный переход, наоборот, эквивалентен растяжению данного участка горизонтального слова. Ломаная траектория между начальной и конечной точками как бы «нанизывает на шампур самые крупные кусочки» мер сходства.

Функция  является мерой похожести двух сравниваемых слов. Чтобы мера сходства не зависела от длины слов, разделим  на число сегментов более длинного из них. В итоге нормированной мерой похожести двух слов при самом лучшем варианте нелинейной деформации оси времени считаем величину .

Описанный алгоритм требует больших затрат машинного времени: количество операций пропорционально квадрату длины слова . Если различия в темпах произнесения разных участков одного и того же слова будут не слишком большими, то линии наилучшего совмещения сегментов будут лежать в окрестностях диагонали, соединяющей вершины (1,1) и . В расчете на это объем вычислений можно сократить, не проводя их для вершин, удаленных от диагонали на расстояние, большее некоторого порога . Расстояние вершины от диагонали можно оценивать величиной . В нашем примере при  базовую процедуру можно не делать для заштрихованных ячеек. Значения  для этих вершин принимаются равными нулю. Если сравниваются слова, содержащие по 30-40 сегментов, то такой прием без заметного риска потерять оптимальное решение позволяет сократить объем вычислений примерно вдвое.

В процессе распознавания нужно сравнить распознаваемое слово со всеми эталонами, что при большом словаре может оказаться неприемлемым по времени. Для значительного сокращения времени счета можно применить комбинированный метод принятия решений [67,69], в котором сначала вычисляются приближенные меры сходства между словами, затем среди всех эталонов выбирается несколько наиболее сильных конкурентов и сравнение между ними делается описанным выше методом ДП.

В данной задаче приближенная мера сходства вычислялась следующим образом. В качестве эталонов использовалось по одной реализации на каждое распознаваемое слово. При проверке гипотезы о принадлежности контрольного слова к очередному эталонному слову совмещались их начальные сегменты и вычислялись меры сходства для нескольких первых сегментов с одинаковыми номерами. По полученным мерам сходства начальных участков отбиралось 10% наиболее правдоподобных гипотез, окончательный выбор из которых делался уже с применением ДП.