Probabilistic automata with bounded ambiguity

Probabilistic automata of bounded ambiguity

Nathanaël Fijalkow,
Cristian Riveros, James Worrell

CNRS, LaBRI, and Alan Turing Institute, London, and University of Warwick

University of Warwick, March 13th, 2018

$$\mathbb{P}(\text{train train predict}) = 0.4 \cdot 0.6 \cdot 1\ +\ 0.6 \cdot 0.45 \cdot 1$$

A probabilistic automaton induces $\mathbb{P} : A^* \to [0,1]$

Goal: algorithmically determine the properties of $\mathbb{P}$

In this paper: emptiness problem $$\exists w \in A^*,\ \mathbb{P}(w) \ge \frac{1}{2}$$

Many models somehow embed:

HMM: Hidden Markov Models
PSR: Predictive State Representations
OOM: Observable Operator Models

Ambiguity

An automaton has ambiguity $f : \mathbb{N} \to \mathbb{N}$ if each word of length $n$ have at most $f(n)$ accepting runs.

Undecidability

This automaton computes the binary value function and is linearly ambiguous: undecidability follows for emptiness, universality, isolation with infinite ambiguity

Results

Emptiness:

in NEXPTIME and PSPACE-hard for finitely ambiguous
PSPACE-complete if the ambiguity is polynomially bounded in the number of states
in NP for $k$-ambiguous, for every constant $k$
in quasi-polynomial time $O(n^{\log(n)})$ for 2-ambiguous

Approximation of emptiness:

no polynomial time approximation for finitely ambiguous unless P = NP
polynomial time approximation for $k$-ambiguous, for every constant $k$

Stochastic path problem

value of the red path: $.4 \times .9 \times .9\ +\ .6 \times .1 \times .9 = .27$.

Input: a graph and a threshold $c$
Question: does there exist a path from $s$ to $t$ whose value is at least $c$?

Reduction

Given a $k$-ambiguous probabilistic automaton with $n$ states, we construct a graph with $O(n^k)$ vertices such that:

path $\implies$ $k$ accepting runs of some word,
$k$ accepting runs of a word $\implies$ path

TL;DR: emptiness of $k$-ambiguous reduces to $k$-stochastic path problem

(Convex) Pareto curves

Theorem: quasi-polynomial time algorithm returns a convex Pareto curve for the bi-stochastic path problem

Corollary: quasi-polynomial time algorithm for emptiness of 2-ambiguous probabilistic automata

Approximate Pareto curves

Theorem: polynomial time algorithm returns a convex $\varepsilon$-Pareto curve for the $k$-stochastic path problem

Corollary: polynomial time algorithm for approximation of the emptiness of $k$-ambiguous probabilistic automata