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 1304–1403 of 1604. Source text is displayed literally.
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)]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)}),