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

Эта статья поднимает множество проблем. Пожалуйста, помогите улучшить его или обсудите эти проблемы на странице обсуждения . ( Узнайте, как и когда удалить эти сообщения-шаблоны ) Эта статья включает в себя список общих ссылок , но он остается в значительной степени непроверенным, поскольку в нем отсутствует достаточное количество соответствующих встроенных ссылок . Пожалуйста, помогите улучшить эту статью, добавив более точные цитаты. ( Август 2014 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения ) У этой статьи нечеткий стиль цитирования . Используемые ссылки можно сделать более ясными с помощью другого или последовательного стиля цитирования и сносок . ( Август 2014 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения ) ( Узнайте, как и когда удалить этот шаблон сообщения )

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

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

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

Обзор [ править ]

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

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

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

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

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

Формальная конструкция [ править ]

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

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

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

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

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

• ${\ displaystyle \ delta \ substeq \ delta ^ {*}}$;
• ${\ displaystyle (q, \ epsilon, \ epsilon, q) \ in \ delta ^ {*}}$для всех ; а также${\ displaystyle q \ in Q}$
• всякий раз, когда и тогда .${\ Displaystyle (д, х, у, г) \ в \ дельта ^ {*}}$${\ displaystyle (r, a, b, s) \ in \ delta}$${\ displaystyle (q, xa, yb, s) \ in \ delta ^ {*}}$

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

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

Взвешенные автоматы [ править ]

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

• Q , Σ, Γ, I , F определены выше;
• ${\ displaystyle E \ substeq 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 существует преобразователь со следующими свойствами:${\displaystyle T^{*}}$

${\displaystyle \epsilon [T^{*}]\epsilon }$;

( k1 )

если и , то ;${\displaystyle w[T^{*}]y}$${\displaystyle x[T]z}$${\displaystyle wx[T^{*}]yz}$

( k2 )

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

• Состав . Для данного преобразователя T на алфавитах Σ и Γ и преобразователя S на алфавитах Γ и Δ существует такой преобразователь на Σ и Δ, что тогда и только тогда, когда существует такая строка , что и . Эта операция распространяется на взвешенный случай. ^[5]${\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 может быть расширена до преобразователей или даже преобразователей с весом, но иногда не удается остановиться; действительно, некоторые недетерминированные преобразователи не допускают эквивалентных детерминированных преобразователей. ^[6] Были предложены характеристики детерминируемых преобразователей ^[7] вместе с эффективными алгоритмами их тестирования: ^[8] они основаны на полукольце, используемом во взвешенном случае, а также на общем свойстве структуры преобразователя (близнецы собственности ).
• Весовой толчок для утяжеленного ящика. ^[9]
• Минимизация для взвешенного случая. ^[10]
• Удаление эпсилон-переходов .

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

• Решаемо , является ли отношение [ T ] преобразователя T пустым.
• Разрешаемо, существует ли строка y такая, что x [ T ] y для данной строки x .
• Это неразрешимое ли два преобразователя эквивалентны. ^{[11] Однако} эквивалентность разрешима в частном случае, когда отношение [ 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 \})]}$

Приложения [ править ]

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

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

См. Также [ править ]

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

Заметки [ править ]

Ссылки [ править ]

Внешние ссылки [ править ]

• 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.
• Бисли, Кеннет Р .; Лаури Карттунен (2003). Конечная морфология состояния . Центр изучения языка и информации. ISBN 1-57586-434-7.
• Рорк, Брайан; Ричард Спроут (2007). Вычислительные подходы к морфологии и синтаксису . Издательство Оксфордского университета. ISBN 0-19-927478-9.
• Берстель, Жан (1979). Переводы и контекстно-свободные языки . Teubner Verlag.. Бесплатная версия PDF