Decision Graphs 

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) x_{3} and x_{4}. If the learning problem is made slightly harder, for example,
the decision treetree 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 messagelength, and therefore can be justified by much less data (evidence). Decisiontrees and decisiongraphs describe exactly the same set of function but decisiongraphs 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 joinnode, 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 GraphIn learning with MML,
the twopart 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,
SearchThe 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. References


↑ © L. Allison, www.allisons.org/ll/ (or as otherwise indicated). Created with "vi (Linux)", charset=iso88591, fetched Friday, 01Mar2024 04:59:30 UTC. Free: Linux, Ubuntu operatingsys, OpenOffice officesuite, The GIMP ~photoshop, Firefox webbrowser, FlashBlock flash on/off. 