View source for Encoding Decision Trees

Decision trees are often used to teach concepts of probability and decision making with uncertain outcomes.  Analytica does not support the direct encoding computation over decision trees -- it uses an influence diagram paradigm instead.  But the logic of a decision tree can be encoded within an influence diagram, and the same computations you might perform on a decision tree can be performed within an influence diagram encoding.  This page describes this "transformation" from a decision tree representation to an influence diagram representation, and then proceeds to additional advanced topics related to dynamic programming and sequential decision making.

= What Is a Decision Tree? =

A decision tree is a branching depiction of a set of sequential decision and chance outcomes, depicted in a decision tree diagram such as the following:

[[Image:Decision_tree.PNG||348x279px]]

Although the diagram shown was "drawn" using Analytica, this is ''not'' an Analytica model -- it is drawn only for illustration, and although the node shapes are the same as those in an influence diagram, the semantics of the nodes shown are different in a decision tree case.  The green rectangles are decision nodes, the ovals are chance outcomes, and the far right hexigons are objective (utility) nodes -- the same shape distinctions used by Analytica's influence diagrams.   But where an influence diagram would depict one decision node (e.g., D2), we see multiple instances of that decision on the decision tree -- one instance on each branch.  In a sense, a decision tree expands out the dimensionality visually, where the visual complexity increases multiplicatively with the number of decisions and chance nodes, whereas an influence diagram depiction increases only additively as we add decisions and chance outcomes.

In the decision tree, there are two possible options for decision D1.  If we were to decide D1=1, we'd take the top branch, otherwise if we were to decide D1=2 we'd take the bottom branch.  Suppose we take the top branch, then nature randomly selects one of two outcomes for C1, leading either up or down the next branch.  Through a set of sequential decisions and sequential chance outcomes, we eventually end up at a leaf, where a certain utility for that outcome is obtained.  The probabilities at each chance outcome can vary with the decisions and chance outcomes that preceded it, and likewise, a decision maker can base his decision on the decisions and chance outcomes that preceded that decision (i.e., each preceding chance outcome is observable at the time the decision is made).  Furthermore, the utility at each leaf can vary with all decisions and chance outcomes.

In general, decisions may have more than 2 options and chance nodes may have more than 2 possible outcomes.  The number of arrows emanating to the right of a node it called its branching factor.  The total number of leaf nodes is multiplicative in the branching factors of nodes, and hence, decision trees become infeasible in practice for all but the most simplistic of examples.  For this reason, they are often viewed primarily as a tool for teaching concepts of probability and sequential decision making with uncertainty.  Building your models as influence diagrams, and learning to think in terms of influence diagrams, will generally lead to more scalable approaches to modeling.

== Solving a decision tree ==

Solving a decision tree means involves computing, for each decision on each branch, what the optimal decision would be.  The collective set of decisions (aka policy) should be one that maximizes expected utility.  Notice in the diagram there are 4 instances of D2 -- one on each of the four branches (contingent on D1 and C1).  A separate decision may be assigned to each of those four instances of D2.  In the diagram, there are 13 decision node instances, each having 2 possible decisions, so that the total number of possible policies is 2<sup>13</sup> = 8,192.  If we added one more stage to the tree, this would increase to 2<sup>29</sup>=536,870,912 possible policies.

One can assign a probability to every leaf node -- the probability of reaching that leaf node given that all preceding decisions are taken to guide you on the path to that leaf node.  This probability is just the product of the probabilities of each outcome on the path from the root to the leaf node.

If you select a single policy, the decision tree could be collapsed to an ''event tree'' consisting only of chance nodes and utility nodes.   All branches inconsistent with the chosen policy are pruned away to get the event tree.  If you then multiply each utility by its probability, and add them all up, you'll get the expected utility of following that policy.  So one way to compute the optimal policy is brute force -- cycle through all policies, compute the expected utility and keep the policy that scores the highest.  This algorithm is, of course, horribly inefficient -- in fact, it is doubly-exponential in complexity.

One can do much better, with a singly-exponential algorithm (singly-exponential since the decision tree is already multiplicative in size compared to the number of decision and chance variables).  The method starts at the right of the diagram and backs up the utilities one layer at a time, determining first the decisions at D3, then the decisions at D2, and lastly the decisions at D1.  For each D3 node, you select the decision leading to the greated utility.  That becomes the utility on the arrow leading into that decision.  Using those, at each C2 node you compute the expected utility based on the probabilities of outcomes at that C2 instance, which becomes the utility on the arrow leading into each C2.  The arrows thus get labelled working your way back until the optimal decision at D1 is finally determined to complete the computation.