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 361–460 of 1085. Source text is displayed literally.
361 362\begin{theorem}[Reflect padding is the Neumann condition]\label{thm:reflect}363\Srf[\cite{Str99}; \cite{PDEHC}, Thm.~3.5] Write $C^{\mathrm{refl}}_w$ and $C^{\mathrm{circ}}_w$ for the layer with364reflect padding on $\R^n$ and circular padding on $\R^{2n}$.365\begin{enumerate}[label=(\alph*),leftmargin=1.6em,itemsep=1pt,topsep=2pt]366\item $C^{\mathrm{refl}}_w=R\,C^{\mathrm{circ}}_wE$ for every kernel.367\item $\rho\,C^{\mathrm{circ}}_w\rho=C^{\mathrm{circ}}_{\check w}$ with $\check w_j=w_{-j}$. Hence if $w$ is symmetric,368$C^{\mathrm{circ}}_wE=E\,C^{\mathrm{refl}}_w$, and a network of symmetric kernels, reflect padding and pointwise369nonlinearities is the restriction to invariant signals of a circular network on the doubled cycle.370\item The circular layer preserves the reflected subspace exactly when the kernel, reduced modulo $2n$ by371summing coefficients with the same residue, is symmetric. An asymmetric periodized kernel sends some372even input outside that subspace.373\end{enumerate}374\end{theorem}375\begin{proof}376(a) The reflect rule is the definition of $E$ read at indices outside $0,\dots,n-1$. (b) Substituting377$i\mapsto2n-1-i$ in the sum reverses the kernel. Pointwise maps commute with $E$ and $R$.378For (c), work with the periodized kernel and set $a=w-\check w$. If the circular layer preserves the379reflected subspace, then $C^{\mathrm{circ}}_a$ annihilates the even input $\delta_0+\delta_{-1}$,380by (b). Its output at $i$ is $a_i+a_{i+1}=0$. Since $a_0=0$, all $a_i$ vanish.381\end{proof}382 383\noindent For a random input and the kernels $(0.2,-0.5,1,-0.5,0.2)$ and $(0.2,-0.5,1,0.7,-0.3)$: identity (a)384holds to rounding for both; the output on the double is invariant to rounding for the first and has an385anti-invariant part of relative size $1.18$ for the second; and two layers on the double differ from two386reflect-padded layers by $0$ when the symmetric kernel comes first and by $0.100$ when the other does.387\chk{N3} The circular model with symmetric kernels is equivariant under the dihedral group of the doubled388cycle. The half-sample construction restricts it to signals fixed by the chosen reflection. The Dirichlet389construction uses the odd extension about the neighbouring grid points.390 391\begin{proposition}[Zero padding is Dirichlet only for short kernels]\label{prop:zero}392\Sob Let $O\colon\R^n\to\R^{2n+2}$ be the odd extension $(0,x,0,-x^{\mathrm{rev}})$. For a symmetric kernel of radius393one, zero padding equals circular convolution on $Ox$ restricted to the original positions. For radius two or394more it does not: the image construction supplies $-x_0$ beyond the boundary where zero padding supplies $0$.395Pointwise maps commute with $O$ only if they are odd.396\end{proposition}397 398\noindent The relative difference is $0$ for $(0.3,1,0.3)$ and $0.160$ for the five-point symmetric kernel above.399\chk{N4} The Dirichlet image construction can differ from zero padding for wider kernels. A rectifier can400also destroy the odd symmetry required by the construction.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)};