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

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.

# 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.

# 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.

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.

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.

# 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.

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.

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.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}