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 675–774 of 1055. Source text is displayed literally.
675\draw[ink2] (4.22,2.97)--(4.22,3.11);676\draw[ink2] (4.956,2.97)--(4.956,3.11);677\draw[ink2] (5.271,2.97)--(5.271,3.11);678\draw[ink2] (6.06,2.97)--(6.06,3.11);679\node[above,inner sep=2pt] at (2.61,3.04) {\scriptsize $S^1$};680\node[above,inner sep=2pt] at (4.588,3.04) {\scriptsize $S^3$};681\node[above,inner sep=2pt] at (5.134,3.34) {\scriptsize $S^5$};682\draw[ink2,very thin] (5.114,3.06)--(5.134,3.34);683\node[above,inner sep=2pt] at (5.666,3.04) {\scriptsize $\cdots$};684\node[below,inner sep=2.5pt] at (4.22,3.02) {\tiny $\frac13$};685\node[below,inner sep=2.5pt] at (4.956,3.02) {\tiny $\frac25$};686\node[below,inner sep=2.5pt] at (6.06,3.02) {\tiny $\frac12$};687\node[right,inner sep=3pt] at (6.06,3.04) {\scriptsize circle};688\end{tikzpicture}689\caption{Betti numbers over $\Fp_2$ of the Vietoris--Rips complex of twelve equally spaced points on a circle, by scale. The class of the circle (blue) lasts up to $k=3$. At $k=4$, exactly a third of a turn, three classes appear in degree $2$, and at $k=5$ one in degree $5$ (red); at $k=6$ the complex is a full simplex. The line above shows the homotopy type of the complex of the whole circle at the corresponding scale \cite{AdAd17}.}\label{fig:barcode}690\end{figure}691 692\noindent For $n=12$ the Betti numbers over $\Fp_2$ are $(1,1)$ for $k=1,2,3$; $(1,0,3)$ for $k=4$; and693$(1,0,0,0,0,1)$ for $k=5$ (\cref{fig:barcode}). For $n=13$ and $k=5$, which lies between $\frac13$ and $\frac25$, they are $(1,0,0,1)$.694\chk{V4, V5} For $16$ random points on the unit circle whose largest gap is a chord of length $1.516$, the complex695has Betti numbers $(11,0)$ at $r=0.15$, $(1,1)$ at $r=1.55$ and $(1,0)$ at $r=1.9$. \chk{V6} The circle is seen from the largest gap up to about $\sqrt3$,696the chord of a third of a turn. Above that scale the classes in dimensions697$2$, $3$ and $5$ are topology of the construction and not of the data. A learned model that consumes persistence698diagrams should not treat high-dimensional classes at large scales as evidence of high-dimensional structure.699 700\subsection{Stability}701 702A \term{persistence diagram} records, for each homology class of the sublevel sets $\{f\le t\}$ of a function,703the levels at which it is born and dies. The \term{bottleneck distance} between two diagrams is the least704$\delta$ for which their points can be matched, to each other or to the diagonal, with no point moved by more705than $\delta$.706 707\begin{theorem}[Stability]\label{thm:stability}708\Scl[\cite{CEH07}] For two functions $f,g$ on a finite complex, the bottleneck distance between their persistence709diagrams is at most $\max|f-g|$.710\end{theorem}711 712\noindent For $60$ random functions on a cycle of $40$ vertices, perturbed by between $0.02$ and $0.3$ in the713maximum norm, the distance between the diagrams in degree $0$ was never larger than the perturbation, and714equal to it in the worst case, while the number of points of the diagram changed in $35$ of the $60$ cases.715\chk{V7} The diagram is a Lipschitz function of the data and a Betti number is not even continuous. This is the716property that lets persistence enter a model as a feature or a loss, and it is the quantitative form of the717functoriality of homology: a small change of $f$ is an interleaving of the two filtrations.718 719\section{Counts}\label{sec:counts}720 721\subsection{Where regions meet}722 723\begin{theorem}[Junctions]\label{thm:junctions}724\Srf[Lebesgue; \cite{ADTHC}, Thm.~4.3] Let the cube $[0,1]^n$ be covered by finitely many closed sets, none of725which meets two opposite faces. Then some point lies in at least $n+1$ of them.726\end{theorem}727 728\noindent Apply this to the closures of the decision regions of a classifier, a region being a connected set of inputs729with one label. If no region reaches across the cube, there is a point every neighbourhood of which meets $n+1$730regions. Small regions731cannot be arranged so that at most $n$ meet anywhere; the brick pattern, in which exactly $n+1$ meet, is optimal732\cite[Fig.~4.4]{ADTHC}.733 734\begin{figure}[t]735\centering736\begin{tikzpicture}737\fill[fwd!10] (1.401,2.877)--(0.521,3.118)--(0,3.082)--(0,0.925)--(1.286,1.775)--cycle;738\fill[fwd!10] (0.826,5.4)--(0.079,5.4)--(0.53,3.569)--(1.116,4.969)--cycle;739\fill[fwd!10] (1.882,0)--(4.185,0)--(3.21,1.164)--(2.829,1.232)--(2.243,1.074)--cycle;740\fill[bwd!14] (0.079,5.4)--(0,5.4)--(0,3.082)--(0.521,3.118)--(0.53,3.569)--cycle;741\fill[accent!10] (1.116,4.969)--(0.53,3.569)--(0.521,3.118)--(1.401,2.877)--(2.026,3.347)--(2.102,3.835)--cycle;742\fill[fwd!10] (2.407,3.084)--(2.576,2.811)--(3.841,2.118)--(4.278,2.381)--(3.928,3.183)--cycle;743\fill[bwd!14] (5.4,2.101)--(5.4,4.757)--(4.151,4.075)--(3.928,3.183)--(4.278,2.381)--cycle;744\fill[bwd!14] (3.841,2.118)--(2.576,2.811)--(2.829,1.232)--(3.21,1.164)--cycle;745\fill[bwd!14] (0,0)--(1.882,0)--(2.243,1.074)--(1.286,1.775)--(0,0.925)--cycle;746\fill[ink2!12] (2.026,3.347)--(1.401,2.877)--(1.286,1.775)--(2.243,1.074)--(2.829,1.232)--(2.576,2.811)--(2.407,3.084)--cycle;747\fill[accent!10] (4.185,0)--(5.4,0)--(5.4,2.101)--(4.278,2.381)--(3.841,2.118)--(3.21,1.164)--cycle;748\fill[bwd!14] (2.982,5.4)--(0.826,5.4)--(1.116,4.969)--(2.102,3.835)--(2.86,4.425)--cycle;749\fill[fwd!24] (2.86,4.425)--(2.102,3.835)--(2.026,3.347)--(2.407,3.084)--(3.928,3.183)--(4.151,4.075)--cycle;750\fill[fwd!10] (5.4,4.757)--(5.4,5.4)--(2.982,5.4)--(2.86,4.425)--(4.151,4.075)--cycle;751\draw[ink2,thin] (1.401,2.877)--(0.521,3.118)--(0,3.082)--(0,0.925)--(1.286,1.775)--cycle;752\draw[ink2,thin] (0.826,5.4)--(0.079,5.4)--(0.53,3.569)--(1.116,4.969)--cycle;753\draw[ink2,thin] (1.882,0)--(4.185,0)--(3.21,1.164)--(2.829,1.232)--(2.243,1.074)--cycle;754\draw[ink2,thin] (0.079,5.4)--(0,5.4)--(0,3.082)--(0.521,3.118)--(0.53,3.569)--cycle;755\draw[ink2,thin] (1.116,4.969)--(0.53,3.569)--(0.521,3.118)--(1.401,2.877)--(2.026,3.347)--(2.102,3.835)--cycle;756\draw[ink2,thin] (2.407,3.084)--(2.576,2.811)--(3.841,2.118)--(4.278,2.381)--(3.928,3.183)--cycle;757\draw[ink2,thin] (5.4,2.101)--(5.4,4.757)--(4.151,4.075)--(3.928,3.183)--(4.278,2.381)--cycle;758\draw[ink2,thin] (3.841,2.118)--(2.576,2.811)--(2.829,1.232)--(3.21,1.164)--cycle;759\draw[ink2,thin] (0,0)--(1.882,0)--(2.243,1.074)--(1.286,1.775)--(0,0.925)--cycle;760\draw[ink2,thin] (2.026,3.347)--(1.401,2.877)--(1.286,1.775)--(2.243,1.074)--(2.829,1.232)--(2.576,2.811)--(2.407,3.084)--cycle;761\draw[ink2,thin] (4.185,0)--(5.4,0)--(5.4,2.101)--(4.278,2.381)--(3.841,2.118)--(3.21,1.164)--cycle;762\draw[ink2,thin] (2.982,5.4)--(0.826,5.4)--(1.116,4.969)--(2.102,3.835)--(2.86,4.425)--cycle;763\draw[ink2,thin] (2.86,4.425)--(2.102,3.835)--(2.026,3.347)--(2.407,3.084)--(3.928,3.183)--(4.151,4.075)--cycle;764\draw[ink2,thin] (5.4,4.757)--(5.4,5.4)--(2.982,5.4)--(2.86,4.425)--(4.151,4.075)--cycle;765\draw[ink2,thick] (0,0) rectangle (5.4,5.4);766\fill[ink2] (0.361,2.232) circle (1pt);767\fill[ink2] (0.597,4.061) circle (1pt);768\fill[ink2] (2.761,0.268) circle (1pt);769\fill[ink2] (0.242,3.974) circle (1pt);770\fill[ink2] (0.833,3.962) circle (1pt);771\fill[ink2] (3.404,2.723) circle (1pt);772\fill[ink2] (4.621,3.254) circle (1pt);773\fill[ink2] (3.096,2.16) circle (1pt);774\fill[ink2] (1.343,0.745) circle (1pt);