Microsoft Word - PalkoM.doc

ВЫВОД И ОЦЕНКА ПАРАМЕТРОВ ДАЛЬНОДЕЙСТВУЩЕЙ

ТРИГРАММНОЙ МОДЕЛИ ЯЗЫКА

INFERENCE AND ESTIMATION OF A LONG-RANGE TRIGRAM MODEL

Протасов С. В. svp@tj.ru

Московский Физико-Технический Институт (Государственный Университет)

Аннотация

В докладе описывается простая вероятностная грамматика связей (Link Grammar), известная также, как "Модель дальнодействующих триграмм" (Long-range Trigram Model). Эта вероятностная модель языка расширяет триграммные модели, предсказывая слова не только по двум непосредственно предшествующим словам в предложении, но и потенциально по любой паре стоящих рядом слов, которые лежат внутри этого же предложения. Таким образом, триграммная модель может пропускать менее информативные слова для более точного прогноза. Лежащая в основе "грамматика" есть не более, чем множество пар слов, которые могут быть связаны вместе через несколько разделяющих слов; это множество слов получается автоматически из корпуса текста, используемого для "обучения модели" грамматики. В докладе представлены результаты экспериментов, совершенные на корпусе предложений русского языка.

1 Вступление

В данной работе мы исследуем модель языка, которая может использоваться для практических задач, где требуется вероятностная оценка корректности предложений. В работе [Protasov 06] автором исследовалась более сложная модель и её реализация не позволила провести обучение (тренировку) на большом корпусе. В частности, использовался корпус около 3 тыс предложений со словарём примерно 300 слов. Конечно же в реальных задачах нам потребуются модели, которые позволяют обрабатывать корпуса размером на несколько порядков больше. Далее мы будем обсуждать одну из таких моделей, которая, по сути, является упрощением контекстно-свободной модели языка из работы [Protasov 06].

Наиболее широко используемой статистической моделью языка в настоящий момент является так называемая триграммная модель. В этой простой модели слово предсказывается на основе только лишь двух слов, непосредственно стоящих перед ним. Простота триграммной модели одновременно является и ее наибольшим преимуществом, и недостатком. Преимущество модели заключается в том, что для оценки параметров модели языка существует достаточно простой и быстро работающий алгоритм, который может обработать сотни миллионов слов текста. Реализация модели будет содержать внутри всего лишь поиск по большой таблице, что достаточно просто в практическом плане. Все новые статистические модели практически всегда оцениваются по отношению к триграммной модели. На сегодняшний день многие успешные системы распознавания речи в той или иной форме используют именно n-граммную модель (где n=2,3) [Jelinek, 97]. Несмотря на свои успехи триграммная модель ничего не знает о богатых синтаксических и семантических связях, которые содержат естественные языки, позволяя им быть легко распознаваемыми и понимаемыми людьми. Во многих реальных предложениях зависимые слова находятся на довольно большом расстоянии в 5-7 слов и триграммная модель никак не может учесть эти связи. Использование n-граммных моделей с п=5,6,7 требует гиганских ресурсов и сталкивается с проблемой "редких данных".

Вероятностная грамматика связей была предложена как подход, который сохраняет достоинства и вычислительные преимущества триграммной модели, и в то же время включает дальнодей-ствующие зависимости и более сложную информацию в статистическую модель [Lafferty et al. 92]. В этом докладе будет представлена реализация очень простого варианта вероятностной грамматики связей, которая (реализация) применима для любого естественного языка, включая

русский. Грамматика расширяет триграммные модели через разрешение связей между словами, предшествующими не только в пределах двух предыдущих слов, но и потенциально находящимися на большем расстоянии от предсказываемого слова в пределах предложения. Таким образом далънодействующая триграммная модель может пропускать малоинформативные слова и улучшать предсказуемость в модели. Лежащая в основе грамматика представляет собой множество пар слов, которые могут быть соединены друг с другом через несколько промежуточных слов. Впервые далънодействующая триграммная модель была предложена в работе [Pietra et al. 94], где она исследовалась на англоязычном материале, но к сожалению результаты исследований ученых из IBM не были подтверждены независимо, не говоря уже о доступности каких-либо программных реализаций модели, а публикации по исследованию на корпусах других языков отсутствуют до сих пор.

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

2 Дальнодействующая триграммная модель

В качестве примера рассмотрим рисунок 1. На диаграмме представлена связка (linkage) предложения "Если у Вас есть ... заработать.", согласно формализму, впервые введенному в [Sleator and Temperley, 91], важными свойствами связки является непересечение связей, их связность (отсутствие неприсоединенных областей), единственность связей (каждая пара слов соединена только одной связью). Рассматривая вероятностную модель, мы считаем, что каждое слово генерируется из биграммы заканчивающейся словом, примыкающим к генерируемому слову слева. Таким образом, первая правая скобка сгенерирована на основе биграммы (сайт|(), а первое слово "сайт" сгенерировано из биграммы (есть(свой). Слово "то" сгенерировано из биграммы (_1_, |Если), где _1_ является специальным словом-границей.

еУМЙ Х чБУ ЕУФШ УЧПК УБКФ ЪРФ ФП ТЕЗЙУФТБГЙС ДБУФ ЧПЪНПЦОПУФШ : ЧП-РЕТЧЩИ ЪРФ ТБУЛТХФЙФШ

сЧой сайт ( баннеры Ч нашей сети имеют хороший CTR ) зпт Чо-Чторых зпт заработать тчк

Рис. 1: Дальнодействующие триграммы.

Для описания модели более детально, рассмотрим следующее описание стандартной триграммной модели. Модель может быть рассмотрена как простой конечный автомат, генерирующий предложения. Состояния этого автомата проиндексированы парами слов. Добавив слово-границу _1_ в наш словарь слов, мы зададим начальное состояние конечного автомата как (_1_,_1_) . Когда автомат находится в каком-либо состоянии (w1,w2) , он может перейти в состояние (w2,w₃), с вероятностью t(w3\w1w2) и остановится с вероятностью t(_1_ \w1w2) , таким образом остановив предложение.

Наша расширенная триграммная модель может быть описана похожим образом. Для ссылки на состояния автомата используются пары слов, но состояние s = (w 1,w2) теперь может быть одним из трех: останов (halt), шаг (step), ветвление (branch) с вероятностями d(halt\s) , d(step\s)₇

d(branch|s) соответственно. В случае выбора состояния step или branch, следующее слово w генерируется с триграммной вероятностью t(w|w1,w2)- Но в случае выбора branch генерируется дополнительное слово w на основе дальнодействующей триграммы l(w'|w1,w2)- Например, в процессе генерирования связки из примера выше, состояние с индексом s = (то,регистрация) приводит к состоянию step с вероятностью d(step|s) и слово "позволит" затем генерируется с вероятностью t(позволит|то,регистрация) С другой стороны, состояние s = (_1_,Если) ответвляется с вероятностью d(branch|s) и затем из этого состояния генерируется слово "у" и слово "то" с вероятностью t(у| _1_Если) и l(to| _1_Если) .

В результате все слова в связках, как на примере выше, имеют ровно одну связь слева и ноль, одну или две связи справа. Если мы пронумеруем слова в предложении S от 1 до |S|, тогда вполне удобно обозначать через ⊳i индекс слова, которое генерирует слово слева от i-ro в предложении. Таким образом, i соединено слева с ⊳i . Например, на связке из примера выше мы видим, что ⊳9 = 8 , ⊳8 = 1 , и ⊳26 = 18 . Подобная запись позволяет нам записать вероятность предложения как P(S) = Ylag) P(S,L), где L(S) есть набор всех связок S и где соединяющая вероятность P(S, L) расписывается как

\s\
(1) P(S,L) = nd(d_i|w_i,w_i-1)t(w_i|w_i-2w_i-1)⁽ⁱ-¹^l(w_i|w_i-1w_i)¹-^(i-1'^

i=1

Здесь di € halt, step, branch, δ(i,j) равен единице, если i = j , и нулю, если не равен. Индекс ⊳i должен пониматься по отношению к заданной связке L .

В терминах грамматики связей [Sleator and Temperley, 91] переменные halt , step и branch эквивалентны трем простым дизъюнктам, определяющим, как заданное слово соединяется с другими словами. Значение halt соответствует дизъюнкту, имеющему один левый коннектор (без метки) и не имеющий правых коннекторов. Значение step соответствует дизъюнкту, имеющему единственный левый и единственный правый коннектор. Значение branch соответствует дизъюнкту имеющему один левый коннектор и два правых коннектора. В формализме данной грамматики вероятностная модель (1) является простым вариантом более общей вероятностной грамматики связей, представленной в работе [Lafferty et al. 92].

На этом мы закончим сверхкраткое введение в дальнодействующие триграммные модели и за дополнительной информацией рекомендуем обратиться к работе [Pietra et al. 94]. Там же дано описание эффективного алгоритма "обучения" модели (что равносильно выводу грамматики). Целью алгоритма является увеличение суммы (1) по всем предложениям в обучающем корпусе. Алгоритм "обучения" хоть и является разновидностью ЕМ (Expectation-maximization, разновидность алгоритма максимизации правдоподобия) [Вашп 72], в действительности довольно сильно отличается от популярного подхода Inside-Outside [Lari and Young, 90], который часто использ-утеся для обучения формальных вероятностных моделей [Manning and Shutze, 99].

3 Вывод грамматики

Вероятностная модель (1), описанная в предыдущем разделе, делает свои предсказания на основе как обычных триграммных моделей, так и на основе дальнодействующих триграмм. Мы можем разрешить использовать связи со словами, присоединяющееся слева к любому слову. Это соответствует "грамматике", которая разрешает дальнодействующие связи между любыми двумя словами. Число возможных связок для такой грамматики растет очень быстро с увеличением длины предложения: если предложение состоящие из 10 слов имеет всего-лишь 835 связок, то предложение, состоящее из 25 слов уже имеет 3 192 727 797 связок. Однако большинство дальнодействующих связей в этих связках скорее всего будут неправильными. Получившаяся вероятностная модель имеет слишком много параметров, которые не могут быть достаточно точно оценены. А для целей качественного обучения нам требуется высокое отношение "число примеров/число параметров".

L	R	log(Gain_LR)	d(branchLR\L)	dLR(halt) ^:
( Если либо и Ни Чем столько Чем больше Что касается ни	) то либо II ни тем сколько тем то ни	11.05 8.81 8.44 8.33 7.92 7.78 7.76 7.66 7.47 7.43	0.8558 0.3541 0.3398 0.2171 0.4228 0.4414 0.2661 0.9585 0.7549 0.2123	4.4 7.1 4.2 7.9 2.6 5.0 2.6 4.2 3.5 2.8
Чем больше Ни одна Чем дольше кроме тех случаев только в том случае Никакой Что касается	тем не тем когда если не то	7.66 5.92 5.83 5.14 7.21 5.22 7.47	0.9585 0.9364 0.9157 0.9241 0.7349 0.7549 0.7549	4.2 2.8 4.2 1.2 1.1 3.1 3.5
Интересно Даже если Во-первых Неужели Разве Ах Если Почему Сначала Одна	? все равно во-вторых ? ? ! то ? потом другая	5.73 5.25 6.08 7.17 6.57 6.54 8.81 7.41 5.77 5.04	0.2437 0.1187 0.1294 0.4026 0.2864 0.4918 0.3541 0.3296 0.2168 0.0877	8.8 8.7 8.5 7.6 7.6 7.4 7.1 7.0 6.3 6.1
отличить не обращал избавить споткнулся Одним из отделить превратить Делать прижала обращать Целью нашелся Прошло поблагодарить	от внимания от упал является от в нечего к внимание является ответить прежде чем за	6.49 6.12 5.88 5.86 5.81 5.68 5.36 5.30 5.17 4.91 4.84 4.55 4.53 4.48	0.6775 0.5178 0.7158 0.3114 0.4638 0.6820 0.6560 0.4220 0.6869 0.2997 0.5089 0.2091 0.1653 0.4136	1.7 2.1 1.2 2.3 4.3 1.8 1.7 2.1 1.3 2.0 2.1 1.9 3.0 1.5

Таблица 1: Примеры пар слов

Раз неограниченная грамматика непрактична, мы попробуем ограничить грамматику через разрешение только тех дальнодействующих связей, которые приносят наибольшие улучшения в вероятностную модель. В идеале нам нужно автоматически выявлять пары слов, такие как "(" и ")" с дальнодействующими корреляциями, которые могут быть хорошими кандидатами на соединение через дальнодействующую связь. Мы можем поискать такие пары через просмотр слов с высокой взаимной информацией. Но если мы представим, что мы уже включили связи всех ближайших соседей в нашу модель, как в случае модели (1), то у нас не будет точек для связывания слов L и R , независимо от того, насколько велика их взаимная информация, ведь слово R уже хорошо предсказывается непосредственными предшествиниками. Вместо этого мы будем искать связи между словами, которые имеют потенциал улучшения модели только по сравнению с обычными короткими связями.

Рис. 2: Модель LR.

Для нахождения таких пар используем следующий подход. Пусть V - словарь языка. Для каждой пары (L, R) € V х V сконструируем модель Plr, которая содержит все связи биграммами с одной дополнительной дальнодействующей связью, идущей от L к R . На основе анализа корпуса русскоязычных предложений мы определим пользу пары (L, R) по сравнению с биграммной моделью.

Мы выбрали модель Plr достаточно простой, чтобы параметры всех \V\ возможных моделей оценивались параллельно. Затем мы отсортируем модели согласно их правдоподобию GainLR [Pietra et al. 94], которую каждая модель показывает на обучающем корпусе, и выберем те пары (L, R), которые соответствуют самым лучшим моделям. Этот список пар слов и будет составлять нашу новую "грамматику", описанную в предыдущем разделе.

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

Этот раздел представляет результаты обучения наших дальнодействующих триграммных моделей на корпусе предложений, собранных через интернет. Наш обучающий корпус состоял из более чем 11 млн. предложений, содержащих примерно 150 млн. слов. Таблица 1 включает примеры пар слов, которые были получены после использования формул из раздела 3. Напомним, что эти пары были получены при первом шаге обучения грамматики связей, которая позволяет дальние связи между одной фиксированной парой слов. Каждая пара проверяется уменьшением энтропии, которая ее односвязная модель достигает по сравнению с биграммной моделью. В таблице это улучшение показано в 3-м столбце. Мы сразу отсекаем все пары, которые не приводят к уменьшению энтропии. В первой секции таблица содержит пары, которые приводят к наибольшему уменьшению энтропии. Четверый столбец таблицы дает значения вероятности d(branch_LR\L) . Это значение показывает вероятность, с которой L генерирует R с некоторого расстояния в соответствии с обучаемой моделью. Вторая секция таблицы включает примеры пар с высоким значением вероятности d(branchLR\L) . Пятый столбец таблицы дает значения вероятности dLR(halt)~^l. Поскольку в обучающих данных число слов между L и R убывает геометрически со средним d_LR(halt)~ , то большое значение в этом столбце указывает, что L и R находятся в среднем на достаточно большом расстоянии. Третья секция таблицы приводит примеры таких пар. В заключение, четвертая секция таблицы показывает пары, где одно из слов является глаголом, и только некоторые из этих пар с наибольшим уменьшением энтропии показаны в таблице. Мы довольны результатами, так как полученные списки пар практически не содержат мусора, который в избытке появляется при использовании других методов. Однако из-за нечеткости критерия "что есть мусор", нам очень сложно провести численное сравнение. Более того, нам вообще

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

5 Выводы и планы

Полученные данные позволяют сделать вывод, что модель дальнодействующих триграмм представляет собой еще один инструмент корпусной лингвистики. Этот инструмент, в частности, позволяет автоматически устанавливать факт наличия синтаксической связи между словами, не стоящими рядом. Полученная "грамматика пар слов" может быть использована для инициализации более сложных вероятностных моделей. Исследование пар, отфильтрованных по частям речи, может помочь в изучении "дальних" валентностей глаголов, а также составлению списка глаголов, потенциально имеющих большое число валентностей. Было бы интересно изучить таким способом какой-либо мертвый язык, имеющий достаточно большой корпус текстов. Однако наша долгосрочная цель - не словарь парных слов, а более мощная статистическая модель языка. Если в процессе тренировки модели мы получаем качественный словарь, содержащий мало мусора, то это хорошее свидетельство того, что мы движемся в правильном направлении. После того как мы получили список пар кандидатов, имеющих дальние связи, нам нужно провести несколько шагов пере-инициализации параметров Expectation - Maximization. Данная процедура может существенно изменить вероятности связей и даже сделать какие-либо из них несущественными для грамматики. Несколько шагов тренировки могут привести к дальнейшему отсеву мусора среди пар кандидатов. К сожалению, делать переобучение нужно не целиком в основной памяти компьютера (для больших словарей порядка 100 тыс слов её может не хватить), а через последовательную обработку файлов корпуса на жестком диске. Данный этап работы автором еще не завершен. Кроме этого, качественная статистическая модель обязательно содержит процедуры сглаживания, а это требует дополнительного программирования.

Так как каждая пара приводит к уменьшению кросс-энтропии корпуса, то все пары в сумме также гарантировано должны приводить к снижению кросс-энтропии. Однако нам неизвестно, насколько велико будет суммарное улучшение и будет ли оно существенно лучше n-gram моделей. Проводить сравнение несглаженной дальнодействующей модели со сглаженной n-gram моделью не вполне корректно, так как несглаженные модели существенно хуже, чем сглаженные. После настройки параметров вероятностной модели, мы можем подключить нашу модель языка в какую-либо практическую систему для измерения качественных результатов. К примеру известно, что в системах распознавания речи, где также используются статистические модели языка, число ошибок линейно уменьшается в зависимости от кросс-энтропии. Мы также можем подключить модель языка к системе статистического машинного перевода и измерить улучшение по стандартной BLEU метрике, хотя у нас есть подозрения, что BLEU метрика не увидит улучшения, так как использует ngram-совпадения при сравнении переводов. Человеческие оценки качества перевода несколько затратны и не могут быть осуществлены для больших корпусов. Таким образом, за неимением лучшего, мы будем использовать кросс-энтропию на тестовом корпусе как самый главный критерий качества нашей языковой модели.

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

[Protasov 06] Протасов С . В . Обучение с нуля грамматики связей русского языка. //Десятая национальная конференция по искусственному интеллекту с международным участием., КИИ-2006.

[Lafferty et al. 92] 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.

[Pietra et al. 94] Pietra S., Pietra D., Gillet J., Lafferty J., Prinz H., Ures L. Inference and Estimation of a Long-Range Trigram Model. //Grammatical Inference and Applications, Second International Colloquium, ICGI-94, 1994.