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 1241–1340 of 1604. Source text is displayed literally.

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)1284    order = sorted(range(n), key=lambda i: f[i])1285    parent = {}1286    birth = {}1287    pairs = []1288 1289    def find(i):1290        while parent[i] != i:1291            parent[i] = parent[parent[i]]1292            i = parent[i]1293        return i1294 1295    for v in order:1296        parent[v] = v1297        birth[v] = f[v]1298        for u in ((v - 1) % n, (v + 1) % n):1299            if u in parent:1300                ru, rv = find(u), find(v)1301                if ru != rv:1302                    old, young = (ru, rv) if birth[ru] <= birth[rv] else (rv, ru)1303                    if f[v] > birth[young]:1304                        pairs.append((birth[young], f[v]))1305                    parent[young] = old1306    return pairs1307 1308 1309def bottleneck(D1, D2):1310    """bottleneck distance between two finite diagrams, with the diagonal; sup norm in the plane"""1311    n1, n2 = len(D1), len(D2)1312    cand = {0.0}1313    for p in D1:1314        cand.add((p[1] - p[0]) / 2)1315        for q in D2:1316            cand.add(max(abs(p[0] - q[0]), abs(p[1] - q[1])))1317    for q in D2:1318        cand.add((q[1] - q[0]) / 2)1319    cand = sorted(cand)1320 1321    def feasible(delta):1322        # left: points of D1, then diagonal copies of the points of D2; right: points of D2, then diagonal copies of D11323        NL = n1 + n21324        adj = [[] for _ in range(NL)]1325        for i, p in enumerate(D1):1326            for j, q in enumerate(D2):1327                if max(abs(p[0] - q[0]), abs(p[1] - q[1])) <= delta + 1e-12:1328                    adj[i].append(j)1329            if (p[1] - p[0]) / 2 <= delta + 1e-12:1330                adj[i].append(n2 + i)1331        for j, q in enumerate(D2):1332            if (q[1] - q[0]) / 2 <= delta + 1e-12:1333                adj[n1 + j].append(j)1334            adj[n1 + j].extend(range(n2, n2 + n1))1335        match = {}1336 1337        def aug(u, seen):1338            for v in adj[u]:1339                if v in seen:1340                    continue