Конечный автомат с двумя лентами (вход, выход)
Конечный автомат ( 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 , множества конечных состояний ; и
- (где ε — пустая строка ) — отношение перехода .
Мы можем рассматривать ( Q , δ ) как помеченный ориентированный граф , известный как граф переходов T : множество вершин равно Q , и это означает, что существует помеченное ребро, идущее от вершины q к вершине r . Мы также говорим, что a — это входная метка , а b — выходная метка этого ребра.
ПРИМЕЧАНИЕ: Это определение конечного преобразователя также называется буквенным преобразователем (Roche и Schabes, 1997); возможны альтернативные определения, но все они могут быть преобразованы в преобразователи, следующие этому.
Определим расширенное отношение перехода как наименьшее множество, такое что:
- ;
- для всех ; и
- когда бы то ни было и тогда .
Расширенное отношение перехода по сути является рефлексивным транзитивным замыканием графа перехода, которое было дополнено для учета меток ребер. Элементы известны как пути . Метки ребер пути получаются путем конкатенации меток ребер его составляющих переходов по порядку.
Поведение преобразователя T — это рациональное отношение [ T ], определяемое следующим образом: тогда и только тогда, когда существует и такое, что . Это означает, что T преобразует строку в строку , если существует путь из начального состояния в конечное состояние, входная метка которого — x , а выходная метка — y .
Взвешенные автоматы
Конечные преобразователи состояний могут быть взвешенными, где каждый переход помечен весом в дополнение к входным и выходным меткам. Взвешенный конечный преобразователь состояний (WFST) над набором K весов может быть определен аналогично невзвешенному как 8-кортеж T =( Q , Σ, Γ, I , F , E , λ , ρ ) , где:
- Q , Σ, Γ, I , F определены, как указано выше;
- (где ε — пустая строка ) — конечный набор переходов;
- отображает начальные состояния в веса;
- отображает конечные состояния в веса.
Для того чтобы сделать некоторые операции над WFST хорошо определенными, удобно потребовать, чтобы набор весов образовывал полукольцо . [3] Два типичных полукольца, используемых на практике, — это логарифмическое полукольцо и тропическое полукольцо : недетерминированные автоматы можно рассматривать как имеющие веса в булевом полукольце . [4]
Стохастический FST
Стохастические FST (также известные как вероятностные FST или статистические FST) предположительно являются формой взвешенных FST. [ необходима ссылка ]
Операции с конечными преобразователями
Следующие операции, определенные на конечных автоматах, применимы также к конечным преобразователям:
- Объединение . Для данных преобразователей T и S существует преобразователь такой, что тогда и только тогда, когда или .
- Конкатенация . При наличии преобразователей T и S существует преобразователь такой, что тогда и только тогда, когда существуют с и
- Замыкание Клини . При наличии преобразователя T может существовать преобразователь со следующими свойствами: [5]
- и не выполняется, если это не предписано ( k1 ) или ( k2 ).
- Композиция . Если задан преобразователь T на алфавитах Σ и Γ и преобразователь S на алфавитах Γ и Δ, то существует преобразователь на Σ и Δ такой, что тогда и только тогда, когда существует строка такая, что и . Эта операция распространяется на взвешенный случай. [6]
- Это определение использует ту же нотацию, которая используется в математике для композиции отношений . Однако общепринятое прочтение композиции отношений — наоборот: даны два отношения T и S , когда существуют некоторые y, такие что и
- Проекция на автомат. Есть две функции проекции: сохраняет входную ленту и сохраняет выходную ленту. Первая проекция определяется следующим образом:
- Для данного преобразователя T существует конечный автомат , который принимает x тогда и только тогда, когда существует строка y, для которой
- Вторая проекция определяется аналогично.
- Детерминизация . Имея преобразователь T , мы хотим построить эквивалентный преобразователь, который имеет уникальное начальное состояние и такой, что никакие два перехода, покидающие любое состояние, не имеют одну и ту же входную метку. Конструкция powerset может быть расширена до преобразователей или даже взвешенных преобразователей, но иногда не останавливается; действительно, некоторые недетерминированные преобразователи не допускают эквивалентных детерминированных преобразователей. [7] Были предложены характеристики детерминируемых преобразователей [8] вместе с эффективными алгоритмами для их проверки: [9] они опираются на полукольцо, используемое в взвешенном случае, а также на общее свойство структуры преобразователя (свойство близнецов).
- Толкание веса для утяжеленного случая. [10]
- Минимизация для взвешенного случая. [11]
- Удаление эпсилон-переходов .
Дополнительные свойства конечных преобразователей
- Можно решить , является ли отношение [ T ] преобразователя T пустым.
- Можно решить, существует ли строка y такая, что x [ T ] y для данной строки x .
- Невозможно решить , эквивалентны ли два преобразователя. [12] Однако эквивалентность разрешима в частном случае, когда отношение [ T ] преобразователя T является (частичной) функцией.
- Если определить алфавит меток , то конечные преобразователи изоморфны NDFA над алфавитом и, следовательно, могут быть детерминированы (превращены в детерминированные конечные автоматы над алфавитом ) и впоследствии минимизированы так, чтобы они имели минимальное количество состояний. [ требуется ссылка ]
Приложения
FST используются на этапе лексического анализа компиляторов для связывания семантического значения с обнаруженными токенами. [13]
Контекстно-зависимые правила перезаписи вида a → b / c _ d , используемые в лингвистике для моделирования фонологических правил и изменения звука , вычислительно эквивалентны конечным преобразователям, при условии, что применение нерекурсивно, т. е. правилу не разрешено переписывать одну и ту же подстроку дважды. [14]
Взвешенные FST нашли применение в обработке естественного языка , включая машинный перевод , и в машинном обучении . [15] [16] Реализацию для разметки частей речи можно найти в качестве одного из компонентов библиотеки OpenGrm [17] .
Смотрите также
Примечания
- ^ Джурафски, Дэниел (2009). Обработка речи и языка . Пирсон. ISBN 9789332518414.
- ^ Коскенниеми 1983
- ^ Берстель, Жан; Ройтенауэр, Кристоф (2011). Некоммутативные рациональные ряды с приложениями . Энциклопедия математики и ее приложений. Т. 137. Кембридж: Cambridge University Press . С. 16. ISBN 978-0-521-19022-0. Збл 1250.68007.
- ^ Лотер, М. (2005). Прикладная комбинаторика к словам. Энциклопедия математики и ее приложений. Том. 105. Коллективная работа Жана Берстеля, Доминика Перрена, Максима Крошмора, Эрика Лапорта, Мехрияра Мори, Нади Пизанти, Мари-Франс Саго, Жезины Рейнерт , Софи Шбат , Михаэля Уотермана, Филиппа Жаке, Войцеха Шпанковского , Доминика Пулалона, Жиля Шеффера, Роман Колпаков, Григорий Кучеров, Жан-Поль Аллуш и Валери Берте . Кембридж: Издательство Кембриджского университета . п. 211. ИСБН 0-521-84802-4. Збл 1133.68067.
- ^ 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.
- ^ Мохри 2004, стр. 3–5
- ^ «Определение преобразователей».
- ^ Мохри 2004, стр. 5–6
- ^ Аллаузен и Мохри 2003
- ^ Мохри 2004, стр. 7–9
- ^ Мохри 2004, стр. 9–11
- ^ Гриффитс 1968
- ^ Чарльз Н. Фишер; Рон К. Сайтрон; Ричард Дж. Леблан, младший (2010). «Сканирование — теория и практика». Создание компилятора . Addison-Wesley. ISBN 978-0-13-606705-4.
- ^ "Regular Models of Phonological Rule Systems" (PDF) . Архивировано из оригинала (PDF) 11 октября 2010 г. . Получено 25 августа 2012 г. .
- ^ Кевин Найт; Джонатан Мэй (2009). «Применение взвешенных автоматов в обработке естественного языка». В Manfred Droste; Werner Kuich; Heiko Vogler (ред.). Справочник по взвешенным автоматам . Springer Science & Business Media. ISBN 978-3-642-01492-5.
- ^ "Обучение с весовыми преобразователями" (PDF) . Получено 29 апреля 2017 г.
- ^ 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