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

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$.1041Solving $\Phi_\gamma=0$ for $t$ as a function of $x$ near the point exhibits $W_\gamma$ as a graph over $X$1042on which $\tau$ is the function $t(x)$, whose Hessian at $x_i$ is1043$-\nabla^2f_{t_i}(x_i)/\partial_t\Phi_\gamma$. So $\tau$ is non-degenerate there exactly when $x_i$ is a1044non-degenerate critical point of $f_{t_i}$, and the normal form follows from the Morse lemma with parameters.1045(c) is \DT{Thm.~8.6} for $\tau$ on $W_\gamma$: the level sets of $\tau$ are the $B_t$, and passing a critical1046point of index $\lambda$ changes the level set by the stated surgery.1047\end{proof}1048 1049In words: the topology of a decision boundary changes exactly when a critical point of the network function1050crosses the threshold, and the change is read off from the index of the critical point and the direction of1051crossing. \Cref{tab:surgery} lists the cases for inputs of dimension two and three.1052 1053\begin{table}[ht]\centering\small1054\begin{tabular}{@{}llp{0.58\textwidth}@{}}1055\toprule1056$d$ & index $k$ of $x_i$ & effect on the region $\{f_t\le0\}$ when the critical value becomes negative\\1057\midrule1058$2$ & $0$ (minimum) & a new disc appears; the boundary gains a circle\\1059$2$ & $1$ (saddle) & two parts of the region join, or one part meets itself; two boundary arcs1060reconnect, so the number of boundary circles changes by $\pm1$\\1061$2$ & $2$ (maximum) & a hole in the region is filled; a boundary circle disappears\\1062$3$ & $0$ & a new ball appears; the boundary gains a sphere\\1063$3$ & $1$ & a tube joins two parts of the region, or adds a handle to one\\1064$3$ & $2$ & a tunnel through the region is closed by a disc, or a cavity is split in two\\1065$3$ & $3$ & a cavity is filled; a boundary sphere disappears\\1066\bottomrule1067\end{tabular}1068\caption{Elementary changes of topology of a decision region, by the index of the critical point crossing1069zero from above. Crossing in the other direction reverses each.}\label{tab:surgery}1070\end{table}1071 1072\begin{proposition}\label{prop:chi}\Sob1073In the situation of \cref{thm:surgery}(c), $\chi(B_{t_i+\varepsilon})-\chi(B_{t_i-\varepsilon})$ equals1074$2(-1)^\lambda$ if $d$ is odd and $0$ if $d$ is even, and the Euler characteristic of the region1075$\{f_t\le0\}$ changes by $\pm(-1)^k$.1076\end{proposition}1077 1078\begin{proof}1079The change is $\chi(D^\lambda\times S^{d-\lambda-1})-\chi(S^{\lambda-1}\times D^{d-\lambda})1080=\chi(S^{d-\lambda-1})-\chi(S^{\lambda-1})=(-1)^{d-\lambda-1}-(-1)^{\lambda-1}$. The second statement is