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 1441–1540 of 2141. Source text is displayed literally.
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)$.1481\end{corollary}1482 1483\begin{proof}1484Take $e_0$ the inclusion of $K$ in $\R^d\times\{0\}\subset\R^N$ and $e_1=e_0\pm(0,\dots,0,1)$ on $K_\pm$, and1485apply \cref{thm:augment} to get a field $v$ with flow $\varphi$. For the last statement, approximate $v$ in1486$C^1$ on a compact set containing the support, by Hornik's theorem \cite{Hor91}; by Gr\"onwall's inequality1487the time-one maps are then close in $C^1$ on compact sets, and the conclusion, being an open condition on1488the images of the compact sets $K_\pm$, persists.1489\end{proof}1490 1491So the obstructions of \cref{cor:nodeobst} disappear once the state space has dimension at least $2m+2$,1492where $m$ is the dimension of the data and not of the ambient space. For finite data sets $m=0$ and two1493dimensions suffice, in agreement with (a): points on a line cannot be reordered by a flow, points in the1494plane can. For curves the bound is $4$, and it is sharp, since circles link in $\R^3$. For connected data1495of dimension $m\ge2$ the bound can be lowered to $2m+1$ by the second part of \DT{Thm.~10.9}. Zhang et al.\1496\cite{ZGUA20} prove a related statement about maps: every homeomorphism of $\R^d$ can be embedded in a flow on1497$\R^{2d}$, and hence approximated by a neural ODE or an invertible residual network acting there. The dimension count of \cref{thm:augment}1498depends on the data alone.1499 1500Residual networks fit the same description. A block $x\mapsto x+g(x)$ with $g$ of Lipschitz constant less1501than one is a diffeomorphism isotopic to the identity (\cref{prop:iresnet}), and a composite of such blocks1502is a discretized isotopy. Depth, for such architectures, is time.1503 1504\section{The space of representations}1505 1506\begin{problem}\label{prob:calculus}\Spg1507For a compact data manifold $K$ of dimension $m$ and width $k\ge m+3$, the space $\Emb(K,\R^k)$ of1508representations that preserve the topology of the data is described by manifold calculus1509\DT{Thm.~10.10}: it is the limit of a tower whose first stage is the space of immersions and whose higher1510stages are built from configuration spaces of $K$. Determine which components and which homotopy classes of1511this space are reached by the realization map of a given architecture, as a function of width and depth.1512\end{problem}1513 1514For $k\ge2m+2$ the space is connected and the question is about higher homotopy; in the range1515$m+3\le k\le2m+1$ already the set of components is interesting, and \cref{cor:nodeobst}(c) is the first1516example outside that range.1517 1518\section*{Notes}1519 1520The picture of a network as progressively untangling data manifolds goes back at least to expository1521writing of Olah in 2014, where \cref{thm:obstruction} for $d=2$ and the role of an extra dimension are1522described. Minimal width for universal approximation is treated in \cite{HS17,Joh19}. Neural ODEs are from1523\cite{CRBD18}, their limitations and augmentation from \cite{DDT19}, and approximation properties from1524\cite{ZGUA20}.1525 1526\section*{Exercises}1527 1528\begin{exercise}\label{exer:monotone}1529Show that the time-one map of a bounded smooth vector field on $\R$ is increasing.1530\end{exercise}1531 1532\begin{exercise}\label{exer:swap}1533Write down a compactly supported vector field on $\R^2$ whose time-one map exchanges the points $(\pm1,0)$.1534\end{exercise}1535 1536\begin{exercise}\label{exer:link}1537Show that the linking number of two disjoint closed curves in $\R^3$ is unchanged when both are moved by a1538diffeomorphism isotopic to the identity.1539\end{exercise}1540