Easy-First Non-Directional Dependency Parser
Тынц www.cs.bgu.ac.il/~elhadad/papers/naacl2010.pdf
Только недавно удалил из своего движка код для очередной своей версии аналогичного алгоритма. Свой был с шахматами (недетерминированный), но без поэтесс (правила писались вручную, а не выводились при обучении по размеченному корпусу).
Почему он (мой) мне не понравился (причем не понравился 3 раза, если считать варианты реализации).
Главная проблема - локальность принимаемых решений. Которые синтаксические конструкции должны учитывать для правильной обработки более 2х токенов. И не просто учитывать, заглядывая вперед на пару-тройку-размер окна, а связывать сразу несколько. В статье, кстати, именно поэтому вводятся признаки "pp-attachment", а именно
"This should help the model learn lexicalized attachment preferences ..."
Вторая проблема - переписывание токенов. Когда мы заменяем собранный consituence из цепочки на headword, то неявно предполагаем, что синтаксически этот headword в одиночку работает так же, как он работает вместе со своими аргументами. Это собственно показало на иллюстрации в указанной работе:
Беда в том, что, как мне довелось испытать на своей шкуре, это не всегда так для русского языка.
Простой пример - падеж для подлежащего. Приятно и комфортно работать, когда подлежащее - это существительное или подобная часть речи (включая прилагательное: "каждый должен попробовать"), имеющая признак именительного падежа в качестве одной из feature. Заменяем всю группу существительного на главное существительное, и можем продолжать связывание дальше, на сжавшемся предложении. OK. Рано или поздно мы натыкаемся на первую ловушку
- числа, которые арабские.
Пример: "13 негритят играют во дворе". Чего тут неудобного? А то, что приписывать числам категорию падежа - достаточно искуственная операция, а рассматривать считаемое существительное главным словом не позволяет совесть и логика, так как это существительное стоит в родительном падеже, хотя может и в именительном для остроты ощущений:
21 негритенок играет во дворе
Я делал так: в правилах связывания переписывал некоторые feature, чтобы алгоритм видел правильные признаки, а не реальные. Иначе говоря, feature set не был жестко прибит гвоздями к токенам, а иногда становился свойством constituence как новой сущности разбора. Кроме числительных такие штуки вытворяли наречия, точнее - некоторые счетные слова "несколько негритят", "много-много диких кошек". И много таких ситуаций, когда конструкция в целом имеет морфологические свойства, не выводимые непосредственно из своих токенов. К примеру:
Люди много чего говорят.
Что говорят люди? Много чего. Это словосочетание ведет себя как группа существительного в винительном падеже и присоединяется
к глаголу как прямое дополнение.
Или так:
Впереди нас ждало много интересного.
Ждало что? Много интересного. Счетное слово "много" и прилагательное. Присоединяются к глаголу как подлежащее.
Ну и тому подобные художественные штучки, коих есть у нас в изобилии.
Третья проблема, с которой я худо-бедно научился бороться - вложенность некоторых конструкций и трудности обработки таких рекурсивных вещей через итерационный механизм. Причастный оборот может атрибутировать существительное слева или справа. При этом причастный оборот может включать еще один причастный оборот, хотя конечно это уже крайне редкий случай радикального графоманства. А еще есть "квази-причастные" обороты со словом "который", которые позволяют вводить вспомогательные предложения внутрь группы прилагательного - а это уже ого-го какой простор для фантазии:
я видел кошку, которая бегала по двору, усыпанному стружками, держа в зубах мышку, которая еще пищала.
Грубо говоря, основная задача для таких предложений - не допустить преждевременного сворачивания группы слов и замены на главное слово, так как оставшиеся не свернутые запчасти этой группы банально мешают правильно разбирать дальше.
Я делал это через особую организацию порядка применения связываний и недетерминированность процесса. Как я понимаю, в предлагаемом алгоритме "easy-first parsing" это предлагается делать на основе дополнительных feature и учета их в статистике при принятии решения "связывать вправо" и "связывать влево".
И, справедливости ради, отмечу, что я пытался делать все-таки недетерминированный вариант, так как с самого начала всплыла проблема распространения ошибок неправильного связывания и невозможности иногда сделать правильное действие на основе локального контекста. Поэтому решение ветвилось в ожидании того, что неправильный вариант потом будет подавлен на основе информации о разборе, сделанном в другом месте. То есть бонусом в виде хорошей производительности я заведомо жертвовал. Была также отчаянная попытка сделать детерминированный разбор, но количество ошибок из-за "жадности" алгоритма оказалось великовато и результаты слишком скучными.