Обучение с нуля грамматики связей русского языка

Размещено на http://www.allbest.ru/

УДК 004.855

ОБУЧЕНИЕ С НУЛЯ ГРАММАТИКИ СВЯЗЕЙ РУССКОГО ЯЗЫКА

С.В. Протасов Россия, Москва 117303, ул. Керченская, д. 1A, корп. 1, МФТИ, svp@mtu.ru

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

Введение

В настоящий момент в некоторых практических приложениях пользуются популярностью n-грамные модели грамматики [Bahl et al., 1983], [Jelinek, 1997]. К n-грамным грамматикам относятся и триграмные модели, занимающие сильные позиции в статистическом моделировании языка [Brown et al., 1992]. Однако в триграмной модели каждое слово зависит только лишь от двух предыдущих, и не может учитывать дальние связи в предложении. Если лингвистический формализм будет иметь дальние связи, то он потенциально должен иметь лучшие характеристики при моделировании естественного языка. В данной работе изучаются вероятностные грамматики связей, относительно новый контекстно-свободный формализм (относительно грамматик непосредственно составляющих [Chomsky, 1957] и грамматик зависимостей [Mel'chuk, 1979]), которые впервые были предложены в работе [Sleator et al., 1991], а применимость для русского языка была показана в работе [Протасов, 2005]. Формализм грамматики связей содержит n-грам модели как подкласс и одновременно допускает наличие дальних связей [Lafferty et al., 1992].

В данной работе рассмотрена концепция грамматики связей, её вероятностная модель и обучающий алгоритм. На базе алгоритма была создана программа, которая при тестировании на реальных русскоязычных текстах показала значительное снижении кросс-энтропии кросс-энтропия - (нестрого) среднее число бит, необходимых для кодирования каждого слова с помощью модели грамматики языка, что подтверждает принципиальную возможность существования автоматизированных технологий создания грамматики связей русского языка. Предполагается вывод правил грамматики, и оценка вероятности срабатывания выведенных правил грамматики при отсутствии подробной грамматической теории. Исследование возможности создания грамматики связей с помощью только лишь анализа неразмеченного корпуса предложений есть главная цель данной работы.

Попытки статистического обучения контекстно-свободных грамматик уже совершались [Lari et al., 1990] [Jelinek et al., 1992] [Yuret, 1998] [Collins, 1999], однако кросс-энтропия моделей языка либо не указывалась, либо была хуже триграмных моделей [Brown et al., 1992]. В большинстве подобных работ для обучения используются предварительно размеченные тексты, специфичные для данной модели языка, что сильно осложняет возможность сравнения самих моделей языка с другими формализмами. Мы же попытались получить численное значение (кросс-энтропии), которое можно сравнивать с другими моделями. Так как грамматика связей имеет дальние связи, контекстную свободу и эффективный алгоритм разбора, то мы надеемся на получение преимущества над триграмными моделями.

Далее в работе будет показан процесс создания вероятностной модели языка, основанной на грамматике связей. После короткого описания концепции грамматики связей мы рассмотрим алгоритм разбора и обучения. После чего будут обсуждены вопросы, касающиеся сглаживания параметров, лингвистических ограничений и оценки качества модели.

1. Предварительная информация

1.1 Грамматика связей

Лучшим способом объяснить основы грамматики связей является демонстрация связки. Связка - один из вариантов разбора, разрешенный грамматикой связей. На рисунке 1 показан пример связки слов, разрешенный грамматикой связей, разработанной вручную [Протасов, 2005].

Рис. 1. Связка слов.

Разбор или связка предложения составляется путем выбора дизъюнктов для всех слов. Дизъюнкт (или дизъюнктивное слагаемое) - это два упорядоченных списка коннекторов. Все коннекторы во всех выбранных дизъюнктах должны соединяться друг с другом не более одного раза, то есть на каждый коннектор по одной связи. Соединенные коннекторы образуют связи и граф, где узлы - слова, а дуги - связи с названиями коннекторов. Граф расположен выше линейно расположенных слов. Дуги графа не пересекаются (это свойство называется планарностью планарность - слабая проективность в формализме грамматики зависимостей). Если подобрать дизъюнкты невозможно, тогда разбираемое предложение не принадлежит языку грамматики.

В работах [Протасов, 2005] [Sleator et al., 1993] [Sleator et al., 1991] грамматика связей разъяснена более подробно. У неё есть некоторое сходство с грамматикой зависимостей [Mel'chuk, 1979] [Mel'chuk, 1988], однако грамматика связей может иметь циклы и в ней отсутствует корневое слово. В работах [Протасов, 2005] [Schneider, 1998] можно найти подробное сравнение с грамматикой зависимостей, довольно популярной у нас в стране. Следует отметить, что демонстрационный рисунок 1 соответствует грамматике связей, разработанной вручную с использованием школьных правил грамматики русского языка. В дальнейшем мы предполагаем отсутствие априорных знаний о грамматических связях.

1.2 Алгоритм анализа

Алгоритм обучения грамматики связей во многом опирается на алгоритм разбора (анализа). Алгоритм разбора подробно представлен в работе [Sleator et al., 1991]. Алгоритм представляет собой рекурсивный разбор предложения сверху вниз с кэшированием промежуточных результатов.

1.3 Вероятностная модель

Если всему языку грамматики весь язык - это множество (возможно бесконечное) всех предложений языка, удовлетворяющий правилам грамматики языка назначить полную вероятность, равную 1, тогда каждое предложение языка будет иметь свою вероятность появления, и мы сможем оценивать, какова вероятность того, что данная последовательность слов и связей между ними принадлежит языку. Зная вероятность каждого предложения в корпусе предложений, мы можем расчитать сумму логарифмов этих вероятностей со знаком минус. Эта величина будет называться кросс-энтропией. А в процедуре обучения используется алгоритм, который ищет локальный минимум кросс-энтропии корпуса предложений. Найденные параметры вероятностей позволят нам сконструировать грамматику, анализирующую новые предложения.

2. Обучающий алгоритм

Целью алгоритма обучения грамматики является нахождение максимально-правдоподобных оценок параметров вероятностной грамматики связей. Алгоритм работает в духе Inside-Outside [Jelinek et al., 1992] [Lari et al., 1990], который по сути является частным случаем более общего алгоритма EM (Expectation Maximization) [Baum, 1972]. В алгоритме рассчитываются две вероятности: внешняя вероятность и внутренняя вероятность. Внутренние и внешние вероятности вычисляются рекурсивно через формулы из работы [Lafferty et al., 1992], где обучающий алгоритм рассмотрен достаточно подробно.

Очень важно, что отсутствие экспоненциального роста требуемых ресурсов при работе алгоритма позволяет надеяться на легкую масштабируемость и применимость алгоритма к крупным текстам.

2.1 Сглаживание

Сглаживание значительно улучшает качество обучения вероятностной модели языка. Языковые явления могут быть довольно редки и чтобы обучающий алгоритм сходился, необходимы сглаживающие оценки параметров вероятностей. Различные техники сглаживания подробно рассмотрены в работе [Manning and Shutze, 1999]. А в работе [Lafferty et al., 1992] рассмотрена методика грамматических триграм, которая позволяет производить качественное сглаживание на основе оценок, полученных из неразмеченного корпуса предложений.

2.2 Ограничения на поиск

Эксперимент заключается в выводе набора параметров вероятностей грамматики связей путем анализа корпуса предложений русского языка. Предполагается, что априори мы имеем самые минимальные знания о грамматике языка. Известно лишь, что есть слова и между словами есть связи. Предложим самые простые и сильные ограничения на типы связей и классы слов.

Единственный тип связи. Для уменьшения пространства поиска рационально ввести единственный тип связи. На рисунке 3 показан пример связки с единственным типом связи. Число дизъюнктивных слагаемых растет по экспоненте от числа типов связей, и обучение без этого ограничения крайне затруднительно.

Рис.3. Единственный тип связи N.

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

Единственный класс слова. В алгоритме не используются знания о частях речи и не используется какая-либо кластеризация слов. Предполагается, что набор дизъюнктивных слагаемых после процедуры обучения и подскажет нам грамматический класс слова.

2.3 Процедура обучения

Процедура обучения состоит из 3-х этапов: 1) Инициализация вероятностных параметров; 2) Обучение на неразмеченном корпусе предложений; 3)Отсев дизъюнктивных слагаемых.

Инициализация вероятностных параметров. Так как алгоритм обучения гарантирует только нахождение локального минимума кросс-энтропии, то задача выбора начальных параметров вероятностей очень важна для качества обучения. В процедуре инициализации мы предполагаем, что все события равновероятны. То есть в процессе генерации предложения вероятность выбора слова равна вероятности выбора любого другого слова, а вероятность выбора дизъюнкта равна вероятности выбора любого другого дизъюнкта.

Обучение на неразмеченном корпусе предложений. Для обучения важно подобрать корпус. Желательно максимальное значение отношения числа предложений к числу слов, чтобы для каждого слова было достаточно примеров его использования. Для этих целей был создан корпус, где число предложений примерно в 10 раз больше числа используемых слов. Корпус создавался автоматически, путем фильтрации большого корпуса русского языка и поиска только тех предложений, все слова в которых принадлежали заданному набору из 355 высокочастотных слов. Если бы мы попытались составить корпус из более простых слов средней частотности, то мы бы получили меньшее число предложений, что для наших целей обучения не совсем подходит.

Отсев дизъюнктивных слагаемых. В конце обучения происходит отсев дизъюнктивных слагаемых с низкими вероятностями. После процедуры удаления общие вероятности пересчитываются, и число вариантов разбора уменьшается. Для увеличения скорости работы алгоритма процедуру удаления дизъюнктивных слагаемых можно повторять на каждом шаге обучения.

3. Эксперимент

Для целей эксперимента был составлен русскоязычный корпус из 2780 предложений русского языка длины от 3 до 8 слов, содержащий 355 разных слов. Максимальное число коннекторов с каждой стороны было ограничено двумя, а число дизъюнктивных слагаемых восьмью. Порог отсева дизъюнктивных слагаемых был установлен на 0.001. Корпус был разбит на обучающую часть и на тестирующую часть тремя различными способами согласно таблице 1.

Таблица 1. Параметры корпусов

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

3.1 Результаты эксперимента

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

Разборы оценивались на принадлежность к трем классам: правильные, приемлемые и неправильные. На рисунке 4 приведен пример связки правильного разбора, а на рисунке 5 - приемлемого, на рисунке 6 - неправильного.

Рис.4. Пример правильного разбора

Рис.5. Пример приемлемого разбора

Рис.6. Пример неправильного разбора/Пример биграм модели

В таблице 2 приведены проценты приемлемых и правильных разборов для предложений из тестовых корпусов. Читатель может самостоятельно оценить адекватность полученных коэффициентов См. корпус разборов http://sz.ru/parser/corpora1-test.txt.

Таблица 2. Проценты приемлемых и правильных разборов.

В данной работе был рассмотрен метод получения вероятностной грамматики связи только лишь на основе анализа корпуса языка. Оригинальная модель языка [Lafferty et al., 1992] была упрощена до небольшого числа дизъюнктов и одного типа коннекторов. При тестировании использовался небольшой корпус неразмеченных русскоязычных предложений из ограниченного списка слов. Результаты показали хороший процент разбора и стабильное превосходство над биграмной моделью языка.

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

Следующим шагом в развитии статистического обучения грамматики является ввод вспомогательных данных (учет частей речи) и обучение на более крупных текстах. Обучение может происходить поэтапно, от простого к сложному, опираясь на результаты предыдущего шага, постепенно добавляя дополнительные слова, дизъюнктивные слагаемые и более длинные предложения.

Список литературы

[Протасов, 2005] Протасов С. В. Автогенерация семантических словарей с использованием грамматики связей для русского языка. //Процессы и методы обработки информации. М., 2005.

[Bahl et al., 1977] Bahl L. R., Baker J. K., Jelinek F., Mercer R. L. Perplexity - A measure of the difficulty of speech recognition tasks. //J. Acoust. Soc. Amer., vol. 62. 1977.

[Bahl et al., 1983] Bahl L. R., Jelinek F., Mercer R. L. A maximum likelihood approach to continuous speech recognition. //IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-5(2):179-190. 1983.

[Baum, 1972] Baum L. E. An inequality and associated maximization technique in statistical estimation of probabilistic functions of a Markov process. //Inequalities, 627(3):1-8. 1972.

[Brown, 1992] Brown P. F. Stepen A. L. An estimate of an upper bound for the entropy of English. //Computational Linguistics. 1992.

[Chomsky, 1957] Chomsky N. Syntactic Structures. //Mouton, The Hague, 1957.

[Collins, 1999] Collins M. Head-Driven Statistical Models for Natural Language Parsing. //PhD Dissertation, University of Pennsylvania. 1999.

[Jelinek, 1992] Jelinek F. Lafferty J. Mercer R. Basic methods of probabilistic context-free grammars. //In Speech Recognition and Understanding. 1992.

[Jelinek, 1992] Jelinek F. Statistical Methods for Speech Recognition. //MIT Press. 1997.

[Lafferty et al., 1992] Lafferty J. Sleator D. Temperley D. Grammatical Trigrams: A Probabilistic Model of Link Grammar. //Proceedings of the AAAI Conference on Probabilistic Approaches to Natural Language. 1992.

[Lari et al., 1990] Lari K. Young S. The estimation of stochastic context-free grammars using the inside-outside algorithm. //Computer Speech and Language. 1990.

[Manning and Schutze, 1999] Manning C., Schutze H. Foundations of Statistical Natual Language Processing. //Cambridge, MA: MIT Press, 1999.

[Mel'chuk, 1979] Mel'cuk I.A. Studies in dependency syntax. //Karoma Publishers, Ann Arbor, 1979.

[Mel'chuk, 1988] Mel'cuk I.A. Dendency Syntax: Theory and Practice. //State University of New York Press. 1988.

[Schneider, 1998] Schneider G. A Linguistic Comparison Constituency, Dependency, and Link Grammar. //Master's Thesis, University of Zurich. 1998.

[Sleator et al., 1991] Sleator D. Temperley D. Parsing English with a Link Grammar. //Carnegie Mellon University Computer Science technical report CMU-CS-91-196. 1991.

[Sleator et al., 1993] Sleator D. Temperley D. Parsing English with a Link Grammar. //Third International Workshop on Parsing Technologies. 1993.

[Yuret, 1998] Yuret D. Discovery of Linguistic Relations Using Lexical Attraction. //PhD thesis, MIT. 1998.

Размещено на Allbest.ru