Содержание к диссертации
Введение
Глава 1. Обзор существующих языковых моделей 13
1.1. Важность задачи моделирования естественного языка 14
1.2. Типы языковых моделей 16
1.2.1. Дискретные языковые модели 17
1.2.2. Статистические языковые модели 23
1.3. Анализ качества языковых моделей 29
Глава 2. Использование дискретных моделей 31
2.1. Основные определения и формальная постановка задачи 31
2.2. Случай регулярной грамматики 33
2.3. Случай контекстно-свободной грамматики 36
2.3.1. Пример работы алгоритма 38
2.3.2. Случай произвольных обобщённых слов 40
2.4. Примеры применения алгоритмов в задачах распознавания . 41
2.5. Задача поиска и исправления ошибок 48
Глава 3. Статистические языковые модели для систем распознавания русской речи 52
3.1. Анализ применимости существующих языковых моделей и их модификаций 54
3.2. Составные языковые модели 56
3.3. Результаты экспериментов 62
Глава 4. Марковские языки 63
4.1. Свойства введённых п-грамм 66
4.2. Свойства марковских языков 68
4.3. Число марковских языков 73
4.4. Достаточное условие марковости 76
Глава 5. Аппроксимация марковских языков 79
5.1. Каскадно-дефинитные языки 83
5.2. Моделирование марковских языков 85
Литература 95
- Типы языковых моделей
- Случай регулярной грамматики
- Составные языковые модели
- Свойства марковских языков
Введение к работе
В работе рассматриваются вопросы моделирования естественного языка в задачах, связанных с обработкой и анализом различной информации. Такие модели используются в широком классе задач, начиная от систем распознавания речи и заканчивая извлечением знаний из документов, поиском информации в сети Интернет и автоматическим переводом текстов с одного языка на другой.
Основная часть работы посвящена вопросам построения адекватных моделей, пригодных для использования в системах распознавания русской речи, а также изучению их свойств.
Для значительной части романских и германских языков, а также для ряда азиатских языков (например, китайского и японского) в настоящее время уже разработаны коммерческие системы распознавания речи. Удачной коммерческой системы для русского языка до сих пор не существует. Одной из основных причин этого является отсутствие эффективной модели для представления русского языка в системе распознавания. Поэтому любые исследования в этой области являются актуальной задачей. Кроме того, большинство работ, посвященных вопросам построения языковых моделей имеют ярко выраженную инженерную направленность. В данной работе предприня- ^ та попытка не только построить работающую модель для русского языка, но и изучить математические свойства вероятностных моделей, получить новый инструментарий для их разработки и анализа.
Целью настоящей работы было разработать новую языковую модель, пригодную для использования в системе распознавания слитной речи для русского языка, а также исследовать свойства n-граммных моделей и построить новый аппарат для их изучения и использования. Основной решаемой проблемой при этом было создание адекватного формализма для п-граммного подхода в рамках теории автоматов и теории формальных языков.
Предметом исследования является формализованная модель естественного языка и её основные свойства.
В работе сравниваются различные подходы к задаче моделирования естественного языка - дискретные и вероятнстные, для каждого подхода предлагаются новые алгоритмы, описывается, в каких случаях лучше применять тот или иной подход.
Работа состоит из пяти глав, введения и списка литературы.
В первой главе приводится анализ существующих методов моделирования естественного языка, пригодных к использованию в задачах, связанных с распознаванием слитной речи.
Известно, что подавляющее превосходство человека над компьютерами в точности распознавания речи, в первую очередь обусловлено именно учётом человеком контекста высказывания (в том числе и смысла) и умением отличить правильно построенное предложение от неправильного. Поэтому важность создания хорошей модели языка для систем распознавания речи трудно переоценить.
Поскольку в задачах распознавания речи обычно приходится иметь дело не с линейной последовательностью букв в слове, а с деревом вариантов распознавания, используемые здесь модели должны обладать некоторыми особенностями. А именно, они должны иметь достаточно высокую скорость работы, чтобы справляться с экспоненциальным взрывом количества вариантов распознавания, а также допускать возможность работы «слева направо», то есть позволять на ранних этапах отсекать те варинаты распознавания, которые не могут быть продолжены до правильного предложения естественного языка.
В этой главе рассматриваются:
дискретные модели:
регулярные языки;
контекстно-свободные языки;
— системы, основанные на использовании лингвистических экс
пертных систем и систем понимания и учёта смысла;
вероятностные модели:
п-граммы;
системы, основанные на деревьях решений;
— вероятностные обобщения контекстно-свободных грамматик.
Здесь показаны преимущества и недостатки каждого из этих подходов, а
также приведена общепринятая на сегодняшний день оценка качества модели, так называемый коэффициент неопределённости (perplexity coefficient).
В случае невозможности или нежелательности проводить полный эксперимент с использоваием системы распознавания, коэффициент неопределённости позволяет сравнивать между собой две модели, а также, в случае использования одинаковых моделей, сравнивать относительную сложность языков.
Во второй главе рассмотрен подход, основанный на использовании дискретных моделей, а именно - регулярных и контекстно-свободных языков.
Пусть дан ориентированный граф без ориентированных циклов, рёбрам которого приписаны буквы алфавита и веса (штрафы). Такой объект в работе назван обобщённым словом. Он примерно соответствует понятию lattice в англоязычной литературе. В каждом таком графе есть источник (вершина без входящих рёбер) и сток (вершина без выходящих рёбер). Они называются начальной и конечной вершиной обобщенного слова соответственно.
Задача формулируется следующим образом.
Пусть дано обобщённое слово а и некоторая грамматика Г. Требуется найти в обобщённом слове путь, ведущий из начальной вершины в конечную и обладающий двумя свойствами:
1. слово, полученной конкатенацией букв, записанных вдоль этого пути должно быть допустимым словом в грамматике Г;
2. сумма весов, стоящих па рёбрах пути должна быть минимальна.
В работе показано, что в случае, если грамматика Г задаётся конечным автоматом, то данная задача может быть решена за время 0(п2), где п - количество вершин в графе обобщённого слова. В том случае, если грамматика Г является контекстно-свободной, то данная задача может быть решена за время 0(п3), где п - количество вершин в графе обобщённого слова.
Описанные во второй главе работы алгоритмы также позволяют несколько обобщить задачу, а именно - перечислить все пути, удовлетворяющие первому условию, либо найти такой путь, который может быть представлен в виде конкатенации произвольного числа слов, допустимых в грамматике Г.
Кроме того, в данной главе приведены также два примера применения построенной техники: в задаче коррекции результатов оптического распознавания символов и в задаче поиска минимального исправления ошибочно написанного слова (так называемая задача spellchecker'a).
В третьей главе рассматриваются вероятностью модели для систем распознавания русской речи.
В настоящее время в задачах распознавания слитной речи чаще всего используются вероятностные модели, построенные на принципе независимости от «далёкой» истории, так называемые n-граммные модели.
Р((Н.\а^щ2... аі._х) « Р(аф^_п+1а{._п+2... а^_г).
Известно, что для моделирования русского языка такие модели подходят плохо. В этой главе предложено простое обобщение n-граммной модели, которое позволило построить работающую вероятностную модель и для русского языка тоже. Главными трудностями в русском языке на пути создания таких моделей являются большое количество словоформ (что приводит к серьёзному увеличению словарей системы) и относительно свободный порядок слов. Основной особенностью предложенного подхода является декомпозиция
общей n-граммной модели в декартово произведение двух моделей: модели, построенной на леммах слов и модели, построенной на морфологической информации.
Каждая из этих моделей была построена и обучена на материале российской периодики. При этом было показано, что полученные характеристики языковых моделей примерно соответствуют среднестатистическим характеристикам моделей для английского языка (коэффициент неопределённости в модели, основанной на леммах, составил около 230; для моделей на английском языке этот коэффициент обычно оказывается в районе 100). Коэффициент неопределённости в категорной модели (построенной исключительно па морфологической информации) оказался около 20.
Таким образом, в этой главе показано, что существующие п-граммные подходы могут быть адаптированы для работы с русским языком. Поэтому исследование свойств подобных вероятностных моделей является важной задачей и с точки зрения создания полноценной системы распознавания слитной русской речи.
К сожалению, несмотря на то, что, как уже было отмечено выше, наибольшее распространение в мире получили именно n-граммные модели, их формальные математические свойства исследованы довольно мало. Поэтому следующие две главы посвящены более детальному анализу свойств п-грамм. Для этого используется аппарат теории автоматов и регулярных языков.
В четвёртой главе вводится обобщение понятия n-граммной модели на бесконечные формальные языки. А именно, вводится частота встречаемости слова w на s-ом месте, а затем рассматривается предельная частота встречаемости слова w как предел при s —> со. Аналогичным образом вводится понятие n-граммы. Если в языке существуют все n-граммы для некоторого фиксированного числа п, то такой язык в работе называется марковским языком порядка п. В том случае, если в языке существуют все n-граммы для всех натуральных чисел п, то этот язык называется марковским языком.
Показано, что даже в классе регулярных языков существуют языки, не являющиеся марковскими. Тем не менее, число марковских регулярных языков достаточно велико. А именно, как доказано в Теореме 4.4, отношение количества марковских языков, задаваемых автоматами с N состояниями, к общему количеству регулярных языков, задаваемых автоматами с N состояниями, для достаточно больших N не меньше, чем (і — -).
Оказывается, что классы марковских языков строго вкладываются друг в друга. А именно, как доказано в Теореме 4.2, из того, что язык является марковским порядка к, с необходимостью следует, что он является марковским для всех порядков меньше к. Но при этом для любого числа п можно указать такой регулярный язык, который являлся бы марковским языком порядка п, но не являлся бы марковским языком порядка п + 1.
С другой стороны, если язык L фиксирован, то для ситуация становится обратной. А именно, справедлива Теорема 4.3: если язык <С является марковским языком порядка 2', где Q - множество состояний задающего данный язык автомата, то язык является марковским языком любого порядка (и, соответственно, является просто марковским языком).
Любая n-грамма может быть вычислена по диаграмме переходов автомата, однако это требует умения находить собственные числа для матриц большой размерности.
Более точно, для этого необходимо выделить так называемый активный граф автомата 21, то есть подмножество рёбер диаграммы переходов, которые входят хотя бы в один путь из начального состояния в одно из финальных. Активной матрицей автомата 21 называется матрица инцедентности его активного графа.
Теорема 4.5 утверждает, что в том случае, если активная матрица автомата 21 имеет единственное максимальное по модулю собственное значение, то задаваемый этим автоматом язык является марковским.
К сожалению, класс марковских языков не замкнут относительно основ-
ных теоретико-языковых операций: объединения, пересечения и дополнения, поэтому в пятой главе рассматривается новый класс языков - каскадно-дефинитные языки.
Понятие дефинитных языков (то есть таких языков, функция переходов которых «забывает» далёкую предысторию) является прямым переносом идеологии марковских языков непосредственно на теорию автоматов. Однако это свойство оказывается слишком жестким: любой дефинитный язык является марковским языком и все его n-граммы (для любого фиксированного п) равны между собой. Поэтому сами по себе дефинитные языки не очень интересны в свете рассмотрения марковских языков. Тем не менее, из них можно получить новый класс языков, с одной стороны небольшой (его доля среди всех языков, задаваемых автоматами с N состояниями стремится к нулю с ростом N), а с другой стороны - в некотором смысле «всюду плотный» в множестве марковских языков. В работе вводится операция склейки двух автоматов по паре состояний, позволяющая получить два интересных класса регулярных языков из простейших «кирпичиков» - дефинитных языков, а также циклов и деревянных автоматов.
В работе показано, что для любого марковского автомата можно построить другой марковский автомат, полученный путём применения операции склейки к простейшим автоматам - деревьям и циклам - и имеющий матрицу биграмм сколь угодно близкую к исходной. Очевидно, мощность этого класса невелика: доля таких автоматов среди всех автоматов с фиксированным числом состояний N стремится к нулю с ростом N. В том случае, если матрица биграмм исходного автомата была рациональной, новый автомат будет иметь матрицу биграмм, в точности совпадающую с матрицей биграмм исходного автомата.
Более точно, как утверждает Теорема 5.1, для произвольной биграммной матрицы с рациональными коэффициентами существует автомат 21, имеющий в точности такое же множество биграмм, который может быть получен
путём применения операции склейки к простейшим автоматам - деревянным автоматам и циклам.
Теорема 5.2 показывает, что для произвольного марковского языка можно при помощи операции склейки автоматов построить из циклов и деревянных автоматов новый язык, имеющий матрицу биграмм, сколь угодно близкую к матрице биграмм исходного автомата.
Научная новизна работы заключается в следующем:
предложены новые алгоритмы и подходы для работы с дискретными моделями естественных языков, позволяющие интегрировать их в небольшие системы распознавания в качестве дополнительных блоков, контролирующих и корректирующих результаты распознавания;
разработано новое представление для моделирования русского языка средствами n-граммного подхода, для него получены оценки качества на базе представительной выборки текстов из области деловой прозы и публицистики.
основные положения n-граммной модели перенесены на бесконечные регулярные языки, выделены новые нетривиальные классы регулярных, языков (в работе они названы марковскими языками), изучены их свойства.
найден класс «просто устроенных» регулярных языков, позволяющий промоделировать произвольный марковский язык порядка 2 с любой наперёд заданной точностью.
Практическая значимость работы определяется наличием полиномиальных алгоритмов исправления ошибок в формальных языках и новой языковой моделью, готовой для интеграции в системы распознавания слитной русской речи. Кроме того, изучение свойств n-грамм при помощи методов теории автоматов позволяет выделить новый нетривиальный специальный класс автоматов, которые в некотором смысле адекватны естественным языкам.
Я выражаю глубокую и искреннюю благодарность своему научному руководителю - доктору физико-математических наук, профессору Дмитрию Николаевичу Бабину за постановку задач, постоянную поддержку и внимание к работе.
Я благодарю научного сотрудника лаборатории Проблем теоретической кибернетики, кандидата физико-математических наук Ивана Леонидовича Мазуренко за ценные обсуждения.
Я выражаю глубокую признательность заведующему кафедрой Математической теории интеллектуальных систем, академику, профессору Валерию Борисовичу Кудрявцеву за постоянное внимание к работе и поддержку, а также всем сотрудникам кафедры Математической теории интеллектуальных систем и лаборатории Проблем теоретической кибернетики за творческую атмосферу, способствующую научной работе.
Типы языковых моделей
В литературе известны различные классификации языковых моделей, см., например, [7]. В рамках настоящей работы мы выделим два больших класса языковых моделей - дискретные и статистические модели. Зафиксируем конечный алфавит А и некоторый язык С А . Определение 1.1 Дискретной языковой моделью называется функция f : А — {0,1} такая, что для любого слова а Є A f{a) — 1 тогда и только тогда, когда а Є -С. Определение 1.2 Статистической языковой моделью называется произвольная функция распределения на множестве А . Таким образом, дискретные языковые модели являются средством проверки, принадлежит ли указанное слово а языку, в то время как статистические языковые модели определяют вероятность того, что указанное слово является допустимым словом языка. Очевидно, что дискретные языковые модели являются частным случаем статистических. В самом деле, достаточно лишь взять в качестве функции распределения характеристическую функцию множества & С. А . Однако наличие эффективных методов вычисления и другие особенности позволяют всё же выделить дискретные языковые модели в отдельный класс. Рассмотрим эти два класса более подробно. Дискретные языковые модели удобны тем, что позволяют точно ответить на вопрос, принадлежит ли анализируемое слово заданному языку, или нет. Это приводит к тому, что нам не нужно хранить заведомо неверные варианты распознавания, а это, в свою очередь, положительно сказывается на быстродействии системы и расходе памяти. Однако, это достоинство часто оборачивается их недостатком. В самом деле, если в результате неизбежных неточностей при моделировании языка правильный вариант распознавания окажется не допустимым словом в рамках используемой языковой модели, то система не сможет выдать правильного варианта распознавания даже в том случае, когда этот вариант был не только самым вероятным после прохождения через акустическую часть системы распознавания, по и вообще единственным.
Прежде чем переходить к дальнейшему изложению, напомним несколько общеизвестных определений [8], которыми мы будем часто пользоваться в дальнейшем. Определение 1.3 Языком в алфавите А называется множество слов в А. Через А обозначим множество всех слов в алфавите А, включая пустое слово Л. Тогда каждый язык в алфавите А является подмножеством множества А . Заметим, что пустой язык (который мы будем обозначать через 0) и язык, состоящий из одного пустого слова Л в нашем определении являются различными языками. Введём также несколько операций над языками: Определение 1.4 Пусть i - язык в алфавите А\, аЯ 2 язык в алфавите A i. Тогда язык -1 2 называемый конкатенацией языков i и L 2 - это язык {а(3\аЄ&и/ЗЄ&2}.
Определение 1.9 Будем говорить, что автомат 21 допускает (или принимает) слово а, если (p(a,qo) Є QF Справедлива следующая теорема (см., например, [9]): Теорема 1.1 (Клини) Язык И является регулярным тогда и только тогда, когда он порождается каким-нибудь конечным детерминированным атома-том.
Автоматное представление языка позволяет очень быстро проверять допустимость входного слова, то есть его принадлежность множеству . В общем случае проверка занимает линейное время относительно длины входного слова.
Очевидно, что автоматаными языками можно описать практически любой естественный язык. В самом деле, если задаться достаточно большим числом N (скажем, 10 000) и выписать все возможные предложения естественного языка, имеющие длину не более N, то их количество, очевидно, не превосходит \D\N, где D - словарь языка, то есть множество всех возможных «словарных» слов. Вероятность встретить предложение длиной более 10 000 слов в естественном языке исчезающе мала, поэтому такое представление языка будет достаточно точным. Однако, сложность такого представления колоссальна, поэтому использовать его в реальных системах не представляется возможным.
Другим аргументом за использование автоматных моделей естественных языков является тот факт, что человеческий мозг с математической точки зрения является нейронной сетью, то есть сам представляет собой гигантский и очень сложно устроенный конечный автомат. Таким образом, человек, вообще говоря, сам может пользоваться только регулярными языками. Однако здесь возникает тот же самый аргумент - колоссальная сложность такого автомата. Для действующих компьютерных систем необходимо уметь строить гораздо более компактные модели естественных языков. А вот промоделировать естественный язык компактной автоматной моделью уже не получается. Более удачным с точки зрения богатства представления является следующий класс языков в классификации грамматик Хомского - контекстно-свободные языки. Тем не менее, регулярные языки находят своё применение при моделировании небольших ограниченных предметных областей. Другое применение регулярных языков будет предложено в конце второй главы.
Контекстно-свободные языки позволяют моделировать достаточно широкий спектр лингвистических конструкций: так, например, русский язык является «почти» контекстно-свободным, то есть его синтаксическая структура моделируется контекстно-свободным языком с точностью до правил поглощения знаков препинания на границах вложенных конструкций. Например, по правилам русского языка деепричастные обороты при письме выделяются запятыми. Однако, если деепичастный оборот стоит в самом конце предложения, то последнюю запятую опускают, оставляя лишь точку в конце предложения. Такие правила не могут быть смоделированы КС-грамматиками.
К сожалению, скорость работы анализатора для контекстно-свободной грамматики оказывается гораздо ниже, чем скорости анализаторов для регулярных языков. В общем случае известные алгоритмы показывают скорость порядка п3, где n-длина анализируемого слова (см., например, [8]). Существуют также другие дискретные модели, по выразительной силе совпадающие с контекстно-свободными грамматиками. К ним можно отнести грамматики Вудса [2] и грамматики зависимостей (Link grammar) [4]. Модели, основанные на экспертных системах Последним важным классом языковых моделей, который стоит здесь упомянуть, является класс моделей, построенных на экспертных системах. Данный класс моделей нашёл очень широкое применение в диалоговых вопрос-ответных системах для общения с компьютерами на естественном языке, а также в рамках систем автоматического перевода. В рамках этого класса могут быть построены любые языковые модели, однако скорость их работы, особенно в условиях экспоненциального возрастания количества вариантов распознавания, не позволяет использовать их в системах распознавания речи.
Случай регулярной грамматики
Разберем сначала случай, когда грамматика Г является регулярной. По теореме Клини [9] существует конечный детерминированный автомат, порождающий тот же самый язык. Предположим вначале, что наше обобщенное слово линейно. Тогда задача сводится к построению разбиения входного слова на подслова, допускаемые заданным конечным детерминированным автоматом. Пусть автомат 21р = {A Q, QF, р, 7о} реализует грамматику Г, а - слово над алфавитом А. Положим /3 := %г{сч),[3 Є Е%, где п = а. Pi :— 1 = - ip([a]i,qo) Є QF, ТО есть / равно единице тогда и только тогда, когда начало слова а длины і является допустимым. Заметим, что для вычисления вектора (3 требуется в точности п операций. Рассмотрим множество {&k,n}k=v Pk,n := %1т(&к,п)- Введем матрицу С = (cij) следующего вида. Ее /с-ая строка начинается с (к — 1) нуля, после чего стоит вектор Pk,n- Ясно, что Cij = 1 4= слово otjj является допустимым. ТІ Очевидно, что матрицу С можно построить за Yl іп к-\-1) — п("2+ « Ц к=1 операций. Введем вектора k = (ki,..., кп+і) и q = (qi,..., qn+i) ks — 1 тогда и только тогда, когда перед s-ой буквой во входном слове можно поставить границу между двумя подсловами. Если это можно сделать, то qs указывает на конец предыдущего слова при таком разбиении. Положим к\ := 1 (перед первой буквой всегда можно вставить границу).
Для s 1: ks := 1 4=Ф- Э такое, что ki = 1 и cs_i = 1. В этом случае положим qs := I. Это означает, что перед s-ой буквой можно вставить границу тогда и только тогда, когда существует такой номер Z, что на 1-ом месте можно вставить границу, а слово с і5_і - допустимо. Очевидно, что слово допускает разбиение тогда и только тогда, когда можно вставить границу после последней буквы, то есть кп+\ = 1. При этом, двигаясь по вектору q из конца в начало, мы получим само разбиение. Ясно, что для вычисления ks требуется s операций, а на вычисление всего вектора к требуется s = (п+ « Ц . s=l Таким образом, общее число операций составляет п2 и мы доказали следующее утверждение: Утверждение 2.1 Существует алгоритм, который для любого слова длины п строит его разбиение на подслова, допускаемые данной регулярной грамматикой. Сложность указанного алгоритма есть 0(п2) плюс время перечисления ответа. Таким образом, мы получили алгоритм, «за квадратичное время» разбивающий слово на подслова. Замечание 2.1 Необходимо отметить,что за квадратичное время можно построить ориентированный граф, являющийся обобщенным словом над алфавитом всех всевозможных допустимых слов. При этом реальное число путей, содержащееся в этом обобщенном слове может быть даже экспоненциально. (Пример. А = {а}; Г = а ). Если слово было нагруженным, то в матрице С мы будем хранить штра — фы за использование данного подслова, а в векторе к - величину штрафа, накопленного нами к этому моменту. При этом число I из алгоритма выбирается из условия минимизации суммарного штрафа. Отсутствие разбиения для момента s означает, что ks = +оо. Если мы хотим получить все возможные пути, то необходимо хранить не одно значение I, а все подходящие значения. Перейдем теперь к произвольным обобщенным словам. Построим систему множеств {5j}=1, где п-длина обобщенного слова. Положим S\ = go- Пусть множества Si уже построены для всех г к. Пусть N = {i\ \..., ц: }- номера вершин, из которых ребра ведут в вершину к] А.(к),..., А.{к) - множества букв, стоящих на этих ребрах. Тогда гк Sk=\J r&N U 4 {b а) qeSr;aeAr Множество Sk определено корректно, так как все элементы в множестве iV строго меньше к (в силу способа нумерации). Содержательно это означает, что на первом шаге мы находимся в начальном состоянии, а дальше - мы из каждой вершины для всех доступных в ней состояний совершаем все возможные переходы, причем множество состояний для каждой вершины получается объединением множеств состояний, полученных при переходе в нее из какой-то одной. — Теперь вектор /3 можно быть определен следующим образом: = 1 == Si n Q ф 0.
Дальнейший ход алгоритма полностью аналогичен рассмотренному выше случаю. Элемент матрицы qj кладется равным нулю (бесконечности), если не существует пути, ведущего из j -ой вершины в г-ую. Так как из j-ой вершины в &-ую может вести не более \А\ ребер, а число вершин, подлежащих обработке, не превосходит к, то для вычисления множества Sk необходимо произвести не более \А\ -\Q\-k операций. Таким образом, для вычисления к -ой строки матрицы С необходимо затратить О (к) операций. Следовательно, всего алгоритм требует 0(п2) операций. Замечание 2.2 Если язык, задаваемый регулярной грамматикой, конечен, то полученные оценки можно улучшить. Так, например, для построения одного разбиения в случае линейного обобщенного слова требуется 0(п) операций, где константа зависит от словаря и не зависит от анализируемого слова. 2.3. Случай контекстно-свободной грамматики Перейдем теперь к случаю контекстно-свободных грамматик. Для этого приведем вначале несколько определений и общеизвестных свойств КС-грамматик (без доказательства). В дальнейшем терминалы грамматики мы будем обозначать строчными латинскими буквами, нетерминалы - заглавными, а пустое слово обозначим через Л. Утверждение 2.2 Если язык, порождаемый К С-грамматикой не содержит пустого слова, то грамматику можно привести к виду, в котором не будет правил с пустой правой частью. Известно множество алгоритмов для проверки, является ли данное слово выводимым в данной КС-грамматике (см., например, [8]). Приведем известный алгоритм разбора, который мы в дальнейшем перенесём на случай обобщённых слов. В силу утверждения 2.2 можно считать, что в грамматике нет правил с пустой правой частью. Введем помимо существующих нетерминалов еще два новых специальных символа: 0 и «.».
Составные языковые модели
Второй подход, разработанный в ходе проведенных исследований, был призван решить проблему большого количества словоформ. В русском языке связи между словами определяются не порядком слов в предложении, а морфологическими характеристиками слов. Вот простой пример. Рассмотрим следующее предложение: «Черная собака укусила кошку» Несмотря на то, что этот вариант является самым частотным, в русском языке можно переставить слова в предложении, не меняя общего смысла всего высказывания. Например: «Кошку укусила черная собака» или даже «Укусила черная кошку собака» где между объектом (собака) и его свойством (черная) находится другой объект (кошка). Для того чтобы иметь возможность связать между собой, например, объект и его свойства, они должны быть морфологически согласованы. Так, в этом примере существительное и прилагательное имеют одинаковый падеж, род и число. Таким образом, очевидно, что морфологическая информация должна являться очень важной частью языковой модели.
Кроме того, как уже упоминалось ранее, многие словоформы очень незначительно различаются с акустической точки зрения. Для того, чтобы облегчить задачу распознавания этих словоформ, также полезно предварительно выделить морфологическую составляющую грамматики в отдельную языковую модель. Таким образом, для преодоления указанных недостатков стандартных моделей вводится понятие категорной языковой модели, и, в частности, кате-горных п-грамм. Категорной языковой моделью называется модель, каждому слову в которой дополнительно приписана определённая категория, то есть элемент некоторого конечного множества К. В простейшем случае такой категорией может служить информация о части речи; в более сложных ситуациях -подробная морфологическая информация (как это сделано в предлагаемой модели) или даже семантическая разметка. Для английского языка подобная модель впервые была рассмотрена в работе [24], где введение в словарь вручную расставленных семантических классов было использовано в качестве одной из возможных техник сглаживания. В работах [25] и [26] было показано, что использование информации о части речи для языковых моделей в английском языке приводит к незначительному улучшению всей модели относительно стандартной n-граммной модели.
В описанной в настоящей главе модели каждое слово в словаре системы имеет 15 атрибутов, определяющих морфологические свойства словоформы. Каждый атрибут в нашей модели может иметь одно из нескольких значений (например, значениями для атрибута «часть речи» являются «существительное», «прилагательное», «глагол» и так далее). В том случае, если некоторый атрибут оказывается бессмысленным для данного слова, например, атрибут «время» для имени существительного, он получает специальное значение «не определено».
Совокупность значений всех атрибутов определяет морфологический «класс» словоформы. Введенный набор атрибутов позволяет выделить в русском языке 562 морфологических класса. Таким образом, каждое слово в предложении может рассматриваться как его начальная форма плюс его мор 61
фологический класс, что позволяет вложить грамматику в прямое произведение двух более простых грамматик: изменяемую часть (основанную на морфологии) и постоянную часть (основанную на начальных формах слов). Например, слово «черный» будет преобразовано в начальную форму («черный») плюс два варианта списка морфологических характеристик (Таблица 2).
Основное внимание в описываемой части работы работе было уделено разработке категорной части языковой модели. По части обучающего корпуса была построена категорная триграммная модель, после чего были вычислены коэффициенты неопределенности для возрастающей последовательности вложенных друг в друга тестовых корпусов. В качестве техники сглаживания была использована техника линейного сбрасывания и торможения, linear discounting and back-off, [7]).
Итоговый коэффициент неопределенности для всего обработанного корпуса оказался равен « 22. Данное значение коэффициента было получено уже на корпусках объёмам несколько сотен тысяч слов и в дальнейшем не менялось. Таким образом, можно предполагать, что значение коэффициента неопределённости для русской категорной грамматики вычислено корректно. Неизменяемая часть грамматики: начальные формы слов Вторая составляющая грамматики строится обычным образом, это п-граммная языковая модель, построенная на начальных формах слов. В результате экспериментов удалось установить, что коэффициент неопределенности этой модели на рассмотренном фрагменте корпуса примерно в 2-2,5 раза выше, чем в случае среднестатистических моделей для английского языка (около 230 в нашей модели против примерно 100 в модели для тестового корпуса Wall Street Journal; см., например, [38]).
Свойства марковских языков
Покажем несколько важных свойств марковских языков. Теорема 4.1 Если язык является марковским порядка п, то он также является марковским порядка к п. Доказательство этого факта напрямую следует из утверждений 4.2 и 4.3, поскольку, как следует из этих утверждений, частоты и n-граммы языков более низкого порядка получаются суммированием слева соответственно частот и n-грамм языка более высокого порядка. Таким образом, все они существуют. Замечание 4.2 Следует отметить, что обратное неверно. Например, существует язык, являющийся марковским языком первого порядка и не являющийся марковским языком второго порядка.
На этом рисунке приведена диаграмма переходов автомата, порождающего язык , являющийся марковским языком порядка п, но не являющийся марковским языком порядка п + 1. Таким образом, доказано следующее утверждение: Теорема 4.2 Для любого п Є N существует язык , такой, что Є Жп-\, но при этом L Жп. Тем не менее, для любого фиксированного языка Л можно указать такой номер N, что из утверждения Є M(iV) будет следовать, что бМ. Более точно, справедлива следующая теорема: Теорема 4.3 Пусть язык = &% задан автоматом 21 = {A, Q, ip, QF, QO}-Тогда из Є М(2 91) следует, что Є Ж. Доказательство. Обозначим через xq(t) число слов длины t, ведущих из начального состояния qo в состояние q. Рассмотрим произвольное слово а. Для данного слова а рассмотрим такие состояния q, из которых по некоторому слову а/3 можно попасть в какое-то финальное состояние автомата 21. Множество таких состояний обозначим через Q(a). Таким образом, Q(a) = {q\3p,ip(q,aj3)GQF}. Тогда, очевидно, выполнены соотношения la{s) = 2 Xq(s) qeQ(a) и ]Г l,(s) = \Ж(з)\. ы=н Отсюда получаем, что ... Е xv(s) \w \—\w\ Рассмотрим Q(a) при всех а. Очевидно, что этих множеств не может быть больше 2 1. Таким образом вопрос о существовании бескончного числа пределов lim rwa(s) для всех возможных слов w Є А сводится к провер-ке существования конечного множества пределов. Для завершения доказательства теоремы нам осталось показать, что проверка существования этих пределов может быть осуществлена на словах длины не более 2 1.
Следовательно, начиная с множества QA, МЫ при помощи слов длины не более чем 2 1 исчерпаем все возможные Q(a), а пределы при п-граммах большей длины будут выражаться через п-граммы длины не больше чем 2І0І. Теорема доказана. Сформулируем и докажем вначале вспомогательное утверждение: Утверждение 4.4 Всякий силъпосвязный автомат А порождает марковский язык с равномерными частотами встречаемости слов.
В качестве следствия этого утверждения можно получить оценку числа марковских языков. Обозначим через MJV класс марковских языков, задаваемых автоматами не более чем с N состояниями. Через Лн обозначим класс всех регулярных языков, задаваемых автоматами не более чем с N состояниями. Тогда справедлива следующая теорема: Теорема 4.4 (Оценка числа марковских языков) Для достаточно больших N Доказательство. Зафиксируем алфавит А и множество состояний Q; \Q\ = к. Пусть = я, 21 = {A, Q, р, QF, go} 75 Если автомат 21 является сильносвязным, то для любой пары состояний i,j существует слово а Є А , что p(qt, a) = qj. Оценим количество автоматов, не являющихся сильносвязными. Если автомат не является сильносвязным, то существует подмножество Q С Q, которое является образом функции переходов ср. Пусть, для определённости, і . Q .
Учитывая, что для отсутствия сильной связности необходимо, чтобы указанное выше условие выполнялось для любой буквы as Є А, получаем, что частота ситуации, когда по всем буквам из А образ функции переходов не содержит 1, будет равняться (к-1)к\{А{ кк ) Устремляя число состояний к бесконечности, получаем, что к— оо у Таким образом, число сильно связных автоматов не меньше, чем 1 — Q) 1 — -, а число марковских автоматов по предыдущему утверждению не меньше, чем число сильно связных. Из этих двух утверждений и следует утверждение теоремы. Теорема доказана. 4.4. Достаточное условие марковости Пусть дан язык и задающий его автомат 21. Определение 4.3 Активным графом автомата 21 назовём подмножество ребер диаграммы переходов автомата 21, которые входят хотя бы в один путь из начальной вершины в одну из финальных вершин, а также инце-дентные им вершины. Определение 4.4 Активной матрицей автомата 21 назовём матрицу ин-цедентности его активного графа. Справедлива следующая теорема: Теорема 4.5 Если активная матрица автомата 21 имеет единственное максимальное по модулю собственное значение, то задаваемый этим автоматом язык является марковским. Доказательство. В самом деле, обозначим снова через xq(t) число слов длины і, ведущих из начального состояния go в состояние q. Замечание 4.3 Следует отметить, что это достаточное условие марковости, но не необходимое. В самом деле, рассмотрим произвольный автомат 21, удовлетворяющий условиям теоремы. Рассмотрим теперь автомат 21 , представляющий собой параллельное соединение двух копий автомата 21. Очевидно, что языки, задаваемые автоматами 21 и 21 , совпадают. Однако, если автомат 21 имеет собственное значение Л кратности &, то автомат 21 будет иметь собственное значение Л кратности 2 х к, и других собственных значений у него не будет.
Таким образом, построенный автомат 21 будет иметь максимальное по модулю собственное значение кратности 2, однако при этом будет являться марковским языком по построению, что и требовалось показать.