USING THE MINIMUM DESCRIPTION LENGTH PRINCIPLE TO INFER REDUCED ORDERED DECISION GRAPHS

We propose an algorithm for the inference of decision graphs from a se t of labeled instances. In particular, we propose to infer decision gr aphs where the variables can only be tested in accordance with a given order and no redundant nodes exist. This type of graphs, reduced orde red decision graphs, can be used as canonical representations of Boole an functions and can be manipulated using algorithms developed for tha t purpose. This work proposes a local optimization algorithm that gene rates compact decision graphs by performing local changes in an existi ng graph until a minimum is reached. The algorithm uses Rissanen's min imum description length principle to control the tradeoff between accu racy in the training set and complexity of the description. Techniques for the selection of the initial decision graph and for the selection of an appropriate ordering of the variables are also presented. Exper imental results obtained using this algorithm in two sets of examples are presented and analyzed.