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 1381–1480 of 2141. Source text is displayed literally.
1381\begin{proof}1382Applying $\sigma$ coordinatewise after a translation is a diffeomorphism onto its image, so the question is1383whether $W|_K$ is an embedding. The map $(W,(x,y))\mapsto W(x-y)$ on1384$\R^{k\times D}\times(K\times K\setminus\Delta)$ is a submersion to $\R^k$, so by \DT{Thm.~4.5} for almost1385every $W$ its restriction to $K\times K\setminus\Delta$, a manifold of dimension $2m<k$, is transverse to1386$0$ and hence misses it: $W|_K$ is injective. Likewise $(W,(x,v))\mapsto Wv$ on the unit tangent bundle of1387$K$, of dimension $2m-1$, is a submersion, so for almost every $W$ no unit tangent vector is killed: $W|_K$ is1388an immersion. An injective immersion of a compact manifold is an embedding. Openness is \DT{Prop.~3.12}.1389\end{proof}1390 1391So a hidden layer wider than twice the intrinsic dimension of the data loses no topological information for1392almost every choice of weights, however small it is compared with the ambient dimension $D$. This is1393Whitney's embedding theorem read as a statement about random projections. Narrower layers may fail to be1394injective on $K$, and that is where the topology of a representation can change.1395 1396\section{What injective networks cannot do}1397 1398A classifier ends with a linear map, so the last hidden representation must make the classes linearly1399separable. If the network up to that point is injective, its restriction to $K$ is a homeomorphism onto1400the image, and separability becomes a constraint on how $K_+$ and $K_-$ sit in the ambient space.1401 1402\begin{theorem}[Nested classes]\label{thm:obstruction}\Scl[invariance of domain; cf.\ \cite{Joh19}]1403Let $h\colon\R^d\to\R^d$ be continuous and injective, let $\beta\subset\R^d$ be a closed topological ball with1404boundary sphere $S$, and let $p$ be an interior point of $\beta$. Then $h(p)$ lies in the convex hull of1405$h(S)$. In particular no hyperplane separates $h(p)$ from $h(S)$.1406\end{theorem}1407 1408\begin{proof}1409Suppose a linear functional $\lambda$ satisfies $\lambda>0$ on $h(S)$ and $\lambda(h(p))\le0$. Let $q$ be a1410point of the compact set $h(\beta)$ at which $\lambda$ is smallest. Then $\lambda(q)\le0$, so $q\notin h(S)$1411and $q\in h(\operatorname{int}\beta)$, which is open in $\R^d$ by invariance of domain. But a linear1412functional has no local minimum on an open set.1413\end{proof}1414 1415\begin{corollary}\label{cor:width}\Scl[\cite{Joh19,HS17}]1416A feedforward network on $\R^d$ in which every hidden layer has width $d$, every weight matrix is1417invertible, and the activation is injective, cannot separate a point from a sphere surrounding it. To do so1418a network must either have a layer of width at least $d+1$ or use a layer that is not injective.1419\end{corollary}1420 1421Both escapes are used in practice. A wider layer provides the extra dimension into which the inner class can1422be lifted. A $\relu$ layer is not injective: it folds space along hyperplanes, and a network of $\relu$1423layers can map a nested data set to a separable one by collapsing. Naitzat, Zhitnikov and Lim \cite{NZL20}1424measured the Betti numbers of the two classes layer by layer and found that well-trained networks reduce1425them steadily, faster with $\relu$ than with smooth invertible activations. In the terms of this chapter:1426smooth invertible layers of constant width act by diffeomorphisms and cannot change topology, and the1427network must then rely on the few layers where injectivity fails.1428 1429\section{Neural ordinary differential equations}1430 1431A \term{neural ODE} \cite{CRBD18} is the time-$T$ map $\varphi_\theta$ of the equation1432$\dot x=v_\theta(x,t)$, where $v_\theta$ is a network with input $(x,t)$ and output in $\R^d$.1433 1434\begin{proposition}\label{prop:node}\Srf[\DT{Thm.~10.2}]1435If $v_\theta$ is smooth with bounded velocity, as it is when its last hidden layer has a bounded activation,1436then $t\mapsto\varphi^t_\theta$ is a diffeotopy of $\R^d$. Hence $\varphi_\theta$ is a diffeomorphism isotopic1437to the identity, it preserves orientation, and for every compact $K\subset\R^d$ the image $\varphi_\theta(K)$1438is ambient isotopic to $K$.1439\end{proposition}1440 1441\begin{corollary}[Obstructions]\label{cor:nodeobst}\Scl[cf.\ Dupont--Doucet--Teh \cite{DDT19}]1442A neural ODE on $\R^d$ cannot:1443\begin{enumerate}[label=(\alph*)]1444\item for $d=1$, reverse the order of two points;1445\item map a sphere and a point inside it to linearly separable sets (\cref{thm:obstruction});1446\item for $d=3$, map two linked circles to unlinked ones, or a knotted circle to a round one.1447\end{enumerate}1448\end{corollary}1449 1450\begin{proof}1451(a) A diffeomorphism of $\R$ isotopic to the identity is increasing. (c) The linking number is the degree of1452the Gauss map \DT{Ex.~7.12} and is invariant under isotopy by \DT{Thm.~7.2}; the knot type is an isotopy1453invariant by definition.1454\end{proof}1455 1456These are statements about exact representation. A neural ODE can still approximate a map that violates1457them, at the cost of a vector field with large derivatives, and \cite{DDT19} observed that training then1458becomes slow and unstable. Their remedy was to append extra coordinates to the state.1459 1460\section{Augmentation}1461 1462\begin{theorem}[Flows in the stable range]\label{thm:augment}1463\Srf[\DT{Thm.~10.9, Thm.~10.3, Thm.~10.2}]1464Let $K$ be a compact manifold of dimension $m$ and let $e_0,e_1\colon K\to\R^N$ be embeddings, with1465$N\ge2m+2$. Then there is a smooth, compactly supported, time-dependent vector field on $\R^N$ whose1466time-one map $\varphi$ satisfies $\varphi\circ e_0=e_1$.1467\end{theorem}1468 1469\begin{proof}1470By \DT{Thm.~10.9} the two embeddings are isotopic. By the isotopy extension theorem \DT{Thm.~10.3} the1471isotopy is induced by a diffeotopy of $\R^N$ with compact support, and by \DT{Thm.~10.2} the diffeotopy is1472the flow of its velocity field.1473\end{proof}1474 1475\begin{corollary}[Separation after augmentation]\label{cor:separate}\Sob1476Let $K=K_+\sqcup K_-\subset\R^d$ be a compact submanifold of dimension $m$, the union of two disjoint compact1477submanifolds, and let $N\ge\max(d+1,2m+2)$. Then there is a compactly supported flow on $\R^N$ whose1478time-one map carries $K_+\times\{0\}$ and $K_-\times\{0\}$ into the open half-spaces $\{x_N>0\}$ and1479$\{x_N<0\}$. The vector field may be taken to be a neural network with one hidden layer and input1480$(x,t)$.