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

1341 1342\begin{exercise}\label{exer:linreg}1343For the linear family of \cref{exer:linear} with $P>n$ and features in general position, describe $M_y$ and1344the Hessian of the loss.1345\end{exercise}1346 1347\begin{exercise}\label{exer:hyperbola}1348Verify \cref{ex:hyperbola}: find all critical points of $\tfrac12(ab-1)^2$, their Hessians, and the1349components of the sublevel sets.1350\end{exercise}1351 1352\begin{exercise}\label{exer:PL}1353In the setting of \cref{prop:PL}, show that the limit point of the flow line lies within1354$\sqrt{2\loss(\theta_0)/\mu}$ of $\theta_0$.1355\end{exercise}1356 1357\begin{exercise}\label{exer:deeplin}1358For $F(a_1,\dots,a_k;x)=a_1\cdots a_kx$ with data $(1,1)$, show that $M_y$ has $2^{k-1}$ components and1359dimension $k-1$, and that the origin is a degenerate critical point for $k\ge3$.1360\end{exercise}1361%% ---- end ch/06-loss.tex ----1362\part{Maps}1363%% ---- begin ch/07-isotopy.tex ----1364\chapter{Embeddings, Isotopy, and Depth}\label{ch:isotopy}1365 1366The previous three chapters studied level sets. This one studies the maps themselves, and in particular1367what a network does to a data set regarded as a subset of input space. The standing assumption, usually1368called the manifold hypothesis \cite{FMN16}, is that the data lie on or near a compact submanifold1369$K\subset\R^D$ of dimension $m$ much smaller than $D$, with the classes occupying disjoint closed subsets1370$K_+,K_-$. A hidden layer of width $k$ is a map $h_\theta\colon\R^D\to\R^k$, and the question is what1371$h_\theta(K)$ can be.1372 1373\section{The first layer generically embeds}1374 1375\begin{proposition}\label{prop:firstlayer}\Srf[Whitney; \DT{Thm.~4.5, Cor.~4.8, Prop.~3.12}]1376Let $K\subset\R^D$ be a compact submanifold of dimension $m$, let $k\ge2m+1$, and let $\sigma$ be a1377diffeomorphism of $\R$ onto an open interval. Then for almost every $W\in\R^{k\times D}$ and every $b$, the1378map $x\mapsto\sigma(Wx+b)$ restricted to $K$ is an embedding. The set of such $(W,b)$ is open.1379\end{proposition}1380 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