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 1404–1503 of 1604. Source text is displayed literally.
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)1461 break1462 # leave through the other 01-edge1463 other = edge[0] if lab(edge[0]) != lab(third) else edge[1]1464 new_edge = (other, third)1465 nxt = [c for c in cells_of_edge(*new_edge) if c not in tri]1466 if not nxt:1467 break1468 edge, third = new_edge, nxt[0]1469 return best1470 1471 1472walks = {n: door_walk(n) for n in (16, 32, 64, 128)}1473check('N3 finding a complete Sperner cell by walking through doors takes a number of steps proportional to the side of the grid, not to the number of cells',1474 all(walks[n] is not None for n in walks) and walks[128] < 6 * 128 and 1.5 < walks[128] / walks[64] < 2.6,1475 'steps %s for n = 16, 32, 64, 128; cells %s' % ([walks[n] for n in sorted(walks)], [n * n for n in sorted(walks)]))1476 1477 1478def circle_fixed(d, eps, g, n=6000):1479 h = lambda t: (d - 1) * t + eps * g(t)1480 tot = cnt = 01481 for m in range(-abs(d) - 6, abs(d) + 7):1482 prev = h(0.0) - 2 * PI * m1483 for i in range(1, n + 1):1484 cur = h(2 * PI * i / n) - 2 * PI * m1485 if prev == 0 or prev * cur < 0:1486 cnt += 11487 tot += -1 if cur > prev else 11488 prev = cur1489 return tot, cnt1490 1491 1492okcf = True1493info = []1494for d in (-2, 0, 1, 2, 3):1495 for eps in (0.3, 2.0):1496 g = trig_poly(4)1497 s, c = circle_fixed(d, eps, g)1498 okcf = okcf and s == 1 - d and c >= abs(1 - d) and (c - abs(1 - d)) % 2 == 01499 if eps == 2.0:1500 info.append('d=%d: %d points, signed %d' % (d, c, s))1501check('N4 fixed points of a circle map of degree d, counted with index, number 1 - d; a perturbed ring attractor (d = 1) has an even number, half of them stable',1502 okcf, '; '.join(info))1503