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 784–883 of 1244. Source text is displayed literally.
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)]881Xs, Xo = list(X0), list(X0)882for _ in range(3000):883 Xs = axpy(-1 / lf[-1], mv(LF, Xs), Xs)