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

Конечный автомат с двумя лентами (вход, выход)

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

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

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

Обзор

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

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

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

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

Формальное строительство

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

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

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

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

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

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

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

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

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

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

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

Для того чтобы сделать некоторые операции над WFST хорошо определенными, удобно потребовать, чтобы набор весов образовывал полукольцо . ^[3] Два типичных полукольца, используемых на практике, — это логарифмическое полукольцо и тропическое полукольцо : недетерминированные автоматы можно рассматривать как имеющие веса в булевом полукольце . ^[4]

Стохастический FST

Стохастические FST (также известные как вероятностные FST или статистические FST) предположительно являются формой взвешенных FST. ^{[ необходима ссылка ]}

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

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

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

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

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

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

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

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

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

• Детерминизация . При наличии преобразователя T мы хотим построить эквивалентный преобразователь, который имеет уникальное начальное состояние и такой, что никакие два перехода, покидающие любое состояние, не имеют одну и ту же входную метку. Конструкция powerset может быть расширена до преобразователей или даже весовых преобразователей, но иногда не останавливается; действительно, некоторые недетерминированные преобразователи не допускают эквивалентных детерминированных преобразователей. ^[7] Были предложены характеристики детерминируемых преобразователей ^[8] вместе с эффективными алгоритмами для их проверки: ^[9] они полагаются на полукольцо, используемое в весовом случае, а также на общее свойство структуры преобразователя (свойство близнецов).
• Толкание веса для утяжеленного случая. ^[10]
• Минимизация для взвешенного случая. ^[11]
• Удаление эпсилон-переходов .

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

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

Приложения

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

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

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

Смотрите также

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

Примечания

1. Джурафски, Дэниел (2009). Обработка речи и языка . Пирсон. ISBN 9789332518414.
2. Коскенниеми 1983
3. Берстель, Жан; Ройтенауэр, Кристоф (2011). Некоммутативные рациональные ряды с приложениями . Энциклопедия математики и ее приложений. Т. 137. Кембридж: Cambridge University Press . С. 16. ISBN 978-0-521-19022-0. Збл  1250.68007.
4. Лотер, М. (2005). Прикладная комбинаторика к словам. Энциклопедия математики и ее приложений. Том. 105. Коллективная работа Жана Берстеля, Доминика Перрена, Максима Крошмора, Эрика Лапорта, Мехрияра Мори, Нади Пизанти, Мари-Франс Саго, Жезины Рейнерт , Софи Шбат , Михаэля Уотермана, Филиппа Жаке, Войцеха Шпанковского , Доминика Пулалона, Жиля Шеффера, Роман Колпаков, Григорий Кучеров, Жан-Поль Аллуш и Валери Берте . Кембридж: Издательство Кембриджского университета . п. 211. ИСБН 0-521-84802-4. Збл  1133.68067.
5. Boigelot, Bernard; Legay, Axel; Wolper, Pierre (2003). "Итерационные преобразователи в большом". Computer Aided Verification . Lecture Notes in Computer Science. Vol. 2725. Springer Berlin Heidelberg. pp. 223–235. doi :10.1007/978-3-540-45069-6_24. eISSN  1611-3349. ISBN 978-3-540-40524-5. ISSN  0302-9743.
6. Мохри 2004, стр. 3–5
7. «Определение преобразователей».
8. Мохри 2004, стр. 5–6
9. Аллаузен и Мохри 2003
10. Мохри 2004, стр. 7–9
11. Мохри 2004, стр. 9–11
12. Гриффитс 1968
13. Чарльз Н. Фишер; Рон К. Сайтрон; Ричард Дж. Леблан, младший (2010). «Сканирование — теория и практика». Создание компилятора . Addison-Wesley. ISBN 978-0-13-606705-4.
14. "Regular Models of Phonological Rule Systems" (PDF) . Архивировано из оригинала (PDF) 11 октября 2010 г. . Получено 25 августа 2012 г. .
15. Кевин Найт; Джонатан Мэй (2009). «Применение взвешенных автоматов в обработке естественного языка». В Manfred Droste; Werner Kuich; Heiko Vogler (ред.). Справочник по взвешенным автоматам . Springer Science & Business Media. ISBN 978-3-642-01492-5.
16. "Обучение с весовыми преобразователями" (PDF) . Получено 29 апреля 2017 г.
17. OpenGrm

Ссылки

• Аллаузен, Сирил; Мохри, Мехриар (2003). «Эффективные алгоритмы для проверки свойства близнецов» (PDF) . Журнал автоматики, языков и комбинаторики . 8 (2): 117–144.
• Коскенниеми, Киммо (1983), Двухуровневая морфология: общая вычислительная модель распознавания и производства словоформ (PDF) , Кафедра общей лингвистики, Хельсинкский университет , заархивировано из оригинала (PDF) 21.12.2018 , извлечено 10.01.2010
• Mohri, Mehryar (2004). "Взвешенные конечно-статистические алгоритмы преобразователя. Обзор" (PDF) . Формальные языки и приложения . Исследования по нечеткости и мягким вычислениям. Том 148. стр. 551–564. doi :10.1007/978-3-540-39886-8_29. ISBN 978-3-642-53554-3.
• Гриффитс, ТВ (1968). «Неразрешимость проблемы эквивалентности для Λ-свободных недетерминированных обобщенных машин». Журнал ACM . 15 (3). ACM: 409–413. doi :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). Обработка речи и языка . Prentice Hall. стр. 71–83. ISBN 0-13-095069-6.
• Корнаи, Андраш (1999). Расширенные модели языка с конечным состоянием . Издательство Кембриджского университета. ISBN 0-521-63198-X.
• Рош, Эммануэль; Ив Шабес (1997). Обработка конечного языка . МТИ Пресс. стр. 1–65. ISBN 0-262-18182-7.
• Бисли, Кеннет Р.; Лаури Карттунен (2003). Морфология конечных состояний . Центр изучения языка и информации. ISBN 1-57586-434-7.
• Роарк, Брайан; Ричард Спроут (2007). Вычислительные подходы к морфологии и синтаксису . Oxford University Press. ISBN 978-0-19-927478-9.
• Берстель, Жан (1979). Трансдукции и контекстно-свободные языки . Тойбнер Верлаг.. Бесплатная версия PDF