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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$\delta \subseteq \delta ^{*}$ ;
$(q,\epsilon ,\epsilon ,q)\in \delta ^{*}$ для всех $q\in Q$ ; и
в любое время $(q,x,y,r)\in \delta ^{*}$ и $(r,a,b,s)\in \delta$ затем $(q,xa,yb,s)\in \delta ^{*}$ .

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

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

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

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

$Q, Σ, Γ, I, F$ определены, как указано выше;
$E\subseteq Q\times (\Sigma \cup \{\epsilon \})\times (\Gamma \cup \{\epsilon \})\times Q\times K$ (где ε — пустая строка ) — конечное множество переходов;
$\lambda :I\rightarrow K$ отображает начальные состояния на веса;
$\rho :F\rightarrow K$ отображает конечные состояния на веса.

Чтобы четко определить некоторые операции над WFST, удобно потребовать, чтобы набор весов образовывал полукольцо . ^[3] Двумя типичными полукольцами, используемыми на практике, являются лог-полукольцо и тропическое полукольцо : недетерминированные автоматы можно рассматривать как имеющие веса в булевом полукольце . ^[4]

Стохастическое FST [ править ]

Стохастические FST (также известные как вероятностные FST или статистические FST), предположительно, являются формой взвешенного FST. ^{[ нужна цитата ]}

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

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

Союз . Для данных преобразователей $T$ и $S$ существует преобразователь $T\cup S$ такой, что $x[T\cup S]y$ если и только если $x[T]y$ или $x[S]y$ .
Конкатенация . Для данных преобразователей $T$ и $S$ существует преобразователь $T\cdot S$ такой, что $x[T\cdot S]y$ тогда и только тогда, когда существуют $x_{1},x_{2},y_{1},y_{2}$ с $x=x_{1}x_{2},y=y_{1}y_{2},x_{1}[T]y_{1}$ и $x_{2}[S]y_{2}.$
Закрытие Клини . Учитывая преобразователь $T$ , может существовать преобразователь $T^{*}$ со следующими свойствами: ^[5]

\epsilon [T^{*}]\epsilon

;

( к1 )

если

w[T^{*}]y

и

x[T]z

, затем

wx[T^{*}]yz

;

( к2 )

и

x[T^{*}]y

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

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

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

T

и

S

,

(x,z)\in T\circ S

когда существуют такие

y

, что

(x,y)\in S

и

(y,z)\in T.

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

Для преобразователя

T

существует конечный автомат

\pi _{1}T

такой, что

\pi _{1}T

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

x[T]y.

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

\pi _{2}

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

Определенность . Учитывая преобразователь $T$ , мы хотим построить эквивалентный преобразователь, который имеет уникальное начальное состояние и такой, чтобы никакие два перехода, выходящие из любого состояния, не имели одну и ту же входную метку. Конструкция силового набора может быть распространена на датчики или даже на взвешенные датчики, но иногда не может остановиться; действительно, некоторые недетерминированные преобразователи не допускают эквивалентных детерминированных преобразователей. ^[7] характеристики детерминируемых преобразователей. Предложены ^[8] вместе с эффективными алгоритмами для их тестирования: ^[9] они основаны на полукольце, используемом в случае взвешивания, а также на общем свойстве конструкции преобразователя ( свойстве двойников ).
Увеличение веса для утяжеленного корпуса. ^[10]
Минимизация для взвешенного случая. ^[11]
Удаление эпсилон-переходов .

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

Можно решить , является ли отношение [ T ] преобразователя T пустым.
Можно решить, существует ли строка y такая, что x [ T ] y для данной строки x .
Неизвестно , эквивалентны ли два преобразователя. ^[12] Однако эквивалентность разрешима в частном случае, когда отношение [ T ] преобразователя T является (частичной) функцией.
Если определить алфавит меток $L=(\Sigma \cup \{\epsilon \})\times (\Gamma \cup \{\epsilon \})$ , преобразователи с конечным состоянием изоморфны NDFA по алфавиту $L$ , и поэтому может быть детерминирован (превращен в детерминированные конечные автоматы над алфавитом $L=[(\Sigma \cup \{\epsilon \})\times \Gamma ]\cup [\Sigma \times (\Gamma \cup \{\epsilon \})]$ ) и впоследствии минимизируются так, чтобы они имели минимальное количество состояний. ^{[ нужна цитата ]}

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

FST используются лексического анализа на этапе компиляторами для связывания семантического значения с обнаруженными токенами. ^[13]

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

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

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

Примечания [ править ]

^ Юрафский, Дэниел (2009). Речевая и языковая обработка . Пирсон. ISBN 9789332518414 .
^ Коскенниеми 1983 г.
^ Берстель, Жан; Ройтенауэр, Кристоф (2011). Некоммутативные рациональные ряды с приложениями . Энциклопедия математики и ее приложений. Том. 137. Кембридж: Издательство Кембриджского университета . п. 16. ISBN 978-0-521-19022-0 . Збл 1250.68007 .
^ Лотер, М. (2005). Прикладная комбинаторика к словам . Энциклопедия математики и ее приложений. Том. 105. Коллективная работа Жана Берстеля, Доминика Перрена, Максима Крошмора, Эрика Лапорта, Мехрияра Мори, Нади Пизанти, Мари-Франс Саго, Жезины Рейнерт , Софи Шбат , Михаэля Уотермана, Филиппа Жаке, Войцеха Шпанковского , Доминика Пулалона, Жиля Шеффера, Роман Колпаков, Григорий Кучеров, Жан-Поль Аллуш и Валери Берте . Кембридж: Издательство Кембриджского университета . п. 211 . ISBN 0-521-84802-4 . Збл 1133.68067 .
^ Буажело, Бернар; Легай, Аксель; Вулпер, Пьер (2003). «Итерационные преобразователи в целом». Компьютерная проверка . Конспекты лекций по информатике. Том. 2725. Шпрингер Берлин Гейдельберг. стр. 223–235. дои : 10.1007/978-3-540-45069-6_24 . eISSN 1611-3349 . ISBN 978-3-540-40524-5 . ISSN 0302-9743 .
^ Мори 2004 , с. 3–5
^ «Определение преобразователей» .
^ Мори 2004 , с. 5–6
^ Аллаузен и Мори, 2003 г.
^ Мори 2004 , с. 7–9
^ Мори 2004 , с. 9–11
^ Гриффитс 1968
^ Чарльз Н. Фишер; Рон К. Сайтрон; Ричард Дж. ЛеБлан-младший (2010). «Сканирование – теория и практика». Создание компилятора . Аддисон-Уэсли. ISBN 978-0-13-606705-4 .
^ «Регулярные модели систем фонологических правил» (PDF) . Архивировано из оригинала (PDF) 11 октября 2010 г. Проверено 25 августа 2012 г.
^ Кевин Найт; Джонатан Мэй (2009). «Применение взвешенных автоматов в обработке естественного языка». В Манфреде Дросте; Вернер Куич; Хайко Фоглер (ред.). Справочник по взвешенным автоматам . Springer Science & Business Media. ISBN 978-3-642-01492-5 .
^ «Обучение с помощью взвешенных датчиков» (PDF) . Проверено 29 апреля 2017 г.
^ ОпенГрм

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

Аллаузен, Кирилл; Мори, Мехриар (2003). «Эффективные алгоритмы проверки свойства близнецов» (PDF) . Журнал автоматов, языков и комбинаторики . 8 (2): 117–144.
Коскенниеми, Киммо (1983), Двухуровневая морфология: общая вычислительная модель распознавания и производства словоформ (PDF) , Департамент общей лингвистики, Хельсинкский университет , заархивировано из оригинала (PDF) 21 декабря 2018 г. , получено 10 января 2010 г.
Мори, Мехриар (2004). «Алгоритмы взвешенных преобразователей конечных состояний. Обзор» (PDF) . Формальные языки и приложения . Исследования нечеткости и мягких вычислений. Том. 148. стр. 551–564. дои : 10.1007/978-3-540-39886-8_29 . ISBN 978-3-642-53554-3 .
Гриффитс, ТВ (1968). «Неразрешимость проблемы эквивалентности для Λ-свободных недетерминированных обобщенных машин». Журнал АКМ . 15 (3). АКМ: 409–413. дои : 10.1145/321466.321473 .

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

OpenFst — библиотека с открытым исходным кодом для операций FST.
Морфология конечных состояний — книга , заархивированная 25 марта 2022 г. в Wayback Machine XFST/LEXC, описание реализации Xerox преобразователей с конечным состоянием, предназначенных для лингвистических приложений.
Хельсинкская реализация с открытым исходным кодом и расширение Xerox fst.
FOMA — реализация с открытым исходным кодом большинства возможностей реализации Xerox XFST/LEXC.
Stuttgart Finite State Transducer Tools , еще один набор инструментов FST с открытым исходным кодом.
Java FST Framework — Java FST Framework с открытым исходным кодом, способная обрабатывать текстовый формат OpenFst.
Vcsn. Архивировано 23 июня 2020 г. на Wayback Machine , платформе с открытым исходным кодом (C++ и IPython) для взвешенных автоматов и рациональных выражений.

Дальнейшее чтение [ править ]

Юрафски, Дэниел ; Джеймс Х. Мартин (2000). Речевая и языковая обработка . Прентис Холл. стр. 71–83 . ISBN 0-13-095069-6 .
Корнаи, Андраш (1999). Расширенные модели языка с конечным состоянием . Издательство Кембриджского университета. ISBN 0-521-63198-Х .
Рош, Эммануэль; Ив Шабес (1997). Обработка конечного языка . МТИ Пресс. стр. 1 –65. ISBN 0-262-18182-7 .
Бисли, Кеннет Р.; Лаури Карттунен (2003). Морфология конечного состояния . Центр изучения языка и информации. ISBN 1-57586-434-7 .
Рорк, Брайан; Ричард Спроат (2007). Вычислительные подходы к морфологии и синтаксису . Издательство Оксфордского университета. ISBN 978-0-19-927478-9 .
Берстель, Жан (1979). Трансдукции и контекстно-свободные языки . Тойбнер Верлаг. . Бесплатная PDF-версия

[1] Юрафский, Дэниел (2009). Речевая и языковая обработка . Пирсон. ISBN 9789332518414 .

[2] Коскенниеми 1983 г.

[BR16-3] Берстель, Жан; Ройтенауэр, Кристоф (2011). Некоммутативные рациональные ряды с приложениями . Энциклопедия математики и ее приложений. Том. 137. Кембридж: Издательство Кембриджского университета . п. 16. ISBN 978-0-521-19022-0 . Збл 1250.68007 .

[Lot211-4] Лотер, М. (2005). Прикладная комбинаторика к словам . Энциклопедия математики и ее приложений. Том. 105. Коллективная работа Жана Берстеля, Доминика Перрена, Максима Крошмора, Эрика Лапорта, Мехрияра Мори, Нади Пизанти, Мари-Франс Саго, Жезины Рейнерт , Софи Шбат , Михаэля Уотермана, Филиппа Жаке, Войцеха Шпанковского , Доминика Пулалона, Жиля Шеффера, Роман Колпаков, Григорий Кучеров, Жан-Поль Аллуш и Валери Берте . Кембридж: Издательство Кембриджского университета . п. 211 . ISBN 0-521-84802-4 . Збл 1133.68067 .

[BoigelotLegayWolper2003-5] Буажело, Бернар; Легай, Аксель; Вулпер, Пьер (2003). «Итерационные преобразователи в целом». Компьютерная проверка . Конспекты лекций по информатике. Том. 2725. Шпрингер Берлин Гейдельберг. стр. 223–235. дои : 10.1007/978-3-540-45069-6_24 . eISSN 1611-3349 . ISBN 978-3-540-40524-5 . ISSN 0302-9743 .

[6] Мори 2004 , с. 3–5

[7] «Определение преобразователей» .

[8] Мори 2004 , с. 5–6

[9] Аллаузен и Мори, 2003 г.

[10] Мори 2004 , с. 7–9

[11] Мори 2004 , с. 9–11

[12] Гриффитс 1968

[13] Чарльз Н. Фишер; Рон К. Сайтрон; Ричард Дж. ЛеБлан-младший (2010). «Сканирование – теория и практика». Создание компилятора . Аддисон-Уэсли. ISBN 978-0-13-606705-4 .

[14] «Регулярные модели систем фонологических правил» (PDF) . Архивировано из оригинала (PDF) 11 октября 2010 г. Проверено 25 августа 2012 г.

[DrosteKuich2009-15] Кевин Найт; Джонатан Мэй (2009). «Применение взвешенных автоматов в обработке естественного языка». В Манфреде Дросте; Вернер Куич; Хайко Фоглер (ред.). Справочник по взвешенным автоматам . Springer Science & Business Media. ISBN 978-3-642-01492-5 .

[16] «Обучение с помощью взвешенных датчиков» (PDF) . Проверено 29 апреля 2017 г.

[17] ОпенГрм

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]