Pull to refresh

Заметки об NLP (часть 10)

Reading time 9 min
Views 8.3K
(Первые части: 1 2 3 4 5 6 7 8 9). Как говорилось в известной рекламе, «вы не ждали, а мы пришли» :)

За время, прошедшее после публикации девятой части, я прочитал одну хорошую книжку по теме (в to-read списке ещё парочка), множество статей, а также пообщался с несколькими специалистами. Соответственно, накопился новый объём материала, заслуживающий отдельной заметки. Как обычно, знакомлю других, параллельно структурирую знания для себя.

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

Немного о машинном переводе: статистика против правил

Начну с любимого холивара. Что лучше — статистические модели или модели, основанные на явных правилах грамматики? Неплохо пишет об этом Yorick Wilks в книге Machine Translation: Its Scope and Limits. В книге рассматривается задача машинного перевода. Понятно, что без разбора структуры предложений далеко в переводе не уйти, так что темы синтаксического анализа и перевода тесно связаны.

В целом Уилкс так видит развитие отрасли. Изначально всё строилось на основе правил. Затем, в начале 90-х годов, группа ребят из IBM придумала применить чистую статистику (вообще без правил), и получила результаты, гораздо лучше ожидаемых. Впрочем, Уилкс говорит, что неплохие результаты вначале не гарантируют улучшений в дальнейшим, поскольку «теоретический потолок» технологии может оказаться не так высок. И вообще, в соответствии с «законом Уилкса», любая теория, даже самая ненормальная, позволяет получать неплохие результаты в машинном переводе. Есть ещё «второй закон Уилкса»: успешная система машинного перевода обычно работает не на заявленных принципах.

То есть если взять современное состояние динозавра SYSTRAN, то окажется, что называть эту систему «основанной на правилах» не совсем корректно, там используется куча различных «костылей» и специфических алгоритмов. Аналогично, системы имени Google & IBM быстро вышли из категории «чисто статистических». Скажем, IBM изначально отрицали даже модули морфологии для отдельных языков, предполагая абсолютно всё выводить «на лету» из корпусов текстов. Теперь так уже не делают. Да, ещё отметим: «чистый» статистический анализ текста так или иначе сводится к статистике следования одних слов за другими. Если рассматривать «триграммы», то есть три подряд идущих слова в качестве базового элемента анализа, современный компьютер ещё более-менее справляется (хотя для начала 90-х и триграммы были весьма тяжелы). Более длинные цепочки слов приводят к пространству вариантов, находящемуся за пределами возможностей любого нынешнего оборудования.

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

В целом Уилкс считает, что: (1) голая статистика, так же как и голые правила, не очень перспективна (хороший машинный перевод требует базы знаний об объектах текста и о внешнем мире); (2) будущие системы будут гибридными, но пока не совсем понятно, как эти гибриды сделать; (3) даже чисто статистические алгоритмы должны быть «умнее». Приводится ещё вот такое наблюдение. Сейчас на статистике построены системы распознавания речи. Система изначально «тренируется» на примерах входных данных, а затем уже может быть использована на практике. Подсчитано, что если бы детям для обучения речи требовалось бы столько же учебных данных, сколько компьютерным распознавателям, обучение детей языку заняло бы более 100 лет круглосуточных занятий.

На пути к гибридизации

Машинный перевод — это сложная и многогранная тема. Так что давайте лучше вернёмся к парсингу, то есть к синтаксическому анализу предложений.

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

Поговорим сначала немного о самих трибанках (напомню, мы обсуждаем почти исключительно dependency treebanks). Мне кажется, создание банка образцов разобранных предложений — очень правильная задача. Очевидно, что размеченные фразы позволяют выполнить гораздо больше интересных видов анализа текста, нежели неразмеченные предложения. При этом объём работы для создания трибанка не столь уж велик. По сути дела, составление трибанка — это разбор предложений по членам, то есть работа, с который каждый из нас знаком по школе. Авторы финского Turku dependency treebank считают, что на основе трибанка из десяти тысяч предложений можно написать полноценный парсер. О'кей, если ежедневно, не напрягаясь, разбирать 10 предложений, такой трибанк можно сделать за три года. А если работать втроём — то за год. Разве это много? Количество трибанков в мире растёт, это факт. Причём многие из них доступны любым желающим, нередко бесплатно.

С горечью можно заметить, что с русским языком, как обычно, всё сложно. Существует довольно крупный трибанк SynTagRus (около 42 тысяч разобранных предложений). Я с его авторами не связывался, но с точки зрения стороннего наблюдателя как-то непрозрачно всё у них. «Пишите письма, а мы, может быть, ответим. Может, дадим, а может, не дадим». Сравните это со свободно доступными чешским и финским корпусами! Я не говорю, что банк обязан быть бесплатным, но чётко разъяснить правила раздачи ведь явно проще, чем проаннотировать 42 тысячи фраз? Почему же сложная работа выполнена, а простая до сих пор «висит»?.. На сайте ruscorpora.ru можно поискать отдельные слова в корпусе и оценить выдаваемые в PDF деревья разбора. При этом особенно «радует» фраза: «Какие-либо оффлайновые версии корпуса пока недоступны, но работа в этом направлении ведётся». Я очень живо себе представляю эти «ведущиеся работы»: видимо, на стареньком 80286 компьютере круглосуточно работает архиватор RAR, пакующий гигабайты деревьев для последующего выкладывания архива на сайт. А что ещё делать-то? Уже упомянутый финский трибанк тупо выложен в архиве с пояснениями, и никто не жалуется.

Думаю, имеет смысл говорить о двух основных проблемах в «treebank-based parsing»: как аннотировать трибанк и как на основе готового трибанка автоматически создать синтаксический анализатор текста. Начнём со второй задачи. Предположим, трибанк уже есть и «как-то» аннотирован. То есть для каждого предложения из трибанка имеется готовый граф разбора; иными словами, перечислены свзяи между словами (какое слово с каким связано), и для каждой связи указан её «тип» (например, «подлежащее»).

В одной из прошлых частей я упоминал о работе, в которой трибанк конвертировался в правила грамматики XDG для последующего разбора. Направление это пока, к сожалению, заглохло. Автор объясняет причину так. Трибанк не даёт достаточного количества ограничений для деревьев. То есть на выходе получаются правила, по которым можно сгенерировать десять разных деревьев для одного входного предложения. В целом автор верит, что проблему можно решить путём ранжирования по «хорошести» получаемых деревьев. Действительно, такие исследования есть. Посмотрим, что из них выйдет (а может, и поучаствуем :) ). Кстати, к вопросу о Гугле и о чистой статистике: один из продвигающих это направление ранжирования деревьев товарищ Liang Huang некоторое время сам работал в Гугле.

Генерация правил а-ля XDG, впрочем, не единственный вариант построения парсера. Есть и более успешные на сегодняшний день проекты, например, MaltParser. Обещает эта штука практически фантастику: дайте ей на вход трибанк любого языка, и она сгенерирует соответствующий парсер. Причём работает система, судя по всему, неплохо. Помнится, где-то я пытался язвить: если статистика так хороша, почему же никто не пытался написать статистический анализатор Паскаля? :) Ведь Паскаль явно проще любого естественного языка! Так вот, авторы MaltParser действительно сумели решить эту задачу — они сгенерировали парсер C++ с помощью MaltParser'а!

Я пока не знакомился с подробностями алгоритмов, конвертирующих трибанки в парсеры, но в самом общем виде суть в том, что процесс разбора представляется в виде процедуры, зависящей от численных параметров. Различные значения параметров направляют процедуру разбора по тому или иному сценарию. Трибанк используется как training set для некоторого стандартного алгоритма machine learning, с помощью которого подбирается требуемый набор параметров. Получается, что «набор параметров + фиксированный алгоритм = синтаксический анализатор».

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

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

Грани синтаксического анализа

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

Одно и только одно дерево: это хорошо или плохо? Думаю, надо разделить дерево как структуру связей «вообще» и дерево как структуру чётко обозначенных видов связей. Иными словами, дерево как (1) граф с непомеченными рёбрами и как (2) граф с помеченными рёбрами.

Рассмотрим фразу Иван пришёл из гостей. Ей соответствует дерево с рёбрами (пришёл, Иван), (пришёл, из) и (из, гостей). Фраза Иван пришёл из вежливости синтаксически устроена точно так же, и ей соответствует аналогичное дерево разбора. Однако если добавить метки рёбер, описывающие некие «типы связи», деревья уже не будут идентичными. Иван пришёл (откуда?) из гостей, но: Иван пришёл (почему?) из вежливости.

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

Мне кажется, что ситуация такова. Предложению должен соответствовать ровно один граф без меток. Случай, когда имеются два и более графов, возможен, но в этом случае мы имеем словесный каламбур — как бы с текстом и подтекстом. Нужна ли нам подобная игра слов на практике — большой вопрос. Честно говоря, не думаю, что нужна. Фактически, здесь идёт речь о примерах такого сорта:

Он увидел её перед своими глазами => он увидел (кого?) её (где?) перед своими глазами.
                                     он увидел (что?) её перед (как?) своими глазами.
									 
Графиня ехала в карете с поднятым задом => графиня ехала в карете (какой?) с поднятым задом.
                                           ехала в карете (кто?) графиня с поднятым задом.

Конечно, мне трудно утверждать наверняка, но по ощущениям предложению должно соответствовать только одно дерево разбора (с непомеченными рёбрами). Может ли парсер самостоятельно построить такое дерево, и какого рода информация ему нужна — вопрос сложный. Например, слегка изменим фразу с графиней (простите, что было в голове, то и докладываю): Графиня ехала в карете с поднятой задницей. Здесь можно бы заметить, что задница есть у графини, но нет у кареты; стало быть, в правильном дереве разбора «задница» должна быть соединена со словом «графиня», а не со словом «карета». Но это требует от парсера обширных познаний в анатомии, так что вопрос о целесообразности разбора таких сложностей остаётся открытым.

Таким образом, для непомеченных графов MaltParser прекрасно подходит. Ситуация заметно осложняется для графов с метками рёбер. По логике вещей, идеальному разбору фразы всегда соответствует одно дерево. Однако на практике с ростом наших аппетитов резко снижаются возможности парсера. Реальные масштабы проблемы зависят от предусмотренных видов связи между словами трибанка. Чем «навороченнее» система связей, тем сложнее парсеру. В итоге ведь парсер пытается разбирать предложения «по образу и подобию» трибанка, то есть используя все известные ему способы связи слов. (Таким образом, мы подходим к первой упомянутой выше задаче — к задаче аннотирования трибанка).

Не думайте, что я говорю о каких-то сугубо теоретических вещах. Разметка трибанка — вопрос нетривиальный. Не существует единой системы разметки трибанков. Есть отдельные разработанные подходы, которыми можно воспользоваться. А можно и не воспользоваться. Скажем, авторы MaltParser говорят, что тренируясь на разных трибанках, они получали различное качество разбора. Так, Prague Dependency Treebank в целом даёт качество похуже. И объясняется это тем, что разметка в нём более детальная, типов связей больше. Соответственно, у парсера, оперирующего таким солидным количеством связей, больше возможностей совершить ошибку.

Так вот, здесь я хотел бы поставить вопрос ребром: какого рода детализация должна быть в трибанке, чтобы сделать парсер полезным? Если ограничиться системой «подлежащее — сказуемое — дополнение», MaltParser'а (и других статистических анализаторов) вполне хватит. Если же приписывать каждому слову целый набор семантических атрибутов, неизбежно возникает проблема «underspecification», то есть истинная нехватка данных для построения единственного дерева.

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

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

Пока не знаю. Копаю дальше :)
Tags:
Hubs:
+21
Comments 12
Comments Comments 12

Articles