language: en

Inferring Reduced Ordered Decision Graphs of Minimal Description Length

Arlindo L. Oliveira * Alberto Sangiovanni-Vincentelli
Dept. of EECS, UC Berkeley,
Berkeley CA 94720
july 1, 1994

Abstract This work describes an approach for the inference of reduced ordered decision graphs from training sets. Reduced ordered decision graphs (RODGs) are graphs where the variables can only be tested in accordance with a pre-specified order and no redundant nodes exist. RODGs have several interesting properties that has made them the representation of choice for the manipulation of Boolean functions in the logic synthesis community. We derive a RODG representation of the function implemented by a decision tree. This decision tree can be obtained from a training set using any one of the different algorithms proposed to date. This RODG is then used as the starting point for an algorithm that derives another RODG of minimal description length. The reduction in complexity is obtained by performing incremental changes in the RODG. By using ordered decision diagrams, the task of identifying common subgraphs is made much simpler than the identification of common sub-trees in a decision tree. Ordered decision graphs require that a variable ordering be specified in advance. The algorithm that derives such an ordering is based on a reordering algorithm commonly used that finds a locally optimal ordering by swapping the order of two adjacent variables. These algorithms are tested in a set of examples that are known to be hard to solve using decision trees. The results show that when an effective reduction of the description length is obtained, significant gains in generalization accuracy can be achieved. In all casesthe generalization accuracy of the final RODGwas better than the generalization accuracy of the decision tree that was used as the starting point.

1 Introduction