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

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

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

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

Обзор

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

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

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

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

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

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

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

  • Q - конечное множество , множество состояний ;
  • Σ - конечное множество, называемое входным алфавитом ;
  • Γ - конечное множество, называемое выходным алфавитом ;
  • Я это подмножество из Q , множество начальных состояний ;
  • F - подмножество Q , множество конечных состояний ; а также
  • (где ε - пустая строка ) - отношение перехода .

Мы можем рассматривать ( Q , & delta ; ) в качестве меченого ориентированного графа , известного как графы переходов из T : множество вершин является Q , и означает , что существует меченое ребро , выходящее из вершины ц в вершину г . Мы также говорим, что a - это входная метка, а b - выходная метка этого ребра.

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

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

  • ;
  • для всех ; а также
  • всякий раз, когда и тогда .

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

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

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

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

  • Q , Σ, Γ, I , F определены выше;
  • (где ε - пустая строка ) - конечное множество переходов;
  • отображает начальные состояния в веса;
  • отображает конечные состояния в веса.

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

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

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

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

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

  • Союз . Для преобразователей T и S существует такой преобразователь , что если и только если или .
  • Конкатенация . Для преобразователей T и S существует такой преобразователь , что тогда и только тогда, когда существуют с и
  • Клини закрытие . Для преобразователя T существует преобразователь со следующими свойствами:
;

 

 

 

 

( k1 )

если и , то ;

 

 

 

 

( k2 )

и не выполняется, если это не требуется ( k1 ) или ( k2 ).
  • Состав . Для данного преобразователя T на алфавитах Σ и Γ и преобразователя S на алфавитах Γ и Δ существует такой преобразователь на Σ и Δ, что тогда и только тогда, когда существует такая строка , что и . Эта операция распространяется на взвешенный случай.
В этом определении используются те же обозначения, которые используются в математике для композиции отношений . Однако обычное прочтение композиции отношений - это наоборот: при двух отношениях T и S , когда существует некоторый y такой, что и
  • Проекция на автомат. Есть две функции проецирования: сохраняет входную ленту и сохраняет выходную ленту. Первая проекция определяется следующим образом:
Для преобразователя T существует такой конечный автомат , который принимает x тогда и только тогда, когда существует строка y, для которой
Вторая проекция определяется аналогично.
  • Детерминированность . Учитывая преобразователь T , мы хотим создать эквивалентный преобразователь, который имеет уникальное начальное состояние и такой, что никакие два перехода, выходящие из любого состояния, не имеют одинаковой входной метки. Конструкция powerset может быть расширена до преобразователей или даже преобразователей с весом, но иногда не удается остановиться; действительно, некоторые недетерминированные преобразователи не допускают эквивалентных детерминированных преобразователей. Были предложены характеристики детерминируемых преобразователей, а также эффективные алгоритмы их тестирования: они полагаются на полукольцо, используемое во взвешенном случае, а также на общее свойство структуры преобразователя ( свойство близнецов ).
  • Весовой толчок для утяжеленного ящика.
  • Минимизация для взвешенного случая.
  • Удаление эпсилон-переходов .

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

  • Решаемо , является ли отношение [ T ] преобразователя T пустым.
  • Разрешаемо, существует ли строка y такая, что x [ T ] y для данной строки x .
  • Это неразрешимое ли два преобразователя эквивалентны. Однако эквивалентность разрешима в частном случае, когда отношение [ T ] преобразователя T является (частичной) функцией.
  • Если определить алфавит меток , преобразователи с конечным числом состояний изоморфны NDFA по алфавиту и, следовательно, могут быть детерминированы (превращены в детерминированные конечные автоматы по алфавиту ) и впоследствии минимизированы так, чтобы они имели минимальное количество состояний.

Приложения

Контекстно-зависимые правила перезаписи формы ab / c _ d , используемые в лингвистике для моделирования фонологических правил и изменения звука , в вычислительном отношении эквивалентны преобразователям с конечным числом состояний, при условии, что приложение нерекурсивно, т.е. одна и та же подстрока дважды.

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

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

Примечания

использованная литература

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

  • OpenFst , библиотека с открытым исходным кодом для операций FST.
  • Stuttgart Finite State Transducer Tools , еще один набор инструментов FST с открытым исходным кодом
  • java FST Framework , java FST Framework с открытым исходным кодом, способная обрабатывать текстовый формат OpenFst.
  • Vcsn , платформа с открытым исходным кодом (C ++ и IPython) для взвешенных автоматов и рациональных выражений.
  • Конечная морфология состояния - Книга XFST / LEXC, описание реализации Xerox преобразователей с конечным числом состояний, предназначенных для лингвистических приложений.
  • FOMA , реализация с открытым исходным кодом большинства возможностей реализации Xerox XFST / LEXC.

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