[Natural Language Processing] Грамматический разбор для естественных языков. Ч.1: Языки описания языков
Автор
Сообщение
news_bot ®
Стаж: 6 лет 9 месяцев
Сообщений: 27286
Исторически первой попыткой формализовать язык и автоматизировать его разбор были регулярные выражения, придуманные С.К. Клейни в 1951. Регулярное выражение составляется из символов языка ("терминалов"), и трёх операций: конкатенация, чередование и замыкание. Для разбора регулярных выражений достаточно ДКА без памяти: разборщик знает, в каком состоянии он находится сейчас, но не помнит ничего о своих прошлых состояниях. Это значит, что языки, допускающие вложенные конструкции — например, язык вложенных скобок (n)n и язык самих регулярных выражений — невозможно описать регулярными выражениями. Естественные языки тоже допускают конструкции неограниченной вложенности ("Вот два петуха, которые будят того пастуха, который бранится с коровницей строгою, которая доит корову безрогую, лягнувшую старого пса без хвоста, который за шиворот треплет кота, который пугает и ловит синицу, которая часто ворует пшеницу, которая в тёмном чулане хранится в доме, который построил Джек."), поэтому для описания естественных языков регулярные выражения недостаточно выразительны.Более выразительный способ описания языков — формальные грамматики — предложил Н. Чомски в 1956. Предложения на английском довольно неплохо поддаются такому описанию:
S → NP VP
NP → N' | Det N'
N' → N | Adj N | N PP | N' CP
VP → V | V NP | V PP
PP → P NP
CP → VnP | C VP | C S
VnP → Vn | Adv VnP | VnP Conj Vn
N → This | rooster | morn | judge | man | maiden | cow |
horn | dog | cat | rat | malt | house | Jack
V → is | crowed | woke | married | kissed | milked |
tossed | worried | killed | ate | lay | built
Vn → shaven | shorn | tattered | torn | forlorn
Adj → crumpled
Adv → all
P → in | with
Det → the
C → that
Conj → and
Этой формальной грамматики из пары десятков абстрактных символов ("нетерминалов") и пары десятков правил вывода (не считая лексикона) достаточно, чтобы разобрать вложенные конструкции в том самом предложении про петуха, коровницу, пса и кота:
Для контекстно-свободных грамматик (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
===========
Похожие новости:
- [Читальный зал, Лайфхаки для гиков, Здоровье] Нехорошее Кароси. Как не умереть от переработок?
- [C++, API] Альтернатива ML-Agents: интегрируем нейросети в Unity-проект с помощью PyTorch C++ API (перевод)
- [Машинное обучение, Здоровье, Natural Language Processing] Тематическое исследование распознавания именованных сущностей в биомедицине (перевод)
- [Научно-популярное] Граф Цеппелин, открывший эпоху дирижаблей
- [Разработка веб-сайтов, ReactJS, Serverless] Реализация подписки на обновления с помощью Google Sheets, Netlify Functions и React. Часть 1
- [Мессенджеры, ООП, Функциональное программирование, Kotlin, Natural Language Processing] Распознавание команд
- [GTD] Воспитание Obsidian — вашего персонального информационного менеджера
- [Разработка мобильных приложений, API, Разработка для Office 365] 4 технических решения, которые делают API сервис успешным (перевод)
- [Работа с 3D-графикой, Разработка игр, Видеокарты, Игры и игровые приставки] Краткая история 3D в видео-играх
- [Управление персоналом, Карьера в IT-индустрии, Научно-популярное] Откровения трезвого инженера (перевод)
Теги для поиска: #_natural_language_processing, #_mcfg, #_blog_kompanii_maklaud (
Блог компании Маклауд
), #_natural_language_processing
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Текущее время: 22-Ноя 22:28
Часовой пояс: UTC + 5
| Автор | Сообщение |
|---|---|
|
news_bot ®
Стаж: 6 лет 9 месяцев |
|
 Исторически первой попыткой формализовать язык и автоматизировать его разбор были регулярные выражения, придуманные С.К. Клейни в 1951. Регулярное выражение составляется из символов языка ("терминалов"), и трёх операций: конкатенация, чередование и замыкание. Для разбора регулярных выражений достаточно ДКА без памяти: разборщик знает, в каком состоянии он находится сейчас, но не помнит ничего о своих прошлых состояниях. Это значит, что языки, допускающие вложенные конструкции — например, язык вложенных скобок (n)n и язык самих регулярных выражений — невозможно описать регулярными выражениями. Естественные языки тоже допускают конструкции неограниченной вложенности ("Вот два петуха, которые будят того пастуха, который бранится с коровницей строгою, которая доит корову безрогую, лягнувшую старого пса без хвоста, который за шиворот треплет кота, который пугает и ловит синицу, которая часто ворует пшеницу, которая в тёмном чулане хранится в доме, который построил Джек."), поэтому для описания естественных языков регулярные выражения недостаточно выразительны.Более выразительный способ описания языков — формальные грамматики — предложил Н. Чомски в 1956. Предложения на английском довольно неплохо поддаются такому описанию: S → NP VP
NP → N' | Det N' N' → N | Adj N | N PP | N' CP VP → V | V NP | V PP PP → P NP CP → VnP | C VP | C S VnP → Vn | Adv VnP | VnP Conj Vn N → This | rooster | morn | judge | man | maiden | cow | horn | dog | cat | rat | malt | house | Jack V → is | crowed | woke | married | kissed | milked | tossed | worried | killed | ate | lay | built Vn → shaven | shorn | tattered | torn | forlorn Adj → crumpled Adv → all P → in | with Det → the C → that Conj → and  Для контекстно-свободных грамматик (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) S → XY ⇐ P → X,Y
P → a,a | b,b | XY,ZW ⇐ P → X,Z ∧ P → Y,W  Практическая польза 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 |
|
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Текущее время: 22-Ноя 22:28
Часовой пояс: UTC + 5