Bayesian Classification

Bayesian classifiers are statistical classifiers based on Bayes' theorem. They predict the class with the maximum posterior probability, are competitive in accuracy with decision trees and neural nets, and are extremely fast even on large databases. The naive Bayes classifier assumes class-conditional independence of attributes.

1. Bayes' Theorem

P(H \mid X)=\frac{P(X \mid H)\,P(H)}{P(X)}

Term	Name	Meaning
$P(H)$	prior probability	probability that hypothesis $H$ holds before seeing data
$P(X\mid H)$	likelihood	probability of observing evidence $X$ given $H$
$P(X)$	evidence	prior probability of the evidence (constant for all classes)
$P(H\mid X)$	posterior probability	probability of $H$ after seeing $X$

For classification with class set $C$ and attribute tuple $X=(x_1,\dots,x_n)$ :

P(C_i\mid X)=\frac{P(X\mid C_i)\,P(C_i)}{P(X)}

The denominator is the same for every class, so the decision rule is:

\boxed{\text{Classify } X \text{ as } C_i \iff P(X\mid C_i)P(C_i) > P(X\mid C_j)P(C_j)\ \ \forall j e i}

If priors are unknown, $P(C_i) = |C_{i,D}|/|D|$ (fraction of training tuples in the class).

2. The "Naive" Independence Assumption

Attributes are assumed conditionally independent given the class (no dependence relationships among attributes):

P(X\mid C_i)=\prod_{k=1}^{n}P(x_k\mid C_i)

Then

P(C_i\mid X)\propto P(C_i)\prod_{k=1}^{n}P(x_k\mid C_i)

Lazy learning: naive Bayes needs no model building — probabilities are computed at classification time from the training set.

3. Worked Example (buys_computer, 14 tuples)

Class priors: $P(buys=yes)=\frac{9}{14}=0.357$ , $P(buys=no)=\frac{5}{14}=0.357$ (i.e. 9/14 and 5/14).

Class-conditional counts:

Attribute value	yes	no	Attribute value	yes	no
age = youth	2	3	income = high	2	2
age = middle	4	0	income = medium	4	2
age = senior	3	2	income = low	3	1
student = yes	6	1	credit = fair	6	2
student = no	3	4	credit = excellent	3	3

Classify $X = (\text{age}=youth,\ income=medium,\ student=yes,\ credit=fair})$

For $buys = yes$ :

P(youth\mid yes)=\tfrac{2}{9},\ P(medium\mid yes)=\tfrac{4}{9},\ P(yes\mid yes)=\tfrac{6}{9},\ P(fair\mid yes)=\tfrac{6}{9}

P(X\mid yes)P(yes)=\tfrac{2}{9}\cdot\tfrac{4}{9}\cdot\tfrac{6}{9}\cdot\tfrac{6}{9}\cdot\tfrac{9}{14}=0.028

For $buys = no$ :

P(youth\mid no)=\tfrac{3}{5},\ P(medium\mid no)=\tfrac{2}{5},\ P(yes\mid no)=\tfrac{1}{5},\ P(fair\mid no)=\tfrac{2}{5}

P(X\mid no)P(no)=\tfrac{3}{5}\cdot\tfrac{2}{5}\cdot\tfrac{1}{5}\cdot\tfrac{2}{5}\cdot\tfrac{5}{14}=0.007

Since $0.028 > 0.007$ → buys_computer = yes.

4. Zero-Frequency Problem and Laplace (Additive) Smoothing

If a class-attribute value never appears in the training data, $P(x_k \mid C_i) = 0$ and the whole product becomes 0, wiping out the other evidence.

Laplace smoothing:

P(x_k\mid C_i)=\frac{n_{ic}+1}{n_i+k}\quad \text{or}\quad \frac{n_{ic}+\lambda}{n_i+\lambda k}

where $n_{ic}$ = number of training tuples of class $C_i$ having value $x_k$ , $n_i$ = number of tuples of class $C_i$ , and $k$ = number of distinct values of the attribute. This is a Bayesian estimate — a uniform Dirichlet prior of $\lambda = 1$ .

5. Handling Numeric Attributes

Assume a Gaussian (normal) distribution per attribute per class, then use the density:

g(x,\mu,\sigma)=\frac{1}{\sqrt{2\pi}\,\sigma}\,e^{-\frac{(x-\mu)^2}{2\sigma^2}}

P(x_k\mid C_i)=g(x_k,\mu_{C_i},\sigma_{C_i})

where $\mu$ and $\sigma$ are the mean and standard deviation of attribute values for the class. Example: for income = 120K and class yes with $\mu=110,\sigma=20$ : $g=\frac{1}{\sqrt{2\pi}\,20}e^{-(120-110)^2/(2\cdot400)}=0.0089$ .

(Discretisation into intervals is an alternative to the Gaussian assumption.)

6. Alternative: Bayesian Belief Networks (BBN)

When attributes are dependent, naive Bayes is unrealistic. A Bayesian belief network is a DAG where nodes = random variables and arcs = probabilistic dependencies; each node carries a conditional probability table (CPT) given its parents:

P(x_1,\dots,x_n)=\prod_{i=1}^{n}P(x_i \mid \text{Parents}(x_i))

      FamilyHistory        Smoker
            \             /
             \           /
              \         /            P(LungCancer | FH, Smoker) given by CPT
            LungCancer  <-- from both
               /   \
        PositiveXRay   Dyspnea

BBNs can answer arbitrary queries with evidence (inference is NP-hard in general; approximations/junction trees used), give believable results with thousands of variables and are interpretable because structure shows dependencies.

Training a BBN: parameters (CPTs) are estimated by counting if the structure is known; structure learning is harder (hill climbing, K2, MDL/BIC scoring). Incomplete data needs EM or gradient methods.

7. Advantages and Limitations

Advantages

Easy, fast and highly scalable — no iterative parameter search, one pass over training data.
Robust to isolated noise (noise averaged out) and handles missing values (skip that attribute's probability term).
Works well on high-dimensional data; no need for many iterations/tuning; can be used for incremental learning.
Provides probabilistic predictions (useful for costs/thresholds) and a clear Bayesian foundation for combining prior domain knowledge.
BBN extension models dependencies → better accuracy when attributes correlate.

Limitations

Strong (naive) independence assumption — often violated, which can degrade accuracy (though the decision may still be right because the ranking is preserved).
Sensitivity to correlated/redundant attributes — duplicated attributes get their evidence counted twice; requires attribute selection (or BBN).
Zero-frequency estimates need Laplace smoothing; numeric attributes need discretisation or a normality assumption.
No output is a readable model (no rules/tree), and Bayesian belief network inference and structure learning are computationally expensive.

8. Exam Points

State Bayes' theorem and explain the naive Bayes classifier with the conditional independence assumption — 7-10 marks (very frequent).
Numerical: classify a given tuple using the buys_computer/weather data and show all probabilities — 10 marks (extremely frequent).
Explain the zero-frequency problem, Laplace smoothing and numeric attribute handling (Gaussian) — 5-7 marks.
Short note on Bayesian belief networks with CPT and an example DAG — 5-7 marks.
List advantages and limitations of Bayesian classification — 5 marks.

Bayesian Classification