The Bottom Line: The value at each CHANCE node depends on all the possible outcomes. The value at each CHOICE node is the value of the preferred outcome only.

Introduction

In everyday usage the word "ramification" is an over-the-top word for "consequence" or, sometimes, "implication" as in "What are the ramifications of this?" If you look it up in the dictionary, though, you'll find it has another meaning — to be structured by branches (from ramify which means "to divide or spread out into branches or extend into subdivisions" from a Latin word, rāmus, for branch). Thus, linguistically, we have an association of "consequence" and "branch" and this nicely sets up the topic of decision trees and decision analysis.

oakland_tree_logo.jpg

Yogi Berra's advice, "If you come to a fork in the road, take it," is funny precisely because a fork in the road demands a choice. If take Robert Frost1 literally, such choices matter, but many hold that he was being ironic in his poem, suggesting that we tend to inflate the importance of our choice for the life we end up living, a little more in line with that the Chesire Cat has in mind:

One day Alice came to a fork in the road and saw a Cheshire cat in a tree. "Which road do I take?" she asked. "Where do you want to go?" was his response. "I don't know," Alice answered. "Then," said the cat, "it doesn't matter." — Lewis Carroll


From Berra we get the imperative, at a fork, to choose. It's also embodied in that old quote, "If you chase two rabbits, both will escape."

The CC (via LC, aka CD) gives us an important insight: the motivation for choosing one branch over another depends on our goals, and Frost suggests that you can only know the value of a fork in the road if you know where it lands you in the long run.

All these insights will prove important as we look at decisions and decision trees.

Lecture I

Decision trees as non-deterministic flowcharts. A quick refresher on probability and expected value. Conventions. How to work backward in a decision tree.

Everything we have looked at so far seems to be about how to arrive at a decision as to the best course of action in given situation. We now turn to a slightly more complex (and more realistic) situation: sequential decisions in which some decisions depend on the outcome of previous decisions and some depend on the results of events we can't control.

Each path from the root of the tree on the left to the end of a branch on the right represents a sequence of decisions (things we can control) and events (things we can't control).

We'll divide our work into three parts. First, we'll learn how to build a basic decision tree and how to compare various branches in terms of the expected value of the sequence it represents. Next we'll learn how to incorporate into the model the amount of riskiness we are willing to accept. Finally, we will look at the value of information (for example, of tests or inspections that can reduce the uncertainty about the outcomes of particular courses of action).

Decision Trees as Fallen Flow Charts — Sorta

Recall our encounter earlier in the semester with flow charts. There, we used a chart with actions, decisions, and arrows to describe the logical flow of a process, the implementation of a protocol that included consideration of contingencies (if X, then do Y) –- situations where we reach a fork in the road and must assess solid information to decide which path to pursue.

A flow chart described a process in which the rules have already been set and the information needed to make a decision is available, and certain, when the decision must be made. It is deterministicSaid of a process when there are contingencies but these depend only on measurable or observable conditions rather than on chance. Opposite, obviously, of non-deterministic, but also, sometimes, of "stochastic" or "probabilistic." (google, wikipedia). A flow chart tells us what decision to make at each fork in the road based on some existing condition.

Notice in the flow chart below that even though we call diamond 1 a "decision" it does not actually represent CHOICE. If we are following this flow chart we must exit the diamond either to the left or right depending on some condition we've labeled "1".

The decision tree at the right captures this. At step A we have only one choice: move on to node 1. There, depending on some external condition, we go up the branch toward B or down the branch toward C. At node B we have only one choice: D. Similarly at node C — after C, we do D. Stare at these for a moment to be sure you see how they represent the same logic.

flowcharts-and-decisiontrees.png

A Change in Focus

Let's go back to the circle labeled 1 — the proverbial "fork in the road." In a (deterministic) flow chart, we have a condition and if it is true, we take one path, and if false the other. In a nondeterministic situation there is agency, when we arrive at a fork in the road, we have to decide.

Example: my dinner plans are to start with an Appetizer and then I am going to have either Beef or Cod and the I will have Dessert. But the waiter is coming so I have to decide between Beef and Cod. Which one should I choose?

What will happen if I have the beef? How will my evening, my life, turn out? There's a chance it will lead to ultimate happiness, but there's a chance it will lead to disaster! How about if I have the cod? What does the future hold?

What we want to do now, is come up with a technique for determining what best course of action to pursue when outcomes are uncertain.

A decision tree is a graphic representation of a technique for analyzing sequences of choices and contingencies.

Basics

  1. A tree consists of nodes and branches.
  2. Time/Sequence moves from left to right
  3. Two kinds of nodes: chance and choice.
    1. Choice nodes (square) — here we have one or more branches from which we can select.
    2. Chance nodes (circle) — here there is some probability that one or another event will occur and send us down a particular branch to the next node.

Example

Suppose I have the opportunity to apply for a job. Should I call about a job? I'm probably not qualified, I think (for shame! don't think negatively!). It's probably already filled. It is a perfect job for me and I'd love to get it. I hate getting turned down. I feel ashamed and embarrassed when I get my hopes up and then get disappointed. Especially if others know about it. The job pays 45,000 a year to start. It's what I've trained for. I'll never get it. Do I sound like Eyeore?

Here's how we diagram this situation.

First, we note that I have a decision to make (to call or not to call) and that after I take an action, different things can happen.
Important: two very different things — decisions and chances.
We start on the left with a square which represents a decision. We label it 1. From this square a branch leads off to the right for each alternative among which I can decide. Here it is "to call" or "to not call."

to-call-or-not-to-call-01.gif

What can happen if I do not call? It is certain: I will not get the job. And, of course, I run no risk of getting embarrassed about getting turned down. We draw a circle for a "chance" node that we'll label B — even though the chance is, in this case, a certainty.

to-call-or-not-to-call-02.gif

But what if I do call? Then there is a chance (let's call it '''X''') that I get the job and am happy and there is a chance (it will be '''1 - x''') that I will not get the job and I'll feel embarrassed and disappointed. We draw this as a chance node labeled A with two branches coming off it.

to-call-or-not-to-call-03.gif

We can put these together in a decision tree. Note that the tree ends on the right with the end of each branch labeled by the outcome or payoff that we get if we follow the tree out to that spot. Here we have labeled these with smiley faces to indicate being happy, sad, or ambivalent.

to-call-or-not-to-call-full.gif

The next step is to figure out the "value" of the branches. To do this, we use expected values. Recall that the expected value is equal to the product of the likelihood of an outcome and the value of the outcome.

Here, the value of the "get job" branch is the product of $X$, the chance you get the job, and "HAPPY," the level of happiness getting a job represents.

Next we consider the expected value of the do not get a job branch. It's equal to $(1-X)$ times "SAD."

The convention for decision trees is that at a chance node, we add the expected values of the branches.

'''STOP AND THINK.''' This parallels the rule for "OR" with probabilities.

Thus, the value at node A is $X \times HAPPY - (1-X) \times SAD$

Just for fun, let's put some numbers on these. Suppose the delight of getting a job is worth 25 and the disappointment of not getting a job is $-5$. And assume that getting no job but avoiding disappointment is just 0. Then, the value of the top branch is $25X$ and the next branch is $-(1-X)5 = 5X-5$ and the bottom branch is zero.

The value at node A, then, is $25X + 5X - 5 = 30X-5$.

The value at node B is 0. Do you see why?

To make "call" more attractive than "do not call" $30X-5$ has be greater than zero. Or, $X > \frac {1} {6}$. So, if there's a better than 1 in 6 chance you'll get the job, you should call.

Review

What we just did was set up a scenario in which we had to choose between two courses of action. For each course of action there was a contingency — more than one outcome could occur and we were able to estimate both how likely the outcome and what its value was. On the lower branch it was simple: one outcome only (100% likely) and value is zero. We combined the expected value of the two paths out of the chance node (getting the job and getting turned down) to produce an expected value for the upper branch out of the choice node. And at this node we decide in favor of the branch with the highest expected value.

Choice nodes are square. Chance nodes are round. Expected value of a path is "chance" x "payoff." Expected value at a chance node is sum of expected values of branches coming out of it. Expected value at a choice node is expected value of maximum path out of the node.

See also

Getting Started with TreeAge Pro (youtube)
http://www.treeplan.com/chapters/19_decan_20071029_1042.pdf
http://people.brunel.ac.uk/~mastjjb/jeb/or/decmore.html
http://www.public.asu.edu/~kirkwood/DAStuff/decisiontrees/DecisionTreePrimer-3.pdf
http://en.wikipedia.org/wiki/Decision_tree_learning
http://courses.csail.mit.edu/6.825/fall04/exercises/dec_thy.pdf
https://groups.google.com/forum/#!msg/d3-js/99XttLC6DsI/Onz66IwJsa8J