Applying information theory to the construction of decision diagrams

S. Khuri, C. R P Hartmann, Pramod Kumar Varshney

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationIEEE 1988 Int Symp on Inf Theory Abstr of Pap
PublisherIEEE Computer Society
Pages132
Number of pages1
Volume25 n 13
StatePublished - 1988
Externally publishedYes

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint Dive into the research topics of 'Applying information theory to the construction of decision diagrams'. Together they form a unique fingerprint.

  • Cite this

    Khuri, S., Hartmann, C. R. P., & Varshney, P. K. (1988). Applying information theory to the construction of decision diagrams. In IEEE 1988 Int Symp on Inf Theory Abstr of Pap (Vol. 25 n 13, pp. 132). IEEE Computer Society.