[Natural Language Processing] Грамматический разбор для естественных языков. Ч.1: Языки описания языков

Ответить на тему

Автор

Сообщение

news_bot ^®

Стаж: 6 лет 3 месяца
Сообщений: 27286

news_bot ^® написал(а)
06-Июн-2021 16:31

Цитировать

Исторически первой попыткой формализовать язык и автоматизировать его разбор были регулярные выражения, придуманные С.К. Клейни в 1951. Регулярное выражение составляется из символов языка ("терминалов"), и трёх операций: конкатенация, чередование и замыкание. Для разбора регулярных выражений достаточно ДКА без памяти: разборщик знает, в каком состоянии он находится сейчас, но не помнит ничего о своих прошлых состояниях. Это значит, что языки, допускающие вложенные конструкции — например, язык вложенных скобок (n)n и язык самих регулярных выражений — невозможно описать регулярными выражениями. Естественные языки тоже допускают конструкции неограниченной вложенности ("Вот два петуха, которые будят того пастуха, который бранится с коровницей строгою, которая доит корову безрогую, лягнувшую старого пса без хвоста, который за шиворот треплет кота, который пугает и ловит синицу, которая часто ворует пшеницу, которая в тёмном чулане хранится в доме, который построил Джек."), поэтому для описания естественных языков регулярные выражения недостаточно выразительны.Более выразительный способ описания языков — формальные грамматики — предложил Н. Чомски в 1956. Предложения на английском довольно неплохо поддаются такому описанию:

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

Для контекстно-свободных грамматик (CFG) — когда в левой части каждого правила вывода стоит ровно один нетерминал, как в этом примере — существуют эффективные алгоритмы разбора текста; поэтому почти все языки программирования описываются CFG. В отличие от языков программирования, тексты на естественных языках часто допускают несколько возможных разборов — например, [that woke the judge…]CP могло бы относиться и к mornN' — выбор между которыми требует семантического разбора. Однако для естественных языков с более гибким порядком слов, чем в английском, CFG недостаточно: уже для разбора русского стишка понадобились бы и VP → V PP, N' → N Adj ("бранится с коровницей строгою"), и VP → PP V, N' → Adj N ("в тёмном чулане хранится"); чуть ли не для каждого правила вывода в грамматику понадобилось бы добавить его "зеркальное отражение" — и тогда количество возможных разборов текста растёт экспоненциально. Ещё хуже то, что при топикализации листья поддерева, соответствующего нетерминалу, могут идти в тексте не подряд: например, в "Я тебя детям просил помочь, [а не родителям]" члены сложного дополнения [детям помочь]CP разделены сказуемым просилV. В нескольких языках — исследователи отмечают голландский и швейцарский немецкий — есть не связанные с топикализацией "параллельно-вложенные" конструкции, например:... dasmerd'chindem Hanses huuslöndhälfeaastriiche... чтомыдетейГансудомпросимпомочьпокрасить"... что мы просим детей помочь Гансу покрасить дом"Такую цепочку можно наращивать неограниченно, как в стишке про дом Джека; но глаголы во второй части предложения должны идти в том же порядке, в котором идут их дополнения в первой части предложения. Такие явления — скрэмблинг при топикализации и "параллельно-вложенные" конструкции в голландском и швейцарском немецком — формальные грамматики не в состоянии описать.Более формально можно доказать, что CFG могут описывать вложенные конструкции — в частности, язык вложенных скобок (n)n описывается тривиальной грамматикой S → () | (S) – но неиерархические зависимости описанию не поддаются: в частности, CFG не может описать язык anbncn или язык дважды повторённых строк ((a|b)+)2.В 1987 в Осакском университете разработали ещё более выразительный способ описания языков — множественные CFG (MCFG); одновременно с этим и независимо от осакцев в Университете Пенсильвании разработали линейные контекстно-свободные системы перезаписи (LCFRS), которые отличаются от MCFG только более простой формой записи. В MCFG/LCFRS нетерминалы становятся многоместными предикатами — например, эта LCFRS описывает язык дважды повторённых строк:

S(XY) ← P(X,Y)
P(a,a) ← ε
P(b,b) ← ε
P(XY,ZW) ← P(X,Z),P(Y,W)

Стрелка влево обозначает дизъюнкт Хорна. В левой части каждого правила вывода описывается составление аргументов нетерминала-предиката из терминалов и переменных; в правой перечисляются предикаты, которым переменные должны удовлетворять. Порядок записи предикатов в правой части не имеет значения. Каждая переменная, использованная в левой части, должна быть ограничена предикатом в правой части; повторное использование одной переменной не допускается. Если в левой части нет переменных, то правая часть может быть пустой — это значит, что никаких дополнительных условий, кроме совпадения терминалов, не накладывается. Способ записи LCFRS сильно отличается от принятого для CFG — например, грамматику языка дважды повторённых строк можно было бы записать в более прозрачном, хоть на практике и не используемом виде:

S → XY ⇐ P → X,Y
P → a,a | b,b | XY,ZW ⇐ P → X,Z ∧ P → Y,W

В отличие от CFG, где каждый узел дерева разбора соответствует подстроке разобранного текста, — при разборе MCFG/LCFRS узел дерева разбора может соответствовать нескольким подстрокам, идущим в тексте не подряд: (толщина линии показывает, сколько подстрок нетерминал получает от дочерних узлов)

Практическая польза MCFG/LCFRS в том, что они позволяют описать "разорванный" член предложения (детям, помочь)CP:

VP(X,Y) ← NP(X),V(Y)
CP(X,Y) ← VP(X,Y)
VP(X,YZW) ← NP(X),V(Z),CP(Y,W)
S(XYZ) ← NP(X),VP(Y,Z)

Но для практической применимости MCFG/LCFRS нужен ещё и эффективный алгоритм разбора. Этому будет посвящена ч.2.Облачные серверы от Маклауд быстрые и безопасные.Зарегистрируйтесь по ссылке выше и получите 10% скидку на первый месяц аренды сервера любой конфигурации!

===========
Источник:
habr.com
===========
Похожие новости:

Теги для поиска: #_natural_language_processing, #_mcfg, #_blog_kompanii_maklaud (
Блог компании Маклауд
), #_natural_language_processing

Профиль ЛС

Ответить на тему

Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы

Текущее время: 09-Май 16:15
Часовой пояс: UTC + 5