P-algos writes when the script runsDictionary of Applied Machine Learning · hypothesis space
Numerical companion to the entry hypothesis space: it recomputes what the entry states and prints one line per check
One block per paragraph of the entry (marked [P...]): each block verifies numerically what the corresponding statement asserts. Self-contained (numpy/matplotlib only), fixed seed.
Run it with python3 hypospace.py, from any directory — it writes its output files into the current directory. Requires NumPy and Matplotlib only, and uses fixed seeds, so the printed numbers reproduce exactly. Download hypospace.py
One cell per block of the script: the code, and what that code printed when it last ran here
"""
hypospace.py — numerical companion to the glossary entry
'hypothesis space'.
One block per paragraph of the entry (marked [P...]): each block verifies
numerically what the corresponding statement asserts. Self-contained
(numpy/matplotlib only), fixed seed.
Blocks
------
[P-def] The hypothesis space is the committed set of candidate maps,
a subset of Y^X: for |X| = 4, |Y| = 2 the full map space has
16 elements, the threshold subset only 5.
[P-examples] Canonical hypothesis spaces: the linear model (linear maps
R^d -> R closed under evaluation) and the set of maps
realizable by a fixed ANN architecture as its parameters
vary (different parameters, different maps; same
architecture).
[P-design] The choice of H trades computation against the number of
data points: with m = 15 points, raising the polynomial
degree (larger H) drives the training error down but the
error on fresh data points up — the overfitting limit on the usable
size of H.
[P-size] The size of H anticipates generalization BEFORE training:
the maximal generalization gap over H grows with the
cardinality |H| (finite classes of random threshold maps).
[P-algos] The same H serves different algorithms: ERM on a fixed training set, online
online learning over a stream, and Bayesian inference (a
posterior over a finite H) all operate on one linear
hypothesis space; ERM and online learning agree in the limit,
the posterior concentrates on the same hypothesis.
Outputs
-------
hypospace.png : preview figure (checking only).
Data generated by pythondemos/hypospace.py.
"""
import numpy as np
import matplotlib
matplotlib.use("Agg")
import matplotlib.pyplot as plt
from itertools import product
rng = np.random.default_rng(42)
report = []
def check(name, ok):
report.append((name, bool(ok)))
print(f" [{'ok' if ok else 'FAIL'}] {name}")
The hypothesis space is the committed set of candidate maps, a subset of Y^X: for |X| = 4, |Y| = 2 the full map space has 16 elements, the threshold subset only 5.
print("[P-def] H is a subset of Y^X")
X_space, Y_space = [0, 1, 2, 3], [0, 1]
all_maps = set(product(Y_space, repeat=4))
H_thresh = {tuple(int(x >= t) for x in X_space) for t in range(5)}
check("|Y^X| = 16", len(all_maps) == 16)
check("H (threshold maps) is a strict subset of Y^X",
H_thresh < all_maps)
[P-def] H is a subset of Y^X [ok] |Y^X| = 16 [ok] H (threshold maps) is a strict subset of Y^X
Canonical hypothesis spaces: the linear model (linear maps R^d -> R closed under evaluation) and the set of maps realizable by a fixed ANN architecture as its parameters vary (different parameters, different maps; same architecture).
print("[P-examples] linear model and fixed-architecture ANN as H")
w1, w2 = rng.normal(size=3), rng.normal(size=3)
x = rng.normal(size=3)
check("linear model: every parameter vector w defines the map x -> w^T x",
np.isclose(w1 @ x, np.sum(w1 * x)))
relu = lambda a: np.maximum(a, 0)
ann = lambda W, v, xx: v @ relu(W @ xx) # fixed 3-8-1 architecture
W_a, v_a = rng.normal(size=(8, 3)), rng.normal(size=8)
W_b, v_b = rng.normal(size=(8, 3)), rng.normal(size=8)
check("fixed ANN architecture: different parameters realize different maps",
not np.isclose(ann(W_a, v_a, x), ann(W_b, v_b, x)))
[P-examples] linear model and fixed-architecture ANN as H [ok] linear model: every parameter vector w defines the map x -> w^T x [ok] fixed ANN architecture: different parameters realize different maps
The choice of H trades computation against the number of data points: with m = 15 points, raising the polynomial degree (larger H) drives the training error down but the error on fresh data points up — the overfitting limit on the usable size of H.
print("[P-design] larger H overfits a small trainset")
m = 15
xd = np.sort(rng.uniform(-1, 1, m))
yd = np.sin(2.5 * xd) + 0.15 * rng.normal(size=m)
xv = rng.uniform(-1, 1, 200)
yv = np.sin(2.5 * xv) + 0.15 * rng.normal(size=200)
tr_err, va_err = [], []
for deg in (1, 3, 12):
c = np.polyfit(xd, yd, deg)
tr_err.append(np.mean((yd - np.polyval(c, xd)) ** 2))
va_err.append(np.mean((yv - np.polyval(c, xv)) ** 2))
print(f" train err deg 1,3,12: {tr_err[0]:.3f}, {tr_err[1]:.3f}, "
f"{tr_err[2]:.4f} | val err: {va_err[0]:.3f}, {va_err[1]:.3f}, "
f"{va_err[2]:.1f}")
check("training error decreases with the size of H",
tr_err[0] > tr_err[1] > tr_err[2])
check("the error on fresh data points blows up for the largest H (overfitting)",
va_err[2] > 5 * va_err[1])
[P-design] larger H overfits a small trainset
train err deg 1,3,12: 0.098, 0.009, 0.0012 | val err: 0.098, 0.043, 58356.0
[ok] training error decreases with the size of H
[ok] the error on fresh data points blows up for the largest H (overfitting)
The size of H anticipates generalization BEFORE training: the maximal generalization gap over H grows with the cardinality |H| (finite classes of random threshold maps).
print("[P-size] the size of H bounds the gap before training")
mg = 60
xg = rng.uniform(0, 1, (2000, mg)) # 2000 fresh problems? no:
xg_tr, xg_va = rng.uniform(0, 1, mg), rng.uniform(0, 1, 1000)
yg_tr = (xg_tr > 0.5).astype(float)
yg_va = (xg_va > 0.5).astype(float)
def max_gap(n_hypos):
ts = rng.uniform(0, 1, n_hypos) # random threshold class
gaps = [abs(np.mean((xg_tr > t) != yg_tr)
- np.mean((xg_va > t) != yg_va)) for t in ts]
return max(gaps)
gaps = [np.mean([max_gap(n) for _ in range(30)]) for n in (2, 16, 256)]
print(f" max train-val gap for |H| = 2, 16, 256: "
f"{gaps[0]:.3f}, {gaps[1]:.3f}, {gaps[2]:.3f}")
check("the maximal gap over H grows with |H|", gaps[0] < gaps[1] < gaps[2])
[P-size] the size of H bounds the gap before training
max train-val gap for |H| = 2, 16, 256: 0.042, 0.077, 0.093
[ok] the maximal gap over H grows with |H|
The same H serves different algorithms: ERM on a fixed training set, online online learning over a stream, and Bayesian inference (a posterior over a finite H) all operate on one linear hypothesis space; ERM and online learning agree in the limit, the posterior concentrates on the same hypothesis.
print("[P-algos] one H, three algorithms")
mt = 200
Xa = rng.normal(size=(mt, 2))
w_true = np.array([1.0, -0.5])
ya = Xa @ w_true + 0.1 * rng.normal(size=mt)
w_erm = np.linalg.lstsq(Xa, ya, rcond=None)[0] # ERM on a fixed training set
w_og = np.zeros(2) # online learning on the stream
for t in range(mt):
w_og += 0.05 * (ya[t] - w_og @ Xa[t]) * Xa[t]
H_fin = [w_true, np.array([0.0, 0.0]), np.array([-1.0, 0.5]),
np.array([1.0, 0.5])] # finite H for Bayes
log_post = np.array([-np.sum((ya - Xa @ w) ** 2) / (2 * 0.1**2)
for w in H_fin])
post = np.exp(log_post - log_post.max())
post /= post.sum()
check("batch ERM and online GD agree on the same H (|w| close)",
np.linalg.norm(w_erm - w_og) < 0.1)
check("Bayesian inference returns a distribution over H that "
"concentrates on the best hypothesis",
post[0] > 0.99)
# ------------------------------------------------------------ preview
fig, ax = plt.subplots(1, 2, figsize=(8.6, 3.0))
xx = np.linspace(-1, 1, 300)
ax[0].plot(xd, yd, "ko", ms=4)
for deg, st in ((1, "--"), (3, "-"), (12, ":")):
ax[0].plot(xx, np.polyval(np.polyfit(xd, yd, deg), xx), st,
label=f"deg {deg}")
ax[0].set_ylim(-2, 2); ax[0].legend(frameon=False)
ax[0].set_title("[P-design] size of H vs overfitting")
ax[1].semilogx([2, 16, 256], gaps, "o-")
ax[1].set_xlabel("|H|"); ax[1].set_ylabel("max generalization gap")
ax[1].set_title("[P-size]")
fig.tight_layout()
fig.savefig("hypospace.png", dpi=110)
print(f"\n{sum(ok for _, ok in report)}/{len(report)} checks passed")
assert all(ok for _, ok in report)
[P-algos] one H, three algorithms [ok] batch ERM and online GD agree on the same H (|w| close) [ok] Bayesian inference returns a distribution over H that concentrates on the best hypothesis 9/9 checks passed
P-algos writes when the script runs