Optimum decision trees - an optimal variable theorem and its related applications (Q1057175)

The problem of translation of a decision table into an optimal sequential testing procedure (STP) under two cost criteria is considered. STP is formulated as a decision tree (herafter simply tree) and its description and execution costs are introduced. Given a decision table, optimum trees are defined as those with a minimal cost. A variable is called optimal when it is placed and hence to be tested at the root of an optimum tree. Quasi-decisive variables are defined as those whose all ''branches'' are constants except a single branch. It is proved that under both costs and under the strong equivalence assumption of quasi-decisive variables (SEA), quasi-decisive variables are optimal and conversely, whenever they exist, only the quasi-decisive variables are optimal (main theorem). SEA holds under the general description cost and under the uniform execution cost. It is shown that SEA cannot be weakened in case of the general execution cost. An algorithm is described which constructs an optimum tree in \(O(N^{\log_ 23}\log_ 2N)\) comparison operations, where N is the size of the input table. Then it is shown that one can speed-up this algorithm by applying the optimal variable theorem in the description cost case though the computational order cannot be lowered below \(O(N^{\log_ 23})\). In fact, the number of executions of the inner- most loop of the algorithm was reduced to 42 \% its value without acceleration in case of the test-data tables. As a related topic, the optimization problem of a quasi-decisive chain under the execution cost is presented. It requires O(N log\({}_ 2N)\) operations. Optimum decision trees have wide applications in various concrete problems, for example, they allow to resolve the optimal ordering of IF statements in programs.