ROC Curve Points

mediumFREEModel EvaluationMachine Learning 1

Compute the ROC curve points (TPR and FPR at each threshold).

Given true labels and predicted probabilities, compute the True Positive Rate (TPR) and False Positive Rate (FPR) at each unique threshold.

For each unique predicted probability (used as threshold, sorted descending), classify all predictions $\geq$ threshold as positive:

$TPR = \frac{TP}{TP + FN}, \quad FPR = \frac{FP}{FP + TN}$

Return a list of (fpr, tpr) tuples rounded to 4 decimal places, starting from (0, 0) when threshold is above the max prediction, ending at (1, 1) when every prediction is classified positive. The point (1, 1) appears exactly once: the lowest threshold already produces it, so do not append a second copy.

Example

Input

y_true = [1, 0, 1, 0]
y_scores = [0.9, 0.4, 0.65, 0.3]

Output

[(0.0, 0.0), (0.0, 0.5), (0.0, 1.0), (0.5, 1.0), (1.0, 1.0)]

Reasoning

y_true says items 1 and 3 are real positives, so there are $P = 2$ positives and $N = 2$ negatives; y_scores are the model's confidences.
The unique scores, highest first, give the thresholds $0.9, 0.65, 0.4, 0.3$ . Above $0.9$ nothing is predicted positive, which is the starting point $(0, 0)$ .
At $0.9$ only the item scored $0.9$ (a real positive) passes: $TP = 1$ , $FP = 0$ , so $TPR = \frac{1}{2} = 0.5$ , $FPR = \frac{0}{2} = 0$ , giving $(0.0, 0.5)$ .
At $0.65$ the second positive also passes: $TP = 2$ , $FP = 0$ , giving $(0.0, 1.0)$ .
At $0.4$ the first negative passes: $TP = 2$ , $FP = 1$ , $FPR = \frac{1}{2}$ , giving $(0.5, 1.0)$ .
At $0.3$ , the lowest score, every item is predicted positive: $TP = 2$ , $FP = 2$ , giving $(1.0, 1.0)$ . That is already the end point, so it appears only once.
Notice that both positives outrank both negatives, so the curve reaches $TPR = 1$ before any false positive appears: a perfect ranking.

Constraints

y_true: list of 0s and 1s
y_scores: list of predicted probabilities
Return sorted list of (fpr, tpr) tuples from (0,0) to (1,1)
Round to 4 decimal places

Learn this in

Model EvaluationML Study Plan Text ClassificationNLP 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 Receiver Operating Characteristic (ROC) curve is a fundamental concept in model evaluation, used to assess the performance of a binary classification model. It plots the True Positive Rate (TPR) against the False Positive Rate (FPR) at different thresholds. The TPR represents the proportion of actual positive instances that are correctly identified, while the FPR represents the proportion of actual negative instances that are misclassified as positive. The ROC curve provides a comprehensive picture of a model's performance, allowing for the selection of an optimal threshold that balances TPR and FPR.

In the context of binary classification, a threshold is a decision boundary that determines whether a prediction is classified as positive or negative. By varying the threshold, we can trade off between TPR and FPR. A higher threshold results in fewer false positives (lower FPR) but may also miss some true positives (lower TPR), while a lower threshold increases the TPR but may also increase the FPR. The predicted probabilities output by a model are used to determine the classification outcome based on the chosen threshold.

To compute the ROC curve points, we need to calculate the TPR and FPR at each unique threshold. This involves categorizing predictions into true positives (TP), false positives (FP), true negatives (TN), and false negatives (FN) based on the true labels and predicted probabilities. The TPR and FPR are then calculated using these values: $TPR = \frac{TP}{TP + FN}$ and $FPR = \frac{FP}{FP + TN}$ . Understanding these concepts is crucial for solving the "ROC Curve Points" problem.

Algorithm/Approach

The general approach to solving this problem involves iterating over the unique predicted probabilities in descending order, using each as a threshold to classify predictions. At each threshold, we calculate the TPR and FPR based on the resulting TP, FP, TN, and FN values. This process requires sorting the predicted probabilities, iterating over the sorted values, and updating the TPR and FPR calculations at each step.

Step-by-Step Strategy

To implement the solution:

Sort the predicted probabilities in descending order.
Initialize lists to store the TPR and FPR values at each threshold.
Iterate over the sorted predicted probabilities, using each as a threshold:

Classify predictions as positive or negative based on the threshold.
Calculate TP, FP, TN, and FN values.
Compute TPR and FPR using the calculated values.
Append the (FPR, TPR) tuple to the result list.

Ensure the result list includes the points (0, 0) and (1, 1) for thresholds above the max prediction and 0, respectively.

Common Pitfalls

When implementing the solution, watch out for:

Incorrect sorting of predicted probabilities.
Failure to handle edge cases, such as a threshold above the max prediction or 0.
Incorrect calculation of TP, FP, TN, and FN values.
Rounding errors in TPR and FPR calculations.

Time & Space Complexity

The expected time complexity is O(n log n) due to sorting the predicted probabilities, where n is the number of predictions. The space complexity is O(n) for storing the sorted probabilities and the resulting (FPR, TPR) tuples.

solution.py

Python 3.13

Test results