Конечный преобразователь

Преобразователь с конечным числом состояний ( FST ) — это конечный автомат с двумя лентами памяти , следуя терминологии машин Тьюринга : входная лента и выходная лента. Это контрастирует с обычным конечным автоматом , имеющим одну ленту. FST — это тип конечного автомата (FSA), который отображает два набора символов. FST является более общим, чем FSA. FSA определяет формальный язык , определяя набор принимаемых строк, а FST определяет отношения между наборами строк.

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

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

Обзор

Внешние видео
Преобразователи конечных состояний // Технологический институт Карлсруэ , видео на YouTube

распознает автомат Можно сказать, что строку , если мы рассматриваем содержимое его ленты как входные данные. Другими словами, автомат вычисляет функцию, которая отображает строки в набор {0,1}. Альтернативно мы можем сказать, что автомат генерирует строки, что означает просмотр его ленты как выходной ленты. С этой точки зрения автомат генерирует формальный язык , который представляет собой набор строк. Два вида автоматов эквивалентны: функция, которую вычисляет автомат, является в точности индикаторной функцией набора генерируемых им строк. Класс языков, порождённых конечными автоматами, известен как класс регулярных языков .

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

Каждый преобразователь конечных состояний «строка-строка» связывает входной алфавит Σ с выходным алфавитом Γ. Отношения R на Σ*×Γ*, которые могут быть реализованы как преобразователи конечных состояний, называются рациональными отношениями . Рациональные отношения, которые являются частичными функциями , т. е. которые связывают каждую входную строку из Σ* не более чем с одной Γ*, называются рациональными функциями .

Преобразователи конечных состояний часто используются для фонологического и морфологического анализа в исследованиях и приложениях обработки естественного языка . Пионерами в этой области являются Рональд Каплан , Лаури Карттунен , Мартин Кей и Киммо Коскенниеми . Распространенным способом использования преобразователей является так называемый «каскад», когда преобразователи для различных операций объединяются в один преобразователь путем многократного применения оператора композиции (определенного ниже).

Формальная конструкция

Формально конечный преобразователь T представляет собой 6-кортеж ( Q , Σ , Γ , I , F , δ ) такой, что:

• Q — конечное множество , множество состояний ;
• Σ — конечное множество, называемое входным алфавитом ;
• Γ — конечное множество, называемое выходным алфавитом ;
• I — подмножество Q ; множество начальных состояний ,
• F — подмножество Q , множество конечных состояний ; и
• $\delta \subseteq Q\times (\Sigma \cup \{\epsilon \})\times (\Gamma \cup \{\epsilon \})\times Q$ (где ε — пустая строка ) — отношение перехода .

Мы можем рассматривать ( Q , δ ) как помеченный ориентированный граф , известный как граф переходов T Q : множество вершин равно , и $(q,a,b,r)\in \delta$ означает, что существует помеченное ребро, идущее из вершины q в вершину r . Мы также говорим, что a — входная метка , а b — выходная метка этого ребра.

ПРИМЕЧАНИЕ. Это определение конечного преобразователя также называется буквенным преобразователем (Roche and Schabes 1997); Возможны альтернативные определения, но все они могут быть преобразованы в преобразователи, соответствующие этому.

Определите расширенное отношение перехода $\delta ^{*}$ как наименьшее множество такое, что:

• $\delta \subseteq \delta ^{*}$;
• $(q,\epsilon ,\epsilon ,q)\in \delta ^{*}$ для всех $q\in Q$; и
• в любое время $(q,x,y,r)\in \delta ^{*}$ и $(r,a,b,s)\in \delta$ затем $(q,xa,yb,s)\in \delta ^{*}$.

Расширенное отношение перехода — это, по сути, рефлексивное транзитивное замыкание графа переходов, дополненное для учета меток ребер. Элементы $\delta ^{*}$ известны как пути . Метки ребер пути получаются путем объединения меток ребер составляющих его переходов по порядку.

Поведение ] , преобразователя T представляет собой рациональное отношение [ T определяемое следующим образом: $x[T]y$ тогда и только тогда, когда существует $i\in I$ и $f\in F$ такой, что $(i,x,y,f)\in \delta ^{*}$. Это означает, что T преобразует строку $x\in \Sigma ^{*}$ в строку $y\in \Gamma ^{*}$ если существует путь от начального состояния к конечному состоянию, входная метка которого равна x , а выходная метка — y .

Взвешенные автоматы

См. также: Серия Rational

Преобразователи конечных состояний могут иметь взвешивание, при этом каждый переход помечается весом в дополнение к меткам входа и выхода. Взвешенный преобразователь конечных состояний (WFST) над набором K весов можно определить аналогично невзвешенному преобразователю как 8-кортеж T =( Q , Σ, Γ, I , F , E , λ , ρ ) , где:

• Q , Σ, Γ, I , F определены, как указано выше;
• $E\subseteq Q\times (\Sigma \cup \{\epsilon \})\times (\Gamma \cup \{\epsilon \})\times Q\times K$ (где ε — пустая строка ) — конечное множество переходов;
• $\lambda :I\rightarrow K$ отображает начальные состояния на веса;
• $\rho :F\rightarrow K$ отображает конечные состояния на веса.

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

Стохастический ТФТ

Стохастические FST (также известные как вероятностные FST или статистические FST), предположительно, являются формой взвешенного FST.

Операции с конечными преобразователями

Следующие операции, определенные на конечных автоматах, также применимы к конечным преобразователям:

• Союз . Для данных преобразователей T и S существует преобразователь $T\cup S$ такой, что $x[T\cup S]y$ тогда и только тогда, когда $x[T]y$ или $x[S]y$.
• Конкатенация . Для данных преобразователей T и S существует преобразователь $T\cdot S$ такой, что $x[T\cdot S]y$ тогда и только тогда, когда существуют $x_{1},x_{2},y_{1},y_{2}$ с $x=x_{1}x_{2},y=y_{1}y_{2},x_{1}[T]y_{1}$ и $x_{2}[S]y_{2}.$
• Закрытие Клини . Учитывая преобразователь T , может существовать преобразователь $T^{*}$ со следующими свойствами:

$\epsilon [T^{*}]\epsilon$; ( к1 )

если $w[T^{*}]y$ и $x[T]z$, затем $wx[T^{*}]yz$; ( к2 )

и $x[T^{*}]y$ не выполняется, если это не предписано ( k1 ) или ( k2 ).

• Состав . Для данного преобразователя T на алфавитах Σ и Γ и преобразователя S на алфавитах Γ и Δ существует преобразователь $T\circ S$ на Σ и Δ такие, что $x[T\circ S]z$ тогда и только тогда, когда существует строка $y\in \Gamma ^{*}$ такой, что $x[T]y$ и $y[S]z$. Эта операция распространяется на взвешенный случай.

В этом определении используются те же обозначения, которые используются в математике для композиции отношений . Однако традиционное прочтение композиции отношений происходит наоборот: учитывая два отношения T и S , $(x,z)\in T\circ S$ когда существуют такие y , что $(x,y)\in S$ и $(y,z)\in T.$

• Проекция на автомат. Есть две функции проецирования: $\pi _{1}$ сохраняет входную ленту и $\pi _{2}$ сохраняет выходную ленту. Первая проекция, $\pi _{1}$ определяется следующим образом:

Для преобразователя T существует конечный автомат $\pi _{1}T$ такой, что $\pi _{1}T$ принимает x тогда и только тогда, когда существует строка y , для которой $x[T]y.$

Вторая проекция, $\pi _{2}$ определяется аналогично.

• Определенность . Учитывая преобразователь T , мы хотим построить эквивалентный преобразователь, который имеет уникальное начальное состояние и такой, чтобы никакие два перехода, выходящие из любого состояния, не имели одну и ту же входную метку. Конструкция силового набора может быть распространена на датчики или даже на взвешенные датчики, но иногда не может остановиться; действительно, некоторые недетерминированные преобразователи не допускают эквивалентных детерминированных преобразователей. характеристики детерминируемых преобразователей. Предложены вместе с эффективными алгоритмами для их тестирования: они основаны на полукольце, используемом в случае взвешивания, а также на общем свойстве конструкции преобразователя ( свойстве двойников ).
• Увеличение веса для утяжеленного корпуса.
• Минимизация для взвешенного случая.
• Удаление эпсилон-переходов .

Дополнительные свойства конечных преобразователей

• Можно решить , является ли отношение [ T ] преобразователя T пустым.
• Можно решить, существует ли строка y такая, что x [ T ] y для данной строки x .
• Неизвестно, эквивалентны ли два преобразователя. Однако эквивалентность разрешима в частном случае, когда отношение [ T ] преобразователя T является (частичной) функцией.
• Если определить алфавит меток $L=(\Sigma \cup \{\epsilon \})\times (\Gamma \cup \{\epsilon \})$, преобразователи с конечным состоянием изоморфны NDFA по алфавиту $L$, и поэтому может быть детерминирован (превращен в детерминированные конечные автоматы над алфавитом $L=[(\Sigma \cup \{\epsilon \})\times \Gamma ]\cup [\Sigma \times (\Gamma \cup \{\epsilon \})]$) и впоследствии минимизируются так, чтобы они имели минимальное количество состояний.

Приложения

FST используются лексического анализа на этапе компиляторами для связывания семантического значения с обнаруженными токенами.

Контекстно-зависимые правила переписывания формы a → b / c_d . , , используемые в лингвистике для моделирования фонологических правил и изменения звука вычислительно эквивалентны преобразователям с конечным состоянием, при условии, что приложение нерекурсивно, т. е. правило не разрешено переписывать одну и ту же подстроку дважды.

Взвешенные FST нашли применение в обработке естественного языка , включая машинный перевод , и в машинном обучении . Реализацию тегирования части речи можно найти как один из компонентов OpenGrm. библиотека.

См. также

• Мучнистая машина
• Машина Мура
• Морфологический словарь
• foma (software)
• Датчик дерева
• Реляционный преобразователь

Ссылки

• Аллаузен, Кирилл; Мори, Мехриар (2003). «Эффективные алгоритмы проверки свойства близнецов» (PDF) . Журнал автоматов, языков и комбинаторики . 8 (2): 117–144.
• Коскенниеми, Киммо (1983), Двухуровневая морфология: общая вычислительная модель распознавания и производства словоформ (PDF) , Департамент общей лингвистики, Хельсинкский университет , заархивировано из оригинала (PDF) 21 декабря 2018 г. , получено 10 января 2010 г.
• Мори, Мехриар (2004). «Алгоритмы взвешенных преобразователей конечных состояний. Обзор» (PDF) . Формальные языки и приложения . Исследования нечеткости и мягких вычислений. Том. 148. стр. 551–564. дои : 10.1007/978-3-540-39886-8_29 . ISBN  978-3-642-53554-3 .
• Гриффитс, ТВ (1968). «Неразрешимость проблемы эквивалентности для Λ-свободных недетерминированных обобщенных машин». Журнал АКМ . 15 (3). АКМ: 409–413. дои : 10.1145/321466.321473 .

Внешние ссылки

• OpenFst — библиотека с открытым исходным кодом для операций FST.
• Морфология конечных состояний — книга, заархивированная 25 марта 2022 г. в Wayback Machine XFST/LEXC, описание реализации Xerox преобразователей с конечным состоянием, предназначенных для лингвистических приложений.
• Хельсинкская реализация с открытым исходным кодом и расширение Xerox fst.
• FOMA — реализация с открытым исходным кодом большинства возможностей реализации Xerox XFST/LEXC.
• Stuttgart Finite State Transducer Tools , еще один набор инструментов FST с открытым исходным кодом.
• Java FST Framework — Java FST Framework с открытым исходным кодом, способная обрабатывать текстовый формат OpenFst.
• Vcsn. Архивировано 23 июня 2020 г. на Wayback Machine , платформе с открытым исходным кодом (C++ и IPython) для взвешенных автоматов и рациональных выражений.

Дальнейшее чтение

• Юрафски, Дэниел ; Джеймс Х. Мартин (2000). Речевая и языковая обработка . Прентис Холл. стр. 71–83 . ISBN  0-13-095069-6 .
• Корнаи, Андраш (1999). Расширенные модели языка с конечным состоянием . Издательство Кембриджского университета. ISBN  0-521-63198-Х .
• Рош, Эммануэль; Ив Шабес (1997). Обработка конечного языка . МТИ Пресс. стр. 1 –65. ISBN  0-262-18182-7 .
• Бисли, Кеннет Р.; Лаури Карттунен (2003). Морфология конечного состояния . Центр изучения языка и информации. ISBN  1-57586-434-7 .
• Рорк, Брайан; Ричард Спроат (2007). Вычислительные подходы к морфологии и синтаксису . Издательство Оксфордского университета. ISBN  978-0-19-927478-9 .
• Берстель, Жан (1979). Трансдукции и контекстно-свободные языки . Тойбнер Верлаг. . Бесплатная PDF-версия