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 655–754 of 1055. Source text is displayed literally.
655\draw[ink2,very thin,fill=white] (4.68,1.68) rectangle (5.6,2.1);656\draw[ink2,very thin,fill=accent!28] (4.68,2.1) rectangle (5.6,2.52);657\node at (5.14,2.31) {\scriptsize $1$};658\node at (5.14,-0.22) {\scriptsize $5$};659\draw[ink2,very thin,fill=fwd!22] (5.6,0) rectangle (6.52,0.42);660\node at (6.06,0.21) {\scriptsize $1$};661\draw[ink2,very thin,fill=white] (5.6,0.42) rectangle (6.52,0.84);662\draw[ink2,very thin,fill=white] (5.6,0.84) rectangle (6.52,1.26);663\draw[ink2,very thin,fill=white] (5.6,1.26) rectangle (6.52,1.68);664\draw[ink2,very thin,fill=white] (5.6,1.68) rectangle (6.52,2.1);665\draw[ink2,very thin,fill=white] (5.6,2.1) rectangle (6.52,2.52);666\node at (6.06,-0.22) {\scriptsize $6$};667\node[left,inner sep=2pt] at (1,0.21) {\scriptsize $H_0$};668\node[left,inner sep=2pt] at (1,0.63) {\scriptsize $H_1$};669\node[left,inner sep=2pt] at (1,1.05) {\scriptsize $H_2$};670\node[left,inner sep=2pt] at (1,1.47) {\scriptsize $H_3$};671\node[left,inner sep=2pt] at (1,1.89) {\scriptsize $H_4$};672\node[left,inner sep=2pt] at (1,2.31) {\scriptsize $H_5$};673\node at (3.76,-0.62) {\scriptsize scale $k$ (steps of $\frac1{12}$ of a turn)};674\draw[ink2] (1,3.04)--(6.06,3.04);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;