Independent scholarship · Open accessThe monthly digest

Indexed text attachment

verify-topology-learning.py

Source for Algebraic and Differential Topology in Machine Learning and AI: Obstructions, Invariants, and Counts

View paper · Download original file

Lines 1184–1283 of 1604. Source text is displayed literally.

1184    if k > 0:1185        B = K.bd(k)1186        L = mat_mul([list(r) for r in zip(*B)], B)1187    if k < K.dim:1188        B = K.bd(k + 1)1189        U = mat_mul(B, [list(r) for r in zip(*B)])1190        L = [[a + b for a, b in zip(r, q)] for r, q in zip(L, U)]1191    return L1192 1193 1194disc, _ = cone(circle(6))1195models = [('sphere', simplex_boundary(2)), ('torus', torus7()), ('projective plane', rp2()), ('Klein bottle', klein()), ('Moebius band', moebius()), ('disc', disc)]1196harm = {nm: [K.n(k) - rank_mod(hodge(K, k), BIGP) for k in range(3)] for nm, K in models}1197check('V1 Hodge: the kernel of the k-th Hodge Laplacian has dimension the k-th Betti number over the reals',1198      harm == {'sphere': [1, 0, 1], 'torus': [1, 2, 1], 'projective plane': [1, 0, 0], 'Klein bottle': [1, 1, 0], 'Moebius band': [1, 1, 0], 'disc': [1, 0, 0]}1199      and all(harm[nm] == bettis(K) for nm, K in models), 'harmonic dimensions %s' % harm)1200 1201m2 = {nm: betti_mod(K, 2) for nm, K in models}1202check('V2 real coefficients are blind to torsion: the projective plane and the disc have the same harmonic spaces, and are separated modulo 2; the Klein bottle and the torus the reverse',1203      harm['projective plane'] == harm['disc'] and m2['projective plane'] == [1, 1, 1] and m2['disc'] == [1, 0, 0]1204      and m2['Klein bottle'] == m2['torus'] == [1, 2, 1] and harm['Klein bottle'] != harm['torus'],1205      'mod 2: projective plane %s, disc %s, Klein bottle %s, torus %s' % (m2['projective plane'], m2['disc'], m2['Klein bottle'], m2['torus']))1206 1207T7 = torus7()1208L1 = [[float(v) for v in r] for r in hodge(T7, 1)]1209ev, _ = jacobi_eig(L1)1210nz = [v for v in ev if v > 1e-9]1211gap, lmax = min(nz), max(ev)1212steps = int(math.ceil(math.log(1e-11) / math.log(1 - gap / lmax)))1213lims = []1214for _ in range(4):1215    X = [random.gauss(0, 1) for _ in range(len(L1))]1216    for _ in range(steps):1217        X = axpy(-1 / lmax, mv(L1, X), X)1218    lims.append(X)1219resid = max(vnorm(mv(L1, X)) / vnorm(X) for X in lims)1220G = [[dot(a, b) for b in lims] for a in lims]1221ge, _ = jacobi_eig(G)1222rk = sum(1 for v in ge if v > 1e-8 * max(ge))1223check('V3 simplicial message passing on edges converges to the harmonic 1-forms: a two-dimensional space on the torus, at the rate of the spectral gap',1224      len(ev) - len(nz) == 2 and resid < 1e-9 and rk == 2, 'gap %.4f, largest eigenvalue %.4f, %d layers for 1e-11; limits of four random inputs span dimension %d' % (gap, lmax, steps, rk))1225 1226 1227def rips_circulant(n, k, maxdim=None):1228    def ok(c):1229        return all(min((a - b) % n, (b - a) % n) <= k for a, b in itertools.combinations(c, 2))1230    simp = []1231    frontier = [(i,) for i in range(n)]1232    while frontier:1233        simp += frontier1234        new = []1235        for c in frontier:1236            if maxdim is not None and len(c) > maxdim:1237                continue1238            for v in range(c[-1] + 1, n):1239                if all(min((a - v) % n, (v - a) % n) <= k for a in c):1240                    new.append(c + (v,))1241        frontier = new1242    return Cx(simp)1243 1244 1245rb = {k: betti_mod(rips_circulant(12, k), 2) for k in (1, 2, 3, 4, 5)}1246def trim(b):1247    b = list(b)1248    while len(b) > 1 and b[-1] == 0:1249        b.pop()1250    return b1251rb = {k: trim(v) for k, v in rb.items()}1252check('V4 Betti numbers for 12 equally spaced points match a circle at steps 1 to 3, a wedge of three 2-spheres at step 4, and a 5-sphere at step 5',1253      rb[1] == rb[2] == rb[3] == [1, 1] and rb[4] == [1, 0, 3] and rb[5] == [1, 0, 0, 0, 0, 1], 'Betti numbers mod 2 by scale k = 1..5: %s' % rb)1254 1255r13 = trim(betti_mod(rips_circulant(13, 5), 2))1256r13b = trim(betti_mod(rips_circulant(13, 4), 2))1257check('V5 for 13 points the scale 5/13 lies between 1/3 and 2/5 and the complex is a 3-sphere', r13 == [1, 0, 0, 1] and r13b == [1, 1], 'Betti numbers at scales 4 and 5: %s, %s' % (r13b, r13))1258 1259angs = sorted(random.uniform(0, 2 * PI) for _ in range(16))1260pts = [(math.cos(a), math.sin(a)) for a in angs]1261gaps = [angs[i + 1] - angs[i] for i in range(15)] + [angs[0] + 2 * PI - angs[-1]]1262maxchord = 2 * math.sin(max(gaps) / 2)1263 1264 1265def rips_points(r):1266    n = len(pts)1267    adj = [[math.hypot(pts[i][0] - pts[j][0], pts[i][1] - pts[j][1]) <= r for j in range(n)] for i in range(n)]1268    F = [[i] for i in range(n)] + [[i, j] for i in range(n) for j in range(i + 1, n) if adj[i][j]]1269    F += [[i, j, k] for i in range(n) for j in range(i + 1, n) for k in range(j + 1, n) if adj[i][j] and adj[i][k] and adj[j][k]]1270    F += [[i, j, k, l] for i in range(n) for j in range(i + 1, n) for k in range(j + 1, n) for l in range(k + 1, n)1271          if adj[i][j] and adj[i][k] and adj[j][k] and adj[i][l] and adj[j][l] and adj[k][l]]1272    return betti_mod(Cx(F), 2)[:2]1273 1274 1275rmid = max(maxchord + 0.03, 1.2)1276bs = {r: rips_points(r) for r in (0.15, rmid, 1.9)}1277check('V6 a random sample of 16 points on the circle: the Rips complex has the Betti numbers (1,1) of the circle from the largest gap up to about sqrt 3, and not outside',1278      rmid < 1.7 and bs[rmid] == [1, 1] and bs[0.15][0] > 1 and bs[1.9] == [1, 0], 'largest gap (chord) %.3f; (b0,b1) at r = 0.15, %.2f, 1.9: %s, %s, %s' % (maxchord, rmid, bs[0.15], bs[rmid], bs[1.9]))1279 1280# --- V7: stability of persistence (own generator)1281def persistence0(f):1282    """sublevel-set persistence in degree 0 of a function on the vertices of a cycle graph: finite pairs (birth, death)"""1283    n = len(f)