lira.py
Checks: RULER: The per-example audit states its Gaussian limit property.
Cited on: RULER.
To run it: save lira.py; needs numpy.
"""lira.py -- a published per-example membership audit scored against
the exact posterior: the probability it states converges to its
Gaussian limit rather than to the truth, and whether its membership
call survives is a side criterion read cell by cell.
QUESTION. U-LiRA (Hayes, Shumailov, Triantafillou, Khalifa and
Papernot, "Inexact Unlearning Needs More Careful Evaluations to Avoid
a False Sense of Privacy", arXiv:2403.01218, Algorithm 1 and Sec. 4.3,
read at source) audits one example: it collects the example's score
under N shadow models that saw and then unlearned it (in) and N that
never saw it (out), fits a Gaussian to each, and for the audited
model's score o states
p_member = N(o; mu1, s1^2) / (N(o; mu1, s1^2) + N(o; mu0, s0^2)),
calling a member iff p_member > 1/2. Its stated outputs are the
balanced accuracy of that call and the per-example p_member itself
("an optimal unlearning algorithm would result in a predicted
membership probability of 1/2"); it states no interval. The source
names the Gaussian fit as a risk to the attack's ACCURACY on
non-Gaussian shadow distributions (its Sec. 7, bimodal and skewed
examples). Where the truth is known exactly, what do the call and the
probability each converge to?
THE WORLD. The depth cell (a, b) of audit.py: the audited datum is the
first move of a uniform arrangement of a twos and b threes, member =
first move 2, and the score is the number of 2-moves in the three
positions after the first, so
P_in(c) = HG(T - 1, a - 1, 3), P_out(c) = HG(T - 1, a, 3), T = a + b.
p_member is the posterior at prior 1/2 under the fits, so its estimand
is the EQUAL-PRIOR posterior tau(c) = P_in(c)/(P_in(c) + P_out(c)), an exact
Fraction; the balanced accuracy's ceiling is
(1/2) sum_c max(P_in(c), P_out(c)). The audited mass of cell c is
P_u(c) = (a/T) P_in(c) + (b/T) P_out(c). Cells W1 = (5, 5), W2 = (12, 3),
W3 = (2, 8); S, ring-free: support points {0, 3}, member mass
(9/10, 1/10), non-member mirrored; PC, a positive control where the
fit is right: member N(0, 1), non-member N(3, 4).
THE ARGUMENT (written before the engine).
(A) THE LIMIT (property). The fitted means and variances converge to
the class moments, so p_member(c) converges to the GAUSSIAN-LIMIT
posterior p_lim(c), the formula at the exact moments, and every
calibration error converges to its value at p_lim: the floor
ECE_lim = sum_c P_u(c) |p_lim(c) - tau(c)| is a property of the
model class, not of the shadow count. At W2, by hand,
tau = (1, 11/15, 5/9, 3/7) and p_lim = (0.982, 0.840, 0.554, 0.414):
over-confident at c = 1 and c = 3, under-confident at c = 0,
where the truth is certain. At S the fits share variance 81/100
and p_lim(0) = 1/(1 + e^{-40/9}) = 0.988 against tau = 9/10: a
Gaussian prices a far support point at the exponential of a
squared distance where the world holds linear mass. The share of
audited mass stated more extremely than tau converges to the mass
of the cells where p_lim is more extreme than tau on tau's side.
(B) THE SIDE CRITERION (property). The balanced accuracy is
(1/2) sum over cells of the class mass the call picks, maximized
exactly by picking the larger of P_in(c), P_out(c), i.e. by tau's side
of 1/2. So the limit call reaches the ceiling iff sign(p_lim(c) -
1/2) = sign(tau(c) - 1/2) at every cell with mass and tau != 1/2, and
each disagreeing cell costs |P_in(c) - P_out(c)|/2. Whether the call
survives is therefore a cell-by-cell fact, not a property of the
tool, and a census decides whether it ever fails on this world.
(C) DEGENERATE FITS. A class whose N shadow scores coincide fits a
zero variance, a point mass; the stated probability is then 0, 1
or 1/2 by where o sits. At W3 the member score takes two values
at masses (2/3, 1/3), so at N = 8 one class or the other
collapses with probability about 0.044.
DESIGN. For S, W1, W2, W3 and N in {8, 32, 128, 512} (128 the source's
own count), R = 400 replicates of N member and N non-member shadow
scores; fits by mean and MLE variance; scored EXACTLY over the support:
ACC the call's balanced accuracy, against the ceiling;
ECE sum_c P_u(c) |p(c) - tau(c)|;
OVER sum of P_u(c) where p(c) is more extreme than tau(c) on tau's
side of 1/2;
COLLAPSE the share of replicates with a zero-variance fit.
PC is scored by Monte Carlo, 100 shadow replicates at N = 128 and 2000
evaluation draws per class, against its closed-form posterior. The CENSUS: every depth cell with
2 <= a, b <= 30 (both classes then have positive variance), exact tau in
Fraction and p_lim in float, counting the cells whose limit call
disagrees with tau's side at a cell of positive mass, and the largest
limit loss; the disagreeing cell with the largest loss is then run
like the others. One seed per (cell, N).
PREDICTIONS (fixed before the engine).
Q0 CONTROL, read first: at PC, N = 128, balanced accuracy within 0.02
of the Gaussian ceiling and mean |p - posterior| below 0.05.
Q1 In Fraction, W2's tau = (1, 11/15, 5/9, 3/7) and ceiling 419/728;
W2's p_lim within 0.001 of (0.982, 0.840, 0.554, 0.414), and S's
p_lim(0) equal to 1/(1 + e^{-40/9}) to 1e-12.
Q2 (A) At N = 512, the mean stated p at every cell of audited mass
above 0.01 is within 0.02 of p_lim at S, W1, W2 and W3; ECE is
within 0.015 of ECE_lim; ECE_lim exceeds 0.01 at all four.
Q3 (A) At N = 512, OVER is within 0.05 of the limit's over-confident
mass at all four.
Q4 (B) At N = 512 the balanced accuracy is within 0.01 of the ceiling
wherever the census finds the sides agree. The census finds at
least one disagreeing cell; at the one with the largest limit
loss, N = 512's accuracy sits below the ceiling by that loss,
within 0.01.
Printed and weighed: COLLAPSE at W3, N = 8, against (C)'s 0.044.
KILL. Q0 off: nothing is read. Q2 off: the stated probability does not
converge to the Gaussian limit and (A) is false.
FINDINGS. No kill fired. Three frozen clauses were wrong or empty, all
the slate's. Q2's "ECE_lim above 0.01 at all four" was never computed
at W1, whose limit is 0.0031: at (5, 5) the limit sits within 0.004 of
tau at every score. Q3 read OVER, an indicator, as if it converged at
N = 512 everywhere; where p_lim sits within the replicate noise of tau
the indicator counts about half the replicates, and at W2's score 2
(gap 0.0016, mass 0.435) OVER reads 0.697 against a limit of 0.563.
Q3' was added after the second run and gates the cells whose every gap
on scores of mass above 0.01 exceeds 0.02. Q4's second clause gave a
0.01 band to a 0.0098 loss, so a zero loss would pass: it is printed
and decides nothing. Q4's first clause is read at S, W1, W2 and W3,
fixed in the code, where the sides agree (S lies off the census); its
band too exceeds the largest loss, so it reads convergence, never a
disagreement.
controls PC at N = 128: accuracy 0.8528 against ceiling 0.8539,
mean |p - posterior| 0.0177. W2: tau = (1, 11/15, 5/9, 3/7),
ceiling 419/728, p_lim = (0.9816, 0.8400, 0.5540, 0.4141).
S: p_lim(0) = 0.988393 = 1/(1 + e^{-40/9}).
limit at N = 512 every mean stated p within 0.02 of p_lim; ECE
against its limit ECE_lim: S 0.0870/0.0884 (0.0897, 0.0803,
0.0852 at N = 8, 32, 128: flat from the start, and below
the limit at N = 32 and 128, so (A)'s "floor" is a limit
and not a lower bound), W1
0.0132/0.0031, W2 0.0214/0.0162, W3 0.0358/0.0348.
W2's certain score c = 0 is stated 0.9816 in the limit;
its score 1 at 0.8400 against 11/15.
over OVER converges where the gaps are wide: S 0.881, 0.969,
1.000, 1.000 to its limit 1.000; W3 0.544, 0.672, 0.807,
0.925 to 0.933. Where they are not it is noise: W1 0.591
against 0.833, W2 0.697 against 0.563.
census over 2 <= a, b <= 30, 90 of 841 cells have a score whose
limit call takes the side tau does not (28 (cell, score)
pairs at an exact tie set aside); the largest limit loss is 11/1120 = 0.0098 at
(5, 12), score 1, where tau = 0.4898 and p_lim = 0.5019. A
disagreement needs tau near 1/2, where the two class masses
nearly tie, so in the depth column it is common and costs
little. Off the column that fails: a far support point
(member masses 0.45, 0.1, 0.45 at 0, 1, 10, non-member 0.2,
0.8 at 1, 5) puts tau(1) = 1/3 against p_lim(1) = 0.6483, an
exception costing 1/20 (Q4', added after run 3). At the four
named cells the call's accuracy at N = 512 equals the
ceiling to 0.0005. At (5, 12) it sits 0.0054 below:
p_lim is 0.0019 from 1/2 there, and N = 512 splits the call.
collapse at W3, N = 8: 0.055 against (C)'s 0.044, R = 400.
Rates over R = 400 read to about 0.025 at their largest.
[Read later, on a code read: Q4's first clause is gated at the four
fixed cells, never checked against the census's disagreeing list, so
their agreement is assumed there.]
RUN RECORD. python lira.py: run 1 stopped on an index error in the
control harness; run 2 3 of 5 (Q2's floor clause, Q3); run 3, the
frozen clauses printed as records and Q3' added, 5 of 5, 0.1 s, peak
commit 25.3 MB; run 4, with Q4', 6 of 6, 0.1 s; run 5, after an audit,
6 of 6, 0.1 s, 25.9 MB.
"""
import os
os.environ.setdefault("OPENBLAS_NUM_THREADS", "1")
import sys
import time
from fractions import Fraction as F
from math import comb, exp, pi, sqrt
import numpy as np
NS = (8, 32, 128, 512)
R = 400
CHECKS = []
def check(name, ok, detail=""):
CHECKS.append(bool(ok))
tag = "ok " if ok else "FAIL"
print(f" [{tag}] {name}" + (f" ({detail})" if detail else ""))
def section(title):
print()
print(title)
# -------------------------------------------------------------- worlds
def hg(M, K, w=3):
return [F(comb(K, c) * comb(M - K, w - c), comb(M, w))
for c in range(w + 1)]
class Cell:
"""A two-class score world on a finite support, exact throughout."""
def __init__(self, name, xs, Pm, Pn, wm):
self.name, self.xs = name, np.array(xs, dtype=float)
self.Pm, self.Pn, self.wm = Pm, Pn, F(wm)
self.Pu = [self.wm * m + (1 - self.wm) * n for m, n in zip(Pm, Pn)]
self.tau = [m / (m + n) if m + n else None for m, n in zip(Pm, Pn)]
self.ceiling = sum(max(m, n) for m, n in zip(Pm, Pn)) / 2
def mom(P):
mu = sum(x * p for x, p in zip(xs, P))
return float(mu), float(sum((x - mu) ** 2 * p
for x, p in zip(xs, P)))
self.mom_m, self.mom_n = mom(Pm), mom(Pn)
self.plim = stated(*self.mom_m, *self.mom_n, self.xs)
def live(self):
"""Support indices with audited mass."""
return [i for i, p in enumerate(self.Pu) if p > 0]
def depth(a, b):
T = a + b
return Cell(f"W({a},{b})", range(4), hg(T - 1, a - 1), hg(T - 1, a),
F(a, T))
def logpdf(o, mu, var):
"""Gaussian log density; a zero variance is the point mass."""
with np.errstate(divide="ignore", invalid="ignore"):
g = -(o - mu) ** 2 / (2 * var) - 0.5 * np.log(2 * pi * var)
at = np.isclose(o, mu)
return np.where(var > 0, g, np.where(at, np.inf, -np.inf))
def stated(mu1, v1, mu0, v0, o):
"""U-LiRA's p_member at scores o (broadcast over leading axes)."""
mu1, v1, mu0, v0 = (np.asarray(t, dtype=float)[..., None]
for t in (mu1, v1, mu0, v0))
l1, l0 = logpdf(o, mu1, v1), logpdf(o, mu0, v0)
tie = (l1 == l0) & np.isinf(l1)
with np.errstate(invalid="ignore", over="ignore"):
p = 1.0 / (1.0 + np.exp(l0 - l1))
return np.where(tie, 0.5, p)
def score(cell, p):
"""ACC, ECE and OVER of stated probabilities p over the support."""
acc, ece, over = 0.0, 0.0, 0.0
for i in cell.live():
pm, pn, pu, tau = (float(cell.Pm[i]), float(cell.Pn[i]),
float(cell.Pu[i]), float(cell.tau[i]))
call = p[..., i] > 0.5
acc = acc + np.where(call, pm, pn) / 2
ece = ece + pu * np.abs(p[..., i] - tau)
more = np.where(tau > 0.5, p[..., i] > tau,
np.where(tau < 0.5, p[..., i] < tau, False))
over = over + pu * more
return acc, ece, over
def rng_for(ci, N):
return np.random.default_rng([20260930, ci, N])
# ------------------------------------------------------------ sections
W1, W2, W3 = depth(5, 5), depth(12, 3), depth(2, 8)
S = Cell("S", (0, 3), [F(9, 10), F(1, 10)], [F(1, 10), F(9, 10)], F(1, 2))
def section_controls():
section("CONTROLS")
rng = np.random.default_rng([20260930, 0])
grid = np.linspace(-20, 25, 90001)
f1 = np.exp(-grid ** 2 / 2) / sqrt(2 * pi)
f0 = np.exp(-(grid - 3) ** 2 / 8) / sqrt(8 * pi)
ceil = float(np.sum(np.maximum(f1, f0)) * (grid[1] - grid[0]) / 2)
accs, maes = [], []
for _ in range(100):
s1, s0 = rng.normal(0, 1, 128), rng.normal(3, 2, 128)
e1, e0 = rng.normal(0, 1, 2000), rng.normal(3, 2, 2000)
o = np.concatenate([e1, e0])
p = stated(s1.mean(), s1.var(), s0.mean(), s0.var(), o)
true = 1 / (1 + (np.exp(-(o - 3) ** 2 / 8) / 2)
/ np.exp(-o ** 2 / 2))
accs.append(((p[:2000] > 0.5).mean() + (p[2000:] <= 0.5).mean()) / 2)
maes.append(np.abs(p - true).mean())
acc, mae = float(np.mean(accs)), float(np.mean(maes))
print(f" PC, N = 128: accuracy {acc:.4f} against ceiling {ceil:.4f}, "
f"mean |p - posterior| {mae:.4f}")
check("Q0 the fit calibrates where the model is right",
abs(acc - ceil) <= 0.02 and mae < 0.05)
ok = W2.tau == [F(1), F(11, 15), F(5, 9), F(3, 7)] \
and W2.ceiling == F(419, 728)
gap = max(abs(float(x) - y) for x, y in
zip(W2.plim, (0.982, 0.840, 0.554, 0.414)))
s_gap = abs(float(S.plim[0]) - 1 / (1 + exp(-40 / 9)))
print(f" W2: tau = {[str(x) for x in W2.tau]}, ceiling {W2.ceiling}, "
f"p_lim = {np.round(W2.plim, 4).tolist()}")
print(f" S: tau(0) = 9/10, p_lim(0) = {float(S.plim[0]):.6f}")
check("Q1 exact tau and ceiling at W2; p_lim at W2 and S",
ok and gap <= 0.001 and s_gap < 1e-12,
f"W2 gap {gap:.1e}, S gap {s_gap:.1e}")
def limits(cell):
ece = sum(float(cell.Pu[i]) * abs(float(cell.plim[i]) - float(cell.tau[i]))
for i in cell.live())
over = float(score(cell, cell.plim)[2])
return ece, over
def section_census():
section("THE CENSUS: does the limit call keep tau's side? "
"2 <= a, b <= 30")
bad, ties, worst, margin = [], 0, None, 1.0
for a in range(2, 31):
for b in range(2, 31):
c = depth(a, b)
loss = F(0)
for i in c.live():
tau = c.tau[i]
if tau == F(1, 2):
ties += 1
continue
margin = min(margin, abs(float(c.plim[i]) - 0.5))
if (c.plim[i] > 0.5) != (tau > F(1, 2)):
loss += abs(c.Pm[i] - c.Pn[i]) / 2
if loss:
bad.append((a, b, loss))
if worst is None or loss > worst[2]:
worst = (a, b, loss)
print(f" {len(bad)} of 841 cells disagree at some score; "
f"{ties} exact ties tau = 1/2 set aside; "
f"least |p_lim - 1/2| {margin:.2e}")
if worst:
print(f" the largest limit loss: W{worst[:2]}, loss {worst[2]} = "
f"{float(worst[2]):.4f}")
print(" disagreeing cells: " + ", ".join(
f"({a},{b})" for a, b, _ in bad[:40])
+ (" ..." if len(bad) > 40 else ""))
far = Cell("FAR", [0, 1, 5, 10], [F(45, 100), F(1, 10), F(0), F(45, 100)],
[F(0), F(2, 10), F(8, 10), F(0)], F(1, 2))
tau1, p1 = far.tau[1], float(far.plim[1])
cost = abs(far.Pm[1] - far.Pn[1]) / 2
print(f" off the depth column, a far support point: tau(1) = {tau1}, "
f"p_lim(1) = {p1:.4f}, exception cost {cost}")
check("Q4' a far support point puts an exception at a score far from a tie",
tau1 == F(1, 3) and p1 > 0.5)
return bad, worst
def run(cell, ci):
rows = {}
for N in NS:
rng = rng_for(ci, N)
pm = np.array([float(x) for x in cell.Pm])
pn = np.array([float(x) for x in cell.Pn])
sm = rng.choice(cell.xs, size=(R, N), p=pm / pm.sum())
sn = rng.choice(cell.xs, size=(R, N), p=pn / pn.sum())
p = stated(sm.mean(1), sm.var(1), sn.mean(1), sn.var(1), cell.xs)
acc, ece, over = score(cell, p)
collapse = float(((sm.var(1) == 0) | (sn.var(1) == 0)).mean())
rows[N] = (float(acc.mean()), float(ece.mean()), float(over.mean()),
collapse, p.mean(0))
return rows
def section_tool(worst):
section("THE TOOL: R = 400 replicates per shadow count, scored exactly")
cells = [S, W1, W2, W3]
if worst:
cells.append(depth(worst[0], worst[1]))
q2, q3, q4 = True, True, True
floor_ok, q3_frozen, q4_vacuous = True, True, None
for ci, c in enumerate(cells, start=1):
e_lim, o_lim = limits(c)
print(f" == {c.name}: ceiling {c.ceiling} = {float(c.ceiling):.4f}, "
f"ECE_lim {e_lim:.4f}, over-confident mass {o_lim:.3f}")
print(" N ACC ECE OVER COLLAPSE")
rows = run(c, ci)
for N in NS:
acc, ece, over, col, _ = rows[N]
print(f" {N:4d} {acc:.4f} {ece:.4f} {over:.3f} "
f"{col:.3f}")
mean_p = rows[512][4]
print(" score P_u tau p_lim mean p at N = 512")
for i in c.live():
print(f" {c.xs[i]:.0f} {float(c.Pu[i]):.3f} "
f"{float(c.tau[i]):.4f} {float(c.plim[i]):.4f} "
f"{mean_p[i]:.4f}")
acc, ece, over = rows[512][:3]
gap = min(abs(float(c.plim[i]) - float(c.tau[i]))
for i in c.live() if c.Pu[i] > F(1, 100))
if ci <= 4:
q2 &= all(abs(mean_p[i] - float(c.plim[i])) <= 0.02
for i in c.live() if c.Pu[i] > F(1, 100))
q2 &= abs(ece - e_lim) <= 0.015
floor_ok &= e_lim > 0.01
q3_frozen &= abs(over - o_lim) <= 0.05
if gap > 0.02:
q3 &= abs(over - o_lim) <= 0.05
q4 &= abs(acc - float(c.ceiling)) <= 0.01
print(f" least |p_lim - tau| on scores of mass above 0.01: "
f"{gap:.4f}")
else:
q4_vacuous = abs((float(c.ceiling) - acc)
- float(worst[2])) <= 0.01
print(f" ceiling - ACC at N = 512: "
f"{float(c.ceiling) - acc:.4f} against the limit loss "
f"{float(worst[2]):.4f}")
check("Q2 at N = 512 the stated p sits at p_lim (0.02) and ECE at its "
"limit (0.015)", q2)
print(f" Q2 as frozen also asked ECE_lim above 0.01 at all four: "
f"{'holds' if floor_ok else 'FAILS'} (record, not gated)")
print(f" Q3 as frozen, OVER within 0.05 of its limit at all four: "
f"{'holds' if q3_frozen else 'FAILS'} (record, not gated)")
check("Q3' (after run 2) OVER within 0.05 of the limit's "
"over-confident mass where every gap on scores of mass above "
"0.01 exceeds 0.02", q3)
check("Q4 the call reaches the ceiling at the four cells, and the "
"census finds a disagreeing cell", q4 and worst is not None)
q4_word = {None: "not run", True: "holds", False: "FAILS"}[q4_vacuous]
print(f" Q4 as frozen also asked the loss at the worst cell within "
f"0.01: {q4_word}, and the 0.01 band "
f"holds a zero loss too (record, not gated)")
def main():
t0 = time.time()
section_controls()
if not all(CHECKS):
print("\nCONTROL FAILED: nothing below is read.")
sys.exit(1)
_, worst = section_census()
section_tool(worst)
print()
print(f"{sum(CHECKS)} of {len(CHECKS)} checks, "
f"{time.time() - t0:.1f} s")
sys.exit(0 if all(CHECKS) else 1)
if __name__ == "__main__":
main()