On Algebraic Constructions of Neural Networks with Small Weights

Threshold functions are commonly treated functions in Boolean analysis and machine learning as they form the basis of neural networks. Threshold functions compute a weighted summation of binary inputs and feed it to a threshold or equality check. If this sum is fed to the former, we call the functions linear threshold functions (see (4)). If it is fed to the latter, we call them exact threshold functions (see (5)). We can write an $n$-input threshold function using the indicator function where $w_{i}$s are integer weights and $b$ is a bias term.

A device computing the corresponding threshold function is called a gate of that type. To illustrate the concept, we define COMPARISON (denoted by COMP) function which computes whether an $n$-bit integer $X$ is greater than another $n$-bit integer Y. The exact counterpart of it is defined as the EQUALITY (denoted by EQ) function which checks if two $n$-bit integers are equal (see Figure 1). For example, we can write the EQ function in the following form.

In general, it is proven that the weights of a threshold function can be represented by $O(n\log{n})$-bits and this is tight [1, 3, 11, 19]. However, it is possible to construct “small” weight threshold circuits to compute any threshold function [2, 8, 12, 23]. This transformation from a circuit of depth $d$ with exponentially large weights in $n$ to another circuit with polynomially large weights in $n$ is typically within a constant factor of depth (e.g. $d+1$ or $3d+3$ depending on the context) [8, 25]. For instance, such a transformation would simply follow if we can replace any ”large“ weight threshold function with “small” weight depth-$2$ circuits so that the new depth becomes $2d$.

It is possible to reduce polynomial size weights into constant weights by replicating the gates that is fed to the top gate recursively (see Figure 2). Nevertheless, this would inevitably introduce a polynomial size blow-up in the circuit size. We emphasize that our focus is to achieve this weight size reduction from polynomial weights to constant weights with at most a constant size blow-up in the circuit size.

For neural networks and learning tasks, the weights are typically finite precision real numbers. To make the computations faster and more power efficient, the weights can be quantized to small integers with a loss in the accuracy of the network output [14, 13]. In practice, given that the neural circuit is large in size and deep in depth, this loss in the accuracy might be tolerated. We are interested in the amount of trade-off in the increase of size and depth while using as small weights as possible. More specifically, our goal is to provide insight to the computation of single threshold functions with large weights using threshold circuits with small weights by relating theoretical upper and lower bounds to the best known constructions.

In this manner, for the ternary weight case ($\{-1,0,1\}$ as in [17]), we give an explicit and optimal size circuit construction for the EQ function using depth-2 circuits. This optimality is guaranteed by achieving the theoretical lower bounds asymptotically up to vanishing terms [16, 20]. We also prove an existential result on the COMP constructions to reduce the weight size on the best known constructions. It is not known if constant weight constructions exist without a polynomial blow-up in the circuit size and an increase in the depth for arbitrary threshold functions.

It seems that choosing powers of two as the weight set is important. In fact, we can expand any arbitrary weight in binary and use powers of two as a fixed weight set for any threshold function [16]. This weight set is a choice of convenience and a simple solution for the following question: How small could the elements of $\mathcal{W}=\{w_{1},w_{2},\cdots,w_{n}\}$ be if $\mathcal{W}$ has all distinct subset sums (DSS)? If the weights satisfy this property, called the DSS property, they can define a bijection between $\{0,1\}^{n}$ and integers. Erdős conjectured that the largest weight $w\in\mathcal{W}$ is upper bounded by $c_{0}2^{n}$ for some $c_{0}>0$ and therefore, choosing powers of two as the weight set is asymptotically optimal. The best known result for such weight sets yields $0.22002\cdot 2^{n}$ and currently, the best lower bound is $\Omega(2^{n}/\sqrt{n})$ [5, 7, 9].

Now, let us consider the following linear equation where the weights are fixed to the ascending powers of two but $x_{i}$s are not necessarily binary. We denote the powers of two by the vector $w_{b}$.

As the weights of $w_{b}$ define a bijection between $n$-bit binary vectors and integers, $w_{b}^{T}x=0$ does not admit a non-trivial solution for the alphabet $\{-1,0,1\}^{n}$. This is a necessary and sufficient condition to compute the EQ function given in (6). We extend this property to $m$ many rows to define EQ matrices which give a bijection between $\{0,1\}^{n}$ and $\mathbb{Z}^{m}$. Thus, an EQ matrix can be used to compute the EQ function in (6) and our goal is to use smaller weight sizes in the matrix.

Let $A\in\mathbb{Z}^{m\times n}$ be an EQ matrix with the weight constraint $W\in\mathbb{Z}$ such that $|a_{ij}|\leq W$ for all $i,j$ and let $R$ denote the rate of the matrix $A$, which is $n/m$. It is clear that any full-rank square matrix is an EQ matrix with $R=1$. Given any $W$, how large can this $R$ be? For the maximal rate, a necessary condition can be proven by Siegel’s Lemma [22].

It is shown that if $m=o(n/\log{nW})$, then any $A\in\mathbb{Z}^{m\times n}$ with weight constraint $W$ admits a non-trivial solution in $\{-1,0,1\}^{n}$ and cannot be an EQ matrix, i.e., $R=O(\log{nW})$ is tight [16]. A similar result can be obtained by the matrix generalizations of Erdős’ Distinct Subset Sum problem [6].

When $m=O(n/\log{nW})$, the story is different. If $m=O(n/\log{n})$, there exists a matrix $A\in\{-1,1\}^{m\times n}$ such that every non-trivial solution of $Ax=0$ satisfies $\max_{j}|x_{j}|\geq c_{0}\sqrt{n}^{\frac{m}{n-m}}$ for a positive constant $c_{0}$. This is given by Beck’s Converse Theorem on Siegel’s Lemma [4].

For an explicit construction, it is possible to achieve the optimal rate $R=O(\log{nW})$ if we allow $W=poly(n)$. This can be done by the Chinese Remainder Theorem (CRT) and the Prime Number Theorem (PNT) [2, 12, 16]. It is known that CRT can be used to define residue codes [18]. For an integer $x$ and modulo base $p$, we denote the modulo operation by $[x]_{p}$, which maps the integer to a value in $\{0,...,p-1\}$. Suppose $0\leq Z<2^{n}$ for an integer $Z$. One can encode this integer by the $m$-tuple $(d_{1},d_{2},\cdots,d_{m})$ where $[Z]_{p_{i}}=d_{i}$ for a prime number $p_{i}$. Since we can also encode $Z$ by its binary expansion, the CRT gives a bijection between $\mathbb{Z}^{m}$ and $\{0,1\}^{n}$ as long as $p_{1}\cdots p_{m}>2^{n}$. By taking modulo $p_{i}$ of Equation (7), we can obtain the following matrix, defined as a CRT matrix:

We have $Z<256$ since $n=8$ and $3\cdot 5\cdot 7\cdot 11=1155$. Therefore, this CRT matrix is an EQ matrix. In general, by the PNT, one needs $O(n/\log{n})$ many rows to ensure that $p_{1}\cdots p_{m}>2^{n}$. Moreover, $W$ is bounded by the maximum prime size $p_{m}$, which is $O(n)$ again by the PNT.

However, it is known that constant weight EQ matrices with asymptotically optimal rate exist by Beck’s Converse Theorem on Siegel’s Lemma [4, 16]. In this paper, we give an explicit construction where $W=1$ and asymptotic efficiency in rate is achieved up to vanishing terms. It is in fact an extension of Sylvester-type Hadamard matrices.

One can verify that the matrix in (10) is an EQ matrix and its rate is twice the trivial rate being the same in (8). Therefore, due to the optimality in the weight size, this construction can replace the CRT matrices in the constructions of EQ matrices.

We can also focus on $q$-ary representation of integers in a similar fashion by extending the definition of EQ matrices to this setting. In our analysis, we always treat $q$ as a constant value.

If $q=2$, then we drop $q$ from the notation and say that the matrix is an EQ matrix. For the $\text{EQ}_{q}$ matrices, the optimal rate given by Siegel’s Lemma is still $R=O(\log{nW})$ and constant weight constructions exist. We give an extension of our construction to $\text{EQ}_{q}$ matrices where $W=1$ and asymptotic efficiency in rate is achieved up to constant terms.

Residue codes are treated as Maximum Distance Separable (MDS) codes because one can extend the CRT matrix by adding more prime numbers to the matrix (without increasing $n$) so that the resulting integer code achieves the Singleton bound in Hamming distance [24]. However, we do not say a CRT matrix is an MDS matrix as this refers to another concept.

Because Definition 4 considers solutions over a restricted alphabet, we denote such matrices as $\textit{RMDS}_{q}$. Remarkably, as $q\rightarrow\infty$, both MDS definitions become the same. Similar to the $\text{EQ}_{q}$ definition, we drop the $q$ from the notation when $q=2$. A CRT matrix is not MDS, however, it can be $\text{RMDS}_{q}$.

We can demonstrate the difference of both MDS definitions by the following matrix. This matrix is an RMDS matrix with EQ rate $2$ and MDS rate $5/4$ because any $4\times 8$ submatrix is an EQ matrix. This is in fact the same matrix in (8) with an additional row with entries $[2^{i-1}]_{13}$ for $i\in\{1,...,8\}$.

Here, the determinant of the $5\times 5$ submatrix given by the first five columns is 0. Thus, this matrix is not an MDS matrix.

In this work, we are interested in $\text{RMDS}_{q}$ matrices. We show that for a constant weight $\text{RMDS}_{q}$ matrix, the MDS rate bound $r=O(1)$ is tight. We also provide an existence result for such $\text{RMDS}_{q}$ matrices where the weight size is bounded by $O(r)$ given that the EQ rate is $O(\log{n})$.

The following is a summary of our contributions in this paper.

• •

  In Section II, we explicitly give a rate-efficient EQ matrix construction with constant entries $\{-1,0,1\}$ where the optimality is guaranteed up to vanishing terms. This solves an open problem in [16] and [20].

• •

  In Section III, we prove that the MDS rate $r$ of an $\text{RMDS}_{q}$ matrix with entries from an alphabet $\mathcal{Q}$ with cardinality $k$ should satisfy $r\leq k^{k+1}$. Therefore, constant weight $\text{RMDS}_{q}$ matrices can at most achieve $r=O(1)$.

• •

  In Section III, provide an existence result for $\text{RMDS}_{q}$ matrices given that $W=O(r)$ and the optimal EQ rate $O(\log{n})$. In contrast, the best known results give $W=O(rn)$ with the optimal EQ rate $O(\log{n})$.

• •

  In Section IV, we apply our results to Circuit Complexity Theory to obtain better weight sizes with asymptotically no trade-off in the circuit size for the depth-2 EQ and COMP constructions, as shown in the Table I.