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 341–440 of 1085. Source text is displayed literally.

341\draw[thick,bwd] (3.2,-6)--(3.2,-5.538);342\fill[bwd] (3.2,-5.538) circle (1.3pt);343\draw[thick,bwd] (3.6,-6)--(3.6,-5.802);344\fill[bwd] (3.6,-5.802) circle (1.3pt);345\draw[thick,bwd] (4,-6)--(4,-5.637);346\fill[bwd] (4,-5.637) circle (1.3pt);347\draw[thick,bwd] (4.4,-6)--(4.4,-5.34);348\fill[bwd] (4.4,-5.34) circle (1.3pt);349\draw[thick,bwd] (4.8,-6)--(4.8,-5.67);350\fill[bwd] (4.8,-5.67) circle (1.3pt);351\node[anchor=west] at (-3.04,-4.98) {\scriptsize circular};352\end{tikzpicture}353\caption{Four ways of continuing a signal of six samples (shaded) beyond its ends. Reflect padding is the even extension about the half-sample points (dashed), which is the Neumann condition. The odd extension about the neighbouring grid points is the Dirichlet condition; zero padding agrees with it only on the first sample outside. Circular padding is the periodic extension.}\label{fig:pad}354\end{figure}355 356The method of images \cite[Thm.~3.5]{PDEHC} explains this construction. In \cref{fig:pad}, the padding reflects357about half-sample points, repeating the end samples. Let $E\colon\R^n\to\R^{2n}$ be the even extension358$Ex=(x_0,\dots,x_{n-1},x_{n-1},\dots,x_0)$, regarded as a signal on the cycle $\Z/2n$, and let $R$ be the359restriction to the first $n$ entries. The image of $E$ is the space of signals invariant under the reflection360$\rho\colon i\mapsto2n-1-i$.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}