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 421–520 of 1055. Source text is displayed literally.
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.481 482\begin{proposition}[Depth multiplies degree]\label{prop:depth}483\Srf[\cite{Tel16}] Let $F$ be the map of the plane that is linear on each of the eight cones over the half-sides484of the square $[-1,1]^2$ and doubles the perimeter coordinate on its boundary. Then $F^L$ maps the boundary to485itself with degree $2^L$ and with $4\cdot2^L$ linear pieces. A network with one hidden layer of $k$ rectifier486units maps the boundary to a curve of at most $2k+4$ pieces, hence of degree less than $k+2$.487\end{proposition}488\begin{proof}489Degree is multiplicative under composition \cite[Prop.~5.4]{ADTHC}. The breaking line of a unit meets the490boundary of the square in at most two points, and the square has four corners; now apply491\cref{thm:pieces}\emph{(b)}.492\end{proof}493 494\noindent The windings are $2,4,\dots,64$ and the pieces $8,16,\dots,256$ for $L=1,\dots,6$. \chk{O9} Each layer495is a fixed continuous piecewise linear map, hence a rectifier network of fixed size \cite{ABMM18}. So a496network of depth $L$ and bounded width reaches degree $2^L$, with a number of pieces within a factor $2$ of the497least that \cref{thm:pieces} allows, while one hidden layer needs more than $2^L-2$ units. This is the498depth-separation phenomenon \cite{Tel16} with the count of oscillations replaced by a homotopy invariant:499degrees multiply under composition and pieces only add within a layer.500 501\subsection{Width}502 503\begin{theorem}[Narrow networks]\label{thm:narrow}504\Sli[\cite{Joh19,HaSe17}] Let $f\colon\R^n\to\R$ be a network whose hidden layers all have $n$ units, with invertible505weight matrices, a non-zero output layer, and an activation that is continuous, strictly increasing and onto506$\R$, such as the leaky rectifier. Then each decision region $\{f>0\}$, $\{f<0\}$ is homeomorphic to $\R^n$ and unbounded. In particular507$f$ cannot separate a bounded class from a class that surrounds it. With one hidden layer of $n+1$ rectifier508units a bounded decision region exists.509\end{theorem}510\begin{proof}511Each hidden layer is a homeomorphism of $\R^n$, so their composite $h$ is one, and $\{f>0\}=h^{-1}(H)$ for an512open half-space $H$. If it were bounded its closure would be compact, and so would the image of the closure513under $h$, which contains $H$. For the last statement let $a_0,\dots,a_n$ be the vertices of a regular simplex centred at the514origin and $f(x)=1-\sum_i\relu(a_i\cdot x)$. Every $x\ne0$ has $a_i\cdot x>0$ for some $i$, and by compactness515$\sum_i\relu(a_i\cdot x)\ge c|x|$ with $c>0$; so $\{f>0\}$ is bounded, and it contains the origin.516\end{proof}517 518\begin{figure}[t]519\centering520\begin{tikzpicture}