Independent scholarship · Open accessThe monthly digest

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 895–994 of 1055. Source text is displayed literally.

895\draw[fwd,thick,-{Stealth[length=4pt]}] (3.602,0.667)--(3.561,0.711);896\fill[accent] (2.496,0) circle (1.8pt);897\node at (3.241,-1.504) {\scriptsize $b=1.2930$};898\node at (3.241,-1.824) {\scriptsize undefined};899\draw[ink2,very thin] (4.554,0)--(6.98,0);900\draw[ink2,very thin] (4.709,-1.254)--(4.709,1.254);901\draw[fwd,thick] plot coordinates {(6.795,-0.243) (6.789,-0.21) (6.783,-0.177) (6.775,-0.144) (6.767,-0.11) (6.759,-0.076) (6.75,-0.043) (6.74,-0.009) (6.73,0.024) (6.719,0.058) (6.707,0.091) (6.695,0.124) (6.683,0.157) (6.669,0.19) (6.656,0.222) (6.642,0.254) (6.627,0.285) (6.612,0.316) (6.596,0.347) (6.58,0.377) (6.564,0.406) (6.547,0.435) (6.53,0.464) (6.512,0.491) (6.494,0.518) (6.475,0.545) (6.457,0.571) (6.437,0.596) (6.418,0.62) (6.398,0.644) (6.378,0.667) (6.357,0.689) (6.336,0.711) (6.315,0.732) (6.294,0.752) (6.272,0.772) (6.25,0.791) (6.227,0.809) (6.204,0.826) (6.181,0.843) (6.158,0.859) (6.134,0.875) (6.11,0.89) (6.086,0.904) (6.062,0.918) (6.037,0.931) (6.012,0.943) (5.988,0.955) (5.963,0.967) (5.939,0.977) (5.914,0.988) (5.89,0.997) (5.865,1.006) (5.841,1.015) (5.818,1.022) (5.794,1.03) (5.771,1.036) (5.749,1.042) (5.727,1.048) (5.705,1.052) (5.684,1.056) (5.664,1.06) (5.644,1.063) (5.625,1.065) (5.606,1.067) (5.588,1.068) (5.57,1.068) (5.553,1.068) (5.537,1.067) (5.521,1.065) (5.506,1.062) (5.492,1.059) (5.478,1.056) (5.464,1.051) (5.451,1.046) (5.439,1.04) (5.427,1.033) (5.415,1.026) (5.404,1.018) (5.393,1.009) (5.383,1) (5.373,0.99) (5.363,0.979) (5.354,0.967) (5.345,0.954) (5.336,0.941) (5.327,0.927) (5.319,0.913) (5.311,0.897) (5.303,0.881) (5.295,0.865) (5.288,0.847) (5.281,0.829) (5.274,0.811) (5.268,0.791) (5.262,0.772) (5.256,0.751) (5.25,0.73) (5.244,0.709) (5.239,0.687) (5.235,0.665) (5.23,0.642) (5.226,0.619) (5.222,0.595) (5.219,0.571) (5.216,0.547) (5.214,0.523) (5.211,0.498) (5.21,0.474) (5.209,0.449) (5.208,0.423) (5.208,0.398) (5.208,0.373) (5.209,0.347) (5.21,0.321) (5.212,0.296) (5.214,0.27) (5.217,0.244) (5.221,0.218) (5.225,0.192) (5.229,0.166) (5.234,0.14) (5.24,0.114) (5.246,0.088) (5.253,0.062) (5.26,0.037) (5.268,0.011) (5.277,-0.015) (5.286,-0.04) (5.295,-0.065) (5.306,-0.091) (5.316,-0.116) (5.328,-0.141) (5.34,-0.166) (5.353,-0.19) (5.366,-0.215) (5.38,-0.239) (5.395,-0.263) (5.41,-0.287) (5.426,-0.311) (5.442,-0.335) (5.46,-0.359) (5.478,-0.382) (5.497,-0.405) (5.516,-0.429) (5.536,-0.452) (5.557,-0.474) (5.579,-0.497) (5.601,-0.52) (5.624,-0.542) (5.648,-0.564) (5.672,-0.586) (5.697,-0.608) (5.722,-0.629) (5.749,-0.651) (5.775,-0.672) (5.802,-0.693) (5.83,-0.713) (5.858,-0.733) (5.886,-0.753) (5.915,-0.773) (5.944,-0.792) (5.973,-0.81) (6.002,-0.828) (6.031,-0.846) (6.06,-0.864) (6.089,-0.88) (6.118,-0.896) (6.146,-0.912) (6.174,-0.927) (6.201,-0.942) (6.229,-0.956) (6.255,-0.969) (6.281,-0.982) (6.306,-0.994) (6.331,-1.005) (6.355,-1.016) (6.378,-1.026) (6.4,-1.036) (6.422,-1.044) (6.443,-1.053) (6.463,-1.06) (6.482,-1.067) (6.5,-1.073) (6.518,-1.079) (6.534,-1.084) (6.55,-1.088) (6.566,-1.091) (6.58,-1.094) (6.594,-1.097) (6.607,-1.098) (6.62,-1.099) (6.632,-1.099) (6.643,-1.099) (6.654,-1.098) (6.664,-1.097) (6.673,-1.094) (6.683,-1.091) (6.691,-1.088) (6.7,-1.083) (6.708,-1.078) (6.715,-1.072) (6.723,-1.066) (6.73,-1.059) (6.736,-1.051) (6.742,-1.042) (6.749,-1.032) (6.754,-1.022) (6.76,-1.011) (6.765,-0.999) (6.77,-0.986) (6.775,-0.973) (6.78,-0.958) (6.784,-0.943) (6.789,-0.927) (6.793,-0.91) (6.797,-0.892) (6.801,-0.873) (6.804,-0.854) (6.807,-0.833) (6.81,-0.812) (6.813,-0.79) (6.816,-0.767) (6.818,-0.743) (6.82,-0.719) (6.822,-0.694) (6.823,-0.668) (6.824,-0.641) (6.825,-0.613) (6.825,-0.585) (6.825,-0.557) (6.824,-0.528) (6.823,-0.498) (6.821,-0.467) (6.819,-0.437) (6.817,-0.405) (6.814,-0.374) (6.81,-0.342) (6.806,-0.309) (6.801,-0.276) (6.795,-0.243)};902\draw[fwd,thick,-{Stealth[length=4pt]}] (6.378,0.667)--(6.336,0.711);903\fill[accent] (4.709,0) circle (1.8pt);904\node at (5.767,-1.504) {\scriptsize $b=2.2$};905\node at (5.767,-1.824) {\scriptsize degree $0$};906\end{tikzpicture}907\caption{The output curve of a network with four hidden units, for three values of a bias $b$ added to the first output; the dot is the origin. The normalized output has degree $1$ while the curve encloses the origin and degree $0$ after it has left; in between, at $b=1.2930$, the curve passes through the origin and the normalized output is not defined.}\label{fig:degree}908\end{figure}909 910\noindent For a network with four hidden units (\cref{fig:degree}) the degree is $1$, and the signed number of preimages of three911directions is $1$ each. Adding a bias $b$ to the first output, the degree drops to $0$ at $b=1.2930$, where the912smallest output norm over the circle is $10^{-4}$. \chk{N6} Training that must change the degree of the output,913to fit a target of another class, has to pass through weights at which the normalized output is undefined and914its gradient unbounded; and if the initial class is the right one, a barrier of the same kind protects it. By915Hopf's theorem the degree is the only such invariant for maps to a sphere of the same dimension.916 917\subsection{Zeros of odd networks}918 919\begin{proposition}[Odd networks]\label{prop:odd}920\Scl[Borsuk--Ulam \cite{Mat03}] A network $\R^{n+1}\to\R^n$ without biases and with odd activations is an odd map,921and it vanishes somewhere on every sphere centred at the origin. For $n=1$, if its restriction to the circle is922continuously differentiable and all its zeros are simple, their number is congruent to $2$ modulo $4$.923\end{proposition}924\begin{proof}925Borsuk--Ulam gives an antipodal pair with equal values. Oddness makes that common value zero.926For $n=1$, start the half-turn at a point with nonzero output. The endpoint signs are opposite, and each927simple zero changes the sign, so the half-turn contains an odd number of zeros. The other half-turn contains928their antipodes, giving twice an odd number in all.929\end{proof}930 931\noindent A sign scan on the unit circle found $2$ crossings for $193$ of $200$ random networks with six932hyperbolic tangent units and $6$ for the other $7$. An output bias of $10$ makes the last network strictly933positive, since it exceeds the sum of absolute output weights. \chk{N7} Oddness also applies to934\cref{thm:bottleneck}, whose collisions are the zeros of the odd map $e(x)-e(-x)$. An architecture made odd for935the sake of a symmetry therefore pays for it: its scalar outputs cannot be of one sign on any sphere, and the936decision boundary of a bias-free odd classifier meets every sphere round the origin.937 938\section{Summary of results}\label{sec:summary}939 940\begin{table*}[t]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 the