GitLocker: The Coding Marketplace

Description:

probabilisticautomata 0.4.2

Probabilistic Automata

Python library for manipulating Probabilistic Automata. This library
builds upon the dfa package.

Table of Contents

Probabilistic Automata
Installation
Usage

Dict <-> PDFA
DFA to PDFA
Composition

Installation
If you just need to use probabilistic_automata, you can just run:
$ pip install probabilistic_automata
For developers, note that this project uses the
poetry python package/dependency
management tool. Please familarize yourself with it and then
run:
$ poetry install
Usage
The probabilistic_automata library centers around the PDFA object
which models a finite probabilistic transition system, e.g., a Markov
Decision Process, as a DFA or Moore Machine over a product alphabet
over the system's actions and the environment's stochastic action.
import probabilistic_automata as PA

def transition(state, composite_action):
sys_action, env_action = composite_action
return (state + sys_action + env_action) % 2

def env_dist(state, sys_action):
"""Based on state and the system action, what are the probabilities
of the environment's action."""

return {0: 1/2, 1: 1/2} # Always a coin flip.

noisy_parity = PA.pdfa(
start=0,
label=bool,
inputs={0, 1},
env_inputs={0, 1},
outputs={0, 1},
transition=transition,
env_dist=env_dist, # Equivalently, PA.uniform({0, 1}).
)

The support and transition probabilities can easily calculated:
assert noisy_parity.support(0, 0) == {0, 1}
assert noisy_parity.transition_probs(0, 0) == {0: 1/2, 1: 1/2}
assert noisy_parity.prob(start=0, action=0, end=0) == 1/2

Dict <-> PDFA
Note that pdfa provides helper functions for going from a dictionary
based representation of a probabilistic transition system to a PDFA
object and back.
import probabilistic_automata as PA

mapping = {
"s1": (True, {
'a': {'s1': 0.5, 's2': 0.5},
}),
"s2": (False, {
'a': {'s1': 1},
}),
}

start = "s1"
pdfa = PA.dict2pdfa(mapping=mapping, start=start)
assert pdfa.inputs == {'a'}

mapping2, start2 = PA.pdfa2dict(pdfa)
assert start == start2
assert mapping2 == mapping

DFA to PDFA
The probabilistic_automata library has two convenience methods for
transforming a Deterministic Finite Automaton (dfa.DFA) into a
PDFA.

The lift function simply creates a PDFA whose transitions are
deterministic and match the original dfa.DFA.

import probabilistic_automata as PA
from dfa import DFA

parity = DFA(
start=0,
inputs={0, 1},
label=bool,
transition=lambda s, c: (s + c) & 1,
)

parity_pdfa = lift(parity)

assert pdfa.inputs == parity.inputs
assert pdfa.env_inputs == {None}

The randomize function takes a DFA and returns a PDFA modeling
the actions of the DFA being selected uniformly at random.

noisy_parity = PA.randomize(parity)

assert noisy_parity.inputs == {None}
assert noisy_parity.env_inputs == noisy_parity.inputs

Composition
Like their deterministic variants PDFA objects can be combined in
two ways:

(Synchronous) Cascading Composition: Feed outputs of one PDFA into another.

machine = noisy_parity >> noisy_parity

assert machine.inputs == noisy_parity.inputs
assert machine.outputs == noisy_parity.outputs
assert machine.start == (0, 0)

assert machine.support((0, 0), 0) == {(0, 0), (0, 1), (1, 0), (1, 1)}

(Synchronous) Parallel Composition: Run two PDFAs in parallel.

machine = noisy_parity | noisy_parity

assert machine.inputs.left == noisy_parity.inputs
assert machine.inputs.right == noisy_parity.inputs

assert machine.outputs.left == noisy_parity.outputs
assert machine.outputs.right == noisy_parity.outputs

assert machine.env_inputs.left == noisy_parity.env_inputs
assert machine.env_inputs.right == noisy_parity.env_inputs

assert machine.start == (0, 0)
assert machine.support((0, 0), (0, 0)) == {(0, 0), (0, 1), (1, 0), (1, 1)}

Note Parallel composition results in a PDFA with
dfa.ProductAlphabet input and output alphabets.