Что ж, продолжим.
Я долго решал, что будет лучше в следующей теме — пофилософствовать о прагматике языка или поговорить конкретно об алгоритмах парсинга.
Учитывая, что предыдущая часть была неофициальной, я решил перейти к конкретике, а там посмотрим.
Итак, синтаксический анализ предложения.
Давайте сразу определимся, что речь пойдет о парсинге в рамках концепции парсинга зависимостей, а определяющей методологией парсинга будет точный анализ (не статистический).
Начнем с краткого обзора того, что происходит вокруг нас.
Например, у меня на столе лежит книга под названием Анализ зависимостей .
Судя по названию и аннотации, можно подумать, что нас ждет подробный обзор существующих методов, но это, к сожалению, не совсем так.
Авторы относительно быстро переходят к своей теме, их подходу посвящена половина книги, а многие другие методы даже не упоминаются.
Не подумайте, что я их критикую – дело в том, что эта книга вполне типична для нашего времени.
Текущее состояние отрасли я бы охарактеризовал как «разброд и шатание».
Возможно я ошибаюсь, хотелось бы верить в лучшее :) Причин этому много.
Каждый естественный язык по-своему «особенный».
Вы можете взять какой-нибудь сомалийский язык и всю жизнь адаптировать под него известные методы; всегда будет место новизне.
Сформировались авторитетные лаборатории со своими устоявшимися инструментами — та самая группа в Стэнфорде, которая написала Стэнфордский парсер.
Вряд ли они изменят свои взгляды в ближайшее время.
Более того, качество подходов оценить сложно.
Весь приличный объём Тезис моего коллеги посвящен методам оценки и сравнения алгоритмов парсинга! Но он не такой болтун, как я, пишет лаконично.
(Кстати, диссертацию рекомендую - в ней хороший обзор современных методов анализа.
Да, текста много, но только потому, что методов много - в других источниках объем будет не меньше) .
Если вы читаете книги, особенно старый (пусть и год издания не вводит в заблуждение, это перепечатка текста начала восьмидесятых годов), складывается впечатление, что все было сделано очень давно.
Однако, судя по всему, многое из желаемого выдается за реальность, либо не так отшлифовано, как хотелось бы.
Например, поиск морфологического анализатора финского языка убеждает, что все сделано еще в 1984 году известный специалист в этой области Киммо Коскенниеми.
Однако сайт проекта быстро находится Оморфи - морфологический анализатор финского языка, который сейчас пишется (и еще далеко не завершен) в Хельсинкском университете [имени Линуса Торвальдса] под руководством того же Коскенниеми! Это как бы намекает. Понять имеющиеся сегодня формализмы непросто.
И совершенно невозможно понять, какой из них чего стоит. Я думаю, это вопрос веры.
Вот они, теории синтаксического разбора: 
У каждого подхода своя школа, свои парсеры, проекты.
И понять, где лидер, пока сложно.
Мой фаворит — XDG, но там не все хорошо, и широкого энтузиазма по поводу этой разработки в научных кругах я пока не слышал.
Я сам пытался прочитать о многих других подходах.
В разных теориях много хитрости, и они часто пересекаются.
Извините, полного обзора здесь не будет. Прочитайте упомянутое диссертация Доктор Какконен.
Рисунок я взял оттуда.
ЛексикализацияСтарые формализмы не спешат уходить на пенсию.
Как видно из рисунка, многие довольно древние методы успешно развиваются и по сей день.
Но одна тенденция очевидна: переход к лексикализованный (лексикализованные) модели.
На рисунке они обозначены серым цветом.
Смысл этого термина довольно прост: в записях синтаксических правил языка в том или ином виде появляются настоящие слова из языкового словаря.
Нелексикализованные модели используют более общие понятия.
Например, лексикализированное правило может гласить: здесь должно появиться слово «таблица».
В нелексикализованном правиле можно писать только «существительное мужского рода» и некоторые уточняющие признаки.
В принципе, насколько я понимаю, грань довольно тонкая.
С одной стороны, объект может быть настолько «сжат» условиями, что ничто иное, как слово «стол», не подходит под его определение.
С другой стороны, лексикализованные правила могут содержать не только конкретные предметы, но и абстрактные понятия: «подлежащее», «наречие».
На практике нелексикализованные наборы правил («грамматики») связаны с чем-то небольшим по объему и, вероятно, получены статистически.
Лексикализованные грамматики представляют собой толстые словари, уровень детализации доходящий до описания отдельных слов.
Проблемы проективности и множественности деревьев разбора.
Как видите, хоть мы и обещали парсинг, но до синтаксического анализа мы все равно не дошли.
Давайте предположим, что мы подходим к этому итеративно :) Я уже упоминал, что граф разбора может быть не только деревом (то есть может быть общим графом), но это конкретная ситуация, и при чистом синтаксическом анализе она не возникает. Итак, возможно, мы вернемся к этому сценарию позже, а пока предположим, что в результате синтаксического анализа создается дерево.
Итак, если кто-то захочет показать мне новый парсер (парсер зависимостей), первое, что я у него спрошу, — поддерживает ли алгоритм построение непроективных деревьев и может ли он построить все многообразие вариантов парсинга.
Деревья называются проективными, если их ветви не пересекаются с проекциями на слова исходного предложения.
Это происходит, если всегда объединять в общий узел только соседние элементы.
В принципе, в большинстве случаев происходит именно это: 
Но бывает, что нужно соединить слова между собой, «перепрыгивая» через третье слово: 
(Допускаю, что словесные «колбаски» типа «хочет помочь накормить» в разных теориях обрабатываются по-разному.
На рисунке показан только один из вариантов.
) Насколько я понимаю, такие ситуации вообще не обрабатываются при разборе фразовой структуры.
Потому что грамматики Хомского по определению описывают только элементы, непосредственно примыкающие друг к другу.
Когда апологеты парсинга зависимостей стали говорить, что такой подход позволяет работать с более свободным порядком слов (чем в английском), хомскианцы ответили: сначала напишите парсер, который сможет строить непроективные деревья — без них преимущества потенциальной свободы маленькие.
Насколько актуальна проблема? В одной статье пишут, что при анализе реальных текстов на чешском языке «непроективность» выявлена в 23% случаев.
Часто.
Проблема с непроективными деревьями в том, что если нам позволить попытаться склеить любое слово с любым другим, мы сразу выходим за пределы всех вежливых норм по объёму вычислений.
Фактически в худшем случае мы получаем полный перебор всех возможных графов с N словесными вершинами, то есть задачу экспоненциальной сложности.
Тут вмешались теоретики и доказали, что ценой небольших ограничений возможностей парсера можно снизить его вычислительную сложность до «приемлемой» (детали не изучал, точные расчеты дать не могу).
В то же время для той же чешской коллекции документов этот ограниченный анализатор будет «не по зубам» всего лишь 0,5% предложений.
Кстати, первые упоминания о непроективном разборе предложений появились совсем недавно — примерно 1997 .
Это касается вопроса о том, насколько в принципе можно доверять литературе в нашей области.
Особенно эти замечательные книги восьмидесятых годов, в которых «все уже решено».
Теперь о кратности разбора.
В принципе, это та же проблема, но с другой стороны.
Если мы попытаемся построить все допустимые деревья разбора, мы попадем в одну и ту же «экспоненциальную дыру».
Понятно, что вариантов анализа будет два-три, а то и четыре.
Однако в процессе попыток приклеить что-либо к чему-либо возникают явные накладные расходы :) Понятно, что многие слова неоднозначны, но их интерпретация не влияет на тип дерева, то есть на синтаксический анализ: «Я храню деньги в банке».
Здесь анализ ясен: я храню свои деньги (где?) – в банке.
Неважно, есть ли у меня стеклянная банка или каменное здание банка.
Есть «промежуточные» варианты.
«По улице шла девушка с косой».
Всегда можно разобрать так: девушка (с чем?) – с косой.
И выбрать можно: девочку (какую?) – с косой (если речь о прическе); девушка (с чем?) - с косой (если речь идет о металлической косе).
Есть и очевидные случаи совсем других деревьев.
Мой любимый пример: «он увидел ее перед глазами».
Первый вариант понятен: он увидел (кого?) ее (где?) перед своими глазами.
Но есть и «маргинальная» трактовка: он видел (что?) это перед (т.е.
лицевую часть) (что/как?) - своими глазами.
Не буду врать, но кроме XDG/XDK я не могу вспомнить ни одного проекта, способного построить весь набор допустимых деревьев.
Пожалуй, на сегодня закончим.
Я хочу спать :) Теги: #nlp #обработка слов #обработка слов #компьютерная лингвистика #искусственный интеллект #Обработка естественного языка
-
Бесплатные Форумы Для Начинающих
19 Oct, 24 -
Стартапы, Команды И Продюсеры
19 Oct, 24 -
Куда Идем?
19 Oct, 24 -
Автомойка. Собираем Через Яндекс Директ?
19 Oct, 24
