Privacy-Preserving Learning

In two lessons, what was measured was what the model did to the outside, that is, to the subscribers it is applied to. What the model leaks to the inside, that is, toward the records it was trained on, was not asked. If the output of the model changes when a subscriber in the training set enters the table, that output carries something about that subscriber. The size of what it carries can be measured.

This lesson makes that measurement and is limited to two questions. The first: does deleting the subscriber ID from a table make that subscriber invisible. The second: how much does removing a single record move the output of the model, and what is the cost in accuracy of masking that movement. What personal data is, the retention period and the limit of the analysis were measured in the Detection, Response and Compliance course and in The Structure of Data topic of the Introduction to Data Analytics course; they are not repeated. What is measured here is only the behavior of the model and the table themselves.

• ER17. The set, split, model and subgroup definitions carry over unchanged from the previous two lessons: a training set of 756 rows, a held-out set of 504 subscribers, thirteen subgroups, baseline 0.7857.
• ER18. The table is taken to be anonymized: there is no subscriber ID column. The remaining fields are ordinary fields that come from the measurement and from the subscriber record.
• ER19. The measure of joinability is how many records stand alone in their own field combination. This is not an identification procedure but a count made on the table itself.
• ER20. A second model is built for comparison: the cell table. The four subgroup axes give one cell, and the share of suspicious cases in the cell is the output. It is a small and weak model; its job here is to show how an output that by its structure rests on few records behaves.
• ER21. Record sensitivity is the largest movement seen in the output of the model on the held-out set when a single training record is removed. Since every measurement on the linear model asks for a retraining, sixteen records are sampled; on the cell model all 756 records are computed exactly.
• ER22. Adding noise is adding a number to the published output with equal probability in the negative and positive direction. The noise scale is swept over ten levels and at each level it is drawn twenty times and averaged.
• ER23. A “record above the noise” is a record whose trace exceeds the largest value the noise scale can take. As the number falls, the share of individual records in the output stays inside the noise.
• ER24. The measurement is entirely on the defense side: no inference procedure is built, only the quantities to be protected are counted.

What Deleting the ID Deletes

The first question is asked of the table before the model. When the subscriber ID is deleted, how many records does the combination of the remaining fields leave alone. The block below adds the fields one by one and counts at each step how many separate combinations form and how many records stand alone in their combination.

# privacy.py — MODEL: The same FICTIONAL subscriber table, the same seed and the same split;
# what is measured is on the defense side: the behavior of the table and the model themselves.
import math
import statistics

SEED, RAW, M32 = 20260218, 1400, 0xFFFFFFFF
REGION = [("north", 0.28, 21, 0.00), ("south", 0.22, 17, -0.10),
          ("east", 0.18, 26, 0.30), ("west", 0.14, 14, -0.05),
          ("central", 0.18, 23, 0.05)]


def rng(t):
    x = ((t ^ (t >> 16)) * 2246822507) & M32
    x = ((x ^ (x >> 13)) * 3266489909) & M32
    s = [(x ^ (x >> 16)) & M32]

    def next_value():
        s[0] = (s[0] * 1664525 + 1013904223) & M32
        return s[0] / 4294967296
    return next_value


def pick(u, w):
    t = 0.0
    for i, x in enumerate(w):
        t += x
        if u < t:
            return i
    return len(w) - 1


SUBSCRIBERS, DATA = [], []
for i in range(RAW):
    r = rng(SEED + i)
    b = REGION[pick(r(), [x[1] for x in REGION])]
    household = 1 + pick(r(), [0.06, 0.24, 0.30, 0.24, 0.11, 0.05])
    rating = 1 + pick(r(), [0.08, 0.14, 0.27, 0.34, 0.17])
    if r() >= 0.046:
        SUBSCRIBERS.append({"id": 10001 + i, "region": b, "household": household,
                            "satisfaction": rating})
for k in SUBSCRIBERS:
    r, v = rng(SEED + 7000 + k["id"]), []
    for n in range(pick(r(), [0.05, 0.12, 0.21, 0.62])):
        v.append(0.0 if r() < 0.038 else math.floor(
            k["region"][2] * math.exp((r() + r() + r() - 1.5) * 0.62)
            * (1 - n * 0.05) * 100 + 0.5) / 100)
        r()
    if not v:
        continue
    mean, vol, r = sum(v) / len(v), max(v) - min(v), rng(SEED + 51000 + k["id"])
    z = (0.052 * (mean - 20) + 0.85 * (min(v) == 0.0) + 0.026 * vol
         + 0.24 * (k["household"] >= 5) - 0.20 * (k["satisfaction"] >= 4) + k["region"][3]
         + 0.9 * (k["id"] - 10001) / 1399 + (r() + r() + r() - 1.5) * 1.30)
    x = {"household": k["household"], "satisfaction": k["satisfaction"], "period": len(v),
         "mean_consumption": round(mean, 2), "volatility": round(vol, 2),
         "region_name": k["region"][0], "zero_readings": int(min(v) == 0.0),
         "suspicious": int(z > 1.35)}
    x["per_person"] = round(x["mean_consumption"] / x["household"], 3)
    for b in REGION:
        x["area_" + b[0]] = int(k["region"][0] == b[0])
    DATA.append(x)


def shuffle(data, seed):
    r, s = rng(seed), list(range(len(data)))
    for i in range(len(s) - 1, 0, -1):
        j = int(r() * (i + 1))
        s[i], s[j] = s[j], s[i]
    return [data[i] for i in s]


K = shuffle(DATA, SEED + 90000)
TRAIN, HELD_OUT = K[:756], K[756:]
FIELDS = ["mean_consumption", "volatility", "household", "satisfaction", "period",
          "zero_readings", "per_person", "area_north", "area_south", "area_east",
          "area_west", "area_central"]
MEAN = {a: statistics.fmean(x[a] for x in TRAIN) for a in FIELDS}
STD = {a: max(1e-9, statistics.pstdev([x[a] for x in TRAIN])) for a in FIELDS}


def scaled(x):
    return [1.0] + [(x[a] - MEAN[a]) / STD[a] for a in FIELDS]


def squash(z):
    if z >= 0:
        return 1.0 / (1.0 + math.exp(-z)) if z < 700 else 1.0
    e = math.exp(z) if z > -700 else 0.0
    return e / (1.0 + e)


def train_model(rows, label):            # MODEL: linear model, gradient descent
    X = [scaled(x) for x in rows]
    Y = [x[label] for x in rows]
    w = [0.0] * len(X[0])
    for _ in range(200):
        g = [0.0] * len(w)
        for i in range(len(X)):
            h = squash(sum(w[j] * X[i][j] for j in range(len(w)))) - Y[i]
            for j in range(len(w)):
                g[j] += h * X[i][j]
        for j in range(len(w)):
            w[j] -= 0.3 * g[j] / len(X)
    return w


def probability(w, x):
    return squash(sum(a * b for a, b in zip(w, scaled(x))))


from collections import Counter, defaultdict


def groups(x):
    t = 10 if x["mean_consumption"] <= 10 else 25 if x["mean_consumption"] <= 25 else 40
    return ["region " + x["region_name"], "tariff %d" % t,
            "household " + ("1-2" if x["household"] <= 2 else "3-4" if x["household"] <= 4 else "5+"),
            "readings " + ("few" if x["period"] <= 2 else "full")]


FIELD_NAMES = ["region", "tariff tier", "household size", "reading count",
               "satisfaction", "mean consumption"]


def key_of(x, k):                        # the first k fields of the anonymized record
    return tuple((groups(x) + [x["satisfaction"], x["mean_consumption"]])[:k])


print(f"records {len(DATA)}, subscriber ID not in the table, subgroups examined "
      f"{len({g for x in HELD_OUT for g in groups(x)})}")
print(f"{'field':>5} {'added field':<18}{'combinations':>14}{'lone records':>14}{'share':>9}")
for k in range(1, 7):
    c = Counter(key_of(x, k) for x in DATA)
    single = sum(1 for x in DATA if c[key_of(x, k)] == 1)
    print(f"{k:>5} {FIELD_NAMES[k - 1]:<18}{len(c):>14}{single:>14}{single / len(DATA):>9.4f}")

records 1260, subscriber ID not in the table, subgroups examined 13
field added field         combinations  lone records    share
    1 region                         5             0   0.0000
    2 tariff tier                   15             1   0.0008
    3 household size                41             4   0.0032
    4 reading count                 72             6   0.0048
    5 satisfaction                 247            69   0.0548
    6 mean consumption            1251          1242   0.9857

The first four rows are the subgroup axes of the course and are coarse fields: 1,260 records fall into only 72 combinations, and the lone records number 6. The fifth field raises this number to 69. The sixth field, that is, mean consumption, which carries two digits after the decimal point, splits the table into 1,251 combinations in a single step, and 0.9857 of the records stand alone in their own combination.

What is to be read is not the size of the last row but the jump from the fourth row to the sixth. De-identification deletes a column; it does not delete joinability. The number and the resolution of the fields in a table determine how anonymized that table is more than the presence of the ID does. Rounding a continuous field to a tier lowers this number directly, and the cost of that is the detail the model sees.

The Trace a Single Record Leaves

The second question is asked of the model. When a training record is removed and the model is retrained, how much does the output on the held-out set move. The block below measures this on two models: the twelve-column linear model and the cell table given by the four axes. For the second model the measurement can be made exactly, because removing a record changes only the rate of its own cell.

def cell(x):
    return tuple(groups(x))


COUNT = defaultdict(lambda: [0, 0])      # MODEL: cell table, states the rate of the cell
for x in TRAIN:
    h = COUNT[cell(x)]
    h[0], h[1] = h[0] + 1, h[1] + x["suspicious"]
TRAIN_RATE = sum(x["suspicious"] for x in TRAIN) / len(TRAIN)
HELD_CELLS = Counter(cell(x) for x in HELD_OUT)


def cell_rate(x):
    v = COUNT.get(cell(x))
    return TRAIN_RATE if v is None else v[1] / v[0]


D, flipped = [], 0
for x in TRAIN:
    n, k = COUNT[cell(x)]
    q = (k - x["suspicious"]) / (n - 1) if n > 1 else TRAIN_RATE
    D.append(abs(k / n - q))
    if (k / n > 0.5) != (q > 0.5):
        flipped = max(flipped, HELD_CELLS[cell(x)])
D.sort(reverse=True)
W = train_model(TRAIN, "suspicious")
P0 = [probability(W, x) for x in HELD_OUT]
r = rng(SEED + 71000)
TRACE = []
for _ in range(16):
    x = TRAIN[int(r() * len(TRAIN))]
    w = train_model([y for y in TRAIN if y is not x], "suspicious")
    P1 = [probability(w, y) for y in HELD_OUT]
    TRACE.append((max(abs(a - b) for a, b in zip(P0, P1)),
                  sum((a > 0.5) != (b > 0.5) for a, b in zip(P0, P1))))
TRACE.sort(reverse=True)
held_base = sum(x["suspicious"] == 0 for x in HELD_OUT) / len(HELD_OUT)
print(f"cells {len(COUNT)}, smallest cell size {min(v[0] for v in COUNT.values())}, "
      f"single-record cells {sum(1 for v in COUNT.values() if v[0] == 1)}, "
      f"two or fewer {sum(1 for v in COUNT.values() if v[0] <= 2)}")
print(f"baseline {held_base:.4f}, left-out records {len(TRACE)} (linear), {len(D)} (cell)")
print(f"\n{'model':<22}{'accuracy':>10}{'largest trace':>15}{'median trace':>14}"
      f"{'changed predictions':>21}")
print(f"{'linear model':<22}"
      f"{sum((p > 0.5) == x['suspicious'] for p, x in zip(P0, HELD_OUT)) / len(HELD_OUT):>10.4f}"
      f"{TRACE[0][0]:>15.4f}{TRACE[len(TRACE) // 2][0]:>14.4f}{max(v[1] for v in TRACE):>21}")
print(f"{'cell model':<22}"
      f"{sum((cell_rate(x) > 0.5) == x['suspicious'] for x in HELD_OUT) / len(HELD_OUT):>10.4f}"
      f"{D[0]:>15.4f}{D[len(D) // 2]:>14.4f}{flipped:>21}")

cells 66, smallest cell size 1, single-record cells 13, two or fewer 22
baseline 0.7857, left-out records 16 (linear), 756 (cell)

model                   accuracy  largest trace  median trace  changed predictions
linear model              0.8194         0.0313        0.0030                    2
cell model                0.7917         0.7778        0.0074                   14

The difference between the two rows approaches twenty-five times. In the linear model, removing a record moves the probability by no more than 0.0313 for any of the 504 subscribers and changes at most two predictions; the median trace is 0.0030, that is, more than half of the records leave almost no trace in the output. The reason is that the model produces every output from all 756 records; the share of a single row is spread over thirteen weights.

On the cell model the same measurement gives 0.7778. The reason is the numbers at the start of the second line: 13 of the 66 cells hold a single record, and 22 hold two or fewer. In a single-record cell, the published rate is the label of that single record itself. When the decision of that cell is flipped, the prediction of 14 subscribers in the held-out set changes. The rule follows from here and is independent of the model: the fewer records an output rests on, the more exposed those records are in that output. The same number is the other face of the small subgroup warning in the previous lesson — a subgroup too small to be measured is also a subgroup too small to be hidden.

The Cost of Noise

The direct way to shrink the trace is to add noise to the published output. Noise masks the trace but also takes accuracy away. The sweep below prints side by side, at ten noise levels, the accuracy of the two models and the number of records that leave a trace above that level.

print(f"\n{'noise':>8}{'linear accuracy':>17}{'cell accuracy':>15}"
      f"{'linear above':>14}{'cell above':>12}")
for b in (0.00, 0.02, 0.04, 0.08, 0.12, 0.20, 0.30, 0.45, 0.60, 0.80):
    lin_acc = cell_acc = 0.0
    for t in range(20):                  # the noise is drawn twenty times, the mean is printed
        rd = rng(SEED + 74000 + t * 13)
        lin_acc += sum(((p + b * (2 * rd() - 1)) > 0.5) == x["suspicious"]
                       for p, x in zip(P0, HELD_OUT)) / len(HELD_OUT)
        rc = rng(SEED + 75000 + t * 13)
        noisy = {h: min(1.0, max(0.0, v[1] / v[0] + b * (2 * rc() - 1)))
                 for h, v in COUNT.items()}
        cell_acc += sum((noisy.get(cell(x), TRAIN_RATE) > 0.5) == x["suspicious"]
                        for x in HELD_OUT) / len(HELD_OUT)
    print(f"{b:>8.2f}{lin_acc / 20:>17.4f}{cell_acc / 20:>15.4f}"
          f"{sum(1 for v, _ in TRACE if v > b):>14}{sum(1 for v in D if v > b):>12}")

   noise  linear accuracy  cell accuracy  linear above  cell above
    0.00           0.8194         0.7917            16         679
    0.02           0.8184         0.7792             1         246
    0.04           0.8172         0.7792             0         140
    0.08           0.8151         0.7792             0          59
    0.12           0.8126         0.7780             0          34
    0.20           0.8043         0.7696             0          25
    0.30           0.7910         0.7584             0          12
    0.45           0.7560         0.7265             0          11
    0.60           0.6908         0.6779             0           1
    0.80           0.6436         0.6188             0           0

For the linear model the account is cheap. None of the sixteen records leaves a trace above 0.04 noise, and at that level accuracy falls from 0.8194 to 0.8172, that is, by 0.0022 — still 0.0315 above the baseline. When the noise scale is raised to 0.30, accuracy drops to 0.7910, just above the baseline, and at 0.45 to 0.7560, below the baseline. That is, the whole of the cost comes not from the masking but from masking more than necessary.

On the cell model the same account cannot be paid. To mask the largest trace, the noise scale has to be raised to 0.80; at that level accuracy is 0.6188 and 0.1669 below the baseline. Worse, the model falls to 0.7792 already at 0.02 noise and drops below the baseline — because its noiseless form was exceeding the baseline by only 0.0060. A model with no margin to spend cannot cover the cost of the noise.

Read together, the two columns give the result of the lesson. The cost of privacy is not a fixed number; it depends on the structure of the model and on how far above the baseline it stands. A model that produces its output from many records and clears the baseline comfortably can mask the trace of individual records almost for free. A model that produces its output from few records and sticks to the baseline can buy the same protection only by making itself useless.

Summary

• In a 1,260-row table with the subscriber ID deleted, four coarse fields produce 72 combinations and 6 records stand alone; when the sixth field is added, the records standing alone rise to 1,242, that is, to 0.9857.
• De-identification deletes a column, it does not delete joinability; what decides is the number and the resolution of the fields.
• Removing a single training record moves the output of the linear model by at most 0.0313 and changes two predictions; the median trace is 0.0030.
• The same measurement gives 0.7778 on the cell model and changes 14 predictions, because 13 of the 66 cells hold a single record: the fewer records an output rests on, the more exposed those records are in that output.
• The cost of noise varies with the model: on the linear model masking the trace asks for 0.04 noise and 0.0022 of accuracy, while on the cell model it asks for 0.80 noise and falling 0.1669 below the baseline.

Next Step

In three lessons the harm was measured in three separate forms and in each one an item to be reduced was found: the source of the bias was separated, a fairness criterion was chosen and the cost of the choice was counted, the record trace was measured and masked with noise. None of what was measured has so far reached the person who will use the model. How will someone who has not seen the three tables in this lesson know, when they take over the model, which subgroups were not measured, which fairness criterion was chosen with which threshold, and whether noise was added to the output. The next lesson turns this question into a number: of the set of questions the person taking over the model can ask, how many are closed by a written statement and which remain unanswered.