Краткиетеоретическиесведения. В системах распознавания речи, содержащих слова, распознавание требует сравнения между входным словом и различными словами в словаре

 

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

Алгоритм динамического трансформирования времени (DTW) вычисляет оптимальную последовательность трансформации (деформации) времени между двумя временными рядами. Алгоритм вычисляет оба значения деформации между двумя рядами и расстоянием между ними.

Предположим, что у нас есть две числовые последовательности (a ₁, a ₂, …, a_n) и (b₁, b ₂, …, b_m). Как видим, длина двух последовательностей может быть различной. Алгоритм начинается с расчета локальных отклонений между элементами двух последовательностей, использующих различные типы отклонений. Самый распространенный способ для вычисления отклонений является метод, рассчитывающий абсолютное отклонение между значениями двух элементов (Евклидово расстояние). В результате получаем матрицу отклонений, имеющую n строк и m столбцов общих членов:

d_ij =| a_i-b_j |, i =1,…, n, j =1,…, m

Минимальное расстояние в матрице между последовательностями определяется при помощи алгоритма динамического программирования и следующего критерия оптимизации:

a_ij = d_ij +min(a_{i -1, j -1}, a_{i -1, j} , a_{i , j -1}),

где a_ij — минимальное расстояние между последовательностями (a ₁, a ₂, …, a_n) и (b₁, b ₂, …, b_m).

Путь деформации – это минимальное расстояние в матрице между элементами а ₁₁ и a_nm, состоящими из тех a_ij элементами, которые выражают расстояние до a_nm.

Глобальные деформации состоят из двух последовательностей и определяются по следующей формуле:

,

где: w_i – элементы, которые принадлежать пути деформации; p – их количество.

Пример расчетов для двух коротких последовательностейсведен в таблицу, в которой выделена последовательность деформации.

 

Существует три условия, налагаемых на DTW алгоритм для обеспечения быстрой конвергенции:

1. Монотонность – путь никогда не возвращается, то есть: оба индекса, i и j, которые используются в последовательности, никогда не уменьшаются.

2. Непрерывность – последовательность продвигается постепенно: за один шаг индексы, i и j, увеличиваются не более чем на 1.

3. Предельность – последовательность начинается в левом нижнем углу и заканчивается в правом верхнем.

Пример DTW-алгоритмана языке программирования Java:

 

public static void dtw(double a[],double b[],double dw[][], Stack<Double> w){

// a,b - the sequences, dw - the minimal distances matrix

// w - the warping path

int n=a.length,m=b.length;

double d[][]=new double[n][m]; // the euclidian distances matrix

for(inti=0;i<n;i++)

for(int j=0;j<m;j++)d[i][j]=Math.abs(a[i]-b[j]);

// determinate of minimal distance

dw[0][0]=d[0][0];

for(inti=1;i<n;i++)dw[i][0]=d[i][0]+dw[i-1][0];

for(int j=1;j<m;j++)dw[0][j]=d[0][j]+dw[0][j-1];

for(inti=1;i<n;i++)

for(int j=1;j<m;j++)

if(dw[i-1][j-1]<=dw[i-1][j])

if(dw[i-1][j-1]<=dw[i][j-1])dw[i][j]=d[i][j]+dw[i-1][j-1];

else dw[i][j]=d[i][j]+dw[i][j-1];

else

if(dw[i-1][j]<=dw[i][j-1])dw[i][j]=d[i][j]+dw[i-1][j];

else dw[i][j]=d[i][j]+dw[i][j-1];

inti=n-1,j=m-1;

double element=dw[i][j];

// determinate of warping path

w.push(new Double(dw[i][j]));

do{

if(i>0&&j>0)

if(dw[i-1][j-1]<=dw[i-1][j])

if(dw[i-1][j-1]<=dw[i][j-1]){i--;j--;} else j--;

else

if(dw[i-1][j]<=dw[i][j-1])i--; else j--;

else if(i==0)j--; else i--;

w.push(new Double(dw[i][j]));

}

while(i!=0||j!=0);

}

 

Содержаниеотчета

Отчетдолженсодержать:

1. Постановку задачи.

2. ОценкиэффективностиработыDTW-алгоритма (% правильнораспознанныхкомандпокаждомунаборупризнаков) ввидетаблицы.

% распознавания	Номеранаборовпризнаковсогласнотабл. 1.2
р

 

3. Выводы. В выводах необходимо оценить эффективность работы распознавателя в целом, а также указать наиболее информативный набор признаков.

4. Листинг программы.

5. Приложение к отчету – файл с базой данных, содержащими обучающую выборку для DTW-алгоритма.