Independent scholarship · Open accessThe monthly digest

Indexed text attachment

partial-differential-equations-in-machine-learning-and-ai.tex

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

View paper · Download original file

Lines 645–744 of 1085. Source text is displayed literally.

645\draw[fwd] plot coordinates {(0,3.411) (0.076,3.393) (0.151,3.376) (0.227,3.358) (0.302,3.341) (0.378,3.324) (0.454,3.307) (0.529,3.29) (0.605,3.274) (0.68,3.258) (0.756,3.242) (0.832,3.227) (0.907,3.212) (0.983,3.197) (1.058,3.183) (1.134,3.169) (1.21,3.155) (1.285,3.142) (1.361,3.129) (1.436,3.116) (1.512,3.104) (1.588,3.093) (1.663,3.081) (1.739,3.071) (1.814,3.06) (1.89,3.05) (1.966,3.041) (2.041,3.032) (2.117,3.023) (2.192,3.015) (2.268,3.007) (2.344,2.999) (2.419,2.992) (2.495,2.986) (2.57,2.979) (2.646,2.973) (2.722,2.967) (2.797,2.962) (2.873,2.957) (2.948,2.952) (3.024,2.947) (3.1,2.942) (3.175,2.938) (3.251,2.933) (3.326,2.929) (3.402,2.924) (3.478,2.92) (3.553,2.916) (3.629,2.912) (3.704,2.908) (3.78,2.903) (3.856,2.899) (3.931,2.895) (4.007,2.891) (4.082,2.887) (4.158,2.882) (4.234,2.878) (4.309,2.874) (4.385,2.87) (4.46,2.866) (4.536,2.861) (4.612,2.857) (4.687,2.853) (4.763,2.849) (4.838,2.845) (4.914,2.84) (4.99,2.836) (5.065,2.832) (5.141,2.828) (5.216,2.824) (5.292,2.819) (5.368,2.815) (5.443,2.811) (5.519,2.807) (5.594,2.803) (5.67,2.799) (5.746,2.794) (5.821,2.79) (5.897,2.786) (5.972,2.782) (6.048,2.778) (6.124,2.773)};646\draw[fwd] plot coordinates {(0,3.627) (0.076,3.607) (0.151,3.586) (0.227,3.566) (0.302,3.546) (0.378,3.527) (0.454,3.508) (0.529,3.489) (0.605,3.47) (0.68,3.452) (0.756,3.434) (0.832,3.416) (0.907,3.399) (0.983,3.382) (1.058,3.366) (1.134,3.35) (1.21,3.334) (1.285,3.319) (1.361,3.304) (1.436,3.289) (1.512,3.275) (1.588,3.262) (1.663,3.249) (1.739,3.236) (1.814,3.224) (1.89,3.212) (1.966,3.2) (2.041,3.189) (2.117,3.179) (2.192,3.168) (2.268,3.158) (2.344,3.149) (2.419,3.14) (2.495,3.131) (2.57,3.122) (2.646,3.114) (2.722,3.106) (2.797,3.098) (2.873,3.09) (2.948,3.082) (3.024,3.075) (3.1,3.067) (3.175,3.06) (3.251,3.052) (3.326,3.045) (3.402,3.038) (3.478,3.031) (3.553,3.024) (3.629,3.016) (3.704,3.009) (3.78,3.002) (3.856,2.995) (3.931,2.988) (4.007,2.981) (4.082,2.973) (4.158,2.966) (4.234,2.959) (4.309,2.952) (4.385,2.945) (4.46,2.938) (4.536,2.931) (4.612,2.923) (4.687,2.916) (4.763,2.909) (4.838,2.902) (4.914,2.895) (4.99,2.888) (5.065,2.88) (5.141,2.873) (5.216,2.866) (5.292,2.859) (5.368,2.852) (5.443,2.845) (5.519,2.838) (5.594,2.83) (5.67,2.823) (5.746,2.816) (5.821,2.809) (5.897,2.802) (5.972,2.795) (6.048,2.787) (6.124,2.78)};647\fill[black] (6.3,2.764) circle (1.8pt);648\fill[black] (6.3,1.036) circle (1.8pt);649\node[accent] at (2.406,4.016) {\scriptsize $t^*$};650\end{scope}651\end{tikzpicture}652\caption{Characteristics of the flow-matching field from $N(0,1)$ to the two points $\pm1$ (\cref{prop:pitchfork}). The midpoint is attracting until $t^*=0.382$ and repelling afterwards; the dotted line is the unstable trajectory. No two characteristics cross.}\label{fig:pitchfork}653\end{figure}654 655\noindent The field satisfies the continuity equation with $p_t$ to $10^{-13}$; the slope at the midpoint changes656sign at $0.381966$ and is $890$ at $t=0.9$ (\cref{fig:pitchfork}). \chk{F3} This is the transport-side picture of657\cref{thm:illposed}(c): mass begins to be committed to one of the two points at a definite time $t^*$, by the bifurcation658that \cite[Thm.~14.7]{PDEHC} describes for a buckling rod, and the field then steepens without bound as the659characteristics focus. Such transition times have been studied for diffusion models in high dimension660\cite{BBDM24}.661 662\section{Graph networks}\label{sec:graphs}663 664Let $L$ be the Laplacian of a connected graph with eigenvalues $0=\lambda_1<\lambda_2\le\dots\le\lambda_n$. The665linear part of a message-passing layer is $X\mapsto(I-\tau L)X$, one explicit Euler step of the heat equation on666the graph \cite{CRGBB21}.667 668\begin{theorem}[Oversmoothing is the spectral gap]\label{thm:oversmooth}669\Scl[\cite{LHW18,OoSu20}] For $0<\tau\le1/\lambda_n$ the non-constant part of $X$ is multiplied by at most670$1-\tau\lambda_2$ per layer, with equality in the limit, and the Dirichlet energy $X^{\T}LX$ by at most671$(1-\tau\lambda_2)^2$. The depth at which features become indistinguishable is of order $1/\tau\lambda_2$.672\end{theorem}673 674\noindent On a random connected graph with $12$ nodes, $\lambda_2=0.6251$, $\lambda_n=8.2655$ and the measured675factor is $0.92437$, as predicted; $99\%$ of the Dirichlet energy of a random input is gone after $15$ layers,676the bound from $\lambda_2$ alone being $29$. \chk{G1} The depth scale varies by orders of magnitude with the677graph: on $32$ nodes, with $\tau$ at its largest stable value, it is $415$ layers for a path678($\lambda_2=0.00963$), $5$ for the hypercube ($\lambda_2=2$, $\lambda_n=10$) and $1$ for the complete graph,679where a single layer returns the mean exactly (\cref{fig:smooth}). \chk{G2} Graphs that are good for propagating information are680the ones that oversmooth fastest; the two are the same eigenvalue.681 682\begin{figure}[t]683\centering684\begin{tikzpicture}685\begin{scope}[shift={(0,0)}]686\draw[ink2] (0,3.6)--(0,0)--(6.3,0);687\draw[ink2] (0,0)--(0,-0.07) node[below,inner sep=1.5pt]{\scriptsize $0$};688\draw[ink2] (2.1,0)--(2.1,-0.07) node[below,inner sep=1.5pt]{\scriptsize $20$};689\draw[ink2] (4.2,0)--(4.2,-0.07) node[below,inner sep=1.5pt]{\scriptsize $40$};690\draw[ink2] (6.3,0)--(6.3,-0.07) node[below,inner sep=1.5pt]{\scriptsize $60$};691\draw[ink2] (0,0)--(-0.07,0) node[left,inner sep=1.5pt]{\scriptsize $10^{-8}$};692\draw[ink2] (0,0.774)--(-0.07,0.774) node[left,inner sep=1.5pt]{\scriptsize $10^{-6}$};693\draw[ink2] (0,1.548)--(-0.07,1.548) node[left,inner sep=1.5pt]{\scriptsize $10^{-4}$};694\draw[ink2] (0,2.322)--(-0.07,2.322) node[left,inner sep=1.5pt]{\scriptsize $10^{-2}$};695\draw[ink2] (0,3.096)--(-0.07,3.096) node[left,inner sep=1.5pt]{\scriptsize $1$};696\node[below] at (3.15,-0.38) {\scriptsize layers};697\draw[thick,accent] plot coordinates {(0,3.096) (0.105,3.318) (0.21,3.323) (0.315,3.125) (0.42,3.116) (0.525,3.297) (0.63,3.315) (0.735,3.189) (0.84,3.118) (0.945,3.285) (1.05,3.305) (1.155,3.206) (1.26,3.149) (1.365,3.277) (1.47,3.293) (1.575,3.222) (1.68,3.161) (1.785,3.264) (1.89,3.302) (1.995,3.215) (2.1,3.168) (2.205,3.264) (2.31,3.293) (2.415,3.222) (2.52,3.201) (2.625,3.253) (2.73,3.265) (2.835,3.248) (2.94,3.234) (3.045,3.237) (3.15,3.237) (3.255,3.249) (3.36,3.263) (3.465,3.249) (3.57,3.206) (3.675,3.219) (3.78,3.298) (3.885,3.255) (3.99,3.183) (4.095,3.206) (4.2,3.291) (4.305,3.289) (4.41,3.172) (4.515,3.166) (4.62,3.298) (4.725,3.307) (4.83,3.122) (4.935,3.166) (5.04,3.311) (5.145,3.303) (5.25,3.103) (5.355,3.16) (5.46,3.322) (5.565,3.302) (5.67,3.089) (5.775,3.138) (5.88,3.326) (5.985,3.311) (6.09,3.088) (6.195,3.134) (6.3,3.311)};698\draw[thick,fwd] plot coordinates {(0,3.096) (0.105,2.805) (0.21,2.707) (0.315,2.632) (0.42,2.569) (0.525,2.514) (0.63,2.466) (0.735,2.424) (0.84,2.388) (0.945,2.356) (1.05,2.329) (1.155,2.305) (1.26,2.284) (1.365,2.266) (1.47,2.249) (1.575,2.234) (1.68,2.22) (1.785,2.206) (1.89,2.194) (1.995,2.182) (2.1,2.17) (2.205,2.159) (2.31,2.148) (2.415,2.137) (2.52,2.127) (2.625,2.116) (2.73,2.106) (2.835,2.096) (2.94,2.087) (3.045,2.077) (3.15,2.067) (3.255,2.058) (3.36,2.049) (3.465,2.04) (3.57,2.031) (3.675,2.022) (3.78,2.014) (3.885,2.005) (3.99,1.997) (4.095,1.988) (4.2,1.98) (4.305,1.972) (4.41,1.964) (4.515,1.956) (4.62,1.949) (4.725,1.941) (4.83,1.934) (4.935,1.926) (5.04,1.919) (5.145,1.912) (5.25,1.905) (5.355,1.898) (5.46,1.891) (5.565,1.884) (5.67,1.878) (5.775,1.871) (5.88,1.865) (5.985,1.858) (6.09,1.852) (6.195,1.846) (6.3,1.84)};699\draw[thick,bwd] plot coordinates {(0,3.096) (0.105,2.849) (0.21,2.662) (0.315,2.52) (0.42,2.407) (0.525,2.31) (0.63,2.223) (0.735,2.141) (0.84,2.062) (0.945,1.984) (1.05,1.908) (1.155,1.832) (1.26,1.757) (1.365,1.682) (1.47,1.606) (1.575,1.531) (1.68,1.456) (1.785,1.381) (1.89,1.306) (1.995,1.231) (2.1,1.156) (2.205,1.081) (2.31,1.006) (2.415,0.931) (2.52,0.856) (2.625,0.781) (2.73,0.706) (2.835,0.631) (2.94,0.556) (3.045,0.481) (3.15,0.406) (3.255,0.331) (3.36,0.256) (3.465,0.181) (3.57,0.106) (3.675,0.031)};700\node[accent] at (4.62,2.74) {\scriptsize wave layer, path};701\node[fwd] at (4.41,2.089) {\scriptsize heat layer, path};702\node[bwd,right] at (2.835,0.959) {\scriptsize heat layer, hypercube};703\end{scope}704\end{tikzpicture}705\caption{Dirichlet energy of a random signal on $32$ nodes against depth, relative to its initial value. Heat-type layers lose it at a rate set by the spectral gap, slowly on a path and quickly on a hypercube; a wave-type layer on the path (\cref{thm:wavegnn}) keeps it.}\label{fig:smooth}706\end{figure}707 708A layer of second order in depth behaves as a wave equation \cite{RCRMB22}.709 710\begin{theorem}[Wave layers]\label{thm:wavegnn}711\Srf[\cite{PDEHC}, Thm.~12.3] The recursion $X_{m+1}=2X_m-X_{m-1}-\tau^2LX_m$ conserves712\[ \tau^{-2}\lVert X_{m+1}-X_m\rVert^2+X_{m+1}^{\T}LX_m, \]713which is positive definite on non-constant signals for $\tau^2\lambda_n<4$. For $\tau^2\lambda_n>4$ the top mode714grows per layer by the modulus of the larger root of $\xi^2+(\tau^2\lambda_n-2)\xi+1=0$.715\end{theorem}716 717\noindent Over $500$ layers at $\tau^2\lambda_n=3.6$ the invariant drifts by $2\times10^{-15}$ and the mean718Dirichlet energy of the last hundred layers is $1.001$ times that of the first hundred: nothing is smoothed. At719$\tau^2\lambda_n=4.4$ the growth factor is $1.8633$. \chk{G3} The bound is the Courant--Friedrichs--Lewy720condition, and the dichotomy between the two theorems is that of \cite[Ch.~4]{PDEHC}: a Markov semigroup721forgets, a symplectic group does not.722 723Both layers assume that neighbouring nodes should agree. A \term{cellular sheaf} \cite{HaGh19} replaces724agreement by agreement after transport: each edge carries linear maps from the data at its ends, and the sheaf725Laplacian $L_{\mathcal F}$ penalizes the mismatch. Its kernel is the space $H^0$ of global sections. The simplest726case is a sign $\sigma_e=\pm1$ on each edge, with $x^{\T}L_{\mathcal F}x=\sum_{e=uv}(x_u-\sigma_ex_v)^2$.727 728\begin{theorem}[Sheaf diffusion]\label{thm:sheaf}729\Sli[\cite{HaGh19,BDCLB22}] Diffusion by $L_{\mathcal F}$ converges to the orthogonal projection of the input730onto $H^0$. For a sign sheaf on a connected graph, $H^0$ has dimension one if the signs are a coboundary,731$\sigma_{uv}=\ell_u\ell_v$, in which case it is spanned by $\ell$; otherwise $H^0=0$. The obstruction is the class732of $\sigma$ in $H^1(G;\Z/2)$, a group of order $2^{E-V+1}$.733\end{theorem}734 735\noindent On a random graph with ten nodes, two classes, and signs $+$ within and $-$ between classes, sheaf736diffusion converges to the class labelling times $\langle\ell,X_0\rangle/n$, to rounding, while ordinary diffusion737converges to a constant and loses the classes. Reversing one edge that lies on a cycle makes the smallest738eigenvalue $0.1606$ and the limit zero; for a cycle of length $7$ with one negative edge it is739$4\sin^2\frac\pi{14}=0.19806$, the antiperiodic Laplacian. \chk{G4} On a graph with $5$ nodes and $7$ edges,740exactly $16=2^{V-1}$ of the $128$ sign assignments have a non-zero section, and they are exactly those whose741Laplacian is singular over the rationals; the $128$ assignments fall into $8=2^{E-V+1}$ classes. \chk{G5} This742is the same first cohomology that classifies flat gauge fields in \cite[Prop.~13.1]{PDEHC}: choosing the743transport maps of a sheaf network is choosing a connection, and heterophily is non-trivial holonomy. A sign744sheaf whose class is non-zero cannot be made consistent by relabelling nodes, and its diffusion has no