ILIAD2

12.1 Reviewer abstract

I know a bit about random neural networks but less about computational complexity. I put all my notes in the “abstract” in the hope that it will be useful for others with my background, and because it might expose my errors of reasoning. If you already know about such things, you can skip to the end.

Note: Since there was some notation clash between the original blog post and this paper, I introduce compromise notation. Dunbar’s \(n\) is \(m\).

Neyman and coworkers at the ARC would like to formalise when a neural network has “discovered a way of doing things that we can study” in terms of when an surprising behaviour is susceptible to an easy verification. Their motivation is a computational operationalisation of Tim Gowers’s no coincidence principle

If an apparently outrageous coincidence happens in mathematics, then there is a reason for it.

They see his no-coincidence principle and counter-offer the computational no-coincidence conjecture, (CNCC) which uses the machinery of computational complexity in random function space to convert it into something we can imagine operationalizing.

I don’t come from computational complexity, so I’ll spell the computational no-coincidence conjecture out here for myself and others like me, in the form we need for the paper, with enough abstraction to cover the cases we need but hopefully concrete enough to make it pegadagogic. Suppose we have a universe of functions (circuits, neural networks, Turing machines), and suppose also that this universe come equipped with a probability measure, such that we can draw at random from this universe of functions.

Working with random functions has some annoying technicalities; let’s barrel through them briskly. Because I am an ML guy, I assume we only care about real vector functions which is specific enough for me to keep in my brain, and which has always worked for me so far. Call this universe \(\Omega\). Each function \(f \in \Omega\) is a map from¹ \(\mathbb{R}^{m}\to\mathbb{R}^{m}\) i.e. we have an \(m\)-dimensional input space and an \(m\)-dimensional output space.². We call the probability measure \(\mu\)³ and for technical, probability-theory reasons we want to be certain that there is a \(\sigma\)-algebra defined (“\(\mathcal{F}\)”) over our function space so that things do not go haywire when we attempt to compute probabilities of “things” in this function space. This is generally easy for discrete function spaces but gets tedious for function spaces between vectors over continuous fields like the reals. \(\mathcal{F}\) needs to hold all the sets over which we might attempt to compute probabilities. We wrap these up in probability tuple \((\Omega, \mu, \mathcal{F})\) that lets us do probability stuff in a well-posed way to our universe of functions.

There are various desirable properties for this function space.

1. For our phenomena of interest it should be easy to guesstimate how likely to observe it by chance, i.e. we should be able to bound probabilities of rare events of interest (we will come back to this)
2. We should be require to spend the absolute minimum of time arsing about with \(\sigma\)-algebras and other distracting technical machinery.
3. The function space should map cleanly on to some class of functions we care about (e.g. it should be “easy” to interpret things from our function space as neural nets or Turing machines or what-have-you)

The original blog post addressed these desiderata by dealing with the space of random reversible circuits, i.e. random Boolean functions with some nice structure from \(\{0,1\}^{3n}\to \{0,1\}^{3n}\), i.e. \(m=3n\). These objects are discrete so desideratum (2) is easy. They have neat approximation in terms of random permutations, so that’s (1) dealt with. (3) is addressed by deciding that we care about Boolean circuits for now, and computer scientists are comfortable thinking about the space of Boolean circuits as toy model for all kinds of things like formal logic and… other discrete problems that computer scientists care about.

Let’s fix on the setting of that Neyman blog post: random deep reversible Boolean circuits \(f: \{0,1\}^{3n} \to \{0,1\}^{3n}\). The distribution is concrete — e.g., pick a random sequence of 3-bit reversible gates, arranged in layers that touch all wires, to a given depth. For large enough depth, such circuits behave pseudorandomly: recent results apparently show they achieve strong \(k\)-wise independence.

This motivates modeling a deep random reversible circuit as though it were drawn uniformly from the symmetric group on \(\{0,1\}^{3n}\), \(\mathrm{Sym}(\{0,1\}^{3n})\).⁴ So that solves (1) for us. There are a lot of permutations but we have studied the crap out of them, so that should be manageable. We have a simple, albeit approximate, distribution for circuits here.

To bring us back to the main goal, we are doing this because we want a good notion for the distributions of such functions, which are circuits, which might be something a bit like deductions about the world if we squint at them, so that we can quantify what it means for them to be remarkable and what it might mean to explain a remarkable behaviour \(P\). We are working toward the idea that something is remarkable if it’s behaviour is “outrageously coincidental”, which we can now gloss as very low probability under the null distribution.

We focus on properties \(P\) that talk about the mapping from inputs to outputs across the entire admissible input set. Formally:

\(P(f)\) means : there is no input \(x\) such that \(p_{\text{in}}(x)\) and \(p_{\text{out}}(f(x))\) are both true.

Here \(p_{\text{in}} : \{0,1\}^\ell \to \{\text{True},\text{False}\}\) and \(p_{\text{out}} : \{0,1\}^m \to \{\text{True},\text{False}\}\) are Boolean predicates on inputs and outputs, respectively.⁵ In Neyman’s example, let’s label it \(P^{(0)}\), \(p^0_{\text{in}}(x)\) is “the last \(n\) bits of \(x\) are all 0” and \(p^0_{\text{out}}(y)\) is the same condition on \(y\). The \(P^{(0)}\) in the Neyman blog post says: for every input whose last \(n\) bits are 0, the corresponding output’s last \(n\) bits are not all 0.

Spelling it out again for myself: if there exists even one input in the \(p^0_{\text{in}}\) set whose output also lies in \(p^0_{\text{out}}\), then \(P^{(0)}(f)\) fails. That’s why a property like “output bit \(i > 2n\) is always 1 for all \(p_{\text{in}}\) inputs” is enough to guarantee \(P^{(0)}(f)\) — it eliminates the possibility of the output’s last \(n\) bits all being zero.

Binary strings of length \(3n\), there are \(2^{3n}\) of those. Ones ending in \(n\) zeros? \(2^{2n}\) of those. Permutations \(f\) that happen to never produce a string ending in \(n\) zeros from a string ending in \(n\) zeros? Feels… enumerable. If we model it as something like a it feels like we can estimate the probability of that thing, and in fact the probability that a randomly chosen permutation does that, \[ (1-2^{-n})^{2^{2n}} \approx e^{-2^n} \] In reality, the reversible-circuit distribution isn’t exactly uniform over all permutations — structured outliers exist — but for the purposes of bounding the probability of \(P^{(0)}(f)\) they’re probably negligible, so this simple form will do for the moment. So if a randomly chosen circuit has this property, we’re astonished if \(n\) is bigger than the number of fingers I have.

We’re nearly at the computational no-coincidence conjecture — hang on; what we want to do is use this machinery to capture “structure” in functions that explains outrageous coincidences. We’ll consider an outrageous coincidence for a function \(f\) to be explained by structure if there is an advice string, \(\pi(f)\), such that some verification algorithm \(V(f, \pi(f))\) can quickly check \(P(f)\). “Quickly” means polynomial time in the “size” of \(f\), which can be some count of the number of gates.

The computational no-coincidence conjecture is that

1. For all \(f\) such that \(P(f)\) is true, \(V(f, \pi(f))=\textrm{true}\)
2. For 99% of \(f\) such that \(P(f)\) is false, there is no \(\pi(f)\) that makes \(V(f,\pi(f))=\textrm{true}\).

The 99% thing is to make sure we don’t break the computational complexity hierarchy. We can’t permit ourselves perfect classifiers here.

Meanwhile, (a) does the work of “explaining” structure. It says that if we can always find an advice (let’s gloss that as a compact demonstration that the structure is real) for a fixed, outrageously unlikely property \(P\) (and for a fixed \(\Omega\), etc.), the verifier \(V\), given that advice, has perfect recall (and good specificity) over the set of all random functions. In set diagrams, we claim that the set of functions \(f\) that satisfy \(P(f)\) but for which no proof \(\pi(f)\) will persuade our verifier is empty.

So! A formalisation of the conjecture that all coincidences must be explainable.

import matplotlib.pyplot as plt
import matplotlib as mpl
from matplotlib_set_diagrams import EulerDiagram
from livingthing.matplotlib_style import set_livingthing_style, reset_default_style

set_livingthing_style()

P_true_size = 0.13
V_accepts_size = 0.20
intersection_size = 0.09

subset_sizes = {
    (1, 0): P_true_size - intersection_size,   # A only: "10"
    (0, 1): V_accepts_size - intersection_size,# B only: "01"
    (1, 1): intersection_size,                 # A∩B:   "11"
}

subset_labels = {
    (1, 0): "True\ncoincidences\nmissed",
    (0, 1): "V accepts\nbut P false",
    (1, 1): "Certified\ncoincidences",
}

fig, ax = plt.subplots(figsize=(6, 5))

# Try a cost objective that preserves *relative* sizes nicely.
diagram = EulerDiagram(
    subset_sizes,
    subset_labels=subset_labels,
    set_labels=["P(C) is true", "V accepts"],
    cost_function_objective="relative",   # good for preserving ordering
    verbose=False,
    ax=ax,
)
for key, text_artist in diagram.subset_label_artists.items():
    text_artist.set_color("black")

# Highlight the 10 region directly
artist_10 = diagram.subset_artists[(True, False)]
artist_10.set_facecolor("tab:orange")
artist_10.set_alpha(0.35)
artist_10.set_edgecolor("tab:orange")

# Use shapely centroid for a precise callout
geom_10 = diagram.subset_geometries[(True, False)]
x, y = geom_10.centroid.x, geom_10.centroid.y
ax.annotate(
    "Empty under the conjecture",
    xy=(x, y+0.03),
    xycoords="data",
    xytext=(-15, 65),
    textcoords="offset points",
    ha="right",
    bbox=dict(
      boxstyle="round,pad=0.3", fc="w", ec="0.4"),
    arrowprops=dict(
      arrowstyle="->",
      connectionstyle="arc3,rad=0.2"),
)

ax.set_title("Null model = universe of circuits")
ax.set_axis_off()
plt.tight_layout()
plt.show()
# print(f"savefig.transparent {mpl.rcParams['savefig.transparent']}")
# print(f"figure.facecolor {mpl.rcParams['figure.facecolor']}")
# print(f"axes.facecolor {mpl.rcParams['axes.facecolor"]}")
# print(f"fig patch {fig.get_facecolor(), fig.get_alpha()}")
# print(f"ax patch {ax.get_facecolor(), ax.get_alpha()}")
# print(f"fig facecolor {fig.get_facecolor()}")   # expect rgba with alpha 0
# print(f"ax facecolor {ax.get_facecolor()}")    # expect alpha 0

# (Optional sanity check)
# print("Radii:", diagram.radii)  # different radii reflect set totals A vs B

We can now see what a “structural” explanation of \(P^{(0)}(f)\) might look like. For instance, suppose there exists an output bit in position \(i > 2n\) — i.e., one of the final \(n\) bits — such that for every input whose last \(n\) bits are all zero, the circuit flips that bit from 0 to 1 on the first layer and never changes it again. This ensures that any input in the \(p^0_{\text{in}}\) set (last \(n\) bits zero) will produce an output where bit \(i\) is fixed to 1, so the output’s last \(n\) bits can never all be zero. In other words, \(P(f)\) holds for a simple, structural reason.

In the CNCP world, this is a kind of case where the “advice” \(\pi(f)\) could be very compact — e.g., “bit \(i\) is constant-1 across the entire \(p^0_{\text{in}}\) domain” — and the verifier \(V\) could check it in polynomial time by evaluating the circuit on just the relevant subset of inputs. The conjecture’s claim, I understand, is that all circuits satisfying \(P\) have some succinct, checkable \(\pi\), not just this toy case.

12.2 Review

This paper does a lot of hard work to find criteria and conditions under which wide, deep neural networks give us a tractable null distribution for producing Computational No-Coincidence Conjecture results, and it serves up one such example along with a bunch of useful auxiliary results that would help us manufacture more. As far as I understand the conjecture, this paper mostly adapts it to neural-network domains, which seems useful for making progress. It is, IMO, clearly written, with some rough edges I suspect come from the paper sitting at the edge of two fields with strong opinions about terminology, and thus we may not all agree on how rough those edges are.

I have examined the technical results at a surface level, and they seem credible, but errors could have escaped me.

I have questions.