📘

ROC Curve Points

MediumModel Evaluation 📚 Machine 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 threshold is 0.

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:

First, we sort the predicted probabilities in descending order and use them as thresholds: $[0.9, 0.65, 0.4, 0.3]$ .
Then, we calculate the TPR and FPR at each threshold:
- At threshold $0.9$ , only the first prediction is $\geq$ threshold, so $TP = 1$ , $FP = 0$ , $TN = 1$ , $FN = 1$ , resulting in $TPR = \frac{1}{1+1} = 0.5$ and $FPR = \frac{0}{0+1} = 0$ .
- At threshold $0.65$ , the first two predictions are $\geq$ threshold, so $TP = 2$ , $FP = 0$ , $TN = 1$ , $FN = 0$ , resulting in $TPR = \frac{2}{2+0} = 1$ and $FPR = \frac{0}{0+1} = 0$ .
- At threshold $0.4$ , the first three predictions are $\geq$ threshold, so $TP = 2$ , $FP = 1$ , $TN = 0$ , $FN = 0$ , resulting in $TPR = \frac{2}{2+0} = 1$ and $FPR = \frac{1}{1+0} = 0.5$ .
- At threshold $0$ , all predictions are $\geq$ threshold, so $TP = 2$ , $FP = 2$ , $TN = 0$ , $FN = 0$ , resulting in $TPR = \frac{2}{2+0} = 1$ and $FPR = \frac{2}{2+0} = 1$ .
The final output includes the starting point $(0, 0)$ when the threshold is above the max prediction and the calculated points, resulting in $[(0.0, 0.0), (0.0, 0.5), (0.0, 1.0), (0.5, 1.0), (1.0, 1.0)]$ .

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

More from Machine Learning 1

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

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

0/0

Run code to see test results.