4

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:

enter image description here

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.

desertnaut
  • 57,590
  • 26
  • 140
  • 166
lisandrojim
  • 509
  • 5
  • 18

1 Answers1

6

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:

enter image description here

The package dd can be installed from PyPI with:

pip install dd
0 _
  • 10,524
  • 11
  • 77
  • 109
  • Thanks a lot for your answer. I have two questions for you: (1) is it possible to have explicitly two end-nodes (i.e., true/false)? (2) how could one use the model to evaluate an instance? (e.g., something like bdd.evaluate([x1=True, x2=False, x3= False]), and the answer, for this case, should be False or 0). – lisandrojim Feb 15 '21 at 07:38
  • 2
    The implementation uses complemented edges (so one end-node). It is possible to plot the BDD without complemented edges (so with two end-nodes), using the code at: https://github.com/tulip-control/dd/issues/41#issuecomment-589958394 . To evaluate the BDD, assuming that all variables in the support of the BDD are assigned values, the method `BDD.let` can be used. For example, `bdd.let(dict(x1=True, x2=False, x3=False), u) == bdd.true`. Documentation can be found at: https://github.com/tulip-control/dd/blob/master/doc.md . – 0 _ Feb 15 '21 at 11:10