Notes on maths, machine learning & programmable cryptography
Together with my colleagues Ryan Cao and Kunming Jiang, we re-derived the knowledge soundness of Groth16 as an entertaining exercise. Groth16 is a pairing-based ZK-SNARK. See here for an excellent tutorial on Groth16, or check out the paper itself. R1CS QAPs A witness is $$ \mathbf a = (a_0,\ldots,a_\ell,a_{\ell+1},\ldots,a_m) \in \mathbb{F}^{m+1}, $$ where $a_0,\ldots,a_\ell$ Continue reading…
$$ \newcommand{\ff}[0]{\mathbb{F}} \newcommand{\ffOmega}[0]{\ff^\Omega} \newcommand{\ffOmegaSqrd}[0]{\ff^{\Omega^2}} \newcommand{\fxd}[0]{\ff[X]^{ d}} \newcommand{\fxdHalf}[0]{\ff[X]^{ {d/2}}} \newcommand{\RS}[0]{\mathrm{RS}} \newcommand{\RSd}[0]{\mathrm{RS}_d[\Omega]} \newcommand{\RSdHalf}[0]{\mathrm{RS}_{d/2}[\Omega^2]} \newcommand{\fo}[0]{\ff^\Omega} \newcommand{\eval}[0]{\mathrm{E}}…
(inspired by discussions with my colleagues Giorgos Zirdelis Vishruti Ganesh; any mistakes are my own). Consider the case of multiplication in 2-of-3 Shamir secret sharing. The goal is to compute the product of two secrets $a, b$; the parties should learn the product $ab$, but learn nothing else about $a$ and $b$ than couldn t Continue reading "Re-randomization and information leakage in MPC…
How to Prove False Statements: Practical Attacks on Fiat-Shamir (Khovratovich, Rothblum, Soukhanov; 2025) constructs families of circuits for which the GKR protocol, when made non-interactive by Fiat-Shamir heuristic, will prove false statements. It s a great paper and is so well written that I won t attempt to do better by paraphrasing their constructions. What I d like Continue reading…
$\newcommand{\fxd}[0]{\mathbb{F}[X]^{ d}} \newcommand{\fxdone}[0]{\mathbb{F}[X]^{ d-1}} \newcommand{\RS}[0]{\mathrm{RS}} \newcommand{\drc}[0]{\mathrm{D}_{r, c}\,} \newcommand{\fo}[0]{\ff^\Omega} \newcommand{\eval}[0]{\mathrm{E}}$Here we cover how to build a polynomial commitment scheme (PCS) from the FRI interactive oracle proof of proximity (FRI-IOPP). Specifically, we explain how to reduce an…
Reed-Solomon codes Let $\mathbb{F}$ be a finite field, and write $\mathbb{F}[X]^{ n}$ for the polynomials of degree less than $n$ over $\mathbb{F}$. For any $\omega \in \mathbb{F}^n$, write $$ \epsilon_\omega: \mathbb{F}[X]^{ n} \to \mathbb{F}^n \qquad f \mapsto (f(\omega_i))_{i=1, \dots, n} \quad \forall f$$ for the evaluation map. For any such choice of $n, \omega$ and Continue reading "From…
(The following thought experiment was suggested to me by my colleague Ryan Cao; mistakes and invective are my own). FRI is often described as a low degree test , which suggests that the verifier should reject with high probability if the degree is high. This is not the case, as the simple example below demonstrates. Indeed Continue reading "FRI is a proof of proximity, not a low-degree test"
A polynomial with coefficients in a field and of degree $ n$ is determined by its evaluations at any $n$ distinct points. A common way to see this is via Lagrange interpolation. But what happens in the more general case where the coefficients come from a commutative ring $R$ with $1$? It s easy to see Continue reading "When is a polynomial determined by evaluations? Polynomial interpolation over…
The Vandermonde matrix computes evaluations of polynomials from their coefficients via a matrix-vector product. The Vandermonde matrices are nested, i.e. each Vandermonde matrix is the principal submatrix of any larger Vandermonde matrix that uses (an extension of) the same sequence of evaluation points. For example, here is the (square) Vandermonde matrix for the evaluation points Continue…
We recount here an elementary proof of associativity for the group law on a non-singular elliptic curve. The principal ingredient is the Cayley-Bacharach theorem, which has a neat combinatorial proof using only a corollary of Bézout s theorem (see further reading below). Theorem (Cayley-Bacharach): Let $D, D $ be two cubic curves intersecting in nine distinct points. Continue reading…
The following is intended as an introduction to finite fields for those with already some familiarity with algebraic constructions. It is based on a talk given at our local seminar. A finite field is simply a field with a finite number of elements. An example of a finite field that should already be familiar is Continue reading "A construction of the finite fields (with exercises)"
(This is an extremely useful fact with a straightforward proof. It follows from this, for instance, that any finite extension of a finite field is simple). Let $\mathbb{K}$ be a finite field, so $ \mathbb{K} = p^n$ for some prime $p$ and $n \geq 0$. Denote by $\mathbb{K}^\times$ the multiplicative group consisting of the non-zero elements Continue reading "The multiplicative group of a finite…
While there is famously no royal road to geometry , I believe that there is a royal road to understanding the wonderful logUp, a lookup argument from Starkware s Shahar Papini and Polygon s Ulrich Haböck. We ll take this royal road here. This is significantly more direct than the approach taken in the two papers. The advantage of Continue reading "Understanding LogUp: A Royal Road"
I recently enjoyed a talk by François Charton on Transformers for maths, and maths for transformers (recording). Charton investigates the application of transformer-based translation models to basic mathematical tasks, ranging from basic arithmetic to integer sequence completion and linear algebra. It is important to note that each of these problems is encoded symbolically, not numerically.…
Polynomials are formal sums. So in particular, $\mathbb{K}[x]$ is infinite-dimensional over $\mathbb{K}$, even if e.g. $\mathbb{K} = \mathbb{F}_2$, the field with two elements. This is true even though e.g. $x^2 x$ is the zero function on $\mathbb{F}_2$, as you can check by substituting $0$ and $1$ for $x$. Polynomial functions are functions e.g. on Continue reading "Polynomials over a finite…
This paper (arXiv), authored by Petersen, Borgelt, Kuehne and Deussen, was accepted for NeurIPs 2022. It does one of my favourite things: it learns a discrete structure (in this case, a boolean circuit) via differentiable means. Logic gate networks came up in a recent ZKML discussion as a machine learning paradigm of interest: since boolean Continue reading "Deep Differentiable Logic Gate Networks…
Here is a nice simple example of bilinear pairing on an elliptic curve over a finite field. Different sorts of pairings exist here we ll construct a pairing that coincides with the Weil pairing. For simplicity, our construction will avoid talking about divisors on algebraic curves. Consider the elliptic curve over $\mathbb{F}_7$ defined by the Continue reading "Pairings on elliptic curves: a toy…
The appearance of an elliptic curve from the point of view of the affine $(x,y)$ plane is familiar to us, but leaves us wondering what the curve might look like near the point at infinity (i.e. the identity element $\mathcal{O}$). This is not merely of visual interest, as it allows one to see directly that Continue reading "What does an elliptic curve look like near the point at infinity (the…
Here is a first example of an elliptic curve over a finite field where you can work everything out by hand. Consider the elliptic curve defined by the equation$$ y^2 = (x-1)(x-2)(x-3) $$over the field $\mathbb{F}_5$. Multiplying out the right hand side, we see that (over $\mathbb{F}_5$), the right hand side ( RHS ) is $x^3 Continue reading "A toy elliptic curve over a finite field"
Here are the slides from a talk I gave the Sydney machine learning meetup on Siegelmann and Sontag s paper from 1995 “On the Computational Power of Neural Nets”, showing that recurrent neural networks are Turing complete. It is a fantastic paper, though it is a lot to present in a single talk. I spent some Continue reading "Siegelmann Sontag’s “On the Computational Power of Neural Nets”"
I gave a talk last night at the Berlin machine learning meetup on learning graph embeddings in hyperbolic space, featuring the recent NIPS 2017 paper of Nickel Kiela. Covered are: And here are the slides!
Nickel Kiela had a great paper on embedding graphs in hyperbolic space at NIPS 2017. They work with the Poincaré ball model of hyperbolic space. This is just the interior of the unit ball, equipped with an appropriate Riemannian metric. This metric is conformal, meaning that the inner product on the tangent spaces on Continue reading "Gradient optimisation on the Poincaré disc"
I recently needed to demonstrate this fact to an audience that I could not assume would be familiar with Riemannian geometry, and it took some time to find a way to do it! You can use the HyperRogue game, which takes place on a tiling of the Poincaré disc. The avatar moves across the Poincaré Continue reading "Circle circumference in the hyperbolic plane is exponential in the radius: proof by…
[These are the notes from a talk I gave at the seminar] Hierarchical softmax is an alternative to the softmax in which the probability of any one outcome depends on a number of model parameters that is only logarithmic in the total number of outcomes. In vanilla softmax, on the other hand, the number of Continue reading "Hierarchical Softmax"
In their book Perceptrons (1969), Minsky and Papert demonstrate that a simplified version of Rosenblatt s perceptron can not perform certain natural binary classification tasks, unless it uses an unmanageably large number of input predicates. It is easy to show that with sufficiently many input predicates, a perceptron (even on this type) can perform any classification Continue reading "Minsky…
Suppose you have a model that depends on real-valued parameters, and that you would like to constrain these parameters to be non-negative. For simplicity, suppose the model has a single parameter $a \in \mathbb R$. Let $E$ denote the error function. To constrain $a$ to be non-negative, parameterise $a$ as the square of a real-valued Continue reading "Re-parameterising for non-negativity yields…
Here we derive updates rules for the approximation of a row stochastic matrix by the product of two lower-rank row stochastic matrices using gradient descent. Such a factorisation corresponds to a decomposition $$ p(n m) = \sum_k p(n k) \cdot p(k m) $$ Both the sum of squares and row-wise cross-entropy functions are considered.
I learnt of the 1944 experiment of Heider and Simmel in the Machine Intelligence workshop at NIPS 2016. The experiment involved showing subjects the video below, and asking them to describe what they saw. If you’ve watched the video, you’ll not be surprised to learn that most of the subjects anthropomorphised the geometric objects (i.e. Continue reading "Heider and Simmel misinterpreted"
Non-negative matrix factorisation (NMF) learns to reconstruct samples as a superposition of their constituent parts. In the paper of Lee and Seung (1999) that popularised NMF, this is called a “parts-based” representation. This is illustrated in that paper by applying NMF to encodings of images of faces, where NMF seems to decompose the faces into Continue reading "An LCD digit dataset for…
Having trained a model, it is natural to want to understand how it works. An intuitively appealing approach is to consider data samples that maximise the activation of a hidden unit, and to take the common input features of these samples as an indication of what that unit has learned to recognise. However, as we’ll Continue reading "Don’t interpret linear hidden units, they don’t exist."
Adagrad is a learning regime that maintains separate learning rates for each individual model parameter. It is used, for instance, in GloVe (perhaps incorrectly), in LightFM, and in many other places besides. Below is an example showing that Adagrad models evolve in a manner that depends upon the choice of co-ordinate system (i.e. orthonormal basis) Continue reading "Adagrad depends on the choice…
We show that if the contour lines of a function are symmetric with respect to some rotation or reflection, then so is the evolution of gradient descent when minimising that function. Rotation of the space on which the function is evaluated effects a corresponding rotation of each of the points visited under gradient descent (similarly, Continue reading "Orthogonal transformations and gradient…
I prepared the following one-page overview of the short-time Fourier transform for a recent talk, perhaps it ll be useful to others. For justification of e.g. the conjugate symmetry of the Fourier coefficients or a discussion of aliasing, see here.
We aim to identify the assumptions that are implicit in the sampling of a continuous-time signal and in the subsequent application of the discrete Fourier transform (DFT). In particular, we consider the following questions: When does the sampling of periodic continuous-time signal result in a periodic discrete-time signal? When the resulting discrete-time signal is periodic, Continue reading "The…
Non-negative matrix factorisation (NMF) is a dimension reduction technique that is commonly applied in a number of different fields, for example: in topic modelling, applied to the document x word matrix; in speech processing, applied to the matrix of magnitude spectrograms of framed audio; in recommendation systems, applied to the user x item interaction matrix. Continue reading "Feature scaling…
These are notes from a talk I presented at the seminar on June 22nd. All this material is drawn from Chapter 7 of Bishop s Neural Networks for Pattern Recognition, 1995. In these notes we study the rate of convergence of gradient descent in the neighbourhood of a local minimum. The eigenvalues of the Hessian at Continue reading "Convergence rate of gradient descent"
The paper Neural Word Embeddings as Implicit Matrix Factorization of Levy and Goldberg was published in the proceedings of NIPS 2014 (pdf). It claims to demonstrate that Mikolov s Skipgram model with negative sampling is implicitly factorising the matrix of pointwise mutual information (PMI) of the word/context pairs, shifted by a global constant. Although the paper is Continue reading "Skipgram…
The softmax function provides a convenient parameterisation of the probability distributions over a fixed number of outcomes. Using the softmax, such probability distributions can be learned parametrically using gradient methods to minimise the cross-entropy (or equivalently, the Kullback-Leibler divergence) to observed distributions. This is equivalent to maximum likelihood learning when the…
Steffen Rendle and Christoph Freudenthaler (University of Konstanz), WSDM 2014. PDF The authors present a modification of the Bayesian Pairwise Ranking (BPR) for implicit feedback (i.e. one class) recommendation datasets in which the negative samples are drawn according both to the models current belief and the user/context in question ( adaptive oversampling ). They show that the Continue reading…
We consider the Weighted Approximate-Rank Pairwise- (WARP-) loss, as introduced in the WSABIE paper of Weston et. al (2011, see references), in the context of making recommendations using implicit feedback data, where it has been shown several times to perform excellently. For the sake of discussion, consider the problem of recommending items $i$ to users Continue reading "WARP loss for…
Below are the notes I made to prepare for a short talk given at our seminar on learning distance metrics, and the Mahalanobis distances in particular. We show that the Mahalanobis distances can be parameterised by the positive semidefinite (PSD) matrices or alternatively (in a highly redundant way) by all matrices. The set of PSD Continue reading "Parameterising the Mahalanobis distances for…
Recall that a symmetric matrix $M \in \mathbb{R}^{n \times n}$ is called positive semidefinite ( PSD ) if, for any $x \in \mathbb{R}^n$, we have $x^{T} M x \geqslant 0$. Positive semidefinite matrices occur, for instance, in the study of bilinear forms and as the Gram (or covariance) matrices in probability theory. In the case where $n Continue reading "Visualising the set of 2 2 positive…
In a paper with Adriaan Schakel, we presented controlled experiments for word embeddings using pseudo-words. Performing these experiments in the case of word2vec CBOW showed that, in particular, the vector direction of any particular word changed only moderately when the frequency of the word was varied. Shortly before we released the paper, Schnabel et al presented Continue reading "Does vector…
Below are the notes I prepared for a talk that I gave at our seminar on limiting distributions for (finite-state, time-homogeneous) Markov chains, drawing on PageRank as an example. We see in particular how the random teleport possibility in the PageRank random walk algorithm can be motivated by the theoretical guarantees that result from it: Continue reading "Limiting Distributions of Markov…
Pennington, Socher, Manning, 2014.PDF GloVe trains word embeddings by performing a weighted factorisation of the log of the word co-occurrence matrix. The model scales to very large corpora (Common Crawl 840B tokens) and performs well on word analogy tasks. ModelThe cost function is given by: $\displaystyle \sum_{i, j = 1}^V f(X_{i,j}) (u_i^T v_j + b_i Continue reading "GloVe: Global Vectors for…
We show below that vectors drawn uniformly at random from the unit sphere are more likely to be orthogonal in higher dimensions. In information retrieval and other areas besides, it is common to use the dot product of normalised vectors as a measure of their similarity. It can be problematic that the similarity measure depends Continue reading "Perpendicularity and dimension"
This is the standard, elementary arithmetic proof that the marginal and conditional distributions of the multivariate Gaussian are again Gaussian with parameters expressible in terms of the covariance matrix of the original Gaussian. We use the block multiplication of matrices. I was surprised by how much work is required to show this, and feel moreover Continue reading "Marginal and Conditional…
(We needed this to derive the conditional distribution of a multivariate Gaussian). Consider a matrix product $AB$. Partition the two outer dimensions (i.e. the rows of $A$ and the columns of $B$) and the one inner dimension (i.e. the columns of $A$ and the rows of $B$) arbitrarily. This defines a block decomposition of the Continue reading "Block Multiplication of Matrices"
Presented at NIPS 2014 (PDF) by Dai, Olah, Le and Corrado. Model The authors consider a modified version of the PV-DBOW paragraph vector model. In previous work, PV-DBOW had distinguished words appearing in the context window from non-appearing words given only the paragraph vector as input. In this modified version, the word vectors and the Continue reading "Document Embedding with Paragraph…
Below are notes from a talk on Expectation Maximisation I gave at our ML-learning group. Gaussian mixture models are considered as an example application. The exposition follows Bishop section 2.6 and Andrew Ng s CS229 lecture notes. If you weren t at the seminar, then it is probably better to read one of these instead. Another useful Continue reading "Expectation-Maximisation and Gaussian Mixture…