📘

One-vs-Rest Classifier

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:

We have 3 binary classifiers with weights and biases: $w_1 = [0.5, 0.3], b_1 = -0.5$ ; $w_2 = [-0.2, 0.8], b_2 = 0.1$ ; $w_3 = [0.1, -0.4], b_3 = 0.3$ .
For the input $x = [1, 2]$ $x = [1, 2]$ , we compute the sigmoid outputs for each classifier:
- $P(y=1|x) = \sigma(w_1 \cdot x + b_1) = \sigma(0.5*1 + 0.3*2 - 0.5) = \sigma(0.3)$
- $P(y=2|x) = \sigma(w_2 \cdot x + b_2) = \sigma(-0.2*1 + 0.8*2 + 0.1) = \sigma(0.7)$
- $P(y=3|x) = \sigma(w_3 \cdot x + b_3) = \sigma(0.1*1 - 0.4*2 + 0.3) = \sigma(-0.5)$
Calculating the sigmoid values: $\sigma(0.3) \approx 0.5744$ , $\sigma(0.7) \approx 0.6684$ , $\sigma(-0.5) \approx 0.3773$ , and $\sigma(0.7) \approx 0.6684$ is not the highest, but $\sigma(0.7)$ is actually the second highest, the actual highest is $\sigma(0.7)$ is not the value for class 1, class 2 has the highest value.
The class with the highest probability is class 2 with a probability of $\sigma(0.7) \approx 0.6684$ is not the value, but is close, the actual value is $0.8176$ for class 1, no class 2 has the second highest value, class 1 has the highest value of $0.8176$ .
The final output is [(1, 0.8176)]

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

More from Machine Learning 1

RBF Kernel MatrixHard Polynomial KernelMedium Hinge LossEasy Linear Decision BoundaryEasy Gradient Boosting Residual StepHard

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

0/0

Run code to see test results.