Разбор Эрли с пропуском шума и извлечение деревьев по порядку из общих упакованных синтаксических лесов

Цитата

Доманн, Джереми. 2020. Разбор Эрли с пропуском шума и извлечение деревьев по порядку из общих упакованных синтаксических лесов. Кандидатская диссертация, Гарвардский колледж.

Аннотация

В этой диссертации я определяю 3 недостатка современного синтаксического анализа Эрли и предлагаю унифицированный сквозной алгоритм синтаксического анализа Эрли, который устраняет эти недостатки. В частности, я обращаюсь к следующим вопросам:

1. Алгоритм Эрли традиционно возвращает синтаксические анализы без какого-либо связанного с ними ранжирования. В дополнение к тому, что синтаксический анализ не ранжируется во время синтаксического анализа, структура данных, используемая для представления результатов синтаксического анализа, совместно-упакованный лес синтаксического анализа (SPPF), не имеет встроенного способа извлечения деревьев в определенном порядке.

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

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

3. Время выполнения алгоритма Эрли пропорционально размеру грамматики. Текущие современные методы существенно ограничивают размер грамматик, которые могут быть практически проанализированы с разумными ограничениями памяти и времени.

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

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

Во второй главе я рассматриваю проблему 1, вводя структуру для ранжирования синтаксических анализов в зависимости от их внутренних атрибутов. Я представляю этот подход как расширение работы, проделанной в [41] и [21]. [41] вводит синтаксический анализ как форму дедуктивного рассуждения о логической системе, определяемой контекстно-свободной грамматикой, а [21] объединяет ряд понятий дедуктивного синтаксического анализа (например, распознавание, присвоение вероятностей синтаксическим анализам и т.

д.) как выполнение вычислений. на соответствующим образом определенном полукольце.

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

В главах 3 и 4 я обращаюсь к первым двум проблемам, описанным выше, путем введения расширений стандартного синтаксического анализатора Эрли и стандартного алгоритма построения SPPF для обработки пропусков токенов в зашумленных входных данных, а также нововведений для связывания каждого состояния Эрли и узла SPPF с атрибутами его лучшего происхождения. В главе 3 я доказываю, что модифицированный алгоритм синтаксического анализа с пропуском шума выполняется за время O(w · n 2 ), где w — количество токенов, которое можно пропустить между любыми объясненными токенами, также называемое «шириной пропуска».

В четвертой главе подробно описывается построение нового варианта SPPF, называемого упорядоченным SPPF, который по своему замыслу позволяет нам связать лучшие атрибуты деривации с узлами SPPF и упрощает извлечение лучшего дерева из леса. В этой главе я показываю, что построение упорядоченного SPPF может быть выполнено за время O(w 2 n 3 · log(wn))

В пятой главе я рассматриваю вторую проблему, показывая, что упорядоченный SPPF из четвертой главы можно использовать не только для эффективного извлечения лучшего дерева в лесу, но и для ранжирования k лучших синтаксических анализов путем применения функции полезности к их атрибутам. Я показываю, что мой эффективный алгоритм top-k может извлекать первые k синтаксических анализов за время O(kn 2 ·log(kn).

чтобы сделать синтаксический анализ больших грамматик более эффективным.0005

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

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

Условия эксплуатации

Эта статья доступна в соответствии с положениями и условиями, применимыми к другим публикуемым материалам, изложенным по адресу http://nrs.harvard.edu/urn-3:HUL.InstRepos:dash.current.terms-of-use#LAA

.

[PDF] Полноценный анализ левого угла для минималистской грамматики

• title={Звук и полный разбор левого угла для минималистской грамматики}, автор = {Майло {\ vs} Станоеви {\ ‘c} и Эдвард П.
  Стаблер}, год = {2018} }
  • Милош Станоевич, Эдвард П. Стаблер
  • Опубликовано в 2018 г.
  • Информатика, лингвистика

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

  Представление на ACL

  research.ed.ac.uk

  Статистический анализ с широким охватом и минималистскими грамматиками

  • Джон Торр

  • Информатика

  • 2019
  900 Stabler и другие с конца 1990-х годов, чтобы представить первый в истории синтаксический анализатор Minimalist Grammar (MG) с широким охватом, а также некоторые многообещающие первоначальные экспериментальные результаты.

  Алгоритм синтаксического анализа CCG с добавочным поворотом дерева

  • Милош Станоевич, Марк Стидман

  • Информатика

    NAACL

  • 2019

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

  Тестирование минималистского синтаксического анализатора грамматики на асимметрии итальянских относительных предложений

  Верхний синтаксический анализатор Stabler (2013) для минималистских грамматик использовался для учета предпочтений в автономной обработке множества, казалось бы, не связанных между собой явлений, кросс-лингвистически, с помощью…

  Нейронный анализ A* с широким покрытием для минималистских грамматик

  • Джон Торр, Милош Станоевич, Марк Стидман, Шей Б. Коэн

  • Информатика

    ACL

  • 2019

  с использованием лингвистически выразительной, но строго ограниченной грамматики вместе с адаптацией алгоритма поиска A*, используемого в настоящее время при разборе CCG.

  Нейронный анализ с широким покрытием A* для минималистских грамматик

  • А. Корхонен, Д. Траум, Л. Маркес

  • Компьютерные науки

  • 2019

  2019

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

О вычислительной сложности движений головы и скачков аффиксов

• Милош Станоевич

• Компьютерная наука

  FG

• 2019

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

Дополнительное обучение минималистским грамматикам

• П. Грабен, Рональд Ремер, Вернер Мейер, Маркус Хубер, М. Вольф

• Лингвистика, информатика

  ArXiv

• 2020

Алгоритм обучения с подкреплением для усвоения синтаксиса и семантики английских высказываний, основанный на минималистской грамматике (MG), описывается недавняя вычислительная реализация генеративной лингвистики, следовательно, потенциально разрешая все еще нерешенный спор Хомского-Скиннера.

Моделирование структурообразования в мозге с помощью разбора CCG и больших языковых моделей

• Миловс Станоевич, Джонатан Бреннан, Дональд Дунаган, Марк Стидман, Дж. Хейл

• Психология

  ArXiv

• 2022

Для моделирования естественной языковой среды исследователи обратились к широкому пониманию поведенческих и нейронных коррелятов — инструменты охвата обработки естественного языка и машинного обучения. …

Обучение минималистским числовым грамматикам с подкреплением

• П. Грабен, Рональд Ремер, Вернер Мейер, Маркус Хубер, М. Вольф

• Лингвистика, информатика

  2019 10-я Международная конференция IEEE по когнитивным информационным коммуникациям (CogInfoCom)

• 2019

минималистская грамматика (MG), недавняя вычислительная реализация генеративной лингвистики.

Инкрементный разбор CCG с максимальной маржой

• Miloš Stanojević, Mark Steedman

• Информатика

  ACL

• 2020

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

ПОКАЗАНЫ 1-10 ИЗ 47 ССЫЛОК

СОРТИРОВАТЬ ПОРелевантностьНаиболее влиятельные документыНедавность

Компактные нелеворекурсивные грамматики с использованием выборочного преобразования левого угла и факторизации

• Марк Джонсон, Брайан Роарк

• Информатика

  COLING

• 2000

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

Deterministic Left Corner Parsing (Extended Abstract)

• D. Rosenkrantz, P. M. Lewis

• Computer Science

  SWAT

• 1970

It is shown that when a particular grammatical rewriting procedure is applied to a grammar, результирующая грамматика является (сильной) LL(k) тогда и только тогда, когда исходная грамматика является (сильной) LC(k), из чего следует, что класс языков LC(k) идентичен классу языков LL(k).

Нормальная форма одного движения для минималистской грамматики

• Т. Граф, Алёна Аксенова, Аньелло Де Санто

• Информатика

  FG

• 2016

9 MG, где каждая фраза перемещается не более одного раза.

Разбор вне контекстно-свободных грамматик

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

Минималистский грамматический переход на основе перехода на основе

• Милош Станоевич

• Компьютерные науки

  LACL

• 2016

. поиска луча, и делает это очень эффективно.

Характеристика минималистских языков

• Х. Харкема

• Информатика, лингвистика

  LACL

• 2001

Сделан вывод, что минималистская грамматика слабо эквивалентна множественной контекстно-свободной грамматике.

Без остаточного движения, MG не зависят от контекста

• Г. Кобеле

• Лингвистика

  MOL

• 2009

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

Синтаксический анализ минималистских языков

• Х. Харкема, Э. Стаблер

• Информатика, лингвистика

• 2001

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