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

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

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

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

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

Обзор

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

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

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

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

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

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

Формально конечный преобразователь Т представляет собой набор из шести (Q, Σ, Γ, я, F, δ) такой, что:

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

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

ПРИМЕЧАНИЕ. Это определение конечного преобразователя также называется преобразователь букв (Рош и Шабес, 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 ^ {*}}$ известны как пути. Метки краев пути получаются путем соединения краевых меток составляющих его переходов по порядку.

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

Весовые автоматы

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

• Q, Σ, Γ, я, 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.^{[нужна цитата ]}

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

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

• Союз. Данные преобразователи Т и S, существует преобразователь ${ displaystyle T cup S}$ такой, что ${ Displaystyle х [Т чашка S] у}$ если и только если ${ Displaystyle х [Т] у}$ или же ${ displaystyle x [S] y}$.
• Конкатенация. Данные преобразователи Т и S, существует преобразователь ${ displaystyle T cdot S}$ такой, что ${ Displaystyle х [Т 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}.}$
• Клини закрытие. Учитывая преобразователь Т, существует преобразователь ${ displaystyle T ^ {*}}$ со следующими свойствами:

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

(k1)

если ${ Displaystyle ш [Т ^ {*}] у}$ и ${ displaystyle x [T] z}$, тогда ${ displaystyle wx [T ^ {*}] yz}$;

(k2)

и ${ displaystyle x [T ^ {*}] y}$ не имеет силы, если это не предписано (k1) или же (k2).

• Сочинение. Учитывая преобразователь Т на алфавитах Σ и Γ и преобразователь S на алфавитах Γ и Δ существует преобразователь ${ displaystyle T circ S}$ на Σ и Δ такие, что ${ Displaystyle х [T circ S] z}$ тогда и только тогда, когда существует строка ${ displaystyle y in Gamma ^ {*}}$ такой, что ${ Displaystyle х [Т] у}$ и ${ displaystyle y [S] z}$. Эта операция распространяется на взвешенный случай.^[5]

В этом определении используются те же обозначения, которые используются в математике для состав отношений. Однако общепринятое понимание композиции отношений - это наоборот: при наличии двух отношений Т и S, ${ 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}}$ определяется следующим образом:

Учитывая преобразователь Тсуществует конечный автомат ${ displaystyle pi _ {1} T}$ такой, что ${ displaystyle pi _ {1} T}$ принимает Икс тогда и только тогда, когда существует строка у для которого ${ displaystyle x [T] y.}$

Вторая проекция, ${ displaystyle pi _ {2}}$ определяется аналогично.

• Детерминация. Учитывая преобразователь Т, мы хотим создать эквивалентный преобразователь с уникальным начальным состоянием, чтобы никакие два перехода, выходящие из любого состояния, не имели одинаковой метки ввода. В конструкция электростанции может быть расширен на преобразователи или даже преобразователи с весом, но иногда не останавливается; действительно, некоторые недетерминированные преобразователи не допускают эквивалентных детерминированных преобразователей.^[6] Характеристики детерминируемых преобразователей предложены^[7] наряду с эффективными алгоритмами их тестирования:^[8] они полагаются на полукольцо используется во взвешенном случае, а также в качестве общего свойства конструкции преобразователя ( собственность близнецов ).
• Весовой толчок для утяжеленного ящика.^[9]
• Минимизация для взвешенного случая.^[10]
• Удаление эпсилон-переходы.

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

• это разрешимый имеет ли отношение [Т] преобразователя Т пусто.
• Разрешаемо, существует ли строка у такой, что Икс[Т]у для данной строки Икс.
• это неразрешимый эквивалентны ли два преобразователя.^[11] Однако эквивалентность разрешима в частном случае, когда отношение [Т] преобразователя Т является (частичной) функцией.
• Если определить алфавит меток ${ Displaystyle L = ( Sigma чашка { epsilon }) раз ( Gamma cup { epsilon })}$, конечные преобразователи изоморфны NDFA по алфавиту ${ displaystyle L}$, и поэтому могут быть детерминированы (превращены в детерминированные конечные автоматы по алфавиту ${ Displaystyle L = [( Sigma cup { epsilon }) times Gamma] cup [ Sigma times ( Gamma cup { epsilon })]}$), а затем минимизированы так, чтобы они имели минимальное количество состояний.^{[нужна цитата ]}

Приложения

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

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

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

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

Примечания

Рекомендации

внешняя ссылка

• OpenFst, библиотека с открытым исходным кодом для операций FST.
• Инструменты для измерения конечных состояний Штутгарта, еще один набор инструментов 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  0-19-927478-9.
• Берстель, Жан (1979). Переводы и контекстно-свободные языки. Teubner Verlag.. Бесплатная версия PDF