Chapter 10: Linear Separability — A Deep Dive#
Making the Concept Precise#
Linear separability is the central concept governing what a single-layer perceptron can and cannot compute. In previous chapters, we encountered it informally through examples like AND (separable) and XOR (not separable). In this chapter, we develop the theory systematically: formal definitions, the convex hull criterion with proof, Cover’s function counting theorem, VC dimension, and the powerful idea of lifting data into higher-dimensional spaces where separability is recovered.
These ideas form the mathematical backbone connecting perceptrons to support vector machines, kernel methods, and the broader theory of statistical learning.
Show code cell source
import numpy as np
import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D
from itertools import combinations
plt.rcParams.update({
'figure.figsize': (8, 6),
'font.size': 12,
'axes.grid': True,
'grid.alpha': 0.3
})
1. Formal Definition#
Definition. Two finite sets \(A, B \subset \mathbb{R}^n\) are linearly separable if there exist a weight vector \(\mathbf{w} \in \mathbb{R}^n\) and a bias \(b \in \mathbb{R}\) such that:
The separating hyperplane is the set:
This is an \((n-1)\)-dimensional affine subspace of \(\mathbb{R}^n\):
In \(\mathbb{R}^2\): \(H\) is a line.
In \(\mathbb{R}^3\): \(H\) is a plane.
In \(\mathbb{R}^n\): \(H\) is a hyperplane.
Geometric Interpretation#
The weight vector \(\mathbf{w}\) is normal (perpendicular) to the hyperplane \(H\). The bias \(b\) controls the offset of the hyperplane from the origin. Points in \(A\) lie on the positive side of \(H\) (where \(\mathbf{w} \cdot \mathbf{x} + b > 0\)), and points in \(B\) lie on the negative side.
Equivalence with Perceptron Computation#
A perceptron with weight vector \(\mathbf{w}\) and bias \(b\) computes:
Therefore, a perceptron can classify \(A\) vs. \(B\) correctly if and only if \(A\) and \(B\) are linearly separable.
2. The Convex Hull Criterion#
The most elegant characterization of linear separability uses the concept of convex hulls.
Definition. The convex hull of a finite set \(S = \{\mathbf{x}_1, \ldots, \mathbf{x}_m\} \subset \mathbb{R}^n\) is:
It is the smallest convex set containing \(S\), or equivalently, the set of all convex combinations of points in \(S\).
Theorem (Convex Hull Separability)
Two finite sets \(A, B \subset \mathbb{R}^n\) are linearly separable if and only if their convex hulls are disjoint:
This provides a purely geometric characterization: instead of searching over all possible hyperplanes, you only need to check whether two convex bodies overlap.
Proof
\((\Rightarrow)\) Separable implies disjoint convex hulls.
Assume \(A\) and \(B\) are separated by the hyperplane \(\mathbf{w} \cdot \mathbf{x} + b = 0\), so:
\(\mathbf{w} \cdot \mathbf{a} + b > 0\) for all \(\mathbf{a} \in A\)
\(\mathbf{w} \cdot \mathbf{b}' + b \leq 0\) for all \(\mathbf{b}' \in B\)
Let \(\mathbf{p} \in \text{conv}(A)\), so \(\mathbf{p} = \sum_i \lambda_i \mathbf{a}_i\) with \(\lambda_i \geq 0\), \(\sum \lambda_i = 1\). Then:
since each term is positive and the \(\lambda_i\) are non-negative with sum 1.
Similarly, let \(\mathbf{q} \in \text{conv}(B)\), so \(\mathbf{q} = \sum_j \mu_j \mathbf{b}_j\). Then:
Therefore \(\mathbf{w} \cdot \mathbf{p} + b > 0 \geq \mathbf{w} \cdot \mathbf{q} + b\), so \(\mathbf{p} \neq \mathbf{q}\). Since \(\mathbf{p}\) and \(\mathbf{q}\) were arbitrary, \(\text{conv}(A) \cap \text{conv}(B) = \emptyset\).
\((\Leftarrow)\) Disjoint convex hulls implies separable.
If \(\text{conv}(A) \cap \text{conv}(B) = \emptyset\), then we have two disjoint compact convex sets (compact because they are convex hulls of finite sets). By the Separating Hyperplane Theorem (a fundamental result in convex analysis), there exists a hyperplane \(\mathbf{w} \cdot \mathbf{x} + b = 0\) that strictly separates them. In particular, \(\mathbf{w} \cdot \mathbf{x} + b > 0\) for all \(\mathbf{x} \in \text{conv}(A) \supseteq A\) and \(\mathbf{w} \cdot \mathbf{x} + b < 0\) for all \(\mathbf{x} \in \text{conv}(B) \supseteq B\). \(\blacksquare\)
3. Convex Hull Visualization#
Let us visualize the convex hull criterion for several 2D datasets, both separable and non-separable.
Show code cell source
# Compute convex hull of 2D points (Graham scan)
def convex_hull_2d(points):
"""Compute the convex hull of 2D points using Graham scan.
Returns the hull vertices in counter-clockwise order."""
points = np.array(points)
if len(points) <= 1:
return points
if len(points) == 2:
return points
# Find the point with the lowest y-coordinate (leftmost if tie)
start = np.lexsort((points[:, 0], points[:, 1]))[0]
pivot = points[start]
# Sort by polar angle with respect to pivot
def angle_key(p):
return np.arctan2(p[1] - pivot[1], p[0] - pivot[0])
indices = list(range(len(points)))
indices.sort(key=lambda i: (angle_key(points[i]), np.linalg.norm(points[i] - pivot)))
def cross(o, a, b):
return (a[0]-o[0])*(b[1]-o[1]) - (a[1]-o[1])*(b[0]-o[0])
hull = []
for idx in indices:
while len(hull) >= 2 and cross(points[hull[-2]], points[hull[-1]], points[idx]) <= 0:
hull.pop()
hull.append(idx)
return points[hull]
def check_hull_intersection(hull_A, hull_B):
"""Simple check if two convex polygons (given as hull vertices) intersect.
Uses the Separating Axis Theorem (SAT)."""
def get_edges(hull):
edges = []
n = len(hull)
for i in range(n):
edge = hull[(i+1) % n] - hull[i]
edges.append(edge)
return edges
def project(hull, axis):
projections = np.dot(hull, axis)
return projections.min(), projections.max()
for hull in [hull_A, hull_B]:
if len(hull) < 2:
continue
edges = get_edges(hull)
for edge in edges:
# Normal to the edge
normal = np.array([-edge[1], edge[0]])
if np.linalg.norm(normal) < 1e-10:
continue
normal = normal / np.linalg.norm(normal)
min_A, max_A = project(hull_A, normal)
min_B, max_B = project(hull_B, normal)
if max_A < min_B - 1e-10 or max_B < min_A - 1e-10:
return False # Found a separating axis
return True # No separating axis found => intersection
print("Convex hull and intersection checking functions defined.")
Convex hull and intersection checking functions defined.
Show code cell source
# Generate and visualize several datasets
np.random.seed(42)
datasets = [
# (name, class_A, class_B)
("Separable: Two Clusters",
np.random.randn(8, 2) * 0.5 + np.array([-2, 0]),
np.random.randn(8, 2) * 0.5 + np.array([2, 0])),
("Separable: Diagonal",
np.random.randn(8, 2) * 0.4 + np.array([-1.5, -1.5]),
np.random.randn(8, 2) * 0.4 + np.array([1.5, 1.5])),
("NOT Separable: XOR Pattern",
np.array([[0, 0], [1, 1]]) + np.random.randn(2, 2) * 0.15,
np.array([[0, 1], [1, 0]]) + np.random.randn(2, 2) * 0.15),
("NOT Separable: Interleaved",
np.array([[-1, 0], [0, 1], [1, 0], [0, -1.0]]),
np.array([[0, 0], [-0.5, 0.5], [0.5, 0.5], [0, -0.3]]))
]
fig, axes = plt.subplots(2, 2, figsize=(14, 12))
for idx, (name, A, B) in enumerate(datasets):
ax = axes[idx // 2][idx % 2]
# Compute convex hulls
hull_A = convex_hull_2d(A)
hull_B = convex_hull_2d(B)
# Check intersection
intersects = check_hull_intersection(hull_A, hull_B)
separable = not intersects
# Plot points
ax.scatter(A[:, 0], A[:, 1], c='blue', s=100, zorder=5,
edgecolors='black', linewidths=1.5, marker='o', label='Class A')
ax.scatter(B[:, 0], B[:, 1], c='red', s=100, zorder=5,
edgecolors='black', linewidths=1.5, marker='s', label='Class B')
# Draw convex hulls
if len(hull_A) >= 3:
hull_closed = np.vstack([hull_A, hull_A[0]])
ax.fill(hull_A[:, 0], hull_A[:, 1], alpha=0.15, color='blue')
ax.plot(hull_closed[:, 0], hull_closed[:, 1], 'b-', linewidth=2, alpha=0.5)
elif len(hull_A) == 2:
ax.plot(hull_A[:, 0], hull_A[:, 1], 'b-', linewidth=2, alpha=0.5)
if len(hull_B) >= 3:
hull_closed = np.vstack([hull_B, hull_B[0]])
ax.fill(hull_B[:, 0], hull_B[:, 1], alpha=0.15, color='red')
ax.plot(hull_closed[:, 0], hull_closed[:, 1], 'r-', linewidth=2, alpha=0.5)
elif len(hull_B) == 2:
ax.plot(hull_B[:, 0], hull_B[:, 1], 'r-', linewidth=2, alpha=0.5)
# Title with separability status
color = 'green' if separable else 'red'
status = 'SEPARABLE' if separable else 'NOT SEPARABLE'
ax.set_title(f"{name}\nConvex hulls {'disjoint' if separable else 'overlap'} => {status}",
fontsize=12, color=color)
ax.legend(fontsize=10)
ax.set_aspect('equal')
ax.grid(True, alpha=0.3)
plt.suptitle('Convex Hull Criterion for Linear Separability', fontsize=15, y=1.01)
plt.tight_layout()
plt.show()
4. Cover’s Function Counting Theorem#
A fundamental question in the theory of linear separability is: how many of the possible labelings of \(m\) points can be achieved by a hyperplane in \(\mathbb{R}^d\)?
Setting#
Given \(m\) points \(\mathbf{x}_1, \ldots, \mathbf{x}_m \in \mathbb{R}^d\) in general position (meaning no \(d+1\) points lie on a common hyperplane), a dichotomy is a partition of the points into two classes. There are \(2^m\) possible dichotomies.
A dichotomy is linearly realizable if there exists a hyperplane separating the two classes.
Theorem (Cover, 1965)
The number of linearly realizable dichotomies of \(m\) points in general position in \(\mathbb{R}^d\) is:
Properties:
When \(m \leq d+1\): \(C(m, d) = 2^m\). All dichotomies are realizable (the points can be shattered).
When \(m = 2(d+1)\): \(C(m, d) \approx 2^{m-1}\). Approximately half of all dichotomies are realizable.
When \(m \gg d\): \(C(m, d) \ll 2^m\). Almost no dichotomies are realizable.
There is a sharp phase transition around \(m = 2d\): below this threshold, most dichotomies are separable; above it, most are not.
Tip
Why higher dimensions help separability (Cover’s theorem).
Cover’s theorem reveals a profound principle: data that is not separable in low dimensions often becomes separable in high dimensions. The fraction of realizable dichotomies depends on the ratio \(m/d\) (number of points to number of dimensions). If you double the number of dimensions while keeping the number of points fixed, you go from “almost no dichotomies work” to “almost all dichotomies work.” This is the mathematical foundation for:
Feature engineering: adding computed features increases dimension
Kernel methods: implicitly mapping to high-dimensional feature spaces
Hidden layers in neural networks: the hidden layer creates a high-dimensional representation where the output layer can separate the classes
Show code cell source
# Cover's Function Counting Theorem: computation and visualization
from math import comb
def cover_count(m, d):
"""Number of linearly realizable dichotomies of m points in R^d."""
return 2 * sum(comb(m - 1, k) for k in range(d + 1))
# Table of C(m, d)
print("Cover's Function C(m, d): Number of realizable dichotomies")
print("=" * 65)
print(f"{'m':>4}", end="")
for d in range(1, 7):
print(f"{'d='+str(d):>10}", end="")
print(f"{'2^m':>10}")
print("-" * 65)
for m in range(1, 13):
print(f"{m:>4}", end="")
for d in range(1, 7):
c = cover_count(m, d)
total = 2**m
if c >= total:
print(f"{'ALL':>10}", end="")
else:
print(f"{c:>10}", end="")
print(f"{2**m:>10}")
Cover's Function C(m, d): Number of realizable dichotomies
=================================================================
m d=1 d=2 d=3 d=4 d=5 d=6 2^m
-----------------------------------------------------------------
1 ALL ALL ALL ALL ALL ALL 2
2 ALL ALL ALL ALL ALL ALL 4
3 6 ALL ALL ALL ALL ALL 8
4 8 14 ALL ALL ALL ALL 16
5 10 22 30 ALL ALL ALL 32
6 12 32 52 62 ALL ALL 64
7 14 44 84 114 126 ALL 128
8 16 58 128 198 240 254 256
9 18 74 186 326 438 494 512
10 20 92 260 512 764 932 1024
11 22 112 352 772 1276 1696 2048
12 24 134 464 1124 2048 2972 4096
Show code cell source
# Plot: fraction of realizable dichotomies as m grows
fig, axes = plt.subplots(1, 2, figsize=(14, 5))
# Left: fraction for several dimensions
ax1 = axes[0]
for d in [1, 2, 3, 5, 10]:
m_vals = np.arange(1, 8 * d + 1)
fractions = [min(cover_count(m, d) / 2**m, 1.0) for m in m_vals]
ax1.plot(m_vals / (2*d), fractions, '-', linewidth=2, label=f'd = {d}')
ax1.axvline(x=1, color='black', linestyle='--', alpha=0.5, label='$m = 2d$ (transition)')
ax1.set_xlabel('$m / (2d)$', fontsize=13)
ax1.set_ylabel('Fraction of realizable dichotomies', fontsize=12)
ax1.set_title('Cover\'s Theorem: Phase Transition at $m \\approx 2d$', fontsize=13)
ax1.legend(fontsize=10)
ax1.grid(True, alpha=0.3)
ax1.set_ylim(-0.05, 1.1)
# Right: absolute count for d=2
ax2 = axes[1]
d = 2
m_vals = np.arange(1, 20)
cover_vals = [cover_count(m, d) for m in m_vals]
total_vals = [2**m for m in m_vals]
ax2.semilogy(m_vals, total_vals, 'r-o', markersize=5, label=f'$2^m$ (all dichotomies)')
ax2.semilogy(m_vals, cover_vals, 'b-s', markersize=5, label=f'$C(m, {d})$ (realizable)')
ax2.axvline(x=2*(d+1), color='green', linestyle='--', alpha=0.7,
label=f'$m = 2(d+1) = {2*(d+1)}$ (half-point)')
ax2.set_xlabel('$m$ (number of points)', fontsize=13)
ax2.set_ylabel('Number of dichotomies (log scale)', fontsize=12)
ax2.set_title(f'$d = {d}$: Realizable vs. Total Dichotomies', fontsize=13)
ax2.legend(fontsize=10)
ax2.grid(True, alpha=0.3)
plt.tight_layout()
plt.show()
/var/folders/z7/wp7m8p7x1250jzvklw5z24mm0000gn/T/ipykernel_46000/2536969230.py:9: RuntimeWarning: divide by zero encountered in scalar divide
fractions = [min(cover_count(m, d) / 2**m, 1.0) for m in m_vals]
4a. Graph of Cover’s Counting Function#
Let us plot the number of linearly separable dichotomies \(C(m,d)\) versus the number of points \(m\) for several dimensions \(d\), overlaid with \(2^m\) to see where the gap opens.
Show code cell source
import numpy as np
import matplotlib.pyplot as plt
from math import comb
def cover_count(m, d):
"""Number of linearly realizable dichotomies of m points in R^d."""
return 2 * sum(comb(m - 1, k) for k in range(d + 1))
fig, axes = plt.subplots(1, 2, figsize=(16, 6))
# Left panel: C(m,d) for various d on log scale
ax1 = axes[0]
colors = ['#1f77b4', '#ff7f0e', '#2ca02c', '#d62728', '#9467bd']
dims = [1, 2, 3, 5, 10]
for i, d in enumerate(dims):
m_vals = np.arange(1, 6 * d + 1)
c_vals = [cover_count(int(m), d) for m in m_vals]
total_vals = [2**int(m) for m in m_vals]
ax1.semilogy(m_vals, c_vals, '-o', color=colors[i], markersize=3,
linewidth=2, label=f'$C(m, {d})$')
# Also plot 2^m
m_all = np.arange(1, 61)
ax1.semilogy(m_all, [2**int(m) for m in m_all], 'k--', linewidth=2, alpha=0.5, label='$2^m$ (all)')
ax1.set_xlabel('$m$ (number of points)', fontsize=13)
ax1.set_ylabel('Number of dichotomies (log scale)', fontsize=12)
ax1.set_title('Cover\'s Counting Function $C(m,d)$\nvs. total dichotomies $2^m$', fontsize=13)
ax1.legend(fontsize=10, loc='lower right')
ax1.grid(True, alpha=0.3)
ax1.set_xlim(1, 60)
# Right panel: fraction C(m,d) / 2^m showing the phase transition
ax2 = axes[1]
for i, d in enumerate(dims):
m_vals = np.arange(1, 8 * d + 1)
fractions = [min(cover_count(int(m), d) / 2**int(m), 1.0) for m in m_vals]
ax2.plot(m_vals, fractions, '-', color=colors[i], linewidth=2, label=f'd = {d}')
# Mark the transition point m = 2d
ax2.axvline(x=2*d, color=colors[i], linestyle=':', alpha=0.3)
ax2.set_xlabel('$m$ (number of points)', fontsize=13)
ax2.set_ylabel('Fraction $C(m,d) / 2^m$', fontsize=12)
ax2.set_title('Phase Transition: Fraction of Separable Dichotomies\n'
'Dotted lines mark $m = 2d$', fontsize=13)
ax2.legend(fontsize=10)
ax2.grid(True, alpha=0.3)
ax2.set_ylim(-0.05, 1.1)
plt.tight_layout()
plt.show()
print("Key observation: For each dimension d, the fraction of separable dichotomies")
print("drops sharply around m = 2d points. This is the phase transition.")
print("Higher dimensions push the transition to more points --- this is why")
print("mapping to higher dimensions helps with separability.")
Key observation: For each dimension d, the fraction of separable dichotomies
drops sharply around m = 2d points. This is the phase transition.
Higher dimensions push the transition to more points --- this is why
mapping to higher dimensions helps with separability.
5. VC Dimension#
The Vapnik-Chervonenkis (VC) dimension formalizes the expressive power of a hypothesis class.
Definition (VC Dimension)
Shattering. A hypothesis class \(\mathcal{H}\) shatters a set of points \(S = \{\mathbf{x}_1, \ldots, \mathbf{x}_m\}\) if for every possible labeling \((y_1, \ldots, y_m) \in \{0, 1\}^m\), there exists \(h \in \mathcal{H}\) such that \(h(\mathbf{x}_i) = y_i\) for all \(i\). In other words, \(\mathcal{H}\) can realize all \(2^m\) dichotomies of \(S\).
VC Dimension. The VC dimension of \(\mathcal{H}\) is:
It is the largest number of points that can be arranged so that the hypothesis class can realize every possible labeling. Note the existential quantifier: we only need one arrangement of \(m\) points that can be shattered, not all arrangements.
VC Dimension of Perceptrons#
Theorem. The VC dimension of the class of perceptrons (linear classifiers) in \(\mathbb{R}^n\) is \(n + 1\).
Proof
Proof sketch:
VC dim \(\geq n+1\): Take \(n+1\) points in general position (e.g., the origin plus the \(n\) standard basis vectors). Any labeling can be achieved by a hyperplane. This follows from the fact that \(n+1\) points in general position in \(\mathbb{R}^n\) always have \(C(n+1, n) = 2^{n+1}\) realizable dichotomies (by Cover’s theorem, since \(m = n+1 \leq n+1 = d+1\)).
VC dim \(\leq n+1\): By Radon’s theorem, any set of \(n+2\) points in \(\mathbb{R}^n\) can be partitioned into two disjoint subsets \(P, Q\) such that \(\text{conv}(P) \cap \text{conv}(Q) \neq \emptyset\). The labeling that assigns one class to \(P\) and the other to \(Q\) cannot be realized by any hyperplane (by the Convex Hull Criterion). Therefore no set of \(n+2\) points can be shattered. \(\blacksquare\)
Danger
Curse of dimensionality — more dimensions do NOT always help.
While Cover’s theorem shows that higher dimensions increase the fraction of separable dichotomies, there is a hidden cost: the curse of dimensionality. In high-dimensional spaces:
Data becomes sparse: the volume of the space grows exponentially, so the same number of data points covers an exponentially smaller fraction.
Distance concentration: all pairwise distances become nearly equal, making nearest-neighbor methods unreliable.
Overfitting: with enough dimensions, any dataset becomes trivially separable, but the resulting classifier generalizes poorly.
The VC dimension gives us a quantitative handle on this tradeoff: a hypothesis class with VC dimension \(d\) needs roughly \(O(d / \epsilon^2)\) training examples to generalize well (by the VC theorem). So increasing dimension helps separability but hurts generalization — unless the training set grows proportionally.
Show code cell source
# VC Dimension visualization: 3 points in R^2, all 8 dichotomies
# Choose 3 points in general position
points = np.array([[0, 0], [1, 0], [0.5, 0.87]])
fig, axes = plt.subplots(2, 4, figsize=(16, 8))
# All 8 labelings of 3 points
for idx in range(8):
ax = axes[idx // 4][idx % 4]
labels = [(idx >> i) & 1 for i in range(3)]
# Plot points
for i, (pt, lbl) in enumerate(zip(points, labels)):
color = 'red' if lbl == 1 else 'blue'
marker = 's' if lbl == 1 else 'o'
ax.scatter(pt[0], pt[1], c=color, s=200, marker=marker,
edgecolors='black', linewidths=2, zorder=5)
# Find a separating line (solve for w1*x + w2*y + b = 0)
# Using a simple approach: try to find weights
class_pos = points[np.array(labels) == 1]
class_neg = points[np.array(labels) == 0]
# Find separating line by optimization
found = False
if len(class_pos) == 0 or len(class_neg) == 0:
# Trivial case: all same class
if len(class_pos) == 0:
# All negative: any line with all points on negative side
w = np.array([0, -1])
b = -1.5
else:
w = np.array([0, 1])
b = -0.1 if len(class_pos) == 3 else 1.5
found = True
else:
# Try many random directions
best_w, best_b = None, None
for angle in np.linspace(0, 2*np.pi, 360):
w_try = np.array([np.cos(angle), np.sin(angle)])
proj_pos = [np.dot(w_try, p) for p in class_pos]
proj_neg = [np.dot(w_try, p) for p in class_neg]
if min(proj_pos) > max(proj_neg):
b_try = -(min(proj_pos) + max(proj_neg)) / 2
best_w = w_try
best_b = b_try
found = True
break
if found:
w = best_w
b = best_b
# Draw separating line if found
if found:
x_line = np.linspace(-0.5, 1.5, 100)
if abs(w[1]) > 1e-10:
y_line = -(w[0] * x_line + b) / w[1]
valid = (y_line >= -0.5) & (y_line <= 1.5)
ax.plot(x_line[valid], y_line[valid], 'g-', linewidth=2, alpha=0.7)
else:
ax.axvline(x=-b/w[0], color='g', linewidth=2, alpha=0.7)
label_str = ''.join(str(l) for l in labels)
ax.set_title(f'Labels: {label_str}', fontsize=11)
ax.set_xlim(-0.3, 1.3)
ax.set_ylim(-0.3, 1.2)
ax.set_aspect('equal')
ax.grid(True, alpha=0.2)
ax.set_xticks([])
ax.set_yticks([])
plt.suptitle('VC Dimension: 3 Points in $\\mathbb{R}^2$ --- All 8 Dichotomies are Realizable\n'
'Therefore VCdim(perceptron in $\\mathbb{R}^2$) $\\geq$ 3',
fontsize=14, y=1.02)
plt.tight_layout()
plt.show()
5a. VC Dimension Shatter Diagrams#
To develop deeper intuition for shattering, let us explicitly visualize the shatter diagram: for 3 points in \(\mathbb{R}^2\), we show all 8 dichotomies with their separating lines, and then show that for 4 points, at least one dichotomy (the XOR pattern) cannot be realized.
Show code cell source
import numpy as np
import matplotlib.pyplot as plt
fig, axes = plt.subplots(2, 5, figsize=(20, 8))
# ---- Top row: 3 points shattered by lines in 2D ----
pts3 = np.array([[0.2, 0.1], [0.8, 0.1], [0.5, 0.8]])
for idx in range(8):
ax = axes[0][idx] if idx < 5 else axes[1][idx - 5]
labels = [(idx >> i) & 1 for i in range(3)]
for i, (pt, lbl) in enumerate(zip(pts3, labels)):
color = 'red' if lbl == 1 else 'blue'
marker = 's' if lbl == 1 else 'o'
ax.scatter(pt[0], pt[1], c=color, s=250, marker=marker,
edgecolors='black', linewidths=2, zorder=5)
# Find separating line
class_pos = pts3[np.array(labels) == 1]
class_neg = pts3[np.array(labels) == 0]
found = False
if len(class_pos) == 0 or len(class_neg) == 0:
found = True
w = np.array([0, 1])
b = -1.5 if len(class_pos) == 0 else 0.05
else:
for angle in np.linspace(0, 2 * np.pi, 720):
w_try = np.array([np.cos(angle), np.sin(angle)])
proj_pos = [np.dot(w_try, p) for p in class_pos]
proj_neg = [np.dot(w_try, p) for p in class_neg]
if min(proj_pos) > max(proj_neg) + 1e-6:
b = -(min(proj_pos) + max(proj_neg)) / 2
w = w_try
found = True
break
if found:
x_line = np.linspace(-0.2, 1.2, 200)
if abs(w[1]) > 1e-10:
y_line = -(w[0] * x_line + b) / w[1]
valid = (y_line >= -0.2) & (y_line <= 1.2)
ax.plot(x_line[valid], y_line[valid], 'g-', linewidth=2.5, alpha=0.8)
else:
ax.axvline(x=-b / w[0], color='g', linewidth=2.5, alpha=0.8)
label_str = ''.join(str(l) for l in labels)
ax.set_title(f'{label_str}', fontsize=12, fontweight='bold',
color='green')
ax.set_xlim(-0.1, 1.1)
ax.set_ylim(-0.1, 1.0)
ax.set_aspect('equal')
ax.grid(True, alpha=0.2)
ax.set_xticks([])
ax.set_yticks([])
# ---- Bottom row remaining: 4 points, show XOR failure ----
# Fill remaining bottom-row axes
pts4 = np.array([[0.2, 0.2], [0.8, 0.2], [0.2, 0.8], [0.8, 0.8]])
# Show a separable dichotomy
ax_ok = axes[1][3]
labels_ok = [0, 1, 0, 1]
for i, (pt, lbl) in enumerate(zip(pts4, labels_ok)):
color = 'red' if lbl == 1 else 'blue'
marker = 's' if lbl == 1 else 'o'
ax_ok.scatter(pt[0], pt[1], c=color, s=250, marker=marker,
edgecolors='black', linewidths=2, zorder=5)
# Draw separating line
ax_ok.axvline(x=0.5, color='green', linewidth=2.5)
ax_ok.set_title('4pts: 0101\nSeparable', fontsize=11, color='green', fontweight='bold')
ax_ok.set_xlim(-0.1, 1.1)
ax_ok.set_ylim(-0.1, 1.0)
ax_ok.set_aspect('equal')
ax_ok.grid(True, alpha=0.2)
ax_ok.set_xticks([])
ax_ok.set_yticks([])
# Show the XOR failure
ax_fail = axes[1][4]
labels_fail = [0, 1, 1, 0] # XOR pattern
for i, (pt, lbl) in enumerate(zip(pts4, labels_fail)):
color = 'red' if lbl == 1 else 'blue'
marker = 's' if lbl == 1 else 'o'
ax_fail.scatter(pt[0], pt[1], c=color, s=250, marker=marker,
edgecolors='black', linewidths=2, zorder=5)
# Draw the intersecting convex hulls
ax_fail.plot([0.2, 0.8], [0.2, 0.8], 'b--', linewidth=2, alpha=0.5)
ax_fail.plot([0.8, 0.2], [0.2, 0.8], 'r--', linewidth=2, alpha=0.5)
ax_fail.plot(0.5, 0.5, 'kX', markersize=15, zorder=10)
ax_fail.set_title('4pts: 0110 (XOR)\nNOT Separable!', fontsize=11, color='red', fontweight='bold')
ax_fail.set_xlim(-0.1, 1.1)
ax_fail.set_ylim(-0.1, 1.0)
ax_fail.set_aspect('equal')
ax_fail.grid(True, alpha=0.2)
ax_fail.set_xticks([])
ax_fail.set_yticks([])
plt.suptitle('Shatter Diagrams: 3 points can be shattered (all 8 dichotomies work)\n'
'4 points CANNOT be shattered (XOR dichotomy fails) $\\Rightarrow$ VCdim = 3',
fontsize=14, y=1.04)
plt.tight_layout()
plt.show()
Show code cell source
# Show that 4 points in R^2 CANNOT all be shattered
# The XOR configuration is the failing dichotomy
fig, axes = plt.subplots(1, 2, figsize=(14, 6))
# 4 points in general position
pts4 = np.array([[0, 0], [1, 0], [0, 1], [0.5, 0.5]])
# Show a solvable dichotomy
ax1 = axes[0]
labels_ok = [0, 1, 0, 1]
for i, (pt, lbl) in enumerate(zip(pts4, labels_ok)):
color = 'red' if lbl == 1 else 'blue'
marker = 's' if lbl == 1 else 'o'
ax1.scatter(pt[0], pt[1], c=color, s=200, marker=marker,
edgecolors='black', linewidths=2, zorder=5)
ax1.set_title('4 points: This dichotomy IS realizable', fontsize=12, color='green')
# Draw a separating line
x_line = np.linspace(-0.3, 1.3, 100)
ax1.plot(x_line, -0.8*x_line + 0.35, 'g-', linewidth=2.5)
ax1.set_xlim(-0.3, 1.3)
ax1.set_ylim(-0.3, 1.3)
ax1.set_aspect('equal')
ax1.grid(True, alpha=0.3)
# Show the XOR-like failing dichotomy
ax2 = axes[1]
# Use the standard XOR pattern on a square
pts_xor = np.array([[0, 0], [1, 0], [0, 1], [1, 1]])
labels_fail = [0, 1, 1, 0] # XOR pattern
for i, (pt, lbl) in enumerate(zip(pts_xor, labels_fail)):
color = 'red' if lbl == 1 else 'blue'
marker = 's' if lbl == 1 else 'o'
ax2.scatter(pt[0], pt[1], c=color, s=200, marker=marker,
edgecolors='black', linewidths=2, zorder=5)
# Draw the intersecting convex hulls
ax2.plot([0, 1], [0, 1], 'b--', linewidth=2, alpha=0.5, label='conv(Class 0)')
ax2.plot([1, 0], [0, 1], 'r--', linewidth=2, alpha=0.5, label='conv(Class 1)')
ax2.plot(0.5, 0.5, 'k*', markersize=15, zorder=10)
ax2.set_title('4 points: This dichotomy is NOT realizable (XOR)\n'
'No line can separate blue circles from red squares',
fontsize=12, color='red')
ax2.set_xlim(-0.3, 1.3)
ax2.set_ylim(-0.3, 1.3)
ax2.set_aspect('equal')
ax2.grid(True, alpha=0.3)
ax2.legend(fontsize=11)
plt.suptitle('VCdim(perceptron in $\\mathbb{R}^2$) = 3, NOT 4\n'
'3 points can be shattered, but 4 points cannot', fontsize=14, y=1.02)
plt.tight_layout()
plt.show()
6. Higher-Dimensional Embeddings#
One of the most powerful ideas in machine learning is that data which is not linearly separable in its original space may become separable after mapping it to a higher-dimensional feature space.
XOR in \(\mathbb{R}^3\)#
Consider the feature map \(\varphi: \mathbb{R}^2 \to \mathbb{R}^3\) defined by:
This adds a new dimension: the product of the two inputs. Under this mapping:
\((x_1, x_2)\) |
\(\varphi(x_1, x_2) = (x_1, x_2, x_1 x_2)\) |
XOR |
|---|---|---|
\((0, 0)\) |
\((0, 0, 0)\) |
0 |
\((0, 1)\) |
\((0, 1, 0)\) |
1 |
\((1, 0)\) |
\((1, 0, 0)\) |
1 |
\((1, 1)\) |
\((1, 1, 1)\) |
0 |
Claim: These 4 points are linearly separable in \(\mathbb{R}^3\).
Verification: We need \(w_1 x_1 + w_2 x_2 + w_3 x_1 x_2 + b\) to be positive for XOR=1 and negative for XOR=0.
Try \(w_1 = 1, w_2 = 1, w_3 = -2, b = -0.5\):
\((0,0,0)\): \(0 + 0 + 0 - 0.5 = -0.5 < 0\) (correct: class 0)
\((0,1,0)\): \(0 + 1 + 0 - 0.5 = 0.5 > 0\) (correct: class 1)
\((1,0,0)\): \(1 + 0 + 0 - 0.5 = 0.5 > 0\) (correct: class 1)
\((1,1,1)\): \(1 + 1 - 2 - 0.5 = -0.5 < 0\) (correct: class 0)
Connection to Kernel Methods#
This idea — mapping data to a higher-dimensional space where it becomes linearly separable — is the foundation of kernel methods, including Support Vector Machines (SVMs). The “kernel trick” allows performing computations in the high-dimensional feature space implicitly, without ever computing the mapping \(\varphi\) explicitly.
Show code cell source
# 3D visualization: XOR becomes separable after lifting
fig = plt.figure(figsize=(14, 6))
# Left: original 2D space
ax1 = fig.add_subplot(121)
X = np.array([[0, 0], [0, 1], [1, 0], [1, 1]])
y = np.array([0, 1, 1, 0])
colors = ['blue' if yi == 0 else 'red' for yi in y]
markers = ['o' if yi == 0 else 's' for yi in y]
for i in range(4):
ax1.scatter(X[i, 0], X[i, 1], c=colors[i], s=250, marker=markers[i],
edgecolors='black', linewidths=2, zorder=5)
ax1.annotate(f'XOR={y[i]}', (X[i, 0], X[i, 1]),
xytext=(X[i, 0]+0.05, X[i, 1]+0.08), fontsize=11)
ax1.set_xlabel('$x_1$', fontsize=14)
ax1.set_ylabel('$x_2$', fontsize=14)
ax1.set_title('Original Space $\\mathbb{R}^2$: NOT separable', fontsize=13)
ax1.set_xlim(-0.3, 1.4)
ax1.set_ylim(-0.3, 1.4)
ax1.set_aspect('equal')
ax1.grid(True, alpha=0.3)
# Right: lifted 3D space
ax2 = fig.add_subplot(122, projection='3d')
# Lift to 3D: phi(x1, x2) = (x1, x2, x1*x2)
X_lifted = np.column_stack([X, X[:, 0] * X[:, 1]])
for i in range(4):
ax2.scatter(X_lifted[i, 0], X_lifted[i, 1], X_lifted[i, 2],
c=colors[i], s=200, marker=markers[i],
edgecolors='black', linewidths=2, zorder=5)
# Draw the separating plane: x1 + x2 - 2*x1*x2 = 0.5
# => z3 = (x1 + x2 - 0.5) / 2 (where z3 = x1*x2)
xx, yy = np.meshgrid(np.linspace(-0.2, 1.2, 20), np.linspace(-0.2, 1.2, 20))
zz = (xx + yy - 0.5) / 2
ax2.plot_surface(xx, yy, zz, alpha=0.2, color='green')
ax2.set_xlabel('$x_1$', fontsize=12)
ax2.set_ylabel('$x_2$', fontsize=12)
ax2.set_zlabel('$x_1 x_2$', fontsize=12)
ax2.set_title('Lifted Space $\\mathbb{R}^3$: SEPARABLE!', fontsize=13)
ax2.view_init(elev=25, azim=45)
plt.suptitle('Feature Map $\\varphi(x_1, x_2) = (x_1, x_2, x_1 x_2)$: '
'XOR Becomes Linearly Separable in 3D', fontsize=14, y=1.0)
plt.tight_layout()
plt.show()
# Verify the separation
w = np.array([1, 1, -2])
b = -0.5
print("Verification of linear separability in R^3:")
print(f"Separating plane: {w[0]}*x1 + {w[1]}*x2 + ({w[2]})*x1*x2 + ({b}) = 0")
print()
for i in range(4):
val = np.dot(w, X_lifted[i]) + b
pred = 1 if val > 0 else 0
print(f"phi({X[i]}) = {X_lifted[i]} => w.phi + b = {val:.1f} => class {pred} "
f"(true: {y[i]}) {'OK' if pred == y[i] else 'FAIL'}")
Verification of linear separability in R^3:
Separating plane: 1*x1 + 1*x2 + (-2)*x1*x2 + (-0.5) = 0
phi([0 0]) = [0 0 0] => w.phi + b = -0.5 => class 0 (true: 0) OK
phi([0 1]) = [0 1 0] => w.phi + b = 0.5 => class 1 (true: 1) OK
phi([1 0]) = [1 0 0] => w.phi + b = 0.5 => class 1 (true: 1) OK
phi([1 1]) = [1 1 1] => w.phi + b = -0.5 => class 0 (true: 0) OK
7. Margin and Support Vectors#
When data is linearly separable, there are infinitely many separating hyperplanes. Which one is “best”? This question leads to the concept of margin and eventually to Support Vector Machines (SVMs).
Geometric Margin#
Given a separating hyperplane \(H: \mathbf{w} \cdot \mathbf{x} + b = 0\) (with \(\|\mathbf{w}\| = 1\)), the geometric margin is the minimum distance from any data point to \(H\):
The distance from a point \(\mathbf{x}_i\) to the hyperplane is:
Support Vectors#
The support vectors are the data points closest to the separating hyperplane — those achieving the minimum distance \(\gamma\). These are the “hardest” points to classify and the ones that determine the position of the optimal boundary.
Maximum Margin Classifier#
The maximum margin hyperplane is the one that maximizes \(\gamma\). This is the optimal linear classifier in a precise sense: it provides the greatest “safety buffer” between the two classes.
The optimization problem is:
This is equivalent to minimizing \(\|\mathbf{w}\|^2\) subject to the constraints — a quadratic program that can be solved efficiently. This is the foundation of the Support Vector Machine (SVM), developed by Vapnik and Cortes in the 1990s.
Show code cell source
# Visualization: margin and support vectors
np.random.seed(12)
# Generate linearly separable data
A = np.random.randn(15, 2) * 0.6 + np.array([-1.5, 0])
B = np.random.randn(15, 2) * 0.6 + np.array([1.5, 0])
fig, axes = plt.subplots(1, 2, figsize=(14, 6))
# Left: many valid separating hyperplanes
ax1 = axes[0]
ax1.scatter(A[:, 0], A[:, 1], c='blue', s=80, edgecolors='black', linewidths=1, marker='o')
ax1.scatter(B[:, 0], B[:, 1], c='red', s=80, edgecolors='black', linewidths=1, marker='s')
# Draw several valid separating lines
x_plot = np.linspace(-3.5, 3.5, 100)
for slope, intercept, style in [(0, 0, '-'), (0.5, 0.2, '--'), (-0.3, -0.1, '-.'), (0.8, 0.3, ':')]:
ax1.plot(x_plot, slope * x_plot + intercept, 'gray', linestyle=style, linewidth=1.5, alpha=0.6)
ax1.set_title('Many valid separating lines', fontsize=13)
ax1.set_xlim(-3.5, 3.5)
ax1.set_ylim(-3, 3)
ax1.set_xlabel('$x_1$', fontsize=12)
ax1.set_ylabel('$x_2$', fontsize=12)
ax1.grid(True, alpha=0.3)
# Right: maximum margin hyperplane
ax2 = axes[1]
ax2.scatter(A[:, 0], A[:, 1], c='blue', s=80, edgecolors='black', linewidths=1, marker='o')
ax2.scatter(B[:, 0], B[:, 1], c='red', s=80, edgecolors='black', linewidths=1, marker='s')
# Find approximate maximum margin (simple approach: midpoint of closest pair)
min_dist = np.inf
sv_a, sv_b = None, None
for a in A:
for b in B:
d = np.linalg.norm(a - b)
if d < min_dist:
min_dist = d
sv_a, sv_b = a, b
# The optimal separating line is perpendicular to sv_b - sv_a at the midpoint
midpoint = (sv_a + sv_b) / 2
w_dir = sv_b - sv_a
w_dir = w_dir / np.linalg.norm(w_dir)
# Line perpendicular to w_dir through midpoint
perp = np.array([-w_dir[1], w_dir[0]])
t_vals = np.linspace(-3, 3, 100)
line_pts = midpoint + np.outer(t_vals, perp)
ax2.plot(line_pts[:, 0], line_pts[:, 1], 'g-', linewidth=3, label='Max-margin boundary')
# Draw margin lines
margin = min_dist / 2
for sign, style in [(1, '--'), (-1, '--')]:
margin_pts = midpoint + sign * margin * w_dir + np.outer(t_vals, perp)
ax2.plot(margin_pts[:, 0], margin_pts[:, 1], 'g', linestyle=style, linewidth=1.5, alpha=0.5)
# Highlight support vectors
ax2.scatter([sv_a[0]], [sv_a[1]], c='blue', s=250, edgecolors='green', linewidths=3,
marker='o', zorder=6, label='Support vectors')
ax2.scatter([sv_b[0]], [sv_b[1]], c='red', s=250, edgecolors='green', linewidths=3,
marker='s', zorder=6)
# Draw margin width
ax2.annotate('', xy=sv_b, xytext=sv_a,
arrowprops=dict(arrowstyle='<->', color='purple', linewidth=2))
ax2.text(midpoint[0] + 0.1, midpoint[1] + 0.3, f'margin = {min_dist:.2f}',
fontsize=12, color='purple', fontweight='bold')
ax2.set_title('Maximum margin hyperplane', fontsize=13)
ax2.set_xlim(-3.5, 3.5)
ax2.set_ylim(-3, 3)
ax2.set_xlabel('$x_1$', fontsize=12)
ax2.set_ylabel('$x_2$', fontsize=12)
ax2.legend(fontsize=10, loc='upper left')
ax2.grid(True, alpha=0.3)
plt.suptitle('From Separability to Optimal Separability: The Margin Idea', fontsize=14, y=1.01)
plt.tight_layout()
plt.show()
8. Exercises#
Exercise 10.1: Separability by Convex Hull#
For each of the 5 random 2D datasets below, determine whether the two classes are linearly separable by computing and visualizing the convex hulls. Use the convex_hull_2d and check_hull_intersection functions defined earlier.
Show code cell source
# Exercise 10.1: Generate 5 random datasets and check separability
np.random.seed(2024)
exercise_datasets = []
for i in range(5):
# Randomly generate two clusters
center_A = np.random.randn(2) * 2
center_B = np.random.randn(2) * 2
spread = np.random.uniform(0.3, 1.5)
n_points = np.random.randint(5, 12)
A = np.random.randn(n_points, 2) * spread + center_A
B = np.random.randn(n_points, 2) * spread + center_B
exercise_datasets.append((f'Dataset {i+1}', A, B))
print("Exercise 10.1: For each dataset, determine separability.")
print("Use convex_hull_2d() and check_hull_intersection().")
print()
for name, A, B in exercise_datasets:
hull_A = convex_hull_2d(A)
hull_B = convex_hull_2d(B)
intersects = check_hull_intersection(hull_A, hull_B)
status = "NOT separable" if intersects else "SEPARABLE"
print(f"{name}: {len(A)} vs {len(B)} points => {status}")
Exercise 10.1: For each dataset, determine separability.
Use convex_hull_2d() and check_hull_intersection().
Dataset 1: 7 vs 7 points => SEPARABLE
Dataset 2: 8 vs 8 points => SEPARABLE
Dataset 3: 9 vs 9 points => SEPARABLE
Dataset 4: 8 vs 8 points => NOT separable
Dataset 5: 9 vs 9 points => SEPARABLE
Exercise 10.2: VC Dimension of Circles#
Consider the hypothesis class of circles in \(\mathbb{R}^2\): a point is classified as positive if it lies inside the circle, and negative if outside.
Task: Show that the VC dimension of this class is 3.
Show that 3 points can be shattered.
Show that no set of 4 points can be shattered.
Hint for (1): Place 3 points on a circle. Show all 8 labelings can be achieved.
Hint for (2): Consider 4 points. If one is inside the convex hull of the other three, use that to find a labeling that fails.
Exercise 10.3: Feature Map for Concentric Circles#
Consider a dataset where class 0 points form a ring at distance \(\approx 2\) from the origin, and class 1 points form a cluster near the origin.
Find a feature map \(\varphi: \mathbb{R}^2 \to \mathbb{R}^k\) (for some \(k\)) that makes this dataset linearly separable.
Hint: What quantity naturally separates points near the origin from points far from it?
Show code cell source
# Exercise 10.3: Concentric circles dataset
np.random.seed(42)
# Generate concentric circles data
n_inner = 50
n_outer = 80
# Inner circle (class 1)
theta_inner = np.random.uniform(0, 2*np.pi, n_inner)
r_inner = np.random.uniform(0, 0.8, n_inner)
X_inner = np.column_stack([r_inner * np.cos(theta_inner), r_inner * np.sin(theta_inner)])
# Outer ring (class 0)
theta_outer = np.random.uniform(0, 2*np.pi, n_outer)
r_outer = np.random.uniform(1.5, 2.5, n_outer)
X_outer = np.column_stack([r_outer * np.cos(theta_outer), r_outer * np.sin(theta_outer)])
fig, axes = plt.subplots(1, 2, figsize=(14, 6))
# Original space
ax1 = axes[0]
ax1.scatter(X_inner[:, 0], X_inner[:, 1], c='red', s=30, label='Class 1 (inner)', alpha=0.7)
ax1.scatter(X_outer[:, 0], X_outer[:, 1], c='blue', s=30, label='Class 0 (outer)', alpha=0.7)
ax1.set_title('Original Space: NOT linearly separable', fontsize=13)
ax1.set_xlabel('$x_1$', fontsize=12)
ax1.set_ylabel('$x_2$', fontsize=12)
ax1.legend(fontsize=10)
ax1.set_aspect('equal')
ax1.grid(True, alpha=0.3)
# Feature space: phi(x1, x2) = x1^2 + x2^2 (just the radius squared)
r2_inner = X_inner[:, 0]**2 + X_inner[:, 1]**2
r2_outer = X_outer[:, 0]**2 + X_outer[:, 1]**2
ax2 = axes[1]
ax2.scatter(r2_inner, np.zeros_like(r2_inner) + np.random.randn(n_inner)*0.05,
c='red', s=30, label='Class 1 (inner)', alpha=0.7)
ax2.scatter(r2_outer, np.zeros_like(r2_outer) + np.random.randn(n_outer)*0.05,
c='blue', s=30, label='Class 0 (outer)', alpha=0.7)
ax2.axvline(x=1.0, color='green', linewidth=3, linestyle='--',
label='Threshold at $r^2 = 1.0$')
ax2.set_title('Feature Space $\\varphi(x_1, x_2) = x_1^2 + x_2^2$: SEPARABLE!', fontsize=13)
ax2.set_xlabel('$r^2 = x_1^2 + x_2^2$', fontsize=12)
ax2.set_ylabel('(jittered for visibility)', fontsize=10)
ax2.legend(fontsize=10)
ax2.grid(True, alpha=0.3)
plt.suptitle('Exercise 10.3: The radius-squared feature makes concentric circles separable',
fontsize=14, y=1.01)
plt.tight_layout()
plt.show()
print("The feature map phi(x1, x2) = x1^2 + x2^2 maps each point to its squared distance from the origin.")
print("In this 1D feature space, a simple threshold separates the two classes.")
print(f"\nInner class r^2 range: [{r2_inner.min():.3f}, {r2_inner.max():.3f}]")
print(f"Outer class r^2 range: [{r2_outer.min():.3f}, {r2_outer.max():.3f}]")
The feature map phi(x1, x2) = x1^2 + x2^2 maps each point to its squared distance from the origin.
In this 1D feature space, a simple threshold separates the two classes.
Inner class r^2 range: [0.000, 0.623]
Outer class r^2 range: [2.265, 6.116]