Independent scholarship · Open accessThe monthly digest

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 455–554 of 1055. Source text is displayed literally.

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}521\begin{scope}522\clip (0,0) rectangle (3.3,3.3);523\fill[fwd!16] (-20.35,-20.35)--(1.445,1.821)--(1.459,1.837)--(2.195,2.429)--(2.194,2.428)--(1.897,1.884)--(1.897,1.883)--(1.921,1.903)--(1.972,1.945)--(1.976,1.944)--(17.881,-7.904)--(17.933,-7.942)--(23.65,-20.35)--(23.65,-20.35)--(23.65,-20.35)--(23.65,-20.35)--(23.65,-20.35)--(23.65,-20.35)--(23.65,-20.35)--(23.65,-20.35)--(23.65,-20.35)--(23.65,-20.35)--(23.65,-20.35)--(23.65,-20.35)--(23.65,-20.35)--(23.65,-20.35)--(23.65,-20.35)--(23.65,-20.35)--(23.65,-20.35)--(23.65,-20.35)--(23.65,-20.35)--(23.65,-20.35)--(23.65,-20.35)--(23.65,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--cycle;524\draw[fwd,thick] (-20.35,-20.35)--(1.445,1.821)--(1.459,1.837)--(2.195,2.429)--(2.194,2.428)--(1.897,1.884)--(1.897,1.883)--(1.921,1.903)--(1.972,1.945)--(1.976,1.944)--(17.881,-7.904)--(17.933,-7.942)--(23.65,-20.35);525\end{scope}526\draw[ink2] (0,0) rectangle (3.3,3.3);527\node at (1.65,-0.28) {\scriptsize two units per layer};528\begin{scope}529\clip (4.3,0) rectangle (7.6,3.3);530\draw[ink2,densely dotted] (1,1.65)--(10.9,1.65);531\draw[ink2,densely dotted] (8.425,-2.637)--(3.475,5.937);532\draw[ink2,densely dotted] (8.425,5.937)--(3.475,-2.637);533\draw[fwd,thick,fill=fwd!16] (6.585,1.65)--(6.268,2.2)--(5.632,2.2)--(5.315,1.65)--(5.632,1.1)--(6.268,1.1)--cycle;534\end{scope}535\draw[ink2] (4.3,0) rectangle (7.6,3.3);536\node at (5.95,-0.28) {\scriptsize three units, one layer};537\end{tikzpicture}538\caption{Decision regions on the square $[-3,3]^2$. Left: a network of depth three with two leaky rectifier units per layer; the positive region (shaded) is the image of a half-plane under a piecewise linear homeomorphism: it bends where units switch, and it has no holes and no end. Right: $1-\sum_i\relu(a_i\cdot x)$ with three units; the dotted lines are where the units switch, and the positive region is a bounded hexagon.}\label{fig:narrow}539\end{figure}540 541\noindent For $30$ random networks of depth four on the plane, with two leaky rectifier units per layer, two points542of the same region were joined inside it by the preimage of a segment, the preimages of rays left every543bounded set, and both classes were present on circles of radius $10$, $100$ and $1000$ times the distance of544the decision boundary from the origin. The three-unit function above is positive at the origin and at most545$-2.46$ on the circle of radius $4$ (\cref{fig:narrow}). \chk{O10} The argument uses only that the layers are546homeomorphisms: topology can change only where a layer folds, as the rectifier does, or changes dimension547\cite{NZL20}. For the rectifier itself and for other activations that are limits of injective ones a related548statement holds, with unbounded level sets \cite{Joh19}; and width $n+1$ is also the threshold for approximating549arbitrary continuous functions \cite{HaSe17}.550 551\section{Invariants}\label{sec:invariants}552 553\subsection{Hodge Laplacians}554