Автоматический поиск переводных словосочетаний

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

Автоматический поиск переводных словосочетаний

В.И. Новицкий (nov.valerij@gmail.com)

МФТИ, Москва



Аннотация

автоматический словосочетание текст перевод

В работе описывается подход к автоматическому построению списка словосочетаний по корпусу выровненных параллельных текстов (текстов и их переводов, сопоставленных по предложениям).



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

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

Постановка задачи

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

Данная работа преследует следующие цели:

Получение словосочетаний (статистических данных) для улучшения работы синтаксического анализатора (применяемого в том числе в данной работе).

Расширение переводного словаря (так же используемого в данной работе) за счёт нахождения новых переводных статей.

Создание ТМ-базы (Translation memory) словосочетаний.

Известные подходы к решению задачи

Существует ряд известных работ, посвященных извлечению словосочетаний, В первую очередь следуют упомянуть работу [Smadja, 1993], считающуюся классической в этой области, В её основе лежит статистический подход. Словосочетания порождаются для слов, часто встречающихся совместно и в определённых позициях друг относительно друга.

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

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

Используемая терминология

Опишем терминологию, применяемую в данной работе:

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

Переводное словосочетание - словосочетание и его перевод на другой язык.

Значимое слово - семантически значимое слово, т.е. несущее смысловую нагрузку.

Грамматическое слово - служебное подчинённое слово, не имеющее самостоятельного семантического значения. К грамматическим словам относятся следующие части речи: предлоги, артикли, междометия, частицы и т.п.

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

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

Синтаксический анализатор (парсер) - алгоритм или его программная реализация, порождающая дерево синтаксического разбора по тексту предложения.

Дерево синтаксического разбора (дерево зависимостей) - специальное представление предложения в виде ациклического направленного графа (дерева), в котором вершинам соответствуют слова предложения, а рёбрам - связи между ними (подробнее будет описано ниже).

Используемые обозначения

Введём следующие обозначения:

- слово (в лингвистическом понимании).

- словосочетание (от англ. «collocation»).

- множество всех словосочетаний на одном языке и различной длины.

- переводное словосочетание (от англ. «parallel collocation»), т.е. словосочетание и его перевод на другой язык.

C^p = {c^p} - множество переводных словосочетаний.

- частота («frequency») переводного словосочетания в рассматриваемом корпусе текстов.

- ограничение сверху на длину словосочетания (количество неграмматических слов в словосочетании).

Виды представления синтаксической структуры предложения

Существуют два наиболее известных способа представления синтаксической структуры предложения [Bolshakov, 2004].

Дерево непосредственных составляющих.

Дерево зависимостей.

Представление синтаксической структуры предложения в виде набора составляющих было разработано в 50-х годах XX века на заре компьютерной эры американским лингвистом Ноамом Хомским (Noam Chomsky).

Представление синтаксической структуры деревом зависимостей изначально требует более тщательной проработки описания языка. Результатом разбора является дерево зависимостей (от главного слова к подчинённому), для которого нет ограничения на порядок слов в предложении (которые изначально накладывает представление контекстно-свободными грамматиками в модели Хомского).

Исторически первый подход (на основе составляющих) характерен для лингвистической школы Северной Америки, Англии, Второй (на основе деревьев зависимости) - для части Европы (Франция, Германия) и России.

Используемые средства

В работе используются следующие алгоритмы и данные, разработанные ранее в компании ABBYY:

Переводной словарь (русско-английский).

Синтаксический анализатор (парсер).

Алгоритм пословного выравнивания предложений.

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

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

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

Описание применяемого подхода

Поиск словосочетаний можно разделить на следующие этапы :

Пословное сопоставление предложений.

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

Генерация переводных словосочетаний.

Фильтрация кандидатов с учётом частоты их появления в корпусе текстов.

Сортировка полученных результатов (словосочетания и новые переводы для словаря).

Ниже рассмотрим каждый этап подробнее.

Пословное выравнивание предложений

Напомним, что пословное выравнивание - процесс сопоставления слов параллельных фрагментов текста. Мы используем словарь на основе семантических межъязыковых инвариантов. Здесь мы сталкиваемся с двумя основными сложностями:

Сопоставление омонимов (в случае неправильного выбора межъязыкового инварианта).

Сопоставление нескольких синонимов в предложении.

Первая проблема решается сравнительно легко. Мы можем взять всевозможные межъязыковые инварианты для слова и сравнивать их со всеми возможными переводами второго слова. В случае не пустого их пересечения можно считать, что слова сопоставились (табл. 1).

Табл.1. Пример пересечения множества межъязыковых инвариантов

Ключ	родник		Key
	…
	дверной	дверной
	решение	решение
		…
		клавиша

Вторая проблема интереснее и будет рассмотрена ниже. Простейшим способом её решения могло бы быть линейное (в порядке их появления в предложении) сопоставление синонимов.

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



Табл. 2. Нелинейное сопоставление синонимов.

Бегемот смотрел на него, а он - на бегемота.	He was staring at hippopotamus, and hippopotamus - at him

Применяемый в данной работе алгоритм сопоставляет предложения, опираясь на результаты работы синтаксического анализатора. Это позволяет учесть зависимости слов в предложении. В частности, в примере выше можно заметить, что в одной части предложения «бегемот» - дополнение при сказуемом («смотрел на бегемота»), а в другой - подлежащее. Обнаружив описанную (или аналогичную) зависимость в предложении, мы с уверенностью можем сопоставить рассматриваемые слова.

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

Генерация одноязычных словосочетаний

Наложим следующие ограничения на словосочетания (и их переводы):

Количество значимых (неграмматических) слов в словосочетании от одного до пяти ().

Слова образуют поддерево в дереве разбора предложения.

Среди слов словосочетания нет местоимений.

Вершиной синтаксического поддерева словосочетания не может быть грамматическое слово.

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

Должно быть не более одной «дырки» (разрыва в линейном представлении словосочетания в предложении).

Будем идти по дереву разбора и строить всевозможные сочетания слов, удовлетворяющие описанным выше критериям.

Перебор словосочетаний в предложении

Наша задача - перебрать всевозможные поддеревья дерева разбора предложения, удовлетворяющие описанным выше условиям (размер не более пяти слов, связанность и т.д.). При этом будет считать, что проверка «корректности» словосочетания имеет сложность.

Данная задача решается обходом дерева «снизу вверх». При этом в каждой рассматриваемой вершине для всех её дочерних вершин словосочетания уже построены, поэтому задача сводится к перебору всевозможных комбинаций текущей вершины и её дочерних словосочетаний: .

Генерация переводных словосчетаний

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

Разница в длине словосочетания и его перевода (без учёта грамматических частей) должна быть не больше одного слова.

Наличие пословных соответствий среди словосочетания (чем длиннее словосочетание, тем больше должно быть соответствий).

Для коротких словосочетаний (1-2 слова) пословных соответствий может не быть, но тогда должны совпадать предок корня и все исходящие вершины в дереве синтаксического разбора.

Если удалось сопоставить входящие или исходящие вершины одного из словосочетаний, то эти связи должны соответствовать соответственно входящим или исходящим вершинам второго словосочетания.

На этом этапе порождаются всевозможные словосочетания. На корпусе текстов размером 4,1 млн. фрагментов (параллельных предложений) получается порядка 62 млн. различных переводных словосочетаний, из которых только менее 6 млн. встречаются 2 и более раза.

Фильтрация кандидатов

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

Удаляем редкие словосочетания (предварительная фильтрация по частоте).

Удаляем словосочетания, содержащие стоп-слова (неинтересные нам запрещённые слова, например, артикли).

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

Аналогично удаляем вложенные словосочетания (например, «объединённых наций» - часть словосочетания «организация объединённых наций»), если их частота не сильно превышает частоту объемлющего словосочетания.

Из множества неоднозначных переводов выбираем наиболее вероятные. При этом проверяем, чтобы выбранный вариант был доминирующим (составлял не менее 90% от возможных переводов словосочетания).

Снова удаляем редкие словосочетания, но уже с большим порогом.

Удаляем известные словарные переводы.

Отделение новых (несловарных) переводов.

Количественные результаты

Эксперименты проводились на русско-английском корпусе, содержащем 4,2 млн. фрагментов (параллельных предложений).

Алгоритм порождения переводных словосочетаний даёт 62 млн. различных пар (всего порождается около 107 млн. словосочетаний). Из них подавляющее большинство (56 млн.) встречаются только один раз. Динамика количества остающихся словосочетаний на различных этапах фильтрации показана в табл. 3.

Табл. 3. Динамика фильтрации словосочетаний

Название фильтра	Слосочетаний на выходе	Время работы
По частоте (предварительно)	2,5 млн.	30 сек
По списку стоп-слов	1,1 млн	20
Грамматические дочки корня	793 тыс.	1 мин.
Вложенные словосочетания	568 тыс.	2 мин.
Неоднозначные переводы	105 тыс.	30 сек.
Словарные переводы	66,5 тыс.	5 сек.
По частоте (окончательно)	42 636	3 сек.
Отделение новых несловарных переводов	42 535	2 сек.

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

Можно заметить, что на последнем этапе наблюдается совсем небольшое количество отфильтрованных словосочетаний. Это можно объяснить тщательной проработкой словаря. Несколько примеров новых переводов, найденных на этом этапе приведены в табл. 4.

Табл. 4. Новые переводы (отсутствовали в используемом словаре)

Английский	Русский
Glib	бойкий
Meatball	фрикаделька
Ledger	гроссбух
Reciter	чтец



Несколько примеров найденных словосочетаний приведены в табл. 5.

Табл. 5. Примеры найденных словосочетаний

Английский	Русский	Встретилось в корпусе
job time	срок задания	12
galaxy space	космическое пространство	13
other foreign object	иной посторонний объект	5
air transport field	область воздушного транспорта	30



Заключение

Разработанный алгоритм показал свою практическую применимость, и используется сейчас в компании ABBYY.

Есть несколько направлений возможного дальнейшего его развития.

Более тщательная настройка параметров алгоритма (пороговых значений для фильтров).

Добавление новых фильтров (например, оценка «случайности» словосочетания на основе частоты его появления в корпусе, а так же частот всех входящих в него слов).

Сейчас основные усилия сосредоточены на первом пункте - выборе оптимальных параметров.



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

[Bolshakov, 2004] Bolshakov, I. A. Computational Linguistics: Models, Resources, Applications / I. A. Bolshakov, A. F. Gelbukh. -- IPN - UNAM - Fondo de Cultura Economica, 2004.

[Smadja, 1993] Smadja, F. A. Retrieving collocations from text: Xtract / F. A. Smadja // Computational Linguistics. -- 1993. -- Vol. 19, № 1.

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

...