7. Bayesian Classification

7.1 Introduction

All Bayesian classification methods are fundamentally based on Bayes’ Theorem.

Bayes’ Theorem Formula:

Given two random events, $A$ and $B$, Bayes’ Theorem is stated as:

$P(A|B)=\frac{P(B|A)P(A)}{P(B)}$

This can also be expanded using the law of total probability for the denominator, assuming $A$ and its complement $\bar{A}$ form a partition of the sample space:

$P(A|B)=\frac{P(B|A)P(A)}{P(B|A)P(A)+P(B|\bar{A})P(\bar{A})}$ (Eq 7.1)

Terminology:

• $A$ and $B$: Random events.
• $\bar{A}$: The complement of event $A$.
• $A$: Typically represents a hypothesis to be tested or predicted.
• $B$: Represents the new data, observation, or evidence used to predict $A$.
• $P(A)$: The prior probability of hypothesis $A$. This reflects our belief or knowledge before observing the evidence $B$.
• $P(B|A)$: The likelihood of observing evidence $B$ given that hypothesis $A$ is true. Represents experience or prior knowledge about the relationship between $A$ and $B$.
• $P(B)$: The observation probability or evidence probability. This is the overall probability of observing the evidence $B$, regardless of hypothesis $A$. It acts as a normalization constant.
• $P(A|B)$: The posterior probability of hypothesis $A$ after observing the evidence $B$. This is the updated belief about $A$.

Core Idea of Bayes’ Theorem:

• It allows converting the computation of the posterior probability $P(A|B)$ into a form involving the likelihood $P(B|A)$, which is often easier to estimate or compute.
• Extremely helpful when $A$ and $B$ are dependent events and predicting $A$ directly is difficult due to lack of information.
• Information about $B$ (evidence) helps predict $A$ (hypothesis) more accurately.
• Information needed (like $P(A)$ and $P(B|A)$) can often be obtained from historical data or experience.

General Application Idea:

Predicting one event using other related events is a common practice (e.g., symptoms predict disease, clouds predict rain, rainfall predicts harvest). Bayes’ theorem provides a formal framework for this.

Example 1: Weather Prediction

• Goal: Predict if the weather will be fine (No Rain) for a weekend sports event, given the prediction of high humidity.

• Events:

  • $R=\text{Rain}$
  • $\bar{R}=\text{No rain}$
  • $H=\text{High humidity (humidity > 80\%)}$

• Prior Information (from history/meteorology):

  • $P(R)=35\%=0.35$
  • $P(\bar{R})=65\%=0.65$
  • $P(H|R)=30\%=0.3$ (Likelihood of high humidity given it rains)
  • (Implicitly assumed in the PDF’s calculation for this specific example, though not explicitly stated beforehand: $P(H|\bar{R})=1$. This seems counter-intuitive, likely meaning if it doesn’t rain, humidity is guaranteed to be high in this simplified scenario, or there’s a typo in the text/calculation setup. We follow the PDF’s calculation flow.)

• Evidence: We know there will be high humidity ($H$).

• Prediction: Calculate the chance of no rain given high humidity, $P(\bar{R}|H)$.

• Calculation (using Bayes’ Theorem as presented in PDF): $P(\bar{R}|H)=\frac{P(H|\bar{R})P(\bar{R})}{P(H)}$ $P(\bar{R}|H)=\frac{P(H|\bar{R})P(\bar{R})}{P(H|\bar{R})P(\bar{R})+P(H|R)P(R)}$

  Substituting the values used in the PDF’s calculation: $P(\bar{R}|H)=\frac{0.3\times 0.65}{0.3\times 0.65+1\times 0.35}$ $P(\bar{R}|H)=\frac{0.195}{0.195+0.35}=\frac{0.195}{0.545}\approx 0.357$ or $35.7\%$

  (Note: The PDF calculation arrives at $\approx 23\%$ with a denominator of $0.845$. There appears to be a numerical error or inconsistency in the values used within the PDF’s example calculation itself. The formula structure is correct, but the numbers applied don’t match the stated priors consistently leading to the PDF’s final answer. Reporting the PDF’s given result: $\approx 23\%$.)

• Conclusion: This posterior probability helps make a decision about the sports event. Prior information was crucial. In practice, more factors (temperature, pressure) are combined.

Example 2: Image Classification (Zebra)

• Goal: Determine how likely an image containing black and white strips ($BWS$) is a zebra ($Z$). We want $P(Z|BWS)$.

• Challenge: Need evidence/statistics to determine this likelihood accurately (e.g., 70%, 80%, 99%?).

• Approach: Use statistics from a sample of images (image database) to approximate population statistics.

• Events:

  • $Z=\text{Zebra image}$
  • $\bar{Z}=\text{non-Zebra image}$
  • $BWS=\text{Black and white strips detected (feature)}$

• Prior/Likelihood Information (from training set/database):

  • $P(BWS|Z)=1.0$ (Likelihood of strips given it’s a zebra - assume all zebras have strips)
  • $P(Z)=0.05$ (Prior probability of an image being a zebra)
  • $P(BWS|\bar{Z})=0.01$ (Likelihood of strips given it’s not a zebra - some other things might have strips)

• Evidence: We detected black and white strips ($BWS$) in a new image.

• Prediction: Calculate $P(Z|BWS)$.

• Calculation (using Bayes’ Theorem): $P(Z|BWS)=\frac{P(BWS|Z)P(Z)}{P(BWS)}$ $P(Z|BWS)=\frac{P(BWS|Z)P(Z)}{P(BWS|Z)P(Z)+P(BWS|\bar{Z})P(\bar{Z})}$

  Note: $P(\bar{Z})=1-P(Z)=1-0.05=0.95$. $P(Z|BWS)=\frac{1.0\times 0.05}{1.0\times 0.05+0.01\times 0.95}$ $P(Z|BWS)=\frac{0.05}{0.05+0.0095}=\frac{0.05}{0.0595}\approx 0.8403$ or $84\%$

• Conclusion: High chance ($\approx 84\%$) the image is a zebra. High confidence in classification.

Extension to Multiple Events (Hypotheses)

Bayes’ theorem can be extended when the evidence $B$ could be related to one of multiple mutually exclusive and exhaustive events $A_1,A_2,...,A_n$.

$P(A_i|B)=\frac{P(B|A_i)P(A_i)}{P(B)}$

Where the denominator is expanded using the law of total probability:

$P(A_i|B)=\frac{P(B|A_i)P(A_i)}{{\sum }_{k=1}^{n}P(B|A_k)P(A_k)}$ (Eq 7.2)

• Use Case: Predicting which specific event $A_i$ is responsible for the observation $B$.
• Example: Fever ($B$) can be caused by many diseases $A_i$ (flu, infection, etc.). Each disease $A_i$ has a different probability of causing fever, $P(B|A_i)$. Given a patient has fever ($B$), Eq 7.2 can be used to find the probability they have a specific disease, e.g., flu ($P(A_{flu}|B)$).
• Note: In practice (like clinical diagnosis), multiple symptoms ($B_1,B_2,...$) are often combined to increase diagnostic accuracy.

---

7.2 Naïve Bayesian Image Classification

Based on a simple application of Bayes’ theorem to numerical and high-dimensional image data.

7.2.1 NB Formulation

Setup:

• Given a set of $N$ images: $I=\{I_1,I_2,...,I_N\}$.
• Given a set of $n$ semantic classes: $C=\{C_1,C_2,...,C_n\}$ (these are the “hypotheses” or events).
• Each image $I$ belongs to one class in $C$.
• Each image $I$ is represented by a feature vector: $x=(x_1,x_2,...,x_m)$ (this is the “evidence” or observation).

Goal:

Classify (or annotate) a given image $I$ (represented by its feature vector $x$) into one of the classes $C_i$. We want to find the class $C_i$ that maximizes the posterior probability $P(C_i|I)$ or $P(C_i|x)$.

Applying Bayes’ Theorem:

$P(C_i|x)=\frac{P(x|C_i)P(C_i)}{P(x)}$

Expanding the denominator $P(x)$ (evidence probability):

$P(C_i|x)=\frac{P(x|C_i)P(C_i)}{{\sum }_{k=1}^{n}P(x|C_k)P(C_k)}$ (Eq 7.3, Eq 7.4)

Simplification:

• The denominator $P(x)={\sum }_{k=1}^{n}P(x|C_k)P(C_k)$ is the same for all classes $C_i$ when classifying a specific image $x$.
• It acts as a scaling factor and is independent of the class $C_i$ we are considering.
• Let $Z=P(x)$. Then:

$P(C_i|x)=\frac{1}{Z}P(x|C_i)P(C_i)$ (Eq 7.5)

Decision Rule: Maximizing A Posteriori (MAP)

To decide the class of image $I$ (with features $x$), we choose the class $C_i$ with the highest posterior probability. Since $Z$ is constant for a given $x$, maximizing $P(C_i|x)$ is equivalent to maximizing the numerator $P(x|C_i)P(C_i)$.

$\hat{C}=\arg {\max }_{i}P(C_i|x)=\arg {\max }_i\{P(x|C_i)P(C_i)\}$ (Eq 7.6)

Where $\hat{C}$ is the predicted class.

Components:

• Prior Probability $P(C_i)$:
  • Often assumed to be uniform for all classes ($P(C_i)=1/n$) if there’s no prior knowledge favoring any class.
  • Alternatively, can be estimated from the training data as the frequency or proportion of training samples belonging to class $C_i$.
• Likelihood $P(x|C_i)$:
  • The probability of observing the feature vector $x$ given that the image belongs to class $C_i$.
  • This is the core component that needs to be modeled or learned from the training data.
  • Since image features $x$ are often numerical and continuous, they typically need to be discretized or modeled using probability distributions before computing the likelihood.

Procedure for Likelihood Modeling (Typical Practice):

Described in the following Training section.

Training Steps:

1. Create Training Database: Collect images from all $n$ classes $C_1,...,C_n$.

2. Feature Extraction & Clustering:

   • Extract feature vectors $x$ from all training images.
   • Cluster these feature vectors into $m$ clusters $X_1,...,X_m$ using a vector quantization (VQ) algorithm (e.g., K-means). Each cluster $X_j$ represents a region in the feature space.

3. Compute Centroids: Calculate the centroid $x_j$ for each cluster $X_j$. The centroid $x_j$ acts as a representative feature vector for all samples in that cluster.

4. Calculate Likelihoods: Estimate the likelihood $P(x_j|C_i)$ (the probability of a feature vector belonging to cluster $X_j$ given it’s from class $C_i$). This is done by calculating the frequency:

   $P(x_j|C_i)=\frac{\text{No. of samples in cluster }{X}_j\text{ which are from class }{C}_i}{\text{Total no. of samples in cluster }{X}_j}$ (Eq 7.7)

Classification/Annotation Steps:

1. Input: A new image $I$ with its extracted feature vector $x$.

2. Match Feature: Find the closest cluster centroid $x_j$ to the input feature vector $x$ (e.g., using Euclidean distance). This step effectively discretizes the input feature $x$ by mapping it to $x_j$.

3. Apply MAP: Use the MAP decision rule (Eq 7.6), replacing the continuous likelihood $P(x|C_i)$ with the discretized likelihood $P(x_j|C_i)$ calculated during training (Eq 7.7):

   $\hat{C}=\arg {\max }_i\{P(x_j|C_i)P(C_i)\}$

   Calculate this value for all classes $i=1,...,n$ and choose the class $\hat{C}$ that gives the maximum value. This gives the posterior probability $P(C_i|I)$.

Figure 7.1: Image classification with Naïve Bayesian method

• Diagram Description: Illustrates the two main modules: Training and Annotation.
  • Training Module:
    1. Input Images are fed into Features extraction.
    2. Features are clustered into $m$ clusters (visualized as groups of points).
    3. Centroid $x_j$ is found for each cluster.
    4. Model building calculates the likelihoods $p(x_j|c)$ (using Eq 7.7) for each centroid $x_j$ and class $c$.
  • Annotation Module:
    1. Input image x (new image) goes through Features extraction.
    2. Matching finds the closest centroid $x_j$ from the training phase to the input features $x$.
    3. The corresponding likelihood $p(x_j|c)$ is retrieved.
    4. The posterior $p(x_j|c)p(c)` is calculated.
    5. MAP decision selects the class with the highest posterior.
    6. Output is the predicted `Label, $\hat{c}$.
  • A matching arrow connects the centroids from training to the matching step in annotation, indicating the link between the learned model and its application.

7.2.2 NB with Independent Features

Assumption: The individual features $x_1,x_2,...,x_m$ within the feature vector $x$ are independent of each other, given the class $C_i$.

• This is the “naïve” part of Naïve Bayes - this assumption is often violated in practice but simplifies the model significantly and works surprisingly well.

Likelihood Calculation:

Under the independence assumption, the likelihood of the entire feature vector $x$ is the product of the likelihoods of its individual features:

$P(x|C_i)=P(x_1,x_2,...,x_m|C_i)={\prod }_{j=1}^{m}P(x_j|C_i)$ (Eq 7.8)

Applicability:

• Useful when features are naturally independent or treated as such.
• Examples:
  • Nominal features from web crawling (e.g., presence/absence of keywords like ‘tree’, ‘grass’, ‘sand’). If $x=(\text{sand},\text{water},\text{sky},\text{people})$, classify image as “beach” vs “non-beach”.
  • Combining different types of numerical image features (e.g., $x=(\text{color features},\text{shape features},\text{texture features})$) where independence is assumed for computational simplicity.

7.2.3 NB with Bag of Features

Setup:

• An image $I$ is segmented into $k$ regions (or patches, blocks).
• Each region $j$ is represented by its own feature vector $x_j$.
• The image $I$ is represented as a bag (set) of these regional feature vectors: $I=\{x_1,x_2,...,x_k\}$. The spatial arrangement is ignored.

Assumption:

• The regions within the image are independent of each other, given the class $C_i$.

Conditional Probability Calculation:

The probability of observing the entire bag of features $I$ given the class $C_i$ is the product of the probabilities of observing each regional feature vector:

$P(I|C_i)=P(x_1,x_2,...,x_k|C_i)={\prod }_{j=1}^{k}P(x_j|C_i)$ (Eq 7.9)

• Here, $P(x_j|C_i)$ could be modeled using the clustering approach from section 7.2.1 (mapping $x_j$ to a cluster centroid) or using distributional assumptions if features are continuous.

---

7.7 Image Classification with Gaussian Process (GP)

Alternative Perspective on Feature Vectors:

• GMM View: Treats a multidimensional feature vector $x=(x_1,x_2,...,x_n)$ as a single point in an $n$-dimensional space (${\mathbb{R}}^n$). Models the distribution of these points.
• GP View: Treats a multidimensional feature vector $x$ as a discretized function $f:D\to \mathbb{R}$, where $y=f(d)$. The indices ($1,...,n$) represent points $d_i$ in some domain $D$, and the feature values $x_i=f(d_i)$ are the function outputs.
  • Example: A histogram feature vector. The bin indices are the domain $D‘,andthebinheightsarethefunctionvalues$x_i$.

Figure 7.6: Feature vectors shown as functions

• Diagram Description: Shows three different histograms (normalized feature vectors) from the same class, represented by vertical bars (red, green, blue). Above the bars, corresponding continuous functions (curves in red, green, blue) are shown, visualizing how each histogram can be seen as a sample from an underlying function.

Analogy to Regression:

• Linear regression fits a line to a cluster of data points.
• Gaussian Process can be thought of as fitting a mean function and confidence band to a cluster of functions (where each function corresponds to a data sample like a histogram).

Figure 7.7: A cluster of multidimensional data (green) and the approximation function (pink)

• Diagram Description: Shows many data points (green dots) representing the values $x_i=f(d_i)$ from multiple sample functions (histograms) plotted together. The pink curves show the learned Gaussian Process model: a mean function (center pink curve) and confidence bounds (outer pink curves) that capture the distribution of functions in this class.

Formal Setup:

1. Data: A set of $N$ data samples $x_1,x_2,...,x_N$ from a certain class $C$.
2. Dimensionality: Each sample $x_i$ is a $D$-dimensional feature vector: $x_i=(x_{i1},x_{i2},...,x_{iD})$.
3. Matrix Representation: Create a matrix $X$ of size $D\times N$. Each row ${\mathbf{d}}_j$ ($j=1,...,D$) represents the $j$-th dimension across all $N$ samples.

$$X=\left[\begin{array}{cccc}{x}_{11}& x_{21}& \dots & x_{N1}\\ x_{12}& x_{22}& \dots & x_{N2}\\ ⋮& ⋮& \ddots & ⋮\\ x_{1D}& x_{2D}& \dots & x_{ND}\end{array}\right]=\left[\begin{array}{c}{\mathbf{d}}_1\\ {\mathbf{d}}_2\\ ⋮\\ {\mathbf{d}}_D\end{array}\right]$$

(Eq 7.24) Here, ${\mathbf{d}}_j=(x_{1j},x_{2j},...,x_{Nj})$ is the $j$-th row vector.

4. Gaussian Process Definition:

   • Assume the elements within each dimensional vector ${\mathbf{d}}_j$ are samples from (or follow) a Normal distribution $\mathcal{N}({\mu }_j,{\sigma }_j)$.
   • The entire matrix $X$ (viewed as a collection of function values) is modeled as a Gaussian Process (GP).
   • A GP is defined by a mean function $\mu (d)$ and a covariance (kernel) function $k(d_i,d_j)$.
   • The data $X$ follows a multivariate Normal distribution: $X\sim \mathcal{N}({\mu }_X,K_{XX})$.

5. Mean Vector (${\mu }_X$) and Covariance Matrix ($K_{XX}$):

   • The mean vector ${\mu }_X$ contains the mean values for each dimension: $${\mu }_X=\left[\begin{array}{c}\mu ({\mathbf{d}}_1)\\ \mu ({\mathbf{d}}_2)\\ ⋮\\ \mu ({\mathbf{d}}_D)\end{array}\right]$$ (Eq 7.25) (Often simplified to assume a zero mean prior).
   • The covariance matrix $K_{XX}$ (or ${\Sigma }_{XX}$) describes the correlations between dimensions: $$K_{XX}=\left[\begin{array}{cccc}k({\mathbf{d}}_1,{\mathbf{d}}_1)& k({\mathbf{d}}_1,{\mathbf{d}}_2)& \dots & k({\mathbf{d}}_1,{\mathbf{d}}_D)\\ k({\mathbf{d}}_2,{\mathbf{d}}_1)& k({\mathbf{d}}_2,{\mathbf{d}}_2)& \dots & k({\mathbf{d}}_2,{\mathbf{d}}_D)\\ ⋮& ⋮& \ddots & ⋮\\ k({\mathbf{d}}_D,{\mathbf{d}}_1)& k({\mathbf{d}}_D,{\mathbf{d}}_2)& \dots & k({\mathbf{d}}_D,{\mathbf{d}}_D)\end{array}\right]$$ (Eq 7.26) Where $k({\mathbf{d}}_i,{\mathbf{d}}_j)$ is the kernel function evaluating the covariance between dimension $i$ and dimension $j$. Typical kernels include the RBF kernel.

6. Prediction with GP:

   • Given new data points $X_{\ast }$.
   • Concatenate observed data $X$ and new data $X_{\ast }$. The joint distribution is also a GP: $$f\left(\left[\begin{array}{c}X\\ X_{\ast }\end{array}\right]\right)\sim \mathcal{N}\left(\left[\begin{array}{c}{\mu }_X\\ {\mu }_{X_{\ast }}\end{array}\right],\left[\begin{array}{cc}{K}_{XX}& K_{X{X}_{\ast }}\\ K_{X_{\ast }X}& K_{X_{\ast }{X}_{\ast }}\end{array}\right]\right)$$ (Eq 7.27, using K notation consistent with 7.26) Where $K_{X{X}_{\ast }}$, $K_{X_{\ast }X}$, $K_{X_{\ast }{X}_{\ast }}$ are covariance matrices computed using the kernel function between the respective data points.
   • The predictive distribution for the new data $X_{\ast }$ given the observed data $X$ is also Gaussian: $p(X_{\ast }|X)=\mathcal{N}({\mu }_{pred},K_{pred})$ Where:
     • Predictive Mean: ${\mu }_{pred}={\mu }_{X_{\ast }}+K_{X_{\ast }X}{K}_{XX}^{-1}(X-{\mu }_X)$
     • Predictive Covariance: $K_{pred}=K_{X_{\ast }{X}_{\ast }}-K_{X_{\ast }X}{K}_{XX}^{-1}{K}_{X{X}_{\ast }}$ (Eq 7.28)
   • This allows predicting the values of the new data points and quantifying the uncertainty in the prediction.
   • Proof referenced to Appendix [7–9].

---

7.8 Summary

Chapter Overview:

• Introduced Bayesian classification as the first image classification method.
• Described several important applications and variations:
  • Naïve Bayes (NB)
  • Word Co-occurrence (WCC) model
  • Cross-Media Relevance Model (CMRM)
  • Parametric model (using GMMs)
  • Gaussian Process (GP) method

Key Features of Bayesian Classifiers:

1. Generative:
   • They are typically generative models.
   • They assume an underlying distribution or model for the likelihood probability ($P(\text{evidence}|\text{hypothesis})$ or $P(x|C_i)$).
   • This likelihood model is usually learned or estimated from known training samples.
2. Intuitive:
   • Compared to “black-box” classifiers like SVM or Neural Networks (ANN), Bayesian classifiers are often more intuitive.
   • The results can be more easily interpreted by humans.
   • The core idea directly reflects the process of updating prior beliefs using new evidence via Bayes’ theorem.

---