Qinvert

Qinvert takes summary statistics that an agency published exactly (quartiles, outlier fences, minima, maxima, means) and the part of the dataset the agency released. It returns the smallest sets of added or removed rows that make every published statistic recompute exactly, in Python Fraction arithmetic, so a match means exact equality. Each quantilethe value below which a given fraction p of the data lies; statistical packages define it in several slightly different ways is computed under one of the nine definitions of Hyndman and Fan or the five of SAS Institute, whichever the publisher used.

What it does

Agencies often publish statistics computed on a full dataset and release only part of it, for example without the rows of organizations that closed before publication. When the released rows do not reproduce the published numbers, Qinvert searches for the added or removed rows that make them match.

A target is a pair (statistic, published value). The statistic is a quantile under a named definition, a Tukey fencean outlier cutoff placed a multiple m of the interquartile range below the first quartile or above the third, an order statistic (the j-th smallest value), a mean, or a linear combination of these. The published value is an exact number, or an Interval when the publication is capped or only bounds it. A cap is a bound at which the publisher truncates a printed fence, a low fence from below and a high fence from above.

Given the released values and the targets for one dataset, solve finds delta families: added values plus removed released values, as few in total as possible, after which every target recomputes exactly.

The definitions are named "sas1" to "sas5" (SAS's QNTLDEF 1–5) and "r1" to "r9" (the nine R types of Hyndman and Fan). A Tukey fence pair with multiplier $m$ is $\mathrm{lo} = (1+m)Q_1 - mQ_3$, $\mathrm{hi} = (1+m)Q_3 - mQ_1$, and when neither published fence sits at its cap both quartiles follow from the pair:

$$Q_1 = \frac{(1+m)\,\mathrm{lo} + m\,\mathrm{hi}}{1+2m}, \qquad Q_3 = \frac{m\,\mathrm{lo} + (1+m)\,\mathrm{hi}}{1+2m}.$$

For a fence published at its cap value only an inequality is known, and the solver then scans candidate values for the quartile left free.

Every family is verified before it is returned, by rebuilding the dataset and re-evaluating every target, so every reported family is a solution. The search is bounded by caps: the total delta size k_cap, the removals per family rem_cap, the families kept max_witnesses, and the budgets in DEFAULT_CAPS. Every cap the search reaches is named in the result's caps_hit list.

stack covers one withheld entity that appears in several datasets, such as one closed contract entering every measure published for its year. It solves each dataset separately, then assembles the families into shared entities carrying one value per dataset they take part in. A dataset whose targets already recompute exactly must stay exact, and stack raises StackerError instead of returning a delta that breaks one.

Qinvert has these limits:

Examples

One dataset with a capped fence pair (the README quickstart). The released scores have two decimals. The publisher printed a low outer fence of 0, which is this measure's cap, and a high outer fence of 1.41, under SAS's default quantile definition. With the package tools/qinvert/ set up (see Requirements) and values holding your list of released scores:

from fractions import Fraction as F
from qinvert import (Quantile, TukeyFence, Mean, Interval,
                     solve, Dataset, stack)

# one dataset, published Q1/Q3 (SAS default definition) + capped fences
targets = [
    (TukeyFence("lo", 3, "sas5", cap=0), F(0)),        # published "0" = cap
    (TukeyFence("hi", 3, "sas5"),        F("1.41")),   # exact published
]
res = solve(values, targets, register=F(1, 100),  # data are 2dp
            value_lo=0, k_cap=8, rem_cap=2)
res["k"]          # minimal delta size, or None if unreachable within caps
res["families"]   # [{k_add, k_rem, removed, adds:[{value, window, role}]}]
res["caps_hit"]   # every truncation leaves a note

register=F(1, 100) puts added values on the 0.01 grid and value_lo=0 forbids negative scores. res["k"] is the smallest number of added plus removed rows that reproduces both fences, searching up to 8 rows with at most 2 removals per family. If the released rows already match, it is 0 and res["exact_already"] is True.

Invert a fence pair for the quartiles. From the package tests. The last element of the returned tuple is the mode, which names the fence equations that can be used.

from fractions import Fraction as F
from qinvert import invert_fence_pair

invert_fence_pair("0", "1.41", 3, F(0), None)[2]     # "hi_only"
invert_fence_pair("57", "100", 3, F(0), F(100))[2]   # "lo_only"
invert_fence_pair("0", "100", 3, F(0), F(100))[2]    # "none"

In the first call the low fence equals its cap of 0, so only the high-fence equation constrains the quartiles. In the second the high fence is at its cap, and in the third both are and only inequalities remain. With two uncapped fences the mode is "both" and the first two elements are the exact $Q_1$ and $Q_3$ from the formula above.

Several datasets sharing withheld entities (also from the README). Each Dataset holds released rows as (entity_id, value) pairs plus its own targets. Two entity classes are declared, the second never participates in D2, and an entity that carries a value in D2 carries the same value in D1.

d1 = Dataset("D1", rows1, targets1, register=F(1, 100))   # rows: (eid, value)
d2 = Dataset("D2", rows2, targets2, register=F(1, 100))
out = stack([d1, d2], classes=("MA-PD", "MA-only"),
            participation=lambda cls, ds: not (cls == "MA-only" and ds == "D2"),
            couplings=[("D1", "D2")],   # entity in D2 carries equal value in D1
            k_cap=8, rem_cap=1)
out["entities"], out["removed_entities"], out["battery"], out["regressions"]

out["entities"] lists the added entities, each with an id, a class cls and a values map from dataset name to the value it carries there. out["removed_entities"] lists the released entity ids taken out, and out["battery"] holds one record per dataset with its before_exact and after_exact flags. out["unsolved"] and out["notes"] name any dataset not solved within the caps and why, and out["regressions"] is empty on any normal return.

Routines

Statistics and targets (targets.py)

FunctionWhat it returns
Quantile(p, definition)The quantile at probability p, strictly between 0 and 1, under one of the 14 named definitions
TukeyFence(side, mult, definition, cap)The "lo" or "hi" fence (mult=3 outer, F(3, 2) inner), truncated at cap when one is given
OrderStat(j), MinStat(), MaxStat(), RangeStat()The j-th smallest value, counted from the top for negative j; the minimum, the maximum and the range
Mean()The arithmetic mean, handled as an exact sum constraint on the delta
LinearCombo([(coeff, stat), ...])A linear combination, which drives the search only with exactly two order-statistic terms and is otherwise checked on each candidate
Interval(lo, hi)A published range in place of an exact value
invert_fence_pair(pub_lo, pub_hi, mult, cap_lo, cap_hi)The tuple (Q1, Q3, mode)

Solving one dataset (solver.py)

FunctionWhat it returns
solve(values, targets, ...)A dictionary with k, families, caps_hit, exact_already, n, k_cap and rem_cap
solve_many(jobs, workers)One solve result per job, run in parallel worker processes; each job is a dictionary of solve arguments with an optional job_id
DEFAULT_CAPSThe enumeration budgets; override any of them through caps=

The keyword arguments of solve are register, value_lo, value_hi, k_cap, rem_cap, max_witnesses and caps. By default it searches up to 8 rows and removes none. Each family lists its removed values and its adds. An add's window (lo, hi, lo_strict, hi_strict), when present, means any grid value inside it also keeps the order-statistic targets exact. An answer therefore often reads "one extra row anywhere above some value." solve_many starts its worker processes with the spawn start method.

Stacking across datasets (stacker.py)

FunctionWhat it returns
Dataset(name, rows, targets, ...)One released dataset, with the methods values(), exact() and entity_ids()
stack(datasets, ...)The shared entities across datasets, with the check that no exact dataset is broken
StackerErrorRaised when an assembled delta would break an already-exact dataset, or when the class rules admit no class for a dataset

The lower-level exports, among them evaluate_targets, targets_exact and as_fraction, are listed in __init__.py.

Requirements

Source and references

The code is in tools/qinvert/ in the BootLoops repository, released under the MIT license. Its README.md has the algebra and the full list of structural limits.

Qinvert generalizes the solver written for the Medicare star ratings analysis, whose code is at github.com/bootloops-papers/healthstars. In that analysis, values are filled in for the blanked scores until both of the outlier bounds that the Centers for Medicare & Medicaid Services (CMS) prints match. The quantile definitions are implemented from the formulas in the references below.

ReferenceWhat it supplies
R. J. Hyndman and Y. Fan, "Sample Quantiles in Statistical Packages," The American Statistician 50(4), 361–365 (1996)The nine sample-quantile types "r1" to "r9"
R's ?quantile help pageThe formulas of the same nine types
SAS Institute, Base SAS 9.4 Procedures Guide, "The UNIVARIATE Procedure: Calculating Percentiles"The five percentile definitions "sas1" to "sas5" (QNTLDEF 1–5)
CMS, Star Ratings Technical Notes 2024, pp. 149–150The cap convention of TukeyFence

← back to the tools index