Рекурсивная переходная сеть с фильтрацией

Рекурсивная переходная сеть с фильтрацией и извлечением ( FPRTN ), ^[1] или просто сеть с фильтрацией ( FPN ), представляет собой рекурсивную переходную сеть ( RTN ) ^[2] расширен за счет сопоставления состояний с ключами, где для возврата из перехода к подпрограмме требуется, чтобы состояния приемника и возврата были сопоставлены с одним и тем же ключом. RTN — это конечные автоматы , которые можно рассматривать как автоматы с конечным числом состояний, расширенные стеком возвращаемых состояний; а также потреблять переходы и $\varepsilon$ -переходы, RTN могут определять переходы вызовов. Эти переходы выполняют переход подпрограммы , помещая целевое состояние перехода в стек и переводя машину в вызываемое состояние. Каждый раз, когда достигается состояние акцептора, состояние возврата наверху стека выскакивает, при условии, что стек не пуст, и машина переводится в это состояние.

В этой статье мы называем рекурсивные переходные сети с фильтрацией и извлечением FPN , хотя эта аббревиатура неоднозначна (например: нечеткие сети Петри ). Сети с фильтрацией и FPRTN являются однозначной альтернативой.

Формальное определение

ФПН — это структура $(Q,K,\Sigma ,\delta ,\kappa ,Q_{I},F)$ где

$Q$ представляет собой конечное множество состояний,
$K$ представляет собой конечный набор ключей,
$\Sigma$ — конечный входной алфавит,
$\delta :Q\times (\Sigma \cup \{\varepsilon \}\cup Q)\to Q$ — частичная функция перехода, $\varepsilon$ будучи пустым символом,
$\kappa :Q\to K$ это карта состояний с ключами,
$Q_{I}\subseteq Q$ – набор начальных состояний, а
$F\subseteq Q$ — это набор состояний принятия.

Переходы

Переходы представляют собой возможность вывода ФПН из исходного состояния. $q_{s}$ в целевое состояние $q_{t}$ возможно, выполнив дополнительное действие. В зависимости от этого действия различают следующие типы явно -определенных переходов:

$\varepsilon$ -переходы – это переходы вида $\delta (q_{s},\varepsilon )\to q_{t}$ и не выполнять никаких дополнительных действий,
потребляющие переходы - это переходы вида $\delta (q_{s},\sigma )\to q_{t}$ и использовать входной символ $\sigma$ , и
переходы вызовов — это переходы вида $\delta (q_{s},q_{c})\to q_{t}$ и выполнить переход подпрограммы в вызываемое состояние $q_{c}$ прежде чем достичь $q_{t}$ .

Поведение переходов вызовов определяется двумя видами неявно определенных переходов:

за каждый переход вызова $\delta (q_{s},q_{c})\to q_{t}$ FPN неявно определяет переход , который выводит машину из $q_{s}$ к $q_{c}$ толкая $q_{t}$ в стек и
для каждой пары состояний $(q_{f},q_{r})\in F\times Q$ FPN неявно определяет всплывающий переход , который выводит машину из $q_{f}$ к $q_{r}$ выскакивая $q_{r}$ из стека, если только $q_{r}$ это состояние на вершине стека и $\kappa (q_{f})=\kappa (q_{r})$ .

Push-переходы инициализируют переходы подпрограммы , а pop-переходы эквивалентны операторам возврата .

Цель

Текст ( естественный язык ) может быть обогащен метаинформацией путем применения RTN с выводом ; например, RTN, вставляющая теги XML , может использоваться для преобразования обычного текста в структурированный документ XML. RTN с выходными данными, представляющими естественного языка, грамматику будет разграничивать и добавлять синтаксическую структуру каждого текстового предложения (см. синтаксический анализ ). Другие RTN с выводом могут просто отмечать текстовые сегменты, содержащие соответствующую информацию (см. Извлечение информации ). Применение RTN с выходными данными, представляющими неоднозначную грамматику, приводит к набору возможных переводов или интерпретаций входных данных. Вычисление этого набора имеет экспоненциальную стоимость в худшем случае , даже для анализатора Эрли для RTN с выходом, ^[3] из-за случаев, когда количество переводов увеличивается экспоненциально по отношению к длине ввода; например, количество интерпретаций предложения естественного языка увеличивается экспоненциально по отношению к количеству неразрешенных вложений предложных фраз : ^[4]^[5]

в предложении девочка видела обезьяну в подзорную трубу , неизвестно, пользовалась ли девочка телескопом или обезьяна держала его (2 ¹ интерпретации),
в предложении девочка увидела обезьяну в подзорную трубу в саду , также неизвестно, была ли обезьяна в саду или действие происходило в саду (2 ² интерпретации),
в предложении девочка увидела обезьяну в подзорную трубу в саду под деревом , также неизвестно, была ли обезьяна под деревом или действие происходило под деревом (2 ³ интерпретации),
и т. д.

FPN служат компактным представлением этого набора переводов, позволяя вычислять его в кубическом времени с помощью парсера, подобного Эрли. ^[1] Состояния FPN соответствуют состояниям выполнения (см. шаги инструкции ) анализатора Эрли для RTN без вывода, а переходы FPN соответствуют возможным переводам входных символов. $\kappa$ карта результирующего FPN дает соответствие между представленными выходными сегментами и распознанными входными сегментами: с учетом распознанной входной последовательности $\sigma _{1}\ldots \sigma _{l}$ и путь FPN $p$ начиная с состояния $q$ и заканчивая состоянием $q^{\prime }$ , $p$ представляет возможный перевод входного сегмента $\sigma _{\kappa (q)+1}\ldots \sigma _{\kappa (q^{\prime })}$ . Функция фильтрованного извлечения необходима для того, чтобы пути FPN не представляли трансляции разъединенных или перекрывающихся входных сегментов: вызов FPN может содержать несколько путей трансляции из вызываемого состояния в состояние принимающего, где соответствующие им входные сегменты имеют одинаковые начальную точку, но не обязательно имеют одинаковую длину. состояниями возврата являются только состояния возврата, соответствующие той же точке ввода, что и состояние получателя, завершающее вызов Действительными .

Ссылки

^ Перейти обратно: ^а ^б Хавьер М. Састре, «Эффективный синтаксический анализ с использованием рекурсивных переходных сетей с фильтрацией» , Конспект лекций по искусственному интеллекту , 5642 : 241-244, 2009 г.
^ Уильям А. Вудс, «Грамматики сети переходов для анализа естественного языка» , Communications of the ACM , ACM Press , 13 :10:591-606, 1970
^ Хавьер М. Састре и Микель Л. Форкада, «Эффективный синтаксический анализ с использованием рекурсивных переходных сетей с выводом» , Конспект лекций по информатике , 5603 : 192-204, 2009 г.
^ Адвайт Ратнапархи, « Статистические модели для неконтролируемого прикрепления предложных фраз » , ACL-36: Материалы 36-го ежегодного собрания Ассоциации компьютерной лингвистики и 17-й Международной конференции по компьютерной лингвистике, стр. 1079-1085, 1998.
^ Мириам Батт, « Чанк/мелкий анализ » , конспекты лекций, 2002 г.

[sastre09jb-1] Перейти обратно: ^а ^б Хавьер М. Састре, «Эффективный синтаксический анализ с использованием рекурсивных переходных сетей с фильтрацией» , Конспект лекций по искусственному интеллекту , 5642 : 241-244, 2009 г.

[woods70jb-2] Уильям А. Вудс, «Грамматики сети переходов для анализа естественного языка» , Communications of the ACM , ACM Press , 13 :10:591-606, 1970

[sastre09ja-3] Хавьер М. Састре и Микель Л. Форкада, «Эффективный синтаксический анализ с использованием рекурсивных переходных сетей с выводом» , Конспект лекций по информатике , 5603 : 192-204, 2009 г.

[ratnaparkhi98ip-4] Адвайт Ратнапархи, « Статистические модели для неконтролируемого прикрепления предложных фраз » , ACL-36: Материалы 36-го ежегодного собрания Ассоциации компьютерной лингвистики и 17-й Международной конференции по компьютерной лингвистике, стр. 1079-1085, 1998.

[5] Мириам Батт, « Чанк/мелкий анализ » , конспекты лекций, 2002 г.

[1]

[2]

[3]

[4]

[5]