Содержание к диссертации
Введение
Глава I. АНАЛИЗ ОСНОВНЫХ ВАРИАНТОВ АЛГОРИТМА КОЛИЧЕСТВЕННОГО СРАВНЕНИЯ ОБРАЗОВ СЛОВ 13
1.1. Анализ проблем, решаемых при создании систем распознавания речи с обучением под конкретного диктора 13
1.2. Форяальное описание исходных данных и условий решения задачи количественного сравнения образов слов 22
1.3. Анализ преимуществ применения методов динамического программирования для количественного сравнения образов слов с нелинейной деформацией их по времени 27
Глава 2. ЭКСПЕРИМЕНТАЛЬНЫЙ МЕТОД ОПРЕДЕЛЕНИЯ НАДЕЖНОСТИ РАСПОЗНАВАНИЯ УСТРОЙСТВ РЕЧЕВОГО ВВОДА 36
2.1. Условия проведения эксперимента 36
2.2. Методика определения надежности распознавания для устройств ввода раздельно произнесенных слов 40
2.3. Методика определения надежности распознавания для устройств ввода слитно произнесенных слово сочетаний 44
Глава 3. ЭКСПЕРИМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ ВАРИАНТОВ АЛГОРИТМА ДИНАМИЧЕСКОГО ПРОШММИРОВАНИЯ ДЛЯ РАСПОЗНАВАНИЯ РАЗДЕЛЕНО И СЛИТНО ПР0ИЗН0СШЫХ СЛОВ 50
3.1. Выбор множества вариантов алгоритма определения меры сходства образов слов для их экспериментального исследования 50
3.2. Условия и результаты экспериментов по определению надежности распознавания раздельно произнесенных слов с использованием различных вариантов алгоритма динамического программирования 57
3.3. Анализ различных алгоритмов распознавания слитно произнесенных слов 75
Глава 4. ОБЩАЯ ПОСТАНОВКА ЗАДАЧИ ОПТИМИЗАЦИИ СТРУКТУРЫ МУЛЬТИБЛОЧНОЙ СИСТЕМЫ, ЕШОЛНЯНЦЕЙ ЦИКЛИЧЕСКИЙ ВЫЧИСЛИТЕЛЬНЫЙ ПРОЦЕСС 89
4.1. Формализованное описание исходных данных для построения мультиблочной вычислительной системы. Критерии и ограничения 89
4.2. Представление циклического вычислительного процесса в виде направленного графа 92
4.3. Сведение задачи оптимизации структуры вычислительной системы к задаче целочисленного программирования ЮЗ
4.4. Оптимизация вычислительных систем с применением универсальных блоков 107
Глава 5. ОПТИМИЗАЦИЯ СТРУКТУРЫ СПЕЦИАЛИЗИРОВАННОЙ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЫ ОПРЕЩЕЛЕНИЯ МЕРЫ СХОДСТВА ОБРАЗОВ СЛОВ 113
5.1. Постановка задачи. Исходные данные ИЗ
5.2. Составление условий задачи целочисленного программирования 123
5.3.Определение раннего и позднего времени выполнения операций вычислительного процесса. 128
5.4.Блок-схема вычислительной системы определения меры сходства образов слов. Вытекающая из решения оптими зационной задачи 131
ЗАКЛЮЧЕНИЕ 138
СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ 139
ПРИЛОЖЕНИЕ.ДОКУМЕНТЫ О ВНЕДРЕНИИ ПОЛУЧЕННЫХ НАУЧНЫХ
РЕЗУЛЬТАТОВ 148
- Анализ проблем, решаемых при создании систем распознавания речи с обучением под конкретного диктора
- Методика определения надежности распознавания для устройств ввода раздельно произнесенных слов
- Выбор множества вариантов алгоритма определения меры сходства образов слов для их экспериментального исследования
- Формализованное описание исходных данных для построения мультиблочной вычислительной системы. Критерии и ограничения
- Составление условий задачи целочисленного программирования
Введение к работе
Одной из основных задач современности является повышение производительности труда на базе ускорения научно-технического прогресса.
Совершенствование человеко-машинного общения возможно за счет применения естественных для человека каналов информации, к числу которых относится речевое общение. Рядом авторов [9, 56, 13, 79, 46, 30, 48] доказана принципиальная возможность решения ограниченных задач распознавания речи, таких, как ввод раздельно произнесенных слов или ввод нескольких слитно произнесенных словосочетаний.
Широко известны работы советских ученых Винцюка Т.К. [9, 8, II, I0J, Загоруйко Н.Г. [25], Книппера А.В. [26], Рамишви-ли Г.С. |44], Слуцкера Г.С. [5l]t Трунина-Донского В.Н. [14, 13, 42], Фролова Г.Д. [бб], Цемеля Г.И. [56, 27] и других, посвященные вопросам распознавания речи. Значительные успехи в этом вопросе достигнуты иностранными учеными Елинеком [2Ї], Итакурой Ф. [бб], Като Я. [25], Маркиным [30] , Редди [48], Фланаганом Дне. [54] и другими. Достаточно широкий анализ проблем и описание зарубежных разработок в области речевого ввода даны в [Зі].
Имеются сообщения о коммерческом выпуске систем ввода ограниченного числа устных команд в США. [35, 61, S2t J"J, 77, 78, 49] и Японии [50, 5з]. В 1983 году начат серийный выпуск отечественного устройства распознавания слов "ИКАР" [I], Устройства речевого ввода находят широкое применение: для ввода инструкций при работе с графическими дисплеями [76J, для ввода картографических и гидрографических данных [67], при сортиров- ке различного рода материалов [30], для программирования станков с цифровым программным управлением [70, 82], для контроля качества с одновременным вводом информации о проверяемом изделии [ЗО], для непосредственного ввода и коррекции программ, написанных на алгоритмических языках [30], для ввода данных при складировании материалов [52], в военном деле [60] и в других областях.
Однако, несмотря на достигнутые успехи, на пути создания систем речевого ввода лежит немало нерешенных проблем, связанных, главным образом, с построением малогабаритных терминальных устройств распознавания речевых команд универсального назначения с достаточно высокой надежностью распознавания и временем реакции, составляющим доли секунды.
Многие авторы [9, 8, II, 10, 23, 25, 50, 79, SH, 65", 83] для количественного сравнения образа распознаваемой команды с образами эталонных слов успешно используют процедуру динамического программирования. Несмотря на то, что многие авторы признают преимущества пршленения динамического программирования при количественном сравнении образов слов, между концепциями иссле-дрвмямкбг научных групп, занимающихся этим вопросом, имеются различные точки зрения. Различие точек зрения заключается главным образом,в том, что исследователи, исходя из теоретических предпосылок и экспериментальных данных, отдают предпочтение различным вариантам алгоритма динамического программирования, что дает повод для сравнительного анализа имеющихся вариантов.
Поскольку создание полной модели речеобразования является на современном этапе неразрешимой задачей, то окончательное решение о преимуществе одного варианта алгоритма над другими можно сделать только опираясь на результаты экспериментов по оцен- ке надежности распознавания исследуемых вариантов. Поскольку надежность распознавания устройства речевого ввода является величиной непостоянной и зависит от множества внешних по отношению к устройству факторов, то проведение экспериментов по оценке надежности распознавания должно проводиться на строго научной основе.
Применение алгоритмов AWM/ического программирования для сравнения образов слов требует большого объема однообразных вычислений [icfj. При создании малогабаритных терминальных устройств распознавания речевых команд целесообразно применять специализированные системы (процессоры) для реализации алгоритма динамического программирования. Выбор различных вариантов технической реализации, при которых минимизируются время вычислений и объем оборудования, является серьезной оптимизационной задачей, которую необходимо решить.
Основываясь на критическом анализе уже достигнутых результатов, с учетом специфических особенностей разработки малогабаритных терминальных устройств речевого ввода, автором были сформулированы следующие конкретные задачи:
1) создать на основании исследования физических осо бенностей речеобразования обобщенную модель алгоритма срав нения речевых образов, заданных последовательностью наборов речевых признаков;
2) разработать научно обоснованную методику проведе ния экспериментов по определению достоверной надежности рас познавания устройств ввода раздельно и слитно произносимых слов;
3) синтезировать на основании результатов эксперименталь ных исследований алгоритмы сравнения речевых образов для тер минальных устройств раздельно и слитно произносимых слов; поставить и решить задачу оптимального выбора блоков мультиблочной вычислительной системы, выполняющей циклический вычислительный процесс, с учетом использования конкретной элементной базы; на основании исследований по пункту 4 синтезировать структуру блока сравнения образов слов для терминального устройства ввода речевых команд.
Диссертационная работа состоит из введения, пяти глав и заключения, в которых изложены положения, выдвигаемые для зашиты .
В первой главе рассмотрены основные задачи, которые необходимо решать при построении системы распознавания речи. Приведены примеры решения этих задач в уже имеющихся системах. Сделан вывод о том, что для построения всех систем, работающих с предварительным обучением под конкретного диктора, необходимо решать задачу сравнения образа распознаваемой команды с образами эталонных слов.
Показано, что для образов слов необходимо их нелинейное преобразование во времени. Для сокращения объема вычислений при рассмотрении всех допустимых вариантов нелинейного преобразования образов слов применим алгоритм динамического программирования.
К числу новых научных результатов следует отнести: обобщение причин, требующих нелинейной деформации образов слов при их сравнении; анализ различных концепций нелинейной деформации образов слов, приводящих к различным вариантам алгоритма динамического программирования, обобщение всех возможных вариантов алгоритмов подобного класса.
Вторая глава посвящена вопросам постановки эксперимента иЬбработки результатов эксперимента с целью оценки надежности распознавания устройств речевого ввода.
Поскольку надежность распознавания зависит не только от характеристик самого устройства, но и от множества внешних причин,необходимо четко выделять ту цель, ради достижения которой проводятся эксперименты. Автором выделено три основные цели, требующие различной постановки эксперимента.
Сделан вывод о том, что для получения достоверных результатов оценки надежности распознавания необходимо вычислять доверительный интервал оценки и приведена методика его расчета.
Для устройств распознавания слитно произнесенных слов разработан алгоритм получения словосочетаний, дающих наихудшую и наилучшую надежность распознавания. Это дает возможность оценить надежность распознавания данных устройств сверху и снизу.
К числу новых научных достижений следует отнести: анализ условий проведения эксперимента по определению надежности распознавания в зависимости от цели исследований; применение аппарата вычисления доверительных интервалов по заданной доверительной вероятности к задаче оценки надежности распознавания устройств; разработка методики вычисления оценочных границ надежности распознавания слитно произнесенных слов.
Третья: глава посвящена экспериментальному исследованию различных вариантов алгоритма динамического программирования для распознавания раздельно и слитно произнесенных слов. В ней рассмотрены уже существующие варианты алгоритма и проведен их сравнительный анализ путем проведения научных экспериментов оценки надежности распознавания по методике, разработанной во второй главе.
К числу новых научных достижений следует отнести: выбор варианта алгоритма динамического программирования для реализации его в терминальном устройстве распознавания раздельных слов; выбор граничных условий алгоритма динамического программирования; способ повышения надежности распознавания за счет нелинейного преобразования функции подобия пары векторов речевых признаков; синтез, на основании исследования результатов экспериментов, нового алгоритма распознавания слитно произнесенных слов, допускающего его реализацию при создании малогабаритного терминального устройства.
В четвертой главе ставится и решается общая задача опти-мизации мультиблочной системы, производящей циклический вычислительный процесс. Решение этой задачи необходимо для оптимизации структуры специализированной системы, вычисляющей меру сходства образоЬслов.
Предполагается, что объект оптимизации состоит из набора блоков, каждый из которых независимо от других выполняет свою вычислительную операцию. Для реализации каждого блока возможно несколько вариантов, отличающихся быстродействием и физическими характеристиками (весом, объемом,, стоимостью, надежностью и тому подобное).
Задача оптимизации состоит в подборе для каждого блока такого его варианта, чтобы при оптимальной синхронизации работы блоков были сведены к минимуму общие физические характеристики при ограничении на время выполнения одной операции вычислений. - II -
Решение данной задачи сведено к решению задачи целочисленного линейного программирования с дихотомическими переменными. Решение задачи расширено на случай применения для нескольких операций одного унифицированного блока.
В качестве нового научного результата следует признать оригинальность постановки и решения задачи оптимизации технических средств, в основу которой положена конвейерная обработка данных.
В пятой главе, разработанная в четвертой главе, оптимизационная задача применена для оптимизации структуры вычислительной системы, вычисляющей меру сходства образов слов по варианту алгоритма динамического программирования, выбранному в третьей главе. В данном случае минимизации подвергается объем оборудования, выраженный в корпусах микросхем при ограничении времени на вычисление частичных мер сходства.
К научной новизне следует отнести применение аппарата линейного программирования для синтеза структурной схемы специализированной вычислительной системы.
Основными положениями, разработанными лично автором-' в рамках данной диссертации, выносимыми для защиты, следует признать: обобщенную модель алгоритма сравнения речевых признаков; методику проведения экспериментов по определению достоверной надежности распознавания устройств ввода раздельно и слитно произносимых слов; алгоритмы сравнения речевых образов для терминальных устройств распознавания раздельно и слитно произносимых слов; метод оптимального выбора блоков мулътиблочной вычислительной системы, выполняющей циклический вычислительный процесс, позволяющий минимизировать материальные затраты при ограничении на время выполнения цикла вычислений с учетом использования конкретной элементной базы; структуру специализированного блока определения меры сходства образов плов для устройства вво^а раздельно произносимых слов.
Использование положений, выдвигаемых для защиты, позволило решить одну из задач построения малогабаритных, надежных и быстродействующих терминаяьных устройств распознавания речевых команд, представляющих практический интерес для развития вычислительной техники.
Результаты исследование были использованы в опытно-конотрук-торских работах;, в которых была произведена разработка серийно выпускаемого устройства распознавания раздельно произносимых слов "ЖАР" и устройства распознавания слитно произносимых слов ТС 6300.
Б приложении приведены документы, подтверждающие практическое внедрение полученных автором результатов. - ІЗ -
Анализ проблем, решаемых при создании систем распознавания речи с обучением под конкретного диктора
В настоящее время актуальна разработка устройств, распознающих раздельно произнесенные слова или команды, состоящие из нескольких слитно произнесенных слов, входящих в заданный словарь, с предварительным обучением системы под конкретного диктора.
Причем объем словаря обычно ограничивается одной или двумя сотнями слов [50, 73, 71, 59], но иногда достигает тысячи слов [И, 74, 84]. Обучение данных систем состоит в однократном [25] или многократном [ю] повторении диктором всех слов словаря.
Несмотря на разнообразие систем такого рода, всех их объединяет сходный принцип работы, состоящий в том, что машинный образ устной команды, которую необходимо распознать, сравнивается с эталонными образами словарных слов, полученных в процессе обучения в системах распознавания раздельно произнесенных слов и с комбинациями образов слов в случае распознавания слитно произнесенных словосочетаний.
Следует отметить, что необходимость обучения под конкретного диктора делает невозможным одновременное использование систем подобного рода несколькими дикторами без предварительной идентификации диктора. Это является существенннм ограничением по сравнению с системами, работающими без предварительного обучения под диктора, но с конкретным словарем [15, 28, 14, 50]. С другой стороны, системы с предварительным обучением под диктора допускают работу с различными словарями, соответствующими классу решаемых задач при конкретном применении устройства, поэтому данный тип систем распознавания является более универсальным.
Исходя из этих соображений, данная работа посвящена решению вопросов, связанных с разработкой алгоритмов и построением систем распознавания раздельных слов и слитно произнесенных словосочетаний из ограниченного словаря с предварительным обучением под конкретного диктора. Разработка производилась с учетом использования результатов душ построения терминальных устройств ввода речи для широкого применения. Конкретно данная работа посвящена решению вопросов, связанных с разработкой специализированной мультиблочной вычислительной системы, выполняющей функцию количественного сравнения речевых образов.
Для того, чтобы определить место и назначение данной системы в устройстве распознавания речи, рассмотрим общие этапы функционирования устройств распознавания речи с предварительным обучением под конкретного диктора, а также рассмотрим различные примеры реализации данных этапов.
Методика определения надежности распознавания для устройств ввода раздельно произнесенных слов
Если нет статистического материала о частоте произнесения каждого слова при эксплуатации устройства, то логично при проведении испытаний на надежность распознавания все словарные слова повторять одинаковое число раз. Кроме того, не следует при эксперименте повторять подряд одно и то же слово, так как в этом случае у диктора образуется стереотип произнесения, повышающий распознаваемость данного слова. Однако при эксплуатации устройства, когда ситуация многократного повторения одного и того же слова случается крайне редко, надежность распознавания, рассчитанная на основании таких экспериментов, будет завышена.
Из изложенного следует, что целесообразно за элементарный эксперимент принять распознавание всех словарных слов, произнесенных по одному разу в случайном порядке.
В работе р?] отмечается, что использование функции нормального распределения т(%) при определении доверительного интервала оправдано лишь для достаточно большого числа элементарных экспериментов (порядка 10-20). В противном случае полученный доверительный интервал не будет соответствовать действительному.
Однако для определения надежности распознавания число элементарных экспериментов может быть и меньше десяти, так как саму величину ХЇ можно представить в виде среднего арибметичес-; кого случайных величин Yi і І={ ... N » определяющих вероят случайные величины fl мжно считать независимыми, поскольку вероятность распознавания конкретного слова зависит лишь от качества его произнесения в данный момент времени независимо от того, насколько качественно будут произнесены, а следовательно, и распознаны другие слова.
Нине приведен реальный пример вычисления доверительных интервалов для определения того, какой из двух вариантов работы устройств дает большую надежность распознавания. В первом варианте мера сходства распознаваемого образца слова с каждым эталоном нормировалась на сумму длин данного образца и эталона, во втором - на максимальную из этих двух величин. В данном случае преследовалась научная цель. При каждом произнесении выдавались результаты распознавания для обоих вариантов, что позволило проводить эксперименты на одной и той же обучающей и распознающей выборке. Было проделано восемь элементарных экспериментов при объеме словаря 100 слов. Результаты экспериментов приведены в табл..
Выбор множества вариантов алгоритма определения меры сходства образов слов для их экспериментального исследования
Рассмотрим результаты теоретических и практических исследований других авторов в области разработки алгоритмов динамического программирования для определения меры сходства (различия) образов слов. Основными исследователями этого направления являются: группа под руководством Т.К.Винцюка [9, 10, II, 12], Н.Г.Загоруйко [23], Я.Като, Х.Сакое, С.Чиба и другие сотрудники фирмы NEС (Япония) [25, 50, 79], В.И .Галунов и др. авторы статьи [іб], Ф.Итакура [бб] (Япония), Г.Вайт и Р.Нили [ІЗЗ] (США) и другие.
Этими авторами были проведены исследования с различными вариантами алгоритмов динамического программирования. Все рассмотренные ими варианты подходят под обязую формулировку алгоритма определения меры сходства (различия) образов слов, описанную в 1.3. Это дает возможность охарактеризовать каждый вариант алгоритма, описав такие его параметры, как коэффициенты Л, Л, функции переходов Пі(і,р} пцііЛ), П3(і,ї) и нормирующую Функцию (1,д) . Варианты алгоритмов, предлагаемые перечисленными авторами, описаны в таблице 3.1 в терминах указанных параметров.
Отметим, что все семь вариантов алгоритмов динамического программирования, приведенных в таблице, имеют различия друг от друга. Однако. авторы каждого из перечисленных алгоритмов считают, основываясь на теоретических исследованиях или результатах экспериментов, свой вариант наиболее оптимальным. Основываясь на данных разногласиях, автор данной работы сделал вывод о необходимости проведения дополнительных исследований с целью выбора оптимального варианта алгоритма динамического программирования.
Формализованное описание исходных данных для построения мультиблочной вычислительной системы. Критерии и ограничения
После того, как теоретически обоснован, разработан в деталях и подтвержден экспериментально алгоритм нахождения меры сходства речевых образов, возникает задача построения определенной вычислительной систеглы, выполняющей данный алгоритм. Причем параметры системы должны быть оптимальны с точки зрения выбранных критериев.
Рассмотрим, какие основные параметры вычислительной системы следует рассматривать при ее создании, учитывая, что данная система должна входить в состав терминального устройства распознавания устных команд. Такими параметрами являются:
1. Материальные затраты на производство системы.
2. Объем оборудования системы.
3. Надежность Функционирования.
4. Быстродействие.
Все эти параметры тесно связаны между собой и улучшение одного из них, как правило, ведет к ухудшению других. Так, например, реализацию какой-либо вычислительной операции можно осуществить на универсальном вычислительном блоке и специализированном блоке. В первом случае выигрывается объем оборудования, а во втором - время выполнения операции. Разработка систем с использованием микросхем большей интеграции дает выигрыш в объеме оборудования и в увеличении надежности функционирования, но система может получиться дорогостоящей. Уменьшение времени срабатывания достигается за счет распараллеливания вычислительных процессов, за счет чего увеличивается объем оборудования и уменьшается надежность.
Найти компромисс между изложенными выше параметрами возможно путем выбора для каждой вычислительной операции соответствующего варианта ее реализации. Для решения данной оптимизационной задачи следует самый важный из изложенных параметров использовать как функционал, а остальные - как ограничения. Возможно также использование в качестве функционала линейной комбинации нескольких параметров с коэффициентами, определяющими их значимость .
Ниже предлагается способ оптимизации структуры вычислительной системы, выполняющей циклический вычислительный процесс, при котором время выполнения одной итерации вычислений входит в ограничения, а оптимизируется линейная комбинация остальных параметров системы. Этот случай замечателен тем, что для него задача оптимизации сводится к задаче целочисленного программирования.
Форлальная постановка задачи заключается в следующем. Задан циклический вычислительный процесс, каждая итерация которого состоит из выполнения п взаимосвязанных операций Из алгоритма вычисления известно, выполнение каких операций необходимо для начала выполнения каждой операции V/,.. . Vn.
Составление условий задачи целочисленного программирования
В конечном итоге задача состоит в минимизации функционала (5.1) при ограничениях (5.2) и (5.4). Найдем решение этой задачи. Определим сначала все значения переменных, которые не удовлетворяют ограничениям. При би = І не удовлетворяется первое условие (5.4), при (5ц = I не удовлетворяется пятое условие (5.4). Тогда из первого и второго условий (5.2) следует, что (он = I и = I. При б"і{і - І не удовлетворяется восьмое условие (5.4). Все оставшиеся значения переменных удовлетворяют всем условиям. Путем перебора определяем, что при значениях оставшихся переменных б = 0, бзг. = I» (5V/ = 0, ( = О, (ОнІ - 0» Йу = I функционал (5.1) принимает минимальное значение .
Итак, для построения данной вычислительной системы выгоднее всего применить отдельные блоки для операций Vi -/ /а, применить для операций I//5", ]/ б $ V/Тч VJLD И \/U дополнительные регистры, использовать для операции Vy/ сумматор с последовательным переносом и применить для операции Vis параллельный выбор максимума с использованием сумматоров с последовательным переносом. При этом, для реализации системы потребуется 230 корпусов микросхем, что займет при средней упаковке 24 корпуса на ТЭЗ десять ТЭЗов. Время выполнения одной итерации вычислений равно максимуму из времени выполнения всех контуров. Базовым контуром (контуром, имеющим наибольшее время выполнения) является PA Vl( , V 9 Via l/j/J . Время его выполнения, а следовательно, и время выполнения итерации вычислений равно Т = 1385 не.
