Applying information theory to the construction of decision diagrams

Summary form only given, as follows. An important problem with many applications is the problem of converting a decision table into an efficient decision diagram (an acyclic, directed graph with indegrees of the internal nodes possibly exceeding one). The authors treat the conversion problem as an optimization problem where a problem instance is a probabilistic decision table, and a feasible solution is a diagram that satisfies a given constraint on a linear combination of two performance measures, the discrimination measure based on Shannon's entropy and the probability of misclassification, which is the overall probability of error of the diagram. The objective function associates a cost to each feasible solution and the problem is to find the optimal solution, i.e., the feasible solution that minimizes the objective function. For the most commonly used costs (e.g. height or total storage) the conversion of a deterministic decision table into an optimal tree is an NP-hard problem. This provides the motivation for developing efficient heuristics for the construction of near-optimum decision diagrams. The authors' heuristic is a one-step look-ahead greedy algorithm that builds successive diagrams starting from the one-leaf tree and ending with a feasible diagram. An upper bound on the objective function is derived. Complexity issues are discussed, and examples are presented for illustration.