Transcript Business System Analysis & Decision Making - Lecture 3

Lecture Notes 16: Bayes’
Theorem and Data Mining
Zhangxi Lin
ISQS 6347
1
Modeling Uncertainty
 Probability Review
 Bayes Classifier
 Value of Information



Conditional Probability and Bayes’ Theorem
Expected Value of Perfect Information
Expected Value of Imperfect Information
2
Probability Review
 P(A|B) = P(A and B) / P(B)
 “Probability of A given B”
 Example, there are 40 female students in a class of
100. 10 of them are from some foreign countries. 20
male students are also foreign students.
 Even A: student from a foreign country
 Even B: a female student
 If randomly choosing a female student to present in
the class, the probability she is a foreign student:
P(A|B) = 10 / 40 = 0.25, or P(A|B) = P (A & B) / P (B)
= (10 /100) / (40 / 100) = 0.1 / 0.4 = 0.25
 That is, P(A|B) = # of A&B / # of B = (# of A&B / Total)
/ (# of B / Total) = P(A & B) / P(B)
3
Venn Diagrams
30+10 = 40
Female
(30)
Male non-foreign student
(40)
20+10 = 30
Foreign
(10) Student
(20)
Female foreign student (10)
4
Probability Review
 Complement
P( A )  1  P( A)
P( B )  1  P( B)
Non Female
Female
Non Foreign
Student
Foreign
student
5
Bayes Classifier
6
Bayes’ Theorem (From Wikipedia)
 In probability theory, Bayes' theorem (often called Bayes' Law) relates
the conditional and marginal probabilities of two random events. It is
often used to compute posterior probabilities given observations. For
example, a patient may be observed to have certain symptoms. Bayes'
theorem can be used to compute the probability that a proposed
diagnosis is correct, given that observation.
 As a formal theorem, Bayes' theorem is valid in all interpretations of
probability. However, it plays a central role in the debate around the
foundations of statistics: frequentist and Bayesian interpretations
disagree about the ways in which probabilities should be assigned in
applications. Frequentists assign probabilities to random events
according to their frequencies of occurrence or to subsets of
populations as proportions of the whole, while Bayesians describe
probabilities in terms of beliefs and degrees of uncertainty. The articles
on Bayesian probability and frequentist probability discuss these
debates at greater length.
7
Bayes’ Theorem
P( A & B)
 P( A | B) P( B)  P( A & B)
P( B)
P( A & B)
P( B | A) 
 P( B | A) P( A)  P( A & B)
P( A)
P( A | B) 
So:
P( A | B) P( B)  P( B | A) P( A)
P( B | A) 
P( A | B) P( B)
P( A | B) P( B)

P( A)
P( A | B) P( B)  P( A | B ) P( B )
The above formula is referred to as Bayes’ theorem. It is extremely
Useful in decision analysis when using information.
8
Example of Bayes Theorem
 Given:



A doctor knows that meningitis (M) causes stiff neck (S) 50% of
the time
Prior probability of any patient having meningitis is 1/50,000
Prior probability of any patient having stiff neck is 1/20
 If a patient has stiff neck, what’s the probability
he/she has meningitis?
P( S | M ) P( M ) 0.5 1 / 50000
P( M | S ) 

 0.0002
P( S )
1 / 20
9
Bayes Classifiers
 Consider each attribute and class label as random
variables
 Given a record with attributes (A1, A2,…,An)
 Goal is to predict class C (= (c1, c2, …, cm))
 Specifically, we want to find the value of C that
maximizes P(C| A1, A2,…,An )
 Can we estimate P(C| A1, A2,…,An ) directly from data?
10
Bayes Classifiers
 Approach:
 compute the posterior probability P(C | A1, A2, …, An) for
all values of C using the Bayes theorem
P (C | A A  A ) 
1
2
n
P ( A A  A | C ) P (C )
P( A A  A )
1
2
n
1
2
n

Choose value of C that maximizes
P(C | A1, A2, …, An)

Equivalent to choosing value of C that maximizes
P(A1, A2, …, An|C) P(C)
 How to estimate P(A1, A2, …, An | C )?
11
Example
ca
 C: Evade (Yes, No)
 A1: Refund (Yes, No)
 A2: Marital Status (Single,
t
o
g
e
l
a
ric
ca
t
o
g
e
l
a
ric
n
o
c
u
it n
s
u
o
s
s
a
cl
Tid Refund Marital
Status
Taxable
Income Evade
1
Yes
Single
125K
No
2
No
Married
100K
No
3
No
Single
70K
No
4
Yes
Married
120K
No
 We can obtain P(A1, A2,
5
No
Divorced 95K
Yes
A3|C), P(A1, A2, A3), and
P(C) from the data set
 Then calculate P(C|A1, A2,
A3) for predictions given A1,
A2, and A3, while C is
unknown.
6
No
Married
No
7
Yes
Divorced 220K
No
8
No
Single
85K
Yes
9
No
Married
75K
No
10
No
Single
90K
Yes
Married, Divorced)
 A3: Taxable income (60k –
220k)
60K
10
12
Naïve Bayes Classifier
 Assume independence among attributes Ai when
class is given:

P(A1, A2, …, An |C) = P(A1| Cj) P(A2| Cj)… P(An| Cj)

Can estimate P(Ai| Cj) for all Ai and Cj.

New point is classified to Cj if P(Cj)  P(Ai| Cj) is
maximal.
Note: The above is equivalent to find i such that  P(Ai|
Cj) is maximal, since P(Cj) is identical.

13
How to Estimate
Probabilities
from
Data?
l
l
c
Tid
10
at
Refund
o
eg
a
c
i
r
c
at
o
eg
a
c
i
r
co
in
nt
u
s
u
o
s
s
a
cl
Marital
Status
Taxable
Income
Evade
 Class: P(C) = Nc/N

e.g., P(No) = 7/10,
P(Yes) = 3/10
1
Yes
Single
125K
No
2
No
Married
100K
No
3
No
Single
70K
No
 For discrete attributes:
4
Yes
Married
120K
No
P(Ai | Ck) = |Aik|/ Nc
5
No
Divorced
95K
Yes
6
No
Married
60K
No
7
Yes
Divorced
220K
No
8
No
Single
85K
Yes
9
No
Married
75K
No
10
No
Single
90K
Yes


k
where |Aik| is number of
instances having
attribute Ai and belongs
to class Ck
Examples:
P(Status=Married|No) =
4/7
P(Refund=Yes|Yes)=0
14
*How to Estimate Probabilities from Data?
 For continuous attributes:
 Discretize the range into bins
 one ordinal attribute per bin
 violates independence assumption
 Two-way split: (A < v) or (A > v)
 choose only one of the two splits as new attribute
 Probability density estimation:
 Assume attribute follows a normal distribution
 Use data to estimate parameters of distribution
(e.g., mean and standard deviation)
 Once probability distribution is known, can use it to
estimate the conditional probability P(Ai|c)
15
l
l
s
a
u
*How toricaEstimate
Probabilities
from Data?
c
i
r
uo
c
Tid
at
Refund
o
g
e
c
at
o
g
e
co
in
t
n
as
l
c
Marital
Status
Taxable
Income
Evade
1
Yes
Single
125K
No
2
No
Married
100K
No
3
No
Single
70K
No
4
Yes
Married
120K
No
5
No
Divorced
95K
Yes
6
No
Married
60K
No
7
Yes
Divorced
220K
No
8
No
Single
85K
Yes
9
No
Married
75K
No
10
No
Single
90K
Yes
s
 Normal distribution:
1
P( A | c ) 
e
2
i
j

( Ai   ij ) 2
2  ij2
2
ij

One for each (Ai,ci) pair
 For (Income, Class=No):

If Class=No
sample mean = 110
 sample variance = 2975

10
1
P( Income  120 | No) 
e
2 (54.54)

( 120110) 2
2 ( 2975)
 0.0072
16
Example of Naïve Bayes Classifier
Given a Test Record:
X  (Refund  No, Married, Income  120K)
naive Bayes Classifier:
P(Refund=Yes|No) = 3/7
P(Refund=No|No) = 4/7
P(Refund=Yes|Yes) = 0
P(Refund=No|Yes) = 1
P(Marital Status=Single|No) = 2/7
P(Marital Status=Divorced|No)=1/7
P(Marital Status=Married|No) = 4/7
P(Marital Status=Single|Yes) = 2/7
P(Marital Status=Divorced|Yes)=1/7
P(Marital Status=Married|Yes) = 0
For taxable income:
If class=No:
sample mean=110
sample variance=2975
If class=Yes: sample mean=90
sample variance=25

P(X|Class=No) = P(Refund=No|Class=No)
 P(Married| Class=No)
 P(Income=120K| Class=No)
= 4/7  4/7  0.0072 = 0.0024

P(X|Class=Yes) = P(Refund=No| Class=Yes)
 P(Married| Class=Yes)
 P(Income=120K| Class=Yes)
= 1  0  1.2  10-9 = 0
Since P(X|No)P(No) > P(X|Yes)P(Yes)
Therefore P(No|X) > P(Yes|X)
=> Class = No
17
Naïve Bayes Classifier
 If one of the conditional probability is zero,
then the entire expression becomes zero
 Probability estimation:
Original : P( Ai | C ) 
N ic
Nc
c: number of classes
N ic  1
Laplace : P( Ai | C ) 
Nc  c
m - estimate : P( Ai | C ) 
N ic  mp
Nc  m
p: prior probability
m: parameter
18
*Example of Naïve Bayes Classifier
Name
human
python
salmon
whale
frog
komodo
bat
pigeon
cat
leopard shark
turtle
penguin
porcupine
eel
salamander
gila monster
platypus
owl
dolphin
eagle
Give Birth
yes
Give Birth
yes
no
no
yes
no
no
yes
no
yes
yes
no
no
yes
no
no
no
no
no
yes
no
Can Fly
no
no
no
no
no
no
yes
yes
no
no
no
no
no
no
no
no
no
yes
no
yes
Can Fly
no
Live in Water Have Legs
no
no
yes
yes
sometimes
no
no
no
no
yes
sometimes
sometimes
no
yes
sometimes
no
no
no
yes
no
Class
yes
no
no
no
yes
yes
yes
yes
yes
no
yes
yes
yes
no
yes
yes
yes
yes
no
yes
mammals
non-mammals
non-mammals
mammals
non-mammals
non-mammals
mammals
non-mammals
mammals
non-mammals
non-mammals
non-mammals
mammals
non-mammals
non-mammals
non-mammals
mammals
non-mammals
mammals
non-mammals
Live in Water Have Legs
yes
no
Class
A: attributes
M: mammals
N: non-mammals
6 6 2 2
P( A | M )      0.06
7 7 7 7
1 10 3 4
P( A | N )      0.0042
13 13 13 13
7
P( A | M ) P ( M )  0.06   0.021
20
13
P( A | N ) P( N )  0.004   0.0027
20
P(A|M)P(M) > P(A|N)P(N)
=> Mammals
?
19
Naïve Bayes (Summary)
 Robust to isolated noise points
 Handle missing values by ignoring the instance during
probability estimate calculations
 Robust to irrelevant attributes
 Independence assumption may not hold for some
attributes

Use other techniques such as Bayesian Belief
Networks (BBN)
20
Value of Information
When facing uncertain prospects we need information in order
to reduce uncertainty
Information gathering includes consulting experts, conducting
surveys, performing mathematical or statistical analyses, etc.
21
Expected Value of Perfect Information
(EVPI)
Problem: An buyer is to buy something online
Seller type Bad
Not use insurance
Pay $100
Net gain
- $100
0.01
EMV = $18.8
0.99
Buyer
Good
$20
Bad
- $2
0.01
EMV = $17.8
Use insurance
Pay $100+$2 = $102
Good
0.99
$18
22
Expected Value of Imperfect
Information (EVII)
 We rarely access to perfect information, which is common. Thus
we must extend our analysis to deal with imperfect information.
 Now suppose we can access the online reputation to estimate
the risk in trading with a seller.
 Someone provide their suggestions to you according to their
experience. Their predictions are not 100% correct:
 If the product is actually good, the person’s prediction is 90%
correct, whereas the remaining 10% is suggested bad.
 If the product is actually bad, the person’s prediction is 80%
correct, whereas the remaining 20% is suggested good.
 Although the estimate is not accurate enough, it can be used to
improve our decision making:
 If we predict the risk is high to buy the product online, we
purchase insurance
23
Decision Tree
Extended from the previous online trading question
Seller type
No Ins
Predicted Good
Insurance
Buyer
No Ins
- $100
Good (?)
$20
Bad (?)
- $2
Good (?)
$18
Bad (?)
- $100
Good (?)
$20
Bad (?)
Predicted Bad
Insurance
Questions:
Bad (?)
Good (?)
1. Given the
suggestion
What is your
decision?
2. What is the
probability
wrt the decision you
made?
3. How do you
estimate
The accuracy of a
prediction?
- $2
$18
24
Applying Bayes’ Theorem





Let “Good” be even A
Let “Bad” be even B
Let “Predicted Good” be event G
Let “Predicted Bad” be event W
According to the previous information, for example by data mining the
historical data, we know:



P(G|A) = 0.9, P(W|A) = 0.1
P(W|B) = 0.8, P(G|B) = 0.2
P(A) = 0.99, P(B) = 0.01
 We want to learn the probability the outcome is good providing the
prediction is “good”. i.e.

P(A|G) = ?
 We want to learn the probability the outcome is bad providing the
prediction is “bad”. i.e.

P(B|W) = ?
 We may apply Bayes theorem to solve this with imperfect information
25
Calculate P(G) and P(W)
 P(G) = P(G|A)P(A) + P(G|B)P(B)
= 0.9 * 0.99 + 0.2 * 0.01
= 0.893
 P(W) = P(W|B)P(B) + P(W|A)P(A)
= 0.8 * 0.01 + 0.1 * 0.99
= 0.107
= 1 - P(G)
26
Applying Bayes’ Theorem
 We have
P(A|G) = P(G|A)P(A) / P(G)
= P(G|A)P(A) / [P(G|A)P(A) + P(G|B)P(B)]
= P(G|A)P(A) / [P(G|A)P(A) + P(G|B)(1 - P(A))]
= 0.9 * 0.99 / [0.9 * 0.99 + 0.2 * 0.01]
= 0.9978 > 0.99
 P(B|W) = P(W|B)P(B) / P(W)
= P(W|B)P(B) / [P(W|B)P(B) + P(W|A)P(A)]
= P(W|B)P(B) / [P(W|B)P(B) + P(W|A)(1 - P(B))]
= 0.8 * 0.01 / [0.8 * 0.01 + 0.1 * 0.99]
= 0.0748 > 0.01
 Apparently, data mining provides good information and changes
the original probability

27
Decision Tree
P(A) = 0.99, P(B) = 0.01
Seller type
Predicted Good
P(G) = 0.893
No Ins
Bad (0.0022)
- $100
Good (0.9978)
$20
Bad (0.0022)
- $2
EMV = $19.87
Your choice
EMV = $17.78
Insurance
Buyer
No Ins
Good (0.9978)
$18
Bad (0.0748)
- $100
EMV = $11.03
Good (0.9252)
Bad (0.0748)
Predicted Bad
P(W) = 0.107
Insurance
Good (0.9252)
$20
- $2
$18
EMV = $16.50
Your choice
Data mining can significantly improve your decision making accuracy!
28
Consequences of a Decision
Actual Good
(A)
Actual Bad (B)
Predicted Good
(G) (not to buy
insurance)
Predicted Bad
(W) (need to buy
insurance $2)
a
Gain $20
b
Net Gain $18
P(A)
= (a + b) / (a + b + c + d)
=0.99
d
Cost $2
P(B)
= (c + d) / (a + b + c + d)
= 0.01
c
Lose $100
P(G)
= (a + c) / (a + b + c + d)
= 0.893
P(W)
= (b + d) / (a + b + c + d)
= 0.107
P(G|A) = a / (a + b) = 0.9, P(W|A) = b / (a + b) = 0.1
P(W|B) = c / (c + d) = 0.8, P(G|B) = d / (c + d) = 0.2
29
German Bank Credit Decision
Computed Good
(Action A, B)
Computed Bad
(Action A, B)
Actual
Good
True Positive
600 ($6, 0)
False Negative
100 (0, -$1)
700
Actual
Bad
False Positive
80 (-$2, -$1)
True Negative
220 (-$20, 0)
300
680
320
This is a modified version of the German Bank credit decision problem.
1. Assume because of the anti-discrimination regulation there could be a cost in FN
depending on the action taken.
2. The bank has two choices of actions: A & B. Each will have different results.
3.Question 1: When the classification model suggests that a specific loan applicant has
a probability 0.8 to be GOOD, which action should be taken?
4. Question 2: When the classification model suggests that a specific loan applicant has
a probability 0.6 to be GOOD, which action should be taken?
30
The Payoffs from Two Actions
Computed Good
(Action A)
Computed Bad
(Action A)
Actual
Good
True Positive
600 ($6)
False Negative
100 (0)
700
Actual
Bad
False Positive
100 (-$2)
True Negative
200 (-$20)
300
700
Computed Good
(Action B)
300
Computed Bad
(Action B)
Actual
Good
True Positive
600 (0)
False Negative
100 (-$1)
700
Actual
Bad
False Positive
100 (-$1)
True Negative
200 (0)
300
700
300
31
Summary
 There are two decision scenarios
 In previous classification problems, when predicted
target is 1 then take an action, otherwise do nothing.
Only the action will make something different.
 There is a cutoff value for this kind of decision. A riskaversion person may set a higher level of cutoff value,
when the utility function is not linear with regard to the
monetary result.
 The risk-aversion person may opt for earn less without
the emotional worry of the risk.
 In current Bayesian decision problem, when the
predicted target is 1 then take action A, otherwise take
Action B. Both actions will result in some outcomes.
32
Web Page Browsing
P0
Problem:
When a browsing user
Entered P5 from P2,
What is the probability
He will proceed to P3?
P1
P2
0.7
P5
P4
0.3
P3
How to solve the problem
in general?
1. Assume this is the first
Order Markovian chain.
2. Construct a transition
probability matrix
We notice that
1. P(P2|P4P0) may not equal to P(P2|P4P1)
2. There is only one entrance of the web site at P0
3. There is no link from P3 to other pages.
33
Transition Probabilities
P(K,L)=Probability of traveling FROM K TO L
P0/H
P1
P2
P3
P4
P5
Exit
P0/H
P(H,H) P(H,1) P(H,2) P(H,3) P(H,4) P(H,5) P(H,E)
P1
P(1,H) P(1,1) P(1,2) P(1,3) P(1,4) P(1,5) P(1,E)
P2
P(2,H) P(2,1) P(2,2) P(2,3) P(2,4) P(2,5) P(2,E)
P3
P(3,H) P(3,1) P(3,2) P(3,3) P(3,4) P(3,5) P(3,E)
P4
P(4,H) P(4,1) P(4,2) P(4,3) P(4,4) P(4,5) P(4,E)
P5
P(5,H) P(5,1) P(5,2) P(5,3) P(5,4) P(5,5) P(5,E)
Exit
0
0
0
0
0
0
0
34
Demonstration
 Dataset: Commrex web log data
 Data Exploration
 Link analysis
 The links among nodes
 Calculate the transition matrix
 The Bayesian network model for the web log data
 Reference:
 David Heckerman, “A Tutorial on Learning With
Bayesian Networks,” March 1995 (Revised November
1996), Technical Report, MSR-TR-9506\\BASRV1\ISQS6347\tr-95-06.pdf
35
Readings
 SPB, Chapter 3
 RG, Chapter 10
36