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 881–980 of 2141. Source text is displayed literally.
881submanifold 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}961 962\begin{exercise}\label{exer:d1}963Let $d=1$ and $X=[-R,R]$. Show that for almost every $\theta$ the decision boundary is a finite set at which964$f_\theta$ changes sign, and that the parity of its cardinality is determined by the signs of965$f_\theta(\pm R)$.966\end{exercise}967 968\begin{exercise}\label{exer:plane}969Let $X$ be a closed disc in the plane. Describe the generic decision boundary up to diffeomorphism.970\end{exercise}971 972\begin{exercise}\label{exer:crossex}973For the family $F(c,x)=x_1^2-x_2^2+c$ on the plane, determine $\Sigma$ and $\Delta$, and describe the974chambers.975\end{exercise}976 977\begin{exercise}\label{exer:triple}978For a three-class classifier in the plane satisfying the conclusion of \cref{prop:multiclass}, show that979near a point where all three classes tie the decision regions look like three sectors meeting at a point.980\end{exercise}