stringtranslate.com

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

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

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

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

Обзор

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

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

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

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

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

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

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

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

Определим расширенное отношение перехода как наименьшее множество, такое что:

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

Поведение преобразователя T — это рациональное отношение [ T ], определяемое следующим образом: тогда и только тогда, когда существует и такое, что . Это означает, что T преобразует строку в строку , если существует путь из начального состояния в конечное состояние, входная метка которого — x , а выходная метка — y .

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

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

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

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

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

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

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

и не выполняется, если это не предписано ( k1 ) или ( k2 ).
Это определение использует ту же нотацию, которая используется в математике для композиции отношений . Однако общепринятое прочтение композиции отношений — наоборот: даны два отношения T и S , когда существуют некоторые y, такие что и
Для данного преобразователя T существует конечный автомат , который принимает x тогда и только тогда, когда существует строка y, для которой
Вторая проекция определяется аналогично.

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

Приложения

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

Контекстно-зависимые правила перезаписи вида ab / 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

Ссылки

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

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