Frequent Patterns and Fairness: Apriori, FP-Growth and Adversarial Debiasing
Four tutorial questions, in the order of the worksheet. Each brings in the lecture material it needs where it is needed; a recap of both lectures follows at the end.
Question 1 · Contrast data mining lecture, pages 11–48
Q1 · Frequent itemsets with Apriori and FP-growth
Problem statement
A database has five transactions. Let min sup = 60% and min conf = 80%.
TID
items bought
T100
{M, O, N, K, E, Y}
T200
{D, O, N, K, E, Y}
T300
{M, A, K, E}
T400
{M, U, C, K, Y}
T500
{C, O, O, K, I, E}
Find all frequent itemsets using Apriori and FP-growth, respectively. Compare the efficiency of the two mining processes.
The five transactions spell MONKEY, DONKEY, MAKE, MUCKY and COOKIE. An item counts once per transaction, so the second O in COOKIE adds nothing.
Q1 · Background · Contrast data mining lecture, pages 3–14
What the question is about: finding items that occur together
Picture a shop's till receipts. Each receipt is a transaction: the set of items bought together. Frequent itemset mining asks which combinations of items appear on many receipts.
These combinations are the raw material for two later results. Association rules, "customers who buy X also buy Y", come in Question 2. Contrast patterns are itemsets whose frequency changes between two datasets, such as yesterday's and today's network traffic (pages 3–10 and 49).
Where frequent itemsets are used
Retail
Products bought together drive recommendations, shelf layout and promotions (Question 2).
Network security
Common combinations of source, destination, port and size summarise thousands of flows into a short report (pages 7–8).
Contrast mining
Compare two datasets and report the itemsets whose support jumped: what changed today? (page 49, A1)
IllustrativeThe question's data: five words become five transactions
A transaction is a set: order does not matter and repeats count once, so COOKIE contributes \(\{c, o, k, i, e\}\). Items shared by many transactions, like \(k\), are candidates for frequent itemsets.
Why this is hard. With \(d\) distinct items, every non-empty subset is a possible itemset:
$$\#\text{itemsets} = 2^d - 1 .$$
Counting every one of them against the database is hopeless beyond a handful of items.
LiveHow fast the search space grows
This question has \(d = 11\) distinct letters. A real shop has thousands of products: with \(10^4\) frequent single items, Apriori would already need about \(5 \times 10^7\) candidate pairs (page 14).
Strategy 1 · generate and test (Apriori)
Build candidate itemsets one size at a time, count them with a database scan, and skip any candidate that cannot be frequent.1
Strategy 2 · grow without candidates (FP-growth)
Compress the database into a tree once, then grow patterns only from paths that actually occur.2
How the question fits
Given5 transactions; min sup 60%, so a count of at least 3
Askedevery frequent itemset, found twice (Apriori and FP-growth), then a comparison of the work each does
Not neededmin conf 80%: confidence belongs to rules (Question 2), not itemsets
\(X\) is frequent when its support reaches min sup. Here \(|D| = 5\), so 60% means a count of at least 3.
Adding items to a set can only shrink the transactions that contain it. So if an itemset is infrequent, every superset is infrequent too: the Apriori principle. Apriori uses it to skip candidates without counting them.1
LiveThe itemset lattice of the five frequent single items
frequentcounted, infrequentpruned: a subset is infrequent, never counted
Each node shows an itemset over \(\{k, e, m, o, y\}\) and its count. Lower min sup and the frequent region grows upwards; raise it and whole branches above an infrequent set disappear without being counted.
Warm-up exercise · counting support
1. With min sup = 60%, the smallest count a frequent itemset can have:
2. The count of \(\{o\}\):
3. The support of \(\{k, e\}\), as a fraction:
Show solution
\(0.6 \times 5 = 3\). \(\{o\}\) is in T100, T200 and T500: count 3. \(\{k, e\}\) is in T100, T200, T300 and T500: \(4/5 = 0.8\).
Bridge to the question. Apriori counts candidate itemsets level by level; FP-growth counts nothing it has not seen. The same three facts drive both.
Q1 · Guided activity · pages 12–14
Apriori, level by level
How many candidates does Apriori count, and how many database scans does it need?
Each level \(k\) generates candidates \(C_k\) by joining frequent \((k-1)\)-itemsets, prunes any candidate with an infrequent subset, scans the database to count the rest, and keeps the frequent ones as \(L_k\).
LiveApriori on the five transactions
\(\{k, e, y\}\) is joined from \(\{k, e\}\) and \(\{k, y\}\), but its subset \(\{e, y\}\) has count 2. The prune step discards it before the third scan, so \(C_3 = \{\{o, k, e\}\}\). (The answer sheet lists \(\{k, e, y\}\) with its count, 2; the result is the same.)
Q1 · Guided activity · pages 15–34
Building the FP-tree
FP-growth scans the database twice. Scan 1 counts single items and orders the frequent ones by count: \(k{:}5,\ e{:}4,\ m{:}3,\ o{:}3,\ y{:}3\). Scan 2 sorts each transaction in that order and inserts it as a path from the root, sharing the prefix it has in common with earlier transactions.2
LiveInsert the ordered transactions one at a time
Dashed links (the header table's node-links) join every node of the same item; FP-growth follows them in the next step. Each count is the number of transactions that share the path down to that node.
Q1 · Guided activity · pages 35–47
Mining the FP-tree
For each item, from the bottom of the header table up: collect the prefix paths that lead to its nodes (its conditional pattern base), keep the items that are frequent within it (its conditional FP-tree), and add the item to every pattern grown from that tree.
LivePick an item to see its prefix paths
LiveAll four items, as in the answer sheet
Q1 · Interpretation · pages 14 and 48
Comparing the work done
Apriori
FP-growth
LiveOn a larger random database: candidates Apriori counts as min sup falls
200 random transactions over 20 items with skewed item popularity. FP-growth always scans twice and generates no candidates; Apriori's candidate count grows fastest exactly when patterns get long, at low support.
\(C_3\): oke (key is pruned: ey is infrequent), so \(L_3\): oke:3
FP-growth: the tree \(\text{root} \to k{:}5\) with branches \(e{:}4 \to m{:}2 \to o{:}1 \to y{:}1\), \(e{:}4 \to o{:}2 \to y{:}1\), and \(k \to m{:}1 \to y{:}1\). Mining it:
item
conditional pattern base
conditional tree
frequent patterns
y
{k,e,m,o:1}, {k,e,o:1}, {k,m:1}
k:3
{k,y:3}
o
{k,e,m:1}, {k,e:2}
k:3, e:3
{k,o:3}, {e,o:3}, {k,e,o:3}
m
{k,e:2}, {k:1}
k:3
{k,m:3}
e
{k:4}
k:4
{k,e:4}
Both give the same 11 frequent itemsets: the five single items, the five pairs, and \(\{k, e, o\}\).
Efficiency: Apriori scans the database once per level (three scans here) and generates candidates by an expensive self-join; FP-growth builds the FP-tree in two scans and generates no candidates.
The price of each item in a store is nonnegative. The store manager is only interested in patterns of the form: "one free item may trigger $200 total purchases in the same transaction". State how to mine such patterns efficiently.
Q2 · Background
What the question is about: rules that answer a business question
Question 1 found itemsets. A shop acts on association rules \(A \Rightarrow B\): "transactions that contain \(A\) also tend to contain \(B\)". A rule is judged by two numbers. Its support, \(\operatorname{support}(A \cup B)\), says how often it applies. Its confidence says how reliable it is:
$$\operatorname{conf}(A \Rightarrow B) = \frac{\operatorname{support}(A \cup B)}{\operatorname{support}(A)} ,$$
the fraction of transactions containing \(A\) that also contain \(B\). This is where a "min conf" threshold is used.
Unconstrained mining returns thousands of rules. The manager here has a specific promotion question: if we give an item away free, do customers then spend at least $200 in the same visit? Constraint-based mining reports only rules of that shape, and, if the constraint is pushed into the miner, finds them with less work.3
IllustrativeThe anatomy of one wanted rule
one free item
mug $0
⇒
items totalling at least $200
headphones $150speaker $120
total $270 \(\ge\) $200
frequent? \(\operatorname{support}(\{\text{mug, headphones, speaker}\}) \ge\) min supreliable? \(\operatorname{conf} \ge\) min conf
How the question fits
Giventransactions, item prices (all nonnegative), min sup and min conf
Askeda method, not numbers: how to mine "free item ⇒ total \(\ge\) $200" patterns efficiently
The catchthe price condition behaves the opposite way to support as itemsets grow
The catch: a monotone constraint cannot prune. An itemset below $200 may still have supersets above it, so it must not be thrown away.
Warm-up exercise · which way does a constraint point?
Five items cost $0 (a free mug), $15, $40, $120 and $150.
1. \(\{\$120, \$150\}\) totals $270. What fraction of its supersets also reach $200?
2. \(\{\$150\}\) fails "≥ $200". How many of its supersets that add one item pass it?
Show solution
1: all of them, fraction 1, because the constraint is monotone.
2: adding the mug, cable, charger or speaker gives $150, $165, $190 and $270, so only 1 passes. With two extra items, \(\{\$150, \$40, \$15\}\) totals $205 and passes too. \(\{\$150\}\) failing the constraint said nothing about its supersets: it cannot be pruned.
Bridge to the question. Support prunes from below; the price constraint can only be confirmed from above. The efficient method has to use each in its own direction.
Q2 · Guided activity
Two regions of the lattice
Where do the patterns the manager wants live? What does Apriori lose if it filters by price as it goes?
A small shop: a free mug, plus headphones ($150), a speaker ($120), a charger ($40), a case ($30) and a cable ($15), in eight transactions.
IllustrativeFrequent itemsets sit at the bottom, expensive ones at the top
frequent, total below thresholdfrequent and total ≥ threshold (wanted)infrequentwanted but never generated
Frequency is closed downwards and the price condition upwards: the wanted patterns are where the two regions overlap. Discarding cheap itemsets during Apriori removes the very building blocks, \(\{\text{headphones}\}\) and \(\{\text{speaker}\}\), from which the expensive pair is joined.
Q2 · Guided activity
From itemsets to "free item ⇒ $200" rules
IllustrativeThe three steps of the answer, on the shop's transactions
Answer to Q2
Find the set of frequent "free" 1-itemsets. Call it \(S_1\).
Generate the set of frequent itemsets whose price is at least $200, using FP-growth. Call it \(S_2\).
The price constraint is monotone, so we need not generate-and-test at every iteration: once a frequent itemset reaches $200, any superset does too, and only its frequency needs checking.
FP-growth rather than Apriori: Apriori discards frequent itemsets whose price is below $200 and so cannot discover their supersets that satisfy the constraint. FP-growth keeps all the information about the database in its tree.
Find the frequent itemsets in \(S_1 S_2\): a free item from \(S_1\) together with an itemset from \(S_2\).
Generate patterns of the form \(S_1 \Rightarrow S_2\) from them that meet the minimum confidence.
Q3 · Mitigating bias by annotating and balancing subgroups
Problem statement
One common approach in mitigating bias adopted by many companies and organizations would be to annotate different subclasses (i.e., light-skinned females, males with hats, etc.) within the training data, and then manually even out the data with respect to these groups. What are the major issues with such solutions?
Q3 · Background · Lecture 22, slides 3–5 and 18–22
What the question is about: fixing biased training data by hand
A model learns from its training data. If some kinds of people are rare in it, the model sees few examples of them and tends to work worse for them. This is representation bias (slides 18–19).
It causes real harm. Commercial face-analysis systems were 88–94% accurate overall, but up to 34 percentage points worse on darker-skinned women than on lighter-skinned men (slide 5).
A common industrial fix works on the data before training (pre-processing, slides 21–22). Label every training image with the attributes that might matter (skin tone, gender, hat, glasses, …), then even out the subgroups by collecting more, over-sampling or down-sampling until each is equally represented.
IllustrativeWhere the fix sits in the pipeline
Collect data→Annotate subgroups→Even out the groups→Train→Evaluate per group
The question is about the two highlighted steps. They sound reasonable, since they target the cause, the data. The question asks what goes wrong when they meet a real dataset.
How the question fits
Giventhe procedure: annotate subclasses such as "light-skinned females" or "males with hats", then manually balance them
Askedthe major issues with it
Kind of answerreasoning, not computation; the answer sheet names two issues
Representation bias: some groups are rare in the training data, so the model learns them poorly. Open Images and ImageNet draw about a third to a half of their images from the US (slide 19).
The worst-served groups are often intersections. In Gender Shades, IBM's classifier was 99.7% accurate on lighter-skinned men but 65.3% on darker-skinned women, while its overall accuracy hid the gap (slide 5).5
Lecture dataAccuracy by intersectional group (Gender Shades, slide 5)
Warm-up exercise · how many groups?
1. Six skin tones, two genders, hat or not, glasses or not. How many subgroups must be balanced?
2. How many labels must annotators write for 100 000 images and these 4 attributes?
Show solution
\(6 \times 2 \times 2 \times 2 = 48\) subgroups, and \(100\,000 \times 4 = 400\,000\) labels. One more attribute with 3 values triples the subgroups to 144 and adds 100 000 labels.
Bridge to the question. Both numbers grow with every attribute you think of, and the attributes you do not think of are not balanced at all.
Q3 · Guided activity
The subgroup explosion
Add attributes one by one. What happens to the number of groups, the rarest group, and the balanced dataset?
IllustrativeA face dataset of 100 000 images with realistic skews
attributes annotated · count (log scale)
subgroups to balanceimages in the rarest subgroupbalanced dataset (every subgroup cut to the rarest)
Attribute frequencies are assumptions for illustration, treated as independent. Balancing here means down-sampling every subgroup to the size of the rarest one.
Q3 · Extension · Lecture 22, slides 27–29
Learning what is rare instead of annotating it
DBVAE avoids the annotation step.6 A variational autoencoder maps each face \(x\) to a latent code \(z(x)\); a histogram \(\hat Q\) of the codes shows which faces are common, and rare ones are sampled more often during training (slide 28):
IllustrativeOne latent variable: a common mode and a rare mode
training data \(\hat Q(z)\)what a training batch sees after resampling
Small \(\alpha\) equalises the latent space; large \(\alpha\) makes the weights uniform and turns debiasing off. No one had to name the rare feature.
Answer to Q3
This approach has two major disadvantages:
It requires annotating massive amounts of data, which is not scalable. Every image needs a label for every attribute, and the subgroups multiply with each attribute added.
It requires knowing in advance which biases to look for (race, gender, pose, occlusion, hats, glasses, …). Manual annotation may not capture all the features that are imbalanced in the training data; any attribute not annotated stays unbalanced.
Methods such as DBVAE learn the under-represented features from the data instead.
To implement this loss function, it would be easier and more effective to treat the adversary as a separate neural network with its own weights. In this case, we feed the output of the final layer of the predictor network into the input of the adversarial network:
Given this description, write the code (in Python) and describe how you can obtain the classifier prediction and the adversary prediction loss.
Q4 · Background · Lecture 22, slides 21–25
What the question is about: a model that cannot reveal the group
Instead of fixing the data (Question 3), in-processing changes how the model is trained so that it is fair by construction (slide 21).
The goal here: the prediction \(\hat y\) should carry no information about the protected attribute \(z\). For a loan model this means the approval rate is the same in both groups (demographic parity, A3).
How do we know \(\hat y\) carries no information about \(z\)? Train a second model, the adversary, to guess \(z\) from \(\hat y\). If even the best adversary can only guess, the information is gone. Both models train together as a two-player game, like the generator and discriminator of a GAN.
IllustrativeReading the question's loss term by term
$$\min \Big[\underbrace{\cm{\sum_{(x, y)} L_Y\big(f(g(x)), y\big)}}_{\text{predictor: predict } y \text{ well}} \;+\; \underbrace{\ce{\sum_{(x, z)} L_Z\big(a(J_\lambda(g(x))), z\big)}}_{\text{adversary: predict } z \text{ from the predictor's features}}\Big]$$
Predictor \(W\) wants
a correct \(\hat y\) (low \(L_P\)) and a confused adversary (high \(L_A\)).
Adversary \(U\) wants
to recover \(z\) from \(\hat y\) (low \(L_A\)).
At equilibrium
\(\hat y\) is as accurate as it can be while telling nothing about \(z\).
\(J_\lambda\) is the gradient-reversal layer: the identity going forward, \(-\lambda\) times the gradient going back. The question replaces it with a separate adversary network and an explicit update rule.
How the question fits
Giventhe loss above and the design: predictor \(W\), its output fed into an adversary \(U\)
AskedPython code, how to obtain the classifier's prediction, and how to obtain the adversary's loss
Hidden stephow the predictor's weights are updated using both losses: the projection rule
Predicts the label: \(\hat y = f(x; W)\), trained to make \(L_P(\hat y, y)\) small.
Adversary, weights \(U\)
Sees only the predictor's output and tries to recover the protected attribute: \(\hat z = a(\hat y; U)\), trained to make \(L_A(\hat z, z)\) small.
The predictor also wants the adversary to fail. If \(\hat y\) carries no information about \(z\), the decisions satisfy demographic parity: the approval rate is the same in both groups (A3).
In the lecture's single-network form, the gradient-reversal layer \(J_\lambda\) is the identity going forward and multiplies the gradient by \(-\lambda\) going back, so the shared layers move against the adversary.7
Q4 · Prerequisite 4.2
The predictor's update and its projection term
Zhang, Lemoine and Mitchell update the predictor's weights with8
Without the projection, part of an ordinary accuracy step can point the way that helps the adversary. Removing that part first, then pushing along \(+\nabla_W L_A\), means every step makes the adversary's job no easier.
Warm-up exercise · one projected step by hand
Take \(\nabla_W L_P = (3, 1)\), \(\nabla_W L_A = (1, 0)\) and \(\alpha = 1\).
1. The first component of \(\operatorname{proj}_{\nabla L_A}\nabla L_P\):
3. The step is \(-(\text{bracket})\). Its dot product with \(\nabla L_A\):
Show solution
\(\operatorname{proj} = 3 \cdot (1, 0) = (3, 0)\). Bracket: \((3, 1) - (3, 0) - (1, 0) = (-1, 1)\). Step: \((1, -1)\), whose dot product with \(\nabla L_A\) is \(1 > 0\): the step raises the adversary's loss, while still lowering \(L_P\) along the second axis.
Without the projection the step would be \(-(3, 1) + (1, 0) = (-2, -1)\), with dot product \(-2 < 0\): it would help the adversary.
Bridge to the question. In code, the same three vectors come from two calls to autograd.grad, one per loss.
Q4 · Guided activity
Training the two networks live
Turn the adversary on. What happens to accuracy, to the approval gap between groups, and to the adversary's accuracy?
LiveA logistic predictor and a logistic adversary on synthetic loan data
\(x_1\) (income) · \(x_2\) (a proxy correlated with the group)
training step
group \(z = 0\)group \(z = 1\)accuracyapproval-rate gap \(|P(\hat y{=}1 \mid z{=}1) - P(\hat y{=}1 \mid z{=}0)|\)adversary accuracy
The historical labels depend on the proxy \(x_2\), so a plain predictor approves the groups at very different rates. The adversary pushes the boundary towards \(x_1\) alone: the gap shrinks and the adversary falls to guessing, at a cost in accuracy measured against those historical labels (slide 25). Switch to "adversary, no projection": with the same \(\alpha\) much of the gap remains, because ordinary accuracy steps keep handing the adversary information.
Q4 · The code
PyTorch implementation
Classifier prediction: run the predictor, \(\hat y = \sigma(f(x; W))\), and threshold it at 0.5.
Adversary prediction loss: feed the predictor's output (its logit) into the adversary and compare its prediction \(\hat z\) with the protected attribute, \(L_A = \operatorname{BCE}(\hat z, z)\).
Update: take \(\nabla_W L_P\) and \(\nabla_W L_A\) with two calls to autograd.grad, combine them as above, then update the adversary on its own loss. AIF360's AdversarialDebiasing does the same in TensorFlow.9
Q4Adversarial debiasing with the projection update (PyTorch)
import torch, torch.nn as nn, torch.nn.functional as F
torch.manual_seed(0)
# ---------- synthetic loan data with a proxy feature ----------
n = 4000
z = torch.bernoulli(torch.full((n,), 0.5)) # protected attribute
x1 = torch.randn(n) # legitimate feature
x2 = 1.5 * (2 * z - 1) + torch.randn(n) # proxy: correlated with z
y = ((x1 + 0.6 * x2 + 0.5 * torch.randn(n)) > 0).float() # historical labels depend on the proxy
X = torch.stack([x1, x2], 1)
# ---------- predictor f(x) and adversary a(logit) ----------
class Predictor(nn.Module):
def __init__(self): super().__init__(); self.net = nn.Sequential(nn.Linear(2, 16), nn.ReLU(), nn.Linear(16, 1))
def forward(self, x): return self.net(x).squeeze(1) # logit of y-hat
class Adversary(nn.Module):
def __init__(self): super().__init__(); self.lin = nn.Linear(1, 1)
def forward(self, logit): return self.lin(logit.unsqueeze(1)).squeeze(1) # logit of z-hat
def train(alpha, epochs=400, lr=0.05, debias=True):
torch.manual_seed(1)
P, A = Predictor(), Adversary()
optP, optA = torch.optim.SGD(P.parameters(), lr=lr), torch.optim.SGD(A.parameters(), lr=lr)
for _ in range(epochs):
logit = P(X)
loss_p = F.binary_cross_entropy_with_logits(logit, y) # L_P(y-hat, y)
loss_a = F.binary_cross_entropy_with_logits(A(logit), z) # L_A(z-hat, z)
params = list(P.parameters())
gp = torch.autograd.grad(loss_p, params, retain_graph=True) # grad_W L_P
ga = torch.autograd.grad(loss_a, params, retain_graph=True) # grad_W L_A
optP.zero_grad()
for p, g1, g2 in zip(params, gp, ga):
if debias:
u = g2 / (g2.norm() + 1e-8) # unit vector along grad_W L_A
p.grad = g1 - (g1 * u).sum() * u - alpha * g2 # grad L_P - proj - alpha grad L_A
else:
p.grad = g1
optP.step()
optA.zero_grad(); F.binary_cross_entropy_with_logits(A(P(X).detach()), z).backward(); optA.step() # adversary update
with torch.no_grad():
yhat = (P(X) > 0).float(); zl = A(P(X))
acc = (yhat == y).float().mean().item()
dp = (yhat[z == 1].mean() - yhat[z == 0].mean()).abs().item()
adv_acc = ((zl > 0).float() == z).float().mean().item()
return acc, dp, adv_acc
for name, a, d in [('no adversary', 0, False), ('adversary, alpha=1', 1, True), ('adversary, alpha=3', 3, True)]:
acc, dp, adv = train(a, debias=d)
print(f'{name:20s} accuracy {acc:.3f} demographic-parity gap {dp:.3f} adversary accuracy {adv:.3f}')
print(f'base rates: P(y=1 | z=1) = {y[z == 1].mean():.3f}, P(y=1 | z=0) = {y[z == 0].mean():.3f}')
Output (CPU, PyTorch 2.6)
no adversary accuracy 0.908 demographic-parity gap 0.559 adversary accuracy 0.780
adversary, alpha=1 accuracy 0.760 demographic-parity gap 0.098 adversary accuracy 0.507
adversary, alpha=3 accuracy 0.751 demographic-parity gap 0.079 adversary accuracy 0.513
base rates: P(y=1 | z=1) = 0.755, P(y=1 | z=0) = 0.245
Answer to Q4
For the first part we can use any loss function and try to ensure we get accurate predictions. For the second part we take what the predictor output, add a set of weights (the adversarial model), make a prediction about the protected attribute, and use the same kind of loss to measure the adversary's error.
We modify the weights over the whole network by updating them through the classification loss as well as the gradient through the adversary:
The middle term removes all components of the predictor's gradient update that would contribute to the adversary. Without it, the predictor could still make updates that benefit the adversary.
Lecture content the four questions did not need, each with a figure. Useful before the exam, and for the discussion at the end of the workshop.
A1 · Contrast data mining lecture, pages 3–10 and 49–55
Contrast data mining and emerging patterns
Contrast data mining finds patterns whose support differs between two datasets: today's traffic against yesterday's, attacks against normal flows, one class against another.10 The growth rate of a pattern \(X\) from a negative dataset \(D_n\) to a positive dataset \(D_p\) is
\(X\) is an emerging pattern if \(\operatorname{gr} \ge \rho\), and a jumping emerging pattern if it never occurs in \(D_n\), so \(\operatorname{gr} = \infty\) (page 49).11
LiveBuild a pattern from the network flows of pages 50–51
Pattern: click cells in the table to add attribute values
Summarising changes
Report only the flows whose support jumped between days, instead of thousands of rows (pages 7–10, 52–53).12
One-class classification
OCLEP: a test case from the training class tends to contain long emerging patterns; one from another class, short ones (page 54).
Versus anomaly detection
An anomaly detector learns "normal" and flags deviations; contrast mining compares two current datasets and reports what changed (page 55).
A2 · Lecture 22, slides 3–10
Harms and the three families of fairness
Five kinds of harm (slide 8)
Allocation
Opportunities, resources or information given unfairly: loans, jobs.
Quality of service
Works worse for some people: Gender Shades.
Representation
Over- or under-represents some groups, or ignores them.
Stereotypes
Repeats and reinforces stereotypes: word analogies (slide 24).
Denigration
Produces offensive or insulting outputs about a group.
Who decides? (slide 9)
Individuals, policymakers, lawyers and the media each care about different things; there are more than 20 definitions, and many conflict.13
Three families of definitions (slide 10)
Group fairness
Do groups get similar statistics, such as approval or error rates? (A3)
Individual fairness
Do similar people get similar predictions, whatever their group?
Causal fairness
Would the decision change if only the protected attribute changed?
A3 · Lecture 22, slides 11–16
Group fairness metrics on the toy loan example
200 applicants in two groups of 100; \(\hat Y = 1\) means approved, \(Y = 1\) means would repay. Four metrics compare the groups:14
LiveChange group B's decisions and watch the metrics; group A is fixed as on slide 11
Group A: 80 of 100 would repay; group B: 50 of 100. With different base rates, no setting makes all four metrics equal at once (slide 15).15
Not all errors cost the same (slide 16)
A false positive loses the bank money on a loan, but labels an innocent person high-risk in criminal justice. Choose the metric with the people affected.
Limits (slide 15)
Metrics conflict, small groups are noisy (with 8 people one mistake moves a rate by 12.5%), labels may be wrong, and a gap does not show its cause.
A4 · Lecture 22, slide 17
A decision tree for choosing a metric
Lecture figure, redrawnAnswer the questions to reach a metric (Aequitas fairness tree)16
A5 · Lecture 22, slides 18 and 21–22
Where bias enters, and where to intervene
Training data
Historical, representation and measurement bias.
The model
Algorithmic bias from the learning method; evaluation bias from an unrepresentative test set.
Deployment
People override or misuse predictions; users and the world change.
Pre-processing (the data)
Reweighting, disparate-impact remover, fair data augmentation with a GAN (slide 26). Use it if you can edit the data.
In-processing (training)
Fairness regularisers, adversarial debiasing (Q4), DBVAE (Q3). Use it if you can change the training.
Post-processing (predictions)
Group-specific thresholds, equalized-odds post-processing, reject option. Use it if the model is a black box.
Reduce bias early, and keep checking after deployment (slide 30). Toolkits such as AI Fairness 360 measure; they do not decide what is fair.9
outputs carry no information about \(z\); some accuracy lost
Our PyTorch run
no adversary → adversary, \(\alpha = 1\)
accuracy 0.908 → 0.760; approval gap 0.559 → 0.098
Reference material
References
Rakesh Agrawal and Ramakrishnan Srikant. Fast algorithms for mining association rules. In VLDB, pages 487–499, 1994.
Jiawei Han, Jian Pei and Yiwen Yin. Mining frequent patterns without candidate generation. In SIGMOD, pages 1–12, 2000. doi:10.1145/342009.335372
Jiawei Han, Micheline Kamber and Jian Pei. Data Mining: Concepts and Techniques, 3rd edition, chapters 6–7. Morgan Kaufmann, 2011.
Raymond T. Ng, Laks V. S. Lakshmanan, Jiawei Han and Alex Pang. Exploratory mining and pruning optimizations of constrained associations rules. In SIGMOD, pages 13–24, 1998. doi:10.1145/276304.276307
Joy Buolamwini and Timnit Gebru. Gender shades: intersectional accuracy disparities in commercial gender classification. In FAT*, PMLR 81, pages 77–91, 2018.
Alexander Amini, Ava P. Soleimany, Wilko Schwarting, Sangeeta N. Bhatia and Daniela Rus. Uncovering and mitigating algorithmic bias through learned latent structure. In AIES, pages 289–295, 2019. doi:10.1145/3306618.3314243
Yaroslav Ganin and Victor Lempitsky. Unsupervised domain adaptation by backpropagation. In ICML, PMLR 37, pages 1180–1189, 2015.
Brian Hu Zhang, Blake Lemoine and Margaret Mitchell. Mitigating unwanted biases with adversarial learning. In AIES, pages 335–340, 2018. doi:10.1145/3278721.3278779
Rachel K. E. Bellamy et al. AI Fairness 360: an extensible toolkit for detecting and mitigating algorithmic bias. IBM Journal of Research and Development 63(4/5):4:1–4:15, 2019. doi:10.1147/JRD.2019.2942287. Code: adversarial_debiasing.py
Guozhu Dong and James Bailey (editors). Contrast Data Mining: Concepts, Algorithms, and Applications. CRC Press, 2012.
Guozhu Dong and Jinyan Li. Efficient mining of emerging patterns: discovering trends and differences. In KDD, pages 43–52, 1999. doi:10.1145/312129.312191
Elaheh Alipour Chavary, Sarah M. Erfani and Christopher Leckie. Summarizing significant changes in network traffic using contrast pattern mining. In CIKM, pages 2015–2018, 2017. doi:10.1145/3132847.3133111
Ninareh Mehrabi, Fred Morstatter, Nripsuta Saxena, Kristina Lerman and Aram Galstyan. A survey on bias and fairness in machine learning. ACM Computing Surveys 54(6):115:1–115:35, 2021. doi:10.1145/3457607
Moritz Hardt, Eric Price and Nathan Srebro. Equality of opportunity in supervised learning. In NeurIPS, pages 3315–3323, 2016.
Jon Kleinberg, Sendhil Mullainathan and Manish Raghavan. Inherent trade-offs in the fair determination of risk scores. In ITCS, pages 43:1–43:23, 2017. doi:10.4230/LIPIcs.ITCS.2017.43
Pedro Saleiro, Benedict Kuester, Loren Hinkson, Jesse London, Abby Stevens, Ari Anisfeld, Kit T. Rodolfa and Rayid Ghani. Aequitas: a bias and fairness audit toolkit. arXiv:1811.05577, 2018. arXiv:1811.05577
Lecture slides: COMP90073 Trustworthy Machine Learning, The University of Melbourne. "Contrast Data Mining: Methods and Applications" (Sarah Erfani; cited by PDF page) and Lecture 22 "Bias and Fairness in Machine Learning" (Hanxun Huang, Semester 2, 2026; cited by slide). Tutorial: w12-tutorial-answers.pdf.