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

Источник: Dept. Foreign Languages Wuhan University of Science and Engineering, 430073, Wuhan, P. R. China

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

Ключевые слова: морфологический анализ; статистическое обучение; межсекторная двусмысленность; комбинаторная неоднозначность; порядок формирования словоформ

Автоматический морфологический анализ (CMA) до сих пор является широко обсуждаемой темой в обработке естественного языка. Цель CMA является понять внутренний механизм формирования словоформ. Морфологический анализатор может предоставить ценную информацию для других компьютеризированных лингвистических задач, таких как лемматизация, синтаксический разбор, машинный перевод, получение информации, и многие другие.

Goldsmith (2001) классифицирует работу автоматического морфологического анализа четырьмя категориями. Классификация делается с акцентом на том, как формируются морфологические правила. Первая категория определяет границы морфемы на основе степени предсказуемости n+1 буквы с помощью n-буквы. Вторая использует грамматику н-грамм, чтобы с высокой вероятностью получить морфемную структуру. Третья категория стремится обнаружить правила через фонологические отношения между парами связанных слов. Четвертая ищет анализ для языка, который является самым кратким и, следовательно, сводится к набору правил для языка.

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

Машинное обучение является перспективной альтернативой для получения морфологических правил. Оно позволяет избежать дорогостоящий человеческий труд, исключает несогласованность и может предоставить дополнительную статистическую информацию, которая может быть использована в процедуре морфологического анализа. На основе информации, используемой в задаче машинного обучения, мы можем получить два класса обучения: контролируемое обучение и неконтролируемое обучения. Класс обучения с учителем (Bosch, 1999; Wicentowski, 2004) использует лексическую базу данных с морфологической информацией. Хорошим примером такой лексической базы данных является CELEX. Класс неконтролируемого обучения (Goldsmith, 2001; Kurino и др, 2004; Creutz, 2005) использует только список слов, с или без информации о частоте слов.

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

Другой метод морфологического разбора представлен моделью двухуровневой морфологии, предложенный Koskenniemi(1983). Эта модель учитывает морфологический анализ и морфологические трансформации в различных фонологических ситуациях и кодирует соответствие между формой слова и лексической формой с конечным числом состояний преобразователя. Например:

Первая система морфологического анализа, которая принимает эту модель – KIMMO (Karttunen,1983). Система состоит из двух частей: правила и лексическая информация, такая как структура морфемы и морфосинтаксическое ограничение.

Морфологический анализатор, представленный в данной статье, относится к первой классификационной группе. Система направлена на высокую точность морфологического анализа английского языка с морфологическими правилами, полученными с помощью неконтролируемого машинного обучения. Анализатор применяет переходные вероятности слов, которые предложили Keshava & Pilter (2005) в морфологическом обучении и правила неоднозначности морфологического анализа. Первоначальная оценка анализатора показывает 88,42% точность, которая обходит лучший результат для английского языка, представленного в Unsupervised Segmentation of Words into Morphemes – Challenge 2005.

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

Мы приняли подход, предложенный Kashava & Pilter (2005) в обучении аффикс-правил из словаря и протестировали подход с использованием списка слов различных объёмов. Наши эксперименты показывают, что аффикс-правила, полученные с помощью словарей разных объёмов, сильно отличаются. Различия охвата и правильность правил также приводит к разной производительности системы. Для того, чтобы обучить аффикс-правила используется лексикографическое дерево и встроенное обратное лексикографическое дерево. Потенциальные аффиксы распознаются через процедуру подсчета очков. Процедура подсчета очков состоит из двух шагов. На первой стадии рассматривают словоформу aАBβ. Если следующие три условия будут удовлетворены:

2. P(A|a)≈1, то есть, в прямом лексикографическом дереве переходная вероятность от a до А приблизительно равна 1;

3. P(B|aA)<1, то есть, в прямом лексикографическом дереве переходная вероятность от αA к B составляет менее 1;

то Bβ считается кандидатом в суффикс. Аффикс также может быть оценён с использованием лексикографического дерева в обратном направлении с симметричными условиями.

Второй шаг оценивает Bβ путем проверки все словоформ, заканчивающихся строкой этой. Функция подсчет очков приведена ниже:

Условие (а) указывает на то, что если строка заканчивается на Bβ, то Bβ удовлетворяет всем условиям, указанным в первом шаге, оценка Bβ в качестве суффикса растет (AwardScore). Условие (б) указывает на то, что если строка заканчивается на Bβ, то Bβ не удовлетворяет всем условиям – счет Bβ в качестве суффикса уменьшается (PenaltyScore). После проверки всех строк, заканчивающихся на Bβ, применяется золотой стандарт: если очки (Bβ) больше, чем 0, то строка Bβ рассматривается как суффикс. В противном случае, Bβ отбрасывается. Приставки обрабатываются подобным образом с помощью обратного дерева.

В таблице 1 приведены результаты эксперимента, полученные с помощью различных размеров словаря. Для прямого и обратного дерева мы используем свод из 24,447,034 токенов. Как показано в таблице, размер словаря, используемого при проверке условия (а), на первом этапе является одним из основных фактором, влияющим на количество префикс-правил, суффикс-правил и качество работы. Не трудно найти причину отличий: в английском языке не все словоформы могут быть использованы в качестве корня, из которого можно сформировать словообразовательные слова.

Таблица 1 – Сравнение результатов с разным размером словаря

3. Управление процедурой морфологического анализа

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

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

Межсекторная неоднозначность обозначает тип строк, которые имеют более одного возможного межсекторного анализа. Например, в строке «ABCD» B, CD, C, и D являются потенциальными аффиксами. Чтобы разрешить межсекторную двусмысленность, необходимо определить морфологическую границу. Посмотрим на следующий пример:

Межсекторная неоднозначность является часто встречающимся явлением в морфологическом анализе и является важным фактором, который является причиной неудовлетворительного анализа.

Keshawa & Pilter (2005) предлагают разрешать межсекторную двусмысленность, используя вероятности перехода между буквами. Посмотрим на следующие примеры:

(a) action → acti on TransProb(i,o) = 0.583511
action → act ion TransProb(t,i) = 0.500998

(b) aeroplaces → aeroplane s TransProb(e,s) =0.295008
aeroplaces → aeroplan es TransProb(n,e)=0.996983

Реальные морфологические границы во втором примере, как правило, имеют более низкие переходные вероятности, таким образом, правильно оказались определены. В нашем эксперименте фильтр устанавливается равным 0,40, и словоформа с переходной вероятностью меньше, чем 0,40, разделяется.

Но этот метод не работает для слов, которых не было при анализе переходных вероятностей. Не смотря на то, что обучающий словарь был большой, в нашем эксперименте всё ещё есть некоторые двусмысленные слова:

(a) pilation → pilati on TransProb(i,o)=0
pilation → pilat ion TransProb(t,i)=0

В таких случаях переходная вероятность не может помочь в устранении неоднозначности. В системе мы прибегали к аппроксимации, которая наиболее часто используется как результат анализа. В итоге, в примере 3 результат "ion", оказывается правым.

Комбинаторная неоднозначность в морфологическом анализе приводит к тому, что анализатор не может решить, имеет ли словоформа аффикс. То есть, имея словоформу АВ, в которой В является потенциальным суффиксом, мы должны решить, является ли AB словом и B не является аффиксом, или B действительно является аффиксом, а А – корень. Необходимо решить, где находится морфологическая граница внутри словоформы. Вот некоторые примеры:

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

Для решения комбинаторной двусмысленности, мы также решили полагаться на вероятность перехода между буквами. Решение может быть объяснено с соблюдением следующих действий:

Морфологическое граница, как правило, имеет гораздо более низкую переходную вероятность. Мы также установили фильтр равный 0,4 и разделяем те, которые имеют переходные вероятности меньше. Что касается примера 5d, где вероятность перехода букв равна 0 – ниже фильтра – мы также считаем реальным аффиксом, если после вычитания строка слева является словом в словаре. В таких случаях, переходная вероятность 0 указывает на то, что, хотя такого слова не было в обучающем словаре, слово содержит морфемы и словоформы и, вероятно, является новым словом.

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

Beard(1995) разделяет флективные и словообразовательные морфемы и утверждает, что эти два типа морфем ведут себя по-разному в словообразовании. Флективные морфемы образуют замкнутый класс вместо одного открытого; они допускают нулевые формы; они не допускают дальнейшее преобразование словоформ; и, наконец, они не могут быть парадигмально объединены. Словообразовательные морфемы, не имеют таких возможностей.

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

Лексическая морфема → словообразующая морфема → флективная морфема

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

При проведении анализа, который противоположен формированию словоформ, мы используем обратную последовательность:

Флективная морфема → словообразующая морфема → лексическая морфема

Точный алгоритм, принятый в системе, показан на рисунке 1.

Рисунок 1 – Блок-схема морфологического анализа, который является противоположностью образования словоформ

Таблица 2 – Сравнение результатов разных морфологических систем

Эксперимент был проведен для оценки эффективности анализатора, показанного выше. Результаты неконтролируемой сегментации слов в Unsupervised Segmentation of Words into Morphemes – Challenge 2005 представлены в таблице 2. Как видим, наш анализатор показал лучший результат, чем другие. Следует заметить, наш алгоритм превзошёл алгоритм, предложенный Pilter&Keshava (2005), на котором базируется современные анализаторы.

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

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

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

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

Тем не менее, проблемы остаются. Наиболее сложной является комбинаторная двусмысленность. Некоторые словоформы, такие как "as", "this" путем установления переходного вероятностного фильтра, могут быть не правильно проанализированы. И мы сомневаемся, что такая сочетаемость неоднозначностей может быть анализирована с помощью вероятностей переходов букв. Для правильного анализа необходимо больше информации, например, часть речи или контекст между словами. Это может быть темой наших будущих исследований.

1. Beard, Robert: Lexeme-Morpheme Base Morphology, a General Theory of Inflection and Word Formation. SUNY Linguistic Series, Albany SUNY Press (1995)

2. Bosch, Antal van den and Daelemans, Walter: Memory-based Morphological Analysis. In: Proceedings of the 37th Annual Meeting of the Association for Computational Linguistics, ACL'99, University of Maryland, USA, June 20-26, (1999) 285-292.

3. Creutz, Mathias and Lagus, Krista: Unsupervised Morpheme Segmentation and Morphology Induction from Text Corpora Using Morfessor 1.0. In: Publications in Computer and Information Science, Report A81, Helsinki University of Technology, (2005)

4. Daille, Béatrice, Fabre, Cécile & Sébillot, Pascale: Applications of Computational Morphology. In: Boucher, Paul, Plénat, Marc (eds.) Many Morphologies. Somerville, MA, Cascadilla Press (2002) 210–234

5. Goldsmith, John: Linguistica: An Automatic Morphological Analyzer. In: Okrent, Arika and Boyle, John (eds.) The Proceedings from Main Session of the Chicago Linguistic Society’s Thirty-sixth Meeing. (2000)

6. Goldsmith, John: Unsupervised Learning of the Morphology of a Natural Language. In: Computational Linguistics, Vol 27, number 2, (2001) 153-189

7. Karttunen, Lauri: KIMMO: A general morphological processor. In: Linguistic Forum 22, (1983) 163–186

8. Keshava, Samarth & Pitler, Emily: A Simpler, Intuitive Approach to Morpheme Induction. In: Proceedings of Unsupervised segmentation of words into morphemes -- Challenge 2005, Helsinki University of Technology, Helsinki, Finland (2005)

9. Koskenniemi, Kimmo: Two-level morphology: A general computational model for word-form recognition and production. Ph.D. dissertation, University of Helsinki, (1983)

10. Kurimo, Mikko et al: Unsupervised segmentation of words into morphemes – Challenge 2005 -- An Introduction and Evaluation Report. In: Proceedings of Unsupervised segmentation of words into morphemes -- Challenge 2005. Helsinki University of Technology, Helsinki, Finland, (2005)

11. Porter, M.F.: An algorithm for suffix stripping. In: Program 14, (1980) 130–137.

12. Wicentowski, R: Multilingual Noise-Robust Supervised Morphological Analysis using the WordFrame Model. In: Proceedings of Seventh Meeting of the ACL Special Interest Group on Computational Phonology (SIGPHON), (2004) 70-77.

Индекс	Размер словаря	Кол-во префиксов	Кол-во суффиксов	Точность (%)	Отзывы (%)	F-очки (%)
1	167377	683	1584	87.52	77.14	82.00
2	57046	694	1322	88.42	78.46	83.14
3	14760	373	989	90.57	72.43	80.49

Название	Автор	Точность (%)	Отзывы (%)	F-очки (%)
RePortS	Pitler and Keshava, Univ. Yale, USA	76.2	77.4	76.8
Cheatall	Atwell et al, Leeds and Helsinki	86.0	70.4	77.4
Cheattop5	Atwell et al, Leeds and Helsinki	83.2	74.6	78.6
Наша система		88.46	78.61	83.24