Indexed text attachment
parametrized-neural-networks-and-their-representations-in-differential-topology.tex
Source for Parametrized Neural Networks and Their Representations in Differential Topology
View paper · Download original file
Lines 861–960 of 2141. Source text is displayed literally.
861In the plane, then, a generic classifier has decision regions bounded by smooth arcs meeting three at a time862at isolated points, like the cells of a foam, and four regions never meet at a point.863 864\section{Chambers}865 866Let $X$ be compact, and for simplicity without boundary. Define867\[\Sigma=\{(\theta,x):F(\theta,x)=0,\ d_xF(\theta,x)=0\}\subset\Theta\times X,868\qquad\Delta=\pi(\Sigma)\subset\Theta ,\]869the set of parameters for which $0$ is not a regular value: the \term{discriminant} of the family.870 871\begin{theorem}[Chambers]\label{thm:chambers}\Srf[\DT{Lem.~4.4, Thm.~8.5, Thm.~10.3}]872Let $F$ be as in \cref{thm:boundary} with $X$ compact. Then $\Delta$ is closed and of measure zero. If873$\gamma$ is a path in $\Theta\setminus\Delta$, there is a diffeotopy $\varphi_t$ of $X$ with874$\varphi_t(B_{\gamma(0)})=B_{\gamma(t)}$. In particular the diffeomorphism type of the pair $(X,B_\theta)$ is875constant on each connected component of $\Theta\setminus\Delta$.876\end{theorem}877 878\begin{proof}879$\Sigma$ is closed and $\pi|_\Sigma$ is proper because $X$ is compact, so $\Delta$ is closed; its complement880has full measure by \cref{thm:boundary}. Over $\Theta\setminus\Delta$ the set $W=F^{-1}(0)$ is a881submanifold of $\Theta\times X$, since $d_xF\ne0$ there, and by \DT{Lem.~4.4} the projection882$W\to\Theta\setminus\Delta$ is a submersion; it is proper. By Ehresmann's theorem \DT{Thm.~8.5} it is a fibre883bundle. Pulled back along $\gamma$ it is trivial, which gives an isotopy of embeddings884$B_{\gamma(0)}\to X$ with image $B_{\gamma(t)}$ at time $t$, and the isotopy extends to a diffeotopy of $X$ by885\DT{Thm.~10.3}.886\end{proof}887 888The components of $\Theta\setminus\Delta$ are the \term{chambers} of the architecture. The theorem says that889a classifier has a well-defined topology (the number of components of its decision boundary and of its890decision regions, their genera, how they are nested) which does not change under small changes of the891parameters, and can change only when the parameter crosses $\Delta$. What happens at a crossing is the892subject of the next chapter. The symmetry group of \cref{ch:symmetry} permutes the chambers.893 894For manifolds with boundary the same holds with $\Delta$ enlarged by the parameters for which $B_\theta$ is895tangent to $\partial X$.896 897\begin{proposition}[Walls]\label{prop:walls}\Sob898Consider the one-hidden-layer architecture899$F(\theta,x)=\sum_{j\le H}a_j\sigma(\langle w_j,x\rangle+b_j)+c$ on $\R^d$ with $\sigma'>0$. At every point900where the matrix $W$ with rows $w_j$ has rank $d$, the map901$\Phi(\theta,x)=(F,d_xF)\in\R\times\R^d$ is a submersion. Hence, over the open set of such parameters,902$\Sigma$ is a submanifold of dimension $P-1$, and $\Delta$ is the image of a manifold of dimension $P-1$.903\end{proposition}904 905\begin{proof}906$d_xF=W^{\mathsf T}(a\odot\sigma'(z))$ with $z=Wx+b$. A variation $\delta a$ changes $d_xF$ by907$W^{\mathsf T}(\delta a\odot\sigma'(z))$, and $\delta a\mapsto\delta a\odot\sigma'(z)$ is a linear908isomorphism since $\sigma'>0$; so if $W^{\mathsf T}$ is onto, every variation of $d_xF$ is produced. The909resulting change in $F$ is compensated by $\delta c$.910\end{proof}911 912So the discriminant is no larger than a hypersurface, and the picture of parameter space is that of open913chambers separated by walls of codimension one. The proposition is stated for the simplest architecture;914the argument needs only that the parameters can move the value and the input-gradient of the network915independently at each point, which holds for deeper networks at parameters where the layer Jacobians have916full rank.917 918\section{Every hypersurface is a decision boundary}919 920\begin{theorem}[Realization]\label{thm:realize}\Srf[\DT{Thm.~6.2}; Hornik \cite{Hor91}]921Let $K\subset\R^d$ be a compact domain with smooth boundary and $B\subset\operatorname{int}K$ a closed922hypersurface. Let $\sigma$ be smooth, bounded and non-constant. Then for all sufficiently large $H$ there is923a non-empty open set of parameters $\theta$ of the one-hidden-layer architecture with $H$ units for which924$B_\theta\cap K$ is carried to $B$ by a diffeomorphism of $K$ isotopic to the identity.925\end{theorem}926 927\begin{proof}928A closed hypersurface in $\R^d$ separates and so has a trivial normal bundle; using a tubular neighbourhood929\DT{Thm.~6.2} one constructs a smooth $g\colon K\to\R$ with $g^{-1}(0)=B$, $0$ a regular value, and $g\ne0$ on930$\partial K$. Since $B$ is compact, there is $\varepsilon>0$ such that every $h$ with931$\|h-g\|_{C^1(K)}<\varepsilon$ has $0$ as a regular value and does not vanish on $\partial K$. By Hornik's932theorem, networks with one hidden layer are dense in $C^1(K)$, so some $f_{\theta_0}$ is within933$\varepsilon$ of $g$, and so is $f_\theta$ for $\theta$ near $\theta_0$, the realization map being continuous934into $C^1(K)$. The family $(1-s)g+sf_\theta$, $s\in[0,1]$, stays within $\varepsilon$ of $g$, and the935argument of \cref{thm:chambers} applied to it gives the diffeotopy.936\end{proof}937 938So there is no topological restriction on decision boundaries beyond those satisfied by every compact939hypersurface in $\R^d$: it is orientable, it separates, and it bounds (\cref{prop:constraints}). The theorem940is silent on how large $H$ must be. Upper bounds for the Betti numbers of decision regions in terms of the941architecture, which give lower bounds for $H$, are due to Bianchini and Scarselli \cite{BS14}.942 943\section{Piecewise-linear networks}944 945For $\sigma=\relu$ a network is piecewise linear, its decision boundary is a polyhedral complex, and the946smooth theory does not apply as it stands. The counterpart of \cref{thm:boundary} is due to Grigsby and947Lindsey \cite{GL22}. They define what it means for a $\relu$ network to be generic and transversal, in948terms of the bent hyperplane arrangement formed by the zero sets of its units, and prove that almost all949$\relu$ networks have both properties. As an application they show that for the architecture with one950hidden layer of $d+1$ units, a decision region has at most one bounded connected component: a restriction on951topology coming from the architecture, of the kind \cref{thm:realize} rules out for unbounded width.952 953\section*{Notes}954 955That decision boundaries are generically manifolds is folklore, and is usually justified by Sard's theorem956in the form (a). The statement about chambers is the standard structure theory of discriminants in957singularity theory, applied to this family. For topological complexity of decision regions see958\cite{BS14}, and for an empirical study of how networks change the topology of data, \cite{NZL20}.959 960\section*{Exercises}