Об автоматной аппроксимации реальных языков

• Автор: Холоденко, Александр Борисович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2008
• Место защиты: Москва
• Количество страниц: 99 с. : ил.

Содержание

Введение
Глава 1. Обзор существующих языковых моделей
1.1. Важность задачи моделирования естественного языка
1.2. Типы языковых моделей
1.2.1. Дискретные языковые модели
1.2.2. Статистические языковые модели
1.3. Анализ качества языковых моделей
Глава 2. Использование дискретных моделей
2.1. Основные определения и формальная постановка задачи
2.2. Случай регулярной грамматики
2.3. Случай контекстно-свободной грамматики
2.3.1. Пример работы алгоритма
2.3.2. Случай произвольных обобщённых слов
2.4. Примеры применения алгоритмов в задачах распознавания
2.5. Задача поиска и исправления ошибок
Глава 3. Статистические языковые модели для систем распознавания русской речи
3.1. Анализ применимости существующих языковых моделей и их модификаций
3.2. Составные языковые модели
3.3. Результаты экспериментов
Глава 4. Марковские языки
4.1. Свойства введённых п-грамм

4.2. Свойства марковских языков
4.3. Число марковских языков
4.4. Достаточное условие марковости
Глава 5. Аппроксимация марковских языков
5.1. Каскадно-дефинитные языки
5.2. Моделирование марковских языков
Литература
Введение

В работе рассматриваются вопросы моделирования естественного языка в задачах, связанных с обработкой и анализом различной информации. Такие модели используются в широком классе задач, начиная от систем распознавания речи и заканчивая извлечением знаний из документов, поиском информации в сети Интернет и автоматическим переводом текстов с одного языка на другой.
Основная часть работы посвящена вопросам построения адекватных моделей, пригодных для использования в системах распознавания русской речи, а также изучению их свойств.
Для значительной части романских и германских языков, а также для ряда азиатских языков (например, китайского и японского) в настоящее время уже разработаны коммерческие системы распознавания речи. Удачной коммерческой системы для русского языка до сих пор не существует. Одной из основных причин этого является отсутствие эффективной модели для представления русского языка в системе распознавания. Поэтому любые исследования в этой области являются актуальной задачей. Кроме того, большинство работ, посвященных вопросам построения языковых моделей имеют ярко выраженную инженерную направленность. В данной работе предприня- ' та попытка не только построить работающую модель для русского языка, но и изучить математические свойства вероятностных моделей, получить новый инструментарий для их разработки и анализа.
Целью настоящей работы было разработать новую языковую модель, пригодную для использования в системе распознавания слитной речи для русского языка, а также исследовать свойства п-граммных моделей и построить новый аппарат для их изучения и использования. Основной решаемой проблемой при этом было создание адекватного формализма для 71-граммного подхода в рамках теории автоматов и теории формальных языков.

к; А.(к)
и (?’а)
гбЛГ де5г;аеЛг
Множество Бк определено корректно, так как все элементы в множестве N строго меньше к (в силу способа нумерации).
Содержательно это означает, что на первом шаге мы находимся в начальном состоянии, а дальше - мы из каждой вершины для всех доступных в ней состояний совершаем все возможные переходы, причем множество состояний для каждой вершины получается объединением множеств состояний, полученных при переходе в нее из какой-то одной.
Теперь вектор /3 можно быть определен следующим образом: Д = 1 -<=> Б{ Г) Я' Ф 0.
Дальнейший ход алгоритма полностью аналогичен рассмотренному выше случаю. Элемент матрицы кладется равным нулю (бесконечности), если не существует пути, ведущего из j-oй вершины в г-ую.
Так как из 3~ой вершины в к-ую может вести не более |Д] ребер, а число вершин, подлежащих обработке, не превосходит к, то для вычисления множества Бк необходимо произвести не более А |<2| к операций. Таким образом, для вычисления к -ой строки матрицы С необходимо затратить О (к) операций.
Следовательно, всего алгоритм требует О (в2) операций.
Замечание 2.2 Если язык, задаваемый регулярной грамматикой, конечен, то полученные оценки можно улучшить. Так, например, для построения одного разбиения в случае линейного обобщенного слова требуется 0(п) операций, где константа зависит от словаря и не зависит от анализируемого слова.