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

1144        for i in range(41):1145            t = i / 401146            x = narrow_inv(net, ((1 - t) * ys[0][0] + t * ys[1][0], (1 - t) * ys[0][1] + t * ys[1][1]))1147            ok_conn = ok_conn and sgn * narrow_fwd(net, x) > 01148        # a ray inside the half-plane, pulled back, leaves every bounded set1149        nr = [math.hypot(*narrow_inv(net, (base[0] + sgn * nrm[0] + s_ * tng[0], base[1] + sgn * nrm[1] + s_ * tng[1]))) for s_ in (1e2, 1e3, 1e4)]1150        ok_unb = ok_unb and nr[0] < nr[1] < nr[2] and nr[2] > 501151    r0 = max(1.0, math.hypot(*narrow_inv(net, base)))   # a point of the decision boundary lies at this distance1152    for R_ in (10 * r0, 100 * r0, 1000 * r0):1153        sg = {narrow_fwd(net, (R_ * math.cos(2 * PI * i / 3600), R_ * math.sin(2 * PI * i / 3600))) > 0 for i in range(3600)}1154        ok_circ = ok_circ and sg == {True, False}1155tri = [(math.cos(PI / 2 + 2 * PI * k / 3), math.sin(PI / 2 + 2 * PI * k / 3)) for k in range(3)]1156def island(x):1157    return 1.0 - sum(max(0.0, a[0] * x[0] + a[1] * x[1]) for a in tri)1158isl_out = max(island((4 * math.cos(2 * PI * i / 720), 4 * math.sin(2 * PI * i / 720))) for i in range(720))1159check('O10 width: with two inputs, two units per layer and an injective activation both decision regions are connected and unbounded; three units can enclose a bounded region',1160      ok_conn and ok_unb and ok_circ and island((0.0, 0.0)) > 0 and isl_out < 0,1161      '30 random networks of depth 4: explicit paths inside each region, both classes on three circles of radius 10 to 1000 times the distance of the boundary; three-unit island: value %.1f at the centre, at most %.2f on the circle of radius 4' % (island((0.0, 0.0)), isl_out))1162 1163# --- O11: a global frame on the 3-sphere1164rg11 = random.Random(20261122)1165fr_err = 0.01166for _ in range(200):1167    q = [rg11.gauss(0, 1) for _ in range(4)]1168    n_ = vnorm(q)1169    q = tuple(a / n_ for a in q)1170    fr = [qmul(q, e_) for e_ in ((0, 1, 0, 0), (0, 0, 1, 0), (0, 0, 0, 1))]1171    vs_ = [q] + fr1172    for i in range(4):1173        for j in range(4):1174            fr_err = max(fr_err, abs(sum(a * b for a, b in zip(vs_[i], vs_[j])) - (1.0 if i == j else 0.0)))1175check('O11 the 3-sphere has a global frame: at every unit quaternion q the vectors qi, qj, qk are orthonormal and tangent', fr_err < 1e-12,1176      '200 random points; largest deviation from orthonormality %.1e' % fr_err)1177 1178sec('2. Invariants')1179 1180 1181def hodge(K, k):1182    n = K.n(k)1183    L = [[0] * n for _ in range(n)]1184    if k > 0:1185        B = K.bd(k)1186        L = mat_mul([list(r) for r in zip(*B)], B)1187    if k < K.dim:1188        B = K.bd(k + 1)1189        U = mat_mul(B, [list(r) for r in zip(*B)])1190        L = [[a + b for a, b in zip(r, q)] for r, q in zip(L, U)]1191    return L1192 1193 1194disc, _ = cone(circle(6))1195models = [('sphere', simplex_boundary(2)), ('torus', torus7()), ('projective plane', rp2()), ('Klein bottle', klein()), ('Moebius band', moebius()), ('disc', disc)]1196harm = {nm: [K.n(k) - rank_mod(hodge(K, k), BIGP) for k in range(3)] for nm, K in models}1197check('V1 Hodge: the kernel of the k-th Hodge Laplacian has dimension the k-th Betti number over the reals',1198      harm == {'sphere': [1, 0, 1], 'torus': [1, 2, 1], 'projective plane': [1, 0, 0], 'Klein bottle': [1, 1, 0], 'Moebius band': [1, 1, 0], 'disc': [1, 0, 0]}1199      and all(harm[nm] == bettis(K) for nm, K in models), 'harmonic dimensions %s' % harm)1200 1201m2 = {nm: betti_mod(K, 2) for nm, K in models}1202check('V2 real coefficients are blind to torsion: the projective plane and the disc have the same harmonic spaces, and are separated modulo 2; the Klein bottle and the torus the reverse',1203      harm['projective plane'] == harm['disc'] and m2['projective plane'] == [1, 1, 1] and m2['disc'] == [1, 0, 0]1204      and m2['Klein bottle'] == m2['torus'] == [1, 2, 1] and harm['Klein bottle'] != harm['torus'],1205      'mod 2: projective plane %s, disc %s, Klein bottle %s, torus %s' % (m2['projective plane'], m2['disc'], m2['Klein bottle'], m2['torus']))1206 1207T7 = torus7()1208L1 = [[float(v) for v in r] for r in hodge(T7, 1)]1209ev, _ = jacobi_eig(L1)1210nz = [v for v in ev if v > 1e-9]1211gap, lmax = min(nz), max(ev)1212steps = int(math.ceil(math.log(1e-11) / math.log(1 - gap / lmax)))1213lims = []1214for _ in range(4):1215    X = [random.gauss(0, 1) for _ in range(len(L1))]1216    for _ in range(steps):1217        X = axpy(-1 / lmax, mv(L1, X), X)1218    lims.append(X)1219resid = max(vnorm(mv(L1, X)) / vnorm(X) for X in lims)1220G = [[dot(a, b) for b in lims] for a in lims]1221ge, _ = jacobi_eig(G)1222rk = sum(1 for v in ge if v > 1e-8 * max(ge))1223check('V3 simplicial message passing on edges converges to the harmonic 1-forms: a two-dimensional space on the torus, at the rate of the spectral gap',1224      len(ev) - len(nz) == 2 and resid < 1e-9 and rk == 2, 'gap %.4f, largest eigenvalue %.4f, %d layers for 1e-11; limits of four random inputs span dimension %d' % (gap, lmax, steps, rk))1225 1226 1227def rips_circulant(n, k, maxdim=None):1228    def ok(c):1229        return all(min((a - b) % n, (b - a) % n) <= k for a, b in itertools.combinations(c, 2))1230    simp = []1231    frontier = [(i,) for i in range(n)]1232    while frontier:1233        simp += frontier1234        new = []1235        for c in frontier:1236            if maxdim is not None and len(c) > maxdim:1237                continue1238            for v in range(c[-1] + 1, n):1239                if all(min((a - v) % n, (v - a) % n) <= k for a in c):1240                    new.append(c + (v,))1241        frontier = new1242    return Cx(simp)1243