Конечный преобразователь - 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 )
-
- Состав . Для данного преобразователя T на алфавитах Σ и Γ и преобразователя S на алфавитах Γ и Δ существует такой преобразователь на Σ и Δ, что тогда и только тогда, когда существует такая строка , что и . Эта операция распространяется на взвешенный случай.
- В этом определении используются те же обозначения, которые используются в математике для композиции отношений . Однако обычное прочтение композиции отношений - это наоборот: при двух отношениях T и S , когда существует некоторый y такой, что и
- Проекция на автомат. Есть две функции проецирования: сохраняет входную ленту и сохраняет выходную ленту. Первая проекция определяется следующим образом:
- Для преобразователя T существует такой конечный автомат , который принимает x тогда и только тогда, когда существует строка y, для которой
- Вторая проекция определяется аналогично.
- Детерминированность . Учитывая преобразователь T , мы хотим создать эквивалентный преобразователь, который имеет уникальное начальное состояние и такой, что никакие два перехода, выходящие из любого состояния, не имеют одинаковой входной метки. Конструкция powerset может быть расширена до преобразователей или даже преобразователей с весом, но иногда не удается остановиться; действительно, некоторые недетерминированные преобразователи не допускают эквивалентных детерминированных преобразователей. Были предложены характеристики детерминируемых преобразователей, а также эффективные алгоритмы их тестирования: они полагаются на полукольцо, используемое во взвешенном случае, а также на общее свойство структуры преобразователя ( свойство близнецов ).
- Весовой толчок для утяжеленного ящика.
- Минимизация для взвешенного случая.
- Удаление эпсилон-переходов .
Дополнительные свойства конечных преобразователей
- Решаемо , является ли отношение [ T ] преобразователя T пустым.
- Разрешаемо, существует ли строка y такая, что x [ T ] y для данной строки x .
- Это неразрешимое ли два преобразователя эквивалентны. Однако эквивалентность разрешима в частном случае, когда отношение [ T ] преобразователя T является (частичной) функцией.
- Если определить алфавит меток , преобразователи с конечным числом состояний изоморфны NDFA по алфавиту и, следовательно, могут быть детерминированы (превращены в детерминированные конечные автоматы по алфавиту ) и впоследствии минимизированы так, чтобы они имели минимальное количество состояний.
Приложения
Контекстно-зависимые правила перезаписи формы a → b / c _ d , используемые в лингвистике для моделирования фонологических правил и изменения звука , в вычислительном отношении эквивалентны преобразователям с конечным числом состояний, при условии, что приложение нерекурсивно, т.е. одна и та же подстрока дважды.
Взвешенные FST нашли применение в обработке естественного языка , включая машинный перевод , и в машинном обучении . Реализацию тегирования части речи можно найти как один из компонентов библиотеки OpenGrm.
Смотрите также
- Мучная машина
- Машина Мура
- Морфологический словарь
- foma (программное обеспечение)
- Преобразователь дерева
Примечания
использованная литература
- Аллаузен, Кирилл; Мохри, Мехриар (2003). «Эффективные алгоритмы проверки свойства близнецов» (PDF) . Журнал автоматов, языков и комбинаторики . 8 (2): 117–144.
- Коскенниеми, Киммо (1983), Двухуровневая морфология: общая вычислительная модель распознавания и производства словоформ (PDF) , Департамент общего языкознания, Хельсинкский университет
- Мохри, Мехриар (2004). «Взвешенные алгоритмы преобразователя с конечным числом состояний: обзор» (PDF) . Формальные языки и приложения . Исследования в области нечеткости и мягких вычислений. 148 (620): 551–564. DOI : 10.1007 / 978-3-540-39886-8_29 . ISBN 978-3-642-53554-3.
-
Гриффитс, ТВ (1968). «Неразрешимость проблемы эквивалентности для Λ-свободных недетерминированных обобщенных машин». 15 (3). ACM: 409–413. Цитировать журнал требует
|journal=
( помощь )
внешние ссылки
- 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.
дальнейшее чтение
- Джурафски, Даниэль ; Джеймс Х. Мартин (2000). Обработка речи и языка . Прентис Холл. стр. 71 -83. ISBN 0-13-095069-6.
- Корнаи, Андрас (1999). Расширенные модели языка с конечным числом состояний . Издательство Кембриджского университета. ISBN 0-521-63198-X.
- Рош, Эммануэль; Ив Шабес (1997). Обработка конечного языка . MIT Press. стр. 1 -65. ISBN 0-262-18182-7.
- Beesley, Kenneth R .; Лаури Карттунен (2003). Конечная морфология состояния . Центр изучения языка и информации. ISBN 1-57586-434-7.
- Рорк, Брайан; Ричард Спроут (2007). Вычислительные подходы к морфологии и синтаксису . Издательство Оксфордского университета. ISBN 978-0-19-927478-9.
- Берстель, Жан (1979). Переводы и контекстно-свободные языки . Teubner Verlag.. Бесплатная версия PDF