One-vs-Rest Classifier

hardFREEClassificationMachine Learning 1

Implement a One-vs-Rest (OvR) multi-class classifier using multiple binary logistic models.

Given $K$ binary classifiers (each represented as a weight vector and bias), classify data points by running all classifiers and selecting the class with the highest sigmoid output.

Each classifier $k$ computes: $P(y=k|x) = \sigma(w_k \cdot x + b_k)$

For each data point, return the class (0-indexed) with the highest probability, along with that probability.

Return a list of tuples [(class_index, probability), ...].

Example

Input

X = [[1, 2]]
classifiers = [([0.5, 0.3], -0.5), ([-0.2, 0.8], 0.1), ([0.1, -0.4], 0.3)]

Output

[(1, 0.8176)]

Reasoning

X holds one data point, $x = [1, 2]$ (two features). classifiers holds three (weights, bias) pairs, one binary "is it class $k$ ?" model per class: $w_0 = [0.5, 0.3], b_0 = -0.5$ ; $w_1 = [-0.2, 0.8], b_1 = 0.1$ ; $w_2 = [0.1, -0.4], b_2 = 0.3$ .
Each model scores the point with $z_k = w_k \cdot x + b_k$ $z_{k} = w_{k} \cdot x + b_{k}$ , then squashes it with $\sigma(z) = \frac{1}{1 + e^{-z}}$ $σ (z) = \frac{1}{1 + e ^{- z}}$ :
- Class 0: $z_0 = 0.5 + 0.6 - 0.5 = 0.6$ , $\sigma(0.6) \approx 0.6457$
- Class 1: $z_1 = -0.2 + 1.6 + 0.1 = 1.5$ , $\sigma(1.5) \approx 0.8176$
- Class 2: $z_2 = 0.1 - 0.8 + 0.3 = -0.4$ , $\sigma(-0.4) \approx 0.4013$
Class 1 is the most confident, so this point becomes the pair (class 1, probability $0.8176$ rounded to 4 decimal places), giving [(1, 0.8176)]: one tuple per row of X.
Notice the three probabilities sum to $1.8646$ , not 1: each model is an independent yes/no judge. Since $\sigma$ is increasing, the largest $z_k$ always wins.

Constraints

X: 2D list (n_samples x n_features)
classifiers: list of (weights, bias) tuples, one per class
Return list of (class_index, max_probability) tuples
Probabilities rounded to 4 decimal places

Learn this in

NLP FundamentalsML Study Plan ClassificationML Study Plan Support Vector MachinesML Study Plan

More from Machine Learning 1

RBF Kernel Matrixhard Polynomial Kernelmedium Hinge Losseasy Linear Decision Boundaryeasy Gradient Boosting Residual Stephard

Concept primer

Background Knowledge

The One-vs-Rest (OvR) multi-class classifier is a technique used to extend binary classification models to multi-class problems. In a multi-class problem, we have $K$ classes, and we want to predict the class label for a given data point. The OvR approach involves training $K$ binary classifiers, each of which predicts the probability of a data point belonging to a particular class. The class with the highest predicted probability is then selected as the final prediction. This approach is commonly used with logistic regression models, which output a probability value between 0 and 1.

The logistic function, also known as the sigmoid function, is a crucial component of logistic regression models. It maps the input to a probability value between 0 and 1, making it suitable for binary classification problems. The sigmoid function is defined as $\sigma(z) = \frac{1}{1 + e^{-z}}$ , where $z$ is the input to the function. In the context of OvR, each binary classifier computes the probability of a data point belonging to a particular class using the sigmoid function: $P(y=k|x) = \sigma(w_k \cdot x + b_k)$ , where $w_k$ is the weight vector and $b_k$ is the bias term for the $k^{th}$ classifier.

The OvR approach has several advantages, including simplicity and interpretability. However, it can be computationally expensive when dealing with a large number of classes, as we need to train and evaluate $K$ separate binary classifiers. Additionally, the OvR approach assumes that the classes are mutually exclusive, meaning that a data point can only belong to one class.

Algorithm/Approach

The general approach to solving this problem involves the following steps:

Iterate over each data point and compute the sigmoid output for each of the $K$ binary classifiers.
Select the class with the highest sigmoid output as the predicted class.
Return the predicted class and its corresponding probability.

This approach can be implemented using a variety of programming languages and machine learning libraries.

Step-by-Step Strategy

To implement the OvR multi-class classifier, follow these steps:

Initialize an empty list to store the predicted classes and their corresponding probabilities.
Iterate over each data point in the input data.
For each data point, iterate over each of the $K$ binary classifiers.
Compute the sigmoid output for each classifier using the formula $P(y=k|x) = \sigma(w_k \cdot x + b_k)$ .
Select the class with the highest sigmoid output as the predicted class.
Append the predicted class and its corresponding probability to the output list.
Return the output list.

Common Pitfalls

When implementing the OvR multi-class classifier, watch out for the following common pitfalls:

Numerical instability: The sigmoid function can be numerically unstable when dealing with large input values. This can be mitigated by using a numerically stable implementation of the sigmoid function.
Class imbalance: If the classes are imbalanced, the OvR approach can be biased towards the majority class. This can be mitigated by using techniques such as class weighting or oversampling the minority class.
Overfitting: The OvR approach can be prone to overfitting, especially when dealing with a large number of classes. This can be mitigated by using regularization techniques such as L1 or L2 regularization.

Time & Space Complexity

The time complexity of the OvR multi-class classifier is $O(n \cdot K \cdot d)$ , where $n$ is the number of data points, $K$ is the number of classes, and $d$ is the number of features. The space complexity is $O(n \cdot K)$ , as we need to store the predicted classes and their corresponding probabilities for each data point. Note that these complexities assume that the sigmoid function is computed in constant time, which may not be the case in practice due to numerical instability issues.

solution.py

Python 3.13

Test results