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 155–254 of 1055. Source text is displayed literally.
155 156\subsection{Bottlenecks}157 158\begin{theorem}[Bottleneck bound]\label{thm:bottleneck}159\Srf[Borsuk--Ulam \cite{Mat03}] Let $M$ be the unit sphere $S^n\subset\R^{n+1}$, $e\colon S^n\to\R^n$ continuous and160$d\colon\R^n\to\R^{n+1}$ arbitrary. Then161\[ \sup_{x\in S^n}|d(e(x))-x|\ \ge\ 1, \]162and equality holds for $e$ the projection to the first $n$ coordinates and $d$ the inclusion.163\end{theorem}164\begin{proof}165By the Borsuk--Ulam theorem there is $x$ with $e(x)=e(-x)$. Let $y$ be the common reconstruction. Then166$|y-x|+|y+x|\ge|2x|=2$, so one of the two errors is at least $1$. For the projection the error is167$|x_{n+1}|\le1$.168\end{proof}169 170\begin{figure}[t]171\centering172\begin{tikzpicture}173\begin{scope}[shift={(1.5,2.0)}]174\draw[ink2,thick] (0,0) circle (1.25);175\draw[ink2,densely dotted] (-1,-0.75)--(-1,0.75);176\fill[ink2] (-1,-0.75) circle (0.9pt); \fill[ink2] (-1,0.75) circle (0.9pt);177\draw[ink2,densely dotted] (-0.5,-1.146)--(-0.5,1.146);178\fill[ink2] (-0.5,-1.146) circle (0.9pt); \fill[ink2] (-0.5,1.146) circle (0.9pt);179\draw[ink2,densely dotted] (0.5,-1.146)--(0.5,1.146);180\fill[ink2] (0.5,-1.146) circle (0.9pt); \fill[ink2] (0.5,1.146) circle (0.9pt);181\draw[ink2,densely dotted] (1,-0.75)--(1,0.75);182\fill[ink2] (1,-0.75) circle (0.9pt); \fill[ink2] (1,0.75) circle (0.9pt);183\draw[accent,thick] (0,-1.25)--(0,1.25);184\fill[accent] (0,1.25) circle (1.6pt) node[above,inner sep=2pt]{\scriptsize $x$}; \fill[accent] (0,-1.25) circle (1.6pt) node[below,inner sep=2pt]{\scriptsize $-x$};185\fill[bwd] (0,0.28) circle (1.6pt) node[right,inner sep=2pt]{\scriptsize $y$};186\draw[ink2,-{Stealth[length=3pt]}] (-1.35,-1.87)--(1.5,-1.87);187\node[right,inner sep=1pt] at (1.52,-1.87) {\scriptsize $\R$};188\fill[ink2] (-1,-1.87) circle (1.1pt);189\fill[ink2] (-0.5,-1.87) circle (1.1pt);190\fill[accent] (0,-1.87) circle (1.1pt);191\fill[ink2] (0.5,-1.87) circle (1.1pt);192\fill[ink2] (1,-1.87) circle (1.1pt);193\node[left,inner sep=1pt] at (-1.37,-1.87) {\scriptsize $e$};194\node at (0,-2.33) {\scriptsize (a)};195\end{scope}196\begin{scope}[shift={(4.3,0.75)}]197\draw[ink2] (0,2.7)--(0,0)--(3.6,0);198\draw[ink2] (0,0)--(0,-0.07) node[below,inner sep=1.5pt]{\scriptsize $0$};199\draw[ink2] (3.6,0)--(3.6,-0.07) node[below,inner sep=1.5pt]{\scriptsize $\pi$};200\node[below] at (1.8,-0.38) {\scriptsize $\theta$};201\draw[thick,fwd] plot coordinates {(0,1.488) (0.03,1.496) (0.06,1.499) (0.09,1.499) (0.12,1.494) (0.15,1.486) (0.18,1.474) (0.21,1.459) (0.24,1.44) (0.27,1.417) (0.3,1.392) (0.33,1.364) (0.36,1.333) (0.39,1.3) (0.42,1.264) (0.45,1.227) (0.48,1.188) (0.51,1.148) (0.54,1.107) (0.57,1.066) (0.6,1.024) (0.63,0.982) (0.66,0.941) (0.69,0.901) (0.72,0.861) (0.75,0.823) (0.78,0.787) (0.81,0.753) (0.84,0.721) (0.87,0.692) (0.9,0.665) (0.93,0.642) (0.96,0.622) (0.99,0.606) (1.02,0.594) (1.05,0.585) (1.08,0.581) (1.11,0.581) (1.14,0.585) (1.17,0.594) (1.2,0.607) (1.23,0.625) (1.26,0.647) (1.29,0.673) (1.32,0.704) (1.35,0.739) (1.38,0.778) (1.41,0.821) (1.44,0.868) (1.47,0.919) (1.5,0.973) (1.53,1.03) (1.56,1.09) (1.59,1.152) (1.62,1.217) (1.65,1.284) (1.68,1.352) (1.71,1.422) (1.74,1.492) (1.77,1.563) (1.8,1.635) (1.83,1.706) (1.86,1.777) (1.89,1.846) (1.92,1.915) (1.95,1.982) (1.98,2.047) (2.01,2.109) (2.04,2.169) (2.07,2.226) (2.1,2.28) (2.13,2.33) (2.16,2.376) (2.19,2.418) (2.22,2.456) (2.25,2.489) (2.28,2.518) (2.31,2.541) (2.34,2.56) (2.37,2.574) (2.4,2.582) (2.43,2.586) (2.46,2.584) (2.49,2.577) (2.52,2.565) (2.55,2.547) (2.58,2.525) (2.61,2.498) (2.64,2.467) (2.67,2.431) (2.7,2.39) (2.73,2.346) (2.76,2.297) (2.79,2.246) (2.82,2.191) (2.85,2.133) (2.88,2.072) (2.91,2.01) (2.94,1.945) (2.97,1.879) (3,1.811) (3.03,1.743) (3.06,1.674) (3.09,1.606) (3.12,1.537) (3.15,1.47) (3.18,1.403) (3.21,1.338) (3.24,1.274) (3.27,1.213) (3.3,1.153) (3.33,1.097) (3.36,1.044) (3.39,0.993) (3.42,0.947) (3.45,0.904) (3.48,0.865) (3.51,0.83) (3.54,0.799) (3.57,0.772) (3.6,0.75)};202\draw[thick,bwd,densely dashed] plot coordinates {(0,0.75) (0.03,0.733) (0.06,0.72) (0.09,0.711) (0.12,0.707) (0.15,0.708) (0.18,0.712) (0.21,0.722) (0.24,0.735) (0.27,0.752) (0.3,0.773) (0.33,0.798) (0.36,0.826) (0.39,0.857) (0.42,0.892) (0.45,0.928) (0.48,0.967) (0.51,1.009) (0.54,1.051) (0.57,1.095) (0.6,1.14) (0.63,1.186) (0.66,1.232) (0.69,1.278) (0.72,1.324) (0.75,1.369) (0.78,1.413) (0.81,1.455) (0.84,1.496) (0.87,1.535) (0.9,1.571) (0.93,1.605) (0.96,1.636) (0.99,1.664) (1.02,1.688) (1.05,1.709) (1.08,1.726) (1.11,1.74) (1.14,1.749) (1.17,1.754) (1.2,1.755) (1.23,1.751) (1.26,1.744) (1.29,1.732) (1.32,1.716) (1.35,1.695) (1.38,1.671) (1.41,1.643) (1.44,1.61) (1.47,1.574) (1.5,1.535) (1.53,1.492) (1.56,1.446) (1.59,1.397) (1.62,1.345) (1.65,1.291) (1.68,1.236) (1.71,1.178) (1.74,1.119) (1.77,1.059) (1.8,0.999) (1.83,0.938) (1.86,0.876) (1.89,0.816) (1.92,0.755) (1.95,0.696) (1.98,0.638) (2.01,0.582) (2.04,0.528) (2.07,0.476) (2.1,0.427) (2.13,0.38) (2.16,0.337) (2.19,0.297) (2.22,0.26) (2.25,0.227) (2.28,0.198) (2.31,0.174) (2.34,0.153) (2.37,0.137) (2.4,0.125) (2.43,0.117) (2.46,0.114) (2.49,0.116) (2.52,0.122) (2.55,0.132) (2.58,0.147) (2.61,0.165) (2.64,0.188) (2.67,0.215) (2.7,0.245) (2.73,0.279) (2.76,0.316) (2.79,0.356) (2.82,0.399) (2.85,0.444) (2.88,0.492) (2.91,0.542) (2.94,0.593) (2.97,0.645) (3,0.698) (3.03,0.752) (3.06,0.807) (3.09,0.861) (3.12,0.914) (3.15,0.968) (3.18,1.02) (3.21,1.07) (3.24,1.119) (3.27,1.166) (3.3,1.211) (3.33,1.253) (3.36,1.293) (3.39,1.329) (3.42,1.363) (3.45,1.393) (3.48,1.419) (3.51,1.442) (3.54,1.461) (3.57,1.477) (3.6,1.488)};203\fill[accent] (0.56,1.08) circle (2pt);204\fill[accent] (1.652,1.288) circle (2pt);205\fill[accent] (3.283,1.186) circle (2pt);206\draw[thick,fwd] (0.1,2.93)--(0.5,2.93) node[right,inner sep=2pt,black]{\scriptsize $e(\theta)$};207\draw[thick,bwd,densely dashed] (1.75,2.93)--(2.15,2.93) node[right,inner sep=2pt,black]{\scriptsize $e(\theta+\pi)$};208\node at (1.8,-0.83) {\scriptsize (b)};209\end{scope}210\end{tikzpicture}211\caption{The bottleneck bound for the circle. (a)~The fibres of the projection code; the fibre through the poles is an antipodal pair, and whatever point $y$ the decoder returns for it is at distance at least $1$ from one of the two. (b)~A random trigonometric encoder $e$ and its antipodal translate on a half-turn: since $e(\theta)-e(\theta+\pi)$ changes sign, the graphs cross (3 times here), and at a crossing the code identifies $x$ and $-x$.}\label{fig:bottleneck}212\end{figure}213 214\noindent For $n=1$ the collision was located for $200$ random trigonometric encoders, and for $n=2$ for $40$215random cubic encoders, to rounding (\cref{fig:bottleneck}). \chk{O1, O2} For each of $100$ random encoders of the216circle, some fibre of the code, taken to one percent of its range, is contained in no disc of radius less than217$1.0000$: no decoder can do better than error $1$ there. \chk{O3} The theorem is about the worst case. The mean error can be made small, by a code that is218injective except near one point; the bound says that the failure cannot be removed, only moved and made thin.219For a general closed $n$-manifold the qualitative statement survives: by Brouwer's invariance of domain, the220companion of the invariance of dimension \cite[Thm.~4.3]{ADTHC}, it has no continuous injective code in $\R^n$.221The constant is special to round spheres.222This is the topological reason for latent spaces that are themselves spheres, tori or groups223\cite{DFdC18,FdH18}.224 225\subsection{Rotations}226 227Let $\rho\colon S^3\to\SO(3)$ send a unit quaternion $q$ to the rotation $v\mapsto qvq^{-1}$. It is onto, and228$\rho(q)=\rho(-q)$.229 230\begin{theorem}[Naming a rotation]\label{thm:rotation}231\Sli[\cite{ZBLYL19}; \cite{ADTHC}, Thm.~10.1] \emph{(a)} $\rho$ has no continuous right inverse: for every choice232of a quaternion $s(R)$ with $\rho(s(R))=R$ there is, on every non-contractible loop of rotations, a point where233$s$ jumps by $|q-(-q)|=2$. \emph{(b)} More generally a family of rotations $X\to\SO(3)$ has a continuous234quaternion target if and only if it induces the zero map $\pi_1(X)\to\pi_1(\SO(3))=\Z/2$. \emph{(c)} There is no235continuous representation of $\SO(3)$ in $\R^m$ for $m\le4$. \emph{(d)} Two columns of the rotation matrix, with236Gram--Schmidt orthogonalization as decoder, give a continuous representation in $\R^6$.237\end{theorem}238\begin{proof}239(a), (b): $\rho$ is the universal covering, and a map lifts through a covering exactly when it kills the240fundamental group; a full turn about an axis lifts to a path from $q$ to $-q$. (c) is proved in \cite{ZBLYL19}241from the fact that $\SO(3)$, which is real projective $3$-space, does not embed in $\R^4$. (d) The two columns242determine the third by the cross product.243\end{proof}244 245\begin{figure}[t]246\centering247\begin{tikzpicture}248\begin{scope}[shift={(0,0)}]249\draw[ink2] (0,2.3)--(0,0)--(3.25,0);250\draw[ink2] (0,0)--(0,-0.07) node[below,inner sep=1.5pt]{\scriptsize $0$};251\draw[ink2] (1.625,0)--(1.625,-0.07) node[below,inner sep=1.5pt]{\scriptsize $\pi$};252\draw[ink2] (3.25,0)--(3.25,-0.07) node[below,inner sep=1.5pt]{\scriptsize $2\pi$};253\draw[ink2] (0,0.085)--(-0.07,0.085) node[left,inner sep=1.5pt]{\scriptsize $-1$};254\draw[ink2] (0,1.15)--(-0.07,1.15) node[left,inner sep=1.5pt]{\scriptsize $0$};