Dictionary of Applied Machine Learning · dimensionality reduction

dimensionality reduction — Python demo

Updated on 2026-11-03

Numerical companion to the entry dimensionality reduction: it recomputes what the entry states and prints one line per check

Checks the three benefits the entry attributes to using a shorter feature vector, on the patches of a real photograph: the statistical benefit (less overfitting of linear regression on the learned features than on the raw ones), the computational benefit (the matrix that linear regression inverts shrinks with the number of features), and visualization (two learned features place patches that look alike near each other). It also checks that a random projection approximately preserves distances. Self-contained (numpy and matplotlib only), fixed seed.

Run it without installing anything:
uv run https://dictionaryofml.org/terms/dimred.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 dimred.py into a folder and run uv run dimred.py there. With NumPy and Matplotlib already installed, python3 dimred.py, from any directory — it writes its output files into the current directory. Fixed seeds, so the printed numbers reproduce exactly. Download dimred.py · Notebook · Open in Colab

Before running a downloaded copy, scan it: uvx bandit -q -t B102,B307,B602,B605 dimred.py (B102,B307,B602,B605 are the exec, eval and shell checks of bandit) reports nothing: the script runs no shell command and evaluates no generated code.

The script, block by block

One cell per block of the script: the code, and what that code printed when it last ran here

setup

"""
dimred.py — numerical companion to the glossary entry 'dimensionality
reduction'.

Purpose
-------
Checks the three benefits the entry attributes to using a shorter feature
vector, on the patches of a real photograph: the statistical benefit (less
overfitting of linear regression on the learned features than on the raw
ones), the computational benefit (the matrix that linear regression
inverts shrinks with the number of features), and visualization (two
learned features place patches that look alike near each other).  It also
checks that a random projection approximately preserves distances.
Self-contained (numpy and matplotlib only), fixed seed.

Setup
-----
The photograph of the Oetscher massif (assets/oetscher.jpg) is cut into 128 x 128 pixel patches, 27 rows by
36 columns of them.  Each patch is averaged down to a 4 x 4 grid of colors,
so its raw feature vector is d = 48 numbers.  The label of a patch is how
far down the photograph it sits, 0 at the top row and 1 at the bottom one;
appearance predicts it, since sky is above and meadow below, but not
exactly.  Training set m = 60 patches drawn at random, 400 further patches
to measure the error on new data points.  The learned map is PCA with
d' = 2 features; the random projection uses d' = 20 features and a matrix
of independent Gaussian entries.

Two kinds of patch are named for the scatterplot, from the patch's mean color,
which is NOT what the features are built from in a way that makes the
grouping trivial: a patch counts as sky when its blue channel exceeds both
other channels by more than 0.06, and as vegetation when its green channel
does.  Patches that are neither, such as the grey rock face and the mixed
patches along the tree line, stay unnamed and are drawn as small dots.

Blocks
------
[B-patches] Cut the photograph into patches and build the raw feature
            vector of each: a 4 x 4 grid of colors, 48 numbers.  Also
            writes the photograph with the patch grid drawn on it, the
            top panel of the entry's scatterplot figure.
[B-pca]     PCA with d' = 2 reconstructs the raw features with an average
            squared reconstruction error below 20 percent of their total
            variance.
[B-stat]    Linear regression on the d = 48 raw features reaches an error
            near zero on the training set but an error more than fifty
            times larger on new patches; on the two PCA features the error
            on new patches is no larger than on the training set, and far
            smaller than with the raw features.
[B-comp]    The matrix inverted by linear regression has 48 x 48 entries
            with the raw features and 2 x 2 with the PCA features.
[B-vis]     In the scatterplot of the two PCA features, the sky patches and
            the vegetation patches have centers farther apart than the
            spread within either kind, and nine out of ten patches fall on
            their own side of the midpoint between the centers.
[B-rp]      A random projection to d' = 20 features changes every pairwise
            distance between the 60 training patches by less than a factor
            of two, and the average distance by less than 15 percent.

Outputs
-------
dimred_oetscher_raster.png : the photograph with the patch grid drawn
                     on it; each cell is one patch, i.e. one data point.
dimred_sky.csv, dimred_vegetation.csv, dimred_other.csv :
                     z1, z2 of the patches of each kind.
dimred_errors.csv  : features, nfeatures, err_train, err_new for the raw
                     and the PCA features.
dimred.png         : matplotlib preview (checking only).
"""

# /// script
# requires-python = ">=3.10"
# dependencies = ["matplotlib==3.10.7", "numpy==2.3.4"]
# ///

import urllib.request

import numpy as np
import matplotlib

matplotlib.use("Agg")
import matplotlib.pyplot as plt                        # noqa: E402

from pathlib import Path                               # noqa: E402

OUT_DIR = Path(__file__).parent
ASSET_URL = "https://dictionaryofml.org/demoassets/"


def demo_asset(name):
    """Path to the input file `name`, fetched once if it is not already here.

    Inside the repository the committed copy is used (pythondemos/ first,
    then assets/), so a run there reproduces the committed outputs exactly.
    Run from anywhere else -- from the copy published on dictionaryofml.org,
    say -- the file is downloaded and cached beside the script, so the demo
    is runnable without the repository.
    """
    for cand in (OUT_DIR / name, OUT_DIR.parent / "assets" / name):
        if cand.exists():
            return cand
    cached = OUT_DIR / name
    print(f"    fetching {name} from {ASSET_URL}{name}")
    with urllib.request.urlopen(ASSET_URL + name, timeout=180) as resp:
        cached.write_bytes(resp.read())
    return cached


report = []


def check(name, ok):
    report.append((name, bool(ok)))
    print(f"  [{'ok' if ok else 'FAIL'}] {name}")


rng = np.random.default_rng(0)

PATCH, SIDE = 128, 4                 # pixels per patch, cells per side
MARGIN = 0.06                        # how far one color channel must lead
d_pca, d_rp = 2, 20
m_tr, m_va = 60, 400
  photograph cut into 27 x 36 = 972 patches of 128 x 128 pixels, 48 numbers each

B-patches

Cut the photograph into patches and build the raw feature vector of each: a 4 x 4 grid of colors, 48 numbers. Also writes the photograph with the patch grid drawn on it, the top panel of the entry's scatterplot figure.

photo = plt.imread(demo_asset("oetscher.jpg")) / 255.0
prow, pcol = photo.shape[0] // PATCH, photo.shape[1] // PATCH
tiles = photo[:prow * PATCH, :pcol * PATCH].reshape(
    prow, PATCH, pcol, PATCH, 3)
block = PATCH // SIDE
X = (tiles.reshape(prow, SIDE, block, pcol, SIDE, block, 3)
          .mean(axis=(2, 5))
          .transpose(0, 2, 1, 3, 4)
          .reshape(prow * pcol, SIDE * SIDE * 3))
d = X.shape[1]
colour = tiles.mean(axis=(1, 3)).reshape(-1, 3)      # mean color per patch
row_of = np.repeat(np.arange(prow), pcol)
y = row_of / (prow - 1.0)                            # how far down the photo
sky = (colour[:, 2] - np.maximum(colour[:, 0], colour[:, 1])) > MARGIN
veg = (colour[:, 1] - np.maximum(colour[:, 0], colour[:, 2])) > MARGIN
print(f"  photograph cut into {prow} x {pcol} = {len(X)} patches of "
      f"{PATCH} x {PATCH} pixels, {d} numbers each")
check(f"[B-patches] every patch has a raw feature vector of {d} numbers",
      X.shape == (prow * pcol, SIDE * SIDE * 3))
check(f"[B-patches] {int(sky.sum())} patches count as sky and "
      f"{int(veg.sum())} as vegetation, the rest as neither",
      sky.sum() > 100 and veg.sum() > 100 and not np.any(sky & veg))

# the photograph with the patch grid drawn on it, for the entry's figure:
# the reader sees what one data point is before reading the scatterplot
# below it (author, 2026-10-17; the same panel the kmeans entry carries)
def shrink_to_width(img, width_px):
    """Area-average an image down to width_px, keeping its aspect ratio.

    Each output pixel is the mean of the input it covers, which is the right
    filter for a photograph and needs nothing beyond numpy.
    """
    if img.shape[1] <= width_px:
        return np.asarray(img, dtype=float)
    height_px = round(img.shape[0] * width_px / img.shape[1])
    out = np.asarray(img, dtype=float)
    for axis, n_out in ((1, width_px), (0, height_px)):
        n_in = out.shape[axis]
        edges = np.linspace(0.0, n_in, n_out + 1)
        cum = np.cumsum(out, axis=axis)
        cum = np.concatenate(
            [np.zeros_like(np.take(cum, [0], axis=axis)), cum], axis=axis)
        grid = np.arange(n_in + 1)
        cum = np.apply_along_axis(
            lambda col, g=grid, e=edges: np.interp(e, g, col), axis, cum)
        shape = [1] * out.ndim
        shape[axis] = n_out
        out = np.diff(cum, axis=axis) / np.diff(edges).reshape(shape)
    return out


# The panel is printed at 0.56\textwidth, and the book's textwidth is 5.40 in,
# so it is 3.02 in across on the page; at 300 ppi that is 907 px against the
# 1152 px of the full-detail view, which went into the PDF at 381 ppi and was
# the largest single object in the book. The photograph is shrunk first and the
# patch rules drawn afterwards, so every rule stays exactly one white pixel;
# shrinking the ruled image would blur the rules, which are what shows the
# reader the extent of one data point.
SHRINK, TARGET_DPI = 4, 300
RASTER_WIDTH_IN = 3.02
view = photo[:prow * PATCH, :pcol * PATCH, :][::SHRINK, ::SHRINK]
cell = -(-round(RASTER_WIDTH_IN * TARGET_DPI) // pcol)   # ceil: at least 300 ppi
view = shrink_to_width(view, pcol * cell)
view[::cell, :, :] = 1.0                             # horizontal rules
view[:, ::cell, :] = 1.0                             # vertical rules
view[-1, :, :] = 1.0
view[:, -1, :] = 1.0
plt.imsave(OUT_DIR / "dimred_oetscher_raster.png", np.clip(view, 0.0, 1.0))
check("[B-patches] the patch grid has one cell per patch",
      view.shape[:2] == (prow * cell, pcol * cell))

idx = rng.permutation(len(X))
tr, va = idx[:m_tr], idx[m_tr:m_tr + m_va]
  [ok] [B-patches] every patch has a raw feature vector of 48 numbers
  [ok] [B-patches] 386 patches count as sky and 141 as vegetation, the rest as neither
  [ok] [B-patches] the patch grid has one cell per patch

B-pca

PCA with d' = 2 reconstructs the raw features with an average squared reconstruction error below 20 percent of their total variance.

mu = X[tr].mean(axis=0)
C = (X[tr] - mu).T @ (X[tr] - mu) / m_tr
evals, evecs = np.linalg.eigh(C)
W = evecs[:, ::-1][:, :d_pca]                        # d x d' map
Z = (X - mu) @ W
recon = mu + Z[tr] @ W.T
rec_err = float(np.mean(np.sum((X[tr] - recon) ** 2, axis=1)))
total_var = float(np.trace(C))
check(f"[B-pca]   average squared reconstruction error {rec_err:.4f} = "
      f"{100 * rec_err / total_var:.1f} percent of the total variance "
      f"{total_var:.4f}", rec_err / total_var < 0.2)
  [ok] [B-pca]   average squared reconstruction error 0.4548 = 14.2 percent of the total variance 3.2014

B-stat

Linear regression on the d = 48 raw features reaches an error near zero on the training set but an error more than fifty times larger on new patches; on the two PCA features the error on new patches is no larger than on the training set, and far smaller than with the raw features.

def linreg(Xa, ya, Xb, yb):
    A = np.c_[Xa, np.ones(len(Xa))]
    B = np.c_[Xb, np.ones(len(Xb))]
    w = np.linalg.lstsq(A, ya, rcond=None)[0]
    return float(np.mean((ya - A @ w) ** 2)), float(np.mean((yb - B @ w) ** 2))


tr_raw, va_raw = linreg(X[tr], y[tr], X[va], y[va])
tr_pca, va_pca = linreg(Z[tr], y[tr], Z[va], y[va])
check(f"[B-stat]  raw features: error {tr_raw:.4f} on the training set, "
      f"{va_raw:.3f} on new patches; PCA features: {tr_pca:.4f} and "
      f"{va_pca:.4f}",
      va_raw > 50 * tr_raw and va_pca <= tr_pca and va_pca < va_raw / 10)
  [ok] [B-stat]  raw features: error 0.0033 on the training set, 0.833 on new patches; PCA features: 0.0427 and 0.0353

B-comp

The matrix inverted by linear regression has 48 x 48 entries with the raw features and 2 x 2 with the PCA features.

size_raw = (X[tr].T @ X[tr]).shape
size_pca = (Z[tr].T @ Z[tr]).shape
check(f"[B-comp]  matrix to invert: {size_raw[0]} x {size_raw[1]} entries "
      f"with raw features, {size_pca[0]} x {size_pca[1]} with PCA features",
      size_raw == (d, d) and size_pca == (d_pca, d_pca))
  [ok] [B-comp]  matrix to invert: 48 x 48 entries with raw features, 2 x 2 with PCA features

B-vis

In the scatterplot of the two PCA features, the sky patches and the vegetation patches have centers farther apart than the spread within either kind, and nine out of ten patches fall on their own side of the midpoint between the centers.

c_sky, c_veg = Z[sky].mean(axis=0), Z[veg].mean(axis=0)
u = (c_veg - c_sky) / np.linalg.norm(c_veg - c_sky)
mid = 0.5 * (c_sky + c_veg)
spread = max(((Z[sky] - c_sky) @ u).std(), ((Z[veg] - c_veg) @ u).std())
sep = float(np.linalg.norm(c_veg - c_sky))
share = float(np.mean(np.concatenate([(Z[sky] - mid) @ u < 0.0,
                                      (Z[veg] - mid) @ u > 0.0])))
check(f"[B-vis]   centers of sky and vegetation {sep:.2f} apart in the "
      f"scatterplot, spread within either at most {spread:.2f}, and "
      f"{100 * share:.0f} percent of these patches on their own side",
      sep > 2.0 * spread and share > 0.9)
  [ok] [B-vis]   centers of sky and vegetation 2.64 apart in the scatterplot, spread within either at most 0.92, and 93 percent of these patches on their own side

B-rp

A random projection to d' = 20 features changes every pairwise distance between the 60 training patches by less than a factor of two, and the average distance by less than 15 percent.

R = rng.standard_normal((d, d_rp)) / np.sqrt(d_rp)
P_tr = X[tr] @ R


def pairwise(A):
    diff = A[:, None, :] - A[None, :, :]
    return np.sqrt((diff ** 2).sum(axis=2))[np.triu_indices(len(A), 1)]


ratio = pairwise(P_tr) / pairwise(X[tr])
check(f"[B-rp]    random projection to {d_rp} features: distance ratios "
      f"in [{ratio.min():.2f}, {ratio.max():.2f}], mean {ratio.mean():.3f}",
      ratio.min() > 0.5 and ratio.max() < 2.0 and abs(ratio.mean() - 1) < 0.15)

# ---------------------------------------------------------------- CSV
kind = np.where(sky, 0, np.where(veg, 1, 2))
# One file per kind: a pgfplots \addplot reads a whole table, and filtering
# rows by a column inside the figure needs a preamble macro the book does
# not carry.
for name, sel in (("sky", sky), ("vegetation", veg), ("other", kind == 2)):
    with open(OUT_DIR / f"dimred_{name}.csv", "w") as fh:
        fh.write("z1,z2\n")
        for z in Z[sel]:
            fh.write(f"{z[0]:.4f},{z[1]:.4f}\n")
with open(OUT_DIR / "dimred_errors.csv", "w") as fh:
    fh.write("features,nfeatures,err_train,err_new\n")
    fh.write(f"raw,{d},{tr_raw:.4f},{va_raw:.4f}\n")
    fh.write(f"pca,{d_pca},{tr_pca:.4f},{va_pca:.4f}\n")

# -------------------------------------------------------------- preview
fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(9.2, 3.9))
ax1.plot(Z[kind == 2, 0], Z[kind == 2, 1], ".", color="0.6", ms=3,
         label="neither")
ax1.plot(Z[sky, 0], Z[sky, 1], "o", color="k", mfc="none", ms=5,
         label="sky")
ax1.plot(Z[veg, 0], Z[veg, 1], "^", color="k", mfc="k", ms=5,
         label="vegetation")
ax1.set_xlabel("learned feature $z_1$")
ax1.set_ylabel("learned feature $z_2$")
ax1.set_title("two learned features separate sky from vegetation")
ax1.legend(frameon=False, fontsize=8)
xs = np.arange(2)
ax2.plot(xs, [tr_raw, tr_pca], "ko-", ms=7, lw=1.0,
         label="error on the training set")
ax2.plot(xs, [va_raw, va_pca], "k^--", mfc="none", ms=8, lw=1.0,
         label="error on new patches")
ax2.set_yscale("log")
ax2.set_xticks(xs)
ax2.set_xticklabels([f"{d} raw features", f"{d_pca} PCA features"])
ax2.set_xlim(-0.5, 1.5)
ax2.set_ylabel("average squared error")
ax2.set_xlabel("features used by linear regression")
ax2.set_title("fewer features, less overfitting")
ax2.legend(frameon=False, fontsize=8)
fig.tight_layout()
fig.savefig(OUT_DIR / "dimred.png", dpi=110)

n_ok = sum(ok for _, ok in report)
print(f"\n{n_ok}/{len(report)} checks pass")
print(f"wrote dimred_sky.csv, dimred_vegetation.csv, dimred_other.csv, "
      f"dimred_errors.csv, dimred_oetscher_raster.png, dimred.png "
      f"in {OUT_DIR}")
if n_ok != len(report):
    raise SystemExit(1)
  [ok] [B-rp]    random projection to 20 features: distance ratios in [0.60, 1.43], mean 1.001

8/8 checks pass
wrote dimred_sky.csv, dimred_vegetation.csv, dimred_other.csv, dimred_errors.csv, dimred_oetscher_raster.png, dimred.png in /Users/junga1/dictionaryappliedml/pythondemos
Preview figure produced by dimred.py
The preview figure the block B-rp writes when the script runs