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

Диаграмма Хассе некоторых классов количественных автоматов, упорядоченных по выразительности.

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

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

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

Взвешенные автоматы применяются в обработке естественного языка , где они используются для присвоения весов словам и предложениям. а также в сжатии изображений . Впервые они были представлены Марселем-Полем Шютценбергером в его статье 1961 года «Об определении семейства автоматов». С момента их появления было предложено множество расширений, например вложенные взвешенные автоматы, автоматы учета затрат, и взвешенные преобразователи с конечным состоянием . Исследователи изучили взвешенные автоматы с точки зрения изучения машины по ее поведению ввода-вывода. (см. теорию вычислительного обучения ) и изучение вопросов разрешимости .

Определение

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

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

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

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

и

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

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

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

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

Вариации

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

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

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

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

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

См. также

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