Lesson 29: Projection — The Central Idea¶
This begins Part 3 of the course: deep learning for computer vision. Before writing a single neural network, it's worth naming the idea that quietly ran through most of Parts 1 and 2, and that will run through everything from here on: projection — mapping points from one space into another, usually a simpler one, by a linear combination of their coordinates. Nearly every technique so far has secretly been a projection. Neural networks turn out to be nothing more than learned, composed projections.
import numpy as np
import matplotlib.pyplot as plt
Two projections you've already built¶
PCA (Lesson 6). Given a cloud of points, the eigenvectors of their covariance matrix gave directions to project onto. Projecting onto the top eigenvector, $y = v^\top x$, collapses each 2D point to a single number — the coordinate along the direction of greatest spread.
rng = np.random.default_rng(1)
cloud = rng.multivariate_normal([0, 0], [[3, 1.5], [1.5, 1]], 100)
cov = np.cov(cloud.T)
eigvals, eigvecs = np.linalg.eigh(cov)
principal_direction = eigvecs[:, -1] # eigenvector of the largest eigenvalue
projected = cloud @ principal_direction
fig, axes = plt.subplots(1, 2, figsize=(8, 3.5))
axes[0].scatter(cloud[:, 0], cloud[:, 1], s=15, alpha=0.6)
axes[0].plot([0, 3 * principal_direction[0]], [0, 3 * principal_direction[1]], color='red', linewidth=2)
axes[0].set_aspect('equal')
axes[0].set_title('2D cloud + principal direction')
axes[1].scatter(projected, np.zeros_like(projected), s=15, alpha=0.6)
axes[1].set_yticks([])
axes[1].set_title('Projected onto that direction (1D)')
plt.tight_layout()
plt.show()
Camera projection (Lessons 23, 25). $P = K[R|t]$ maps a 3D world point to a 2D pixel. Every row of that matrix, before the final homogeneous divide, is itself a linear projection: a dot product between the point's coordinates and a fixed direction, plus an offset.
Both examples share the same mechanics: pick a direction $w$ (and maybe an offset $b$), then compute $y = w^\top x + b$. What differs is why the direction was chosen: PCA picks $w$ to maximize the spread of the projected data (an unsupervised, purely geometric objective). A camera's rows are fixed by its physical geometry. Neither one is chosen to solve a classification or recognition problem — but nothing stops us from choosing $w$ for exactly that purpose.
A projection for classification¶
Suppose instead of "maximize spread," the goal is "separate two classes." The same formula $y = w^\top x + b$ still applies — project each point onto a direction $w$, and classify by the sign of the resulting score. This is, in its entirety, a single artificial neuron with no activation function: the linear core that every neural network layer is built from.
class_a = rng.normal(loc=[-2, -1], scale=0.8, size=(60, 2))
class_b = rng.normal(loc=[2, 1.5], scale=0.8, size=(60, 2))
# a principled hand-picked direction: point from one class's mean toward the other's
w = class_b.mean(axis=0) - class_a.mean(axis=0)
w = w / np.linalg.norm(w)
midpoint = (class_a.mean(axis=0) + class_b.mean(axis=0)) / 2
b = -w @ midpoint # threshold: the boundary passes through the midpoint between the classes
score_a = class_a @ w + b
score_b = class_b @ w + b
accuracy = (np.sum(score_a < 0) + np.sum(score_b > 0)) / (len(score_a) + len(score_b))
print(f'w = {np.round(w, 3)}, b = {b:.3f}')
print(f'classification accuracy: {accuracy:.1%}')
def plot_projection_classifier(ax, class_a, class_b, w, b, title):
ax.scatter(*class_a.T, s=15, label='class A')
ax.scatter(*class_b.T, s=15, label='class B')
# decision boundary: the line {x : w.x + b = 0}, drawn through its closest point to the origin
foot = -b * w
perp = np.array([-w[1], w[0]])
p1, p2 = foot + 5 * perp, foot - 5 * perp
ax.plot([p1[0], p2[0]], [p1[1], p2[1]], color='black', linewidth=1.5, label='decision boundary')
ax.arrow(*foot, *w, head_width=0.15, color='red', length_includes_head=True, label='w')
ax.set_aspect('equal')
ax.set_title(title, fontsize=9)
fig, axes = plt.subplots(1, 2, figsize=(9, 4))
plot_projection_classifier(axes[0], class_a, class_b, w, b, f'Decision boundary\naccuracy={accuracy:.0%}')
axes[0].legend(fontsize=7)
axes[1].scatter(score_a, np.zeros_like(score_a), s=15, label='class A')
axes[1].scatter(score_b, np.zeros_like(score_b), s=15, label='class B')
axes[1].axvline(0, color='black', linewidth=1.5, label='threshold')
axes[1].set_yticks([])
axes[1].set_title('The same points, projected to 1D')
axes[1].legend(fontsize=7)
plt.tight_layout()
plt.show()
Two views of the exact same operation: on the left, $w$ is a direction in the original 2D space and the decision boundary is the line perpendicular to it; on the right, every point has been projected down onto that direction, and classification is just thresholding a single number at zero. The 2D picture is more intuitive, but the 1D picture is what actually generalizes — in 100 dimensions there's no picture to draw of the "boundary," but "project to a single number, then threshold" still works exactly the same way.
What a single projection cannot do¶
A single linear projection can only ever produce a straight-line decision boundary (a hyperplane, in higher dimensions). Some datasets have no straight-line separator at all, no matter how $w$ and $b$ are chosen — the classic example is one class surrounding the other.
theta_in = rng.uniform(0, 2 * np.pi, 60)
inner = np.stack([0.5 * np.cos(theta_in), 0.5 * np.sin(theta_in)], axis=1) + rng.normal(0, 0.1, (60, 2))
theta_out = rng.uniform(0, 2 * np.pi, 60)
outer = np.stack([2.0 * np.cos(theta_out), 2.0 * np.sin(theta_out)], axis=1) + rng.normal(0, 0.15, (60, 2))
# search many directions and thresholds for the best possible LINEAR separator
best_acc, best_w, best_b = 0, None, None
for _ in range(2000):
w_try = rng.normal(size=2)
w_try /= np.linalg.norm(w_try)
for b_try in np.linspace(-3, 3, 61):
s_in, s_out = inner @ w_try + b_try, outer @ w_try + b_try
acc = max((s_in < 0).sum() + (s_out > 0).sum(), (s_in > 0).sum() + (s_out < 0).sum()) / 120
if acc > best_acc:
best_acc, best_w, best_b = acc, w_try, b_try
print(f'best achievable accuracy with ANY single linear projection: {best_acc:.1%}')
fig, ax = plt.subplots(figsize=(4.5, 4.5))
plot_projection_classifier(ax, inner, outer, best_w, best_b, f'Best possible linear boundary\naccuracy={best_acc:.0%}')
plt.show()
No rotation or shift of a single straight line can separate a ring from the disk it surrounds — the best any linear projection can manage is a mediocre compromise. This is the wall every purely linear method runs into, and it's exactly what motivates the next two lessons: first, learning $w$ and $b$ automatically instead of hand-picking them (Lesson 30), and then, more importantly, composing several projections with nonlinearities in between (Lesson 31), which turns out to be enough to warp even a ring-inside-a-disk into something a straight line can separate.
Exercise¶
- In the PCA recap, project
cloudonto the second (smaller) eigenvector instead of the principal one. How does the spread of the resulting 1D projection compare to projecting onto the principal direction, and why does that match what the eigenvalue itself tells you (Lesson 6)? - Modify
class_a/class_b's means and spread so the classes overlap more. At what point does the mean-difference directionwstop achieving high accuracy, and can you find a betterwthan the mean-difference one by hand for that harder case? - For the ring-and-disk dataset, instead of a linear projection, try classifying by a simple nonlinear function of the points: the distance from the origin, $r = \sqrt{x_1^2+x_2^2}$, thresholded at some value. What accuracy does this one nonlinear feature achieve, and what does that suggest about what kind of projection would actually solve this problem?