# Classical Machine Learning Algorithms in the Maths-CS-AI Compendium: Naive Bayes, SVM, Decision Trees, and Ensemble Methods

> Explore classical machine learning algorithms like Naive Bayes, SVM, decision trees, and ensemble methods in the Maths-CS-AI Compendium. Master foundational ML concepts with rigorous mathematical explanations.

- Repository: [Henry Ndubuaku/maths-cs-ai-compendium](https://github.com/HenryNdubuaku/maths-cs-ai-compendium)
- Tags: deep-dive
- Published: 2026-07-18

---

**The HenryNdubuaku/maths-cs-ai-compendium repository provides mathematically rigorous coverage of eight foundational classical machine learning algorithms, spanning probabilistic classifiers, tree-based methods, ensemble techniques, and clustering algorithms.**

This open-source compendium delivers a theoretically grounded exploration of classical machine learning within `chapter 06 - machine learning/01. classical machine learning.md`. The material distinguishes between generative and discriminative modeling paradigms while providing architectural insights into algorithm design, optimization objectives, and practical implementation patterns.

## Naive Bayes Classifiers

The compendium covers **Naive Bayes** as a family of generative supervised learning algorithms that apply Bayes' theorem with a conditional independence assumption between features. The repository details three primary likelihood variants:

- **Multinomial Naive Bayes** – Models discrete count data, ideal for text classification and spam filtering
- **Gaussian Naive Bayes** – Handles continuous features by assuming normally distributed likelihoods
- **Bernoulli Naive Bayes** – Optimized for binary feature vectors and presence/absence data

In practice, these classifiers learn the joint distribution \(P(x, y)\) rather than directly estimating \(P(y|x)\). This probabilistic foundation makes them particularly effective for high-dimensional sparse data such as document-term matrices.

```python

# Multinomial Naive Bayes for text classification

from sklearn.feature_extraction.text import CountVectorizer
from sklearn.naive_bayes import MultinomialNB

docs = ["spam cheap meds", "meeting schedule", "win lottery now", "project deadline"]
y = [1, 0, 1, 0]  # 1 = spam, 0 = ham

X = CountVectorizer().fit_transform(docs)
clf = MultinomialNB().fit(X, y)
print(clf.predict(X))

```

## Decision Trees

**Decision Trees** appear in the compendium as discriminative models that recursively partition feature space through binary splits. The source material explains how the algorithm selects split points by maximizing impurity reduction using either **Gini impurity** (\(1-\sum_k p_k^2\)) or **entropy** (\(-\sum_k p_k\log_2 p_k\)).

Each internal node represents a feature-threshold test, while leaf nodes contain class predictions (classification) or mean values (regression). This greedy, top-down induction creates highly interpretable models suitable for tabular data analysis and rapid prototyping.

```python

# Decision Tree with Gini criterion

from sklearn.tree import DecisionTreeClassifier
import numpy as np

X = np.random.rand(100, 4)
y = (X[:, 0] + X[:, 1] > 1).astype(int)
tree = DecisionTreeClassifier(criterion="gini", max_depth=3).fit(X, y)
print(tree.predict(X[:5]))

```

## Ensemble Methods

The compendium dedicates significant coverage to **ensemble methods**, distinguishing between variance-reduction and bias-reduction strategies through two primary architectures:

### Random Forests (Bagging)

**Random Forests** implement bootstrap aggregating (bagging) by training multiple decision trees on bootstrap samples of the training data. Each split considers only a random subset of features (\(\sqrt{d}\) for classification), forcing diversity among base learners. Predictions aggregate through majority voting (classification) or averaging (regression), yielding robust off-the-shelf classifiers that handle high-dimensional data without overfitting.

```python
from sklearn.ensemble import RandomForestClassifier

rf = RandomForestClassifier(n_estimators=200, max_features="sqrt").fit(X, y)
print(rf.score(X, y))

```

### Gradient Boosting

**Gradient Boosting** machines take a sequential approach, adding weak learners that fit the negative gradient (residual errors) of the current ensemble's loss function. The repository specifically contrasts this with **AdaBoost**, which reweights misclassified examples rather than fitting residuals. Both methods reduce bias through iterative error correction, forming the algorithmic foundation of modern implementations like XGBoost and LightGBM.

```python
from sklearn.ensemble import GradientBoostingClassifier

gb = GradientBoostingClassifier(n_estimators=100, learning_rate=0.1).fit(X, y)
print(gb.predict(X[:5]))

```

## Support Vector Machines (SVM)

The **Support Vector Machines** section formulates classification as a convex quadratic optimization problem seeking the **maximum-margin hyperplane** that separates classes with maximal geometric distance. The compendium covers critical extensions including:

- **Soft-margin SVM** – Introduces slack variables to handle non-separable data through regularization parameter \(C\)
- **Kernel Trick** – Implicitly maps inputs to high-dimensional spaces using kernel functions (RBF, polynomial, linear) without explicit feature transformation

This kernel method leverages the fact that SVM optimization depends only on inner products between samples, enabling non-linear decision boundaries while maintaining computational tractability.

```python

# SVM with RBF kernel

from sklearn.svm import SVC

svm = SVC(kernel="rbf", C=1.0, gamma="scale").fit(X, y)
print(svm.predict(X[:5]))

```

## Unsupervised Clustering Algorithms

Beyond supervised learning, the repository examines two fundamental clustering paradigms:

### K-Means

**K-Means** minimizes within-cluster sum of squares (inertia) through an alternating two-step procedure: assigning points to nearest centroids and recomputing centroids as cluster means. The compendium notes the use of **K-Means++** for smart initialization to accelerate convergence and improve solution quality.

```python
from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs

X, _ = make_blobs(n_samples=300, centers=4, random_state=42)
kmeans = KMeans(n_clusters=4, init="k-means++").fit(X)
print(kmeans.labels_[:10])

```

### Gaussian Mixture Models

**Gaussian Mixture Models (GMM)** generalize K-Means by modeling data as a weighted sum of multivariate Gaussian distributions. Learned via the **Expectation-Maximization (EM)** algorithm, GMMs provide soft cluster assignments (posterior probabilities) and support full covariance matrices, enabling elliptical cluster shapes rather than spherical regions.

```python
from sklearn.mixture import GaussianMixture

gmm = GaussianMixture(n_components=4, covariance_type="full").fit(X)
print(gmm.predict(X[:5]))

```

## Summary

- **Probabilistic vs. Discriminative**: The compendium contrasts generative models (Naive Bayes) that learn \(P(x, y)\) with discriminative approaches (SVM, Decision Trees) that directly estimate \(P(y|x)\).
- **Impurity Optimization**: Decision Trees utilize Gini impurity or entropy to maximize information gain at each split.
- **Ensemble Strategies**: Bagging (Random Forests) reduces variance through parallel training, while boosting (Gradient Boosting) reduces bias through sequential error correction.
- **Kernel Methods**: SVMs leverage the kernel trick to achieve non-linear separability without explicit high-dimensional mapping.
- **Clustering Foundations**: K-Means provides hard clustering via distance minimization, while GMMs offer probabilistic soft clustering through Gaussian components.

## Frequently Asked Questions

### What is the difference between bagging and boosting in ensemble methods?

**Bagging** (Bootstrap Aggregating) trains multiple models independently on random subsets of data, combining predictions through averaging or voting to reduce variance. **Boosting** trains models sequentially, with each new learner focusing on errors made by previous ensemble members, thereby reducing bias.

### When should I choose Naive Bayes over SVM?

Select **Naive Bayes** when working with high-dimensional sparse data (like text classification) where the conditional independence assumption holds reasonably well, or when you need extremely fast training and prediction with minimal hyperparameter tuning. Choose **SVM** when you have smaller, dense datasets requiring complex decision boundaries, or when you need guaranteed global optima through convex optimization.

### How does the kernel trick work in Support Vector Machines?

The **kernel trick** exploits the fact that SVM optimization depends solely on inner products between training samples. By replacing these inner products with a **kernel function** (such as RBF \(K(x,y) = \exp(-\gamma\|x-y\|^2\)), polynomial, or linear), the algorithm implicitly computes similarities in a high-dimensional feature space without explicitly performing the computationally expensive transformation.

### What distinguishes Gaussian Mixture Models from K-Means clustering?

While **K-Means** assigns each point to exactly one cluster (hard clustering) based on Euclidean distance to centroids, **Gaussian Mixture Models** compute the probability that each point belongs to each component (soft clustering). GMMs model clusters as multivariate Gaussians with full covariance matrices, accommodating elliptical distributions, whereas K-Means assumes spherical clusters of equal size.