Probabilistic Classifier with an Independence Assumption

The previous lesson reduced twelve columns to a single sum of distances. In that sum, the region indicator and the mean consumption stand in the same list of terms and which of them carries the decision is not visible; for a categorical field, “distance” is already a notion attached after the fact. This lesson takes a family that does not sum the columns but counts them: it counts how many times each level of each column is seen under each class.

There is an obstacle to classifying by counting. It is not possible to directly count how many times a particular column combination came out suspicious, because almost all of the combinations have never been seen in the training set. The family gets past this obstacle with a single assumption: it accepts that the columns are independent of each other given the class, and replaces the joint count with the product of the individual column counts. The assumption is not true in this set; the lesson counts the two separate consequences of the falseness separately.

• NM9. The set, the split and the baseline do not change: a fictional table of 1,260 subscribers, seed 20260218, split 756/252/252, baseline 0.7579 on the test set and 61 suspicious subscribers.
• NM10. The feature set is fixed; only its representation changes. The five binary columns of the region turn into a single five-level column, mean consumption is split into the 10, 25 and 40 m³ tariff bands from the Data Analytics curriculum, and volatility and per-person consumption are split into intervals that hold an equal number of rows. The interval boundaries are learned from the training set alone.
• NM11. There are two hyperparameters and neither is learned from the data: the number of intervals and the smoothing coefficient. The product is computed as a sum of logarithms; the direct product of eight small probabilities falls to zero in floating point.
• NM12. The prior is the share of a class in the training set; the posterior is its probability after the columns are seen. The decision threshold is 0.5; threshold selection is left to the evaluation topic of the course.
• NM13. Text classification is not built and is left to the Natural Language Processing and Computer Vision course; all the fields used are categorical fields of the fictional subscriber table.
• NM14. The choice is read from the validation set. In the ranking measurement the 61 subscribers with the highest probabilities are taken; 61 is the actual number of suspicious subscribers in the test set.

From Counts to Probability

The setup generates the set, builds the level representation and gives the reason for the assumption with two numbers.

# counting_model.py — MODEL: the FICTIONAL subscriber table of the Introduction to Machine Learning course is generated with the same seed;
# the feature set is fixed, only its representation is turned into levels.
import collections
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)
    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, VAL, TEST = K[:756], K[756:1008], K[1008:]
BASELINE_TEST = sum(x["suspicious"] == 0 for x in TEST) / len(TEST)


def tariff_band(v):                         # tariff bands 10 / 25 / 40 m3
    return 0 if v < 10 else (1 if v < 25 else (2 if v < 40 else 3))


def cutpoints(train, a, n):                 # LEARNING: interval boundaries from the training set
    v = sorted(x[a] for x in train)
    return [v[int(i * len(v) / n)] for i in range(1, n)]


def level(v, cuts):
    return sum(1 for k in cuts if v >= k)


def categorize(s, cuts):                    # APPLICATION
    return [({"tariff": tariff_band(x["mean_consumption"]), "region": x["region_name"],
              "household": x["household"], "satisfaction": x["satisfaction"],
              "period": x["period"], "zero_readings": x["zero_readings"],
              "volatility": level(x["volatility"], cuts["volatility"]),
              "per_person": level(x["per_person"], cuts["per_person"])}, x["suspicious"])
            for x in s]


COLUMNS = ["tariff", "region", "household", "satisfaction", "period", "zero_readings",
           "volatility", "per_person"]
CUTS = {a: cutpoints(TRAIN, a, 8) for a in ("volatility", "per_person")}
C_TRAIN, C_VAL, C_TEST = categorize(TRAIN, CUTS), categorize(VAL, CUTS), categorize(TEST, CUTS)
print(f"train {len(C_TRAIN)}, test {len(C_TEST)}, suspicious in test {sum(y for _, y in C_TEST)}, "
      f"baseline {BASELINE_TEST:.4f}")
LEVELS = {a: {x[a] for x, _ in C_TRAIN} for a in COLUMNS}
combos, cells = 1, 0
for a in COLUMNS:
    combos, cells = combos * len(LEVELS[a]), cells + 2 * len(LEVELS[a])
print(f"columns {len(COLUMNS)}, combinations {combos}, training rows {len(C_TRAIN)}, "
      f"cells in the per-column count table {cells}")

train 756, test 252, suspicious in test 61, baseline 0.7579
columns 8, combinations 201600, training rows 756, cells in the per-column count table 80

The second line is the reason for the assumption. The levels of the eight columns produce 201,600 distinct combinations and there are 756 training rows; keeping the joint count directly is not an option. Counting the columns separately reduces the same table to 80 cells. The price is in the multiplication itself: the probability that a subscriber is suspicious is the product of the class prior and the shares of the subscriber’s level in each column under that class, and this product gives the right number only if the columns are independent given the class.

The Model’s Number and Twenty Candidates

The model is written with two hyperparameters and a grid is scanned. The table printed belongs to the validation set; the test set numbers are given in the summary lines.

def fit(rows, columns):                     # MODEL: counts and prior shares
    totals = collections.Counter(y for _, y in rows)
    counts = {(a, c): collections.Counter(d[a] for d, y in rows if y == c)
              for a in columns for c in (0, 1)}
    return totals, counts, {a: len({d[a] for d, _ in rows}) for a in columns}


def posterior(m, d, columns, alpha):        # class 1 probability; the product is a sum of logs
    totals, counts, levels = m
    n, logs = sum(totals.values()), []
    for c in (0, 1):
        t = math.log(totals[c] / n)
        for a in columns:
            numerator = counts[(a, c)][d[a]] + alpha
            t = -math.inf if numerator <= 0.0 else t + math.log(
                numerator / (totals[c] + alpha * levels[a]))
        logs.append(t)
    if logs[0] == -math.inf and logs[1] == -math.inf:
        return None                         # both classes eliminated: the model goes silent
    e = [math.exp(t - max(logs)) for t in logs]
    return e[1] / (e[0] + e[1])


def evaluate(train, target, columns, alpha):
    m, p, silent = fit(train, columns), [], 0
    for d, y in target:
        o = posterior(m, d, columns, alpha)
        if o is None:
            silent, o = silent + 1, 0.0
        p.append((o, y))
    return sum((o > 0.5) == y for o, y in p) / len(p), p, silent


GRID, ALPHAS = {}, (0.0, 0.25, 1.0, 4.0)
for n in (3, 4, 6, 8, 12):
    CUTS_N = {a: cutpoints(TRAIN, a, n) for a in ("volatility", "per_person")}
    TR_N, VA_N, TE_N = (categorize(TRAIN, CUTS_N), categorize(VAL, CUTS_N),
                        categorize(TEST, CUTS_N))
    for alpha in ALPHAS:
        GRID[(n, alpha)] = (evaluate(TR_N, VA_N, COLUMNS, alpha)[0],
                            evaluate(TR_N, TE_N, COLUMNS, alpha)[0])
print(f"{'bins':>6}" + "".join(f"{a:>9}" for a in ALPHAS) + "   (validation)")
for n in (3, 4, 6, 8, 12):
    print(f"{n:>6}" + "".join(f"{GRID[(n, a)][0]:>9.4f}" for a in ALPHAS))
cv = max(GRID, key=lambda a: (GRID[a][0], -a[0], -a[1]))
ct = max(GRID, key=lambda a: (GRID[a][1], -a[0], -a[1]))
print(f"\ncandidates tried {len(GRID)}")
for label, a in (("on validation", cv), ("on test", ct)):
    print(f"{'chosen ' + label + ':':<22}bins {a[0]}, alpha {a[1]} -> validation "
          f"{GRID[a][0]:.4f}, test {GRID[a][1]:.4f}")
print(f"family number {GRID[cv][1]:.4f}, {GRID[cv][1] - BASELINE_TEST:+.4f} above the "
      f"baseline; the two selection sets differ by {GRID[ct][1] - GRID[cv][1]:+.4f}")

  bins      0.0     0.25      1.0      4.0   (validation)
     3   0.7540   0.7540   0.7540   0.7579
     4   0.7540   0.7540   0.7540   0.7579
     6   0.7738   0.7738   0.7659   0.7698
     8   0.7778   0.7778   0.7857   0.7857
    12   0.7579   0.7579   0.7619   0.7698

candidates tried 20
chosen on validation: bins 8, alpha 1.0 -> validation 0.7857, test 0.7817
chosen on test:       bins 4, alpha 4.0 -> validation 0.7579, test 0.7857
family number 0.7817, +0.0238 above the baseline; the two selection sets differ by +0.0040

The family number is 0.7817; it beats the baseline by 0.0238, six subscribers, and was found by trying 20 candidates. The instance-based procedure of the previous lesson had read 0.7937 with the same feature set. This family, which produces probabilities and rests on an explicit assumption, stayed behind the procedure that sums distances; the difference is three subscribers. This is the first example of the course’s second claim and it is not hidden.

The two selection sets give different candidates. From validation, eight intervals with 1.0 emerge; had the test set been consulted, four intervals with 4.0 would be chosen and the reported number would be 0.7857. That candidate’s validation number is 0.7579, which puts it among the worst of the twenty candidates.

Zero Counts and Smoothing

The sparsest of the eighty cells is the intersection of the top band of the tariff column with the suspicious class, and its count is zero: a subscriber with consumption above forty cubic meters has never been seen as suspicious in training. In a product, a single zero erases everything the other seven columns say. Smoothing adds a small constant to every count; its reason is not a performance setting but this structural flaw.

def veto_count(train, target, columns, all_levels):
    seen = {(a, c): {d[a] for d, y in train if y == c} for a in columns for c in (0, 1)}
    empty = sum(len(all_levels[a] - seen[(a, c)]) for a in columns for c in (0, 1))
    veto = wrong = 0
    for d, y in target:
        eliminated = [c for c in (0, 1) if any(d[a] not in seen[(a, c)] for a in columns)]
        if eliminated:
            veto, wrong = veto + 1, wrong + (y in eliminated)
    return empty, veto, wrong


print(f"{'train':>6} {'empty cells':>12} {'vetoed':>10} {'wrong veto':>12} "
      f"{'alpha=0':>8} {'alpha=1':>8}")
for m in (60, 120, 250, 500, 756):
    b, v, y = veto_count(C_TRAIN[:m], C_TEST, COLUMNS, LEVELS)
    print(f"{m:>6} {b:>12} {v:>10} {y:>12} "
          f"{evaluate(C_TRAIN[:m], C_TEST, COLUMNS, 0.0)[0]:>8.4f} "
          f"{evaluate(C_TRAIN[:m], C_TEST, COLUMNS, 1.0)[0]:>8.4f}")

 train  empty cells     vetoed   wrong veto  alpha=0  alpha=1
    60            8        137           24   0.7341   0.7302
   120            4         56            9   0.7460   0.7579
   250            2          1            1   0.7381   0.7540
   500            1          1            1   0.7659   0.7698
   756            1          1            1   0.7778   0.7817

With sixty training rows, eight of the eighty cells are empty, and these eight gaps veto 137 of the 252 test rows; in 24 of them the vetoed class is the subscriber’s actual class, that is, the decision rests not on the evidence of eight columns but on a single missing count. When the training grows to 756 rows, the empty cells fall to one and the veto to a single row; the moment the smoothing coefficient is greater than zero, the veto is lifted entirely.

The last two columns show the limit of the fix. With sixty training rows, smoothing lowers the number from 0.7341 to 0.7302; at 120 rows it raises it from 0.7460 to 0.7579. What it pays for is not accuracy but the model not going silent.

When the Assumption Breaks

Conditional independence is a measurable claim: how far the joint count of two columns within a class deviates from the product of their individual shares. If the deviation is zero, the assumption holds for that pair.

def dependence(rows, a, b):     # deviation of the joint count from the product, given the class
    t = 0.0
    for c in (0, 1):
        sub = [d for d, y in rows if y == c]
        n = len(sub)
        pa = collections.Counter(d[a] for d in sub)
        pb = collections.Counter(d[b] for d in sub)
        pab = collections.Counter((d[a], d[b]) for d in sub)
        t += n / len(rows) * sum(abs(pab[(u, v)] / n - pa[u] * pb[v] / n / n)
                                 for u in pa for v in pb) / 2
    return t


for a, b in (("household", "per_person"), ("period", "volatility"),
             ("period", "zero_readings")):
    print(f"{a:<10} {b:<14} deviation {dependence(C_TRAIN, a, b):.3f}")


def duplicate(rows, k):         # the column carrying the same information re-enters the table
    return [(dict(d, **{f"tariff_{i}": d["tariff"] for i in range(k)}), y)
            for d, y in rows]


POS = sum(y for _, y in C_TEST)
print(f"\n{'copies':>6} {'columns':>7} {'accuracy':>9} {'extreme prob':>12} "
      f"{'mean confidence':>15} {'top-' + str(POS) + ' hits':>14}")
for k in (0, 1, 2, 4, 8):
    cols = COLUMNS + [f"tariff_{i}" for i in range(k)]
    d, p, _ = evaluate(duplicate(C_TRAIN, k), duplicate(C_TEST, k), cols, 1.0)
    top = sorted(p, key=lambda t: -t[0])[:POS]
    print(f"{k:>6} {len(cols):>7} {d:>9.4f} "
          f"{sum(1 for o, _ in p if o > 0.99 or o < 0.01):>12} "
          f"{statistics.fmean(max(o, 1 - o) for o, _ in p):>15.3f} "
          f"{sum(y for _, y in top):>14}")

household  per_person     deviation 0.407
period     volatility     deviation 0.235
period     zero_readings  deviation 0.011

copies columns  accuracy extreme prob mean confidence    top-61 hits
     0       8    0.7817            2           0.842             29
     1       9    0.7778            5           0.862             32
     2      10    0.7778           17           0.889             33
     4      12    0.7817           72           0.932             32
     8      16    0.7857          169           0.970             33

The assumption is already broken in this table. The deviation between household size and per-person consumption is 0.407, and this is the definition itself: per-person consumption is mean consumption divided by household size. Period count and volatility deviate by 0.235, because the volatility of a subscriber with a single period is zero. The most independent pair is the period count and zero readings, at 0.011.

The lower table separates two consequences. The probability output goes to the extremes: the number of subscribers with extreme probabilities rises from 2 to 169 and the mean confidence from 0.842 to 0.970; when the same evidence is multiplied eight times, the model behaves as if it had seen eight independent pieces of evidence. The ranking, on the other hand, stays standing: the number of actual suspicious subscribers in the top 61 rises from 29 to 33 and accuracy goes from 0.7817 to 0.7857. Because the copied column pushes the scores of all subscribers in the same direction, it does not break the ranking; what it breaks is the magnitude of the number. The output of this family can be used as a ranking score, but not as a measure of confidence.

Summary

• Against the 201,600 combinations of eight columns there are 756 training rows; the conditional independence assumption reduces the count table to 80 cells, and this is the family’s only justification.
• The family number is 0.7817, 0.0238 above the baseline, and was found by trying 20 candidates; the instance-based procedure of the previous lesson had read 0.7937 with the same feature set.
• Had the choice been made on the test set, a different candidate would be chosen and the reported number would be 0.7857.
• A zero count eliminates a class entirely: with 60 training rows, 137 test rows are vetoed and in 24 of them the vetoed class is the right class. Smoothing removes the veto but does not guarantee accuracy; at 60 rows the number falls from 0.7341 to 0.7302.
• When the assumption breaks, two consequences separate: subscribers with extreme probabilities rise from 2 to 169 while the hits in the top 61 go from 29 to 33.

Next Step

This family’s decision rests on the counts of all the training rows: a subscriber standing far from the boundary and a subscriber standing exactly on the boundary both grow the same cell by one unit. In the neighbor procedure of the previous lesson too, each of the 31 neighbors cast an equal vote. The next lesson takes a family that does the opposite. The margin-based classifier is concerned only with the examples near the boundary; it places the boundary in the middle of the gap between the two classes and counts openly the examples that carry the decision as support vectors. The lesson sweeps the coefficient that tunes the margin width, prints how many examples carry the decision at each width, and measures with explicitly computed polynomial features the kernel transform that produces a curved boundary without opening columns.