Indexed text attachment
algebraic-and-differential-topology-in-machine-learning-and-ai.tex
Source for Algebraic and Differential Topology in Machine Learning and AI: Obstructions, Invariants, and Counts
View paper · Download original file
Lines 381–480 of 1055. Source text is displayed literally.
381\end{tikzpicture}382\caption{The index of a vertex for a function on a mesh. Filled neighbours are higher than the centre, open ones lower; the index is one minus half the number of changes round the link. A minimum has the same link as a maximum with the marks exchanged, and index $1$.}\label{fig:index}383\end{figure}384 385\noindent The rule is drawn in \cref{fig:index}. The sums are $2,2,0,1,0$ for a tetrahedron, an icosahedron, the seven-vertex torus, the six-vertex386projective plane and a Klein bottle, for $100$ random functions each. \chk{O6} So a global frame field exists on a387closed orientable surface only when $\chi=0$, and on a sphere every choice of frames is singular with total388index $2$. This is the obstruction that gauge-equivariant convolution is designed around \cite{CWKW19}: since no389frame can be chosen, the layers must be equivariant for changes of frame.390 391In higher dimensions the same question has a sharp answer. A sphere $S^n$ with $n$ even has $\chi=2$ and not392even one tangent field without zeros; and $S^n$ has a global frame exactly for $n=1,3,7$, a theorem of the same393family as the Hopf invariant one problem \cite[Rem.~9.7]{ADTHC}. On $S^3$ the frame is explicit: at a unit394quaternion $q$ the vectors $qi$, $qj$, $qk$ are orthonormal and tangent. \chk{O11} This is why a latent space or395an output space that is a circle, a torus or the group of unit quaternions needs no gauge, and why constructions396that push a fixed noise distribution through the group multiplication are available there \cite{FdH18}, while397on $S^2$ they are not.398 399\subsection{Pieces and degree}400 401\begin{theorem}[Capacity for winding]\label{thm:pieces}402\Sob \emph{(a)} A continuous piecewise linear function of one variable with $k$ breakpoints is the sum of an403affine function and $k$ rectifier units. \emph{(b)} A closed piecewise linear curve in the punctured plane with $N$404segments has winding number of absolute value less than $N/2$. \emph{(c)} The polygon through the images of $N$405equally spaced points under $z\mapsto z^d$ winds $d'$ times, where $d'\equiv d\pmod N$ and $|d'|<N/2$.406\end{theorem}407\begin{proof}408(a) To the leftmost affine piece add one unit $c_i\relu(x-x_i)$ per breakpoint $x_i$, with $c_i$ the change of409slope. (b) A segment missing the410origin subtends an angle less than $\pi$. (c) Consecutive vertices differ by the angle $2\pi d/N$, taken in411$(-\pi,\pi)$.412\end{proof}413 414\begin{figure}[t]415\centering416\begin{tikzpicture}417\draw[ink2,thin] (1.9,0) circle (1.42);418\draw[fwd,thick,-{Stealth[length=4pt]}] (1.9,1.42)--(2.351,0.033);419\draw[fwd,thick] (2.351,0.033)--(2.735,-1.149);420\draw[fwd,thick,-{Stealth[length=4pt]}] (2.735,-1.149)--(1.555,-0.291);421\draw[fwd,thick] (1.555,-0.291)--(0.549,0.439);422\draw[fwd,thick,-{Stealth[length=4pt]}] (0.549,0.439)--(2.008,0.439);423\draw[fwd,thick] (2.008,0.439)--(3.251,0.439);424\draw[fwd,thick,-{Stealth[length=4pt]}] (3.251,0.439)--(2.071,-0.419);425\draw[fwd,thick] (2.071,-0.419)--(1.065,-1.149);426\draw[fwd,thick,-{Stealth[length=4pt]}] (1.065,-1.149)--(1.516,0.238);427\draw[fwd,thick] (1.516,0.238)--(1.9,1.42);428\fill[bwd] (1.9,1.42) circle (1.5pt);429\node at (1.9,1.64) {\scriptsize $0$};430\fill[bwd] (2.735,-1.149) circle (1.5pt);431\node at (2.864,-1.327) {\scriptsize $1$};432\fill[bwd] (0.549,0.439) circle (1.5pt);433\node at (0.34,0.507) {\scriptsize $2$};434\fill[bwd] (3.251,0.439) circle (1.5pt);435\node at (3.46,0.507) {\scriptsize $3$};436\fill[bwd] (1.065,-1.149) circle (1.5pt);437\node at (0.936,-1.327) {\scriptsize $4$};438\fill[accent] (1.9,0) circle (1.3pt);439\node at (1.9,-2.04) {\scriptsize $N=5$: winding $-2$};440\draw[ink2,thin] (6,0) circle (1.42);441\draw[fwd,thick,-{Stealth[length=4pt]}] (6,1.42)--(5.667,-0.038);442\draw[fwd,thick] (5.667,-0.038)--(5.384,-1.279);443\draw[fwd,thick,-{Stealth[length=4pt]}] (5.384,-1.279)--(6.316,-0.11);444\draw[fwd,thick] (6.316,-0.11)--(7.11,0.885);445\draw[fwd,thick,-{Stealth[length=4pt]}] (7.11,0.885)--(5.763,0.237);446\draw[fwd,thick] (5.763,0.237)--(4.616,-0.316);447\draw[fwd,thick,-{Stealth[length=4pt]}] (4.616,-0.316)--(6.111,-0.316);448\draw[fwd,thick] (6.111,-0.316)--(7.384,-0.316);449\draw[fwd,thick,-{Stealth[length=4pt]}] (7.384,-0.316)--(6.037,0.333);450\draw[fwd,thick] (6.037,0.333)--(4.89,0.885);451\draw[fwd,thick,-{Stealth[length=4pt]}] (4.89,0.885)--(5.822,-0.284);452\draw[fwd,thick] (5.822,-0.284)--(6.616,-1.279);453\draw[fwd,thick,-{Stealth[length=4pt]}] (6.616,-1.279)--(6.283,0.178);454\draw[fwd,thick] (6.283,0.178)--(6,1.42);455\fill[bwd] (6,1.42) circle (1.5pt);456\node at (6,1.64) {\scriptsize $0$};457\fill[bwd] (5.384,-1.279) circle (1.5pt);458\node at (5.288,-1.478) {\scriptsize $1$};459\fill[bwd] (7.11,0.885) circle (1.5pt);460\node at (7.282,1.023) {\scriptsize $2$};461\fill[bwd] (4.616,-0.316) circle (1.5pt);462\node at (4.401,-0.365) {\scriptsize $3$};463\fill[bwd] (7.384,-0.316) circle (1.5pt);464\node at (7.599,-0.365) {\scriptsize $4$};465\fill[bwd] (4.89,0.885) circle (1.5pt);466\node at (4.718,1.023) {\scriptsize $5$};467\fill[bwd] (6.616,-1.279) circle (1.5pt);468\node at (6.712,-1.478) {\scriptsize $6$};469\fill[accent] (6,0) circle (1.3pt);470\node at (6,-2.04) {\scriptsize $N=7$: winding $3$};471\end{tikzpicture}472\caption{The map $z\mapsto z^3$ of the circle sampled at $N$ equally spaced points and joined by segments; the numbers give the order of the samples. With seven pieces each step is $\frac37$ of a turn forwards and the polygon winds $3$ times. With five, each step of $\frac35$ of a turn is drawn as the shorter arc, $\frac25$ of a turn backwards, and the polygon winds $-2$ times.}\label{fig:polygons}473\end{figure}474 475\noindent Part (a) was confirmed on $50$ random functions with six breakpoints. \chk{O7} The polygons for $d=3$ wind $-2$, $3$, $3$ times for $N=5,7,12$ (\cref{fig:polygons}), and for $(d,N)=(5,8)$ and476$(7,10)$ they wind $-3$ times. \chk{O8} A network whose output curve has $N$ linear pieces therefore cannot477represent a map of the circle of degree $d$ unless $N\ge2|d|+1$: too few pieces alias the degree exactly as too478few samples alias a frequency. This is the simplicial approximation theorem \cite[Thm.~3.2]{ADTHC} with its479hypothesis made visible: sampling a map at the vertices of a subdivision always gives a piecewise linear map,480and that map is in the right homotopy class only when the subdivision is fine enough for the star condition.