Jon Oliver devised decision graphs (classification graphs) [Oli92, OW92] to remove the difficulty that decision trees (classification trees) have with modelling "disjunctive" functions, for example,
A decision tree can certainly describe such a function,
but it requires two copies of the subtree for (here) x3 and x4.
If the learning problem is made slightly harder, for example,
the decision tree-tree to describe
it becomes much
The solution is to "factor out" any common subtrees and replace the tree by an equivalent directed acyclic graph (DAG). Such a DAG may be much smaller than the corresponding tree, have a smaller message-length, and therefore can be justified by much less data (evidence). Decision-trees and decision-graphs describe exactly the same set of function but decision-graphs model disjunctive functions more efficiently. (There is a small penalty for describing a DAG that is in fact a tree.)
The tree data structure is extended, to allow DAGs, by adding a new kind of node, a join-node, in addition to a tree's forks (tests) and leaves.
(The examples above use binary variables but decision graphs and trees apply to arbitrary discrete and continuous variables in the obvious way.)
Message Length of a Decision Graph
In learning with MML,
the two-part message length consists of
In step 1, cf trees, there are now 3 kinds of node. Oliver suggests using some fixed probability for pr(join_node); the tree method is used for a fork or a leaf given that a node is not a join.
In step 2, it is necessary to calculate the number
of possible ways, w, in which at least two of the the dangling joins
can be linked together, and encode the actual way,
The search for an optimal decision graph is harder than that for an optimal decision tree. Wallace and Oliver suggest a greedy search with some amount of lookahead.
↑ © L. Allison, www.allisons.org/ll/ (or as otherwise indicated).
Created with "vi (Linux)", charset=iso-8859-1, fetched Tuesday, 25-Jan-2022 06:24:25 EST.
Free: Linux, Ubuntu operating-sys, OpenOffice office-suite, The GIMP ~photoshop, Firefox web-browser, FlashBlock flash on/off.