10 Decision Theory and Bayesian Decision Theory

epgp books

 

 

 

Welcome to the e-PG Pathshala Lecture Series on Machine Learning. In this module we will be discussing Decision Theory in general and Bayesian Decision theory in particular.

 

Learning Objectives:

 

The learning objectives of this module are as follows:

  • To understand decision theory, decision theory process and issues
  • To design the Decision Theory Model
  • To know the representation of Decision Theory
  • To understand and criteria for Decision Making

 

10.1 Decision Theory

 

Decision Theory is an approach to decision making which is suitable for a wide range of applications requiring decision making including management and machine learning. Some of the examples in which decision making is important is shown in Figure 10.1

 

 

Decision analysis provides a “framework for analyzing a wide variety of management models”. This framework is based on the system of classifying decision models which in turn depends on the a     mount of information about the model, decision criterion (a measure of the “goodness” of fit) and the treatment of decisions against nature (outcomes over which you have no control). Here only the decision maker is concerned with the result of the decision.

 

Decision Theory Elements

 

The elements of decision theory are a set of possible future conditions that can exist that will have affect the results of the decision, a list of possible alternatives to choose from and a calculated or known payoff for each of the possible alternatives under each of the possible future conditions.

 

10.1.2 Decision Theory Process

 

The steps involved in the decision theory process are:

 

•  Identification of the possible future conditions

• Development of a list of possible alternatives

• Determination of the payoff associated with each alternative

• Determination of  the likelihood

• Evaluation of the alternatives according to some decision criterion ü Selection of the best alternative

 

10.1.3 Causes of Poor Decisions

 

There are various causes for making poor decisions, the two main theories regarding these poor decisions are Bounded Rationality and Sub optimization.

 

Bounded Rationality is a theory that suggests that there are limits upon how rational a decision maker can actually be. The constraints placed on decision making are due to high costs, limitations in human abilities, lack of time, limited technology, and finally availability of information.

 

Sub optimization is due to narrowing of the boundaries of a system, for example considering a part of a complete system that leads to (possibly very good, but) non-optimal solutions. For example sub optimization may be because different departments try to make decisions that are optimal from the perspective of that department. However this is a viable method for finding a solution.

 

10.2 Decision Theory Representations

 

Decision theory problems are generally represented as any one of the following: Influence Diagram, Payoff Table and Decision Tree.

 

10.2.1 Influence Diagram

 

An influence diagram is an acyclic graph representation of a decision problem. Generally the elements of a decision problem are the decisions to make,uncertain events, and the value of outcomes. These elements are represented using three types of nodes namely random nodes represented as oval nodes, decision nodes represented as squares and value nodes represented as rectangles with rounded corners or triangles. These shapes are linked with arrows or arcs in specific ways to show the relationship among the elements. Figure 10.2 and Figure 10.3 show two examples of influence diagrams. Figure 10.2 shows an example for making a decision regarding Vacation Activity (decision node). Weather Forecast and Weather Condition are random nodes namely uncertain events while Satisfaction is a value node which is a result of the decision. Figure 10.3 shows the Influence Diagram for Treating the sick.

 

Sick 10.2.2 Payoff Matrix

 

The payoff matrix is a matrix whose rows are alternatives and columns are states where values of the matrix Cij is the consequence of state i under alternative j. Figure 10.4 (a) shows the structure of a payoff matrix while Figure 10.4 (b) shows an example of the payoff matrix for the anniversary problem. Here the rows correspond to the alternatives of either buying flowers or not buying flowers and the columns correspond to states of it either being your anniversary or it not being your anniversary. The entries in the matrix show the consequence of taking the alternative given the state.

 

Matrix 10.2.3 Decision Tree

 

Decision tree is a convenient way to explicitly show the order and relationships of possible decisions, the uncertain (chance) outcomes of decisions and the outcome results and their utilities (values). Figure 10.5 (a), shows the structure of the decision tree consisting decision points and chance events while Figure 10.5 (b) shows an same anniversary example described in the previous section but now represented using decision trees.

 

10.3 Formulation of an Example – Home Health

 

10.3.1 Home Health Example

 

In order to understand decision theory and the methods of choosing alternatives, we will consider the example given below. Suppose a home health agency is considering adding physical therapy (PT) services for its clients. There are 3 options for operating the service:

 

Option A: Contract with independent practitioner at ₹60 per visit.

Option B: Hire a staff physical therapist at a monthly salary of ₹4000 plus ₹400/month for leased car plus ₹7/visit for travel.

Option C: Have an independent practitioner at ₹35/visit but pay for fringe benefits at ₹200/month and cover the car & expenses as in Option B.

10.3.2 Alternatives

 

Figure 10.6 shows the three alternatives available to the home health agency. Let us assume that the agency proposes to charge ₹75 per visit. Let us assume that there are D visits. We are calculating the net profit for each alternative per month. The first alternative a1 gives a per visit net profit of ₹75 charged by the agency minus ₹60 paid to the independent practitioner. This has to be multiplied by the number of visits. The second alternative a2 gives a per visit net profit calculated based on monthly salary of ₹4000 paid per month plus the ₹400/month paid for leased car to the consultant and the ₹7 given to him per visit. This expense is subtracted from the amount obtained from the charges per visit. The third alternative a3 gives a per visit net profit calculated based on ₹400/month paid for leased car and fringe benefits paid at ₹200 per month with a contact amount of ₹35 and per visit amount of ₹7 to the consultant. This expense is subtracted from the amount obtained from the charges per visit.

 

Figure 10.6 Home Health Example – Alternatives 10.3.3 Payoff Matrix

 

Figure 10.7 shows the calculation of net profit or the payoff for each alternative considering visits per month to be 30, 90,140 and150. This is called the payoff matrix.

 

Now with this basic formulation of the Home Health Example, we will go on to discuss the different methods used to select the alternatives.

 

 

10.4 Decision Making under Uncertainty

 

There are basically four methods for choosing the alternatives, three of them based on payoffs and one based on regret. We will explain these methods using the example given in the previous section.

 

Maximin is the criterion where the decision making is based on choosing the alternative with the best of the worst possible payoffs

 

Maximax is the criterion where the decision making is based on choosing the alternative with the best possible payoff

 

Minimax Regret is the criterion where the decision making is based on choosing the alternative that has the least of the worst regrets

 

Laplace is the criterion where the decision making is based on choosing the alternative with the best average payoff among all the alternatives

 

10.4.1 Maximin – Conservative Approach

 

The conservative approach would be used by a decision maker who does not want to take risk and is satisfied by conservative returns. In this case the worst possible payoff is maximized and the maximum possible cost is minimized. The decision maker also ensures that the minimum possible profit is maximized.

 

Maximin Criterion is a criterion in decision making that maximizes the minimum payoff for each of the alternative. Here the steps are:

  • First identify the minimum payoff for each alternative (in our example it is ₹450 for alternative a1, ₹-2360 for alternative a2 and ₹390 for alternative a3).
  • Then pick the largest among the minimum payoff( which in our example is ₹450)

 

In other words we are maximizing the minimum payoff – hence the name – Maximin. The maximin criterion is a very conservative or risk adverse criterion.

 

It is a pessimistic criterion and assumes that nature will always vote against you.

 

 

Criterion 10.4.1.1 Minimax Criterion

 

If we consider that the values in the payoff matrix were costs instead of net profit then the equivalent conservative or risk adverse criterion would be the Minimax criterion. Like Maxmin it is also a pessimistic criterion.

 

10.4.2 Maximax Criterion

 

This is a criterion that maximizes the maximum payoff for each alternative. It is a very optimistic or risk seeking criterion and is not a criterion which preserves capital in the long run. Here the steps are:

  • First Identify the maximum payoff for each alternative.
  • Then pick the largest maximum payoff.

If the values in the payoff matrix were costs, the equivalent optimistic criterion is minimin. It assumes nature will vote for you.

 

10.4.3 Minimax Regret Approach

 

This method requires the construction of a regret table or an opportunity loss table. In this method we need to calculate for each state of nature the difference between each payoff and the best payoff for that state of nature. Using regret table, the maximum regret for each possible decision is listed. The decision chosen is the one corresponding to the minimum of the maximum regrets.

 

Minimax Regret Criterion minimizes the loss incurred by not selecting the optimal alternative. The steps are as follows:

 

Figure 10.10 Alternative chosen using Minimax Regret Criterion

 

  • Identify the largest element in each column (In our example this is 450 in the first column, 2370 in the second column, 5120 in the third column and 5800 in the last column)
  • Subtract each element in the column from the largest element to compute the opportunity loss and repeat for each column (we subtract the largest element identified (450) from all other elements of the column (Figure 10.10 (a)). We do this for all four columns of the payment matrix. This means that now each column will have one 0 value).
  • Identify the maximum regret for each alternative and then choose that alternative with the smallest maximum regret ( in our example this is the third alternative with smallest maximum regret of 1450(Figure 10.10 (b))

 

The minimax regret criterion is also a conservative criterion. However it is not as pessimistic as the maximin criterion.

 

10.4.4 Decision Making under Uncertainty- Laplace

 

Figure 10.11 shows the alternative chosen according to Laplace criterion. Here we take the average payoff of each alternative and then choose the alternative with maximum average.

 

10.5 Bayes Decision Theory

 

Now we will discuss the statistical approach that quantifies the tradeoffs between various decisions using probabilities and costs that accompany such decisions.

 

Let us consider the following example : A patient has trouble breathing. A diagnostic decision has to be made between asthma and lung cancer. Now if a wrong decision is made that it is lung cancer when actually the person has asthma or the decision asthma is made when actually the person has lung cancer, the cost is very high since the opportunity to treat cancer at early stage is lost and it may even result in death.

 

We now need a theory for how to make decisions in the presence of uncertainty. In other words we will use a probabilistic approach to help in decision making (e.g., classification) so as to minimize the risk (cost).

 

Therefore what we need is a fundamental statistical approach that quantifies the trade-offs between various classification decisions using probabilities and the costs associated with such decisions.

 

10.5.1 Preliminaries and Notations

 

Let {w1,w2, ……wc} be the state of nature from the finite set of c states of

 

nature (classes, categories).

 

Let {α1, . . . , αa} be the finite set of a possible actions.

 

Let x be the d-component vector-valued random variable called the feature vector.

 

Let λ(αi|wj) be the loss incurred for taking action αi when the true state of nature is wj.

 

Now let us consider the probabilities as we do in Bayes Theorem.

 

Let P(wj) be the prior probability that nature is in state wj.

 

Let P(x|wj) be the class conditional probability density function.

 

Let P(wj|x) is the posterior probability.

 

The posterior probability can be computed as

 

10.5.2 Bayes Decision Rule

 

First let us discuss the concept of probability of error. Let us assume that we have two classes w1, w2. The probability of error is defined as:

 

The Bayes rule is optimum, that is, it minimizes the average probability error since:

In other words probability of x given the error will be P(error/x) = min[P(ω1/x), P(ω2/x)].

 

Now let us generalize this concept in the context of decision theory.

 

Suppose we observe a particular x and that we consider taking action αi. If the true state of nature is wj, the expected incurred loss for taking action αi is

 

 

Overall risk

 

R = Sum of all R(ai | x) for i = 1,…,a where R(ai | x) is the conditional risk given in equation (2)

 

In other words minimizing R is equivalent to minimizing R(ai | x) for all actions  i

  • = 1,…, a. Now we need to select the action ai for which R(ai | x) is minimum.

 

The Bayes decision rule minimizes R by first computing R(αi /x) for every αi given an x and then choosing the action αi with the minimum R(αi /x). The resulting minimum overall risk is called Bayes risk and is the best (i.e., optimum) performance that can be achieved:

 

R* =minR

 

Therefore decision rule is a(x) that is essentially about deciding what action is to be taken in each situation x.

 

The final objective of the decision rule is to minimize the overall risk.

 

Now let us assume we need to compute p(y|x), where y represents the unknown state of nature (eg. does the patient have lung cancer, breast cancer or no cancer), and x are some observable features (eg., symptoms) Determining y based on x is called decision making, inference or prediction. In order to find f(x) we aim at minimizing the risk. As already discussed the risk of a decision rule f(x) is:

A person doesn’t feel well and goes to a doctor. Assume there are two states of nature:

 

ω1 : The person has a common flu and ω2 : The person is really sick.

 

The doctors prior is: p(ω1 )=0.9  p(ω2 )= 0.1 ——————————-

 

This doctor has two possible actions: “prescribe” hot tea or antibiotics. Doctor can use only prior and predict optimally always flu. Therefore doctor will always prescribe hot tea.

 

But there is very high risk in the doctor’s prescription since the doctor is considering only prior probability – that is how many cases of flu and how many cases of really sick has been encountered. Although this doctor can diagnose with very high rate of success using only prior, (s)he can lose a patient once in a while which is not advisable.

 

Now let us denote the two possible actions as a1 = Prescribe hot tea and a2 = Prescribe antibiotics.

Now let us assume the following cost (loss) matrix

Now if we use only prior probability given in equation (1)

 

Choosing a1 results in expected risk of

 

 

Just basing the decision on costs it is much better (and optimal) to always give antibiotics.

 

But doctors always do not make decisions based on costs alone. They generally take some medical observations before making decisions – A reasonable observation is to perform a blood test and

 

x1 = negative (no bacterial infection) and x2 = Positive (infection)

 

However there is the probability that blood tests can give wrong results. In order to account for this factor let us assume the following class conditional probabilities:

 

We would like to compute the conditional risk for each action and observation so that the doctor can choose an optimal action that minimizes risk. Whenever we encounter an observation x, we can minimize the expected loss y minimizing the conditional risk. We use the class conditional probabilities and Bayes inversion rule to calculate the posterior probabilities p(wi/xj) where i=1,2 and j is also = 1,2.

 

We  also  need  to  calculate  the  probabilities  of x1  =  negative  (no  bacterialinfection) and x2 = Positive (infection) that is p(x1) andp(x2). This is done as follows:

 

Figure 10.12 Calculation of Conditional Risk for each action and observation

 

Finally the Doctor chooses hot tea if blood test is negative, and antibiotics otherwise.

 

Summary

  • Outlined the decision theory issues
  • Discussed different decision criterion for pay-off matrix like the Minmax, Maximax and Maximin Regret
  • Bayesian Decision Theory is presented and the risk factor is calculated
  • Using conditional risk we show how the error rate can be reduced to a minimum
you can view video on Decision Theory and Bayesian Decision Theory

Web Links

 

  • http://www.yorku.ca/ptryfos/ch3000.pdf
  • www.calstatela.edu/faculty/ppartow/Java8.ppt
  • http://lesswrong.com/lw/gu1/decision_theory_faq/
  • https://stat.duke.edu/~scs/Courses/STAT102/DecisionTheoryTutorial.pdf
  • http://www.investopedia.com/terms/d/decision-theory.asp
  • http://people.kth.se/~soh/decisiontheory.pdf
  • http://www.umass.edu/preferen/Game%20Theory%20for%20the%20Behavioral%20Sciences/BOR%20Public/BOR%20Decision%20Theory%20and%20Human%20Behavior.pdf
  • www1.cs.columbia.edu/~belhumeur/courses/…/2010/Lecture%204.ppt
  • webcourse.cs.technion.ac.il/236875/Spring2006/ho/…/Tutorial2.ppt
  • web1.sph.emory.edu/users/tyu8/740/Lecture_2.ppt
  • http://www.cs.haifa.ac.il/~rita/ml_course/lectures/Tutorial_bayesianRisk.pdf
  • www.unc.edu/cit/mmaccess/sphSlideShows/…/Lesson9.1-HPAA241.ppt
  • www.academia.edu/7828529/Decision_Theory_and_Decision_Trees