Indexed text attachment
algebraic-and-differential-topology-in-machine-learning-and-ai.tex
Source for Algebraic and Differential Topology in Machine Learning and AI: Obstructions, Invariants, and Counts
View paper · Download original file
Lines 501–600 of 1055. Source text is displayed literally.
501\subsection{Width}502 503\begin{theorem}[Narrow networks]\label{thm:narrow}504\Sli[\cite{Joh19,HaSe17}] Let $f\colon\R^n\to\R$ be a network whose hidden layers all have $n$ units, with invertible505weight matrices, a non-zero output layer, and an activation that is continuous, strictly increasing and onto506$\R$, such as the leaky rectifier. Then each decision region $\{f>0\}$, $\{f<0\}$ is homeomorphic to $\R^n$ and unbounded. In particular507$f$ cannot separate a bounded class from a class that surrounds it. With one hidden layer of $n+1$ rectifier508units a bounded decision region exists.509\end{theorem}510\begin{proof}511Each hidden layer is a homeomorphism of $\R^n$, so their composite $h$ is one, and $\{f>0\}=h^{-1}(H)$ for an512open half-space $H$. If it were bounded its closure would be compact, and so would the image of the closure513under $h$, which contains $H$. For the last statement let $a_0,\dots,a_n$ be the vertices of a regular simplex centred at the514origin and $f(x)=1-\sum_i\relu(a_i\cdot x)$. Every $x\ne0$ has $a_i\cdot x>0$ for some $i$, and by compactness515$\sum_i\relu(a_i\cdot x)\ge c|x|$ with $c>0$; so $\{f>0\}$ is bounded, and it contains the origin.516\end{proof}517 518\begin{figure}[t]519\centering520\begin{tikzpicture}521\begin{scope}522\clip (0,0) rectangle (3.3,3.3);523\fill[fwd!16] (-20.35,-20.35)--(1.445,1.821)--(1.459,1.837)--(2.195,2.429)--(2.194,2.428)--(1.897,1.884)--(1.897,1.883)--(1.921,1.903)--(1.972,1.945)--(1.976,1.944)--(17.881,-7.904)--(17.933,-7.942)--(23.65,-20.35)--(23.65,-20.35)--(23.65,-20.35)--(23.65,-20.35)--(23.65,-20.35)--(23.65,-20.35)--(23.65,-20.35)--(23.65,-20.35)--(23.65,-20.35)--(23.65,-20.35)--(23.65,-20.35)--(23.65,-20.35)--(23.65,-20.35)--(23.65,-20.35)--(23.65,-20.35)--(23.65,-20.35)--(23.65,-20.35)--(23.65,-20.35)--(23.65,-20.35)--(23.65,-20.35)--(23.65,-20.35)--(23.65,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--(-20.35,-20.35)--cycle;524\draw[fwd,thick] (-20.35,-20.35)--(1.445,1.821)--(1.459,1.837)--(2.195,2.429)--(2.194,2.428)--(1.897,1.884)--(1.897,1.883)--(1.921,1.903)--(1.972,1.945)--(1.976,1.944)--(17.881,-7.904)--(17.933,-7.942)--(23.65,-20.35);525\end{scope}526\draw[ink2] (0,0) rectangle (3.3,3.3);527\node at (1.65,-0.28) {\scriptsize two units per layer};528\begin{scope}529\clip (4.3,0) rectangle (7.6,3.3);530\draw[ink2,densely dotted] (1,1.65)--(10.9,1.65);531\draw[ink2,densely dotted] (8.425,-2.637)--(3.475,5.937);532\draw[ink2,densely dotted] (8.425,5.937)--(3.475,-2.637);533\draw[fwd,thick,fill=fwd!16] (6.585,1.65)--(6.268,2.2)--(5.632,2.2)--(5.315,1.65)--(5.632,1.1)--(6.268,1.1)--cycle;534\end{scope}535\draw[ink2] (4.3,0) rectangle (7.6,3.3);536\node at (5.95,-0.28) {\scriptsize three units, one layer};537\end{tikzpicture}538\caption{Decision regions on the square $[-3,3]^2$. Left: a network of depth three with two leaky rectifier units per layer; the positive region (shaded) is the image of a half-plane under a piecewise linear homeomorphism: it bends where units switch, and it has no holes and no end. Right: $1-\sum_i\relu(a_i\cdot x)$ with three units; the dotted lines are where the units switch, and the positive region is a bounded hexagon.}\label{fig:narrow}539\end{figure}540 541\noindent For $30$ random networks of depth four on the plane, with two leaky rectifier units per layer, two points542of the same region were joined inside it by the preimage of a segment, the preimages of rays left every543bounded set, and both classes were present on circles of radius $10$, $100$ and $1000$ times the distance of544the decision boundary from the origin. The three-unit function above is positive at the origin and at most545$-2.46$ on the circle of radius $4$ (\cref{fig:narrow}). \chk{O10} The argument uses only that the layers are546homeomorphisms: topology can change only where a layer folds, as the rectifier does, or changes dimension547\cite{NZL20}. For the rectifier itself and for other activations that are limits of injective ones a related548statement holds, with unbounded level sets \cite{Joh19}; and width $n+1$ is also the threshold for approximating549arbitrary continuous functions \cite{HaSe17}.550 551\section{Invariants}\label{sec:invariants}552 553\subsection{Hodge Laplacians}554 555Let $K$ be a simplicial complex with boundary matrices $\pd_k$. The \term{Hodge Laplacian} on $k$-chains is556$L_k=\pd_k^{\T}\pd_k+\pd_{k+1}\pd_{k+1}^{\T}$; for $k=0$ it is the graph Laplacian. Networks on complexes pass557messages along $\pd_k$ and $\pd_{k+1}^{\T}$ \cite{EDS20,BFW21}.558 559\begin{theorem}[Hodge]\label{thm:hodge}560\Scl[\cite{Eck44,Lim20}] \emph{(a)} $\ker L_k\cong H_k(K;\R)$. \emph{(b)} The iteration $X\mapsto X-\tau L_kX$ with561$0<\tau\le1/\lambda_{\max}$ converges to the orthogonal projection of $X$ on $\ker L_k$, the error contracting by562$1-\tau\lambda_{\min}^+$ per layer, where $\lambda_{\min}^+$ is the smallest non-zero eigenvalue.563\end{theorem}564 565\noindent The kernels have dimensions $(1,0,1)$, $(1,2,1)$, $(1,0,0)$, $(1,1,0)$, $(1,1,0)$, $(1,0,0)$ for the566sphere, torus, projective plane, Klein bottle, M\"obius band and disc, which are the Betti numbers computed567independently by Smith normal form. \chk{V1} On the edges of the seven-vertex torus $\lambda_{\min}^+=1.5858$ and568$\lambda_{\max}=7$; after $99$ layers four random inputs have converged to $10^{-11}$, and their limits span a569space of dimension $2$. \chk{V3} Statement (b) is the oversmoothing of graph networks one dimension up, with a570difference: the limit is not a constant but a harmonic form, and it carries exactly the homology.571 572\begin{proposition}[Coefficients are a choice of what is visible]\label{prop:torsion}573\Sob The limit in \cref{thm:hodge}\emph{(b)} depends only on the real homology of $K$. The projective plane and574the disc have the same harmonic spaces in every degree, although $H_1$ of the projective plane is $\Z/2$. Over575the field $\Fp_2$ the Betti numbers are $(1,1,1)$ and $(1,0,0)$. Conversely the Klein bottle and the torus agree576over $\Fp_2$, with $(1,2,1)$, and differ over $\R$.577\end{proposition}578 579\noindent The Betti numbers quoted are recomputed by the script. \chk{V2} Integral homology sees both distinctions at once and is computed by integer row and column580operations \cite[Ch.~2]{ADTHC}, which are not differentiable. An architecture built from real boundary matrices581has made the choice of the first column of the table below.582 583\begin{center}\small584\begin{tabular}{lccc}585\toprule586 & over $\R$ & over $\Fp_2$ & over $\Z$\\587\midrule588disc & $1,0,0$ & $1,0,0$ & $\Z,0,0$\\589projective plane & $1,0,0$ & $1,1,1$ & $\Z,\Z/2,0$\\590torus & $1,2,1$ & $1,2,1$ & $\Z,\Z^2,\Z$\\591Klein bottle & $1,1,0$ & $1,2,1$ & $\Z,\Z\oplus\Z/2,0$\\592\bottomrule593\end{tabular}594\end{center}595 596\subsection{Complexes built from samples}597 598Topological data analysis replaces a point cloud by the \term{Vietoris--Rips complex} at scale $r$, whose599simplices are the sets of points of diameter at most $r$, and reads off homology as $r$ varies600\cite{Car09,EdHa10}. For small $r$ and dense samples this recovers the homology of the underlying manifold