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

Конечный автомат, где ребра несут вес

Диаграмма Хассе некоторых классов количественных автоматов, упорядоченных по выразительности. ^{[1] : Рис.1}

В теоретической информатике и теории формального языка взвешенный автомат или взвешенный конечный автомат — это обобщение конечного автомата, в котором ребра имеют веса , например, действительные числа или целые числа . Конечные автоматы способны только отвечать на проблемы принятия решений ; они принимают в качестве входных данных строку и выдают логический вывод, то есть либо «принять», либо «отклонить». Напротив, взвешенные автоматы выдают количественный вывод, например, подсчет того , сколько ответов возможно для данной входной строки, или вероятность того, насколько вероятна входная строка в соответствии с распределением вероятностей . ^[2] Они являются одной из простейших изученных моделей количественных автоматов. ^{[1] : Рис.1}

Определение взвешенного автомата обычно дается над произвольным полукольцом , абстрактным множеством с операцией сложения и операцией умножения . Автомат состоит из конечного множества состояний, конечного входного алфавита символов и ребер, которые помечены как символом в , так и весом в . Вес любого пути в автомате определяется как произведение весов вдоль пути, а вес строки является суммой весов всех путей, которые помечены этой строкой. Таким образом, взвешенный автомат определяет функцию от до . [ ^2] ${\displaystyle R}$ ${\displaystyle +}$ ${\displaystyle \times }$ ${\displaystyle \Sigma }$ ${\displaystyle \Sigma }$ ${\displaystyle R}$ ${\displaystyle \Sigma ^{*}}$ ${\displaystyle R}$

Взвешенные автоматы обобщают детерминированные конечные автоматы (DFA) и недетерминированные конечные автоматы (NFA), которые соответствуют взвешенным автоматам над булевым полукольцом , где сложение является логической дизъюнкцией , а умножение является логической конъюнкцией . В случае DFA существует только один принимающий путь для любой входной строки, поэтому дизъюнкция не применяется. Когда веса являются действительными числами, а исходящие веса для каждого состояния добавляются к единице, взвешенные автоматы можно считать вероятностной моделью и также известны как вероятностные автоматы . Эти машины определяют распределение вероятностей по всем строкам и связаны с другими вероятностными моделями, такими как марковские процессы принятия решений и марковские цепи .

Взвешенные автоматы применяются в обработке естественного языка , где они используются для назначения весов словам и предложениям, ^{[3] [2] : 571–596,} а также при сжатии изображений . ^{[2] : 453–480} Впервые они были представлены Марселем-Полем Шютценбергером в его статье 1961 года «Определение семейства автоматов». ^[4] С момента их появления было предложено много расширений, например, вложенные взвешенные автоматы, ^[5] автоматы регистра стоимости, ^[6] и взвешенные конечные преобразователи . ^[7] Исследователи изучали взвешенные автоматы с точки зрения обучения машины по ее поведению ввода-вывода ^[8] (см. вычислительную теорию обучения ) и изучения вопросов разрешимости . ^[9]

Определение

Коммутативное полукольцо (или КП ) — это множество R, снабженное двумя выделенными элементами и операциями сложения и умножения , и такое, что является коммутативным и ассоциативным с единицей , является коммутативным и ассоциативным с единицей , распределяется по , а 0 является поглощающим элементом для . ${\displaystyle 0\neq 1}$ ${\displaystyle \oplus }$ ${\displaystyle \otimes }$ ${\displaystyle \oplus }$ ${\displaystyle 0}$ ${\displaystyle \otimes }$ ${\displaystyle 1}$ ${\displaystyle \otimes }$ ${\displaystyle \oplus }$ ${\displaystyle \otimes }$

Взвешенный автомат ${\displaystyle R}$ — это кортеж , где: ${\displaystyle {\mathcal {A}}=(Q,\Sigma ,\Delta ,I,F)}$

• ${\displaystyle Q}$представляет собой конечный набор состояний.
• ${\displaystyle \Sigma }$— конечный алфавит.
• ${\displaystyle \Delta \subseteq Q\times \Sigma \times R\times Q}$представляет собой конечный набор переходов , где называется характером , а называется весом . ${\displaystyle (q,\sigma ,w,q')}$ ${\displaystyle \sigma }$ ${\displaystyle w}$
• ${\displaystyle I:Q\to R}$— начальная весовая функция.
• ${\displaystyle F:Q\to R}$является конечной весовой функцией.

Путь на входе — это конечный путь в графе, где конкатенация меток символов равна . Вес пути — это произведение ( ) весов вдоль пути, дополнительно умноженное на начальный и конечный веса . Вес слова — это сумма ( ) весов всех путей на входе (или 0, если нет принимающих путей). Таким образом, машина определяет функцию . ${\displaystyle w\in \Sigma ^{*}}$ ${\displaystyle w}$ ${\displaystyle q_{0},q_{1},\ldots ,q_{n}}$ ${\displaystyle \otimes }$ ${\displaystyle I(q_{0})\otimes I(q_{n})}$ ${\displaystyle w}$ ${\displaystyle \oplus }$ ${\displaystyle w}$ ${\displaystyle [\![{\mathcal {A}}]\!]:\Sigma ^{*}\to R}$

Неоднозначность и детерминизм

Поскольку — это набор переходов, взвешенные автоматы допускают множественные переходы (или пути) на одной входной строке. Поэтому взвешенный автомат можно считать аналогом недетерминированного конечного автомата (НКА). Как и в случае с НКА, рассматриваются ограничения взвешенных автоматов, соответствующие понятиям детерминированного конечного автомата и однозначного конечного автомата (детерминированные взвешенные автоматы и однозначные взвешенные автоматы соответственно). ${\displaystyle \Delta }$

Во-первых, предварительное определение: базовый НКА — это НКА, образованный путем удаления всех переходов с весом и последующего стирания всех весов на переходах , так что новый набор переходов лежит в . Начальные состояния и конечные состояния — это наборы состояний, такие что и , соответственно. ${\displaystyle {\mathcal {A}}}$ ${\displaystyle 0}$ ${\displaystyle \Delta }$ ${\displaystyle Q\times \Sigma \times Q}$ ${\displaystyle q}$ ${\displaystyle I(q)\neq 0}$ ${\displaystyle F(q)\neq 0}$

Взвешенный автомат является детерминированным, если базовый НКА является детерминированным, и однозначным, если базовый НКА является однозначным. Каждый детерминированный взвешенный автомат является однозначным.

Как в детерминированном, так и в однозначном случае всегда существует не более одного приемлемого пути, поэтому операция никогда не применяется и может быть исключена из определения. ${\displaystyle \oplus }$

Вариации

• Требование наличия нулевого элемента для иногда опускается; в этом случае машина определяет частичную функцию от до, а не полную функцию. ${\displaystyle \oplus }$ ${\displaystyle \Sigma ^{*}}$ ${\displaystyle R}$

• Можно расширить определение, чтобы разрешить эпсилон-переходы , где — пустая строка. В этом случае нужно потребовать, чтобы не было циклов эпсилон-переходов. Это не увеличивает выразительность взвешенных автоматов. ^{[2] [10]} Если эпсилон-переходы разрешены, начальные веса и конечные веса можно заменить начальными и конечными наборами состояний без потери выразительности. ${\displaystyle (q,\epsilon ,w,q')}$ ${\displaystyle \epsilon }$

• Некоторые авторы опускают начальные и конечные весовые функции и . ^[1] Вместо этого и заменяются набором начальных и конечных состояний. Если эпсилон-переходы отсутствуют, это технически снижает выразительность, поскольку заставляет зависеть только от числа состояний, которые являются как начальными, так и конечными. ${\displaystyle I}$ ${\displaystyle F}$ ${\displaystyle I}$ ${\displaystyle F}$ ${\displaystyle [\![{\mathcal {A}}]\!](\varepsilon )}$

• Функция перехода может быть задана как матрица с записями в для каждого , а не как набор переходов. Запись матрицы в является суммой всех переходов, помеченных . ^{[2] [11]} ${\displaystyle \Delta _{\sigma }\in R^{Q\times Q}}$ ${\displaystyle R}$ ${\displaystyle \sigma }$ ${\displaystyle (q,q')}$ ${\displaystyle (q,\sigma ,q')}$

• Некоторые авторы ограничиваются конкретными полукольцами, такими как или , особенно при изучении результатов разрешимости. ^{[1] [9] [4]} ${\displaystyle \mathbb {N} }$ ${\displaystyle \mathbb {Z} }$

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

• Вероятностный автомат
• Недетерминированный конечный автомат
• Конечный преобразователь
• Рациональный ряд
• Полукольцо
• Матричное кольцо
• Автомат с таймером
• Нечеткая логика
• цепь Маркова

Ссылки

1. Чаттерджи, Кришненду; Хензингер, Томас А.; Отоп, Ян (2016). «Количественные мониторные автоматы». В Rival, Xavier (ред.). Статический анализ . Конспект лекций по информатике. Том 9837. Берлин, Гейдельберг: Springer. С. 23–38. doi :10.1007/978-3-662-53413-7_2. ISBN 978-3-662-53413-7.
2. Дросте, Манфред; Куич, Вернер; Фоглер, Хайко, ред. (2009). Справочник по взвешенным автоматам. Монографии по теоретической информатике. Серия EATCS. ​​Bibcode :2009hwa..book.....D. doi :10.1007/978-3-642-01492-5. ISBN 978-3-642-01491-8. ISSN  1431-2654.гл.1-4, стр.3-26, 69-71, 122-126.
3. Чианг, Дэвид. "Взвешенные автоматы" (PDF) . Обработка естественного языка (CSE 40657/60657), заметки к курсу, осень 2019 г. Получено 09.11.2021 г.
4. Schützenberger, MP (1961-09-01). «Об определении семейства автоматов». Информация и управление . 4 (2): 245–270. doi :10.1016/S0019-9958(61)80020-X. ISSN  0019-9958.
5. Чаттерджи, Кришненду; Хензингер, Томас А.; Отоп, Ян (14.12.2017). «Вложенные взвешенные автоматы». ACM Transactions on Computational Logic . 18 (4): 31:1–31:44. arXiv : 1504.06117 . doi : 10.1145/3152769. ISSN  1529-3785. S2CID  15070803.
6. Алур, Раджив; Д'Антони, Лорис; Дешмукх, Джотирмой; Раготаман, Мукунд; Юань, Ифэй (2013). «Регулярные функции и автоматы регистрации затрат». 2013 28-й ежегодный симпозиум ACM/IEEE по логике в информатике. стр. 13–22. дои : 10.1109/LICS.2013.65. ISBN 978-1-4799-0413-6. S2CID  1286659.
7. Mohri, Mehryar; Pereira, Fernando; Riley, Michael (2002-01-01). «Взвешенные конечные преобразователи в распознавании речи». Computer Speech & Language . 16 (1): 69–88. doi :10.1006/csla.2001.0184. ISSN  0885-2308.
8. Balle, Borja; Mohri, Mehryar (2015). «Обучение взвешенных автоматов». В Maletti, Andreas (ред.). Algebraic Informatics . Lecture Notes in Computer Science. Vol. 9270. Cham: Springer International Publishing. pp. 1–21. doi :10.1007/978-3-319-23021-4_1. ISBN 978-3-319-23021-4.
9. Almagor, Shaull; Boker, Udi; Kupferman, Orna (2011). «Что разрешимо в взвешенных автоматах?». В Bultan, Tevfik; Hsiung, Pao-Ann (ред.). Автоматизированная технология проверки и анализа . Конспект лекций по информатике. Том 6996. Берлин, Гейдельберг: Springer. стр. 482–491. doi :10.1007/978-3-642-24372-1_37. ISBN 978-3-642-24372-1. S2CID  10159261.
10. Mohri, Mehryar (2009), Droste, Manfred; Kuich, Werner; Vogler, Heiko (ред.), "Weighted Automata Algorithms", Handbook of Weighted Automata , Monographs in Theoretical Computer Science. An EATCS Series, Berlin, Heidelberg: Springer, стр. 213–254, Bibcode :2009hwa..book..213M, doi :10.1007/978-3-642-01492-5_6, ISBN 978-3-642-01492-5, получено 2021-11-11
11. Дросте, Манфред; Гастин, Пол (2007-06-21). «Взвешенные автоматы и взвешенные логики». Теоретическая информатика . Автоматы, языки и программирование. 380 (1): 69–86. doi : 10.1016/j.tcs.2007.02.055 . ISSN  0304-3975.