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

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

    На сей раз заметка полностью посвящена проекту XDG/XDK, который я пытаюсь изучать на досуге. Назвать себя специалистом по XDG пока ещё не могу. Но потихоньку двигаюсь.

    Итак, мы остановились на том, что будем рассматривать dependency parsing, причём, по возможности, с непроективными конструкциями и множественной генерацией деревьев. Это естественным путём приводит нас к проекту XDG/XDK, удовлетворяющему все эти требования. Я сам пришёл «в тему» с симпатиями к lexicalized dependency parsing, но в остальном начинаю почти что с чистого листа, и выбор XDG продиктован холодным отсеиванием прочего. Изучал, что есть, выбирал, что лучше. На сегодня так оказалось, что XDG вроде как лучше (по крайней мере, в рамках заданной концепции).

    Что же это такое? XDG расшифровывается как Extensible Dependency Grammar, а XDK, соответственно, как XDG Development Kit. XDG представляет собой формализм для описания допустимых связей между словами в предложении. Это лексикализованный формализм: для каждого конкретного слова языка придётся описать, каким же образом и с чем его можно клеить. XDK включает в себя набор инструментов, наиболее важным из которых является Solver, он же синтаксический анализатор. Solver принимает на входе грамматику языка и предложение на нём. На выходе генерируется множество деревьев, соответствующих разобранному предложению. Как видите, на словах всё очень просто :)

    Сочинение грамматики

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

    Что касается способа записи этих правил — мне он представляется достаточно очевидным и адекватным. Полагаю, что с помощью XDG можно описать не только естественный язык, но и, скажем, Паскаль. Конечно, такой парсер будет далёк от совершенства, но работать, по идее, должен :)

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

    Наверно, имеет смысл дать немного «пощупать» язык предлагаемых грамматик. Он зиждется на трёх базовых принципах:

    Лексикализация. Элементами грамматики являются слова языка. Каждому слову может быть приписан набор атрибутов, собственно, и определяющий, что слово может приклеить к себе и к чему оно может приклеиться само. У каждого атрибута есть имя, тип и значение. Чаще всего используются типы «строка» и «множество строк».

    Принципы создания графа. Помимо ограничений на «склейку», задаваемых на уровне отдельных слов, можно задать ограничения для всего графа разбора фразы. Такие ограничения называются «принципами». Простейший пример принципа — tree principle, требующий того, чтобы генерируемый граф был деревом. О некоторых других полезных принципах поговорим чуть позже.

    Многомерность. Каждый атрибут слова определяется в некотором пространстве имён (задаваемом пользователем). Принципы создания графа также описываются в определённом простанстве имён. Каждое такое пространство называется «измерением». Граф разбора фразы для каждого измерения строится отдельно. Таким образом, можно получить сразу несколько графов разбора, отражающих те или иные структурные особенности предложения (то есть пользователь может посмотреть на предложение как бы под разными углами зрения). Например, наряду с dependency-графом можно построить вырожденный граф-список, показывающий порядок следования слов в предложении. Или, скажем, граф, соединяющий между собой все существительные фразы.

    Принцип валентности

    Теперь пару слов о том, какие бывают принципы. Хочется прежде всего упомянуть принцип валентности, указывающий, что связь между двумя словами w1 и w2 может быть установлена только если атрибут out слова w1 совпадает с атрибутом in слова w2. Поясню на примере:

    defentry { dim lex { word: "eats"}
               dim syn {in: {root} out: {subj obj adv*}}}
    defentry { dim lex {word: "Peter"}
               dim syn {in: {subj? obj?}  out: {} } }
    defentry { dim lex {word: "spaghetti"}
               dim syn {in: {subj? obj?} out: {} } }
    defentry { dim lex {word: "today"}
               dim syn {in: {adv?} out: {} } }


    Спецификация атрибута out глагола «eats» указывает, что слово может присоединить к себе один субъект (subj), один объект (obj) и произвольное количество обстоятельств (adv*). Спецификация атрибута in слова «Peter» разрешает этому слову быть субъектом или объектом. Такова же и спецификация слова «spaghetti». Слово «today» описано как потенциальное обстоятельство. Таким образом, если мы скормим парсеру фразу «Peter eats spaghetti today», итоговое дерево будет иметь «eats» в качестве корня, «Peter» и «spaghetti» будут присоединены к корню в качестве субъекта и объекта, а слово «today» — в качестве обстоятельства.

    Существует ещё «принцип упорядоченности» (пожертвую им ради экономии места), с помощью которого можно указать, что более раннее слово в предложении имеет приоритет в качестве субъекта (таким образом, «spaghetti» субъектом не станет).

    Принцип согласуемости

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

    defentry { dim lex { word: "eats" }
               dim syn { agrs: {["3" sg]}
                         agree: {subj} } }
    defentry { dim lex { word: "eat" }
               dim syn { agrs: {["1" sg] ["2" sg]
                           ["1" pl] ["2" pl] ["3" pl]}
                         agree: {subj}}


    Чтобы слово «Peter» присоединялось и теперь, придётся указать его атрибуты числа и лица:

    defentry { dim lex { word: "Peter" }
               dim syn { agrs: {["3" sg]}
                         agree: {}} }


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

    Разбор заканчивается тогда, когда удалось собрать всю конструкцию и присоединить её к слову, имеющему атрибут «вершина дерева». Например, в качестве такого слова можно описать точку (ибо точкой кончается предложение):

    defentry {
      dim lex {word: "."}
      dim syn {in: {}
               out: {root} 
               agrs: top
               }}


    Пуск!

    Если полученную грамматику (разумеется, тут приведены лишь её фрагменты!) скормить анализатору вместе со входной строкой «Peter eats spaghetti today .», на выходе будет сгенерировано вполне ожидаемое дерево:


    Здесь предлагаю поставить если не точку, то точку с запятой, потому что «кратко» продолжить не получится. Следующий «блок мыслей» тянет на отдельный пост (завтра, вероятно?..) Продолжим про XDG, скорее всего.

    Разве что, дабы не возвращаться к этому вопросу, перечислю проблемы XDK, бросающиеся в глаза. Во-первых, нынешний билд собран под ASCII с поддержкой западноевропейских языков. То есть кириллица превращается в крякозяблы (разбирать всё равно будет, но дебажить неудобно). Впрочем, проблема это небольшая, как мне кажется. Во-вторых, автор защитил диссер и ушёл работать в промышленность, больше он проект не поддерживает, а никто другой пока не подобрал, даром что open source. В-третьих, «войти в проект» не так-то просто, ибо всё написано на сравнительно маргинальной среде программирования Mozart/Oz в парадигме constraint programming. За это как раз автора сложно критиковать — задача уж очень специфическая. Я уже говорил, что полноценный разбор тянет на NP-полную задачу. Автор же рассмотрел парсинг как constraint satisfaction problem: даны узлы графа и дан набор условий, ограничивающих рёбра. Требуется найти удовлетворяющий условиям граф. То есть задачу поставили в более общем виде, и в итоге было решено применить специализированный инструмент для такого рода вещей. Правильно сделали. Есть ещё кое-что, не хватающее лично мне, но об этом в следующий раз.

    Похожие публикации

    Средняя зарплата в IT

    120 000 ₽/мес.
    Средняя зарплата по всем IT-специализациям на основании 3 679 анкет, за 1-ое пол. 2021 года Узнать свою зарплату
    Реклама
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее

    Комментарии 24

      +4
      С нетерпением жду продолжения! И не обращайте внимания на популярность топиков, как по мне — сейчас самое интересное началось!
        0
        Поддерживаю.
          0
          да и на карму автору тоже стоит посмотреть :)

          на фоне топиков типа «поработит ли нас искуственный разум», эта серия статей весьма конструктивна.
            0
            ОК, оставим этот вопрос — я мимоходом упомянул, не будем сосредотачиваться на мелочах в то время как есть темы посерьёзнее и поинтереснее :)
            +2
            Интересная серия статей.
            Популярность — думаю, из-за частоты выхода статей. по 2-3 статьи в день думаю, многовато.
            А статьи занимательные, да. С удовольствием читаю.
              +1
              Не утомил конечно, жду продолжения!
                +2
                Совсем не утомили, наоборот, нечего размазывать по «раз в неделю».
                  0
                  Сейчас заметил, что во время прочтения цикла и перехода по ссылкам пальцы застыли на ctrl+D
                    0
                    а «добавить в избранное» на самом хабре не устраивает?
                    0
                    вродебы где-то у автора проскакивала идея способа обобщения правил,
                    позволяющего объединить в один кластер слова
                    «eat», «eats», «eated», «will eat»,
                    и далее вплоть до того, что
                    dim syn {in: {root} out: {subj obj adv*}}} указывается для всех переходных глаголов
                    dim syn {in: {root} out: {subj adv*}}} для всех переходных глаголов

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

                      0
                      В XDK вроде бы есть какая-то рудиментарная поддержка морфологии, но для случаев сложнее английского это точно не работает.
                      По поводу обобщений «eats» с формами — не помню, но верю. Классы слов («переходные», «непереходные») точно поддерживаются.

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

                      Получается, что для разбора фразы нужно всего-то 5-10 правил. (Понимаю, при этом будут вопросы к производительности, но это уже другая тема).
                        0
                        ну в принципе то да.
                        если все слова фразы в явном виде входят в базу правил,
                        то поиск этих правил проблемы не создаст.
                      0
                      ну и кстати, по части морфологии,
                      со своей колокольни (синтеза),
                      я бы предложил дополнить описания слов пространством имён morph,
                      описывающим возможные вариации слова, сохраняющие все остальные атрибуты.
                      а в пространстве syn заменить атрибут args
                      на атрибут agrees, в котором указывать, по каким именно характеристикам слово согласуется со своими валентностями.
                      например, для глаголов там будет согласование с subj по лицу, числу, роду

                      собственно такую схему я путался сделать. /* опечатку s/ы/у/ оставляю :) */
                      но безуспешно:
                      в русском по родам согласуется только прошедшее время единственное число,
                      число — само по себе согласовываемый признак, и что тут делать не совсем очевидно.
                        0
                        Получается, что мы опять приходим к модели, когда каждая словоформа представляет собой отдельный объект, с собственными правилами согласования.
                          +1
                          Но из информации, что это словоформы одного и того же слова — наверное тоже то-то интересное можно извлечь и использовать. Например, я давно мечтаю об инструменте автопересогласования слов в фразах при правках отдельных слов…

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

                            Можно и ещё проще: словоформа -> (морф анализатор) -> начальная форма -> (морф синтезатор) -> требуемая форма.
                        0
                        5 и 6 части посложнее, конечно, но это ничего не значит :)
                          0
                          Предлагаю автору заняться анализом семантическим, это то, чем сейчас занимаются в научном мире
                            0
                            Об этом будет следующая часть, хотя и, наверно, с её содержанием можно будет поспорить.
                              0
                              по поводу поспорить согласен
                              последний нашумевший проект на эту тему «интерсемантика»- попытка реализации единого семантического когда для всех языков.
                              В мае прошлого года, выступая на конференции посвященной проблемам искусственного интеллекта, один из докладчиков демонстрировал систему автоматизированного тестирования Control. Так вот, когда выяснилось, что система абсолютно не затрагивает вопросы семантического анализа, пошла буря критики и негодования, после этого докладчика слушать уже никто не хотел. Пишите про семантику, будем читать и комментировать ))))
                            0
                            Спасибо вам огромное за ваши статьи, однако у меня теплилась надежда, что вы будете писать статьи чуть шире. Не только о том, чем занимаетесь конкретно. ((

                            А то у меня самого кругозор в компьютерной лингвистике пока очень узок. Это грустно… =(
                              0
                              А что вас интересует?
                              Если я в какой-то метод не верю — не буду писать о нём, зачем зря пропагандировать? :)
                              А если верю, но просто руки не доходят — буду стараться хотя бы затронуть.
                              0
                              А по поводу XDG. Для этой системы уже есть готовая грамматика для английского языка?
                                0
                                Есть «примеры» разного уровня сложности прямо в поставке XDG. Существуют ли более продвинутые грамматики — не знаю.
                                Английский — язык с достаточно жёстко фиксированной структурой, и с ним порою неплохо справляются парсеры, основанные на более простых принципах. Видимо, мотивация «переезжать» не слишком высока.

                              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                              Самое читаемое