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 381–480 of 1085. Source text is displayed literally.
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)};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