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

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                    continue1341                seen.add(v)1342                if v not in match or aug(match[v], seen):1343                    match[v] = u1344                    return True1345            return False1346 1347        return all(aug(u, set()) for u in range(NL))1348 1349    lo_, hi_ = 0, len(cand) - 11350    while lo_ < hi_:1351        md = (lo_ + hi_) // 21352        if feasible(cand[md]):1353            hi_ = md1354        else:1355            lo_ = md + 11356    return cand[lo_]1357 1358 1359rg7 = random.Random(20261123)1360ratio = 0.01361changed = 01362ok_st = True1363for _ in range(60):1364    n_ = 401365    f = [rg7.gauss(0, 1) for _ in range(n_)]1366    # smooth a little so that the diagrams have bars of several lengths1367    f = [(f[i - 1] + 2 * f[i] + f[(i + 1) % n_]) / 4 for i in range(n_)]1368    eps_ = rg7.uniform(0.02, 0.3)1369    g_ = [a + rg7.uniform(-eps_, eps_) for a in f]1370    sup = max(abs(a - b) for a, b in zip(f, g_))1371    D1, D2 = persistence0(f), persistence0(g_)1372    dB = bottleneck(D1, D2)1373    ok_st = ok_st and dB <= sup + 1e-12 and abs(min(f) - min(g_)) <= sup + 1e-121374    ratio = max(ratio, dB / sup)1375    changed += 1 if len(D1) != len(D2) else 01376check('V7 stability: the persistence diagram of a function moves by at most the sup-norm of a perturbation, in the bottleneck distance, although the number of bars changes',1377      ok_st and changed > 0, '60 random functions on a cycle of 40 vertices: largest ratio of bottleneck distance to perturbation %.3f; the number of bars changed in %d cases' % (ratio, changed))1378 1379sec('3. Counts')1380 1381 1382def voronoi_junctions(G, K):1383    sites = [(random.random(), random.random()) for _ in range(K)]