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

941architecture, 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}981%% ---- end ch/04-decision.tex ----982%% ---- begin ch/05-paths.tex ----983\chapter{Topology Change along Paths: Surgery and Cobordism}\label{ch:paths}984 985By \cref{thm:chambers} the topology of a decision boundary can change during training only when the986parameter crosses the discriminant. This chapter answers question (Q2): for a generic path the crossings987are isolated, and at each of them the boundary changes by one surgery, determined by the index of a988critical point. The union of the boundaries along the path is a cobordism, and the surgeries are the989critical points of its height function. This is the Morse theory of \DT{Ch.~8} applied to a manifold that the990path itself creates.991 992\section{The trace of a path}993 994Let $F\colon\Theta\times X\to\R$ be a family as in \cref{thm:boundary}, with $X$ compact of dimension $d$, and995let $\gamma\colon[0,1]\to\Theta$ be a path. Write $f_t=f_{\gamma(t)}$ and $B_t=f_t^{-1}(0)$, and define996\[\Phi_\gamma\colon[0,1]\times X\to\R,\quad\Phi_\gamma(t,x)=F(\gamma(t),x);\qquad997W_\gamma=\Phi_\gamma^{-1}(0)\subset[0,1]\times X .\]998 999\begin{theorem}[The trace is a cobordism]\label{thm:trace}\Srf[\DT{Thm.~1.17, Thm.~4.5}]1000If $0$ is a regular value of $\Phi_\gamma$ and of $f_0$ and $f_1$, then $W_\gamma$ is a compact neat1001hypersurface in $[0,1]\times X$ with $\partial W_\gamma=B_0\sqcup B_1$: a cobordism from $B_0$ to $B_1$1002embedded in $[0,1]\times X$. For a path with endpoints outside $\Delta$, this holds after an arbitrarily1003small perturbation of the bias component of $\gamma$ fixed at the endpoints.1004\end{theorem}1005 1006\begin{proof}1007The first statement is \DT{Thm.~1.17}. For the second, replace the bias component $c(t)$ by1008$c(t)+s\,\beta(t)$ with $\beta>0$ on $(0,1)$ and vanishing with all derivatives at the ends. The map1009$(s,t,x)\mapsto\Phi_\gamma(t,x)+s\beta(t)$ is a submersion on $\{0<t<1\}$, so by \DT{Thm.~4.5} zero is a1010regular value for almost every $s$; near $t=0,1$ it is one already because $f_0,f_1$ have $0$ as a1011regular value.1012\end{proof}1013 1014The times at which $\gamma$ meets $\Delta$ are, by \DT{Lem.~4.4}, exactly the critical values of the height1015function $\tau\colon W_\gamma\to[0,1]$, $\tau(t,x)=t$. At such a point $(t_0,x_0)$ we have $d_xf_{t_0}(x_0)=0$:1016$x_0$ is a critical point of $f_{t_0}$ with critical value $0$.1017 1018\section{Surgery}1019 1020\begin{theorem}[One surgery at a time]\label{thm:surgery}\Srf[\DT{Thm.~8.6, Cor.~8.7}]1021Let $\gamma$ be a path for which $W_\gamma$ is a manifold and $\tau$ is a Morse function with distinct1022critical values $t_1<\dots<t_r$ in $(0,1)$. Then:1023\begin{enumerate}[label=(\alph*)]1024\item On each interval of $[0,1]\setminus\{t_1,\dots,t_r\}$ the boundary $B_t$ moves by an ambient isotopy of1025$X$.1026\item At each $t_i$ there is exactly one point $x_i\in B_{t_i}$ at which $B_{t_i}$ fails to be a manifold. It1027is a non-degenerate critical point of $f_{t_i}$ with $\partial_t\Phi_\gamma(t_i,x_i)\ne0$, and near1028$(t_i,x_i)$ there are coordinates on $X$ in which1029\[\Phi_\gamma(t,x)=\pm(t-t_i)-x_1^2-\dots-x_k^2+x_{k+1}^2+\dots+x_d^2 ,\]1030with $k$ the index of $x_i$ as a critical point of $f_{t_i}$.1031\item $B_{t_i+\varepsilon}$ is obtained from $B_{t_i-\varepsilon}$ by a surgery: a copy of1032$S^{\lambda-1}\times D^{d-\lambda}$ is removed and $D^\lambda\times S^{d-\lambda-1}$ is glued in, where1033$\lambda$ is the index of $\tau$ at $(t_i,x_i)$; $\lambda=k$ or $d-k$ according to the sign in (b).1034Correspondingly the region $\{f_t\le0\}$ gains or loses a handle of index $k$.1035\end{enumerate}1036\end{theorem}1037 1038\begin{proof}1039(a) is \cref{thm:chambers}. For (b): at a critical point of $\tau$ on $W_\gamma$ the tangent space of1040$W_\gamma$ is $\{dt=0\}$, so $d_x\Phi_\gamma=0$ and, $W_\gamma$ being a manifold, $\partial_t\Phi_\gamma\ne0$.