usainboltz.oracle¶
Various oracle implementations for Boltzmann sampling.
Oracles are used to get (often approximate) values of generating functions. Thanks to the symbolic method, functional equations can be derived from grammar specifications. This module implements some mechanics to approximate generating functions based on these equations.
Currently three oracles are implemented:
OracleFromDict
does nothing. It takes a dictionary of already computed values from the user and wraps them as anOracle
. This dictionary must have all the :class:`~usainboltz.grammar.Symbol`s of the grammar as keys and must be of one of the two following form: - Either it maps the symbols of the grammar to floating point values, in whichcase these values are interpreted as the values of the corresponding generating functions at a common point z.
- Or it maps them to an array of floating point values, in which case the j-th entry of each array is interpreted as the value of the corresponding generating function at z^j.
OracleFromPaganini
use the oracle Pagagnini of [BBD2018]OracleFromNewtonGF
use the oracle NewtonGF of [PSS2012] (only when Sagemath and Maple installations are present)
The entry point of these algorithms is the function oracle which determines the oracle to use given its inputs.
AUTHORS: - Matthieu Dien (2019): initial version - Martin Pépin (2019): initial version
References
[BBD2018] | Maciej Bendkowski, Olivier Bodini, Sergey Dovgal, 2018, Polynomial tuning of multiparametric combinatorial samplers, ANALCO |
[PSS2012] | Carine Pivoteau, Bruno Salvy, Michèle Soria, 2012 Algorithms for Combinatorial Structures: Well-founded systems and Newton iterations, Journal of Combinatorial Theory |
Functions
build_oracle (sys, **kargs) |
Build different oracles given different inputs |
Classes
Oracle |
The super class of all oracles. |
OracleFromDict (d, List[float]], …) |
|
OracleFromNewtonGF (grammar) |
Build an orcale using NewtonGF |
OracleFromPaganini (grammar) |
Build an oracle using paganini : a package developped by M.Bendkowski and S.Dovgal. |
-
class
usainboltz.oracle.
Oracle
¶ The super class of all oracles.
Should not be instantiated directly.
The
tuning
method must compute a suitable z and the corresponding values of the generating functions of the system. Sub classes may implement any interface for the tuning method as long as their outputd
satisfy the following requirements:d[Atom()]
is the list[1, z, z**2, z**3, ..., z**k]
for some floating point valuez
et some positive integerk
;- for each symbol
S
of the grammar,d[S]
is the list[1, S(z), S(z**2), S(z**3), ..., S(z**k)]
whereS(z**j)
denotes the generating function forS
(ordinary or exponential depending on the context) evaluated atz**j
; - all the lists appearing in this dictionary should have the same length
(
k+1
).
Most of the time
k=1
is enough but when Pólya operators likeMSet
appear in the grammar, more values are necessary. In such situations, any generation functionS(z**j)
withj > k
will be approximated by zero.-
__init__
¶ Initialize self. See help(type(self)) for accurate signature.
-
class
usainboltz.oracle.
OracleFromDict
(d: Union[Dict[usainboltz.grammar.Symbol, List[float]], Dict[usainboltz.grammar.Symbol, float]])¶ -
__init__
(d: Union[Dict[usainboltz.grammar.Symbol, List[float]], Dict[usainboltz.grammar.Symbol, float]])¶ Initialize self. See help(type(self)) for accurate signature.
-
tuning
(*args, **kwargs) → Dict[usainboltz.grammar.Symbol, List[float]]¶
-
-
class
usainboltz.oracle.
OracleFromNewtonGF
(grammar: usainboltz.grammar.Grammar)¶ Build an orcale using NewtonGF
Note
If you want to use OracleFormNewtonGF, please install the NewtonGF library for Maple into you Maple lib/ directory, or precise a lib/ directory to Maple i.e. maple(‘libname:=”NewtonGF_path”,libname:’)
-
__init__
(grammar: usainboltz.grammar.Grammar)¶ Build an oracle from a grammar
-
tuning
(rule: usainboltz.grammar.Symbol, expectations=None, singular=False) → Dict[usainboltz.grammar.Symbol, List[float]]¶ Run the oracle’s algorithm
Parameters: - rule – the targeted symbol to tune w.r.t.
expectations
- expectations –
- a mapping between grammar symbols and their targeted
- expectations after tuning
- singular: if
True
run the singular tuner (infinite expected size) else run - a tuner targeting the given
expectations
Returns: - a mapping between grammar symbols and their weights in the Boltzmann
model
Return type: values
Note
In the case of NewtonGF, only univariate specifications are supported, so: * if expectations is provided it must have a key corresponding to
Atom()
, * the markers (seeMarker
) will not be handled.Examples
Use of the singular tuner for a binary tree grammar (size is the number of internal nodes):
>>> from usainboltz import * >>> eps = Epsilon(); z = Atom(); B = RuleName() >>> grammar = Grammar({B: eps + z * B * B}) >>> o = OracleFromNewtonGF(grammar) # doctest: +SKIP >>> values = o.tuning(B,singular=True) # doctest: +SKIP >>> values[z] # doctest: +SKIP 0.25 >>> values[B] # doctest: +SKIP 1.999999988
As we expect
z
should be \(\frac14\) (the singularity of \(\frac{1-\sqrt{1-4z}}{2}\))- rule – the targeted symbol to tune w.r.t.
-
-
class
usainboltz.oracle.
OracleFromPaganini
(grammar: usainboltz.grammar.Grammar)¶ Build an oracle using paganini : a package developped by M. Bendkowski and S. Dovgal
Todo
add the reference to the paper
-
__init__
(grammar: usainboltz.grammar.Grammar)¶ Automatically build an oracle from a grammar using paganini.
Parameters: grammar – the grammar for which to build the oracle.
-
tuning
(rule: usainboltz.grammar.RuleName, expectations=None, singular=False) → Dict[usainboltz.grammar.Symbol, List[float]]¶ Run the oracle’s algorithm
Parameters: - rule – the targeted symbol to tune w.r.t.
expectations
- expectations – a mapping between grammar markers and their targeted expectations after tuning
- singular – if
True
run the singular tuner (infinite expected size) else run a tuner targeting the givenexpectations
Returns: - a mapping between grammar symbols and their weights in the Boltzmann
model
Return type: values
Note
If
singular
isTrue
, thenexpectations
should be should be a dictionnary with grammar names (but the atom) as keys and ratios (between 0 and 1) as values.- Else,
expectations
should be a dictionnary with keys as - grammar names (but
rule
) and the values should be integers.
Examples
Use of the singular tuner for a binary tree grammar (size is the number of internal nodes):
>>> from usainboltz import * >>> eps = Epsilon(); z = Atom(); B = RuleName() >>> grammar = Grammar({B: eps + z * B * B}) >>> o = OracleFromPaganini(grammar) >>> values = o.tuning(B, singular=True) >>> abs(values[z][1]-0.25) < 1e-12 True >>> abs(values[B][1]-2.) < 1e-12 True
As we expect
z
should be \(\frac14\) (the singularity of \(\frac{1-\sqrt{1-4z}}{2}\))- rule – the targeted symbol to tune w.r.t.
-
-
usainboltz.oracle.
build_oracle
(sys, **kargs) → usainboltz.oracle.Oracle¶ Build different oracles given different inputs
- EXAMPLES::
>>> from usainboltz import *
>>> leaf, z = Marker("leaf"), Atom() >>> B = RuleName("B") >>> g = Grammar({B: leaf + z * B * B}) >>> build_oracle(g) OracleFromPaganini({ B : Union(leaf, Product(z, B, B)) })
>>> build_oracle({'B': 2, 'z': 1./4}) OracleFromDict({'B': [1.0, 2], 'z': [1.0, 0.25]})