Independent scholarship · Open accessThe monthly digest

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 841–940 of 2141. Source text is displayed literally.

841 842\section{Several classes}843 844A classifier with $k$ classes is a map $f_\theta\colon X\to\R^k$, and the predicted class is the index of the845largest coordinate. For a non-empty $I\subset\{1,\dots,k\}$ let $A_I\subset\R^k$ be the set of points whose846largest coordinate is attained exactly on $I$. Then $A_I$ is an open subset of the linear subspace847$\{y_i=y_j:i,j\in I\}$, a submanifold of codimension $|I|-1$, and the $A_I$ partition $\R^k$.848 849\begin{proposition}\label{prop:multiclass}\Srf[\DT{Thm.~4.5}]850Let $F\colon\Theta\times X\to\R^k$ be a family whose last layer is affine with a bias. For almost every851$\theta$, $f_\theta$ is transverse to every $A_I$. Then the decision region of class $i$ is the open set852$f_\theta^{-1}(A_{\{i\}})$; the set where exactly the classes in $I$ tie is a submanifold of codimension853$|I|-1$; and no more than $d+1$ classes tie anywhere.854\end{proposition}855 856\begin{proof}857$F$ is a submersion, so \DT{Thm.~4.5} applies to each of the finitely many $A_I$, and a finite intersection858of sets of full measure has full measure. A submanifold of codimension greater than $d$ is empty.859\end{proof}860 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 the