Метод нормальной формы Хомского: влияние на производительность анализатора CYK?

9

Парсеры диаграмм могут быть реализованы на основе нормальной формы Хомского или непосредственно на основе правил производства. Предположим на данный момент, что у нас есть анализатор диаграмм CYK, который использует нормальную форму Хомского. Бинаризация не определяется однозначно. Влияет ли это на производительность разбора диаграммы CYK. Можно ли это использовать для повышения производительности анализатора диаграмм CYK?

fl.formal-languages parsing Кава
источник
Подходы создают грамматики одинакового размера, не так ли? CYK всегда заполняет всю таблицу, поэтому вы можете только ускорить проверку «Есть ли подходящее правило?». Следовательно, я ожидаю, что влияние будет иметь только количество правил, а не грамматическая структура.
Рафаэль
Метод, используемый для бинаризации, также влияет на размер грамматики, который влияет на производительность CYK: informatica-didactica.de/cmsmadesimple/… обсуждает некоторые альтернативы CNF
Макс.

Ответы:

6

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

Немного поиска я нашел Лучшую Бинаризацию для CKY Parsing (Song, Ding и Lin, EMNLP 2008), которая, кажется, окончательно заключает, что вы можете выбрать «лучшую» или «худшую» бинаризацию относительно строк, которые вы на самом деле ожидаете чтобы разобрать. Их название «парольных тупиков», которые на практике можно было бы надеяться свести к минимуму, кажется неполным , и на первой странице есть хороший пример.

Роб Симмонс
источник
Рассмотрим грамматику, включая произведения (S -> ABC) (T -> ABD). Если «BC» всегда предшествует «A», но за «AB» иногда не следует «C», при объединении B и C будет меньше тупиков, и относительная частота не имеет значения. Ваша точка зрения о «немногих» и «многих» имеет смысл, если слова появляются в случайном порядке, но я думаю, что Сонг, Дин и Лин делают это с использованием частоты ngram, что немного сложнее. Они также указывают, что, в моем примере, вы все равно можете выиграть с бинаризацией "AB", используя обмен!
Роб Симмонс
4

На самом деле, нормальная форма Хомского (CNF) не требует запуска CYK, только бинаризация. Бинаризация необходима для сохранения кубической сложности синтаксического анализа, но важна только в отношении нетерминалов (NT). Но затем, если у вас есть правила, включающие только 2 нетерминала и несколько терминалов, алгоритм CYK становится более сложным для программирования и объяснения.

Как вы говорите, есть много способов сделать бинаризацию. Некоторые из них будут давать меньшие грамматики, чем другие. Например

X -> B C D
Y -> B C E

может быть преобразован в двоичную форму как

X -> Z D
Y -> Z E
Z -> B C

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

Но с другими правилами вы можете захотеть факторизовать конец правил, а не начало.

Я не знаком с работой Сонга, Дина и Линя , на которую ссылается ответ Роба Симмонса . Идея интересная, но мне интересно, насколько она эффективна по сравнению с другими способами оптимизации вычислений. Я не так боюсь.

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

CYK - это лишь одна из самых простых вариаций в семействе алгоритмов, которые, очевидно, построены на одной модели динамического программирования. Я говорю, по- видимому, потому что самая простая версия этих алгоритмов не известна как динамическое программирование, а как перекрестный продукт. Это старая конструкция CF-грамматики G, которая порождает пересечение языка CF-грамматики F и обычного языка FSA A. из-за работы Бар Гилеля, Перлеса и Шамира (1961) , как отметил Ланг в 1995 году .

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

Будучи восходящим, алгоритм CKY производит бесполезные вычисления частичных разборов, которые не могут быть выведены из аксиомы грамматики.

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

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

Оптимизация процесса синтаксического анализа также тесно связана с «качеством» полученной структуры синтаксического анализа, которая представляет все возможные синтаксические анализы, и часто называется (разделяемым) лесом анализа. Я обсуждаю это в другом ответе .

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

Babou
источник