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

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

На правах рукописи

4854679

Кан Дмитрий Александрович

ПРИМЕНЕНИЕ ТЕОРИИ КОМПЬЮТЕРНОЙ СЕМАНТИКИ РУССКОГО ЯЗЫКА И СТАТИСТИЧЕСКИХ МЕТОДОВ К ПОСТРОЕНИЮ СИСТЕМЫ МАШИННОГО ПЕРЕВОДА

05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических

наук

Санкт-Петербург 2011

2 9 СЕН 2011

4854679

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

Научные руководители:

Официальные оппоненты:

доктор физико-математических наук, профессор [Тузов В.А.1 кандидат физико-математических наук, доцент Сергеев С. Л.

доктор физико-математических наук, профессор Братчиков Игорь Леонидович (Санкт-Петербургский государственный университет)

кандидат физико-математических наук, доцент Комаров Игорь Иванович (Филиал Военно-Учебного Научного Центра ВВС, Военно-воздушная академия, г. Санкт-Петербург)

Ведущая организация:

Санкт-Петербургский экономико-математический институт Российской академии наук

Защита диссертации состоится «_» 2011г. в /О

часов на

-- ----- - - • « п а

заседании совета Д 212.232.51 по защите докторских и кандидатских диссертаций при Санкт-Петербургском государственном университете по адресу: 198504, Санкт-Петербург, Петродворец, Университетский пр. 28, математико-механический факультет, ауд. 405.

С диссертацией можно ознакомиться в Научной библиотеке им. М. Горького Санкт-Петербургского государственного университета по адресу: 199034, Санкт-Петербург, Университетская наб., д. 7/9.

Автореферат разослан » 2011 года.

Учёный секретарь диссертационного совета доктор физико-математических наук, доцент

Кривулин Н.К.

1. Общая характеристика работы

Актуальность работы. Машинный перевод (МП) как область искусственного интеллекта развивается более 50 лет. Выделяется два фундаментальных направления: классическое (многоуровневая формализация естественного языка) и численное (выявление и использование совместных статистических характеристик языков на основе параллельных текстовых корпусов). В настоящий момент становится очевидным, что для эффективного и качественного решения задачи необходимо предпринимать попытки соединения обоих направлений Примеры существующих систем МП свидетельствуют о потребности в повышении качества МП путем перехода на уровень семантического анализа предложений и текстов. Приобретают особую важность методы, позволяющие в автоматическом режиме строить переводные словари дга подобных систем, а также классические и статистические алгоритмы синтеза конструкций естественного языка (ЕЯ) по семантическим структурам.

В основе алгоритмов и методов настоящей работы лежит компьютерная семантическая модель русского языка, разработанная В.А. Тузовым. К двум наиболее существенным результатам работы для МП относятся алгоритм линеаризации предложений по их семантическому представлению и метод автоматического построения переводного семантического словаря с русского на английский язык. Алгоритм линеаризации реализует тезисы И. А. Мельчука об иерархической линеаризации в рамках семантической теории русского языка и является важным компонентом системы МП, использующей компьютерную семантику в качестве фундаментального подхода к решению задачи. Переводной семантический словарь строится посредством сочетания формальной модели ЕЯ (компьютерная семантика русского языка) и численного моделирования параллельных корпусов текстов. Сочетание двух указанных методов для построения переводных словарей производится впервые.

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

Направления исследований:

1. Сравнение функциональной теории языка В. А. Тузова с более ранними моделями ЕЯ и статистическими подходами к формализации ЕЯ.

2. Исследование применимости функциональной теории к задачам синтеза предложений, построения переводных семантических словарей и самой задаче машинного перевода.

3. Изучение задачи анализа текста в контексте МП.

4. Изучение существующих подходов к МП, опубликованных в научной литературе.

5. Исследование задач МП, для которых оправданно сочетание теории компьютерной семантики и статистических методов.

Методы исследования, достоверность и обоснованность результатов. В

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

На защиту выносятся:

1. Алгоритм линеаризации семантических структур для синтеза предложений на русском языке и его программная реализация.

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

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

4. Переводной семантический словарь с русского на английский с количеством статей порядка 18 тысяч.

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

6. Прототип системы МП, базирующийся на построенных в работе методах и переводных словарях, объёмом 7 тысяч строк программного кода.

Научная новизна результатов исследования. Исследованы основные известные алгоритмы статистического МП, являющегося в последнее десятилетие наиболее популярной темой в западной литературе. Результатом исследования является анализ применимости методов статистического МП к построению системы МП в рамках функциональной модели ЕЯ Тузова.

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

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

па политехническом симпозиуме «Молодые учёные _

промышленности северо-западного региона» (С.-Петербург, 6 декабря 2007г.);

2. на научном семинаре по информационному поиску кафедры технологии программирования факультета ПМ-ПУ СПбГУ (С.-Петербург, 23 апреля 2009г.);

3. на ХЬ конференции «Процессы управления и устойчивость» (С.-Петербург, 6-9 апреля 2009г.);

4. на 6-м семинаре «Р1ШСТ» (Хельсинки, Финляндия, 3-6 ноября 2009г.);

5- на научном семинаре кафедры информатики математико-

механического факультета СПбГУ (С.-Петербург, 12 мая 2011 г.).

Публикации. По теме диссертации опубликовано 6 работ [1-6], из них три работы [1-3] в журналах, входящих в список ВАК. Статьи [2-4] и [6] написаны в соавторстве. В статье [2] соискателю принадлежит метод разрешения анафорических ссылок, соавторам — методы идентификации объектов текста. В статье [3] соискателю принадлежит исследование задачи формализации связей в контексте машинного перевода и синтеза предложений, соавтору — методы формализации связей в тексте при обработке естественно-языковых конструкций. В статье [4] соискателю принадлежит формулировка базовых принципов линеаризации семантических структур и их алгоритмическая реализация, соавтору — описание основ теории компьютерной семантики русского языка. В статье [6] соискателю принадлежит компактное представление теории компьютерной семантики в контексте основных задач обработки естественного языка таких, как машинный перевод, соавтору — список идей практического применения теории компьютерной семантики в программных продуктах.

Структура и объём диссертации. Диссертация состоит из введения, четырёх глав, заключения, библиографического списка и приложения. Текст диссертации изложен на 120 страницах машинописного текста, содержит 13 рисунков и 10 таблиц. Библиографический список содержит 70 наименований.

Содержание работы

Во введении описываются уровни задачи формализации ЕЯ и основные подходы к МП в настоящее время. Кратко описывается структура диссертации.

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

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

В третьей главе делается обзор основных подходов к синтезу предложений на ЕЯ. Далее в главе ставится и решается задача линеаризации семантических структур как частная задача синтеза предложений. Приводится реализованный на практике алгоритм линеаризации, а также обсуждается его роль для МП. Общепринятый в западной научной литературе статистический подход к синтезу предложений рассматривает последовательность слов W/,..,w„ переведённого предложения на языке L, без отношения порядка. В частности, ставится задача переупорядочивания слов в рамках некоторой вероятностной языковой модели ЦМ. Результатом такого переупорядочивания должны быть грамотные предложения на целевом языке, подобно тому, как это сделает носитель языка. Введя меру плотности данной подпоследовательности слов длины два (биграммы) над языковой моделью (L' есть совокупность Z, и знаков препинания языка):

X! Л I '' W>Wi €

Ö(W.,W.)= J 1 ' ,

' У 1 0, wiw) iL\M

легко найти плотность всей последовательности слов данной цепочки:

п~\,п

П(и>w )= £ S(w.,w.).

' = \,j = 2 ' J

Тогда множество д наиболее связных цепочек слов в силу модели L\M строится следующим образом:

Д=аг£тахП (w.....w ),

i-I.ii! Л 1 П

где Slk есть значение плотности к-й перестановки слов w,.....w„. Однако

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

We would like to express our thanks to various people, данный метод переупорядочивания помимо исходного предложения предлагает и абсолютно неверный вариант:

Our thanks to various we would like to express people. Видно, что вторая цепочка локально связна синтаксически и почти всегда семантически ("our thanks to", "to various", "we would like to", "to express", "express people"), но не связна семантически, как единое целое. В процессе семантического анализа предложения по теории В. А. Тузова вычисляются аргументные зависимости между словами предложения. Итогом анализа является согласованное семантическое дерево, в котором каждому узлу приписан номер семантического класса и, если есть, семантико-грамматический тип (СГТ), порождаемый словом в этом узле. По набору основных характеристик (лицо, часть речи, падеж и СГТ) можно определить роль, а, следовательно, и место, данного слова в предложении. Имея согласованное семантическое дерево, мы рассматриваем задачу синтеза предложения как иерархический процесс, при котором отдельные слова образуют корректные семантические и синтаксические группы, а группы формируют выходное предложение (линеаризация). Каждому узлу в семантическом дереве приписывается СГТ: @Им, @Вин, @ДееКак, @Где, @Род и т.д. Каждую функцию-слово f можно представить по отношению к её аргументам xix2...xn либо в виде префиксной записи: fx, хг... хп, либо в инфиксной записи: х, х2.../... хп, либо в постфиксной записи: х2... xnf. В частности, существительные выводятся в постфиксной записи по отношению к прилагательным: функция Маша(замечательная) записывается как «замечательная Маша». Предлоги есть функции в префиксной записи: в(магазин) интерпретируется как «в магазин». Глаголы являются в общем виде функциями в инфиксной записи: пошла(Маша(замечательная), в(магазин)) интерпретируется как «замечательная Маша пошла в магазин». Рекурсивно группируя поддеревья семантического дерева по СГТ их корневых узлов, получаем семантическую структуру грамматически правильного семантически связного предложения. Для непосредственного синтеза предложения по его

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

• обмену подлежат только узлы на одном уровне в семантическом дереве и с одним общим родителем;

• причастные и деепричастные обороты образуют единую неделимую группу слов;

• однородные члены, отвечающие на один смысловой вопрос, могут быть упорядочены лексикографически;

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

В четвёртой главе детально описываются наиболее известные алгоритмы статистического МП. Затем МП рассматривается в рамках функциональной теории В. А. Тузова. Ставится и решается задача автоматического построения переводного семантического словаря, как ключевого компонента системы МП. Результатом решения является переводной контекстный семантический словарь. Описываются алгоритмы динамического моделирования контекста при переводе. На основе предложенного метода динамического моделирования контекста строится расширение метода для генерации переводного словаря предложно-падежных групп. Построенные компоненты и методы составляют фундамент авторской экспериментальной системы МП с русского на английский язык. В случае перевода с одного ЕЯ на другой ЕЯ семантический язык выступает в роли универсального промежуточного представления, а центральным компонентом системы перевода выступает переводной семантический словарь. Схема его автоматического построения выглядит следующим образом:

СКА (параллельный корпус) + семантический анализатор = переводной контекстный семантический словарь

Задача статистического МП формулируется как задача максимизации по е условной вероятности Р(е\]), где/есть предложение на иностранном языке Р, и е есть предложение на целевом языке Е. Распишем вероятность Р(е\/) по теореме Байеса:

I«). (1)

Максимизируя по e и опуская знаменатель, не зависящий от е, получим

фундаментальное уравнение статистического МП:

max Р(е \ /) = argmax P(e)P(J | е). е е

Алгоритм GIZA вычисляет совместную вероятность P(f\e) из правой части полученного равенства и выводит те цепочки слов на двух языках, соответствие которых друг другу наиболее вероятно. В результате работы данного алгоритма был получен корпус из 1,3 миллиона параллельных цепочек слов на русском и английском языках. Для снятия неоднозначностей был применён семантический анализ русского языка по методу В. А. Тузова. Для этого каждое из 90 тысяч предложений на русском языке параллельного корпуса было обработано анализатором, и слова на русском языке в словаре были заменены на их семантические формулы в рамках одного переводного контекста (т.е. в рамках одной пары русского и английского предложений). Приведём псевдокод алгоритма генерации переводного семантического словаря:

Function Diet build_sema_translational_dict {

GIZADict = build_giza_dict(parallel_corpora) SemaOutput = annotate_sema( parallel_corpora) TranslationalSemaDict = [] for Vsent e GIZADict for V(word _ sre, word _ tar) e sent

sema_formula=get_sema_formula(word_src, SemaOutput) TranslationalSemaDict[seraa_formula]=word tar

return TranslationalSemaDict }

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

русском языке подыскивалась альтернатива на английском языке при помощи следующей эвристики: первому предлогу предложения на русском языке соответствует первый предлог в предложении на английском языке, второму предлогу - второй предлог в английском предложении и т.д. Так как предлог является корневым элементом своей ПП группы, были выделены его прямые аргументы из соответствующего поддерева семантического дерева предложения. Для обобщения переводной формулы предлога (на) его аргументы (столе) были заменены семантическими классами и семантико-грамматическими типами ($12~@Пред) и приписаны в квадратных скобках к семантической формуле предлога. Для словосочетания «на столе» получаем: НА Yl>Loc(Y1:,ПРЕД:Z1) \\ <93>[$12~@Пред]—>оп

Машинный перевод осуществляется отображением входного предложения на русском языке на семантический язык. Далее каждому слову ищется альтернатива в переводном контекстном семантическом словаре. Если альтернатива найдена, её аналог на английском языке копируется в выходную последовательность слов. В противном случае копируется исходное слово. Помимо прямого сопоставления отдельно анализируются связи слов, вовлекающие семантико-грамматические типы. Завершающий шаг — сборка английского предложения по семантическому дереву. На этом шаге возможно использования двух подходов: иерархическое либо статистическое переупорядочивание (гл. 3). Следующий псевдокод описывает алгоритм перевода предложения на более формальном уровне:

Function Sentence translatel(InputSentence) {

SemaOutput = analyze(InputSentence) TranslationalSemaDict = LoadDictO Sentence OutputSentence for Vword <= InputSentence

sema_formula=get_sema_formula(word,SemaOutput)

word_target = TranslationalSemaDict[sema_formula] if (3word_target)

OutputSentence = OutputSentence + word_target

else

OutputSentence = OutputSentence + word OutputSentence=transiate2(SemaOutput,OutputSentence) return OutputSentence

}

При втором проходе система обрабатывает ППТ:

Function Sentence translate2 (SemaOutput, OutputSentence) {

TranslationalSemaDict = LoadDictO

// PCT=Prepositional Case Type (предложно-падежный тип) for VPCr e InputSentence

s eraa_formu1a=ge t_sema_fo rmu1a(word,SemaOutput)

word_target = TranslationalSemaDict[sema_formula] if (3word_target)

OutputSentence =. OutputSentence + word_tar else

OutputSentence = OutputSentence + PCT return OutputSentence

}

В силу того, что переводной семантический словарь содержит «шумы» (например, GIZA может сопоставить слову на русском языке несколько переводов, в числе которых могут оказаться знаки препинания или комбинации слов на английском языке, не имеющие прямое отношение к данному слову), необходим метод их уменьшения. Назовём этот метод SMTM (от англ. Semantic Machine Translation Model - семантическая модель машинного перевода). Рассмотрим произвольное предложение Р на русском языке (обозначим русский язык через F), состоящее из слов lvi'--vV Следуя приведённому выше алгоритму перевода, на первом шаге построим множество S всех семантических формул, соответствующих словам предложения Р: 4wlePeF3semle:S:seml=sema(w,),i = T^i,

где sema есть функция семантического анализа, переводящая слово w¡ в данном предложении Р в его семантическую формулу sem¡. Используя переводной семантический словарь, на втором шаге получим множество переводов семантических формул на английский язык Е:

Улет, б5Э^/}е£,у = 1,т,т>/1,

где {Г;} есть указанное множество переводов. Используя формулу плотности цепочки слов, запишем определение модели перевода БМТМ для данного предложения Р:

Индекс 5 в записи функций ¿/и П,1 указывает на то, что областью их определения является множество семантических формул, записанных на языке Ь2 = Е.

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

с

БМТМр = а^тахПу

/=1 ,п

где:

а^тах (/£,//),

к=1т-1

1=2, т

1,

О, й ь'2м

Публикации автора по теме диссертации Статьи в журналах, рекомендованных ВАК:

1. Кан Д. А. Задача синтеза предложений на естественном языке // Вестник СПбГУ, Сер.10, Вып.З. — 2009. — С. 205-212.

2. Кан Д. А., Лебедев И. С., Сухопаров Е. А. Идентификация объектов 2009™ Г'сТГТбГ СИСТеМаХ " ПР01?аммные продукты и системы,

3. Кан Д. А., Лебедев И. С. Способ формализации связей в тексте при обработке естественно-языковых конструкций // Вестник СПбГУ Сеп 10 Вып.2, — 2008, — С. 56-61. ' Другие публикации:

4. Кан Д. А., Лебедев И. С. Линеаризация при синтезе предложений на естественном языке // Политехнический симпозиум «Молодые ученые -промышленности Северо-Западного региона»: материалы конференций. СПб.: Изд-во С.-Петерб. политехи, ун-та, 2007. С. 15-16.

5. Кан Д. А. Метод автоматического построения переводного семантического словаря для машинного перевода // Процессы управления и устойчивость: Труды 40-й научной конференции аспирантов и студентов -СПб.: СПбГУ, 2009.-С.429-434.

6 Kan D„ Poroshin V. Semantic Analysis: Theory, Applications and Use Case // Proceedings of 6й1 Seminar of Finnish-Russian University Cooperation in

Telecommunications (FRUCT) Program, 2009. Helsinki, Finland P 191

Подписано в печать «10» июня 2011 г. Формат 60x84/16 Бумага офсетная. Печать офсетная. Усл. печ. л. 1,3. Тираж 100 экз. Заказ № 152

Типография «Восстания -1» 191036, Санкт-Петербург, Восстания, 1.

ТАБЛИЦЫ.

РИСУНКИ.

ВВЕДЕНИЕ.:.

1. Задача формализации естественного языка.

2. Синтез.

3. Машинный перевод.

4. О структуре диссертации.

ГЛАВА 1. ПОДХОДЫ К ФОРМАЛИЗАЦИИ ЯЗЫКА И ТЕОРИЯ КОМПЬЮТЕРНОЙ СЕМАНТИКИ.

1.1. Грамматики Хомского.

1.2. Модель «смысл < - > текст» Мельчука.

1.3. Компьютерная семантика.

ГЛАВА 2. ЗАДАЧА АНАЛИЗА ТЕКСТА НА ЕСТЕСТВЕННОМ ЯЗЫКЕ.

2.1. Задача разрешения анафорических ссылок.

2.2. Портрет объекта в тексте.

2.3. Формализация связей между объектами в тексте.

ГЛАВА 3. СИНТЕЗ ПРЕДЛОЖЕНИЙ НА ЕСТЕСТВЕННОМ ЯЗЫКЕ.

3.1. Обзор литературы.

3.1.1. Формальные грамматики.

3.1.2. Теория мереологии.

3.1.3. Статистические методы.

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

3.3. Алгоритм линеаризации семантических структур.

3.3.1 Технические детали и асимптотическая оценка.

3.3.2 Выводы и обсуждение.

ГЛАВА 4. МАШИННЫЙ ПЕРЕВОД НА ОСНОВЕ КОМПЬЮТЕРНОЙ СЕМАНТИКИ.

4.1. Краткая история машинного перевода.

4.2. Алгоритмы статистического машинного перевода.

4.2.1 Алгоритмы на фразах (Moses).

4.2.2 Алгоритмы, основанные на машинном обучении (Sinuhe).

4.3. Машинный перевод и компьютерная семантика.

4.3.1. Метод автоматического построения переводного контекстного семантического словаря.

4.3.1.1. Giza++.

4.3.1.2. Снятие неоднозначности.

4.3.1.3 Алгоритм построения переводного семантического словаря.

4.3.1.3. Улучшение переводного семантического словаря.

4.3.1.5 Выводы и обсуждение.

4.3.2. Система машинного перевода.101.

1. Задача формализации естественного языка

Задача формализации естественного языка является сложной в теории* и, на практике. Теоретические методы, опережая^ практику на многие годы, (а то и десятилетия), говорят о необходимости создавать базы знаний, которые будут основой искусственного интеллекта. Практические методы продолжают использовать в качестве метрики семантической близости двух документов косинус угла между их векторами. Адептам и первых и вторых методов* понятно, что без строгого семантического анализа на уровне естественного языка невозможно ни качественное решение задач информационного поиска, ни-создание базы знаний. Попытки смоделировать (формализовать) естественный язык на компьютере привели к двум фундаментальным подходам: статистическому [47] и классическому [19]. В рамках данной* работы приводятся результаты экспериментов, сочетающие оба подхода. В работе делается предположение и показывается экспериментально на практике; что сочетание этих двух подходов выводит идею машинного перевода на качественно новый уровень — уровень семантического анализа и синтеза.

Семантический анализ представляет собой первый важный этап на пути к пониманию и оценке того, что изложено в анализируемом документе. Следующим важным и ещё более трудоёмким этапом* является определение прагматической принадлежности документа и отдельных предложений. Предложение Маша любит Джорджа может быть успешно проанализировано семантически с выявлением объекта, действия и субъекта, а также всевозможных морфологических, синтаксических и грамматических характеристик слов, взагшодействуюгцих в этом предложении. Однако эта информация ничего не говорит нам о контексте предложения, о том, где разворачивается действие и что ему предшествует. Вычисление прагматики предложения является результатом анализа всего текста, в котором встречается данное предложение. К примеру, предложению "В молодости он готовил обед часами" серия про братьев Колобков придаёт новый смысл: готовить можно также и часами с кукушкой, используемыми как взбивающий прибор. Для-разрешения* подобных неоднозначностей необходимо вовлечение' новой предметной области, что создаёт предпосылку для создания базы знаний. Рассматривая каждое предложение как суперпозицию его слов, можно утверждать, что для анализа текста необходимо вычисление финальной' суперпозиции предложений*в тексте. .

Построение онтологии и анализ текста документа на её основе (ontology based information extraction) становится всё более популярным' методом семантического и прагматического анализа документа [45]. Исследователи преследуют несколько целей: вычисления мнений в тексте {sentiment récognition), распознавание свойств текста, таких как дата публикации, разрешение темпоральных ссылок (например, в прошлый понедельник), автор публикации, временное направление высказывания. Получаемые базы знаний представляют собой функционирующие системы с взаимодействующими объектами. Темпоральные (временные), атрибутные и реляционные характеристики [50] процессов дают возможность, составлять картину происходящего в тексте. Формализация правил и связей взаимодействующих объектов и загрузка их в базу данных может стать основой для« создания базы, знаний по конкретной области или знаний о мире в целом. База знаний может существенно улучшить качество машинного перевода, который зависит как от корректного семантического анализа на уровне отдельных предложений, так и семантико-прагматического анализа на уровне всего входного текста.

2. Синтез

Способом верификации семантического представления предложений является их синтез. Задача синтеза в целом принадлежит области порождения естественного языка (Natural Language Génération) [24]. Представлением семантического дерева в виде линейной структуры (предложения) занимается задача линеаризации как подзадача ЫЬС. Семантическим представлением предложения можно считать как выходные данные семантического анализатора проф. Тузова [19], так и список Л^-грамм, присутствующих в статистической? модели предложения; При синтезе предложения в случае статистического; анализа' нужно произвести; полный перебор; комбинаций/ пар (троек).' слов предложения, максимизируя? одновременное' присутствие биграмм (триграмм) в статистическихмоделяхпредложения и языка. Термин линеаризация [ 12]; точнее; обозначает процесс превращения»семантического/скобочного'Представленияшз; [19] в- предложение, чем этот же термин описывает поиск, в пространстве Ы-грамм, в случае: которого1 в западной литературе . предпочитают термин

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

У каждого из подходов — статистического и классического — есть свои ограничения:,. Статистика1 борется; за сужение пространства перебора по языковой- модели. Она напрямую зависит, от полноты и качества корпуса, используемого; для составления языковой модели. В классическом подходе нужно;долго; чаще всего вручную^. совершать глубокий, анализ;языка,, выявляя правила, построения предложений. Оба подхода обладают и своими преимуществами. Статистика, помимо высокой' степени автоматизируемости, позволяет генерировать предложения в стиле языковой модели, построенной по входному корпусу, который может быть литературным произведением; или потоком новостных сводок со свойственными им стилем и словарями. Классика, в- сочетании с теорией [19]^ даёт возможность» более точно семантически описать входной текст и более аккуратно проработать смысл генерируемых предложений;

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

Альтернативным, способом- упрощения задачи- является^ вывод переведённых i конструкций в порядке их появления- в исходном предложении, что может давать приемлемые результаты для языков с похожим строем (русский и чешский).' Однако, в случае* пар языков; далёких друг от друга в этом* отношении; таких как английский и японский, без переупорядочивания не обойтись. Известно, что в японском-языке порядок,слов.предписывает цепочку Субъект — Объект — Глагол, что приводит к. рекурсивной структуре в случае со многими'экземплярами вложенных друг в друга цепочек. Так, предложение Репортёры сообщила, что IBM выпустила первый машинный переводчик должно- быть • преобразовано на японском языке в Репортёры- IBM первый машинный переводчик выпустила что сообщили.

3. Машинный перевод

С момента создания первой вычислительной-машины (40е годы ХХ века) машинный перевод являлся первой задачей; с- которой учёные собирались «расправиться» за короткие сроки [23]. Пёрвые опыты специалистами из IBM основывались главным, образом на словарном (прямом) методе и были весьма1, успешными для малого (250) количества входных предложений. Это обстоятельство подкрепляло уверенность в том, что задача машинного перевода — одна из самых простых задач компьютерной науки. Однако дальнейшие исследования, и доклад ALPAC (1966) [63] показали реальное состояние дел и то, что машинный перевод, по крайней мере, не является тривиальной задачей.

Переходя от прямого (словарного) метода к методу трансфера, а затем и к понятию интерлингвы [53], [54], алгоритмы машинного перевода (МП) поделились на две группы: статистические подходы, основанные на входном корпусе данных (Data Driven Machine Translation), и классические, изучающие каждый язык во всех лингвистических деталях {Rule Based Machine Translation).

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

Оба фундаментальных подхода имеют свои- недостатки. Вкратце, классические методы очень трудоёмки и требуют серьёзного труда лингвистов вместе с учёными компьютерной науки; Bi то время как качество работы статистических подходов напрямую зависят от качества входного корпуса, а также совершенно не учитывают семантический уровень формализации языка. Существуют и гибридные системы, делающие попытку вобрать лучшие характеристики классического и статистического МИ, минимизируя их недостатки.

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

4: О структуре диссертации

Первая глава описывает формальные модели естественного языка. Три ключевые теории — грамматики Ноама Хомского, модель «смысл текст» И.А. Мельчука и функциональная теория В.А. Тузова — определили поворотные вехи в попытках учёных построить строгие формальные модели языка, понимаемые компьютером. Основная часть главы уделяет внимание тезисам и главным компонентам теории компьютерной семантики В.А. Тузова. Таким образом, в первой главе описывается теоретический аппарат, который лежит в основе алгоритмов и методов, предлагаемых в последующих главах работы.

Во второй главе описывается метод формализации связей в тексте на естественном языке. По классификации В.А. Тузова анализ текста начинается с анализа слова, продолжается^ анализом предложения и завершается выходом за пределы предложений в; тексте. Задача анализа теста содержит несколько подзадач. Среди них построение портретов объектов текста, формализация связей между объектами и разрешение анафорических ссылок. Решение задачи-анализа текста* необходимо для корректного решения задачи машинного перевода (МП), так как в общем виде МП должен происходить на уровне, выходящем за пределы -одного ^предложения.

Третья глава имеет дело с алгоритмами синтеза предложений на естественном языке. Делается обзор литературы по синтезу, основанному как на классических (контекстно-свободные грамматики, теория мереологии), так и на статистических методах (статистическое моделирование естественного языка). Предложенный далее статистический алгоритм, переупорядочивания слов на Диграммах служит иллюстрацией решения задачи синтеза статистическими методами; показываются сильные и слабые стороны подхода. Далее предлагается, и оценивается алгоритм линеаризации (термин предложен- И.А.Мельчуком в [12]) семантических структур, полученных с использованием семантического анализатора В.А.Тузова. Алгоритм' линеаризации решает частную задачу порождения предложений на естественном языке и имеет прямое приложение в машинном переводе.

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

В конце каждой главы делаются выводы.

Заключение

Задача машинного перевода занимает умы учёных компьютерной науки уже около пяти десятилетий. Изначальные представления учёных о чрезвычайной лёгкости задачи в 50-е гг. прошлого столетия, встретив существенные преграды на практике, показали свою недальновидность. Многочисленные безуспешные попытки решить задачу «одним махом» привели к затишью в научном мире на целое десятилетие. Машинный перевод на правилах, активно развивавшийся более 30 лет после затишья, в последнее время замещается статистическими алгоритмами. Предложенная профессором В.А. Тузовым функциональная теория естественного языка является фундаментом нового направления развития машинного перевода.

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

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

В результате исследования были построены:

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

• Метод анализа текстов на естественном языке. Предложен алгоритм построения портретов объектов в тексте и связей между ними. Произведена классификация связей между объектами в тексте. Изучается и теоретически решается задача разрешения анафорических ссылок в фокусе функциональной теории языка. Разрешение анафорических ссылок на основе теории» компьютерной семантики приводится впервые.

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

• Переводной контекстно-зависимый семантический русско-английский-словарь, пригодный к автоматической обработке в составе системы машинного перевода. Словарь содержит около 18 тысяч статей. Словарь предложно-падежных групп, поставленных в соответствие английским предлогам (более 3,4 тысяч статей).

• Модель перевода, позволяющая избавиться от «шумов» в автоматически построенном переводном контекстном семантическом словаре.

• Экспериментальная система машинного перевода на основе построенных переводного семантического словаря и модели перевода.

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

Другой приоритетной задачей является представление теории компьютерной семантики [19] западному и российскому научному сообществу В частности, ведётся сотрудничество: с авторами корпуса ЦМС [59]; в рамках программы РЕШСТ [35,66], соединяющей Россию и Финляндию; с университетом г. Тампере (Финляндия).

1. Кан Д.А. Задача синтеза предложений на естественном языке // Вестн. С.-Петерб. ун-та. Сер. 10. 2009. Вып. 3. С. 205—212.

2. Кан Д.А., Лебедев И.С. Способ формализации связей в тексте при обработке естественно-языковых конструкций // Вестн. С.-Петерб. ун-та. Сер. 10, 2008. Вып. 2. С. 56—61.

3. Кан ДА., Лебедев И.С., Сухопаров Е.А. Идентификация объектов текста в информационных системах // Программные продукты и системы, 2009, 2(86). С. 163—168.

4. Кан Д.А., Лебедев И.С.: Линеаризация при синтезе предложений наестественном языке. Политехнический симпозиум «Молодые учёныепромышленности Северо-Западного региона»: материалы конференций. СПб.: Изд-во С.-Петерб. политехи, ун-та, 2007. С. 15—16.

5. Кутарба А.Ю. Построение семантического словаря для обработки англоязычных текстов: диссертация на соискание учёной степени кандидата физико-математических наук: 05.13.11.- Санкт-Петербург, 2006. 129 е.: ил. РГБ ОД, 61 06-1/686.

6. Лебедев И.С. Построение шаблонов кода по текстам спецификаций //Информационно-управляющие системы, 2009, 5. С. 39—42.

7. Липатов A.A., Мальцев A.A. Методы автоматизации построения и пополнения двуязычных словарей с использованием корпусов параллельных текстов // Труды международной конференции Диалог'2006, М. 2003.

8. Мельчук И.А. Русский язык в модели «смысл<->текст». — М.: Языки русской культуры, 1995. 682 с.

9. Мельчук И.А., Жолковский А.К.: Толково-комбинаторный словарь современного русского языка. Вена, 1984.

10. Плашенкова И.Н.: Автоматический синтез структурированных предложений. Математическая морфология. — Т. 4. - Вып. 1. 2002.

11. Свердлов С.З. Языки программирования и методы трансляции: Учебное пособие. СПб: Изд-во Питер, 2007. 638 с.

12. Сиротинина О.Б. Порядок слов в русском языке. Изд.З-е,стереотипное. -М.: КомКнига, 2006. 174 с.

13. Толпегин П.В. Информационные технологии анализа русских естественно-языковых текстов. Ч. 1 // Журнал «Информационные технологии», № 8. 2006. С. 41—50.

14. Тузов В.А. Компьютерная семантика русского языка. СПб: Изд-во С.-Петерб. ун-та, 2004. 400 с.

15. Хомский Н. Синтаксические структуры. В сб.: "Новое в лингвистике", вып. 2. М, Изд-во ин. лит., 1962. С. 412—527.

16. Al-Onaizan Y., Curin J., Jahr M., Knight К., Laerty J., Melamed D., Och F.J., Purdy J., Smith N. A., Yarowsky D. Statistical Machine Translation. Final report, JHU Workshop, 1999.

17. Athanaselis Т., Bakamidis S., Dologlou I.: A Fast Algorithm for Words Reordering Based on Language Model. In: 16th International Conference Artificial Neural Networks ICANN 2006. P. 943—951.

18. Baker M.: Routledge Encyclopedia of Translation Studies, 2001. P. 140.

19. Baum L.E. An inequality and associated maximization technique in statistical estimation of probabilistic functions of a Markov process // Proceedings of the Third Symposium on Inequalities. New York. Academic Press. Vol. 3. P. 1—8. 1972.

20. Baykan, E., Henzinger, M., and Weber, I. Web page language identification based on URLs. // Proc. VLDB Endow, vol. 1 no. 1, 2008. P. 176—187.

21. Brown P.F., Delia Pietra V.J., Delia Pietra S.A., Mercer R.L. The mathematics of statistical machine translation: Parameter estimation // Computational Linguistics. Vol. 19. No. 2. P. 263—311. 1993.

22. Callison-Burch C., Osborne M., Koehn P. Re-evaluating the Role of Bleu in Machine Translation Research. Proceedings of EACL, 2006. P. 249—256.

23. Dempster A.P., Laird N.M., Rubin D.B. Maximum likelihood from incomplete data via the EM algorithm // Journal of the Royal Statistical Society. Vol. 39. No. l.P. 1—38. 1977.

24. Elming, J.: Syntactic Reordering Integrated with Phrase-based SMT. Proceedings of the 22nd International Conference on Computational Linguistics, 2008. P. 209—216.

25. Fellbaum, C. (Ed.). WordNet. An Electronic Lexical Database. The MIT Press, 1998.

26. Gale, William A.; Church, Kenneth W.: "A Program for Aligning Sentences in Bilingual Corpora", 1993. Computational Linguistics 19 (1): pp. 75— 102.

27. Gimenez J. Empirical Machine Translation and its Evaluation. Ph.D. Thesis, Universität Politecnica de Catalunya, Barcelona, July, 2008.

28. John Hutchins. Petr Petrovich Troyanskii (1894-1950): A forgotten pioneer of mechanical translation. // Machine Translation, vol. 15 no. 3, 2000. P. 187—221.

29. Kääriäinen M. Sinuhe Statistical Machine Translation using a Globally Trained Conditional Exponential Family Translation Model. In Conference on Empirical Methods in Natural Language Processing, 2009. P. 1027-1036.

30. Kan D., Poroshin V. Semantic Analysis: Theory, Applications and Use Case. // Proceedings of 6th Seminar of Finnish-Russian University Cooperation in Telecommunications (FRUCT) Program, 2009. Helsinki, Finland. P. 191.

31. Koehn P. et al. Moses: Open Source Toolkit for Statistical Machine Translation. // Annual Meeting of the Association for Computational Linguistics (ACL), demonstration session, Prague, Czech Republic, June, 2007.

32. Lavie A., Agarwal A. Meteor: An Automatic Metric for MT Evaluation with High Levels of Correlation with Human Judgments. // Proceedings of the117 "

33. Second Workshop on Statistical Machine Translation, ACL, Prague, June, 2007. P. 228- 231.

34. Liu Di, Gildea D; Syntactic Features; for Evaluation of Machine: Translation. Proceedings of ACL Workshop; on Intrinsic and Extrinsic Evaluation Measures for Machine Translation and/or Summarization, 2005.

35. Maxim Mozgovoy. Enhancing Computer-Aided Plagiarism Detection.

36. University of Joensuu; Computer Science, Dissertations 18 . 131 pp. Joensuu, 2007t

37. Mitkov R., Belguith L., Stys M. Multilingual robust anaphora resolution. In! Proceedings of the 3rd Conference on Empirical Methods in Natural" Language Processing. P. 7—16. 1998.

38. Reiter E., Dale R.: Building Applied Natural Language Generation Systems. Cambridge,University Press, New York (2000).

39. Saggion H., Funk A., Maynard D., Bontcheva K. Ontology-Based Information Extraction for Business Intelligence // Lecture Notes in Computer Science. Vol: 4825/2008: Springer 2008. P. 843—856.

40. Stolcke A.: SRILM: An extensible language modeling toolkit. Speech Technology and Research Laboratory (2002).

41. Toutanova K., Klein D., Manning C., Singer Y. Feature-Rich Part-of-Speech Tagging with a Cyclic Dependency Network. In Proceedings of HLT-NAACC, 2003. P. 252—259.

42. Turney P.D. The Latent Relation Mapping Engine: Algorithm and Experiments. Journal of Artificial Intelligence Research 33, 2008. P. 615—655.

43. Zhang J., Zong C., Li S.: Sentence Type Based Reordering Model for Statistical Machine Translation. In: Proceedings of the 22nd International Conference on Computational Linguistics. 2008. P. 1089—1096.1. Электронные источники

44. Дерновой F. Семантический анализ и РОМИП, 2003. URL: http://romip.ru/romip2003/7 dernovov.pdf (дата обращения: 9.6.2011).

45. Кан Д.А. Курс «Введение в машинный перевод». Ч. 1. С. 19. URL: http://www.slideshare.net/dmitiTkariyintmduction-to-machine-translation-291103 8 (дата обращения: 2.02.2011).

46. Сайт проекта PROMT™' URL: http://translate.ru (дата обращения: 9.6.2011).

47. Clark S. Applications: Statistical Machine Translation, Part II: NLP, University of Cambridge.

48. URL: http://www.cl.cam.ac.uk/teaching/0809/NLP/slides-steve.pdfдата обращения: 9.6.2011).

49. Gerstenberger С. Why mereology for the linearization task in NLG? University of Saarland, 2006.

50. URL:http://www.coli.uni-saarland.de/proiects/igkycontents/Colloquium/WS-05/ciprian.pdf (дата обращения: 9.6.2011).

51. Kaariainen M. Sinuhe Statistical Machine Translation using a Conditional Exponential Family Translation Model. EMLNLP, Singapore, 2009: URL: www.cs.helsinki.fi/u/mtkaaria/sinuhe/emnlpslides.pdf (дата обращения: 9.6.2011).

52. Klyueva N., Bojar O. UMC 0.1: Czech-Russian-English Multilingual Corpus. // Proceedings of the Conference "Corpora 2008".

53. URL: http://ufal.mff.cuni.cz/umc/cer/ (дата обращения: 9.6.2011).

54. Philipp Koehn. Europarl: A Parallel Corpus for Statistical Machine Translation, MT Summit 2005.1. URL:http://www.iccs.inf.ed.ac.uk/~pkoehn/publications/europarl-mtsummit05.pdf (дата обращения: 9.06.2011).61. tree.hh: an STL-like С++ tree class.

55. URL: http://www.aei.mpg.de/~peekas/tree/, (дата обращения: 9.6.2011).

56. Демонстрация системы разрешения анафорических ссылок: TJRL; http://clg.wlv.ac.uk/demos/MARS/index.php (дата обращения: 9.6.2011).

57. Онлайн версия доклада ALPAC. XJRL; http://www.nap.edu/openbook.php?isbn=ARC000005 (дата обращения: 9.6.2011).

58. Сайт Джона Хатчинса: URL: http://www.hutchinsweb.me.uk/maiiTjTi^ (дата обращения: 9.6.2011).65. сайт компании URL: http://www.systran.со.uk/ (дата обращения: 10.6.2011).

59. Сайт проекта FRUCT (Finnish-Russian University Cooperation in Telecommunications) URL: www.fruct.org (дата обращения: 21.03.2010).

60. Сайт проекта Google Translate URL: http://www.translate.googlerr^n (дата обращения: 9.6.2011).

61. Сайт проекта Moses URL: http ://www. statmt.org/moses (дата обращения: 9.6.2011).

62. Сайт проекта Stanford Log-linear Part-of-Speech Tagger URL: http://nlp.stanford.edu/software/tagger.shtml (дата обращения: 9.6.2011).

63. Список английских предлогов:

64. URL: http://en.wikipedia.org/wiki/List of English prepositions (дата обращения: 9.6.2011).