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 an Oracle. 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 which

    case 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 output d satisfy the following requirements:

  • d[Atom()] is the list [1, z, z**2, z**3, ..., z**k] for some floating point value z et some positive integer k;
  • for each symbol S of the grammar, d[S] is the list [1, S(z), S(z**2), S(z**3), ..., S(z**k)] where S(z**j) denotes the generating function for S (ordinary or exponential depending on the context) evaluated at z**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 like MSet appear in the grammar, more values are necessary. In such situations, any generation function S(z**j) with j > 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 (see Marker) 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}\))

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 given expectations
Returns:

a mapping between grammar symbols and their weights in the Boltzmann

model

Return type:

values

Note

If singular is True, then expectations 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}\))

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]})