Machine Learning and Pattern Classification

Module 1: Bayesian Decision Theory and Density Estimation

1.1 Bayesian Decision Theory Fundamentals

Classification can be framed as a probabilistic task governed by the world's fixed probability distribution $p(X, \Omega)$. The goal of Bayesian decision theory is to compute posterior class probabilities using prior and class-conditional probabilities via Bayes' Rule:

$$P(\omega_i \mid \boldsymbol{x}) = \frac{p(\boldsymbol{x} \mid \omega_i)P(\omega_i)}{p(\boldsymbol{x})}$$

To minimise the expected error (Bayes Error), the optimal strategy is the Maximum A-Posteriori (MAP) Decision:

$$\text{Predict } \omega^* = \arg \max_{\omega_1, \omega_2} \{P(\omega_1 \mid \boldsymbol{x}), P(\omega_2 \mid \boldsymbol{x})\}$$

If decisions carry differing costs, the framework extends to risk minimisation using a loss function $\lambda(\alpha_i, \omega_j)$, where $\alpha_i$ is the predicted action and $\omega_j$ is the true class.

1.2 Density Estimation

To perform MAP decisions, probability density functions (PDFs) are required for continuous variables. A common distribution is the Gaussian (Normal) Distribution:

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

For $d$ - dimensional feature spaces, the Multivariate Gaussian PDF is utilised, governed by a mean vector $\boldsymbol{\mu}$ and a covariance matrix $\boldsymbol{\Sigma}$:

$$p(\boldsymbol{x}) = \frac{1}{(2\pi)^{d/2}|\boldsymbol{\Sigma}|^{1/2}} e^{-\frac{1}{2}(\boldsymbol{x}-\boldsymbol{\mu})^T \boldsymbol{\Sigma}^{-1}(\boldsymbol{x}-\boldsymbol{\mu})}$$

The Naïve Bayes Classifier simplifies density estimation by assuming feature independence within a class, thus side-stepping the curse of dimensionality and reducing parameters to $O(nd)$. In Naïve Bayes, the MAP classification decision boundary becomes:

$$\omega^* = \arg \max_{\omega_i} P(\omega_i) \prod_j P(x_j \mid \omega_i)$$

Kernel Density Estimation (KDE) provides a non-parametric alternative, computing densities based on local training point distances:

$$\hat{p}(\boldsymbol{x}) \propto \frac{1}{N} \sum_{i=1}^N K(\boldsymbol{x}_i, \boldsymbol{x})$$

Module 2: Machine Learning Algorithms and Evaluation

2.1 Model Selection and Overfitting

Classifiers are evaluated empirically to avoid overfitting—a scenario where a model memorises training data noise instead of generalisable patterns. Iterative model simplification (pruning) and Cross-Validation are vital techniques to balance the Bias-Variance trade-off. Classifier results are commonly visualised using Confusion Matrices and analysed in ROC Space.

2.2 Core Algorithms

Decision Trees (ID3): ID3 builds trees by splitting training sets using the Information Gain $IG(A_i)$ metric to find the most discriminative features. For numeric features, binary tests $A \le t$ are evaluated to find the best split point $t$.

Support Vector Machines (SVMs): SVMs perform linear classification by maximising the margin between classes, formulated as an optimisation problem:

$$\text{Minimise } \|\boldsymbol{w}\|^2 \quad \text{subject to } y_i(\boldsymbol{w} \cdot \boldsymbol{x}_i + b) \ge 1$$

For non-linearly separable data, SVMs employ the Kernel Trick to implicitly map inputs to high-dimensional spaces. A classic kernel is the Polynomial Kernel:

$$K(\boldsymbol{x}, \boldsymbol{y}) = (\boldsymbol{x} \cdot \boldsymbol{y} + c)^k$$

2.3 Improving Results

Performance can be optimised via feature construction, grid/random parameter search, and Ensemble Methods. Methods like Stacking train meta-classifiers on the predictions of diverse base learners, while Boosting sequentially trains classifiers $c_t$ on datasets $\mathcal{D}_t$ iteratively reweighted based on the errors $\varepsilon_{t-1}$ of the previous models.

Module 3: Neural Networks and Deep Learning

3.1 Artificial Neural Networks (ANNs)

ANNs map inputs $X$ to predictions $Y$ via interconnected units (neurons). A single unit computes a weighted sum (net input) and applies a non-linear activation function $f$:

$$net_i = \sum_j w_{ij}x_j$$
$$y_i = f(net_i)$$

Training involves minimising a loss function $E$, such as the Sum Squared Error for regression:

$$E = \frac{1}{2} \sum_{\boldsymbol{x}_i \in \mathcal{D}} (y_i - \hat{y}(\boldsymbol{x}_i))^2$$

Optimization utilizes Gradient Descent:

$$\boldsymbol{\theta}_{k+1} = \boldsymbol{\theta}_k - \eta \frac{\partial E}{\partial \boldsymbol{\theta}_k}$$

Error Back-propagation: The gradient of the error is passed backwards through the layers. For an output unit $j$, the error signal $\delta_j$ is calculated directly. For a hidden unit $j$, it is computed using its successors $S_j$ via the chain rule:

$$\delta_j = \frac{\partial E}{\partial net_j} = \sum_{k \in S_j} \delta_k w_{jk} f'_j(net_j)$$

3.2 Deep Architectures and Classification

For binary classification, the Logistic (Sigmoid) function provides pseudo-probabilities mapped to Binary Cross-Entropy loss:

$$\hat{y} = \text{sigm}(z) = \frac{1}{1+e^{-z}}$$
$$E(\boldsymbol{x}_i) = -y_i \log \hat{y}_i - (1-y_i)\log(1-\hat{y}_i)$$

For multi-class ($k$-class) scenarios, networks use the Softmax function alongside Categorical Cross-Entropy:

$$\hat{y}_i = \text{softmax}(z_i) = \frac{e^{z_i}}{\sum_{j=1}^k e^{z_j}}$$
$$E(\boldsymbol{x}_i) = -\sum_{j=1}^k y_j(\boldsymbol{x}_i) \log \hat{y}_j(\boldsymbol{x}_i)$$

Deep learning composes multiple non-linear functions $\boldsymbol{y} = (f_{W_n, b_n} \circ \dots \circ f_{W_1, b_1})(\boldsymbol{x})$. Common network variants include:

• Convolutional Neural Networks (CNNs): Utilise convolution and pooling layers for spatial/temporal data, providing translational invariance.
• Recurrent Neural Networks (RNNs/GRUs): Designed for sequential data. A GRU cell updates its hidden state $h_t$ using gates:
  $$h_t = (1 - z_t) \odot h_{t-1} + z_t \odot \tilde{h}_t$$

Deep learning is regulated using techniques like Dropout, which randomly zeroes out hidden units during training to prevent co-adaptation, and data augmentation methods (e.g., noise addition, frequency filtering) to expand datasets synthetically.

Module 4: Unsupervised Learning

4.1 Clustering

Unsupervised learning models the inherent descriptive or generative structure of unlabelled datasets $\mathcal{D} = \{\boldsymbol{x}_i\}$. The $k$-means algorithm provides distance-based clustering into disjoint categories, minimising the Mean Quantisation Error (MQE).

4.2 Statistical Data Modelling

Gaussian Mixture Models (GMMs) represent data as probabilistically generated from a weighted mixture of $k$ distinct distributions:

$$p(\boldsymbol{x}) = \sum_{i=1}^k w_i \cdot p_i(\boldsymbol{x})$$

Here, $w_i = P(C_i)$ represents the mixture coefficient of the $i$ -th component. GMMs are trained using the Expectation-Maximisation (E-M) algorithm to find parameters $\boldsymbol{\theta}^* = \{w_i, \boldsymbol{\mu}_i, \boldsymbol{\Sigma}_i\}$ that maximise the likelihood of generating the observed data:

$$\boldsymbol{\theta}^* = \arg \max_{\boldsymbol{\theta}} \prod_{\boldsymbol{x}_i \in \mathcal{D}} p(\boldsymbol{x}_i \mid \mathcal{M}_{\boldsymbol{\theta}})$$