Learning Binary Decision Diagrams (BDDs) from data in Python

Question

Is it possible to learn Binary Decision Diagrams (BDDs) from data (as in a machine learning fashion)? If so, how?

Background: I've seen some tools in Python to do this task in e.g., Decision Trees (DTs) with scikit-learn, but I have not seen any for BDDs.

As an example, what I want to do is the following:

The first three columns correspond to the 'input' data set (xi), and the label is (y). N corresponds to the counts, you could use the latter for instance to compute the accuracy. Be aware that this is not a cut sets matrix. In the center, you see one corresponding BDD (this is the diagram I want to obtain) and on the right a corresponding DT.

Answer 1

If the objective is to convert the table of input-output valuations to a BDD that represents the Boolean function defined by those valuations, then yes this is possible (it is not any form of learning). For example, using the Python package dd:

from dd import autoref


bdd = autoref.BDD()
bdd.declare('x1', 'x2', 'x3')
# These are the assignments to the input variables
# where the Boolean function is TRUE (the y).
# The assignments where the Boolean function is FALSE
# are not used in the disjunction below.
data = [
    dict(x1=True, x2=False, x3=True),
    dict(x1=True, x2=True, x3=False),
    dict(x1=True, x2=True, x3=True)]
u = bdd.false
for d in data:
    u |= bdd.cube(d)  # disjunction so far
bdd.dump('example.png', roots=[u])

we obtain the following diagram that includes complemented edges:

The package dd can be installed from PyPI with:

pip install dd