Independent scholarship · Open accessThe monthly digest

Indexed text attachment

verify-pde-learning.py

Source for Partial Differential Equations in Machine Learning and AI: Naturality, Well-Posedness, and Spectral Rates

View paper · Download original file

Lines 781–880 of 1244. Source text is displayed literally.

781sec('5. Graph networks: diffusion, waves and sheaves')782 783 784def graph_lap(n, edges, signs=None):785    L = [[0.0] * n for _ in range(n)]786    for idx, (u_, v_) in enumerate(edges):787        s = 1.0 if signs is None else signs[idx]788        L[u_][u_] += 1789        L[v_][v_] += 1790        L[u_][v_] -= s791        L[v_][u_] -= s792    return L793 794 795def rand_graph(n, extra):796    edges = [(random.randrange(i), i) for i in range(1, n)]797    while len(edges) < n - 1 + extra:798        a_, b_ = sorted(random.sample(range(n), 2))799        if (a_, b_) not in edges:800            edges.append((a_, b_))801    return edges802 803 804def center(x):805    m = sum(x) / len(x)806    return [a - m for a in x]807 808 809n = 12810E1 = rand_graph(n, 8)811L = graph_lap(n, E1)812lam, _ = jacobi_eig(L)813tau = 1 / lam[-1]814rho = 1 - tau * lam[1]815X = [random.gauss(0, 1) for _ in range(n)]816e0 = dot(X, mv(L, X))817layers99 = None818prev = None819for k in range(1, 201):820    X = axpy(-tau, mv(L, X), X)821    if layers99 is None and dot(X, mv(L, X)) < 0.01 * e0:822        layers99 = k823    if k == 199:824        prev = norm(center(X))825ratio = norm(center(X)) / prev826pred99 = math.log(0.01) / (2 * math.log(rho))827check('G1 linear message passing contracts the non-constant part by 1 - tau*lambda_2 per layer (oversmoothing rate)',828      close(ratio, rho, 1e-4) and layers99 <= math.ceil(pred99),829      'lambda_2 = %.4f, lambda_max = %.4f; measured factor %.5f, predicted %.5f; 99%% of Dirichlet energy lost after %d layers (bound %.1f)' % (lam[1], lam[-1], ratio, rho, layers99, pred99))830 831n = 32832lp = 4 * math.sin(PI / 64) ** 2833Q5 = [(i, i ^ (1 << b)) for i in range(32) for b in range(5) if i < i ^ (1 << b)]834lq, _ = jacobi_eig(graph_lap(32, Q5))835K32 = [(i, j) for i in range(32) for j in range(i + 1, 32)]836x = [random.gauss(0, 1) for _ in range(32)]837y = axpy(-1 / 32, mv(graph_lap(32, K32), x), x)838lpath, _ = jacobi_eig(lap1(32, 'N'))839check('G2 the depth scale 1/(tau*lambda_2) of oversmoothing on 32 nodes: path 415 layers, hypercube 5, complete graph 1',840      close(lpath[1], lp, 1e-9) and close(1 / (0.25 * lp), 415.4, 1e-3) and close(lq[1], 2, 1e-9) and close(lq[-1], 10, 1e-9) and norm(center(y)) < 1e-12,841      'path lambda_2 = %.6f; hypercube lambda_2 = %.3f, lambda_max = %.3f; one layer on the complete graph leaves non-constant part %.0e' % (lpath[1], lq[1], lq[-1], norm(center(y))))842 843n = 12844 845 846def wave_run(L, tau2, steps, x0):847    xm, xc = list(x0), list(x0)848    inv_ = []849    dirs = []850    norms = []851    for _ in range(steps):852        xn = [2 * a - b - tau2 * c for a, b, c in zip(xc, xm, mv(L, xc))]853        d = axpy(-1, xc, xn)854        inv_.append(dot(d, d) / tau2 + dot(xn, mv(L, xc)))855        dirs.append(dot(xn, mv(L, xn)))856        norms.append(norm(xn))857        xm, xc = xc, xn858    return inv_, dirs, norms859 860 861x0 = center([random.gauss(0, 1) for _ in range(n)])862inv_, dirs, _ = wave_run(L, 3.6 / lam[-1], 500, x0)863drift = (max(inv_) - min(inv_)) / abs(inv_[0])864keep = (sum(dirs[400:]) / 100) / (sum(dirs[:100]) / 100)865_, _, norms = wave_run(L, 4.4 / lam[-1], 200, x0)866gr = norms[-1] / norms[-2]867check('G3 a second-order (wave) layer conserves a discrete energy and does not smooth; past the CFL bound it grows by 1.8633 per layer',868      drift < 1e-9 and 0.5 < keep < 2 and close(gr, (2.4 + math.sqrt(2.4 ** 2 - 4)) / 2, 1e-6),869      'invariant drift %.1e over 500 layers; late/early mean Dirichlet energy %.3f; growth factor %.4f at tau^2*lambda_max = 4.4' % (drift, keep, gr))870 871n = 10872E2 = rand_graph(n, 6)873lab = [random.choice([-1.0, 1.0]) for _ in range(n)]874lab[0], lab[1] = 1.0, -1.0875sg = [lab[u_] * lab[v_] for u_, v_ in E2]876LF = graph_lap(n, E2, sg)877L0 = graph_lap(n, E2)878lf, _ = jacobi_eig(LF)879l0, _ = jacobi_eig(L0)880X0 = [random.gauss(0, 1) for _ in range(n)]