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 1361–1460 of 1604. Source text is displayed literally.
1361changed = 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)]1384 lab = [[min(range(K), key=lambda s: (sites[s][0] - i / G) ** 2 + (sites[s][1] - j / G) ** 2) for j in range(G + 1)] for i in range(G + 1)]1385 left = {lab[0][j] for j in range(G + 1)}1386 right = {lab[G][j] for j in range(G + 1)}1387 bottom = {lab[i][0] for i in range(G + 1)}1388 top = {lab[i][G] for i in range(G + 1)}1389 if (left & right) or (bottom & top):1390 return None1391 return sum(1 for i in range(G) for j in range(G) if len({lab[i][j], lab[i + 1][j], lab[i][j + 1], lab[i + 1][j + 1]}) >= 3)1392 1393 1394vj = [v for v in (voronoi_junctions(60, 14) for _ in range(60)) if v is not None]1395check('N1 Lebesgue: a partition of the square into regions none of which joins opposite sides has a point where three regions meet',1396 len(vj) >= 30 and min(vj) >= 1, '%d random nearest-prototype classifiers with 14 classes: between %d and %d triple junctions' % (len(vj), min(vj), max(vj)))1397 1398 1399def voronoi3(G, K):1400 sites = [(random.random(), random.random(), random.random()) for _ in range(K)]1401 lab = [[[min(range(K), key=lambda s: (sites[s][0] - i / G) ** 2 + (sites[s][1] - j / G) ** 2 + (sites[s][2] - k / G) ** 2) for k in range(G + 1)] for j in range(G + 1)] for i in range(G + 1)]1402 faces = [({lab[0][j][k] for j in range(G + 1) for k in range(G + 1)}, {lab[G][j][k] for j in range(G + 1) for k in range(G + 1)}),1403 ({lab[i][0][k] for i in range(G + 1) for k in range(G + 1)}, {lab[i][G][k] for i in range(G + 1) for k in range(G + 1)}),1404 ({lab[i][j][0] for i in range(G + 1) for j in range(G + 1)}, {lab[i][j][G] for i in range(G + 1) for j in range(G + 1)})]1405 if any(a & b for a, b in faces):1406 return None1407 return sum(1 for i in range(G) for j in range(G) for k in range(G)1408 if len({lab[i + a][j + b][k + c] for a in (0, 1) for b in (0, 1) for c in (0, 1)}) >= 4)1409 1410 1411v3 = [v for v in (voronoi3(18, 40) for _ in range(8)) if v is not None]1412check('N2 in dimension three the same holds with four regions', len(v3) >= 3 and min(v3) >= 1, '%d classifiers with 40 classes on the cube: between %d and %d quadruple junctions' % (len(v3), min(v3), max(v3)))1413 1414 1415def fmap(p):1416 x, y, z = p1417 q = (0.2 + 0.5 * y + 0.3 * z * z, 0.1 + 0.6 * z + 0.2 * x * y, 0.3 + 0.4 * x + 0.1 * y * y)1418 s = sum(q)1419 return tuple(a / s for a in q)1420 1421 1422def door_walk(n):1423 def pt(i, j):1424 return ((n - i - j) / n, i / n, j / n)1425 cache = {}1426 def lab(v):1427 if v not in cache:1428 p = pt(*v)1429 q = fmap(p)1430 cache[v] = next((k for k in range(3) if p[k] > 0 and q[k] <= p[k]), max(range(3), key=lambda k: p[k]))1431 return cache[v]1432 def cells_of_edge(a, b):1433 (i1, j1), (i2, j2) = sorted([a, b])1434 out = []1435 for c in [(i1 + i2 - j1 - j2 + 0, 0)]:1436 pass1437 # third vertices completing a grid triangle with edge ab1438 cands = []1439 di, dj = i2 - i1, j2 - j11440 if (di, dj) == (1, 0):1441 cands = [(i1, j1 + 1), (i2, j2 - 1)]1442 elif (di, dj) == (0, 1):1443 cands = [(i1 + 1, j1), (i1 - 1, j2)]1444 else: # (1,-1)1445 cands = [(i1, j1 - 1), (i2, j1)]1446 return [c for c in cands if c[0] >= 0 and c[1] >= 0 and c[0] + c[1] <= n]1447 best = None1448 for i in range(n):1449 a, b = (i, 0), (i + 1, 0)1450 if {lab(a), lab(b)} != {0, 1}:1451 continue1452 steps = 01453 edge = (a, b)1454 third = cells_of_edge(a, b)[0]1455 prev_third = None1456 while True:1457 steps += 11458 tri = (edge[0], edge[1], third)1459 if lab(third) == 2:1460 best = steps if best is None else min(best, steps)