Transcript Uncertainty

Handling Uncertainty
Uncertain knowledge
• Typical example: Diagnosis. Consider data instances about patients:
Name
Toothache
…
Cavity
Smith
true
…
true
Mike
true
…
true
Mary
false
…
true
Quincy
true
…
false
…
…
…
…
• Can we certainly derive the diagnostic rule:
if Toothache=true then Cavity=true
?
– The problem is that this rule isn’t right always. Not all
patients with toothache have cavities; some of them have
gum disease, an abscess, …:
• We could try turning the rule into a causal rule:
if Cavity=true then Toothache=true
– But this rule isn’t necessarily right either; not all cavities
Belief and Probability
• The connection between toothaches and cavities is not a logical
consequence in either direction.
• However, we can provide a degree of belief on the rules. Our
main tool for this is probability theory.
• E.g. We might not know for sure what afflicts a particular
patient, but we believe that there is, say, an 80% chance – that is
probability 0.8 – that the patient has cavity if he has a toothache.
– We usually get this belief from statistical data.
Syntax
• Basic element: random variable – corresponds to an “attribute” of the
data.
• Boolean random variables
e.g., Cavity (do I have a cavity?)
• Discrete random variables
e.g., Weather is one of <sunny,rainy,cloudy,snow>
• Domain values must be exhaustive and mutually exclusive
• Elementary proposition constructed by assignment of a value to a random
variable: e.g., Weather = sunny, Cavity = false (abbreviated as cavity)
Prior probability and distribution
• Prior or unconditional probability associated with a proposition is the
degree of belief accorded to it in the absence of any other information.
e.g., P(Cavity = true) = 0.1 (or abbrev. P(cavity) = 0.1)
P(Weather = sunny) = 0.7 (or abbrev. P(sunny) = 0.7)
• Probability distribution gives values for all possible assignments:
P(Weather = sunny) = 0.7
P(Weather = rain) = 0.2
P(Weather = cloudy) = 0.08
P(Weather = snow) = 0.02
As a shorthand we can use a vector notation as:
P(Weather) = <0.7, 0.2, 0.08, 0.02> (they sum up to 1)
Conditional probability
• E.g., P(cavity | toothache) = 0.8
i.e., probability of cavity given that toothache is all I know
• It can be interpreted as the probability that the rule
if Toothache=true then Cavity=true
holds.
• Definition of conditional probability:
P(a | b) = P(a  b) / P(b)
if P(b) > 0
• Product rule gives an alternative formulation:
P(a  b) = P(a | b) P(b) = P(b | a) P(a)
Bayes' Rule
• Product rule
P(ab) = P(a | b) P(b) = P(b | a) P(a)
Bayes' rule:
P(a | b) = P(b | a) P(a) / P(b)
• Useful for assessing diagnostic probability from causal probability as:
P(Cause|Effect) = P(Effect|Cause) P(Cause) / P(Effect)
• Bayes’s rule is useful in practice because there are many cases
where we do have good probability estimates for these three
numbers and need to compute the fourth.
Applying Bayes’ rule
For example,
• A doctor knows that the meningitis causes the patient to have a
stiff neck 50% of the time.
• The doctor also knows some unconditional facts:
the prior probability that a patient has meningitis is 1/50,000, and
the prior probability that any patient has a stiff neck is 1/20.
Bayes’ rule (cont’d)
P(StiffNeck=true | Meningitis=true) = 0.5
P(Meningitis=true) = 1/50000
P(StiffNeck=true) = 1/20
P(Meningitis=true | StiffNeck=true)
= P(StiffNeck=true | Meningitis=true) P(Meningitis=true) /
P(StiffNeck=true)
= (0.5) x (1/50000) / (1/20) =
0.0002
That is, we expect only 1 in 5000 patients with a stiff neck to have meningitis.
This is still a very small chance. Reason is a very small apriori probability.
Also, observe that
P(Meningitis=false | StiffNeck=true)
= P(StiffNeck=false | Meningitis=false) P(Meningitis=false) /
P(StiffNeck=true)
1/ P(StiffNeck=true) is the same.
It is called the normalization constant (denoted with ).
Bayes’ rule (cont’d)
• Well, we might say that doctors know that a stiff neck implies meningitis in 1
out of 5000 cases;
– That is the doctor has quantitative information in the
diagnostic direction from symptoms (effects) to causes.
– Such a doctor has no need for the Bayes’ rule?!
• Unfortunately, diagnostic knowledge is more fragile than causal knowledge.
• Imagine, there is sudden epidemic of meningitis. The prior probability,
P(Meningitis=true), will go up.
– The doctor who derives the diagnostic probability P(Meningitis=true|StiffNeck=true)
from his statistical observations of patients before the epidemic will have no idea
how to update the value.
– The doctor who derives the diagnostic probability from the other three values will
see that P(Meningitis=true|StiffNeck=true) goes up proportionally with
P(Meningitis=true).
• Clearly, P(StiffNeck=true|Meningitis=true) is unaffected by the epidemic. It simply
reflects the way meningitis works.
Bayes’ rule -- more vars
P ( cause | effect 1 , effect 2 ) 
P ( cause , effect 1 , effect 2 )
P ( effect 1 , effect 2 )
  P ( cause , effect 1 , effect 2 )
  P ( effect 1 , effect 2 , cause )
  P ( effect 1 | effect 2 , cause ) P ( effect 2 , cause )
  P ( effect 1 | effect 2 , cause ) P ( effect
2
| cause ) P ( cause )
• Although the effect1 might not be independent of effect2, it might be that given
the cause they are independent.
• E.g.
• effect1 is ‘abilityInReading’
• effect2 is ‘lengthOfArms’
• There is indeed a dependence of abilityInReading to lengthOfArms. People
with longer arms read better than those with short arms….
• However, given the cause ‘Age’ the abilityInReading is independent on
lengthOfArms.
Conditional Independence – Naive Bayes
P ( cause | effect 1 , effect 2 )
  P ( effect 1 | effect 2 , cause ) P ( effect
  P ( effect 1 | cause ) P ( effect
2
2
| cause ) P ( cause )
| cause ) P ( cause )
P ( cause | effect 1 ,..., effect n )   P ( effect 1 | cause )... P ( effect n | cause ) P ( cause )
• Two assumptions:
– Attributes are equally important
– Conditionally independent (given the class value)
• This means that knowledge about the value of a particular attribute doesn’t
tell us anything about the value of another attribute (if the class is known)
• Although based on assumptions that are almost never correct, this scheme
works well in practice!
Weather Data
Here we don’t really have
effects, but rather
evidence.
Naïve Bayes for classification
• Classification learning: what’s the probability of the class
given an instance?
– Evidence E = instance or E1,E2,…, En
– Event H = class value for instance
• Naïve Bayes assumption: evidence can be split into
independent parts (i.e. attributes of instance!)
P(H | E1,E2,…, En)
= P(E1|H) P(E2|H)… P(En|H) P(H) / P(E1,E2,…, En)
The weather data example
P(play=yes | E) =
P(Outlook=Sunny | play=yes) *
P(Temp=Cool | play=yes) *
P(Humidity=High | play=yes) *
P(Windy=True | play=yes) *
P(play=yes) / P(E) =
= (2/9) *
(3/9) *
(3/9) *
(3/9) *
(9/14) / P(E) = 0.0053 / P(E)
Don’t worry for the 1/P(E); It’s
alpha, the normalization constant.
The weather data example
P(play=no | E) =
P(Outlook=Sunny | play=no) *
P(Temp=Cool | play=no) *
P(Humidity=High | play=no) *
P(Windy=True | play=no) *
P(play=no) / P(E) =
= (3/5) *
(1/5) *
(4/5) *
(3/5) *
(5/14) / P(E) = 0.0206 / P(E)
Normalization constant
play=yes
play=no
20.5% E
79.5%
P(play=yes, E) + P(play=no, E) = P(E)
P(play=yes, E)/P(E) + P(play=no, E)/P(E) = 1
P(play=yes | E) + P(play=no | E) = 1
0.0053 / P(E) + 0.0206 / P(E) = 1
P(E) = 0.0053 + 0.0206
So,
i.e.
i.e.
i.e.
i.e.
P(play=yes | E) = 0.0053 / (0.0053 + 0.0206) = 20.5%
P(play=no | E) = 0.0206 / (0.0053 + 0.0206) = 79.5%
The “zero-frequency problem”
• What if an attribute value doesn’t P(play=yes | E) =
occur with every class value (e.g.
P(Outlook=Sunny | play=yes) *
“Humidity = High” for class
“Play=Yes”)?
P(Temp=Cool | play=yes) *
– Probability
P(Humidity=High | play=yes) *
P(Humidity=High|play=yes)
P(Windy=True | play=yes) *
will be zero!
P(play=yes) / P(E) =
• A posteriori probability will also be
= (2/9) * (3/9) * (3/9) * (3/9) *(9/14) / P(E) =
zero!
0.0053 / P(E)
– No matter how likely the other
values are!
It will be instead:
Number of possible
values for ‘Outlook’
• Remedy:
– Add 1 to the count for every
= ((2+1)/(9+3)) * ((3+1)/(9+3)) *
attribute value-class
((3+1)/(9+2)) * ((3+1)/(9+2)) *(9/14) /
combination (Laplace
P(E) = 0.007 / P(E)
estimator);
– Add k (no of possible attribute
Number of possible
values) to the denumerator. (see
values for ‘Windy’
example on the right).
Missing values
• Training: instance is not included in frequency count for
attribute value-class combination
• Classification: attribute will be omitted from calculation
• Example:
P(play=yes | E) =
P(Temp=Cool | play=yes) *
P(Humidity=High | play=yes) *
P(Windy=True | play=yes) *
P(play=yes) / P(E) =
= (3/9) * (3/9) * (3/9) *(9/14) / P(E)
= 0.0238 / P(E)
P(play=no | E) =
P(Temp=Cool | play=no) *
P(Humidity=High | play=no) *
P(Windy=True | play=no) *
P(play=no) / P(E) =
= (1/5) * (4/5) * (3/5) *(5/14) / P(E)
= 0.0343 / P(E)
After normalization: P(play=yes | E) = 41%,
P(play=no | E) = 59%
Dealing with numeric attributes
• Usual assumption: attributes have a normal or Gaussian
probability distribution (given the class).
• Probability density function for the normal distribution is:
f ( x | class ) 

1

2
( x )
e
2
2
2
• We approximate  by the sample mean:
x 
1
n
x

n
i
i 1
• We approximate  2 by the sample variance:
s 
2
1
n
(x

n 1
i 1
i
 x)
2
Weather Data
outlook temperature humidity windy
sunny
85
85 FALSE
sunny
80
90 TRUE
overcast
83
86 FALSE
rainy
70
96 FALSE
rainy
68
80 FALSE
rainy
65
70 TRUE
overcast
64
65 TRUE
sunny
72
95 FALSE
sunny
69
70 FALSE
rainy
75
80 FALSE
sunny
75
70 TRUE
overcast
72
90 TRUE
overcast
81
75 FALSE
rainy
71
91 TRUE
play
no
no
yes
yes
yes
no
yes
no
yes
yes
yes
yes
yes
no
f(temperature=66 | yes)
=e(- ((66-m)^2 / 2*var) ) /
sqrt(2*3.14*var)
m=
(83+70+68+64+69+75+75+72
+81)/ 9 = 73
var = ( (83-73)^2 + (70-73)^2 +
(68-73)^2 + (64-73)^2 + (6973)^2 + (75-73)^2 + (75-73)^2
+ (72-73)^2 + (81-73)^2 )/ (9-1)
= 38
f(temperature=66 | yes)
=e(- ((66-73)^2 / (2*38) ) ) /
sqrt(2*3.14*38) = .034
Statistics for the weather data
Classifying a new day
• A new day E:
P(play=yes | E) =
P(Outlook=Sunny | play=yes) *
P(Temp=66 | play=yes) *
P(Humidity=90 | play=yes) *
P(Windy=True | play=yes) *
P(play=yes) / P(E) =
= (2/9) * (0.0340) * (0.0221) * (3/9)
*(9/14) / P(E) = 0.000036 / P(E)
P(play=no | E) =
P(Outlook=Sunny | play=no) *
P(Temp=66 | play=no) *
P(Humidity=90 | play=no) *
P(Windy=True | play=no) *
P(play=no) / P(E) =
= (3/5) * (0.0291) * (0.0380) * (3/5)
*(5/14) / P(E) = 0.000136 / P(E)
After normalization: P(play=yes | E) = 20.9%,
P(play=no | E) = 79.1%
Probability densities
• Relationship between probability and density:
• But: this doesn’t change calculation of a posteriori
probabilities because e cancels out
• Exact relationship:
Discussion of Naïve Bayes
• Naïve Bayes works surprisingly well (even if
independence assumption is clearly violated)
• Why?
• Because classification doesn’t require accurate probability
estimates as long as maximum probability is assigned to
correct class
• However: adding too many redundant attributes will cause
problems (e.g. identical attributes)
• Note also: numeric attributes might not be normally
distributed
Text Categorization
• Text categorization is the task of assigning a given document to one of a fixed
set of categories, on the basis of the text it contains.
• Naïve Bayes models are often used for this task.
• In these models, the query variable is the document category, and the effect
variables are the presence or absence of each word in the language.
• How such a model can be constructed, given as training data a set of
documents that have been assigned to categories?
• The model consists of the prior probability P(Category) and the conditional
probabilities P(Wordi | Category).
• For each category c, P(Category=c) is estimated as the fraction of all the
“training” documents that are of that category.
• Similarly, P(Wordi = true | Category = c) is estimated as the fraction of
documents of category that contain word.
• Also, P(Wordi = true | Category = c) is estimated as the fraction of documents
not of category that contain word.
Text Categorization (cont’d)
• Now we can use naïve Bayes for classifying a new document:
P(Category = c | Word1 = true, …, Wordn = true) =
*P(Category = c)ni=1 P(Wordi = true | Category = c)
P(Category = c | Word1 = true, …, Wordn = true) =
*P(Category = c)ni=1 P(Wordi = true | Category = c)
• Word1, …, Wordn are the words occurring in the new document
•  is the normalization constant.
• Observe that similarly with the “missing values” the new
documents doesn’t contain every word for which we computed
the probabilities.