Что ж, продолжим. (Первые части: 1 2 3 4). Долго выбирал, что будет лучше для следующей темы — пофилософствовать о прагматике языка или поговорить конкретно об алгоритмах разбора. Учитывая, что предыдущая часть была неформальной, решил всё-таки переключиться на конкретику, а там посмотрим.

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

Например, у меня на столе лежит книжка под названием Dependency parsing. По названию и аннотации можно подумать, что нас ждёт детальный обзор существующих методик, но это, к сожалению, не совсем так. Авторы сравнительно быстро «съезжают» к своей теме, и половина книги посвящена их подходу, в то время как многие другие методы даже не упомянуты.

Не подумайте, что я их критикую — в том и штука, что данная книга достаточно характерна для нашего времени. Нынешнее состояние отрасли я бы охарактеризовал как «разброд и шатание». Может, заблуждаюсь, хотелось бы верить в лучшее :) Тому есть масса причин. Каждый естественный язык «особен» по-своему. Можно взять какой-нибудь сомалийский и всю жизнь адаптировать для него известные методы, всегда найдётся место новизне. Сформировались солидные лаборатории со своими сложившимися инструментами — та же группа в Стэнфорде, написавшая Stanford parser. Они менять в своих идеях вряд ли что будут в скором времени. Ко всему прочему, качество подходов трудно оценивать. Целая приличного объёма диссертация моего коллеги посвящена методикам оценки и сравнения алгоритмов синтаксического анализа! А он не такой болтун как я, пишет сжато. (Кстати, диссер рекомендую — там содержится хороший обзор современных методов разбора. Да, текста много, но лишь потому, что методов много — в других источниках объём будет не меньше).

Если почитать книги, особенно старые (пусть год издания не вводит в заблуждение, это перепечатка текста начала восьмидесятых годов), складывается впечатление, что всё давным-давно сделано. Однако, видимо, многое желаемое выдаётся за действительное, либо не так отполировано, как хотелось бы. Например, поиск морфологического анализатора для финского языка убеждает, что всё сделано ещё в 1984 году известным в этой области специалистом Киммо Коскенниеми. Однако быстро находится и сайт проекта Omorfi — морфологического анализатора финского, который сейчас пишется (и ещё далёк от завершения) в Хельсинкском университете [имени Линуса Торвальдса] под руководством того же Коскенниеми! Это как бы намекает.

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

Вот они, теории синтаксического разбора:


За каждым подходом — своя школа, свои парсеры, проекты… И до сих пор трудно понять, где лидер. Мой любимчик — XDG, но и там не всё хорошо, и повального энтузиазма по поводу этой разработки в научных кругах пока не слышу. Сам пытался читать и про многие другие подходы. Много умного есть в разных теориях, и нередко они пересекаются.

Так что простите, полного обзора тут не будет. Читайте упомянутую диссертацию доктора Какконена. Рисунок я взял оттуда.

Лексикализация

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

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

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

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

Проблемы проективности и множественности деревьев разбора

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

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

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


Но бывает, что надо соединять между собой слова, «перепрыгивая» через третье слово:


(Признаюсь, глагольные «колбасы» типа «хочет помочь кормить» в разных теориях обрабатываются по-разному. На рисунке приведён лишь один из вариантов.)
Насколько понимаю, при phrase-structure-разборе такие ситуации вообще не обрабатываются. Потому что грамматики Хомского по определению описывают лишь непосредственно примыкающие друг к другу элементы. Когда апологеты dependency parsing стали говорить, что этот подход позволяет работать с более свободным порядком слов (чем в английском), хомскианцы ответили: а вы сначала парсер напишите, который умеет строить непроективные деревья — без них выгоды от потенциальной свободы невелики.

Насколько же актуальна проблема? В одной статье пишут, что при анализе реальных текстов на чешском языке «непроективность» была выявлена в 23% случаев. Часто. Проблема непроективных деревьев в том, что если разрешено пытаться клеить любое слово к любому другому, мы тут же выходим за все предусмотренные вежливостью нормы по объёму вычислений. Фактически, в худшем случае получается полный перебор всех возможных графов с N вершинами-словами, то есть задача экспоненциальной сложности.

Тут подключились теоретики и доказали, что ценой небольших ограничений возможностей парсера можно свести его вычислительную сложность к «приемлемой» (я не изучал детали, точные выкладки привести не могу). При этом для той же чешской коллекции документов «не по зубам» этому ограниченному анализатору будет уже всего лишь 0.5% предложений.

Кстати, первые упоминания о непроективном разборе предложений достаточно свежи — примерно 1997 год. Это к вопросу о том, насколько можно в принципе доверять литературе в нашей области. Особенно этим замечательным книжкам из восьмидесятых, в которых «уже всё решено».

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

Понятно, что многие слова неоднозначны, но их трактовка не влияет на вид дерева, то есть на синтаксический анализ: «я держу деньги в банке». Здесь разбор однозначен: держу деньги (где?) — в банке. При этом неважно, стеклянная банка у меня или каменное здание банка.

Есть «промежуточные» варианты. «По улице шла девушка с косой». Можно всегда разбирать так: девушка (с чем?) — с косой. А можно выбирать: девушка (какая?) — с косой (если речь о причёске); девушка (с чем?) — с косой (если речь о металлической косе).

Бывают и очевидные случаи совершенно разных деревьев. Мой любимый пример: «он увидел её перед своими глазами».
Первый вариант ясен: он увидел (кого?) её (где?) перед своими глазами.
Но есть и «маргинальная» трактовка: он увидел (что?) её перед (т.е. переднюю часть) (чем/как?) — своими глазами.

Не буду врать, но кроме XDG/XDK мне не приходит на ум проектов, умеющих строить всё множество допустимых деревьев.

Пожалуй, на сегодня закончим. Спать хочется :)