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 521–620 of 1055. Source text is displayed literally.
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 manifold601\cite{NSW08}. For large $r$ it does not, and what it produces instead is known for the circle.602 603\begin{theorem}[Rips complexes of a circle]\label{thm:rips}604\Sli[\cite{Ada13,AdAd17}] As the scale increases, the Vietoris--Rips complex of the circle has the homotopy type of605$S^1$, then $S^3$, then $S^5$, and so on, the type $S^{2l+1}$ occurring for scales between $\frac l{2l+1}$ and606$\frac{l+1}{2l+3}$ of a turn, until it is contractible. For $n$ equally spaced points and scale $k$ steps the same607holds with $k/n$ in place of the scale, and at the transition $k/n=\frac l{2l+1}$ the complex is a wedge of608$n-2k-1$ spheres of dimension $2l$.609\end{theorem}610 611\begin{figure}[t]612\centering613\begin{tikzpicture}614\draw[ink2,very thin,fill=fwd!22] (1,0) rectangle (1.92,0.42);615\node at (1.46,0.21) {\scriptsize $1$};616\draw[ink2,very thin,fill=fwd!22] (1,0.42) rectangle (1.92,0.84);617\node at (1.46,0.63) {\scriptsize $1$};618\draw[ink2,very thin,fill=white] (1,0.84) rectangle (1.92,1.26);619\draw[ink2,very thin,fill=white] (1,1.26) rectangle (1.92,1.68);620\draw[ink2,very thin,fill=white] (1,1.68) rectangle (1.92,2.1);