Models from scratch

1.Standardize features

Write standardize(train, test) for numeric feature rows. For each column, compute the mean and the population standard deviation (divide by n) on train only. Replace each value x in both sets with (x − mean) / std. A column whose std is 0 uses std 1. Return [train_scaled, test_scaled].

2.Polynomial features

Write polynomial_features(X, degree) so a linear model can fit curves. For each feature x of a row, in order, output x, x², …, x^degree, so the row [a, b] with degree 2 becomes [a, a², b, b²]. Do not add cross terms or a constant column. Return the expanded rows.

3.Linear model predictions

Write predict_linear(X, w, b) for a linear regression model. For each row x of X, the prediction is w · x + b, where w · x is the sum of w[j] * x[j] over the features. Return the predictions in row order.

4.Gradients of squared error

Write linear_gradients(X, y, w, b) for mean squared error. For each row, the residual is r = (w · x + b) − y. Over n rows, the gradients are dw[j] = (2 / n) · Σ r · x[j] and db = (2 / n) · Σ r. Return [dw, db].

5.Train linear regression

Write fit_linear(X, y, lr, epochs) to train linear regression with full-batch gradient descent. Start with w as zeros and b = 0. Each epoch, with r = (w · x + b) − y for every row, compute dw[j] = (2 / n) · Σ r · x[j] and db = (2 / n) · Σ r, then set w[j] -= lr · dw[j] and b -= lr · db. Return [w, b].

6.Least-squares line

Write fit_line(xs, ys) to fit y = slope · x + intercept by least squares, without gradient descent. With means x̄ and ȳ, slope = Σ (x − x̄)(y − ȳ) / Σ (x − x̄)², and intercept = ȳ − slope · x̄. If every x is the same, use slope 0.0 and intercept ȳ. Return [slope, intercept].

7.Sigmoid that never overflows

Write sigmoid(z) = 1 / (1 + e^(−z)) for a logistic model. It must work for any float, including z = −1000 and z = 1000. In Python, math.exp raises OverflowError above about 709, so the obvious one-liner crashes on a large negative z.

8.Logistic predictions

Write predict_logistic(X, w, b, threshold) for a trained binary classifier. For each row x, the probability is sigmoid(w · x + b), and the label is 1 when that probability is at least threshold, else 0. Weights can be large, so the sigmoid must not overflow. Return [probabilities, labels].

9.Log loss

Write log_loss(y_true, probs) for a binary classifier, with labels 0 or 1 and predicted probabilities of class 1. First clip each probability into [1e-15, 1 − 1e-15] so the log never sees 0. Return the mean over examples of −(y · ln p + (1 − y) · ln(1 − p)).

10.Train a binary classifier

Write fit_logistic(X, y, lr, epochs) to train logistic regression with labels 0 and 1, using full-batch gradient descent. Start w at zeros and b = 0. Each epoch, with p = sigmoid(w · x + b) for every row, compute dw[j] = mean of (p − y) · x[j] and db = mean of (p − y), then subtract lr times each. Return [w, b].

11.Logistic regression with L2

Write fit_logistic_l2(X, y, lr, epochs, lam): logistic regression with L2 regularization. Start w at zeros and b = 0. Each epoch, with p = sigmoid(w · x + b) for every row, compute dw[j] = mean of (p − y) · x[j] + lam · w[j] and db = mean of (p − y). The bias is not regularized. Subtract lr times each. Return [w, b].

12.Logistic regression with SGD

Write sgd_logistic(X, y, lr, epochs) to train logistic regression with stochastic gradient descent and no shuffling. Start w at zeros and b = 0. Each epoch, visit rows in order and update right after each row: p = sigmoid(w · x + b), then w[j] -= lr · (p − y) · x[j] and b -= lr · (p − y). Return [w, b].

13.Perceptron

Write perceptron(X, y, epochs) with labels −1 and 1. Start w at zeros and b = 0. Each epoch, visit rows in order; when y · (w · x + b) ≤ 0, count a mistake and set w[j] += y · x[j] and b += y. Stop early after an epoch with no mistakes. Return [w, b, mistakes], where mistakes is the total over all epochs.

14.Softmax that never overflows

Write softmax(logits) for a multiclass model: each output is e^(logit) divided by the sum of e^(logit) over all logits. It must work for logits like [1000, 1000], where math.exp overflows. Return the probabilities in the same order.

15.Train a softmax classifier

Write fit_softmax(X, y, num_classes, lr, epochs) with full-batch gradient descent. W has num_classes rows of zeros and b is zeros. Each epoch, for each row take p = softmax of W[k] · x + b[k] over k. With g = p[k] − 1 when y is k, else p[k], dW[k][j] is the mean of g · x[j] and db[k] the mean of g. Subtract lr times each. Return [W, b].

16.One-vs-rest predictions

Write predict_one_vs_rest(X, models) for a multiclass model built from binary ones. models[k] is [w, b], a linear model for class k against the rest. For each row x, predict the class whose score w · x + b is highest, ties going to the lower class. Return the classes in row order.

17.Naive Bayes text classifier

Write naive_bayes_predict(docs, labels, doc, alpha). Each doc is a list of words. Score class c as ln(docs in c / all docs) plus, for each word of doc seen in training, ln((count of the word in c + alpha) / (total words in c + alpha · V)), with V the training vocabulary size. Skip unseen words. Return the top class, ties to the smaller label.

18.Gaussian naive Bayes

Write gaussian_nb_predict(X, y, x) for numeric features. For each class, take each feature's mean and population variance over that class's rows, and add 1e-9 to the variance. Score a class as ln(prior) plus, over features, −0.5 · ln(2π · var) − (x − mean)² / (2 · var). Return the top class, ties to the smaller label.

19.Gini impurity

Write gini(labels) for a decision tree. With p the share of each distinct label, the impurity is 1 − Σ p². A pure node scores 0.0, and so does an empty list. Labels can be numbers or strings.

20.Best decision-tree split

Write best_split(X, y) for a decision tree. For each feature, try thresholds halfway between consecutive distinct sorted values; rows with x[feature] ≤ threshold go left. A split scores the size-weighted mean of the two sides' Gini impurity (1 − Σ p²). Return the lowest-scoring [feature, threshold], ties to the lower feature then threshold, or None if none exists.

21.Grow a decision tree

Write build_tree(X, y, max_depth). A node is a leaf {"label": majority label, ties to the smaller label} when its labels are all equal, its depth is max_depth (the root is 0), or no split exists. Otherwise split as best_split does: Gini, midpoint thresholds, ≤ goes left, ties to the lower feature then threshold. Return {"feature", "threshold", "left", "right"} for a split.

22.Predict with a decision tree

Write tree_predict(tree, X). A tree is either a leaf {"label": y} or a node {"feature": f, "threshold": t, "left": subtree, "right": subtree}. Starting at the root, a row goes left when row[f] ≤ t and right otherwise, until it reaches a leaf. Return the leaf labels in row order.

23.Ensemble majority vote

Write majority_vote(predictions) to combine the models of a bagged ensemble. predictions[m][i] is model m's label for example i, and every model predicts every example. For each example, return the label most models chose, ties going to the smaller label.

24.K-means to convergence

Write kmeans(points, centroids, max_iters), max_iters ≥ 1. Each iteration, assign every point to its nearest centroid by squared Euclidean distance, ties to the lower index. Stop if the assignments match the previous iteration's; otherwise move each centroid to the mean of its points, leaving an empty one in place. Return [centroids, assignments] after stopping or max_iters iterations.

25.Dense layer forward pass

Write dense_forward(X, W, b, activation) for one neural-network layer over a batch. W[i][j] is the weight from input i to output j, and b[j] the bias of output j. For each row x, output j is Σ x[i] · W[i][j] + b[j]. When activation is "relu", replace negatives with 0; when it is "linear", leave them. Return the outputs per row.

26.Two-layer network forward pass

Write mlp_forward(x, W1, b1, W2, b2) for a binary classifier with one hidden layer. Hidden unit j is h[j] = relu(Σ x[i] · W1[i][j] + b1[j]). The output is p = sigmoid(Σ h[j] · W2[j] + b2), where W2 is a list and b2 a number. The sigmoid must not overflow. Return p.

27.Backprop one training step

Write mlp_step(x, y, params, lr): one SGD step on one example for params {"W1", "b1", "W2", "b2"}. Forward: z[j] = Σ x[i]·W1[i][j] + b1[j], h = relu(z), p = sigmoid(h · W2 + b2). Backward: d = p − y; W2[j] and b2 get d·h[j] and d; g[j] = d·W2[j] if z[j] > 0 else 0; W1[i][j] and b1[j] get g[j]·x[i] and g[j]. Subtract lr × each gradient.

28.Train and score a classifier

Write train_and_score(train_X, train_y, test_X, test_y, lr, epochs). Standardize each column with the train mean and population std (std 0 counts as 1). Train logistic regression from zeros by full-batch gradient descent: dw[j] = mean (p − y)·x[j], db = mean (p − y). Predict 1 when p ≥ 0.5. Return the share of test rows predicted right.