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 715–814 of 1055. Source text is displayed literally.
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);775\fill[ink2] (2.286,2.031) circle (1pt);776\fill[ink2] (4.171,1.449) circle (1pt);777\fill[ink2] (2.152,5.109) circle (1pt);778\fill[ink2] (3.35,3.571) circle (1pt);779\fill[ink2] (3.715,4.915) circle (1pt);780\draw[accent,thick,fill=white] (1.401,2.877) circle (2.1pt);781\draw[accent,thick,fill=white] (0.521,3.118) circle (2.1pt);782\draw[accent,thick,fill=white] (1.286,1.775) circle (2.1pt);783\draw[accent,thick,fill=white] (0.53,3.569) circle (2.1pt);784\draw[accent,thick,fill=white] (1.116,4.969) circle (2.1pt);785\draw[accent,thick,fill=white] (3.21,1.164) circle (2.1pt);786\draw[accent,thick,fill=white] (2.829,1.232) circle (2.1pt);787\draw[accent,thick,fill=white] (2.243,1.074) circle (2.1pt);788\draw[accent,thick,fill=white] (2.026,3.347) circle (2.1pt);789\draw[accent,thick,fill=white] (2.102,3.835) circle (2.1pt);790\draw[accent,thick,fill=white] (2.407,3.084) circle (2.1pt);791\draw[accent,thick,fill=white] (2.576,2.811) circle (2.1pt);792\draw[accent,thick,fill=white] (3.841,2.118) circle (2.1pt);793\draw[accent,thick,fill=white] (4.278,2.381) circle (2.1pt);794\draw[accent,thick,fill=white] (3.928,3.183) circle (2.1pt);795\draw[accent,thick,fill=white] (4.151,4.075) circle (2.1pt);796\draw[accent,thick,fill=white] (2.86,4.425) circle (2.1pt);797\end{tikzpicture}798\caption{A nearest-prototype classifier of the square with $14$ classes; the dots are the prototypes. No region reaches from one side to the opposite side, and there are $17$ points (circled) where three classes meet. By \cref{thm:junctions} at least one is forced, however the regions are drawn.}\label{fig:voronoi}799\end{figure}800 801For $60$ random nearest-prototype classifiers of the square with $14$ classes (one is drawn in802\cref{fig:voronoi}) there were between $13$ and $18$ triple points, and for $8$ classifiers of the cube with $40$ classes between $143$ and $174$ points803where four classes meet. \chk{N1, N2} The statement is a topological companion to results on the unavoidability of nearby misclassification804\cite{SHSFG19}: those use isoperimetric inequalities to estimate the measure of the points near a boundary, and805this one says that the boundaries themselves must meet, $n+1$ at a time. The proof is Sperner's806lemma, and the lemma comes with an algorithm: walk from cell to cell through faces carrying a fixed set of $n$807labels. For a labelling induced by a smooth self-map of the triangle the walk reaches a complete cell, and with808it an approximate fixed point, in $13$, $25$, $50$, $97$ steps on grids of side $16$, $32$, $64$, $128$, linear809in the side although the number of cells is quadratic. \chk{N3} In high dimension the walk can be exponentially810long, and finding its end is complete for the class PPAD \cite{Pap94,DGP09}; this is the complexity of computing811an equilibrium of a game, or a fixed point of an implicit layer \cite{BKK19}, without further structure.812 813\subsection{Fixed points of attractors}814