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

редактировать

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

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

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

Содержание

1 Обзор
2 Формальная конструкция
- 2.1 Взвешенные автоматы
- 2.2 Стохастический FST
3 Операции с конечными преобразователями
4 Дополнительные свойства конечных преобразователей
5 Приложения
6 См. Также
7 Примечания
8 Ссылки
9 Внешние ссылки
10 Дополнительная литература

Обзор

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

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

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

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

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

Формальная конструкция

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

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

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

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

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

$δ ⊆ δ ∗ {\ displaystyle \ дельта \ подстекция \ дельта ^ {*}}$ $\ delta \ substeq \ delta ^ *$ ;
$(q, ϵ, ϵ, q) ∈ δ ∗ {\ displaystyle (q, \ epsilon, \ epsilon, q) \ in \ delta ^ {*}}$ $(q, \ epsilon, \ epsilon, q) \ in \ delta ^ *$ для всех $q ∈ Q {\ displaystyle q \ in Q}$ $q \ in Q$ ; и
всякий раз, когда $(q, x, y, r) ∈ δ ∗ {\ displaystyle (q, x, y, r) \ in \ delta ^ {*}}$ $(q, x, y, r) \ in \ delta ^ *$ и $(r, a, b, s) ∈ δ {\ displaystyle (r, a, b, s) \ in \ delta}$ $(r, a, b, s) \ in \ delta$ , затем $(q, xa, yb, s) ∈ δ ∗ {\ displaystyle (q, xa, yb, s) \ in \ delta ^ {*}}$ $(q, xa, yb, s) \ in \ дельта ^ *$ .

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

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

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

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

Q, Σ, Γ, I, F определены, как указано выше;
$E ⊆ Q × (Σ ∪ {ϵ}) × (Γ ∪ {ϵ}) × Q × K {\ displaystyle E \ substeq Q \ times (\ Sigma \ cup \ {\ epsilon \}) \ times (\ Gamma \ cup \ {\ epsilon \}) \ times Q \ times K}$ $E \ substeq Q \ times (\ Sigma \ cup \ {\ эпсилон \}) \ раз (\ Гамма \ чашка \ {\ эпсилон \}) \ раз Q \ раз К$ (где ε - пустая строка ) - конечный набор переходов;
$λ: I → K {\ displaystyle \ lambda: I \ rightarrow K}$ $\ lambda: I \ rightarrow K$ отображает начальные состояния в веса;
$ρ: F → K {\ displaystyle \ rho: F \ rightarrow K}$ $\ rho: F \ rightarrow K$ сопоставляет конечные состояния с весами.

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

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

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

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

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

Union. Для преобразователей T и S существует преобразователь $T ∪ S {\ displaystyle T \ cup S}$ $T \ cup S$ такой, что $x [T ∪ S] y {\ displaystyle x [T \ cup S] y}$ $x [T \ cup S] y$ тогда и только тогда, когда $x [T] y {\ displaystyle x [T] y}$ $x [T] y$ или $x [S] y {\ displaystyle x [S] y}$ $x [S] y$ .
Конкатенация. Для преобразователей T и S существует преобразователь $T ⋅ S {\ displaystyle T \ cdot S}$ $T \ cdot S$ такой, что $x [T ⋅ S] y {\ displaystyle x [T \ cdot S] y}$ $x [T \ cdot S] y$ тогда и только тогда, когда существуют $x 1, x 2, y 1, y 2 {\ displaystyle x_ {1}, x_ {2}, y_ {1}, y_ { 2}}$ $x_1, x_2, y_1, y_2$ с $x = x 1 x 2, y = y 1 y 2, x 1 [T] y 1 {\ displaystyle x = x_ {1} x_ {2}, y = y_ {1} y_ {2}, x_ {1} [T] y_ {1}}$ $x = x_1x_2, y = y_1y_2, x_1 [T] y_1$ и $x 2 [S] y 2. {\ displaystyle x_ {2} [S] y_ {2}.}$ ${\ displaystyle x_ {2} [S] y_ {2}.}$
Замыкание Клини. Для преобразователя T существует преобразователь $T ∗ {\ displaystyle T ^ {*}}$ $T ^ {*}$ со следующими свойствами:

ϵ [T ∗] ϵ {\ displaystyle \ epsilon [T ^ {*}] \ epsilon}

\ эпсилон [T ^ *] \ эпсилон

;

(k1)

если

w [T ∗] y {\ displaystyle w [T ^ {*}] y}

w [T ^ *] y

x [T] z {\ displaystyle x [T] z}

x [T] z

, затем

wx [T ∗] yz {\ displaystyle wx [T ^ {*}] yz}

wx [T ^ *] yz

;

(k2)

x [T ∗] y {\ displaystyle x [T ^ {*}] y}

x [T ^ *] y

не выполняется, если это не предусмотрено (k1) или (k2).

Composition. Для преобразователя T на алфавитах Σ и Γ и преобразователя S на алфавитах Γ и Δ существует преобразователь $T ∘ S {\ displaystyle T \ circ S}$ $T \ circ S$ на Σ и Δ такой, что $x [T ∘ S] z {\ displaystyle x [T \ circ S] z}$ $x [T \ circ S] z$ тогда и только тогда, когда существует строка $y ∈ Γ ∗ {\ displaystyle y \ в \ Gamma ^ {*}}$ $y \ in \ Gamma ^ *$ так, что $x [T] y {\ displaystyle x [T] y}$ $x [T] y$ и $y [S] z {\ displaystyle y [S] z}$ $y [S] z$ . Эта операция распространяется на взвешенный случай.

В этом определении используется то же n Отношение, используемое в математике для композиции отношения. Однако обычное прочтение композиции отношений - наоборот: для двух отношений T и S

(x, z) ∈ T ∘ S {\ displaystyle (x, z) \ in T \ circ S}

(x, z) \ in T \ circ S

когда существует такой y, что

(x, y) ∈ S {\ displaystyle (x, y) \ in S}

(x, y) \ in S

(y, z) ∈ T. {\ displaystyle (y, z) \ in T.}

{\ displaystyle (y, z) \ in T.}

Проекция на автомат. Есть две функции проецирования: $π 1 {\ displaystyle \ pi _ {1}}$ $\ pi _ {1}$ сохраняет входную ленту, и $π 2 {\ displaystyle \ pi _ {2}}$ $\ pi _ {2}$ сохраняет выходную ленту. Первая проекция, $π 1 {\ displaystyle \ pi _ {1}}$ $\ pi _ {1}$ , определяется следующим образом:

Для преобразователя T существует конечный автомат

π 1 T { \ displaystyle \ pi _ {1} T}

\ pi_1 T

такой, что

π 1 T {\ displaystyle \ pi _ {1} T}

\ pi_1 T

принимает x тогда и только тогда, когда существует строка y, для которой

x [T] y. {\ displaystyle x [T] y.}

{\ displaystyle x [T] y.}

Вторая проекция,

π 2 {\ displaystyle \ pi _ {2}}

\ pi _ {2}

, определяется аналогично.

Детерминация. Учитывая преобразователь T, мы хотим создать эквивалентный преобразователь, который имеет уникальное начальное состояние и такой, чтобы никакие два перехода, выходящие из любого состояния, не имели одинаковой метки входа. Конструкцию powerset можно распространить на преобразователи или даже преобразователи с взвешиванием, но иногда не удается остановиться; действительно, некоторые недетерминированные преобразователи не допускают эквивалентных детерминированных преобразователей. Были предложены характеристики детерминируемых преобразователей вместе с эффективными алгоритмами для их проверки: они полагаются на полукольцо, используемое во взвешенных случай, а также общее свойство структуры преобразователя (the).
Давление веса для взвешенного случая.
Минимизация для взвешенного случая.
Удаление эпсилон-переходы.

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

разрешимо, является ли отношение [T] преобразователя T. пустым.
Разрешимо существует ли строка y такая, что x [T] y для данной строки x.
нерешаемо, эквивалентны ли два преобразователя. Однако эквивалентность разрешима в частном случае, когда отношение [T] преобразователя T является (частичной) функцией.
Если определить алфавит меток $L = (Σ ∪ {ϵ}) × (Γ ∪ {ϵ}) {\ displaystyle L = (\ Sigma \ cup \ {\ epsilon \}) \ times (\ Gamma \ cup \ {\ epsilon \})}$ $L = (\ Sigma \ cup \ {\ epsilon \}) \ times (\ Gamma \ cup \ {\ epsilon \})$ , с конечным состоянием преобразователи изоморфны NDFA по алфавиту $L {\ displaystyle L}$ $L$ , и поэтому могут быть детерминированы (превращены в детерминированные конечные автоматы по алфавиту $L = [(Σ ∪ {ϵ}) × Γ] ∪ [Σ × (Γ ∪ {ϵ})] {\ displaystyle L = [(\ Sigma \ cup \ {\ epsilon \}) \ times \ Gamma ] \ cup [\ Sigma \ times (\ Gamma \ cup \ {\ epsilon \})]}$ $L = [(\ Sigma \ cup \ {\ epsilon \}) \ times \ Гамма] \ cup [\ Sigma \ times (\ Gamma \ cup \ {\ epsilon \})]$ ), а затем свернуты так, чтобы они имели минимальное количество состояний.

Приложения

Контекстно-зависимые правила перезаписи формы a → b / 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.

Дополнительная литература

Джурафский, Даниэль ; Джеймс Х. Мартин (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