Types of Learning

The previous lesson used a single setup: the labels of 883 subscribers were known and the procedure saw all of them. The labels were produced for free there. In the field a label means a door visit, and visits are countable. This is what defines a setup — which piece of information is obtained, in what amount, and at what price.

This lesson sets up the same problem in four setups and counts how many labels each setup asks for. The measure and the held-out set stay the same in all four so that the numbers can be read side by side.

• FC8. Supervised learning: the label of every example is known. The procedure searches directly for the mapping from feature to label.
• FC9. Unsupervised learning: there is no label. The output is not a decision but a structure; turning the structure into a decision is a separate job and it asks for labels.
• FC10. Semi-supervised learning: a small number of labeled examples is used together with a large number of unlabeled ones. The contribution of the unlabeled rows is a measurable number.
• FC11. Reinforcement learning: the label is not given in advance, it comes as the return on an action. The procedure chooses whom to visit, sees the label only of the one it visited, and makes its next choice accordingly.
• FC12. The label is a budget. In this lesson the unit of comparison between the setups is not accuracy but labels spent per unit of accuracy.
• FC13. The real measure of the reinforcement setup is not accuracy but the return: the number of illicit cases found with the budget spent. Accuracy is still printed, but the number that describes the setup is the return.

Rebuilding the Fictional Dataset

# setup.py — the fictional dataset of lesson 01 is rebuilt with the same seed: the readings
# table, the subscriber summary, the fictional label, the train / held-out split and the tree learner.
import math

SEED, RAW, M32 = 20260218, 1400, 0xFFFFFFFF
REGION = [("north", 0.28, 21), ("south", 0.22, 17), ("east", 0.18, 26),
          ("west", 0.14, 14), ("central", 0.18, 23)]
FEATURES = ["mean", "per_person", "drop", "zero_readings", "reading_count",
            "satisfaction", "household_size", "highest", "lowest"]


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, _dropped, _series = [], [], {}
for i in range(RAW):
    r = rng(SEED + i)
    b = REGION[pick(r(), [x[1] for x in REGION])]
    k = {"subscriber_id": 10001 + i, "region": b[0], "base": b[2],
         "household_size": pick(r(), [0.06, 0.24, 0.30, 0.24, 0.11, 0.05]),
         "satisfaction": pick(r(), [0.08, 0.14, 0.27, 0.34, 0.17]) + 1}
    (_dropped if r() < 0.046 else _subscribers).append(k)
_valid = {a["subscriber_id"] for a in _subscribers}
for k in _subscribers + _dropped:
    r = rng(SEED + 7000 + k["subscriber_id"])
    for d in range(pick(r(), [0.05, 0.12, 0.21, 0.62])):
        t = 0.0 if r() < 0.038 else math.floor(k["base"] * math.exp(
            (r() + r() + r() - 1.5) * 0.62) * (1 - d * 0.05) * 100 + 0.5) / 100
        if k["subscriber_id"] in _valid:
            _series.setdefault(k["subscriber_id"], []).append(t)
        r()

SUBSCRIBERS = []
for k in _subscribers:
    t = _series.get(k["subscriber_id"])
    if not t:
        continue
    mean = sum(t) / len(t)
    a = {"subscriber_id": k["subscriber_id"], "region": k["region"], "series": t,
         "household_size": k["household_size"], "satisfaction": k["satisfaction"],
         "reading_count": len(t), "mean": mean, "highest": max(t),
         "lowest": min(t), "zero_readings": sum(1 for v in t if v == 0),
         "per_person": mean / max(1, k["household_size"]),
         "drop": (t[0] - t[-1]) / t[0] if len(t) > 1 and t[0] > 0 else 0.0}
    r = rng(SEED + 31000 + a["subscriber_id"])
    a["suspicion"] = 1 if (1.30 * a["zero_readings"] + 1.25 * (a["drop"] > 0.45)
                           + 1.05 * (a["per_person"] > 12.0) + 0.65 * (a["reading_count"] < 3)
                           + 0.45 * (a["satisfaction"] <= 2) - 1.55
                           + (r() + r() - 1.0) * 1.1) > 0 else 0
    SUBSCRIBERS.append(a)

r = rng(SEED + 90001)
TRAIN, HELD_OUT = [], []
for a in SUBSCRIBERS:
    (TRAIN if r() < 0.70 else HELD_OUT).append(a)
positives = lambda k: sum(a["suspicion"] for a in k)
accuracy = lambda f, k: sum(1 for a in k if f(a) == a["suspicion"]) / len(k)
_impurity = lambda k: 2 * (positives(k) / len(k)) * (1 - positives(k) / len(k)) if k else 0.0


def fit(k, depth=3, min_size=40):
    """The greedy decision tree of lesson 01: the split criterion and stopping rule are there."""
    best, choice = _impurity(k) * len(k), None
    if depth and len(k) >= min_size:
        for feat in FEATURES:
            for threshold in sorted({a[feat] for a in k})[1:]:
                left = [a for a in k if a[feat] < threshold]
                right = [a for a in k if a[feat] >= threshold]
                m = _impurity(left) * len(left) + _impurity(right) * len(right)
                if m < best - 1e-9:
                    best, choice = m, (feat, threshold, left, right)
    if choice is None:
        return 1 if 2 * positives(k) > len(k) else 0
    lt, rt = fit(choice[2], depth - 1, min_size), fit(choice[3], depth - 1, min_size)
    return lt if lt == rt else (choice[0], choice[1], lt, rt)


def apply(d, a):
    while isinstance(d, tuple):
        d = d[2] if a[d[0]] < d[1] else d[3]
    return d


print(f"fictional dataset (seed {SEED}): {len(SUBSCRIBERS)} subscribers, {len(TRAIN)} train, "
      f"{len(HELD_OUT)} held-out, {positives(SUBSCRIBERS)} suspicious")

fictional dataset (seed 20260218): 1260 subscribers, 883 train, 377 held-out, 327 suspicious

Supervised: As the Label Budget Shrinks

In the supervised setup the only thing that changes is how many labels are given. With small budgets a single draw is misleading, so five separate subsets are drawn for each budget and the numbers are averaged.

# supervised.py — the number of labels is a budget: the same procedure is built with more labels.
# Five separate random subsets are drawn for each budget and the two numbers are averaged.
import statistics
from collections import Counter

BUDGET, DRAWS = [30, 60, 150, 400, 883], 5
most_frequent = Counter(a["suspicion"] for a in TRAIN).most_common(1)[0][0]
BASE_TRAIN = accuracy(lambda a: most_frequent, TRAIN)
BASE_HELD = accuracy(lambda a: most_frequent, HELD_OUT)
W = [20, 10, 12, 12]
fmt = lambda h: str(h[0]).ljust(W[0]) + "".join(str(v).rjust(W[i + 1])
                                                for i, v in enumerate(h[1:]))
print(fmt(["labels", "train", "held-out", "vs baseline"]))
print(fmt(["baseline (0 labels)", f"{BASE_TRAIN:.4f}", f"{BASE_HELD:.4f}", "0.0000"]))
for n in BUDGET:
    inside, outside = [], []
    for j in range(DRAWS):
        r = rng(SEED + 4100 + j)
        subset = sorted(TRAIN, key=lambda a: r())[:n]
        d = fit(subset, 3, max(12, n // 20))
        inside.append(accuracy(lambda a: apply(d, a), subset))
        outside.append(accuracy(lambda a: apply(d, a), HELD_OUT))
    o = statistics.fmean(outside)
    print(fmt([n, f"{statistics.fmean(inside):.4f}", f"{o:.4f}", f"{o - BASE_HELD:+.4f}"]))

labels                   train    held-out vs baseline
baseline (0 labels)     0.7350      0.7533      0.0000
30                      0.9400      0.7745     +0.0212
60                      0.9267      0.7841     +0.0308
150                     0.8947      0.7873     +0.0340
400                     0.8725      0.8419     +0.0886
883                     0.8709      0.8594     +0.1061

The difference over the baseline erodes together with the budget: 0.1061 at 883 labels, 0.0886 at 400, 0.0212 at 30. A model built with thirty labels does beat the baseline, but the margin by which it beats it is about one fifth of that of the model with 883 labels.

The two columns move in opposite directions. As labels decrease the held-out figure falls while the training figure rises: 0.9400 at 30 labels, 0.8709 at 883 labels. In a set of thirty rows the tree can classify almost every row correctly; on the held-out set the same tree stays at 0.7745. This opposite movement is the subject of the Generalization topic; here it is only put on record.

Unsupervised: Unlabeled Structure and the Cost of Naming

In the unsupervised setup the label column is never read. The procedure looks only at the feature space and divides subscribers who are close to one another into clusters. Because the scales differ, each feature has its mean subtracted and is divided by its own variance; otherwise a column in cubic meters crushes the small-scale columns.

The output of this setup is not a decision. The sentence “this subscriber is in the fourth cluster” tells the field team nothing; the name of the cluster is needed. Naming asks for labels: one subscriber is visited from each cluster, the name of the cluster becomes the label of that subscriber, and the cost is K labels.

# unsupervised.py — no label is used and the cluster structure is derived. The output is not a
# decision but a structure; to turn it into a decision one subscriber is visited from each
# cluster and the name of the cluster becomes the label of that subscriber: cost K labels.
MEANS = {o: statistics.fmean(a[o] for a in TRAIN) for o in FEATURES}
STDS = {o: statistics.pstdev(a[o] for a in TRAIN) or 1.0 for o in FEATURES}
r = rng(SEED + 4100)
MIXED = sorted(TRAIN, key=lambda a: r())
vec = lambda a: [(a[o] - MEANS[o]) / STDS[o] for o in FEATURES]
dist = lambda v, m: sum((x - y) ** 2 for x, y in zip(v, m))


def cluster(K):
    """K centers are picked at random and pulled to the mean of their members over twenty rounds."""
    r = rng(SEED + 4202)
    centers = [vec(MIXED[int(r() * len(MIXED))]) for _ in range(K)]
    for _ in range(20):
        groups = [[] for _ in range(K)]
        for a in TRAIN:
            v = vec(a)
            groups[min(range(K), key=lambda i: dist(v, centers[i]))].append(v)
        for i in range(K):
            if groups[i]:
                centers[i] = [sum(c) / len(c) for c in zip(*groups[i])]
    return lambda a: min(range(K), key=lambda i: dist(vec(a), centers[i]))


print(fmt(["clusters", "labels", "train", "held-out"]))
CLUSTERS = {}
for K in (2, 6):
    which, names = cluster(K), {}
    for a in MIXED:
        names.setdefault(which(a), a["suspicion"])
    f = lambda a, h=which, i=names: i[h(a)]
    CLUSTERS[K] = (which, f, names)
    print(fmt([K, K, f"{accuracy(f, TRAIN):.4f}", f"{accuracy(f, HELD_OUT):.4f}"]))
which6 = CLUSTERS[6][0]
print("K=6 cluster sizes",
      sorted(Counter(which6(a) for a in TRAIN).values(), reverse=True),
      "size of the cluster named suspicious",
      sum(1 for a in TRAIN if CLUSTERS[6][2][which6(a)] == 1))

clusters                labels       train    held-out
2                            2      0.7350      0.7533
6                            6      0.7780      0.8117
K=6 cluster sizes [268, 157, 147, 131, 102, 78] size of the cluster named suspicious 78

The two-cluster split sits exactly on the baseline: 0.7533, a difference of zero. Both clusters were named clean, which means the procedure made the same decision as the baseline that says “clean” to everyone. Clustering does not split by suspicion; it splits by the largest variance, and in this set the largest variance lies in the size of consumption, not in illicit use.

With the six-cluster split the picture changes: 0.8117, 0.0584 above the baseline. The smallest cluster, with 78 subscribers, was named suspicious, and one of the six labels was enough to establish this. The number of clusters is a decision and its effect is 0.0584 — a difference produced not by the clustering but by how many clusters were asked for.

Semi-Supervised: The Contribution of Unlabeled Rows

In the semi-supervised setup the labels of 60 subscribers are known and those of 823 are not. The unlabeled rows are not discarded: according to the cluster structure each one is given a pseudo-label, and the tree is built on the sum of 60 true labels and 823 pseudo-labels.

# semi.py — 60 labels + 823 unlabeled rows: the unlabeled rows get a pseudo-label from the
# cluster structure and the tree is built with 60 true labels and 823 pseudo-labels.
LABELED, UNLABELED = MIXED[:60], MIXED[60:]
name60 = {}
for i in range(6):
    group = [x["suspicion"] for x in LABELED if which6(x) == i]
    name60[i] = 1 if group and 2 * sum(group) > len(group) else 0
PSEUDO = [{**a, "suspicion": name60[which6(a)]} for a in UNLABELED]
tree60, tree_semi = fit(LABELED, 3, 12), fit(LABELED + PSEUDO, 3, 40)
f60, f_semi = lambda a: apply(tree60, a), lambda a: apply(tree_semi, a)
agree = sum(1 for p, a in zip(PSEUDO, UNLABELED) if p["suspicion"] == a["suspicion"])
print(f"pseudo-labels {len(PSEUDO)}, matching the true label {agree}, "
      f"rate {agree / len(PSEUDO):.4f}")
print(fmt(["setup", "labels", "train", "held-out"]))
for setup, f in [("60 labels only", f60), ("60 + 823 unlabeled", f_semi)]:
    print(fmt([setup, 60, f"{accuracy(f, TRAIN):.4f}", f"{accuracy(f, HELD_OUT):.4f}"]))

pseudo-labels 823, matching the true label 633, rate 0.7691
setup                   labels       train    held-out
60 labels only              60      0.7792      0.7905
60 + 823 unlabeled          60      0.7780      0.8090

The same 60 labels, two setups, two numbers. When the 823 unlabeled rows are added, the held-out figure goes from 0.7905 to 0.8090: 0.0185. Only 76.91 percent of the pseudo-labels match the true label, which means nearly a quarter of them are wrong, and the contribution is still positive. What the unlabeled rows carry is not a label but density information: which combinations of features are frequent and which are rare.

Reinforcement: Earning the Label with an Action

In the fourth setup the label column is closed. The procedure picks a subscriber, that subscriber is visited, and only that subscriber’s label is opened. The budget is six rounds of twenty visits each. The first round is random; in the following rounds the choice is made by the vote of five trees built with the labels seen up to that point.

# reinforcement.py — the label is seen only once a visit is made. Six rounds of twenty
# visits each; every round is chosen by the vote of five trees built with what has been seen so far.
ROUNDS, STEP = 6, 20
r = rng(SEED + 4404)
POOL = sorted(TRAIN, key=lambda a: r())
visited, seen = [], set()
print(fmt(["round", "visits", "found", "total"]))
for t in range(ROUNDS):
    if not visited:
        chosen = POOL[:STEP]
    else:
        trees = [fit([visited[int(r() * len(visited))] for _ in visited], 3, 10)
                 for _ in range(5)]
        chosen = sorted((a for a in POOL if a["subscriber_id"] not in seen),
                        key=lambda a: (-sum(apply(d, a) for d in trees),
                                       a["subscriber_id"]))[:STEP]
    seen.update(a["subscriber_id"] for a in chosen)
    visited += chosen
    print(fmt([t + 1, STEP, positives(chosen), positives(visited)]))
tree_rl, tree_full = fit(visited, 3, 20), fit(TRAIN)
print(f"\nillicit cases found in {len(visited)} visits: {positives(visited)}; "
      f"if the same budget were spent at random: {positives(POOL[:ROUNDS * STEP])}")
print(fmt(["setup", "labels", "train", "held-out"]))
FINAL = [("supervised", 883, lambda a: apply(tree_full, a)), ("unsupervised", 6, CLUSTERS[6][1]),
         ("semi-supervised", 60, f_semi),
         ("reinforcement", ROUNDS * STEP, lambda a: apply(tree_rl, a))]
for setup, n, f in FINAL:
    print(fmt([setup, n, f"{accuracy(f, TRAIN):.4f}", f"{accuracy(f, HELD_OUT):.4f}"]))

round                   visits       found       total
1                           20           4           4
2                           20          11          15
3                           20           8          23
4                           20          11          34
5                           20          19          53
6                           20          20          73

illicit cases found in 120 visits: 73; if the same budget were spent at random: 25
setup                   labels       train    held-out
supervised                 883      0.8709      0.8594
unsupervised                 6      0.7780      0.8117
semi-supervised             60      0.7780      0.8090
reinforcement              120      0.7973      0.8090

The found column fluctuates from round to round — 4, 11, 8, 11, 19, 20 — but the return, that is the total, rises by accumulating: 4, 15, 23, 34, 53, 73. In the sixth round all twenty of the twenty subscribers chosen are illicit cases. In total 73 illicit cases were found in 120 visits; had the same budget been spent at random, 25 would have been found. The baseline here is not the most frequent class but the random visit, because what is measured is not classification accuracy but the return on the budget, and the random visit is the counterpart of the non-learning procedure on this measure. The difference is 48 illicit cases.

The last table puts the four setups side by side. In the accuracy column three setups stand very close — 0.8117, 0.8090, 0.8090 — but their label columns are 6, 60 and 120. Producing the same number with a budget twenty times different is not the same thing. Of the 120 labels of the reinforcement setup, 73 came back as illicit cases found in the field; its number is read on the return row.

Summary

• The four setups solve the same problem and all four are measured on the same held-out set: supervised 0.8594 with 883 labels, unsupervised 0.8117 with 6 labels, semi-supervised 0.8090 with 60 labels, reinforcement 0.8090 with 120 visits; the baseline is 0.7533.
• As the label budget shrinks, the difference over the baseline erodes: 0.1061 at 883 labels, 0.0886 at 400, 0.0212 at 30. In the same fall the training figure rises in the opposite direction, from 0.8709 to 0.9400.
• The output of the unsupervised setup is not a decision but a structure; turning the structure into a decision asks for one visit per cluster. The two-cluster split sits exactly on the baseline, the six-cluster split gains 0.0584.
• In the semi-supervised setup the 823 unlabeled rows carry the model built with the same 60 labels from 0.7905 to 0.8090; only 76.91 percent of the pseudo-labels are correct.
• The measure of the reinforcement setup is the return: 73 illicit cases in 120 visits, 25 with random visits; the difference is 48 illicit cases, and this number does not appear in the accuracy column.

Next Step

Three of the four setups paid for labels and the fourth earned them with visits. None of them asked this: can the label be derived from the data. In the readings table there is a structure that no one labeled — the path each subscriber follows across the periods. Predicting the next period from the reading of one period asks for no label, because the answer is already in the table. The next lesson builds this setup: a representation is learned through an unlabeled pretext task, that representation is given to the main task as features, and it is measured how many points the pretext task adds over the baseline in the main task.