Project description

Thresher - THRESHold EvaluatoR for Python

Your model gives you probabilities. Where you cut them is a decision — stop leaving it at 0.5.

A classifier that outputs predict_proba hands you a number between 0 and 1. Turning that into an actual yes-or-no answer needs a cut-off, and almost every pipeline uses 0.5 — because it is the default, not because anyone measured it.

The cut-off that actually maximizes accuracy depends on your data: how far the two classes overlap, how imbalanced they are, and how well your model is calibrated. It is rarely 0.5. When one class is rare it can be nowhere near it, and the gap between the default and the right answer is the gap between a model that looks fine on paper and one that is useful.

Thresher measures it. Give it your scores and the ground truth, and it returns the threshold that classifies the highest fraction of your samples correctly:

from thresher import Thresher

Thresher().optimize_threshold(scores, actual_classes)

Or without writing any Python at all, straight from a terminal:

thresher scores.csv

That is the whole interface. Everything else in this README is about tuning what happens underneath — which of the five search algorithms runs, and how hard it looks.

Project description
- An oracle mechanism
Implemented algorithms
Algorithm scores
How to setup?
Custom parameters
- Control parameters for the algorithms
Sample usage
Command line
Performance tests
Future work

Project description

A bare pandas implementation of a tool for finding the threshold which maximizes accuracy of predict_proba like-outputs (from e.g. scikit-learn), in regard to the provided ground truth (labels).

Note: you can jump directly to the sample usage here.

Method interesting for the user is optimize_threshold(scores, actual_classes), which is available from the Thresher class. This method, for given scores and actual classes, returns a threshold that yields the highest fraction of correctly classified samples.

optimize_threshold parameters:
  scores:list
    The list of scores.
  actual_classes:list
    The list of ground truth (correct) classes.
    Classes are represented as -1 and 1.
returns:
  threshold:float
    The threshold value that yields the highest fraction of correctly classified
    samples. If multiple thresholds give the optimal fraction, return any threshold.

An oracle mechanism

[!WARNING] Deprecated — to be removed in 0.5.0. The oracle existed to choose between algorithms that traded accuracy against input size. Exact sweep settled that question: it is exact at every size and cheaper than everything it chose between, so there is no longer a decision to delegate. In 0.5.0 the mechanism goes away and exact becomes the plain default. Nothing is required of you if you use the default today — you already get exact. If you pass algorithm='auto' explicitly, it will keep working as an alias for the default; any code reading the routing behaviour itself should select an algorithm by name instead.

We implemented a meta-optimizer - an 'oracle' mechanism, which chooses the algorithm for you. This is the default behaviour, and can be controlled by changing the algorithm param of the Thresher constructor. See the source code of oracle.py and interface.py for more details.

Since 0.4.0 it always chooses Exact sweep, and the choice is no longer interesting. It used to route by input size - linear search below 1,000 rows, grid search below 50,000, stochastic gradient descent above that - because the only exact algorithm was O(n²) and stopped being affordable. Exact sweep is exact at every size and cheaper than the approximations it replaced, so there is nothing left to trade off. The other algorithms remain available by name.

Implemented algorithms

Exact sweep

The default, and the one you want. Added in version 0.4.0. It returns the best threshold that exists - not an approximation - in O(n log n).

The insight is that linear search does the same work over and over. Moving a threshold past one sample changes the number of correct predictions by exactly one, in a direction fixed by that sample's class, so there is no need to rescore the whole dataset for every candidate. Sort the samples once, then sweep through them keeping running counts:

correct(k) = (negatives among the first k) + (positives among the remaining n - k)

Both terms are running totals, so each candidate costs constant time and the sort is the only real expense.

This is the standard exact splitter used to pick a decision-stump threshold, and the same linear scan that generates an ROC curve - see Fawcett, An introduction to ROC analysis (Pattern Recognition Letters, 2006), and Google's decision forests documentation, which gives the same O(n log n) bound "because of the sorting of the feature values".

It has no parameters. There is no accuracy left to trade for speed.

Compared with linear search, which it supersedes, it is exact in the same sense and strictly faster - by 104× at 1,000 rows and 1,358× at 16,000, a gap that widens with every row. It is also slightly more accurate: linear search only ever considers the midpoints between adjacent scores, so it cannot express the "classify everything as negative" split, which the sweep reaches for free at max(scores). On randomised inputs that mattered in about 10% of cases.

Linear search

Superseded by Exact sweep, which returns the same answer - or a marginally better one - in a fraction of the time. Kept for comparison and for its multiprocessing option.

This is the most basic, iterative approach. For every threshold present in the input (in the scores list), we evaluate it by calculating the exact accuracy of split produced by such threshold. Then, return the threshold which produce the most accurate split.