Another solution: Practice dynamic visual acuity and predict the opponent's move via their hand shape.

The extreme version of this strategy looks like this robot.

The human version of this strategy (source) is to realize that rock is the weakest (since it is easy to recognize as there is no change in hand shape over time, given that the default hand-state is usually rock), and so conclude that the best strategy is to play paper if you recognize no change in hand shape, and play scissor if you recognize any movement (because it means it's either paper or scissor, and scissor gives win or draw)^[1].

1. ^{^}

   This is of course vulnerable to exploitation once the opponent knows you're using this and they also have good dynamic visual acuity (eg opponent can randomize the default hand-state, diagonalize against your heuristic by inserting certain twitches to their hand movement, etc).

Update to my last shortform on "Why Homology?"

My current favorite frame for thinking about homology is as fixing Poincare's initial conception of "counting submanifolds up to cobordism". (I've learned this perspective from this excellent blog post, and I summarize my understanding below.)

In Analysis Situs, Poincare sought to count m-submanifolds of a given a n-manifold up to some equivalence relation - namely, being a boundary of some (m+1)-submanifold, i.e. cobordism. I personally buy cobordism as a concept that is as natural as homotopy for one to have come up with (unlike the initially-seemingly-unmotivated definition of "singular homology"), so I am sold on this as a starting point.

Formally, given a n-manifold $X$ and m-submanifolds (disjoint) $M_1,\dots ,M_m$, being cobordant means there's a (m+1)-submanifold $W$ such that $\partial W=M_1\bigsqcup \dots \bigsqcup M_m$. These may have an orientation, so we can write this relation as a formal sum ${\sum }_{i=1}^m{c}_i{M}_i\sim 0$ where $c_i=\pm 1$. Now, if there are many such (m+1)-submanifolds for which the $M_i$ form a disjoint boundary, we can sum all of these formal sums together to get ${\sum }_{i=1}^m{a}_i{M}_i\sim 0$ where $a_i\in Z$.

Now, this already looks a lot like homology! For example, above already implies $M_i$ themselves have empty boundary (because manifold boundary of manifold boundary is empty, and $M_i$ are disjoint). So if we consider two formal sums ${\sum }_{i=1}^m{a}_i{M}_i$ and ${\sum }_{i=1}^m{b}_i{M}_i$ to be the same if ${\sum }_{i=1}^m(a_i-b_i)M_i\sim 0$, then 1) we are considering formal sums of $M_i$ with empty boundary 2) up to being a boundary of a (m+1)-dimensional manifold. This sounds a lot like $\ker \partial /\mathrm{im}\partial$ - though note that Poincare apparently put none of this in a group theory language.

So Poincare's "collection of m-submanifolds of $X$ up to cobordism" is the analogue of $H_m\left(X\right)$!

But it turns out this construction doesn't really work for some subtle issues (due to Heegaard). This led Poincare to a more combinatorial alternative to this cobordism idea that didn't face these issues, which became the birth of the more modern notion of simplicial homology.

(The blog post then describes how Poincare's initial vision of "counting submanifolds up to cobordism" can still be salvaged (which I plan to read more about in the future), but for my purpose of understanding the motivation behind homology, this is already very insightful!)

It was a good idea!

Perhaps relevant: An Informational Parsimony Perspective on Probabilistic Symmetries (Charvin et al 2024), on applying information bottleneck approaches to group symmetries:

... the projection on orbits of a symmetry group’s action can be seen as an information-preserving compression, as it preserves the information about anything invariant under the group action. This suggests that projections on orbits might be solutions to well-chosen rate-distortion problems, hence opening the way to the integration of group symmetries into an information-theoretic framework. If successful, such an integration could formalise the link between symmetry and information parsimony, but also (i) yield natural ways to “soften” group symmetries into flexible concepts more relevant to real-world data — which often lacks exact symmetries despite exhibiting a strong “structure” — and (ii) enable symmetry discovery through the optimisation of information-theoretic quantities.

Have you heard of Rene Thom's work on Structural Stability and Morphogenesis? I haven't been able to read this book yet^[1], but my understanding^[2] of its thesis is that: "development of form" (i.e. morphogenesis, broadly construed, eg biological or otherwise) depends on information from the structurally stable "catastrophe sets" of the potential driving (or derived from) the dynamics - structurally stable ones, precisely because what is stable under infinitesimal perturbation are the only kind of information observable in nature.

Rene Thom puts all of this in a formal model - and, using tools of algebraic topology, show that these discrete catastrophes (under some conditions, like number of variables) have a finite classification, and thus (in the context of this morphological model) is a sort of finitary "sufficient statistics" of the developmental process.

This seems quite similar to the point you're making: [insensitive / stable / robust] things are rare, but they organize the natural ontology of things because they're the only information that survives.

... and there seems to be the more speculative thesis of Thom (presumably; again, I don't know this stuff), where geometric information about these catastrophes directly correspond to functional / internal-structure information about the system (in Thom's context, the Organism whose morphogenic process we're modeling) - this presumably is one of the intellectual predecessors of Structural Bayesianism, the thesis that there is a correspondence between internal structures of Programs or the Learning Machine with the local geometry of some potential.

1. ^{^}

   I don't think I have enough algebraic topology background yet to productively read this book. Everything in this comment should come with Epistemic Status: Low Confidence.

2. ^{^}

   From discussions and reading distillations of Thom's work.

Thank you for the suggestion! That sounds like a good idea, this thread seems to have some good recommendations, will check them out.

Learning algebraic topology, homotopy always felt like a very intuitive and natural sort of invariant to attach to a space whereas for homology I don't think I have anywhere as close of an intuitive handle or sense of naturality of this concept as I do for homotopy. So I tried to collect some frames / results for homology I've learned to see if it helps convince my intuition that this concept is indeed something natural in mathspace. I'd be very curious to know if there are any other frames or Deeper Answers to "Why homology?" I'm missing:

1. Measuring "holes" of a space
   • Singular homology: This is the first example I encountered, which will serve as intuition / motivation for the later abstract definitions.
   • Fixing some notations (feel free to skip this bullet point if you're familiar with the notations):
     • Let's fix some space $X$, and recall our goal associating to that space an algebraic object invariant under homeomorphism / homotopy equivalence.
     • First, a singular $p$-simplex is a map $\sigma :{\Delta }^p\to X$, intuitively representing a simplex living inside the space $X$. So there is a natural ${\sigma }^{\left(i\right)}:{\Delta }^{p-1}\to X$ map which represents each of the $i$ faces. Then, it is natural to consider the set $\{{\sigma }^{\left(i\right)}{\}}_{i=0}^p$ as representing the "boundary" of the singular p-simplex $\sigma$.
     • To make this last idea more precise, we define singular p-chain, which is a free abelian group generated from all the singular p-simplicies of a space, denoted ${\Delta }_p\left(X\right)$. In short, its elements look like (finite) formal sums ${\sum }_{\sigma :{\Delta }^p\to X}{n}_{\sigma }\sigma$. A singular p-simplex $\sigma$ is naturally an element of this group via $1\sigma \in {\Delta }_p\left(X\right)$.
       • This construction, again, is motivated by the boundary idea earlier, since we now can define the boundary of a singular p-simplex $\sigma$ as formal sum ${\sum }_{i=0}^p{\sigma }^{\left(i\right)}\in {\Delta }_{p-1}\left(X\right)$.
     • In fact, the boundary of a singular p-simplex $\sigma$ is actually ${\sum }_{i=0}^p(-1{)}^i{\sigma }^{\left(i\right)}\in {\Delta }_{p-1}(X)$.
       • Why? Intuition: if we draw these ${\sigma }^{\left(i\right)}$ of simple shapes like triangles (so $\sigma :{\Delta }^2\to X$, hence ${\sigma }^{\left(i\right)}:{\Delta }^1\to X$, which is identified with a (directed) edge), we will note that they are oriented kind of weird, contra our intuition that the "boundary" of a triangle ought to be these directed edges that are oriented consistently, clockwise or counterclockwise. The signs correct this.
     • So, we now generally define the boundary of a singular p-chain (not just a simplex) as ${\partial }_p:{\Delta }_p\left(X\right)\to {\Delta }_{p-1}\left(X\right)$ where ${\sum }_{\sigma }{n}_{\sigma }\sigma \mapsto {\sum }_{\sigma }{n}_{\sigma }\partial \sigma$, i.e. the obvious extension of the earlier map as group homs of the free group.
       • Also, brute force application of the definitions show that ${\partial }_p\circ {\partial }_{p+1}=0$, which matches the intuition that a boundary of a boundary should be empty. Yet another motivation for the sign fix earlier!
   • Let's collect all the objects so far: $\left({\Delta }_{\ast }\right(X),{\partial }_{\ast })$. Then, abstractly, we associated to a topological space X, a collection of groups and maps inbetween of order 2 (i.e. ${\partial }_p\circ {\partial }_{p+1}=0$). We call this object a singular complex.
   • The singular chain groups ${\Delta }_{\ast }\left(X\right)$ are obviously invariant under homeomorphism! But it's too large to be useful invariants.
   • So the natural thing to do is to take some quotients and make them smaller. Conveniently, note that ${\partial }_p\circ {\partial }_{p+1}=0$, so $\mathrm{im}{\partial }_{p+1}\subseteq \ker {\partial }_p$, and because they're abelian, we can take the quotient.
     • This is the part where it’s like measuring holes - this video explains it nice.
   • So our singular complex $\left({\Delta }_{\ast }\right(X),{\partial }_{\ast })$ induces a new collection of groups, $H_{\ast }\left(X\right)$ where $H_p\left(X\right):=\ker {\partial }_p/\mathrm{im}{\partial }_{p+1}$. This is the p-th singular homology group of $X$, also a homotopy invariant.
   • So singular homology has two objects: 1) singular chain complex $\left({\Delta }_{\ast }\right(X),{\partial }_{\ast })$, and 2) singular homology groups $H_{\ast }\left(X\right)$.
2. Homological algebra on topological spaces
   • We can abstract the structure of singular homology, and talk of "homology theory" in general as anything with the following data:
     • chain complex $(C_{\ast },{\partial }_{\ast })$ - a collection of some groups indexed by the integers and group homomorphisms between consecutive groups of order 2: ${\partial }_p\circ {\partial }_{p+1}=0$.
     • homology groups $H_{\ast }:=\ker {\partial }_{\ast }/\mathrm{im}{\partial }_{\ast +1}$ (note that the definition of our abstract chain complex above suffices to make this well-defined)
     • (Note this doesn't invoke anything about topology - though these chain complexes often arise from topological spaces, as in the singular homology example.)
   • Homology from this perspective is then basically a functor that assigns, to some object of interest, a “chain” of groups that are connected by maps $\partial$ such that they vanish in order 2 ${\partial }_p\circ {\partial }_{p+1}=0$, which implies $\mathrm{im}{\partial }_{p+1}\subseteq \ker {\partial }_p$. But not necessarily exactness, i.e. $\mathrm{im}{\partial }_{p+1}=\ker {\partial }_p$. Homology, then, measures the failure of exactness via taking quotients.
   • Studying properties of chain complexes and their homology groups on their own as algebraic objects (without caring about where they came from) is called homological algebra, and apparently it shows up in various places in mathematics.
     • So given this assumption of homological algebra’s utility, one could expect that it would be useful to do homological algebra on topological spaces by finding a way to construct chain complexes from spaces, and singular complexes for example does that.
       • (though from a historical perspective this reason for framing the utility of homology in topology feels like double-counting evidence; though might be a frame that convinces an expert who is already convinced of the utility of homology in other fields but doesn’t know algebraic topology?)
3. Elienberg-Steenrod axioms
   • Going back to “homology” for topological spaces, we can abstract them from singular homology alternatively via an axiomatic approach using the Eilenberg-Steenrod axioms, which are axioms that a Top to Grp should satisfy. Showing that singular homology satisfies these axioms is somewhat difficult (specifically, the Excision axiom), but once this is done, it's easy to prove various things about singular homologies directly from the axioms.
   • Turns out, for nice topological spaces (CW complex), Eilenberg-Steenrod axioms fully characterize the homology of that space up to isomorphism!!! Singular homology is an example, but if you hand me some other chain complex and homology induced from that space satisfying the axioms, then their homology should match that of singular homology.
     • This is quite impressive! It really seems like “homology,” as a concept, isn’t “ad hoc” (as one might feel when first learning about singular homology), but rather something deep & universal about spaces, as homotopy is?
       • (going back to 1. Measuring holes, we can then add other examples of chain complexes and the resulting homology groups, of topological spaces, aside from singular homology - the standard ones are: cellular homology, simplicial homology. Why care about multiple homology theories of topological spaces that give you isomorphic homology groups (at least for nice spaces)? Because they have comparative advantages, eg singular: easy to prove things in, cellular: easy for humans to compute with, simplicial: easy for computers to compute with, etc)
4. Homology = (Abelianized? Symmetrized? Linearized?) Homotopy
   • Hurewicz theorem gives a homomorphism between the nth homotopy group ${\pi }_n\left(X\right)$ and the nth homology group $H_n\left(X\right)$. In particular, it says that the 1st homology group is an abelianization of the fundamental group (!!!!)
     • But homotopy groups are always abelian for $n\ge 2$, so no hopes of this abelianization connection beyond $n=1$ (or not?)
   • Dold-Thom theorem: $H_n\left(X\right)\cong {\pi }_{n}SP\left(X\right)$ for CW complex $X$
     • $SP\left(X\right)$ is the infinite symmetric product space of $X$ (in short, take finite products of $X$ and mod by permutation - and given such collection, take a direct limit).
     • This is crazy!
   • Dold-Kan correspondence (?)

Not exactly about adversarial error correction, but: there is a construction (Çapuni & Gács 2021) of a (class of) universal 1-tape (!!) Turing machine that can perform arbitrarily long computation subject to random noise in the per-step action. Despite the non-adversarial noise model, naive majority error correction (or at least their construction of it) only fixes bounded & local error bursts - meaning it doesn't work in the general case, because even though majority vote reduces error probability, the effective error rate is still positive, so something almost surely goes wrong (eg error burst of size greater than what majority vote can handle) as $T\to \infty$.

Their construction, in fact, looks like a hierarchy of simulated turing machines where the higher-level TM is simulated by a level below it but at a bigger tape scale, such that it can resist larger error bursts - and the overall construction looks like "moving" the "live simulation" of the actual program that we want to execute up the hierarchy over time to coarser and more reliable levels.

Becoming Stronger™ (Oct 13 - Nov 2)

Notes and reflections on the things I've learned while Doing Scholarship the last two three weeks (i.e. studying math).

(EDIT (Nov 18): I will post these less frequently, maybe once a month or two, and also make it more self-contained in context, since journal-like content like this probably isn't all that useful for most people. I will perhaps make a blog for more regular learning updates.)

The past three weeks were busier than usual so I had slower progress this time but here it is:

Chapter 6 continued: Sard's theorem

• Tubes! I might have thought the fact that you can embed manifolds in $R^N$ might have been one of those theorems whose main values are conceptual but not that useful in practice (such as Cayley's theorem and the famous quote that the fact that any group is a subgroup of a symmetry group never actually made the task of studying & classifying groups easier) - but that is not the case, due to tubular neighborhoods.
  • The main issue with trying to solve problems about smooth maps between manifolds by embedding the codomain manifold in $R^N$ is that the resulting construction may not lie in the original manifold. Tubular neighborhoods address this by showing that it is always possible, given an embedding of a manifold in $R^N$, to come up with a tube-like open neighborhood of the manifold, equipped with a retraction map, i.e. a map from this neighborhood to itself such that it is an identity when restricted to the manifold.
  • So conceptually, tubular neighborhoods let us reason about manifold problems by solving them in $R^N$, and bringing it back to manifolds.
• Applications are massive! Might be my favorite concept so far.
  • Whitney approximation theorem (any continuous map is homotopic to a smooth one. If the original continuous map is smooth on a closed subset, the homotopy can be taken relative to it)
    • Proof: Prove it for the case when the codomain is $R^m$, and just compose it with the tubular neighborhood retraction.
  • If a compact manifold has a nonzero vector field, then there exists a map to itself without fixed points
    • Proof: Embed everything (the manifold, its tangent spaces) in R^m, let the map be the one that takes a point to the direction indicated by the nonzero vector field at some small magnitude $ϵ$. This will take things outside of the manifold, so compose with the tubular neighborhood retraction (which is allowed if $ϵ$ is small enough).
• Transversality was also introduced in this chapter (though I am already somewhat familiar with this from my difftop class long time ago).
  • In a sense, it generalizes regular values. Preimage of regular values form embedded submanifolds, preimage of submanifolds transversal to the map leads to embedded submanifolds.
  • Two submanifolds X, Y \subseteq M being transverse formalize the notion of them intersecting in a "generic manner."
  • Transversality Homotopy Theorem: Given any embedded submanifold X \subseteq M, any smooth map is homotopic to another smooth map which is transverse to X.
    • This shows that transversality is generic. Very important for the study of stable property of smooth maps.

Chapter 8: Vector Fields

• Vector fields a section $X:TM\to M$ of the projection map of the tangent bundle $\pi :TM\to M$. Very elegant definition! Also lets me better appreciate the smooth structure defined over the tangent bundle, which automatically implies that a vector field is smooth iff their coordinate functions are smooth, which is what should morally be true.

Chapter 10: Vector Bundles

• Vector bundles are objects that locally look like product spaces / vector-space "fibers" attached to each point of a manifold. Comb-like picture.

Chapter 11: Cotangent Bundle

• I finally understand what covectors are and what's their point. Cotangent bundle is just the dual of the tangent bundle. Covector takes a tangent vector and returns a number.
• Applications:
  • Gradient of a smooth map, defined as a vector field where (under a given coordinate chart) the components of a function's partial derivatives, is not invariant under change of coordinate chart, so it's ill-defined. But when defined as a covector field, it is well-defined. This makes sense, since a "gradient of a function at a point" is morally an object that you take the inner product with a direction to return a scalar (directional derivative), thus it must be a covector that takes a tangent vector ("direction vector") and returns a number.

Chapter 13: Riemannian Manifold

• Smooth manifolds are metrizable. Why?
  • Broke: Manifold is locally compact Hausdorff second countable. Locally compact Hausdorff => completely regular. By Urysohn metrization theorem, completely regular & second countable => metrizability.
  • Woke: Use the distance metric on the manifold induced by the Riemannian structure, which always exists on manifold. This is much more intuitive.

Then I read some Bredon for Algebraic Topology.

• Turns out, tubular neighborhoods are also useful for algebraic topology: How to show that a sphere $S^n$ is not a retract of a disc $D^{n+1}$?
  • Assume such a retract $f:D^{n+1}\to S^n$ exists. Scale it and compose it appropriately to make it a radial projection ($z\mapsto \frac{z}{||z||}$) near the boundary $S^n$, and f but rescaled in the inside of the disc (easy to do). Smooth out the map in the inside via the Whitney approximation theorem. By Sard's theorem, there is a point $z\in S^n$ that is a regular value of $f$. Its preimage $f^{-1}\left(z\right)$, then, is a 1-dimensional manifold with boundary, where $z$ is the only boundary (via radial projection). This contradicts the classification theorem of compact 1-manifolds which in particular says they have even number of boundary points.
  • From this follows Brouwer's fixed point theorem ($D^n->D^n$ has fixed point), the fact that the sphere $S^n$ is not contractible, etc.
• I should more easily skip sections that I don't understand. I struggled a bit with the first sub-section of the Fundamental Group chapter because it introduced the general notion of $[SX;Y{]}_{\ast }$ (the basepoint-preserving homotopy class of pointed maps $SX\to Y$ where $SX$ refers to the reduced suspension $X\times I/(X\times \partial I\cup \{x_0\}\times I)$), for which the nth homotopy group becomes a special case $[S{S}^{n-1};Y{]}_{\ast }=[S^n;Y{]}_{\ast }$, for which the fundamental group is a special case, which is the only thing that is really needed until like very late in the book.
  • But thanks to muddling through, I think I much better understand this construction and motivation for constructions like the reduced suspension.
• Fundamental group & Covering spaces & Lifting theorems & Deck Transformation
  • Mostly a review. Functors are just really natural objects (no wonder why they came from algebraic topology).
    • Specifically, the functor that transforms $Y$ to $[SX;Y{]}_{\ast }$ and $g:Y\to Z$ to $g_{\#}:[SX;Y{]}_{\ast }\to [SX;Z{]}_{\ast }$ where $f\mapsto g\circ f$. Homotopy groups (including the fundamental group) are a special case of this.
  • Covering spaces are an important tool for calculating fundamental groups. Also covering spaces have a general lifting theorem characterizing when maps can be lifted by the covering map.
    • Deck transformation and fundamental group are resp right / left actions on the fiber of the covering map, and they are commuting actions.
• (Singular) Homology
  • This is new. Has the advantage of not caring about base-points. Weaker than homotopy.
• Hatcher and Bredon are great complements. I saw a lot of anti-recommendations for Hatcher, but I think they're great together.
  • Hatcher provides great intuition (geometric and conceptual) that Bredon just never really talked about. eg geometrically visualizing a deformation retract of a shape onto its skeleton by extruding the map in 3d mirrors the mapping cylinder construction, which is something I learned from Bredon but never (so far) learned the motivation for.
    • Many such examples and expositional niceness that helped reorganize my ontology (eg motivation-of-concept-wise, deformation retract comes prior to mapping cylinder, which comes prior (and motivates) the more general notion of homotopy and retracts. From this, it becomes intuitively clear why eg deformation retract should imply homotopy equivalence. Bredon taught the concepts the opposite way I think.)

There's a couple easy ones, like low rank structure, but I never really managed to get a good argument for why generic symmetries in the data would often be emulatable in real life.

Right, I expect emulability to be a specific condition enabled by a particular class of algorithms that a NN might implement, rather than a generic one that is satisfied by almost all weights of a given NN architecture^[1]. Glad to hear that you've thought about this before, I've also been trying to find a more general setting to formalize this argument beyond the toy exponential model.

Other related thoughts^[2]:

• Maybe this can help decompose the LLC into finer quantities based on where the degeneracy rises from - eg a given critical point's LLC might come solely from the degeneracy in the parameter-function map, some from one of the multiple groups that the true distribution is invariant under at order r, other from an interaction of several groups, etc (sort of Mobius-like inversion)
• And perhaps it's possible to distinguish / measure these LLC components experimentally by measuring how the LLC changes as you perturb the true distribution $q\left(x\right)$ by introducing new / destroying existing symmetries (susceptibilites-style).

1. ^{^}

   This is more about how I conceptually think they should be (since my motivation is to use their non-genericity to argue why certain algorithms should be favored over others), and there are probably interesting exceptions of symmetries that are generically emulatable due to properties of the NN architecture (eg depth).

2. ^{^}

   Some of these ideas were motivated following a conversation with Fernando Rosas.