AI.Cruz - Learn AI Through Interactive Visualizations

MACHINE LEARNING

Multiclass Classification Strategies

Three ways to extend binary classifiers to K classes: One-vs-Rest (K classifiers), One-vs-One (K(K-1)/2 classifiers), and Softmax — which models all K classes natively with one set of parameters per class.

1One-vs-Rest (OvR) and One-vs-One (OvO)

The simplest approach is to decompose the K-class problem into binary subproblems. Both OvR and OvO reuse existing binary classifiers — no algorithm change required.

One-vs-Rest (OvR)

Train K classifiers. Classifier k treats class k as positive and all others as negative. At test time, run all K classifiers and predict the class with the highest score. K=10 (digits): 10 classifiers, each trained on all n samples.

One-vs-One (OvO)

Train K(K-1)/2 classifiers, one for every pair of classes. Each classifier is trained on only the two relevant classes. At test time, each classifier votes and the class with most votes wins. K=10: 45 classifiers, each trained on ~n/5 samples. Faster per classifier, more classifiers total.

OvR vs OvO tradeoff: OvR has class imbalance (one class vs. many). OvO avoids this but requires many more classifiers. For SVMs (which scale poorly with n), OvO is preferred because each classifier trains on fewer samples. For most other classifiers, OvR is simpler and just as good.

2Softmax Regression

Softmax extends logistic regression natively to K classes. Instead of one weight vector, we have a weight matrix W of shape (d × K) — one set of weights per class.

The raw score (logit) for class k is s_k(x) = W_k·x + b_k. The softmax function converts K logits into probabilities: P̂_k = exp(s_k(x)) / Σ_j exp(s_j(x)). All K probabilities sum to 1. The prediction is argmax_k P̂_k.

Logits
s = Wx + b, shape (K,). Raw scores before normalisation. Can be any real number — softmax maps them to (0,1).

Softmax
Exponentiates each logit, then normalises by the sum. Amplifies differences (exp is convex). Numerically: subtract max(s) before exp to prevent overflow.

Prediction
argmax of the probability vector. Equivalent to argmax of the logit vector — softmax is monotone, so the ordering is preserved.

3Cross-Entropy Loss and Gradient

To train softmax, we minimise cross-entropy, which penalises assigning low probability to the true class. It generalises binary cross-entropy to K classes.

J(W) = -(1/m) Σ_i Σ_k y_k⁽ⁱ⁾ log(ŷ_k⁽ⁱ⁾). Here y_k⁽ⁱ⁾ = 1 if sample i belongs to class k, 0 otherwise (one-hot). Because y is one-hot, the sum over k collapses to just -log(P̂_{true class}) per sample.

Clean gradient formula

The gradient of cross-entropy w.r.t. W_k is: ∇_w^kJ(W) = (1/m) Σ_i(ŷ_k⁽ⁱ⁾ - y_k⁽ⁱ⁾) x⁽ⁱ⁾. This is the same structure as logistic regression — error signal times input. In matrix form: ∇J = (1/m) Xᵀ(Υ̂ - Y), where Y is the one-hot matrix (m × K).

4OvR, OvO, and Softmax — When to Use Each

The right strategy depends on the classifier, dataset size, and whether you need calibrated probabilities.

Use OvR when
Your binary classifier already works well and you want the simplest extension. Handles large K efficiently (linear growth in classifiers).

Use OvO when
Using an SVM (training time scales with n²; OvO keeps n small). K is small (OvO's quadratic growth in classifiers is manageable for K ≤ 10).

Use Softmax when
You need proper probabilities across all classes, or when integrating into a neural network. It's the standard output layer for classification in deep learning.

Logistic Regression →Confusion Matrix →Precision, Recall and F1 →

OvR from scratch — softmax and cross-entropy with numpy

import numpy as np

np.random.seed(0)
n_per_class = 80
K = 3  # 3 classes

# Synthetic 2D, 3-class dataset
means = [[-2, 0], [2, 0], [0, 3]]
X_list, y_list = [], []
for k in range(K):
    X_list.append(np.random.randn(n_per_class, 2) + means[k])
    y_list.append(np.full(n_per_class, k))
X = np.vstack(X_list)
y = np.concatenate(y_list)
n = len(y)

def sigmoid(z):
    return 1 / (1 + np.exp(-np.clip(z, -50, 50)))

# One-vs-Rest: train K binary logistic classifiers
def train_ovr_binary(X, y_bin, lr=0.1, n_iter=500):
    w = np.zeros(X.shape[1] + 1)
    Xb = np.column_stack([np.ones(len(X)), X])
    for _ in range(n_iter):
        p = sigmoid(Xb @ w)
        grad = Xb.T @ (p - y_bin) / len(X)
        w -= lr * grad
    return w

weights = []
for k in range(K):
    y_bin = (y == k).astype(float)
    w_k = train_ovr_binary(X, y_bin)
    weights.append(w_k)

Xb = np.column_stack([np.ones(n), X])
scores = np.column_stack([sigmoid(Xb @ w) for w in weights])
y_pred = np.argmax(scores, axis=1)
acc = np.mean(y_pred == y)
print("OvR accuracy: " + str(round(acc * 100, 1)) + "%")

# Softmax from scratch
def softmax(logits):
    e = np.exp(logits - logits.max(axis=1, keepdims=True))
    return e / e.sum(axis=1, keepdims=True)

def train_softmax(X, y, K, lr=0.1, n_iter=500):
    n_obs, d = X.shape
    W = np.zeros((d + 1, K))
    Xb = np.column_stack([np.ones(n_obs), X])
    Y_oh = np.eye(K)[y]  # one-hot
    for _ in range(n_iter):
        P = softmax(Xb @ W)
        grad = Xb.T @ (P - Y_oh) / n_obs
        W -= lr * grad
    return W

W_sm = train_softmax(X, y, K)
Xb = np.column_stack([np.ones(n), X])
y_sm = np.argmax(softmax(Xb @ W_sm), axis=1)
print("Softmax accuracy: " + str(round(np.mean(y_sm == y) * 100, 1)) + "%")