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 941–1040 of 1055. Source text is displayed literally.
941\centering\small942\begin{tabular}{@{}>{\raggedright}p{0.14\textwidth}>{\raggedright}p{0.33\textwidth}>{\raggedright}p{0.36\textwidth}l@{}}943\toprule944Topic & Qualitative statement & Quantitative statement & Checks\\945\midrule946Bottleneck & no continuous injective code of $S^n$ in $\R^n$ & worst-case error $\ge1$, attained; fibre radius $1.0000$ in $100$ trials & O1--O3\\947Rotations & no continuous quaternion or Euler-angle target on a non-contractible loop; a six-dimensional one exists & jumps $2.0000$ and $3.1416$ against steps $0.004$; decoder Lipschitz constant $\le1.40$ & O4, O5\\948Meshes & no global frame field unless $\chi=0$; on spheres only for $n=1,3,7$ & index sums $2,2,0,1,0$ on five surfaces; frame on $S^3$ to $10^{-15}$ & O6, O11\\949Pieces & degree needs pieces & $N\ge2|d|+1$; windings $-2,3,3$ for $d=3$, $N=5,7,12$ & O7, O8\\950Depth & composition multiplies degree & degree $2^L$ with $4\cdot2^L$ pieces at depth $L\le6$; one layer needs more than $2^L-2$ units & O9\\951Width & $n$ units per layer cannot enclose a region; $n+1$ can & $30$ networks: both regions connected and unbounded; island value $1$ inside, $\le-2.46$ outside & O10\\952Hodge diffusion & converges to real homology; blind to torsion & kernels equal Betti numbers on six complexes; gap $1.5858$, $99$ layers & V1--V3\\953Rips complexes & higher spheres at large scales are artefacts & $n=12$ has $S^1$ for $1\le k\le3$, a wedge of three $S^2$ at $k=4$, and $S^5$ at $k=5$. Circle seen for $1.52<r<\sqrt3$ & V4--V6\\954Persistence & diagrams are stable, counts are not & distance $\le$ perturbation in $60$ trials, ratio up to $1.000$; count changed in $35$ & V7\\955Decision regions & $n+1$ regions meet & $13$--$18$ triple points; $143$--$174$ quadruple points & N1, N2\\956Sperner walk & a complete cell is found by a path & $13,25,50,97$ steps on sides $16,\dots,128$ & N3\\957Attractors & index sum $1-d$ on a circle, $0$ on a torus, $2$ on a sphere & $5,7,6,9,8$ fixed points with sums $3,1,0,-1,-2$; four zeros on the torus & N4, N5\\958Normalized outputs & degree changes only through zero & degree $1\to0$ at bias $1.2930$, norm $10^{-4}$ & N6\\959Odd networks & a zero on every origin-centred sphere in $\R^{n+1}$ for $n$ outputs & $2$ sign crossings in $193$ and $6$ in $7$ of $200$ networks. The last is positive with output bias $10$ & N7\\960\bottomrule961\end{tabular}962\caption{Qualitative statements with their quantitative counterparts. Every number is recomputed by the companion script.}\label{tab:summary}963\end{table*}964 965\Cref{tab:summary} pairs the statements. The three headings correspond to three uses of a functor. An obstruction966is a diagram that the functor forbids. An invariant is its value. A count is its value when that value is an967integer that the geometry must realize as a number of points.968 969\section{Limits}\label{sec:limits}970 971\emph{Worst case.} \Cref{thm:bottleneck,thm:rotation} bound the supremum of an error. They say nothing about the972average, and an obstruction confined to a set of small measure may be harmless in practice. What they exclude973is its absence.974 975\emph{Idealization of data.} The data are taken to be exactly a sphere, a rotation group or a circle. Real data976are samples near such a set, and a network is evaluated on finitely many points, where every map is continuous.977The theorems constrain the functions that interpolate, and through them the behaviour between samples.978 979\emph{Small exact models.} The complexes have at most a few hundred simplices, the attractors are maps of a980circle or a torus given by formulas, and the classifier is a nearest-prototype rule. No trained network was981examined.982 983\emph{Real coefficients.} \Cref{prop:torsion} concerns the limit of diffusion. A simplicial network also sees the984non-zero spectrum of its Laplacians, which can distinguish complexes with the same real homology; the statement985is about harmonic features only.986 987\emph{Hypotheses on activations.} \Cref{thm:narrow} is proved for activations that are homeomorphisms of the988line. For the rectifier the regions need not be homeomorphic to $\R^n$, and what survives is as cited.989 990\emph{Complexity.} The PPAD-completeness quoted after \cref{thm:junctions} is for fixed-point problems given by991circuits; the walk on a smooth example is short.992 993\emph{Novelty.} The theorems are classical. \Cref{thm:pieces}, \cref{prop:depth}, \cref{prop:torsion} and the994constant in \cref{thm:bottleneck} are tagged as observations or reformulations; they are elementary and may be in the995literature in other words. The second monograph of the source, on framed manifolds and the first stable stems996\cite[Ch.~8--12]{ADTHC}, has no application here beyond the rotation groups, and we have not forced one.997 998\appendix999\section{The companion script}\label{app:checks}1000 1001\texttt{verify-topology-learning.py} runs in about ten seconds and prints one line per check.1002\textbf{O1--O3} antipodal collisions of codes on the circle and the sphere, and the radius of the worst fibre;1003\textbf{O4, O5} steps of four codes for rotations along a full turn, and the Gram--Schmidt decoder;1004\textbf{O6} index sums on five triangulated surfaces;1005\textbf{O7, O8} piecewise linear functions as rectifier networks, and winding numbers of polygons;1006\textbf{O9} windings and pieces of the iterated doubling map;1007\textbf{O10} decision regions of narrow networks, and a bounded region with three units;1008\textbf{O11} the quaternion frame on the $3$-sphere;1009\textbf{V1--V3} Hodge Laplacians, coefficients, and convergence of diffusion;1010\textbf{V4--V6} Rips complexes of equally spaced and of random points on a circle;1011\textbf{V7} bottleneck distances between persistence diagrams of perturbed functions;1012\textbf{N1, N2} junctions of nearest-prototype classifiers in dimensions two and three;1013\textbf{N3} the length of the Sperner walk;1014\textbf{N4, N5} fixed points of circle maps and zeros of fields on a torus;1015\textbf{N6} the degree of a small network and the bias at which it changes;1016\textbf{N7} zeros of odd networks on a circle.1017Homology is computed exactly, by Smith normal form over the integers and Gaussian elimination over prime1018fields, with the library of the companion volume. Random inputs use fixed seeds. The figures were drawn1019by a separate plotting script from the same formulas and are embedded in the source as coordinates.1020 1021\begin{thebibliography}{DFdC$^{+}$18}\footnotesize\setlength{\itemsep}{0.5pt}1022\newcommand{\bi}[1]{\bibitem[#1]{#1}}1023\bi{ABMM18} R.~Arora, A.~Basu, P.~Mianjy, A.~Mukherjee, Understanding deep neural networks with rectified linear units, \emph{Proc.\ ICLR} 2018.1024\bi{Ada13} M.~Adamaszek, Clique complexes and graph powers, \emph{Israel J.~Math.} 196 (2013), 295--319.1025\bi{AdAd17} M.~Adamaszek, H.~Adams, The Vietoris--Rips complexes of a circle, \emph{Pacific J.~Math.} 290 (2017), 1--40. Checked.1026\bi{ADTHC} Anonymous, \emph{Algebraic and Differential Topology in Higher Categories}, Higher Categorical Semantics, 2026. Companion volume.1027\bi{Ban67} T.~Banchoff, Critical points and curvature for embedded polyhedra, \emph{J.~Differential Geom.} 1 (1967), 245--256.1028\bi{BBS95} R.~Ben-Yishai, R.~L.~Bar-Or, H.~Sompolinsky, Theory of orientation tuning in visual cortex, \emph{Proc.\ Nat.\ Acad.\ Sci.\ U.S.A.} 92 (1995), 3844--3848.1029\bibitem[BFW$^{+}$21]{BFW21} C.~Bodnar, F.~Frasca, Y.~Wang, N.~Otter, G.~Mont\'ufar, P.~Li\`o, M.~Bronstein, Weisfeiler and Lehman go topological: message passing simplicial networks, \emph{Proc.\ ICML} 2021.1030\bi{BKK19} S.~Bai, J.~Z.~Kolter, V.~Koltun, Deep equilibrium models, \emph{Adv.\ Neural Inf.\ Process.\ Syst.} 32 (2019).1031\bi{Car09} G.~Carlsson, Topology and data, \emph{Bull.\ Amer.\ Math.\ Soc.} 46 (2009), 255--308.1032\bi{CEH07} D.~Cohen-Steiner, H.~Edelsbrunner, J.~Harer, Stability of persistence diagrams, \emph{Discrete Comput.\ Geom.} 37 (2007), 103--120.1033\bi{CWKW19} T.~Cohen, M.~Weiler, B.~Kicanaoglu, M.~Welling, Gauge equivariant convolutional networks and the icosahedral CNN, \emph{Proc.\ ICML} 2019.1034\bibitem[DFdC$^{+}$18]{DFdC18} T.~R.~Davidson, L.~Falorsi, N.~De~Cao, T.~Kipf, J.~M.~Tomczak, Hyperspherical variational auto-encoders, \emph{Proc.\ UAI} 2018.1035\bi{DGP09} C.~Daskalakis, P.~W.~Goldberg, C.~H.~Papadimitriou, The complexity of computing a Nash equilibrium, \emph{SIAM J.~Comput.} 39 (2009), 195--259.1036\bi{Eck44} B.~Eckmann, Harmonische Funktionen und Randwertaufgaben in einem Komplex, \emph{Comment.\ Math.\ Helv.} 17 (1944), 240--255.1037\bi{EdHa10} H.~Edelsbrunner, J.~Harer, \emph{Computational Topology: An Introduction}, American Mathematical Society, 2010.1038\bi{EDS20} S.~Ebli, M.~Defferrard, G.~Spreemann, Simplicial neural networks, NeurIPS Workshop on Topological Data Analysis and Beyond, 2020.1039\bibitem[FdH$^{+}$18]{FdH18} L.~Falorsi, P.~de~Haan, T.~R.~Davidson, N.~De~Cao, M.~Weiler, P.~Forr\'e, T.~S.~Cohen, Explorations in homeomorphic variational auto-encoding, ICML Workshop on Theoretical Foundations and Applications of Deep Generative Models, 2018.1040\bibitem[GHP$^{+}$22]{GHP22} R.~J.~Gardner, E.~Hermansen, M.~Pachitariu, Y.~Burak, N.~A.~Baas, B.~A.~Dunn, M.-B.~Moser, E.~I.~Moser, Toroidal topology of population activity in grid cells, \emph{Nature} 602 (2022), 123--128.