P-fit writes when the script runsDictionary of Applied Machine Learning · norm
Numerical companion to the entry norm: 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 without installing anything:uv run https://dictionaryofml.org/terms/norm.py
uv downloads this script and the pinned NumPy and Matplotlib it needs, then runs it; the script fetches any input file it uses. To keep the output files, download norm.py into a folder and run uv run norm.py there. With NumPy and Matplotlib already installed, python3 norm.py, from any directory — it writes its output files into the current directory. Fixed seeds, so the printed numbers reproduce exactly. Download norm.py · Notebook · Open in Colab
One cell per block of the script: the code, and what that code printed when it last ran here
"""
norm.py — numerical companion to the glossary entry 'norm'.
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-axioms] The three norm axioms — definiteness, homogeneity, triangle
inequality — hold for the l1-, l2-, and linf-norms on 10^4
randomly drawn pairs of vectors; the seminorm near miss
u -> |u_1| stays homogeneous and triangle but vanishes on a
non-zero vector.
[P-metric] d(u, v) = ||u - v|| is a metric: symmetry, identity of
indiscernibles, and the triangle inequality checked on random
triples.
[P-inner] The inner product induces the l2-norm: ||u|| = sqrt(<u, u>)
for randomly drawn vectors.
[P-lp] The lp-norm family: the explicit sum formula matches
np.linalg.norm for p in {1, 2, inf}, the linf-norm is the
max absolute entry, and the unit spheres of l1/l2/linf are
nested (||x||_inf <= ||x||_2 <= ||x||_1) — the geometry of
the entry's unit-ball figure.
[P-ml] Norms define losses and regularizers: the squared error loss
is a squared l2-norm of the residual, and the ridge/Lasso
penalty terms evaluate norms of the model parameters.
[P-fit] The choice of norm determines the learned hypothesis: on a
training set of four data points (three on the line y = x,
one outlier), minimizing the l2-norm of the residual (the
squared norm has the same minimizer) gives slope 46/30,
pulled toward the outlier, while minimizing the l1-norm
gives slope 1 exactly — the entry's l2-vs-l1 fit figure.
Outputs
-------
norm.png : preview figure (checking only).
norm_points.csv : the four training data points (x, y).
norm_fits.csv : the l2 and l1 fitted lines (x, l2, l1).
Data generated by pythondemos/norm.py.
"""
import numpy as np
import matplotlib
matplotlib.use("Agg")
import matplotlib.pyplot as plt
from pathlib import Path
OUT_DIR = Path(__file__).parent
rng = np.random.default_rng(42)
report = []
def check(name, ok):
report.append((name, bool(ok)))
print(f" [{'ok' if ok else 'FAIL'}] {name}")
NORMS = {"l1": 1, "l2": 2, "linf": np.inf}
U = rng.normal(size=(10**4, 5))
V = rng.normal(size=(10**4, 5))
The three norm axioms — definiteness, homogeneity, triangle inequality — hold for the l1-, l2-, and linf-norms on 10^4 randomly drawn pairs of vectors; the seminorm near miss u -> |u_1| stays homogeneous and triangle but vanishes on a non-zero vector.
print("[P-axioms] definiteness, homogeneity, triangle inequality")
for name, p in NORMS.items():
nu = np.linalg.norm(U, p, axis=1)
check(f"{name}: norm(0) = 0 and norm(u) > 0 for u != 0",
np.linalg.norm(np.zeros(5), p) == 0 and np.all(nu > 0))
a = rng.normal()
check(f"{name}: homogeneity ||a u|| = |a| ||u||",
np.allclose(np.linalg.norm(a * U, p, axis=1), abs(a) * nu))
check(f"{name}: triangle ||u + v|| <= ||u|| + ||v||",
np.all(np.linalg.norm(U + V, p, axis=1)
<= nu + np.linalg.norm(V, p, axis=1) + 1e-12))
# seminorm near miss: f(u) = |u_1| is homogeneous and satisfies the
# triangle inequality but vanishes on the non-zero vector (0,...,0,1)
f = lambda X: np.abs(np.atleast_2d(X)[:, 0])
a = rng.normal()
check("near miss |u_1|: homogeneous and triangle hold",
np.allclose(f(a * U), abs(a) * f(U))
and np.all(f(U + V) <= f(U) + f(V) + 1e-12))
check("near miss |u_1|: not definite (zero on a non-zero vector)",
np.isclose(f(np.eye(5)[4])[0], 0.0))
[P-axioms] definiteness, homogeneity, triangle inequality [ok] l1: norm(0) = 0 and norm(u) > 0 for u != 0 [ok] l1: homogeneity ||a u|| = |a| ||u|| [ok] l1: triangle ||u + v|| <= ||u|| + ||v|| [ok] l2: norm(0) = 0 and norm(u) > 0 for u != 0 [ok] l2: homogeneity ||a u|| = |a| ||u|| [ok] l2: triangle ||u + v|| <= ||u|| + ||v|| [ok] linf: norm(0) = 0 and norm(u) > 0 for u != 0 [ok] linf: homogeneity ||a u|| = |a| ||u|| [ok] linf: triangle ||u + v|| <= ||u|| + ||v|| [ok] near miss |u_1|: homogeneous and triangle hold [ok] near miss |u_1|: not definite (zero on a non-zero vector)
d(u, v) = ||u - v|| is a metric: symmetry, identity of indiscernibles, and the triangle inequality checked on random triples.
print("[P-metric] d(u, v) = ||u - v|| is a metric")
W = rng.normal(size=(10**4, 5))
d = lambda X, Y: np.linalg.norm(X - Y, 2, axis=1)
check("symmetry d(u, v) = d(v, u)", np.allclose(d(U, V), d(V, U)))
check("d(u, u) = 0", np.all(d(U, U) == 0))
check("d(u, v) > 0 whenever u != v (identity of indiscernibles)",
np.all(d(U, V)[np.any(U != V, axis=1)] > 0))
check("triangle d(u, w) <= d(u, v) + d(v, w)",
np.all(d(U, W) <= d(U, V) + d(V, W) + 1e-12))
[P-metric] d(u, v) = ||u - v|| is a metric [ok] symmetry d(u, v) = d(v, u) [ok] d(u, u) = 0 [ok] d(u, v) > 0 whenever u != v (identity of indiscernibles) [ok] triangle d(u, w) <= d(u, v) + d(v, w)
The inner product induces the l2-norm: ||u|| = sqrt(<u, u>) for randomly drawn vectors.
print("[P-inner] the inner product induces the l2-norm")
check("||u|| = sqrt(<u, u>)",
np.allclose(np.linalg.norm(U, 2, axis=1),
np.sqrt(np.sum(U * U, axis=1))))
[P-inner] the inner product induces the l2-norm [ok] ||u|| = sqrt(<u, u>)
The lp-norm family: the explicit sum formula matches np.linalg.norm for p in {1, 2, inf}, the linf-norm is the max absolute entry, and the unit spheres of l1/l2/linf are nested (||x||_inf <= ||x||_2 <= ||x||_1) — the geometry of the entry's unit-ball figure.
print("[P-lp] the lp family and its unit-ball geometry")
x = rng.normal(size=(10**4, 5))
lp_sum = lambda X, p: (np.sum(np.abs(X) ** p, axis=1)) ** (1 / p)
check("sum formula matches np.linalg.norm for p = 1, 2",
np.allclose(lp_sum(x, 1), np.linalg.norm(x, 1, axis=1))
and np.allclose(lp_sum(x, 2), np.linalg.norm(x, 2, axis=1)))
check("linf-norm is the max absolute entry",
np.allclose(np.linalg.norm(x, np.inf, axis=1),
np.max(np.abs(x), axis=1)))
check("||x||_inf <= ||x||_2 <= ||x||_1 (nested unit balls)",
np.all(np.linalg.norm(x, np.inf, axis=1)
<= np.linalg.norm(x, 2, axis=1) + 1e-12)
and np.all(np.linalg.norm(x, 2, axis=1)
<= np.linalg.norm(x, 1, axis=1) + 1e-12))
[P-lp] the lp family and its unit-ball geometry [ok] sum formula matches np.linalg.norm for p = 1, 2 [ok] linf-norm is the max absolute entry [ok] ||x||_inf <= ||x||_2 <= ||x||_1 (nested unit balls)
Norms define losses and regularizers: the squared error loss is a squared l2-norm of the residual, and the ridge/Lasso penalty terms evaluate norms of the model parameters.
print("[P-ml] norms define losses and regularizers")
Xf = rng.normal(size=(50, 3))
yf = Xf @ np.array([1.0, 0.0, -0.5]) + 0.1 * rng.normal(size=50)
w = np.linalg.lstsq(Xf, yf, rcond=None)[0]
sq_loss = np.mean((yf - Xf @ w) ** 2)
check("squared-error loss = (1/m) ||y - X w||_2^2",
np.isclose(sq_loss, np.linalg.norm(yf - Xf @ w) ** 2 / 50))
check("ridge regularizer alpha ||w||_2^2 and Lasso regularizer "
"alpha ||w||_1 are norm evaluations",
np.isclose(np.linalg.norm(w, 2) ** 2, np.sum(w**2))
and np.isclose(np.linalg.norm(w, 1), np.sum(np.abs(w))))
[P-ml] norms define losses and regularizers [ok] squared-error loss = (1/m) ||y - X w||_2^2 [ok] ridge regularizer alpha ||w||_2^2 and Lasso regularizer alpha ||w||_1 are norm evaluations
The choice of norm determines the learned hypothesis: on a training set of four data points (three on the line y = x, one outlier), minimizing the l2-norm of the residual (the squared norm has the same minimizer) gives slope 46/30, pulled toward the outlier, while minimizing the l1-norm gives slope 1 exactly — the entry's l2-vs-l1 fit figure.
print("[P-fit] the choice of norm determines the learned hypothesis")
x4 = np.array([1.0, 2.0, 3.0, 4.0]) # feature values
y4 = np.array([1.0, 2.0, 3.0, 8.0]) # labels; the last one is an outlier
w_l2 = float(x4 @ y4 / (x4 @ x4)) # minimizes ||y - w x||_2^2
f1 = lambda w: np.sum(np.abs(y4 - np.multiply.outer(w, x4)), axis=-1)
cand = y4 / x4 # the l1 training error attains its
w_l1 = float(cand[np.argmin(f1(cand))]) # minimum at one of these slopes
grid = np.linspace(0.5, 2.5, 20001)
check("l1 fit: slope 1, fits the three regular points exactly and beats "
"every slope on a dense grid",
np.isclose(w_l1, 1.0) and f1(w_l1) <= np.min(f1(grid)) + 1e-9)
check("l2 fit: slope 46/30 > 1, pulled toward the outlier",
np.isclose(w_l2, 46 / 30) and w_l2 > w_l1)
f2 = lambda w: np.sum((y4 - w * x4) ** 2)
check("each fit minimizes its own norm of the residual",
f1(w_l1) < f1(w_l2) and f2(w_l2) < f2(w_l1))
np.savetxt(OUT_DIR / "norm_points.csv",
np.column_stack([x4, y4]),
header="x,y", comments="", delimiter=",", fmt="%.1f")
xs = np.array([0.0, 2.3, 4.6])
np.savetxt(OUT_DIR / "norm_fits.csv",
np.column_stack([xs, w_l2 * xs, w_l1 * xs]),
header="x,l2,l1", comments="", delimiter=",", fmt="%.4f")
# ------------------------------------------------------------ preview
th = np.linspace(0, 2 * np.pi, 400)
circ = np.stack([np.cos(th), np.sin(th)])
fig, (ax, axr) = plt.subplots(1, 2, figsize=(8.0, 4.0))
ax.plot(*(circ / np.linalg.norm(circ, 1, axis=0)), "k--", label="$\\ell_1$")
ax.plot(*circ, "k-", label="$\\ell_2$")
ax.plot(*(circ / np.linalg.norm(circ, np.inf, axis=0)), "k:",
label="$\\ell_\\infty$")
ax.set_xlabel("$x_1$"); ax.set_ylabel("$x_2$")
ax.set_aspect("equal"); ax.legend(frameon=False)
ax.set_title("[P-lp] unit spheres of the $\\ell_1$/$\\ell_2$/$\\ell_\\infty$ norms")
axr.plot(xs, w_l2 * xs, "k-",
label=f"$\\ell_2$ fit: slope {w_l2:.2f}")
axr.plot(xs, w_l1 * xs, "k--",
label=f"$\\ell_1$ fit: slope {w_l1:.0f}")
axr.plot(x4, y4, "ko", label="training set")
axr.annotate("outlier", (x4[-1], y4[-1]), textcoords="offset points",
xytext=(-8, 4), ha="right")
axr.set_xlabel("feature $x$"); axr.set_ylabel("label $y$")
axr.legend(frameon=False)
axr.set_title("[P-fit] the norm of the residual\ndetermines the learned hypothesis")
fig.tight_layout()
fig.savefig(OUT_DIR / "norm.png", dpi=110)
print(f"\n{sum(ok for _, ok in report)}/{len(report)} checks passed")
assert all(ok for _, ok in report)
[P-fit] the choice of norm determines the learned hypothesis [ok] l1 fit: slope 1, fits the three regular points exactly and beats every slope on a dense grid [ok] l2 fit: slope 46/30 > 1, pulled toward the outlier [ok] each fit minimizes its own norm of the residual 24/24 checks passed
P-fit writes when the script runs