Lecture 4: Homology (continuation)

• Checkers, plotting and example data are in lecture4_helpers.py.

• Section 1 gives you last session’s chain addition, already solved. Sections 2–4 pick up last session’s exercises (copy your code over if you finished them). The remaining sections are new.

from typing import Callable
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import gudhi

# Everything below comes from lecture4_helpers.py, next to this notebook.
from lecture4_helpers import (
    Simplex, Chain,                    # type names: a Simplex is a sorted tuple, a Chain is (simplices, coeffs)
    chain_dim, fmt, trace,             # Sec. 1: dimension of a chain, pretty-printing, show a function's outputs
    K, K_COORDS,                       # Sec. 2: the running example complex K, and where to draw its vertices
    draw, draw_chain,                  # Sec. 2: plot a complex, highlight a chain on it
    check_boundary_simplex, check_boundary_chain, SLIDE_EXAMPLES,
    K3, TORUS,                         # Sec. 2: more complexes, to compare with GUDHI
    simplices_of_dim,                  # Sec. 3: the p-simplices of a complex
    check_boundary_matrix,
    check_is_cycle,                    # Sec. 4
    check_equivalence_classes,         # Sec. 5: tests for your equivalence_classes
    check_equivalence_axioms,          # Sec. 5: does a relation satisfy the three axioms?
    rank_mod2, EMPTY_TRIANGLE,         # Sec. 6: rank over Z_2, and a complex showing why we need it
    check_betti,
    ZOO, plot_shapes, plot_double_torus,  # Sec. 7: five shapes to predict, and plots of them
    cech, SHAPES, LETTERS, plot_clouds,  # Sec. 8: Cech complex, point clouds, and a grid plot of clouds
    check_classify, check_group_letters,
)
plt.rcParams["figure.dpi"] = 110

1. Chains (recap, solved)

A \(p\)-chain is a formal sum of \(p\)-simplices, \(\alpha = \sum_i a_i \sigma_i\) (slide 2). We store it as a Chain, a pair of lists (simplices, coeffs):

• each simplex is a tuple of sorted vertex numbers, e.g. (0, 1) for the edge \([0,1]\).

chain	in Python
\(2[0,1] - [1,2]\)	([(0, 1), (1, 2)], [2, -1])
\([2]\)	([(2,)], [1])
\(0\)	([], [])

Helpers:

• chain_dim(chain: Chain) -> int | None: the \(p\) of a \(p\)-chain, None for the zero chain. It raises a ValueError if the chain is invalid (lists of different lengths, unsorted simplex, or mixed dimensions).

• fmt(chain: Chain) -> str: the chain as readable text, e.g. '2[0,1] - [1,2]'.

• trace(fn, calls) -> None: prints what fn returns or raises for each tuple of arguments in the list calls.

print(fmt(([(0, 1), (1, 2)], [2, -1])))
trace(chain_dim, [(([(0, 1), (1, 2)], [2, -1]),), (([], []),), (([(0, 1), (0, 1, 2)], [1, 1]),)])

Exercise 1.1 (solved): chain_add(a, b)

Chains are added coefficient by coefficient (L3 slide 7): \(\sum a_i\sigma_i + \sum b_i\sigma_i = \sum (a_i + b_i)\sigma_i\).

• Input: two chains a, b of the same dimension. Either one can be the zero chain.

• Output: their sum, simplified: each simplex once, no zero coefficients, simplices sorted. Raise a ValueError for invalid chains or mixed dimensions.

• Example: chain_add(([(0, 1)], [1]), ([(0, 1), (1, 2)], [2, 1])) returns ([(0, 1), (1, 2)], [3, 1]).

How the solution works. A dictionary keeps, for each simplex, its total coefficient so far. We go through the terms of a and then the terms of b, adding each coefficient to the total of its simplex. A simplex whose total ends at \(0\) cancelled out, so we drop it, and we sort the simplices that are left.

def chain_add(a: Chain, b: Chain) -> Chain:
    # 1. check the input. chain_dim raises a ValueError on an invalid chain, and returns
    #    None for the zero chain, which can be added to a chain of any dimension.
    pa = chain_dim(a)
    pb = chain_dim(b)
    if pa is not None and pb is not None and pa != pb:
        raise ValueError(f"cannot add a {pa}-chain and a {pb}-chain")

    # 2. add coefficient by coefficient: first every term of a, then every term of b.
    total = {}                                    # simplex -> its coefficient so far
    for chain in [a, b]:
        simplices, coeffs = chain
        for i in range(len(simplices)):
            s = simplices[i]
            if s not in total:                    # the first time we see s, it starts at 0
                total[s] = 0
            total[s] = total[s] + coeffs[i]

    # 3. simplify: drop the simplices that cancelled out (total 0), and sort the rest.
    result_simplices = []
    result_coeffs = []
    for s in sorted(total.keys()):
        if total[s] != 0:
            result_simplices.append(s)
            result_coeffs.append(total[s])
    return result_simplices, result_coeffs

Try it yourself: change a and b below, and add the zero chain ([], []) to something.

a = ([(0, 1), (1, 2)], [1, 1])            # [0,1] + [1,2]
b = ([(1, 2), (2, 3)], [1, 1])            # [1,2] + [2,3]
print("a + b  =", fmt(chain_add(a, b)))
print("a + 0  =", fmt(chain_add(a, ([], []))))
print("a + -a =", fmt(chain_add(a, ([(0, 1), (1, 2)], [-1, -1]))))   # -a flips every sign

Exercise 1.2 (solved): chain_add_mod2(a, b)

The same, with coefficients in \(\mathbb{Z}_2\), where \(1 + 1 = 0\). As in the slides, we use \(\mathbb{Z}_2\) from now on.

• Input / output: as in chain_add, but every coefficient in the output is \(1\).

• Example: chain_add_mod2(([(0, 1), (1, 2)], [1, 1]), ([(1, 2)], [1])) returns ([(0, 1)], [1]), because the two copies of \([1,2]\) cancel.

How the solution works. First add over \(\mathbb{Z}\) with chain_add, which also checks the input. Then reduce mod 2: an odd coefficient becomes \(1\) and an even one becomes \(0\). So we keep the simplices with an odd coefficient, each with coefficient \(1\).

def chain_add_mod2(a: Chain, b: Chain) -> Chain:
    simplices, coeffs = chain_add(a, b)           # add over Z
    result_simplices = []
    result_coeffs = []
    for i in range(len(simplices)):
        if coeffs[i] % 2 == 1:                    # odd -> 1, even -> 0 (also for c < 0: -1 % 2 == 1)
            result_simplices.append(simplices[i])
            result_coeffs.append(1)
    return result_simplices, result_coeffs

How to use it. The same a and b, now over \(\mathbb{Z}_2\). The results differ: \([1,2]\) appears twice, so it cancels. A simplex survives when it appears an odd number of times. In particular \(a + a = 0\) for every chain: over \(\mathbb{Z}_2\) every chain is its own inverse (slide 3), so \(-a = a\) and subtracting is the same as adding.

print("over Z  : a + b =", fmt(chain_add(a, b)), "    a + a =", fmt(chain_add(a, a)))
print("over Z_2: a + b =", fmt(chain_add_mod2(a, b)), "            a + a =", fmt(chain_add_mod2(a, a)))

2. Boundary maps

Over \(\mathbb{Z}_2\) the boundary of a simplex is the sum of the faces obtained by dropping one vertex (slide 4):

\[\partial_p [v_0, \dots, v_p] = \sum_{j=0}^{p} [v_0, \dots, \hat{v}_j, \dots, v_p], \qquad \text{e.g.}\quad \partial_2 [1,2,4] = [2,4] + [1,4] + [1,2].\]

Our running example is the complex \(K\) from Dr. Munch’s notebook, drawn below.

Helpers:

• K: this complex, as a GUDHI SimplexTree with vertices \(0, \ldots, 4\).

• K_COORDS: a \(5 \times 2\) array, where row \(i\) holds the position of vertex \(i\) (only used for drawing).

• draw(points, complex, ax=None, labels=None, title=None) -> Axes: draws a SimplexTree, placing vertex \(i\) at points[i]. labels=True writes the vertex numbers.

print([tuple(s) for s, _ in K.get_simplices()])
draw(K_COORDS, K, labels=True, title="K")
plt.show()

Exercise 2.1: boundary_simplex(simplex, p)

This is the definition above, applied to a single simplex.

• Input: a \(p\)-simplex as a sorted tuple, and \(p\).

• Output: its boundary, as a chain. Raise a ValueError if simplex does not have \(p + 1\) vertices. \(\partial_0\) of a vertex is the zero chain.

• Example: boundary_simplex((1, 2, 4), 2) returns ([(1, 2), (1, 4), (2, 4)], [1, 1, 1]).

def boundary_simplex(simplex: Simplex, p: int) -> Chain:
    # tip: sort the faces, so that the output looks like chain_add's.
    raise NotImplementedError

Solution hidden in this cell

check_boundary_simplex(boundary_simplex)

In GUDHI, SimplexTree.get_boundaries(simplex) lists the faces of a simplex, each with its filtration value, which we ignore. Let’s compare it with your function on every simplex of K, K3 (a hollow tetrahedron with two extra edges) and TORUS (a 7-vertex torus), all SimplexTrees:

def gudhi_boundary(st: gudhi.SimplexTree, simplex: Simplex) -> Chain:
    faces = sorted(tuple(f) for f, _ in st.get_boundaries(list(simplex)))
    return faces, [1] * len(faces)


print("GUDHI: d[1,2,4] =", fmt(gudhi_boundary(K, (1, 2, 4))))
for label, st in [("K", K), ("K3", K3), ("TORUS", TORUS)]:
    simplices = [tuple(s) for s, _ in st.get_simplices()]
    agree = sum(boundary_simplex(s, len(s) - 1) == gudhi_boundary(st, s) for s in simplices)
    print(f"{'ok  ' if agree == len(simplices) else 'FAIL'} {label}: {agree}/{len(simplices)} simplices agree")

Exercise 2.2: boundary_chain(chain)

Use linearity (L3 slide 11): \(\partial\big(\sum_i a_i\sigma_i\big) = \sum_i a_i\,\partial\sigma_i\).

• Input: a chain over \(\mathbb{Z}_2\).

• Output: its boundary, as a chain.

• Example: \(\partial([0,4] + [1,4]) = [0] + [4] + [1] + [4] = [0] + [1]\), so boundary_chain(([(0, 4), (1, 4)], [1, 1])) returns ([(0,), (1,)], [1, 1]).

def boundary_chain(chain: Chain) -> Chain:
    # tip: p = chain_dim(chain); if it is None (the zero chain) the boundary is ([], []).
    # tip: start from result = ([], []) and, for each simplex in chain[0], add its boundary to result using chain_add_mod2.
    raise NotImplementedError

Solution hidden in this cell

check_boundary_chain(boundary_chain)   # the examples of L3 slide 12, on K

The same examples as pictures, with each chain on top and its boundary below.

Helpers:

• SLIDE_EXAMPLES: a list of (description, chain, its boundary) triples.

• draw_chain(points, chain: Chain, ax) -> None: highlights the simplices of chain in red on a plot made by draw.

fig, axes = plt.subplots(2, 4, figsize=(13, 6.4))
for k, (desc, chain, _) in enumerate(SLIDE_EXAMPLES):
    for row, c in enumerate([chain, boundary_chain(chain)]):
        draw(K_COORDS, K, ax=axes[row, k], labels=True)
        draw_chain(K_COORDS, c, axes[row, k])
        axes[row, k].set_title(("chain: " if row == 0 else "boundary: ") + fmt(c), fontsize=9)
plt.tight_layout(); plt.show()

L3 slide 20: \(\partial\partial = 0\). By hand: \(\partial_1\partial_2[1,2,4] = \partial_1([1,2] + [1,4] + [2,4]) = [1] + [2] + [1] + [4] + [2] + [4] = 0\). Your code agrees:

d = boundary_chain(([(1, 2, 4)], [1]))
print("d [1,2,4]   =", fmt(d))
print("d d [1,2,4] =", fmt(boundary_chain(d)))

3. Boundary matrices

\(\partial_p\) is linear, so it has a matrix (L3 slide 13):

• one column per \(p\)-simplex;

• one row per \((p-1)\)-simplex;

• a \(1\) where the row simplex is a face of the column simplex.

We can build these matrices for the complex \(K\) that we showed above, by hand:

vertex_list = ['0', '1', '2', '3', '4']
edge_list = ['04', '03', '12', '14', '23', '24']
triangle_list = ['124']

B1_df = pd.DataFrame(0, index=vertex_list, columns=edge_list)
for edge in B1_df.columns:          # the two vertices of each edge
    B1_df.loc[edge[0], edge] = 1
    B1_df.loc[edge[1], edge] = 1

B2_df = pd.DataFrame(0, index=edge_list, columns=triangle_list)
B2_df.loc['12', '124'] = 1          # the three edges of the triangle, typed by hand
B2_df.loc['14', '124'] = 1
B2_df.loc['24', '124'] = 1

display(B1_df, B2_df)

Exercise 3.1: boundary_matrix(st, p)

Build the same matrices automatically: column \(j\) is boundary_simplex of the \(j\)-th \(p\)-simplex.

• Input: a SimplexTree and \(p\).

• Output: (D, rows, cols), where D is a 0/1 numpy array, rows is the list of \((p-1)\)-simplices and cols is the list of \(p\)-simplices.

• Edge cases: for \(p = 0\), D has 0 rows; above the top dimension, it has 0 columns.

• Helper: simplices_of_dim(st, p: int) -> list[Simplex] gives the sorted \(p\)-simplices, e.g. simplices_of_dim(K, 2) returns [(1, 2, 4)].

• Example: boundary_matrix(K, 2) returns (array([[0], [0], [1], [1], [0], [1]]), [(0, 3), (0, 4), (1, 2), (1, 4), (2, 3), (2, 4)], [(1, 2, 4)]).

def boundary_matrix(st: gudhi.SimplexTree, p: int) -> tuple[np.ndarray, list[Simplex], list[Simplex]]:
    # tip: cols = simplices_of_dim(st, p) and rows = simplices_of_dim(st, p - 1)  (use [] if p == 0).
    # tip: a dictionary row_index, with row_index[rows[i]] = i for every i, tells you the row of each face.
    # tip: You can use np.zeros((len(rows), len(cols)), dtype=int) creating a matrix of the correct size with all zeros.
    # You don't have to use a pandas DataFrame like in the example above.
    raise NotImplementedError

Solution hidden in this cell

check_boundary_matrix(boundary_matrix)   # compares with B1_df and B2_df; row/column order doesn't matter

4. Cycles and boundaries

• cycles: \(Z_p = \ker \partial_p\), the chains with \(\partial_p\alpha = 0\) (slide 5);

• boundaries: \(B_p = \operatorname{im} \partial_{p+1}\) (slide 6);

• since \(\partial\partial = 0\), every boundary is a cycle.

Exercise 4.1: is_cycle(chain)

This is the definition of a cycle.

• Input: a chain over \(\mathbb{Z}_2\).

• Output: True if its boundary is zero.

• Example: the square \([0,3] + [0,4] + [2,3] + [2,4]\) is a cycle; \([0,4] + [1,4]\) is not.

def is_cycle(chain: Chain) -> bool:
    # tip: one line: the boundary (boundary_chain) has no simplices.
    raise NotImplementedError

Solution hidden in this cell

check_is_cycle(is_cycle)

Every boundary is a cycle, but not every cycle is a boundary.

• \(\partial[1,2,4]\) is a boundary, and it is a cycle, since \(\partial\partial = 0\).

• The square is a cycle too, but it is not a boundary. \(K\) has a single triangle, so its only boundaries are \(0\) and \(\partial[1,2,4]\). The square goes around a hole that no triangle fills.

triangle_edges = boundary_chain(([(1, 2, 4)], [1]))
square = ([(0, 3), (0, 4), (2, 3), (2, 4)], [1, 1, 1, 1])
boundaries = [([], []), triangle_edges]        # the boundaries of the 2-chains 0 and [1,2,4]

fig, axes = plt.subplots(1, 2, figsize=(7, 3.6))
for ax, (label, z) in zip(axes, [("d[1,2,4]", triangle_edges), ("square", square)]):
    draw(K_COORDS, K, ax=ax, labels=True)
    draw_chain(K_COORDS, z, ax)
    ax.set_title(f"{label}\ncycle: {is_cycle(z)},  boundary: {z in boundaries}", fontsize=9)
plt.tight_layout(); plt.show()

5. Equivalence relations

The square and the square plus \(\partial[1,2,4]\) go around the same hole, so homology treats them as the same cycle: they differ by a boundary. Equivalence relations make “the same” precise (slide 10).

An equivalence relation \(\sim\) on a set \(S\) satisfies:

1. reflexivity: \(x \sim x\);

2. symmetry: if \(x \sim y\), then \(y \sim x\);

3. transitivity: if \(x \sim y\) and \(y \sim z\), then \(x \sim z\).

The equivalence class of \(x\) is everything related to it, \([x] = \{y \in S \mid y \sim x\}\). Two classes are either equal or disjoint, so the classes split \(S\) into pieces that don’t overlap: every element is in exactly one class.

Example (slide 10): on \(\mathbb{Z}\), \(m \sim n\) when \(m - n\) is even. There are two classes: \([0]\), the even numbers, and \([1]\), the odd numbers. Any element of a class can name it: \([0] = [2] = [-4]\).

In Python, a relation is a function that takes two elements and returns True or False:

def same_parity(m: int, n: int) -> bool:
    return (m % 2) == (n % 2)


trace(same_parity, [(0, 4), (3, 7), (2, 5)])

Exercise 5.1: equivalence_classes(S, are_related)

• Input: S, a finite set; are_related, a function taking two elements of S and returning True or False. You can assume it is an equivalence relation.

• Output: a Python list of sets, one per equivalence class, so every element of S is in exactly one of them. The order of the list doesn’t matter. Don’t modify S.

• Example: equivalence_classes({0, 1, 2, 3, 4, 5}, same_parity) returns [{0, 2, 4}, {1, 3, 5}] (or [{1, 3, 5}, {0, 2, 4}]).

def equivalence_classes(S: set, are_related: Callable) -> list[set]:
    # tip: every x in S is in exactly one class. Loop over S, and only build a class
    #      for an x that is not in any of the classes you already have.
    raise NotImplementedError

Solution hidden in this cell

check_equivalence_classes(equivalence_classes)

Example: words that end with the same letter. Take \(x \sim y\) when the words \(x\) and \(y\) have the same last letter. It is an equivalence relation, and each class collects the words that end in one letter.

Helper:

• check_equivalence_axioms(S, are_related) -> None: tests reflexivity, symmetry and transitivity on every element, pair and triple of S, and prints ok, or FAIL with a counterexample, for each axiom.

# Your turn: replace words and same_last_letter by your own set and relation. 
# Some ideas: words with the same number of letters, words that are anagrams of each other, words with the same number of vowels.
# Remember: the relation must be reflexive, symmetric and transitive. check_equivalence_axioms tells you if it is.
words = {"apple", "grape", "banana", "papaya", "kiwi", "pear", "fig", "mango", "lemon", "melon"}


def same_last_letter(x: str, y: str) -> bool:
    return x[-1] == y[-1]


check_equivalence_axioms(words, same_last_letter)
for c in equivalence_classes(words, same_last_letter):
    print(sorted(c))

6. Betti numbers

\(\beta_p = \dim H_p = \dim Z_p - \dim B_p\) (slide 17). Both dimensions come from ranks of boundary matrices:

• \(\dim Z_p = c_p - \operatorname{rank}\partial_p\), by rank–nullity, where \(c_p\) is the number of \(p\)-simplices;

• \(\dim B_p = \operatorname{rank}\partial_{p+1}\).

So

\[\beta_p = c_p - \operatorname{rank}\partial_p - \operatorname{rank}\partial_{p+1}.\]

Careful: np.linalg.matrix_rank computes the rank over \(\mathbb{R}\). Use the helper instead:

• rank_mod2(M: np.ndarray) -> int: the rank of a 0/1 matrix over \(\mathbb{Z}_2\).

Here is the difference on EMPTY_TRIANGLE, the SimplexTree of a triangle’s three edges without its inside:

D = boundary_matrix(EMPTY_TRIANGLE, 1)[0]   # every column has two 1s, and 1 + 1 = 0 in Z_2
print(D)
print("over R  :", np.linalg.matrix_rank(D), "  <- wrong for us")
print("over Z_2:", rank_mod2(D))

Exercise 6.1: the table for \(K\)

Fill it in with simplices_of_dim, boundary_matrix and rank_mod2:

	\(c_p\)	\(\operatorname{rank}\partial_p\)	\(\operatorname{rank}\partial_{p+1}\)	\(\beta_p\)
\(p=0\)
\(p=1\)
\(p=2\)

Solution hidden in this cell

Exercise 6.2: betti_numbers(st)

• Input: a SimplexTree.

• Output: the list \([\beta_0, \dots, \beta_d]\), where \(d\) = st.dimension().

• Example: betti_numbers(K) returns [1, 1, 0].

In GUDHI, compute_persistence(homology_coeff_field=2, persistence_dim_max=True) followed by betti_numbers() gives the same answer. The first option picks \(\mathbb{Z}_2\); the second makes GUDHI include the top dimension.

def betti_numbers(st: gudhi.SimplexTree) -> list[int]:
    # tip: your Exercise 6.1 cell, as a loop over p = 0, ..., st.dimension().
    raise NotImplementedError

Solution hidden in this cell

def gudhi_betti(st: gudhi.SimplexTree) -> list[int]:
    st.compute_persistence(homology_coeff_field=2, persistence_dim_max=True)
    return st.betti_numbers()


print("K:", betti_numbers(K), "GUDHI:", gudhi_betti(K))
check_betti(betti_numbers)

7. Putting it all together

Exercise 7.1: predict, then compute

ZOO is a dict from a name, "shape 1" to "shape 5", to a SimplexTree. Here they are. Blue triangles are filled: they are 2-simplices of the complex. Triangles in white are empty: only their three edges are in the complex.

plot_shapes()

Predict the Betti numbers \([\beta_0, \beta_1, \beta_2]\) of the five shapes in MY_PREDICTIONS, from the pictures alone. The cell after it plots the shapes again, with GUDHI’s answer, your betti_numbers and your prediction. For a shape without triangles, \(\beta_2 = 0\).

# tip (slide 17):
# beta_0 = number of connected components
# beta_1 = number of independent loops
# beta_2 = number of voids/bubbles (2D holes)
MY_PREDICTIONS = {
    "shape 1": [0, 0, 0],
    "shape 2": [0, 0, 0],
    "shape 3": [0, 0, 0],
    "shape 4": [0, 0, 0],
    "shape 5": [0, 0, 0],  
}

Solution hidden in this cell

The same shapes again, with the answers. A title turns red when the prediction doesn’t match GUDHI.

def padded(betti: list[int]) -> list[int]:
    # a shape without triangles has no beta_2 in the output of betti_numbers: it is 0
    betti = list(betti)
    while len(betti) < 3:
        betti.append(0)
    return betti


info = {}
colors = {}
for name, st in ZOO.items():
    gudhi_answer = padded(gudhi_betti(st))
    your_code = padded(betti_numbers(st))
    info[name] = f"GUDHI: {gudhi_answer}\nyour code: {your_code}\nyour prediction: {MY_PREDICTIONS[name]}"
    colors[name] = "black" if MY_PREDICTIONS[name] == gudhi_answer else "crimson"   # red: the prediction was off
plot_shapes(info, colors)

8. Optional: telling letters apart with homology

A classic exercise (that was already introduced in the lectures): sort the capital letters by their Betti numbers. For example, \(A\) has one hole, \(B\) has two, \(C\) has none.

We do it on point clouds: build the Čech complex at a radius \(r\), then compute its Betti numbers with your code.

Helpers:

• cech(points: np.ndarray, r: float) -> SimplexTree: the Čech complex, up to triangles, of an \(n \times 2\) array of points. It is the one from Lecture 2, sped up.

• plot_clouds(clouds: dict, fn=None) -> None: a grid with one panel per cloud. By default each panel is a scatter plot; fn(ax, key, points) draws something else.

8.1 Warm-up: circles and disks

SHAPES is a dict from a name to (points, expected (b0, b1)). The clouds are noiseless, with neighbouring points \(0.1\) apart.

plot_clouds({k: X for k, (X, _) in SHAPES.items()})

Exercise 8.1: classify(points, r)

• Input: an \(n \times 2\) array of points and a radius \(r\).

• Output: \((\beta_0, \beta_1)\) of the Čech complex at radius \(r\).

• Example: for a circle (and a good \(r\)) it returns (1, 1).

Then choose an r_shapes that gets all five shapes right.

def classify(points: np.ndarray, r: float) -> tuple[int, int]:
    # tip: if r is too small, there are only vertices and no edges, so betti_numbers will only return beta_0.
    #      You are still expected to return (beta_0, beta_1).
    raise NotImplementedError


r_shapes = None   # try different radii: what happens if you pick something around 0.2 or larger? (tip: something below that works)

Solution hidden in this cell

check_classify(classify, r_shapes)
plot_clouds({k: X for k, (X, _) in SHAPES.items()},
            fn=lambda ax, k, X: draw(X, cech(X, r_shapes), ax=ax, ms=4, lw=0.6,
                                     title=f"{k}\n(b0, b1) = {classify(X, r_shapes)}"))

8.2 The alphabet

LETTERS is a dict from a letter to its point cloud, an \(n \times 2\) array sampled every \(0.05\) units. Each letter is about \(1.4\) units tall.

plot_clouds(LETTERS, ncols=9, size=1.7, xlim=(-0.25, 1.25), ylim=(-0.25, 1.6))

Exercise 8.2: group_letters(clouds, r)

• Input: a dict from letter to point cloud, and a radius.

• Output: a dict from \((\beta_0, \beta_1)\) to a string of letters in alphabetical order, e.g. {(1, 0): "CEF...", (1, 1): ..., ...}.

Guess the groups before running it!

def group_letters(clouds: dict[str, np.ndarray], r: float) -> dict[tuple[int, int], str]:
    # tip: for L in sorted(clouds): add L to the string of classify(clouds[L], r).
    raise NotImplementedError


r_letters = None   # tip: points are 0.05 apart, and the hole of the A is about 0.2 across.

Solution hidden in this cell

check_group_letters(group_letters, r_letters)

colors = {(1, 0): "#7FB3D5", (1, 1): "#F5B041", (1, 2): "crimson"}
def draw_letter(ax, L: str, X: np.ndarray) -> None:
    b = classify(X, r_letters)
    draw(X, cech(X, r_letters), ax=ax, ms=3, lw=0.8)
    ax.set_title(f"{L}: {b}", fontsize=10, color=colors.get(b, "black"), fontweight="bold")

plot_clouds(LETTERS, ncols=9, size=1.7, xlim=(-0.25, 1.25), ylim=(-0.25, 1.6), fn=draw_letter)