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 401–500 of 1085. Source text is displayed literally.
401 402\begin{proposition}[What padding breaks and keeps]\label{prop:mass}403\Scl \emph{(a)} Circular convolution commutes with translation. With zero padding the commutator with a shift is404supported within the kernel radius of the boundary. \emph{(b)} A layer with a non-negative symmetric kernel of405sum one and reflect padding is doubly stochastic: it conserves the mean and obeys the maximum principle. With406zero padding it is substochastic, and the mass remaining after $m$ layers is the probability that a random407walk with steps distributed by the kernel has not left the interval.408\end{proposition}409 410\noindent For a five-point kernel on $20$ positions the commutator is supported on positions $0$, $18$ and $19$.411\chk{N5} Position information therefore enters a zero-padded network at the boundary and spreads inwards by one412kernel radius per layer, which is the mechanism behind the observation that such networks learn absolute413position \cite{ILB20}. For the kernel $(\frac14,\frac12,\frac14)$ on $32$ positions, $200$ layers with reflect414padding change the total mass by $2\times10^{-15}$, and with zero padding leave $0.5320$ of it, in agreement415with the sum over the sine basis. \chk{N6}416 417\section{Resolution: what commutes with resampling}\label{sec:resolution}418 419Let $B_K$ be the trigonometric polynomials of degree at most $K$ on the circle and420$S_N\colon B_K\to\R^N$ the sampling map on $N$ equally spaced points, injective for $N>2K$. An operator $T$ on421functions with discretizations $T_N$ is natural for refinement (\cref{def:natural}) when $S_NT=T_NS_N$ on $B_K$;422this is the requirement of representation equivalence in \cite{BBRMMA23}.423 424\begin{theorem}[Three kinds of layer]\label{thm:alias}425\Srf[\cite{BBRMMA23,KALHHLA21}] On $B_K$ and for $N>2K$:426\begin{enumerate}[label=(\alph*),leftmargin=1.6em,itemsep=1pt,topsep=2pt]427\item A Fourier multiplier $m(D)$, discretized by the discrete Fourier transform, is natural exactly.428\item The three-point stencil for $-\pd_x^2$ has symbol $k^2\sinc^2(kh/2)$, $h=2\pi/N$: it is natural to second429order.430\item A polynomial nonlinearity of degree $d$ followed by projection to $B_K$ is natural if $N>(d+1)K$, and431for generic inputs only then.432\item A rectifier followed by projection to $B_K$ is natural for no $N$; the defect is of order $N^{-2}$.433\end{enumerate}434\end{theorem}435\begin{proof}436(a) Sampling intertwines the characters $e^{ikx}$, $|k|\le K$, with the discrete ones. (b) Apply the stencil to437$e^{ikx}$. (c) The power has band $dK$, and a frequency $k'$ is sampled onto $k\ne k'$ when $N$ divides $k'-k$;438the largest $|k'-k|$ with $|k|\le K$ is $(d+1)K$. (d) A function with a corner has Fourier coefficients of order439$k^{-2}$, and the sum of those at $k+mN$, $m\neq0$, is of order $N^{-2}$.440\end{proof}441 442\begin{figure}[t]443\centering444\begin{tikzpicture}445\begin{scope}[shift={(0,0)}]446\draw[ink2] (0,3.5)--(0,0)--(6.3,0);447\draw[ink2] (0,0)--(0,-0.07) node[below,inner sep=1.5pt]{\scriptsize $8$};448\draw[ink2] (1.26,0)--(1.26,-0.07) node[below,inner sep=1.5pt]{\scriptsize $16$};449\draw[ink2] (2.52,0)--(2.52,-0.07) node[below,inner sep=1.5pt]{\scriptsize $32$};450\draw[ink2] (3.78,0)--(3.78,-0.07) node[below,inner sep=1.5pt]{\scriptsize $64$};451\draw[ink2] (5.04,0)--(5.04,-0.07) node[below,inner sep=1.5pt]{\scriptsize $128$};452\draw[ink2] (6.3,0)--(6.3,-0.07) node[below,inner sep=1.5pt]{\scriptsize $256$};453\draw[ink2] (0,0)--(-0.07,0) node[left,inner sep=1.5pt]{\scriptsize $10^{-5}$};454\draw[ink2] (0,0.814)--(-0.07,0.814) node[left,inner sep=1.5pt]{\scriptsize $10^{-4}$};455\draw[ink2] (0,1.628)--(-0.07,1.628) node[left,inner sep=1.5pt]{\scriptsize $10^{-3}$};456\draw[ink2] (0,2.441)--(-0.07,2.441) node[left,inner sep=1.5pt]{\scriptsize $10^{-2}$};457\draw[ink2] (0,3.255)--(-0.07,3.255) node[left,inner sep=1.5pt]{\scriptsize $10^{-1}$};458\node[below] at (3.15,-0.38) {\scriptsize grid points $N$};459\draw[ink2,densely dashed] plot coordinates {(0,3.319) (6.3,0.87)};460\draw[thick,fwd] plot coordinates {(0,2.619) (1.26,2.126) (2.52,1.636) (3.78,1.146) (5.04,0.656) (6.3,0.166)};461\draw[thick,bwd] plot coordinates {(1.26,3.149) (2.52,2.434) (3.78,1.89) (5.04,1.321) (6.3,0.933)};462\fill[fwd] (0,2.619) circle (1.6pt);463\fill[fwd] (1.26,2.126) circle (1.6pt);464\fill[fwd] (2.52,1.636) circle (1.6pt);465\fill[fwd] (3.78,1.146) circle (1.6pt);466\fill[fwd] (5.04,0.656) circle (1.6pt);467\fill[fwd] (6.3,0.166) circle (1.6pt);468\fill[bwd] (1.26,3.149) circle (1.6pt);469\fill[bwd] (2.52,2.434) circle (1.6pt);470\fill[bwd] (3.78,1.89) circle (1.6pt);471\fill[bwd] (5.04,1.321) circle (1.6pt);472\fill[bwd] (6.3,0.933) circle (1.6pt);473\node[fwd] at (1.666,1.092) {\scriptsize mean of $\relu(\sin x)$};474\node[bwd] at (4.923,2.261) {\scriptsize random input, band $4$};475\node[ink2] at (2.926,2.751) {\scriptsize slope $-2$};476\end{scope}477\end{tikzpicture}478\caption{Aliasing error of a rectifier against the number of grid points, on logarithmic scales: the closed-form case of \cref{thm:alias}(d) and the largest in-band coefficient error for a random input of band $4$. Both follow the slope $-2$.}\label{fig:alias}479\end{figure}480 481\noindent For a random input of band $5$, the multiplier $(1+k^2)^{-1}$ computed on $16$ and on $64$ points agrees482with the exact result to $10^{-14}$; the stencil is in relative error by $0.221$ and $0.0153$, its symbol at $k=5$483being $0.7173$ and $0.9801$ of the true one. \chk{A1} For band $4$ the in-band coefficients of the square are484exact on $13$ points and wrong by $1.4$ on $12$: the ``two-thirds rule'' of spectral methods \cite{Ors71}.485\chk{A2} For the rectifier one case is closed-form: the mean of $\relu(\sin x)$ sampled on $N$ points is486$\frac1N\cot\frac\pi N$ instead of $\frac1\pi$, an error of $-\pi/3N^2$ to leading order; $N^2$ times the error is487$-1.058$, $-1.050$, $-1.048$, $-1.047$ for $N=8,\dots,64$. \chk{A3} For a random input of band $4$ the largest488in-band error of the rectified signal is $7.4\times10^{-2}$, $9.8\times10^{-3}$, $2.1\times10^{-3}$,489$4.2\times10^{-4}$, $1.4\times10^{-4}$ on $16,\dots,256$ points (\cref{fig:alias}). \chk{A4} This is the quantitative content of the490practice of applying nonlinearities on an oversampled grid and filtering \cite{KALHHLA21}: oversampling by a491factor $M$ buys $M^{2}$, and no finite factor buys exactness. An architecture built from (a) alone is492resolution-independent \cite{LKALBSA21}; one with stencils is so to the order of the stencil; one with493rectifiers is so only approximately, at every resolution.494 495\section{Diffusion models}\label{sec:diffusion}496 497Let data $X_0\sim p_0$ on the line be noised by $X_t=X_0+W_t$, so that the density solves the heat equation498$\pd_tp=\frac12\pd_x^2p$, and write $s=\pd_x\log p_t$ for the \term{score}. Our example is a mixture of two499Gaussians, for which everything is closed-form. \chk{S1}500