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 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 that minimises mean squared error over training examples.
Normal equation
Setting for gives the closed-form solution:
This is exact and requires no learning rate. For features it costs to invert , so gradient descent is preferred when is large.
Gradient descent update
Each step moves in the direction that most reduces the residual .
Starting from the MSE loss and taking directly yields the normal equation. Gradient descent is just iterating repeatedly — the two views are the same geometry seen at different speeds.
Pitfall: singular
If two features are perfectly collinear, is singular and cannot be inverted. The fix is ridge regularisation:
Adding guarantees positive-definiteness for any .
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 given features :
Binary cross-entropy loss
Gradient
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, , which means , which means . The decision boundary is a hyperplane in feature space. Logistic regression is inherently linear — non-linear boundaries require feature engineering or a kernel.
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 , producing a NaN gradient.
3. K-Means from scratch
Algorithm
- Initialise centroids (random sample or K-means++).
- Assign each point to the nearest centroid: .
- Update each centroid to the mean of its assigned points: .
- Repeat steps 2–3 until centroids move less than 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:
This spreads initial centroids across the data, typically converging faster and to a better solution.
Complexity
Each iteration is where is number of points, is number of clusters, and is dimensionality. Total cost: .
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 samples across classes, with being the fraction of class :
means the node is pure (all one class). is maximised when all classes are equally represented.
Information gain
The quality of a split is the reduction in impurity:
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 ().
Complexity
Finding the best split at one node requires sorting each feature: . For a balanced tree of depth , total cost is , where 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
where is a shallow tree fitted to the negative gradient of the loss evaluated at the current predictions.
For MSE loss , the negative gradient is simply — 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 in the direction . Gradient boosting moves the prediction function in the direction , 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
- (learning rate / shrinkage): smaller values require more trees but generalise better.
max_depthof 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²).