Algorithms from ScratchOpen in Colab
ML project loop
Data·Hypothesis space·Objective·Optimization·Evaluation·Deployment feedback

Algorithms from Scratch

Reaching for sklearn.LinearRegression().fit(X, y) is fast, but it hides everything interesting: how the weights are solved, what breaks when features are collinear, and why the loss landscape looks the way it does. Implementing algorithms from scratch forces you to confront every assumption. It is also the standard bar for ML engineering interviews.

This lesson walks through five algorithms (linear regression, logistic regression, K-Means, decision trees, and gradient boosting) at the level of NumPy operations. Each implementation is short enough to hold in your head and complete enough to train on real data.


Why implement from scratch?

Library APIs optimise for convenience. They handle edge cases silently, default hyperparameters for you, and abstract away the numerical details that bite you in production. Scratch implementations:

  • Make the computational complexity explicit — you see every loop and matrix multiply.
  • Surface hidden assumptions — e.g. linear regression assumes XTXX^TX is invertible.
  • Expose numerical pitfalls — log of zero in cross-entropy, division by cluster size in K-Means.
  • Build the mental model needed to debug library behaviour — if sklearn's coefficients look wrong, knowing the normal equation tells you where to look.
  • Are essential for ML engineering interviews at most top-tier companies.

1. Linear regression from scratch

Linear regression fits a weight vector θ∈Rd\theta \in \mathbb{R}^d that minimises mean squared error over mm training examples.

Normal equation

Setting ∂L/∂θ=0\partial L / \partial \theta = 0 for L=1m∥Xθ−y∥2L = \frac{1}{m}\|X\theta - y\|^2 gives the closed-form solution:

θ=(XTX)−1XTy\theta = (X^TX)^{-1}X^Ty

This is exact and requires no learning rate. For nn features it costs O(n3)O(n^3) to invert XTXX^TX, so gradient descent is preferred when nn is large.

Gradient descent update

θ←θ−α⋅XT(Xθ−y)m\theta \leftarrow \theta - \alpha \cdot \frac{X^T(X\theta - y)}{m}

Each step moves θ\theta in the direction that most reduces the residual Xθ−yX\theta - y.

Starting from the MSE loss L=1m∥Xθ−y∥2L = \frac{1}{m}\|X\theta - y\|^2 and taking ∂L/∂θ=0\partial L / \partial \theta = 0 directly yields the normal equation. Gradient descent is just iterating ∂L/∂θ\partial L / \partial \theta repeatedly — the two views are the same geometry seen at different speeds.

Pitfall: singular XTXX^TX

If two features are perfectly collinear, XTXX^TX is singular and cannot be inverted. The fix is ridge regularisation:

θ=(XTX+λI)−1XTy\theta = (X^TX + \lambda I)^{-1}X^Ty

Adding λI\lambda I guarantees positive-definiteness for any λ>0\lambda > 0.

Python
import numpy as np

class LinearRegressionScratch:
    def fit(self, X, y, lam=1e-4):
        # Add bias column
        X = np.c_[np.ones(len(X)), X]
        # Ridge normal equation
        A = X.T @ X + lam * np.eye(X.shape[1])
        self.theta = np.linalg.solve(A, X.T @ y)

    def predict(self, X):
        X = np.c_[np.ones(len(X)), X]
        return X @ self.theta

# Usage
# model = LinearRegressionScratch()
# model.fit(X_train, y_train)
# preds = model.predict(X_test)

np.linalg.solve(A, b) is numerically safer than np.linalg.inv(A) @ b — it uses LU decomposition internally and avoids explicitly forming the inverse.


2. Logistic regression from scratch

Logistic regression models the probability that y=1y = 1 given features xx:

y^=σ(Xθ),σ(z)=11+e−z\hat{y} = \sigma(X\theta), \quad \sigma(z) = \frac{1}{1 + e^{-z}}

Binary cross-entropy loss

L=−1m∑i=1m[y(i)log⁡y^(i)+(1−y(i))log⁡(1−y^(i))]L = -\frac{1}{m} \sum_{i=1}^{m} \left[ y^{(i)} \log \hat{y}^{(i)} + (1 - y^{(i)}) \log(1 - \hat{y}^{(i)}) \right]

Gradient

∂L∂θ=XT(σ(Xθ)−y)m\frac{\partial L}{\partial \theta} = \frac{X^T(\sigma(X\theta) - y)}{m}

The gradient has the same form as linear regression — the only difference is that the residual passes through the sigmoid. This is not a coincidence: both are members of the generalised linear model family.

Decision boundary

At the boundary, y^=0.5\hat{y} = 0.5, which means σ(θTx)=0.5\sigma(\theta^T x) = 0.5, which means θTx=0\theta^T x = 0. The decision boundary is a hyperplane in feature space. Logistic regression is inherently linear — non-linear boundaries require feature engineering or a kernel.

Python
class LogisticRegressionScratch:
    def __init__(self, lr=0.1, epochs=1000):
        self.lr = lr
        self.epochs = epochs

    @staticmethod
    def _sigmoid(z):
        return 1 / (1 + np.exp(-np.clip(z, -500, 500)))

    def fit(self, X, y):
        X = np.c_[np.ones(len(X)), X]
        self.theta = np.zeros(X.shape[1])
        m = len(y)
        for _ in range(self.epochs):
            y_hat = self._sigmoid(X @ self.theta)
            grad = X.T @ (y_hat - y) / m
            self.theta -= self.lr * grad

    def predict_proba(self, X):
        X = np.c_[np.ones(len(X)), X]
        return self._sigmoid(X @ self.theta)

    def predict(self, X, threshold=0.5):
        return (self.predict_proba(X) >= threshold).astype(int)

Note np.clip(z, -500, 500) inside sigmoid — without it, exp(-z) overflows to inf for large negative zz, producing a NaN gradient.


3. K-Means from scratch

Algorithm

  1. Initialise KK centroids (random sample or K-means++).
  2. Assign each point to the nearest centroid: c(i)=arg⁡min⁡k∥x(i)−μk∥2c^{(i)} = \arg\min_k \|x^{(i)} - \mu_k\|^2.
  3. Update each centroid to the mean of its assigned points: μk=1∣Ck∣∑i∈Ckx(i)\mu_k = \frac{1}{|C_k|}\sum_{i \in C_k} x^{(i)}.
  4. Repeat steps 2–3 until centroids move less than ε\varepsilon between iterations.

K-means++ initialisation

Random initialisation can produce poor clusters (all centroids near each other). K-means++ selects each new centroid with probability proportional to the squared distance from the nearest existing centroid:

P(x(i) chosen)∝min⁡k∥x(i)−μk∥2P(x^{(i)} \text{ chosen}) \propto \min_k \|x^{(i)} - \mu_k\|^2

This spreads initial centroids across the data, typically converging faster and to a better solution.

Complexity

Each iteration is O(n⋅K⋅d)O(n \cdot K \cdot d) where nn is number of points, KK is number of clusters, and dd is dimensionality. Total cost: O(n⋅K⋅d⋅iterations)O(n \cdot K \cdot d \cdot \text{iterations}).

Edge case: empty cluster

If a centroid has no assigned points (can happen with poor initialisation), reintialise it to a random data point. Ignoring this produces NaN centroids.


4. Decision tree from scratch

Gini impurity

For a node containing mm samples across CC classes, with pkp_k being the fraction of class kk:

G=1−∑k=1Cpk2G = 1 - \sum_{k=1}^{C} p_k^2

G=0G = 0 means the node is pure (all one class). GG is maximised when all classes are equally represented.

Information gain

The quality of a split is the reduction in impurity:

IG=G(parent)−∑childnchildnparent⋅G(child)IG = G(\text{parent}) - \sum_{\text{child}} \frac{n_{\text{child}}}{n_{\text{parent}}} \cdot G(\text{child})

The algorithm exhaustively evaluates every feature and every threshold, picking the split with highest information gain.

Stopping criteria

A node becomes a leaf (stops splitting) when any of the following hold:

  • max_depth reached — prevents overfitting.
  • min_samples_split: node has fewer than this many samples.
  • min_impurity_decrease: best information gain is below threshold.
  • Pure leaf: all samples in the node share the same class label (G=0G = 0).

Complexity

Finding the best split at one node requires sorting each feature: O(d⋅nlog⁡n)O(d \cdot n \log n). For a balanced tree of depth DD, total cost is O(d⋅nlog⁡n⋅D)O(d \cdot n \log n \cdot D), where D≤log⁡2nD \leq \log_2 n in the balanced case.


5. Gradient boosting from scratch (conceptual)

Gradient boosting builds an ensemble of trees sequentially, each fitting the residuals of all previous trees.

The update rule

y^t=y^t−1+η⋅ht(x)\hat{y}_t = \hat{y}_{t-1} + \eta \cdot h_t(x)

where hth_t is a shallow tree fitted to the negative gradient of the loss evaluated at the current predictions.

For MSE loss L=12(y−y^)2L = \frac{1}{2}(y - \hat{y})^2, the negative gradient is simply y−y^y - \hat{y} — the residual. Each new tree literally fits the errors of the previous ensemble.

Why this works

This is functional gradient descent in prediction space. Standard gradient descent moves parameters θ\theta in the direction −∂L/∂θ-\partial L / \partial \theta. Gradient boosting moves the prediction function y^\hat{y} in the direction −∂L/∂y^-\partial L / \partial \hat{y}, using a tree as the step.

For arbitrary differentiable losses (Huber, log-loss, quantile), you simply substitute the appropriate negative gradient as the target for each tree. This is how XGBoost handles its many loss functions — only the gradient and Hessian computation changes.

Key hyperparameters

  • η\eta (learning rate / shrinkage): smaller values require more trees but generalise better.
  • max_depth of each tree: shallower trees are higher-bias, lower-variance base learners (depth 3–6 is typical).
  • n_estimators: number of trees; increase until validation loss plateaus.
  • subsample: fraction of training data sampled per tree — adds stochasticity, reduces overfitting.

Key takeaways

  • The normal equation gives a closed-form solution for linear regression; ridge regularisation fixes the singular-matrix problem when features are collinear.
  • Logistic regression shares its gradient form with linear regression because both belong to the generalised linear model family; only the link function changes.
  • K-means++ initialisation dramatically improves convergence by spreading initial centroids; always handle the empty-cluster edge case.
  • Decision trees exhaustively search all feature-threshold pairs; Gini impurity and information gain are nearly equivalent in practice but Gini is faster to compute.
  • Gradient boosting is functional gradient descent — each tree fits the negative gradient of the loss, making it trivially extensible to any differentiable objective.
  • Implementing algorithms from scratch reveals the numerical pitfalls (log-of-zero, singular matrices, NaN centroids) that library APIs silently handle — essential knowledge for debugging production models.

Exercises

Exercise

When implementing linear regression via the normal equation θ = (XᵀX)⁻¹Xᵀy, when does this fail, and what is the fix?

Need a hint?

What matrix property is required for the inverse to exist?

Exercise

K-Means is initialized with K random centroids. Sometimes it converges to a poor solution. What does K-Means++ do differently, and why does it help?

Need a hint?

K-Means++ spreads out the initial centroids. Why is spreading out good?

Exercise

A decision tree node has 10 samples: 6 class A and 4 class B. What is the Gini impurity, and what does a value of 0 mean?

Need a hint?

Gini = 1 − Σ p_k². For binary: 1 − (p_A² + p_B²).


Related concepts

Concept neighbourhood

How this concept connects — click any node to jump there, or explore the whole concept map.

Builds onRelated
Algorithms from ScratchLinear & Logistic Regress…Neural NetworksModel Evaluation & Valida…Gradient DescentLinear RegressionDecision TreesThe CUDA Programming Model