CSE255  THURSDAY JANUARY 8, 1998



BAYES' RULE

Pr(Y|X) = Pr(Y & X)/Pr(X) = (Pr(X|Y)Pr(Y)) / Pr(X)

Conditional probabilities arise from causation often.

Example:
	meningitis causes stiff neck with 50% probability
	prio prob of meningitis is 1/50000
	prio of stiff is 1/20



ECOLOGICALLY VALID FREQUENCIES

Of 100000 patients, 2 have meningitis, one of those has a stiff neck,
and overall 5000 have a stiff neck.

 

NAIVE BAYES CLASSIFIER

See the handout.

Example:        grad admission
               /    |    \    \
              GRE  GPA  school major
 


NAIVE BAYES EQUATIONS



TAKING LOGARITHMS



CONTINUOUS ATTRIBUTES



COMPUTATIONAL COMPLEXITY

Summary: training an NBC requires O(ef) time where
e is the number of training examples, and f is the number of features
for each example.

This is time linear in the size of the input data.
Any learning algorithm that inspects all training data 
must have this complexity or worse.