Об автоматной аппроксимации реальных языков тема автореферата и диссертации по математике, 01.01.09 ВАК РФ
|
Холоденко, Александр Борисович
АВТОР
|
||||
|
кандидата физико-математических наук
УЧЕНАЯ СТЕПЕНЬ
|
||||
|
Москва
МЕСТО ЗАЩИТЫ
|
||||
|
2008
ГОД ЗАЩИТЫ
|
|
01.01.09
КОД ВАК РФ
|
||
|
|
||||
Московский государственный университет имени М В Ломоносова
Механико-математический факультет
На правах рукописи УДК 519 766
Холоденко Александр Борисович
об автоматной аппроксимации реальных языков
01 01 09 - дискретная математика и математическая кибернетика
АВТОРЕФЕРАТ
диссертации на соискание ученой степени кандидата физико-математических наук
ии^1Ь'ЭЭ 15
МОСКВА - 2008
003169915
Работа выполнена на кафедре Математической теории интеллектуальных систем Механико-математического факультета Московского государственного университета имени М В Ломоносова
Научный руководитель
доктор физико-математических наук, профессор Бабин Дмитрий Николаевич
Официальные оппоненты
доктор физико-математических наук, профессор Чуличков Алексей Иванович, кандидат физико-математических наук доцент Карташов Сергей Иванович
Ведущая организация
Московский энергетический институт (технический университет)
Защита диссертации состоится 6 июня 2008 года в 16 часов 40 минут на заседании диссертационного совета Д 501 001 84 при Московском государственном университете им M В Ломоносова по адресу 119991, Российская Федерация, г Москва, ГСП-1, Ленинские горы, Московский государственный университет им M В Ломоносова, Механико-математический факультет, аудитория 14-08
С диссертацией можно ознакомиться в библиотеке Механико-математического факультета МГУ им M В Ломоносова (Главное здание, 14 этаж)
Автореферат разослан 6 мая 2008 года
Ученый секретарь диссертационного совета
Д 501 001 84 при МГУ
доктор физико-математических
профессор
Иванов
Общая характеристика работы
Актуальность темы
Естественный язык - это основной инструмент коммуникации людей, поэтому неудивительно, что изучается он с древнейших времен Однако с появлением и развитием вычислительной техники встала задача «обучить» компьютер естественному языку, то есть построить четкие и эффективные модели, способные решать различные задачи, требующие умения обрабатывать тексты на естественном языке
Среди современных задач, связанных с работой с текстами на естественном языке, можно выделить поиск текстовой информации в больших и сверхбольших базах данных и знаний, автоматическое рубрицирование текстов, построение интеллектуальных вопрос-ответных систем, способных, например, отвечать на наиболее типичные вопросы пользоватлей, автоматический перевод текстов с одного языка на другой, генерация текстов на заданную тему (например, всевозможных отчетов), аннотирование и реферирование текстов, распознавание речи, оптическое распознавание печатных и рукописных символов, создание человеко-машинных интерфейсов с использованием естественного языка и так далее Все эти области требуют специализированных лингвистических и математических моделей, позволяющих представлять синтаксис и семантику текста в удобном для автоматической обработке виде
Исторически, одной из первых задач, потребовавших построения довольно сложной модели естественного языка, была задача автоматического перевода, впервые сформулированная американцами А Бутом и У Уивером в 1946 году Работы над системами автоматического перевода стимулировали развитие ряда языковых моделей, которые в дальнейшем нашли свое место во многих областях вычислительной техники К примерам таких моделей можно отнести иерархию грамматик Хомского1 (в первую очередь - теорию автоматов2 и теорию контекстно-свободных грамматик3), грамматики Вудса4, вероятностные автоматы5, грамматики зависимостей6, модели «Смысл-текст»7 и многие другие Изучение подобных моделей привело к созданию
'Хомский H Синтаксические структуры // Новое в лингвистике Вып II M , 1962
2Кудрявцев В Б , Алешин С В , Подколзин А С Введение в теорию автоматов -М Наука, 1985
3Ахо А и Ульман Дж Теория синтаксического анализа, перевода и компиляции -М Мир, 1978
4 Вудс В А Сетевые грамматики для анализа естественных языков // Кибернетический сборник Новая серия Выл 13 -М Мир, 1978 С 120-158
5Бухараев РГ Основы теории вероятностных автоматов -М Наука, 1985
6Damel Sleator and Davy Temperley 1991 Parsmg English with a Link Grammar Carnegie Mellon University Computer Science technical report CMU-CS-91-196, October 1991
7Мельчук И А Опыт теории лингвистических моделей «Смысл Текст» -М Наука, 1974 /
развитой теории формальных языков, в рамках которой были сформулированы чисто математические задачи, такие как проблема принадлежности снова языку, заданному формальной грамматикой, проблема нахождения пересечения двух языков, проблема сложности описания языка и так далее Параллельно с развитием систем автоматического перевода и общения на естественном языке в начале 60-х годов двадцатого века начались исследования по созданию систем речевого общения, включающих в себя, помимо остальных блоков, также блок распознавания речи До тех пор, пока объемы словарей подобных систем не превосходили порога в несколько сотен слов, эти системы могли строиться без учета каких бы то ни было моделей языка В том случае, если система обладала большим словарем, удовлетворительной работы без учета особенностей языка добиваться уже не удавалось Это также подстегнуло исследования по моделированию естественного языка, однако в области распознавания речи наибольшее распростронение получили вероятностные языковые модели Самая простая из них - так называемая n-граммная модель8 до настоящего времени используется в большинстве современных коммерческих систем распознавания речи
Таким образом, к настоящему моменту в науке накоплено значительное количество различных подходов к формализации естественного языка, сформулированных в виде математических конструкций Значительная доля этих конструкций хорошо изучена, однако «универсальной» модели, которая могла бы очень точно аппроксимировать реальный язык и оказалась бы идеально адаптированной к различным задачам, до сих пор создать не удалось Также остается открытым вопрос о построении модели, оценивающей «естественность» текста Подобная модель нашла бы очень широкое применение в различных системах, начиная с оптимизации работы поисковых систем в сети интернет и заканчивая улучшением качества работы систем распознавания речи
Представленная работа также рассматривает вопросы моделирования естественного языка в задачах, связанных с обработкой и анализом различной информации Основная часть диссертации посвящена вопросам построения языковых моделей, предназначенных для использования в системах распознавания русской речи, а также изучению их математических свойств Для значительной части романских и германских языков, а также для ряда азиатских языков (например, китайского и японского) в настоящее время уже разработаны коммерческие системы распознавания речи Удачной коммерческой системы для русского языка до сих пор не существует Одной из основных причин этого является отсутствие эффективной модели для
8EAGLES «HANDBOOK of Standards and Resources for Spoken Language Systems», Mouton de Gruyter, 1997
представления русского языка в системе распознавания Поэтому любые исследования в этой области являются актуальными Кроме того, большинство работ, посвященных вопросам построения языковых моделей для систем распознавания речи, имеют ярко выраженную «инженерную» направленность В представленной работе предпринята попытка не только построить адекватную и практически применимую модель для русского языка, но и изучить ее математические свойства, получить новый инструментарий для разработки и анализа вероятностых языковых моделей для систем распознавания речи
Цель работы
Цели настоящей работы
• решить задачу исправления ошибок в формальных языках,
• изучить частотные свойства естественных языков,
• определить и изучить классы формальных языков, близких к естественным,
• обобщить эвристические свойства п-граммных моделей на формальные языки
Методы исследования
В диссертации использованы методы теории автоматов, теории формальных языков, комбинаторики, теории графов и математического анализа
Научная новизна и ценность работы
Работа носит теоретический характер Основные результаты диссертации являются новыми и состоят в следующем
1 Решена задача исправления ошибок в формальных языках Построен алгоритм, решающий задачу принадлежности слова формальному языку при наличии в нем ошибок разных типов Найдены полиномиальные относительно длины слова алгоритмы проверки принадлежности слова регулярному или контекстно-свободному языку при условии искажения анализируемых слов
2 п-Граммная модель успешно модернизирована для работы с русским языком
3 Введено понятие регулярных марковских языков и марковских автоматов и изучены их свойства
4 Предложен алгоритм аппроксимации марковского автомата при помощи простейших автоматов, доля которых среди всех автоматов с тем же числом состояний стремится к нулю
Указанные результаты могут быть полезны специалистам, занимающимся теорией автоматов и теорией формальных языков
Помимо чисто теоретической значимости, полученные в диссертации результаты также имеют следующие важные практические приложения, которые могут быть полезны специалистам, занимающимся работой с естественными языками
1 Введено понятие обобщенного слова как ориентированного информационного графа без (ориентированных) циклов с отметками в виде букв и весов на ребрах При потенциально экспоненциальной мощности множества слов, представляемых обобщенным словом, построены полиномиальные алгоритмы нахождения пути в обобщенных словах из регулярных (0(п2)) и контекстно-свободных языков (0(п3)), где п является длиной обобщенного слова и не зависит от используемой грамматики Данные алгоритмы находят применение в задачах коррекции результатов распознавания и в задачах проверки правописания
2 Построена вероятностная языковая модель для русского языка, пригодная к использованию в составе системы распознавания слитной речи
Апробация работы
Результаты диссертации докладывались на следующих семинарах механико-математического факультета МГУ им М В Ломоносова и научных конференциях
1 Семинар «Теория автоматов» под руководством академика, профессора, д ф-м н В Б Кудрявцева (2002 - 2008гг)
2 Семинар «Теория дискретных функций и приложения» под руковод-
ством профессора, д ф-м н Д Н Бабина (1999 - 2008 гг)
3 Международная конференция «Информационные технологии в инновационных проектах» (Ижевск, 1999)
4 Международный семинар «Диалог'99» по компьютерной лингвистике и ее приложениям (Таруса, 1999)
5 IV Всероссийская конференция «Нейрокомпьютеры и их применение» (Москва, 2000)
6 V International Congress on mathematical modeling, (Dubna, 2002)
7 IX Международный семинар «Дискретная математика и ее приложения» (Москва, 2007)
Публикации
Основное содержание диссертации опубликовано в 7 работах автора, список которых приведен в конце автореферата [1-7]
Структура и объем диссертации
Диссертация состоит из введения, пяти глав и списка литературы Текст диссертации изложен на 99 страницах Список литературы содержит 45 наименований
Содержание работы
Во введении дается общая характеристика работы, а также приводятся основные понятия и результаты, изложенные в диссертации
В первой главе приводится обзор существующих в настоящее время языковых моделей, описываются их сильные и слабые стороны, изучается их пригодность к использованию в лингвистическом обеспечении систем распознавания слитной речи В этой главе рассматриваются как дискретные, так и вероятностные подходы, демонстрируются преимущества и недостатки каждого из них
Известно, что подавляющее превосходство человека над компьютерами в точности распознавания речи в первую очередь обусловлено именно учетом человеком контекста высказывания (в том числе и смысла) и умением отличить правильно построенное предложение от неправильного Поэтому важность создания хорошей модели языка для систем распознавания речи трудно переоценить
Поскольку в задачах распознавания речи обычно приходится иметь дело не с линейной последовательностью букв в слове, а с деревом вариантов распознавания, используемые здесь модели должны обладать некоторыми особенностями А именно, они должны иметь достаточно высокую скорость работы, чтобы справляться с экспоненциальным взрывом количества вариантов распознавания, а также допускать возможность работы «слева направо», то есть позволять на ранних этапах отсекать те варинаты распознавания, которые не могут быть продолжены до правильного предложения естественного языка
В этой главе рассматриваются
• дискретные модели:
- регулярные языки,
- контекстно-свободные языки,
- системы, основанные на использовании лингвистических экспертных систем и систем понимания и учета смысла,
• вероятностные модели.
- п-граммы,
- системы, основанные на деревьях решений,
- вероятностные обобщения контекстно-свободных грамматик
Здесь показаны преимущества и недостатки каждого из этих подходов, а также приведена общепринятая на сегодняшний день оценка качества модели, так называемый коэффициент неопределенности (в англоязычной литературе испоаьзуется термин «perplexity coefficient»9) В случае п-граммных моделей, которые и будут преимущественно изучаться в дальнейшем в рамках данной работы, коэффициент неопределенности показывает среднюю степень ветвления в модели, то есть сколькими способами в среднем может быть продолжено фиксированное начало предложения
В случае невозможности или нежелательности проводить полный эксперимент с использованием системы распознавания, коэффициент неопределенности позволяет сравнивать между собой две модели, а также, в случае использования одинаковых моделей сравнивать относительную сложность языков
9L R Bahl, J К Baker, F Jelinek, and R L Mercer Perplexity - a measure of the difficulty of speech recognition tasks Program of the 94th Meeting of the Acoustical Society of America J Acoust Soc Am , vol 62 p S63, 1977 Suppl no 1
Во второй главе более подробно рассматривается вопрос использования дискретных моделей, в первую очередь - регулярных и контекстно-свободных языков Для обоих этих случаев предложены алгоритмы анализа, пригодные для работы в составе систем распознавания речи, которые характеризуются необходимостью анализа не одного, а большого множества вариантов входного слова В работе это моделируется введением т н обобщенного слова, которое представляет дерево вариантов результатов распознавания Для всех алгоритмов вычислены оценки их сложности, а также приведены примеры их использования в различных задачах
Определение. Обобщенным словом над алфавитом А назовем связный ориентированный граф без ориентированных циклов, каждому ребру которого приписана некоторая буква из алфавита А и неотрицательное вещественное число
В каждом таком графе есть источник (вершина без входящих ребер) и сток (вершина без исходящих ребер) Они называются начальной и конечной вершиной обобщенного слова соответственно Задача формулируется следующим образом
Пусть дано обобщенное слово а и некоторая грамматика Г Требуется найти в обобщенном слове путь, ведущий из начальной вершины обобщенного слова в конечную и обладающий двумя свойствами
1 слово, полученное конкатенацией букв, записанных вдоль этого пути, должно быть допустимым словом в грамматике Г,
2 сумма весов, стоящих на ребрах пути, должна быть минимальна
В работе показано, что в случае, если грамматика Г задается конечным автоматом, данная задача может быть решена за время 0(п2), где п - количество вершин в графе обобщенного слова В том случае, если грамматика Г является контекстно-свободной, то данная задача может быть решена за время 0(п3), где п - количество вершин в графе обобщенного слова
Описанные во второй главе работы алгоритмы также позволяют несколько обобщить задачу, а именно - перечислить все пути, удовлетворяющие первому условию, либо найти такой путь, который может быть представлен в виде конкатенации произвольного числа слов, допустимых в грамматике Г Кроме того, в данной главе приведены два примера применения построенной техники в задаче коррекции результатов оптического распознавания символов и в задаче поиска минимального исправления ошибочно написанного слова (так называемая задача зреНсЬескег'а)
Последняя задача решается при помощи моделирования операций пропуска, вставки и замены буквы в обобщенном слове и применения получен-
ных алгоритмов для нахождения оптимального пути, то есть пути с наименьшим суммарным штрафом
В третьей главе рассматривается статистический подход к построению языковых моделей Известно, что прямой перенос моделей, пригодных для построения систем распознавания английской речи, на случай русского распознавателя невозможен, поскольку приводит к слишком громоздким конструкциям, которые невозможно использовать в рамках существующих на сегодняшний день компьютерных технологий10 В этой главе предложен механизм адаптации стандартного n-граммного подхода, который позволяет использовать механизм n-грамм для построения русского распознавателя
В настоящее время в задачах распознавания слитной речи чаще всего используются вероятностные модели, построенные на принципе независимости от «далекой» истории, так называемые n-граммные модели
Если в общем виде вероятностная модель позволяет вычислить вероятность того, что слово а = аг1а,2 a,t является допустмым словом языка, то в n-граммной модели делается допущение о том, что
P(atJatlal2 e^J и P(a,3|o,J_n+1a,J_„+a аь_J
Это приводит к тому, что вероятность P(atla,2 аь), расписанная в виде произведения условных вероятностей
P{a4at2 ati) = Р{аг1) х P(al2\ah) х х P(as\atla,2 a^J,
может быть оценена через произведение вероятностей вида Р{аг]\аь_п+1аг^п+2 at,_i) Очевидно, что в таком случае модель сводится к конечному множеству вероятностей, каждую их которых можно оценить на этапе обучения системы, вычислив частоту встречаемости соответствующих слов в обучающей выборке
Как уже было отмечено, для моделирования русского языка такие модели подходят плохо В этой главе предложено обобщение n-граммной модели, которое позволило распространить аппарат n-граммных моделей и на русский язык Главными трудностями в русском языке на пути создания таких моделей являются большое количество словоформ (что приводит к серьезному увеличению словарей системы) и относительно свободный порядок слов Основной особенностью предложенного подхода является декомпозиция общей n-граммной модели в декартово произведение двух моделей модели, построенной на леммах слов, и модели', построенной на морфологической информации
10D Kanevsky, М Mcmkowsky, J Sedivy Large Vocabulary Speaker-Independent Continuous Speech Recognition m Russian Language Proc SPECOM'96, St -Petersburg, October 28-31, 1996
Модель, построенная на морфологических классах, содержит словарь порядка 550 «слов» и позволяет решать задачи, связанные с моделированием морфологическою строения предложения, в том числе, например, снятие омонимии В то же время модель, построенная на леммах, отвечает за представление смысловой составляющей языка и по своим качественным характеристикам примерно соответствует аналогичным моделям для английского языка Словарь системы составляет приблизительно 130 тыс лемм
Каждая из этих моделей была построена и обучена на материале российской периодики При этом было показано, что полученные характеристики языковых моделей примерно соответствуют среднестатистическим характеристикам моделей для английского языка (коэффициент неопределенности в модели, основанной на леммах, составил около 230, для моделей на английском языке этот коэффициент обычно оказывается в районе 100) Коэффициент неопределенности в категорной модели (построенной исключительно на морфологической информации) оказался около 20
Таким образом, в этой главе показано, что существующие п-граммные подходы могут быть адаптированы для работы с русским языком Поэтому исследование свойств подобных вероятностных моделей является важной задачей и с точки зрения создания полноценной системы распознавания слитной русской речи
К сожалению, несмотря на то, что, как уже было отмечено выше, наибольшее распространение в мире получили именно n-граммные модели, их формальные математические свойства исследованы довольно мало Поэтому следующие две главы посвящены более детальному анализу свойств п-грамм Для этого используется аппарат теории автоматов и регулярных языков
В четвёртой главе вводится обобщение понятия n-граммной модели на бесконечные формальные языки А именно, вводится частота встречаемости слова w на s-ом месте, а затем рассматривается предельная частота встречаемости слова w как предел при s —I оо
Более точно
Пусть 21 = (А, Q, (р, Qf,Qo) - конечный детерминированный автомат, А -входной алфавит, S - множество состояний, Qf QQ- множество финальных состояний, ip А х Q -» Q - функция переходов, q0 - начальное состояние автомата
Введем несколько важных обозначений
Через &а = {а € А*|^(</о>а) £ Qf} обозначим язык, порождаемый автоматом 2i В тех случаях, когда не возникает разночтений, индекс 21 мы будем опускать
Для натурального числа s € N обозначим через L(s) множество слов
языка L длины s
L(s) = {a € -С |a| = s}
Через 7L обозначим множество префиксов слов языка £>, включая сами слова
У£ = {ае А* |Э/3 € Л*, ар € £}, L С Э>£
Через £7 обозначим множество слов языка оканчивающихся на 7, то есть
= {а € Л* € £|3/3 € Л*,а =
Пусть |u>| = п Обозначим через lw{s) число слов языка L, имеющих с (s — п + 1)-ой по s-ую букву подслово w, то есть
Us) = |3>£ш(в)|
Введем Gw(s) - частоту встречаемости слова w на s-ом месте как
lw(s)
Gw{s) =
Е lw'(s)
|w'|=N
Через Gw = lim Gw(.s) обозначим предельную частоту встречаемости
s—>оо
слова w среди слов той же длины
Пусть w € А* - слово и а £ А - буква, \wa\ = п Введем величину rW)„(s) как
гшДз) - Us)
J2 lw'a(s) У|=И
Определение. Величину
rw,a = hm
8—>00
если она существует, назовем п-граммой языка £ для пары (ги, а)
Определение. Язык С назовем марковским языком порядка п, если существуют все п-граммы Г„,|в, где |и;а| = п и существуют все частоты где |и| = п
Множество марковских языков порядка п обозначим через Ж(п) Через М обозначим класс марковских языков, то есть языков, являющихся марковскими при любом порядке п
00
М-р) Ж(п)
п=1 10
Показано, что в классе регулярных языков существуют языки, не являющиеся марковскими, поэтому выделение и изучение подкласса марковских регулярных языков оказывается оправданным Тем не менее, число марковских регулярных языков достаточно велико Обозначим через класс марковских языков, задаваемых автоматами не более чем с N состояниями, через 3£дг обозначим класс всех регулярных языков, задаваемых автоматами не более чем с N состояниями Тогда справедлива следующая теорема
Теорема 4.4 (Оценка числа марковских языков) Для достаточно больших N
Оказывается, что классы марковских языков строго вкладываются друг в друга Это показывают Теорема 4.1 и Теорема 4.2 Теорема 4 1.
Если язык является марковским порядка п, то он также является марковский порядка к < п Теорема 4.2.
Для любого п € N существует язык такой, что £ € Мп-ъ но пРи этом
Таким образом, марковские языки образуют строго сужающуюся последовательность
С другой стороны, если язык И фиксирован, то ситуация становится обратной А именно, справедлива Теорема 4.3.
Пусть язык £< = £а задан автоматом 21 = {А, <5, <р, (¿р, <7о} Тогда из С £ М(21^) следует, что С 6 Ж
Любая п-грамма может быть вычислена по диаграмме переходов автомата, однако это требует умения находить собственные числа для матриц большой размерности
Определение. Активным графом автомата 21 назовем подмножество ребер диаграммы переходов автомата 21, которые входят хотя бы в один путь из начальной вершины в одну из финальных вершин, а также инце-дентные им вершины
Определение. Активной матрицей автомата 21 назовем матрицу ин-цедентности его активного графа (взятую с учетом кратностей ребер)
Л £ М,
■П
М(1) 3 М(2) э М{3) 3 Э М(п) Э
Справедлива следующая теорема, дающая пример достаточного условия марковости
Теорема 4.5.
Если активная матрица автомата 21 имеет единственное максимальное по модулю собственное значение, то задаваемый этим автоматом язык является марковским
Доказательство теоремы 4 5 содержит способ нахождения произвольной п-граммы для языка Л В соответствии с этой процедурой, искомая п-грамма либо будет вычислена, либо будет доказано, что такой п-граммы не существует В соответствии с Теоремой 4.4 для установления принадлежности языка £ к классу марковских языков достаточно проверить только существование п-грамм при п — |<3|, где <2 - множество состояний задающего язык £ автомата Таким образом, установление принадлежности произвольного языка £ классу марковских языков может быть получено за конечное число шагов
В пятой главе изучаются вопросы моделирования одних марковских языков другими В частности, показано, что для любого марковского языка можно построить автомат, обладающий набором биграмм, сколь угодно близким к набору биграмм исходного автомата
Показано, что класс марковских языков не замкнут относительно основных теоретико-языковых операций объединения, пересечения и дополнения, поэтому необходимо рассматривать более узкие классы языков Примером такого класса является, например, класс каскадно-дефинитных языков
Понятие дефинитных языков (то есть таких языков, функция переходов которых «забывает» далекую предысторию) является прямым переносом идеологии марковских языков непосредственно на теорию автоматов Однако это свойство оказывается слишком жестким любой дефинитный язык является марковским языком и все его п-граммы (для любого фиксированного п) равны между собой Поэтому сами по себе дефинитные языки не очень интересны в свете рассмотрения марковских языков Тем не менее, из них можно получить новый класс языков, с одной стороны небольшой (его доля среди всех языков, задаваемых автоматами с N состояниями, стремится к нулю с ростом ЛГ), а с другой стороны - в некотором смысле «всюду плотный» в множестве марковских языков
Пусть 211 = (А, <Э\ <Л Ш2 = (А, 0?, <$) Пусть также д1 £
<3* и д2 е <д2 Введем операцию склейки двух автоматов по паре состояний
(<г\<?2)
Определение. Результатом склейки автоматов 211 и 212 называется автомат
21 = {А, (З^С}^ {51}, <р, и <$Л {д1}, ?3), где
если q € Q1 \ {g1} и ^(q, а) ф q1 если q e Q1 \ {g1} и tp1 (q, a) = q1 если q = q1 если q € Q2
. v>2(q, a)
Каскадно-дефинитные языки получаются из класса дефинитных языков рекурсивно путем применения операции склейки двух автоматов по паре состояний
Оказывается, введенная таким образом операция склейки двух автоматов по паре состояний позволяет получать автоматы с заданными свойствами из набора простейших автоматов циклов и отрезков
Сформулируем сначала следующее утверждение
Утверждение. Множество {Gab} является системой биграмм для некоторого регулярного языка L тогда и только тогда, когда для любого г, 1 ^ г ^ выполнено
где Т,г - сумма по 1-ому столбцу, М, - максимум по г-ой строке в матрице переходов для автомата, задающего язык Л
Определение. Условие (1) будем называть условием биграммности множества а соответствующую ей матрицу тт будем называть
биграммной матрицей Теорема 5.1
Для всякой рациональной биграммной матрицы 7Г найдется автомат 21, матрица биграмм которого п<ц будет в точности совпадать с исходной биграммной матрицей я, и который может быть получен из «простейших» автоматов - отрезков и циклов путем применения к ним операции склейки автоматов
В том случае, если биграммная матрица автомата 21 содержит иррациональные числа, то для любого е > 0 ее можно приблизить рациональной биграммной матрицей и построить автомат, имеющий в точности заданную рациональную биграммную матрицу Это утверждение сформулировно в работе в виде теоремы 5 2 Теорема 5.2
Для любого марковского автомата 21 и любого е > 0 найдется автомат 21' такой, что р(ш, <£, и этот автомат может быть получен из «простейших» автоматов - отрезков и циклов путем применения к ним операции склейки автоматов
При этом под расстоянием между двумя матрицами мы понимаем максимум поэлементного модуля разности, то есть для двух биграммных матриц
Е, ^ М„
(1)
TT = {Gob} и тг' = {G'J
р{тг,тт') = тах\С'аЬ- СаЬ\ а,ЬеА
Таким образом, для произвольной биграммной матрицы может быть построен автомат 21', имеющий биграммную матрицу, сколь угодно близкую к данной При этом следует отметить, что Теорема 5 1 дает конструктивный способ построения такого автомата
Я выражаю глубокую и искреннюю благодарность своему научному руководителю - доктору физико-математических наук, профессору Дмитрию Николаевичу Бабину за постановку задач, постоянную поддержку и внимание к работе
Я благодарю научного сотрудника лаборатории Проблем теоретической кибернетики, кандидата физико-математических наук Ивана Леонидовича Мазуренко за ценные обсуждения
Я выражаю глубокую признательность заведующему кафедрой Математической теории интеллектуальных систем, академику, профессору Валерию Борисовичу Кудрявцеву за постоянное внимание к работе и поддержку, а также всем сотрудникам кафедры Математической теории интеллектуальных систем и лаборатории Проблем теоретической кибернетики за творческую атмосферу, способствующую научной работе
Публикации автора по теме диссертации
1 Холоденко А.Б. Использование лексических и синтаксических анализаторов в задачах распознавания для естественных языков // Интеллектуальные системы Т 4, вып 1-2, 1999, с 185-193
2 Холоденко А.Б. О построении статистических языковых моделей для систем распознавания русской речи // Интеллектуальные системы Т 6, вып 1-4, 2002, с 381-394
3 Холоденко А.Б. О марковских регулярных языках //Материалы IX Международного семинара "Дискретная математика и ее приложения", 1823 июня 2007 года -М , Изд-во механико-математического факультета МГУ, 2007 с 358-361
4 Холоденко А.Б. О языковых моделях для систем распознавания русской речи // Интеллектуальные системы в производстве Периодический научно-практический журнал - 2003 - №1 -Ижевск Изд-во ИжГТУ, 2003 с 146-155
5 Холоденко А Б Лексический анализатор в распознавании последовательных образов // Информационные технологии в инновационных проектах Материалы докладов Международная конференция, 20-22 апреля 1999 г -Ижевск ИжГТУ, 1999, с 43-44
6 Холоденко А.Б. Исправление ошибок в формальных языках // Нейрокомпьютеры и их применение Сборник докладов IV Всероссийская конференция, Москва 16-18 февраля 2000 г -М Издательское предприятие редакции журнала "Радиотехника", 2000, с 627-630
7 Kholodenko А То the creating of the language models for Russian / / V International Congress on mathematical modeling September 30 - October 6, 2002, Dubna, Moscow Region Book of abstracts, V 2, -M "Janus-K", 2002, p 97
Подписано в печать 29 04 2008 г Печать трафаретная
Заказ № 358 Тираж 100 экз
Типография «11-й ФОРМАТ» ИНН 7726330900 115230, Москва, Варшавское ш, 36 (495) 975-78-56, (499) 788-78-56 www autoreferat ru
Введение
Глава 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. Моделирование марковских языков.
В работе рассматриваются вопросы моделирования естественного языка в задачах, связанных с обработкой и анализом различной информации. Такие модели используются в широком классе задач, начиная от систем распознавания речи и заканчивая извлечением знаний из документов, поиском информации в сети Интернет и автоматическим переводом текстов с одного языка на другой.
Основная часть работы посвящена вопросам построения адекватных моделей, пригодных для использования в системах распознавания русской речи, а также изучению их свойств.
Для значительной части романских и германских языков, а также для ряда азиатских языков (например, китайского и японского) в настоящее время уже разработаны коммерческие системы распознавания речи. Удачной коммерческой системы для русского языка до сих пор не существует. Одной из основных причин этого является отсутствие эффективной модели для представления русского языка в системе распознавания. Поэтому любые исследования в этой области являются актуальной задачей. Кроме того, большинство работ, посвященных вопросам построения языковых моделей имеют ярко выраженную инженерную направленность. В данной работе предприня- ^ та попытка не только построить работающую модель для русского языка, но и изучить математические свойства вероятностных моделей, получить новый инструментарий для их разработки и анализа.
Целью настоящей работы было разработать новую языковую модель, пригодную для использования в системе распознавания слитной речи для русского языка, а также исследовать свойства п-граммных моделей и построить новый аппарат для их изучения и использования. Основной решаемой проблемой при этом было создание адекватного формализма для п-граммного подхода в рамках теории автоматов и теории формальных языков.
Предметом исследования является формализованная модель естественного языка и её основные свойства.
В работе сравниваются различные подходы к задаче моделирования естественного языка - дискретные и вероятнстные, для каждого подхода предлагаются новые алгоритмы, описывается, в каких случаях лучше применять тот или иной подход.
Работа состоит из пяти глав, введения и списка литературы.
В первой главе приводится анализ существующих методов моделирования естественного языка, пригодных к использованию в задачах, связанных с распознаванием слитной речи.
Известно, что подавляющее превосходство человека над компьютерами в точности распознавания речи, в первую очередь обусловлено именно учётом человеком контекста высказывания (в том числе и смысла) и умением отличить правильно построенное предложение от неправильного. Поэтому важность создания хорошей модели языка для систем распознавания речи трудно переоценить.
Поскольку в задачах распознавания речи обычно приходится иметь дело не с линейной последовательностью букв в слове, а с деревом вариантов распознавания, используемые здесь модели должны обладать некоторыми особенностями. А именно, они должны иметь достаточно высокую скорость работы, чтобы справляться с экспоненциальным взрывом количества вариантов распознавания, а также допускать возможность работы «слева направо», то есть позволять на ранних этапах отсекать те варинаты распознавания, которые не могут быть продолжены до правильного предложения естественного языка.
В этой главе рассматриваются:
• дискретные модели: регулярные языки; контекстно-свободные языки; t системы, основанные на использовании лингвистических экспертных систем и систем понимания и учёта смысла;
• вероятностные модели: п-граммы; системы, основанные на деревьях решений; вероятностные обобщения контекстно-свободных грамматик.
Здесь показаны преимущества и недостатки каждого из этих подходов, а также приведена общепринятая на сегодняшний день оценка качества модели, так называемый коэффициент неопределённости (perplexity coefficient).
В случае невозможности или нежелательности проводить полный эксперимент с использоваием системы распознавания, коэффициент неопределённости позволяет сравнивать между собой две модели, а также, в случае использования одинаковых моделей, сравнивать относительную сложность языков.
Во второй главе рассмотрен подход, основанный на использовании дискретных моделей, а именно - регулярных и контекстно-свободных языков.
Пусть дан ориентированный граф без ориентированных циклов, рёбрам которого приписаны буквы алфавита и веса (штрафы). Такой объект в работе назван обобщённым словом. Он примерно соответствует понятию lattice в англоязычной литературе. В каждом таком графе есть источник (вершина без входящих рёбер) и сток (вершина без выходящих рёбер). Они называются начальной и конечной вершиной обобщенного слова соответственно.
Задача формулируется следующим образом.
Пусть дано обобщённое слово а и некоторая грамматика Г. Требуется найти в обобщённом слове путь, ведущий из начальной вершины в конечную и обладающий двумя свойствами:
1. слово, полученной конкатенацией букв, записанных вдоль этого пути должно быть допустимым словом в грамматике Г;
2. сумма весов, стоящих на рёбрах пути должна быть минимальна.
В работе показано, что в случае, если грамматика Г задаётся конечным автоматом, то данная задача может быть решена за время 0(п2), где п - количество вершин в графе обобщённого слова. В том случае, если грамматика Г является контекстно-свободной, то данная задача может быть решена за время 0(п3), где п - количество вершин в графе обобщённого слова.
Описанные во второй главе работы алгоритмы также позволяют несколько обобщить задачу, а именно - перечислить все пути, удовлетворяющие первому условию, либо найти такой путь, который может быть представлен в виде конкатенации произвольного числа слов, допустимых в грамматике Г.
Кроме того, в данной главе приведены также два примера применения построенной техники: в задаче коррекции результатов оптического распознавания символов и в задаче поиска минимального исправления ошибочно написанного слова (так называемая задача зреПсЬескег'а).
В третьей главе рассматриваются вероятностью модели для систем распознавания русской речи.
В настоящее время в задачах распознавания слитной речи чаще всего используются вероятностные модели, построенные на принципе независимости от «далёкой» истории, так называемые п-граммные модели.
Р(афг1щ2. (ц.г) ъ Р(аф{.п+1а{.п+7 . а£.1).
Известно, что для моделирования русского языка такие модели подходят плохо. В этой главе предложено простое обобщение п-граммной модели, которое позволило построить работающую вероятностную модель и для русского языка тоже. Главными трудностями в русском языке на пути создания таких моделей являются большое количество словоформ (что приводит к серьёзному увеличению словарей системы) и относительно свободный порядок слов. Основной особенностью предложенного подхода является декомпозиция общей п-граммной модели в декартово произведение двух моделей: модели, построенной на леммах слов и модели, построенной на морфологической информации.
Каждая из этих моделей была построена и обучена на материале российской периодики. При этом было показано, что полученные характеристики языковых моделей примерно соответствуют среднестатистическим характеристикам моделей для английского языка (коэффициент неопределённости в модели, основанной на леммах, составил около 230; для моделей па английском языке этот коэффициент обычно оказывается в районе 100). Коэффициент неопределённости в категорной модели (построенной исключительно па морфологической информации) оказался около 20.
Таким образом, в этой главе показано, что существующие п-граммные подходы могут быть адаптированы для работы с русским языком. Поэтому исследование свойств подобных вероятностных моделей является важной задачей и с точки зрения создания полноценной системы распознавания слитной русской речи.
К сожалению, несмотря на то, что, как уже было отмечено выше, наибольшее распространение в мире получили именно п-граммные модели, их формальные математические свойства исследованы довольно мало. Поэтому следующие две главы посвящены более детальному анализу свойств п-грамм. Для этого используется аппарат теории автоматов и регулярных языков.
В четвёртой главе вводится обобщение понятия п-граммной модели на бесконечные формальные языки. А именно, вводится частота встречаемости слова т на я-ом месте, а затем рассматривается предельная частота встречаемости слова и) как предел при 5 —оо. Аналогичным образом вводится понятие п-граммы. Если в языке £ существуют все п-граммы для некоторого фиксированного числа п, то такой язык в работе называется марковским языком порядка п. В том случае, если в языке существуют все п-граммы для всех натуральных чисел п, то этот язык называется марковским языком.
Показано, что даже в классе регулярных языков существуют языки, не являющиеся марковскими. Тем не менее, число марковских регулярных языков достаточно велико. А именно, как доказано в Теореме 4.4, отношение количества марковских языков, задаваемых автоматами с N состояниями, к общему количеству регулярных языков, задаваемых автоматами с N состояниями, для достаточно больших N не меньше, чем (1 —
Оказывается, что классы марковских языков строго вкладываются друг в друга. А именно, как доказано в Теореме 4.2, из того, что язык является марковским порядка к, с необходимостью следует, что он является марковским для всех порядков меньше к. Но при этом для любого числа п можно указать такой регулярный язык, который являлся бы марковским языком порядка п, но не являлся бы марковским языком порядка п + 1.
С другой стороны, если язык £ фиксирован, то для ситуация становится обратной. А именно, справедлива Теорема 4.3: если язык является марковским языком порядка 2^', где Ц - множество состояний задающего данный язык автомата, то язык £ является марковским языком любого порядка (и, соответственно, является просто марковским языком).
Любая п-грамма может быть вычислена по диаграмме переходов автомата, однако это требует умения находить собственные числа для матриц большой размерности.
Более точно, для этого необходимо выделить так называемый активный граф автомата 21, то есть подмножество рёбер диаграммы переходов, которые входят хотя бы в один путь из начального состояния в одно из финальных. Активной матрицей автомата 21 называется матрица инцедентности его активного графа.
Теорема 4.5 утверждает, что в том случае, если активная матрица автомата 21 имеет единственное максимальное по модулю собственное значение, то задаваемый этим автоматом язык является марковским.
К сожалению, класс марковских языков не замкнут относительно основных теоретико-языковых операций: объединения, пересечения и дополнения, поэтому в пятой главе рассматривается новый класс языков - каскадно-дефинитные языки.
Понятие дефинитных языков (то есть таких языков, функция переходов которых «забывает» далёкую предысторию) является прямым переносом идеологии марковских языков непосредственно на теорию автоматов. Однако это свойство оказывается слишком жестким: любой дефинитный язык является марковским языком и все его п-граммы (для любого фиксированного п) равны между собой. Поэтому сами по себе дефинитные языки не очень интересны в свете рассмотрения марковских языков. Тем не менее, из них можно получить новый класс языков, с одной стороны небольшой (его доля среди всех языков, задаваемых автоматами с N состояниями стремится к нулю с ростом А/"), а с другой стороны - в некотором смысле «всюду плотный» в множестве марковских языков. В работе вводится операция склейки двух автоматов по паре состояний, позволяющая получить два интересных класса регулярных языков из простейших «кирпичиков» - дефинитных языков, а также циклов и деревянных автоматов.
В работе показано, что для любого марковского автомата можно построить другой марковский автомат, полученный путём применения операции склейки к простейшим автоматам - деревьям и циклам - и имеющий матрицу биграмм сколь угодно близкую к исходной. Очевидно, мощность этого класса невелика: доля таких автоматов среди всех автоматов с фиксированным числом состояний N стремится к нулю с ростом N. В том случае, если матрица биграмм исходного автомата была рациональной, новый автомат будет иметь матрицу биграмм, в точности совпадающую с матрицей биграмм исходного автомата.
Более точно, как утверждает Теорема 5.1, для произвольной биграммной матрицы с рациональными коэффициентами существует автомат 21, имеющий в точности такое же множество биграмм, который может быть получен путём применения операции склейки к простейшим автоматам - деревянным автоматам и циклам.
Теорема 5.2 показывает, что для произвольного марковского языка можно при помощи операции склейки автоматов построить из циклов и деревянных автоматов новый язык, имеющий матрицу биграмм, сколь угодно близкую к матрице биграмм исходного автомата.
Научная новизна работы заключается в следующем:
• предложены новые алгоритмы и подходы для работы с дискретными моделями естественных языков, позволяющие интегрировать их в небольшие системы распознавания в качестве дополнительных блоков, контролирующих и корректирующих результаты распознавания;
• разработано новое представление для моделирования русского языка средствами п-граммного подхода, для него получены оценки качества на базе представительной выборки текстов из области деловой прозы и публицистики.
• основные положения п-граммной модели перенесены на бесконечные регулярные языки, выделены новые нетривиальные классы регулярных, языков (в работе они названы марковскими языками), изучены их свойства.
• найден класс «просто устроенных» регулярных языков, позволяющий промоделировать произвольный марковский язык порядка 2 с любой наперёд заданной точностью.
Практическая значимость работы определяется наличием полиномиальных алгоритмов исправления ошибок в формальных языках и новой языковой моделью, готовой для интеграции в системы распознавания слитной русской речи. Кроме того, изучение свойств п-грамм при помощи методов теории автоматов позволяет выделить новый нетривиальный специальный класс автоматов, которые в некотором смысле адекватны естественным языкам.
Я выражаю глубокую и искреннюю благодарность своему научному руководителю - доктору физико-математических наук, профессору Дмитрию Николаевичу Бабину за постановку задач, постоянную поддержку и внимание к работе.
Я благодарю научного сотрудника лаборатории Проблем теоретической кибернетики, кандидата физико-математических наук Ивана Леонидовича Мазуренко за ценные обсуждения.
Я выражаю глубокую признательность заведующему кафедрой Математической теории интеллектуальных систем, академику, профессору Валерию Борисовичу Кудрявцеву за постоянное внимание к работе и поддержку, а также всем сотрудникам кафедры Математической теории интеллектуальных систем и лаборатории Проблем теоретической кибернетики за творческую атмосферу, способствующую научной работе.
1. Хомский Н. Синтаксические структуры. // Новое в лингвистике. Вып. И. М., 1962.
2. Вудс В.А. Сетевые грамматики для анализа естественных языков // Кибернетический сборник. Новая серия. Вып. 13. -М.: Мир, 1978. С. 120158.
3. Бухараев Р.Г. Основы теории вероятностных автоматов -М.: Наука, 1985.
4. Daniel Sleator and Davy Temperley. 1991. Parsing English with a Link Grammar. Carnegie Mellon University Computer Science technical report CMU-CS-91-196, October 1991.
5. Мельчук И. А. Опыт теории лингвистических моделей «Смысл •(-> Текст». -М.: Наука, 1974.
6. Yu. Kosarev, I. Machovikova, A. Machovikov, R. Piotrowski, S. Tseitlin. Language Perception Modeling Based on Analysis of Children's Speech // Speech and computer, St .-Petersburg, Russia, 26-28 October 1998.
7. EAGLES. «HANDBOOK of Standards and Resources for Spoken Language Systems», Mouton de Gruyter, 1997.
8. Ахо А. и Ульман Дж. Теория синтаксического анализа, перевода и компиляции. -М.: Мир, 1978.
9. Кудрявцев В.В., Алёшин С.В., Подколзин А.С. Введение в теорию автоматов. -М.: Наука, 1985.
10. R. Rosenfeld. A maximum entropy approach to adaptive statistical language modeling. Computer Speech and Language, 10. pp. 187-228, 1996.
11. R. Rosenfeld, Adaptive statistical language modeling: A maximum entropy approach, Ph.D. dissertation, Comput. Sci. Dept., Carnegie-Mellon Univ., Pittsburgh, PA, Apr. 1994.
12. I. J. Good. The population frequencies of species and the estimation of population parameters. Biometrika, vol. 40, no.3/4, pp. 237-264, 1953.
13. I. H. Witten and T. C. Bell. The zero-frequency problem: Estimating the probabilities of novel events in adaptive text compression. IEEE Transactions on Information Theory, vol. 37, no. 4, pp. 1085-1094, July 1991.
14. S. M. Katz. Estimation of probabilities from sparse data for the language model component of a speech recognizer. IEEE Transactions on Acoustics, Speech and Signal Processing, vol. 35, no. 3, pp. 400-401, March 1987.
15. H. Ney, U. Essen, and R. Kneser. On structuring probabilistic dependences in stochastic language modeling. Computer Speech and Language, vol. 8. pp. 1-38, 1994.
16. R. Kneser and H. Ney. Improved backing-off for m-gram language modeling. In Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing, volume I, Detroit, Michigan, May 1995, pp. 181-184.
17. F. Jelinek and R. L. Mercer. Interpolated estimation of Markov source parameters from sparse data. In Proceedings of the Workshop on Pattern Recognition in Practice, pages 381-397, Amsterdam, The Netherlands: North-Holland, May 1980.
18. D. Ron, Y. Singer, and N. Tishby. The power of amnesia. In J. Cowan, G. Tesauro, and J. Alspector, editors, Advances in Neural Information Processing Systems, vol. 6, pp. 176-183. Morgam Kaufmann, San Mateo, CA, 1994.
19. I. Guyon and F. Pereira. Design of a linguistic postprocessor using variable memory length Markov models. In Proceedings of the 3rd ICDAR, pp. 454457, 1995.
20. R. Kneser. Statistical language modeling using a variable context length. In Proceedings of ICSLP, vol. 1, pp. 494-497, Philadelphia, October 1996.
21. T. Niesler and P. Woodland. Variable-length category n-gram language models. Computer Speech and Language, vol. 21, pp. 1-26, 1999.
22. M.-H. Siu and M. Ostendorf. Variable n-gram and extensions for conversational speech language modeling. IEEE Transactions on Speech and Audio Processing, vol. 8, no. 1, pp. 63-75, Jan. 2000.
23. P. J. Price. Evaluation of spoken language systems: the atis domain. In Proceedings of the DARPA Speech and Natural Language Workshop, June 1990.
24. W. H. Ward. The emu air travel information service: understanding spontaneous speech. In Proceedings of the DARPA Speech and Natural Language Workshop, pp. 127-129, June 1990.
25. P. F. Brown, V. J. Delia Pietra, P.V. deSouza, J.C. Lai, and R.L. Mercer. Classbased n-gram models of natural language. Computational Linguistics, vol. 18, no. 4, pp. 467-479, December 1992.
26. R. Kneser and H. Ney. Improved clustering techniques for class-based statistical language modeling. In Proceedings of the European Conference on Speech Communication and Technology (Eurospeech), 1993.
27. L. Breiman, J. H. Friedman, R. A. Olshen, and C. J. Stone. Classification and Regression Trees. Wadsworth & Brooks/Cole Advanced Books & Software, Monterey, California, 1984.
28. L. R. Bahl, P. F. Brown, P. V. de Souza, and R. L. Mercer. A tree-based statistical language model for natural language speech recognition. IEEE Transactions on Acoustics, Speech and Signal Processing, vol. 37, pp. 10011008, July 1989.
29. J. K. Baker. Trainable grammars for speech recognition. In Proceedings of the Spring Conference of the Acoustical Society of America, pp. 547-550, Boston, MA, June 1979.
30. J. D. Lafferty, D. Sleator, and D. Temperley. Grammatical trigrams: a probabilistic model of link grammar. In Proceedings of the AAAI Fall Symposium on Probabilistic Approaches to Natural language, Cambridge, MA, October 1992.
31. L. R. Bahl, J. K. Baker, F. Jelinek, and R.L . Mercer. Perplexity a measure of the difficulty of speech recognition tasks. Program of the 94th Meeting of the Acoustical Society of America J. Acoust. Soc. Am., vol. 62 p. S63, 1977. Suppl. no. 1.
32. Соколова E. H. Алгоритмы лемматизации для русского языка. // Рабочий проект многоязычного автоматического словаря на 60 тыс. словарных статей. Т.1. Лингвистическое обеспечение. -М. 1984. Стр. 45-62.
33. Кулагина О. С. Об автоматическом синтаксическом анализе русских текстов. Препринт / ИПМ АН СССР. -М. 1987. №205.
34. The CMU Statistical Language Modeling (SLM) Toolkit chttp://www.speech.cs.emu.edu/SLMinfo.html>
35. D. Kanevsky, M. Monkowsky, J. Sedivy. Large Vocabulary Speaker-Independent Continuous Speech Recognition in Russian Language. Proc. SPECOM'96, St.-Petersburg, October 28-31, 1996.
36. S. Manhung и др. "Integrating a context-dependent phrase grammar in the variable n-gram framework". In Proceeding of ICASSP. 2000.Работы автора по теме диссертации
37. Холоденко A.B. Лексический анализатор в распознавании последовательных образов. // Информационные технологии в инновационных проектах: Материалы докладов. Международная конференция, 20-22 апреля 1999 г. -Ижевск: ИжГТУ, 1999, с. 43-44.
38. Холоденко A.B. Использование лексических и синтаксических анализаторов в задачах распознавания для естественных языков. // Интеллектуальные системы. Т.4, вып. 1-2, 1999, с. 185-193.
39. Холоденко A.B. Исправление ошибок в формальных языках. // Нейрокомпьютеры и их применение: Сборник докладов. IV Всероссийская конференция, Москва. 16-18 февраля 2000 г. -М.: Издательское предприятие редакции журнала "Радиотехника", 2000, с. 627-630.
40. Kholodenko А. То the creating of the language models for Russian. // V International Congress on mathematical modeling. September 30 October 6, 2002, Dubna, Moscow Region. Book of abstracts, V. 2, -M.:"Janus-K", 2002, p. 97.
41. Холоденко A.B. О построении статистических языковых моделей для систем распознавания русской речи. // Интеллектуальные системы. Т.6, вып. 1-4, 2002, с.381-394.
42. Холоденко A.B. О языковых моделях для систем распознавания русской речи. // Интеллектуальные системы в производстве: Периодический научно-практический журнал 2003. - №1 -Ижевск: Изд-во ИжГТУ, 2003. с. 146-155.
43. Холоденко A.B. О марковских регулярных языках. // Материалы IX Международного семинара "Дискретная математика и её приложения", 18-23 июня 2007 года -М., Изд-во механико-математического факультета МГУ, 2007. с.358-361.
