Introduction#

Motivation#

As machine learning systems are increasingly deployed in high-stakes domains — hiring, lending, criminal justice, healthcare — ensuring that these systems do not exhibit discriminatory behavior is a critical requirement. Standard ML training procedures optimize predictive accuracy without regard for fairness, and post-hoc auditing provides no guarantees that a deployed model will satisfy fairness constraints on future data.

Seldonian algorithms [Thomas2019] address this gap by providing high-confidence guarantees that a learned model will satisfy user-specified behavioral constraints. The key insight is that the responsibility for enforcing fairness is shifted from the user (who audits after deployment) to the algorithm designer (who builds safety into the training procedure itself).

Problem Formulation#

Let $\mathcal{D}$ denote a dataset of $n$ i.i.d. samples, and let $a(\mathcal{D})$ denote the model returned by a learning algorithm $a$ . We define:

Primary objective $f(\theta)$ : the quantity to be maximized (e.g., negative log loss).
Behavioral constraint $g(\theta) \leq 0$ : a fairness condition that must hold with high probability (e.g., bounded disparity in group-level true positive rates).
Confidence level $1 - \delta$ : the minimum probability with which the constraint must be satisfied.

A Seldonian algorithm solves:

\max_\theta \; f(\theta) \quad \text{subject to} \quad \Pr\!\left[\, g\!\left(a(\mathcal{D})\right) \leq 0 \,\right] \geq 1 - \delta

If no solution satisfying the constraint can be found with sufficient confidence, the algorithm returns No Solution Found (NSF) rather than a potentially unsafe model.

Framework Overview#

The Fair-Seldonian framework implements the Quasi-Seldonian Algorithm (QSA), which proceeds in three stages:

Stage	Description
1. Data Splitting	The training data $\mathcal{D}$ is partitioned into a candidate set $\mathcal{D}_c$ and a safety set $\mathcal{D}_s$ according to a configurable ratio (default 40/60).
2. Candidate Selection	An optimization procedure finds $\theta^$ that maximizes $f(\theta)$ subject to a predicted* upper bound on $g(\theta)$ computed from $\mathcal{D}_c$ . This predicted bound accounts for the statistical uncertainty that will remain when the safety test uses $\mathcal{D}_s$ .
3. Safety Test	The candidate $\theta^$ is evaluated on $\mathcal{D}_s$ using a concentration inequality (Hoeffding or Student’s t). If the upper bound on $g(\theta^)$ is non-positive, the solution is accepted; otherwise, No Solution Found is returned.

Constraint Specification#

Behavioral constraints are specified as strings in reverse Polish notation (RPN) and parsed into expression trees for evaluation. The supported primitives are:

Primitive	Conditions on	Averaged over
`TPR(g)`	group and `Y = 1`	recall: predicted 1 among the group’s positives
`FPR(g)`	group and `Y = 0`	predicted 1 among the group’s negatives
`TNR(g)`	group and `Y = 0`	predicted 0 among the group’s negatives
`FNR(g)`	group and `Y = 1`	predicted 0 among the group’s positives
`TP(g)`	group only	predicted 1 and labelled 1, as a fraction of the whole group
`FP(g)`	group only	predicted 1 and labelled 0, as a fraction of the whole group
`TN(g)`	group only	predicted 0 and labelled 0, as a fraction of the whole group
`FN(g)`	group only	predicted 0 and labelled 1, as a fraction of the whole group
`PR(g)`	group only	predicted 1, whatever the label; equals `TP + FP`
`NR(g)`	group only	predicted 0, whatever the label; equals `TN + FN`

Supported operators: +, -, *, /, ^, abs.

The distinction between the three kinds is easy to miss and it matters. A cell such as TP(g) is a fraction of the whole of group $g$ — every row of the group contributes, and the four cells sum to 1. A rate such as TPR(g) is a mean over only that group’s positive rows, so it carries a smaller sample size and a wider interval. Fairness constraints covers how to choose.

Example. The default constraint string:

TP(1) TP(0) - abs 0.25 TP(1) * -

encodes the infix expression:

\left| \text{TP}(1) - \text{TP}(0) \right| - 0.25 \cdot \text{TP}(1) \leq 0

This requires the gap between the groups’ true-positive cells to be at most 25% of group 1’s cell.

Note

This is not equal opportunity, despite the resemblance. Equal opportunity compares true-positive rates — TPR(g), conditioned on $Y = 1$ — and is available as equal_opportunity(). The default constraint compares cells, which is a different quantity computed over a different set of rows.

Confidence Bound Propagation#

Evaluating $g(\theta)$ requires computing confidence intervals for each leaf node (e.g., TP(1)) and propagating them through the expression tree using interval arithmetic. Four concentration inequalities are available, three of them distribution-free:

Inequality	Assumption	Guarantee	Half-width at n=2000, rate 0.1
`T_TEST`	the sample mean is approximately normal	asymptotic only	0.0131
`HOEFFDING_INEQUALITY`	each term lies in [0, 1]	distribution-free	0.0304
`EMPIRICAL_BERNSTEIN`	each term lies in [0, 1]	distribution-free	0.0225
`BETTING`	each term lies in [0, 1]	distribution-free	0.0142

Hoeffding’s inequality [Hoeffding1963] is the default. For a bounded random variable with $n$ samples:

\Pr\!\left[\left|\hat{p} - p\right| \geq \epsilon\right] \leq 2\exp\!\left(-2n\epsilon^2\right)

Empirical Bernstein and betting both adapt to the variance they observe, and are tighter than Hoeffding whenever a group’s rate is far from $1/2$ . Student’s t assumes the sample mean is approximately normal — an appeal to the central limit theorem rather than a finite-sample bound, and what puts the quasi in quasi-Seldonian. Concentration Inequalities derives each and shows where the ordering between them changes.

At each internal node of the expression tree, the confidence intervals of the children are combined according to the rules of interval arithmetic [Moore1966] (see fair_seldonian.constraints.bounds). The framework provides several optimizations to tighten these bounds, described in Algorithm Variants.