Learn a PDFA using (Palmer & Goldberg, 2005)
PDFA Learning (Palmer & Goldberg, 2005)
Note: this implementation is deprecated. Consider using the implementation of the Balle's algorithm (see the next documentation page)
In this notebook, we will show how to use the implementation of PDFA learning, as described in [1].
Example
Utility functions to display SVGs.
%matplotlib inline
from pprint import pprint
from helpers import render_automaton
from pdfa_learning.learn_pdfa.base import learn_pdfa, Algorithm
from pdfa_learning.learn_pdfa.utils.generator import MultiprocessedGenerator, SimpleGenerator
from pdfa_learning.pdfa import PDFA
Example with 1 state.
Let's use the following automaton to generate samples.
p = 0.3
automaton = PDFA(
nb_states=2,
alphabet_size=2,
transition_dict={
0: {
0: (0, p),
1: (1, 1 - p),
},
1: {-1: (-1, 1.0)}
}
)
render_automaton(automaton)
Now we will run the PAC learning algorithm
to learn the above automaton.
MultiprocessedGeneratorwraps the automaton and generates samples using multiple processes;learn_pdfais the main entrypoint of the algorithm implementation.n1_max_debugis the maximum number for N_1 (for the subgraph learning)n2_max_debugis the maximum number for N_2 (for the probabilities learning)m0_max_debugis the maximum number for m_0 (for multiset filtering)
generator = MultiprocessedGenerator(SimpleGenerator(automaton), nb_processes=8)
pdfa = learn_pdfa(
algorithm=Algorithm.PALMER,
sample_generator=generator,
alphabet_size=2,
epsilon=0.2,
delta_1=0.2,
delta_2=0.2,
mu=0.1,
n=3,
n1_max_debug=100000,
n2_max_debug=100000,
m0_max_debug=100000 / 10,
)
The learned automaton is:
print("Transitions: ")
pprint(pdfa.transitions)
render_automaton(pdfa)
Example with 2 states.
Now let's try to learn the following automaton:
p1 = 0.4
p2 = 0.7
automaton = PDFA(
3,
2,
{
0: {
0: (1, p1),
1: (2, 1 - p1),
},
1: {
0: (2, 1 - p2),
1: (1, p2),
},
2: {
-1: (-1, 1.0)
}
},
)
render_automaton(automaton)
generator = MultiprocessedGenerator(SimpleGenerator(automaton), nb_processes=8)
pdfa = learn_pdfa(
algorithm=Algorithm.PALMER,
sample_generator=generator,
alphabet_size=2,
epsilon=0.2,
delta_1=0.2,
delta_2=0.2,
mu=0.1,
n=3,
n1_max_debug=3000000,
n2_max_debug=1000000,
m0_max_debug=3000000 / 10,
)
render_automaton(pdfa)
Palmer N., Goldberg P.W. (2005)
PAC-Learnability of Probabilistic Deterministic
Finite State Automata in Terms of
Variation Distance.
In: Jain S., Simon H.U., Tomita E. (eds)
Algorithmic Learning Theory. ALT 2005.
Lecture Notes in Computer Science, vol 3734.
Springer, Berlin, Heidelberg.
https://doi.org/10.1007/11564089_14