# Factorizers for Distributed Sparse Block Codes

Michael Hersche, Aleksandar Terzic, Geethan Karunaratne, Jovin Langenegger,
Angéline Pouget, Giovanni Cherubini, Luca Benini, Abu Sebastian, Abbas Rahimi
M. Hersche, G. Karunaratne, J. Langenegger, G. Cherubini, A. Sebastian, and
Abbas Rahimi are with the Hybrid Cloud Research Department, IBM Research-
Zurich, Säumerstrasse 4, 8803 Rüschlikon, Switzerland (email:
abr@zurich.ibm.com). A. Terzic, A. Pouget, and L. Benini are with the
Department of Information Technology and Electrical Engineering, ETH Zürich,
Gloriastrasse 35, 8092 Zürich, Switzerland. M. Hersche, G. Karunaratne, and J.
Langenegger are also with the Department of Information Technology and
Electrical Engineering, ETH Zürich.

###### Abstract

Distributed sparse block codes (SBCs) exhibit compact representations for
encoding and manipulating symbolic data structures using fixed-with vectors.
One major challenge however is to disentangle, or factorize, such data
structures into their constituent elements without having to search through
all possible combinations. This factorization becomes more challenging when
queried by noisy SBCs wherein symbol representations are _relaxed_ due to
perceptual uncertainty and approximations made when modern neural networks are
used to generate the query vectors. To address these challenges, we first
propose a fast and highly accurate method for factorizing a more flexible and
hence generalized form of SBCs, dubbed GSBCs. Our iterative factorizer
introduces a threshold-based nonlinear activation, a conditional random
sampling, and an $\ell_{\infty}$-based similarity metric, and employs circular
convolution and correlation. Its random sampling mechanism in combination with
the search in superposition allows to analytically determine the expected
number of decoding iterations, which matches the empirical observations up to
the GSBC’s bundling capacity. Secondly, the proposed factorizer maintains its
high accuracy when queried by noisy product vectors generated using deep
convolutional neural networks (CNNs). This facilitates its application in
replacing the large fully connected layer (FCL) in CNNs, whereby $C$ trainable
class vectors, or attribute combinations, can be implicitly represented by our
factorizer having $F$-factor codebooks, each with $\sqrt[F]{C}$ fixed
codevectors. We provide a methodology to flexibly integrate our factorizer in
the classification layer of CNNs with a novel loss function. With this
integration, the convolutional layers can generate a noisy product vector that
our factorizer can still decode, whereby the decoded factors can have
different interpretations based on downstream tasks. We demonstrate the
feasibility of our method on four deep CNN architectures over CIFAR-100,
ImageNet-1K, and RAVEN datasets. In all use cases, the number of parameters
and operations are significantly reduced compared to the FCL.

###### Index Terms:

vector-symbolic architectures, sparse block codes, convolutional neural
networks, deep learning.

##  I Introduction

One problem in deep neural representation is that information becomes
entangled in complex ways that may suit a specific task but make it harder to
generalize to slightly different situations. One promising approach is to
factorize representations in which various aspects of knowledge are
represented separately and can then be flexibly recombined to represent novel
experiences [1] with better downstream performance for abstract reasoning
tasks [2]. Solving such factorization problems is also fundamental to
biological perception and cognition, e.g., factoring sensory and spatial
representations [3, 4], factoring time-varying pixel data [5, 6, 7, 8],
factoring a sentence structure [9, 10], and analogical reasoning [11, 12, 13,
14, 15]. Although it is unclear how the biological neural circuits may solve
these factorization problems, one elegant solution is to cast the entanglement
and disentanglement of neurally-encoded information as multiplication and un-
multiplication (factorization) of high-dimensional distributed vectors
representing neural activities. Such wide vectors are naturally presented in
the context of brain-inspired vector-symbolic architectures (VSAs) [16, 17,
18, 19].

VSA is a powerful computing model that is built on a rich algebra supporting a
set of well-defined operations, including multiplicative binding, unbinding,
additive bundling (superposition), permutations, and similarity search that
allow performing symbolic computations on top of random distributed vectors.
In a VSA, all representations—from atoms to composites—are high-dimensional
distributed vectors of the same, fixed dimensionality. An atom in a VSA is a
randomly drawn i.i.d. vector that is dissimilar (i.e., quasi-orthogonal) to
other random vectors with very high probability, a phenomenon aka
concentration of measure [20]. Deep convolutional neural networks (CNNs) have
exploited this abundance of quasi-orthogonal vectors in representation
learning to express new class categories, or new object combinations, with
effective applications in few-shot [21] continual [22] learning, and visual
abstract reasoning [23] tasks. Counterintuitively, the quasi-orthogonal
vectors can still encode semantic information of the objects. For instance, a
black circle with two factors of color and shape can be described by a two-
factor product vector by binding
($\stackMath\mathbin{\stackinset{c}{0ex}{c}{0ex}{\ast}{\bigcirc}}$) its atomic
quasi-orthogonal vectors
($\mathbf{x}_{\mathrm{black}}\stackMath\mathbin{\stackinset{c}{0ex}{c}{0ex}{\ast}{\bigcirc}}\mathbf{x}_{\mathrm{circle}}$).
The resulting product vector is quasi-orthogonal to all other possible vectors
(atomic and composite). An effective VSA-based iterative search method, dubbed
resonator network [24, 25], is proposed to factorize the product vector to its
atomic factors: $\mathbf{x}_{\mathrm{black}}$ and
$\mathbf{x}_{\mathrm{circle}}$. This factorization, or disentanglement, can
reveal the semantic relation between a black circle and a black square
($\mathbf{x}_{\mathrm{black}}\stackMath\mathbin{\stackinset{c}{0ex}{c}{0ex}{\ast}{\bigcirc}}\mathbf{x}_{\mathrm{square}}$)
because both include $\mathbf{x}_{\mathrm{black}}$.

Considering $F$ factors, each factor $f$ having a codebook of $M_{f}$
codevectors, there are $\prod_{f=1}^{F}M_{f}$ possible combinations to be
searched in the product space for factorizing a product vector computed by
multiplicative binding. The resonator network as a powerful dynamical system
avoids such brute-force search through the combinatorial space of possible
solutions by exploiting the _search in superposition_ capability of VSAs.
However, the resonator network suffers from limit cycles and a relatively low
operational capacity (i.e., the ratio between the maximum factorizable problem
size and the required vector dimensionality). To overcome these limitations, a
stochastic in-memory factorizer [26] introduces new nonlinearities and
leverages intrinsic noise of computational memristive devices. As a result, it
increases the operational capacity by at least five orders of magnitude, while
also reducing the convergence time compared to the resonator network.

So far, both resonator networks [24, 25] and stochastic factorizers [26] have
been successfully used to infer the factors of dense bipolar product vectors
(i.e., each vector element is a Rademacher random variable) that are
synthetically generated by binding codevectors. Instead, when inexact, or
noisy, product vectors are generated by a CNN, which mirrors the binding-based
encoding approximately, both approaches face challenges in accurately
factorizing the noisy dense queries. In fact, experimental results indicated
an accuracy drop of up to $16.22\%$ when factorizing noisy bipolar product
queries generated by a small-sized CNN (see Table IV). As an alternative
representational scheme, sparse block codes (SBCs) [27, 28, 29] could offer
better synergy to integrate factorizers with neural networks. SBCs are
biologically plausible [30, 31, 32, 33] and highly amenable to implementation
on emerging neuromorphic hardware [34, 35]. However, the operations and
dynamics currently provided by resonator networks and stochastic factorizers
cannot work with SBCs. Besides, CNNs might also emit noisy SBC query product
vectors, which so far cannot be processed with current SBC’s operations. To
address these challenges, new methods need to be developed that can accurately
factorize noisy product queries for SBCs.

This paper provides the following contributions, which are divided into two
main parts. In Part I, we propose the first iterative block code factorizer
(BCF) that can reliably factorize blockwise distributed product vectors. The
codebooks are binary SBCs [28], which span the product space, while BCF can
factorize generalized sparse block code (GSBC) product vectors, which can be
generated by CNNs. Factorizing binary SBCs is a special case. BCF introduces a
configurable threshold, a conditional sampling mechanism, and a new
$\ell_{\infty}$-based similarity search operations for the first time in the
VSA context. BCF uses circular convolution and correlation [18] as general
binding and unbinding operators in GSBC. During the iterative decoding, the
novel sampling mechanism induces a random search in superposition over the
product space if no confident solution is present. BCF improves the
convergence speed of the state-of-the-art factorizer [26] on a large problem
size of $10^{6}$ by up to 6$\times$. To gain a deeper understanding of BCF’s
iterative search in superposition, we leverage its configurable threshold and
sampling mechanism to configure it as an unconditional sampler that randomly
searches over the product space. This allows us, to analytically determine the
expected number of decoding iterations, which matches with the empirical
observations when operating within the GSBC’s bundling capacity.

In Part II, motivated by the superior performance of BCF, we exloit its
application in reducing the number of parameters in fully connected layers
(FCLs). FCLs are ubiquitous in modern deep learning architectures, and play a
major role by accounting for most of the parameters in various architectures
such as transformers [36, 37], extreme classifiers [38, 39], and CNNs for edge
devices [40]. The FCL’s trainable parameters
$\mathbf{W}\in\mathbb{R}^{D_{i}\times D_{o}}$ can be replaced by a BCF with
$F$ codebooks of fixed parameters, each
$\mathbf{X}^{f}\in\\{0,1\\}^{D_{i}\times\sqrt[F]{D_{o}}}$. The structure of
the codebooks is naturally given when the product space is defined by semantic
attributes (e.g., in RAVEN [41]), or can be arbitrarily defined when no
semantic attributes are provided (e.g., for natural images in ImageNet-1K
[42]). To map sensory inputs to GSBC product vectors, we propose a methodology
to train deep convolutional layers with a novel blockwise additive loss that
can directly use BCF in place of an FCL classifier. Our BCF reduces the total
number of parameters of a wide range of deep CNNs and datasets by 0.5–44.5%
while maintaining a high accuracy within $0$–$4.46\%$ compared to the baseline
CNNs using the large FCL. Our BCF also lowers the computational cost of the
classifier layer by $55.2$–$86.7\%$ with respect to FCLs.

##  II Related Work

###  II-A Factorizing distributed representations

A resonator network iteratively searches over the alternatives for each factor
individually by leveraging a combination of nonlinear dynamics and searching
in superposition [24, 25]. This iterative process converges empirically by
finding correct factors under operational capacity constraints [25]. The
resonator network can accurately factorize dense bipolar distributed vectors
generated by a two-layer perceptron network trained to approximate the
multiplicative binding for colored MNIST digits [24]. Its operational capacity
and convergence speed have been improved by the stochastic factorizer in [26].
However, we observed that the accuracy of both the resonator network and the
stochastic factorizer significantly drops (by as much as 15%) when it is
queried with product vectors generated from deep CNNs processing natural
images (see Table IV). This challenge motivated us to switch to alternative
block code representations, whereby we can retain high accuracy by using our
BCF. Moreover, compared to the state-of-the-art stochastic factorizer, BCF
requires fewer iterations irrespective of the number of factors $F$ (see Table
II). Interestingly, it only requires two iterations to converge for problems
with a search space as large as $10^{4}$.

###  II-B Fixing the final FCL in CNNs

Typically, a learned affine transformation is placed at the end of deep CNNs,
yielding a per-class value used for classification. In this FCL classifier,
the number of parameters is proportional to the number of class categories.
Therefore FCLs constitute a large portion of the network’s total parameters:
for instance, in models for edge devices, FCLs constitute 44.5% of
ShuffleNetV2 [43], or 37% of MobileNetV2 [44] for ImageNet-1K. This dominant
parameter count is more prominent in lifelong continual learning models, where
the number of classes quickly goes over a thousand and further increases over
time [22].

To reduce the training complexity associated with FCLs, various techniques
have been proposed to fix their weight matrix during training. In turn, an FCL
is replaced by a Hadamard matrix [45], or a cheaper Identity matrix [40], or
vertices of a simplex equiangular tight frame [46]. Although partly effective,
due to square-shaped structures, these methods are restricted to problems in
which the number of classes is smaller than or equal to the feature
dimensionality, i.e., $D_{i}$=$D_{o}$. To address this limitation, methods
that simply draw class vectors randomly distributed over a hypersphere [47,
48] were proposed. However, these methods still need to store the individual
class vectors, which imposes the FCL’s conventional cost of
$\mathcal{O}(D_{i}\cdot D_{o})$ for memory storage and compute complexity
during training and inference.

Our BCF with two factors can reduce the memory and compute complexity to
$\mathcal{O}(D_{i}\cdot\sqrt{D_{o}})$. This is done by using randomly-drawn
distributed binary SBCs that form an intermediate product vector space whose
dimensionality ($D_{p}$) is significantly lower than the number of classes
($D_{p}\ll D_{o}$), but high enough such that a large number of classes can be
expressed thanks to the supplied quasi-orthogonality. We show that the product
vector space can be built either at the output of the last convolutional layer
directly (i.e., its dimensionality is set by the feature dimension
$D_{p}$=$D_{i}$), or at the output of a smaller FCL as a projection layer
(i.e., its dimensionality can be chosen). This flexibly enables a trade-off
between the number of removable parameters and obtainable accuracy.

##  III VSA Preliminary

VSAs define operations over (pseudo)random vectors with independent and
identically distributed (i.i.d.) components. Computing with VSAs begins by
defining a basis in the form of a codebook
$\mathbf{X}:=\\{\mathbf{x}_{1},\mathbf{x}_{2},...,\mathbf{x}_{M}\\}:=\\{\mathbf{x}_{i}\\}_{i=1}^{M}$.
If the dimension $D_{p}$ of two randomly drawn vectors of the space is
sufficiently large, they are highly likely to have an almost-zero similarity,
i.e., they are quasi-orthogonal [19]. VSAs use three primary
operations—bundling, binding, and permutation—that form an algebra over the
space of vectors. Combined with a similarity metric, these operations support
various cognitive data structures: variable binding, sequence, and hierarchy.
See [49] for a review.

For example, consider a VSA model based on the bipolar vector space [16],
i.e., $\mathbf{x}\in\left\\{-1,+1\right\\}^{D_{p}}$. One can define binding
and unbinding in this vector space as the Hadamard (i.e., elementwise)
product. The similarity between two vectors in the space is typically measured
using the cosine similarity metric. A possible bundling operation is the
elementwise sum followed by the sign function, setting all negative elements
to $-1$ and the positive to $+1$. To keep representations bipolar, elements
with a sum equal to zero are randomly set to $-1$ or $+1$.

As an alternative, binary sparse block codes (binary SBCs) [28] induce a local
blockwise structure that exhibits ideal variable binding properties [29] and
high information capacity when used in associative memories [50, 51, 52]. In
binary SBCs, the $D_{p}$-dimensional vectors are divided into $B$ blocks of
equal length, $L$=$D_{p}/B$, where only one element per block is set to 1. The
vectors can either be described with a $D_{p}$-dimensional binary SBC vector
(denoted as $\mathbf{x}$), or with a $B$-dimensional offset vector where each
element indicates the index of the nonzero element within each block (denoted
as $\mathbf{\dot{x}}$). The vectors are initialized by randomly setting one
element in each block to 1. The bundling of two or more vectors is defined as
their elementwise addition, followed by a selection function that retains the
sparsity by setting the largest element of each block to 1 and the remaining
elements to 0. The binding of two vectors is the elementwise modulo-$L$ sum of
their offset representation. Similarly, unbinding is defined using the
modulo-$L$ difference. Both binding and unbinding preserve dimensionality and
sparsity. A typical choice for the similarity metric is the normalized dot-
product, which counts the number of overlapping elements of two vectors [53].

##  IV Part I: Factorization of Generalized Sparse Block Codes

TABLE I: Comparison of operations of binary SBCs and our GSBCs. All operations
except for the similarity are applied blockwise.

| Binary SBCs[28] |  GSBCs (ours)
---|---|---
Binding ($\stackMath\mathbin{\stackinset{c}{0ex}{c}{0ex}{\ast}{\bigcirc}}$) |  | Modulo-$L$ sum
---
of nonzero indices
| Blockwise
---
circular convolution
Unbinding ($\oslash$) |  | Modulo-$L$ difference
---
between nonzero indices
| Blockwise
---
circular correlation
Bundling ($\oplus$) | Argmax of sum |  | Sum & normalization
---
Similarity | Dot-product |  |  $\ell_{\infty}$-based sim.
---
or dot-product

Figure 1: Block code factorizer (BCF) for $F$=2 factors. It can factorize
synthetic binary SBC product vectors and GSBC product vectors ($\mathbf{p}$)
which might be the result of a neural network mapping.

This section presents our first contribution: we propose a novel block code
factorizer (BCF) that efficiently finds the factors of product vectors based
on block codes. We first introduce generalized sparse block code (GSBC), a
generalization of the previously presented binary SBC. We present
corresponding binding, unbinding, and bundling operations and a novel
similarity metric based on the $\ell_{\infty}$-distance. We then continue to
the exposition and experimental evaluation of our BCF, which is capable of
fast and accurate factorization of GSBC product vectors.

###  IV-A Generalized sparse block codes (GSBCs)

Like binary SBCs, GSBCs divide the $D_{p}$-dimensional vectors into $B$ blocks
of equal length $L=D_{p}/B$. However, the individual blocks are not restricted
to be binary or sparse. The requirements imposed upon the vectors are that
their elements are in $\mathbb{R}^{+}$, and each block has a unit
$\ell_{1}$-norm. Binary SBCs satisfy both constraints and are valid GSBCs.
Fig. 1 illustrates an example of a binary SBC and a GSBC vector. The blockwise
distribution of the GSBC representation can be interpreted as blockwise
probabilistic mass functions, serving as a proxy for the binary SBC vector in
this example. Such GSBC product vectors can be produced by neural networks
(see Part II). Besides their benefits in the integration with neural networks,
the GSBC representations inside BCF enable more accurate and faster
factorization.

The individual operations for the GSBCs are defined as follows:

#### Binding/Unbinding

We exploit general binding and unbinding operations in blockwise circular
convolution and correlation to support arbitrary block representations.
Specifically, if both operands have blockwise unit $\ell_{1}$-norm, the result
does as well.

#### Bundling

The bundling of several vectors is defined as their elementwise sum followed
by a normalization operation, ensuring that each result block has unit
$\ell_{1}$-norm.

####  $\ell_{\infty}$-based Similarity

We propose a novel similarity measure based on the $\ell_{\infty}$-norm of the
elementwise difference between two GSBC vectors $\mathbf{x}_{i}$ and
$\mathbf{x}_{j}$:

$\displaystyle
s_{\infty}(\mathbf{x}_{i},\mathbf{x}_{j}):=1-\ell_{\infty}(\mathbf{x}_{i}-\mathbf{x}_{j}),$
(1)

with $\ell_{\infty}(\mathbf{a})=\max_{i}|\mathbf{a}[i]|$, where
$\mathbf{a}[i]$ denotes the $i$-th element of a vector $\mathbf{a}$.

For any GSBC vectors $\mathbf{a}$ and $\mathbf{b}$, it holds that
$0\leq\ell_{\infty}(\mathbf{a}-\mathbf{b})\leq 1$. Therefore, our novel
similarity metric satisfies $0\leq s_{\infty}(\mathbf{a},\mathbf{b})\leq 1$,
whereby equality on the right-hand side holds if, and only if,
$\mathbf{a}=\mathbf{b}$. Table I compares the operations of the GSBCs with
respect to the binary SBCs.

###  IV-B Factorization problem

We define the factorization problem for GSBCs and our factorization approach
for two factors. Applying our method to more than two factors is
straightforward; corresponding experimental results will be presented in
Section IV-F.

Given two codebooks111In our experiments, the codebooks consist of binary SBC
codewords, but they could be GSBC vectors too.,
$\mathbf{X}^{1}$:=$\\{\mathbf{x}_{i}^{1}\\}_{i=1}^{M_{1}}$ and
$\mathbf{X}^{2}$:=$\\{\mathbf{x}_{i}^{2}\\}_{i=1}^{M_{2}}$, and a product
vector
$\mathbf{p}$=$\mathbf{x}_{i}^{1}\stackMath\mathbin{\stackinset{c}{0ex}{c}{0ex}{\ast}{\bigcirc}}\mathbf{x}_{j}^{2}$
formed by binding two factors from the codebooks, we aim to find the estimate
factors $\hat{\mathbf{x}}^{1}\in\mathbf{X}^{1}$ and
$\hat{\mathbf{x}}^{2}\in\mathbf{X}^{2}$ that satisfy

$\displaystyle\mathbf{p}=\hat{\mathbf{x}}^{1}\stackMath\mathbin{\stackinset{c}{0ex}{c}{0ex}{\ast}{\bigcirc}}\hat{\mathbf{x}}^{2}.$
(2)

A naive brute-force approach would compare the product vector ($\mathbf{p}$)
to all possible combinations spanned by the product space
$\mathbf{P}=\mathbf{X}^{1}\stackMath\mathbin{\stackinset{c}{0ex}{c}{0ex}{\ast}{\bigcirc}}\mathbf{X}^{2}:=\left\\{\mathbf{x}_{1}^{1}\stackMath\mathbin{\stackinset{c}{0ex}{c}{0ex}{\ast}{\bigcirc}}\mathbf{x}_{1}^{2},\mathbf{x}_{1}^{1}\stackMath\mathbin{\stackinset{c}{0ex}{c}{0ex}{\ast}{\bigcirc}}\mathbf{x}_{2}^{2},...,\mathbf{x}_{M_{1}}^{1}\stackMath\mathbin{\stackinset{c}{0ex}{c}{0ex}{\ast}{\bigcirc}}\mathbf{x}_{M_{2}}^{2}\right\\}$.
This results in a combinatorial search problem requiring $M_{1}\cdot M_{2}$
similarity computations. BCF can significantly reduce computational
complexity.

###  IV-C Block code factorizer (BCF)

Here, we introduce our novel BCF that efficiently finds the factors of product
vectors based on GSBCs, shown in Fig. 1. The product vector decoding begins
with initializing the estimate factors $\hat{\mathbf{x}}^{1}(0)$ and
$\hat{\mathbf{x}}^{2}(0)$ by bundling all vectors from the corresponding
codebooks. Then, the estimate factors are iteratively updated through the
following steps.

Step 1: Unbinding. At the start of iteration $t\geq 1$, the estimate factors
from the previous iteration $t-1$ are unbound from the product vector by using
blockwise circular correlation:

$\displaystyle\tilde{\mathbf{x}}^{1}(t)$
$\displaystyle=\mathbf{p}\oslash\hat{\mathbf{x}}^{2}(t-1)$ (3)
$\displaystyle\tilde{\mathbf{x}}^{2}(t)$
$\displaystyle=\mathbf{p}\oslash\tilde{\mathbf{x}}^{1}(t-1).$ (4)

Step 2: Similarity search. Next, we query the associative memory, which
contains the codebook $\mathbf{X}^{f}$ for the factor $f$, with the unbound
factor estimates. Here, we deploy our novel $\ell_{\infty}$-based similarity
as an effective associative search. At iteration $t$, this yields a vector of
similarity scores $\mathbf{a}^{f}(t)\in\mathbb{R}^{M_{f}}$ for each factor
$f$. The $i$-th element in $\mathbf{a}^{f}(t)$ is computed as:

$\displaystyle\mathbf{a}^{f}(t)[i]=s_{\infty}(\tilde{\mathbf{x}}^{f}(t),\mathbf{x}^{f}_{i}).$
(5)

We observe that using a conventional dot-product similarity causes a
significant performance drop, as shown in Fig. 3.

Step 3: Sparse activation and conditional random sampling. Recent work on
stochastic factorizers [26] demonstrated that applying a threshold function to
the elements of the similarity vector can improve convergence speed and
operational capacity. We deploy a similar idea in our BCF. In this step, the
previously computed similarities are compared against a fixed threshold
$T\in\mathbb{R}^{+}$. Similarity values that are larger than the threshold
propagate forward, whereas lower ones get zeroed out:

$\displaystyle\mathbf{a^{\prime}}^{f}(t)=\mathrm{thresh}(\mathbf{a}^{f}(t);T)$
(6)
$\displaystyle\mathrm{thresh}(\mathbf{a};T)[i]=\begin{cases}\mathbf{a}[i],&\text{if
}\mathbf{a}[i]\geq T\\\ 0,&\text{otherwise}.\end{cases}$ (7)

This nonlinearity allows us to focus on the most promising solutions by
discarding the likely incorrect low-similarity ones. However, thresholding
entails the possibility of ending up with an all-zero similarity vector,
effectively stopping the decoding procedure. To alleviate this issue, upon
encountering an all-zero similarity vector, we randomly generate a subset of
equally weighted similarity values:

$\displaystyle\mathbf{a^{\prime\prime}}^{f}(t)=\begin{cases}\mathbf{a^{\prime}}^{f}(t),&\text{if
}\mathbf{a^{\prime}}^{f}(t)\neq\mathbf{0}\\\
\mathbf{a}_{rand},&\text{otherwise,}\end{cases}$ (8)

where $\mathbf{a}_{rand}\in\mathbb{R}^{M_{f}}$ is a vector in which $A$-many
randomly selected elements are set to $1/A$. In combination with step 4
(weighted bundling), the conditional random sampling given by (8) yields an
equally weighted bundling of $A$ randomly selected codewords.

The novel threshold and conditional sampling mechanisms are simple and
interpretable, yet leading to faster convergence. The stochastic factorizer
[26] relied on various noise instantiations at every decoding iteration. The
necessary stochasticity was supplied from intrinsic noise of phase-change
memory devices and analog-to-digital converters of a computational analog
memory tile. Instead, BCF remains deterministic in the decoding iterations
unless all elements in the similarity vector are zero, in which case it
activates only a single random source. This can be seen as a conditional
_restart_ of BCF using a new random initialization. The conditional random
sampling could be implemented with a single random permutation of a seed
vector in which $A$-many arbitrary values are set to $1/A$. The conditional
random sampling mechanism is also interpretable, in the sense that it allows
to analytically determine the expected number of decoding iterations, subject
to the bundling capacity (see Section IV-G).

Step 4: Weighted bundling. Finally, we generate the next factor estimate
$\hat{\mathbf{x}}^{f}(t+1)$ as the normalized weighted bundling of the
factor’s codevectors:

$\displaystyle\hat{\mathbf{x}}^{f}(t+1)=\frac{(\mathbf{X}^{f})^{T}\mathbf{a}^{\prime\prime
f}(t)}{\sum_{i=1}^{M_{f}}\mathbf{a}^{\prime\prime f}(t)[i]}.$ (9)

The codevectors $\\{\mathbf{x}_{i}^{1}\\}_{i=1}^{M_{1}}$ are GSBCs with unit
$\ell_{1}$-norm blocks; hence, dividing the weighted bundling by the sum of
the weights yields valid GSBCs.

Step 5: Convergence detection. The iterative decoding is repeated until BCF
converges or a predefined maximum number of iterations ($N$) is reached. We
define the maximum number of iterations such that BCF does at most as many
similarity searches as the brute-force approach [26]:

$\displaystyle N:=\frac{\prod_{f=1}^{F}M_{f}}{\sum_{f=1}^{F}M_{f}}.$ (10)

The convergence detection mechanism is based on an additional, fixed
threshold. Decoding is stopped as soon as both similarity vectors
($\mathbf{a}^{1}(t)$ and $\mathbf{a}^{2}(t)$) contain an element that exceeds
a predefined detection threshold value ($T_{c}$)[26]. We set it to
$T_{c}$=$0.8$ for synthetic product vectors and $T_{c}$=$0.5$ for noisy
product vectors from deep neural networks.

###  IV-D Hyperparameter optimization

This section explains the methodology for finding optimal BCF hyperparameters
to achieve high accuracy and fast convergence. The optimal configuration is
denoted by $\mathbf{c^{\star}}=(T^{\star},A^{\star})$, corresponding to the
optimal threshold and sampling width. As an automatic hyperparameter search
method, we employ Bayesian optimization.

The loss function is defined as the error rate given by the percentage of
incorrect factorizations out of 512 randomly selected product vectors. To put
a strong emphasis on fast convergence, we reduced the maximal number of the
iterations to $N^{\prime}=0.05N$ for all Bayesian optimization runs. The error
rate is an unknown function of the hyperparameters, modeled as a Gaussian
process with a radial basis function kernel. Hyperparameter sampling is done
using the expected improvement acquisition function.

For each problem ($F$, $D_{p}$, $\prod_{f=1}^{F}M_{f}$, $B$), we run five
separate hyperparameter searches, each of which tests 200 different
hyperparameter combinations restricted to the domains $A\in[0,M_{f}]$ and
$T\in[0,1]$. Finally, we select the hyperparamters with the lowest error rate
at the default maximum number of iterations ($N$).

Fig. 2 shows the resulting threshold ($T$) and sampling width ($A$) over
various problem sizes for $D_{p}$=512, $B$=4, and $F$=2. For a range of
problem sizes ($10^{3}$–$10^{5}$), BCF does not require the threshold and
sampling dynamics: it sets the threshold and the sampling width to 0. For
larger problem sizes ($>$$10^{5}$), the threshold $T$ grows with the problem
size. This can be explained by the fact that querying larger codebooks is
likely to activate more codevectors, which will be bundled together. As such,
we expect a higher interference between likely incorrect low-similarity
solutions and promising high-similarity solutions. A higher threshold
effectively reduces the number of bundled vectors, reducing interference.
Similarly, the sampling width ($A$) grows until a problem size of 4,000,000,
where it sharply declines. The sharp decline was observed for all investigated
problem settings ($F$, $D_{p}$, $B$) and might stem from the limited bundling
capacity.

(a) Optimal threshold ($T^{*}$).

(b) Optimal sampling width ($A^{*}$).

Figure 2: Threshold and sampling width of Bayesian optimization for
$D_{p}$=512, $B$=4, and $F$=2.

###  IV-E Experimental setup

Figure 3: Factorization accuracy (left) and number of iterations (right) of
various BCF configurations on synthetic (i.e., exact) product vectors for
different problem sizes ($\prod_{f=1}^{F}M_{f}$). We set $D_{p}$=$512$,
$F$=$2$, and $B$=$4$. The maximum operational capacity is marked with a cross.
Problem sizes exceeding the operational capacity are marked with dashed lines
which face an accuracy lower than 99%. BCF configured with binary SBC
operations (in blue) cannot solve any of the displayed problem sizes at the
required accuracy.

We evaluate the performance of our novel BCF on randomly selected synthetic
product vectors. For each problem ($F$, $D_{p}$, $\prod_{f=1}^{F}M_{f}$, $B$),
we assess the factorization accuracy and the number of iterations by averaging
over 5000 experiments. In each experiment, we randomly select one vector from
each of the $F$-many codebooks, bind the selected vectors together to form a
product vector, then use the product vector as the input into BCF. In this
section, the queries are always binary SBCs. In contrast, the representations
inside BCF (i.e., factor estimates at any step of the decoding loop) do not
have this restriction imposed upon them unless specified otherwise. The
operational capacity is defined as the largest problem size for which BCF
achieves an accuracy higher than $99\%$ [25].

###  IV-F Comparative results

Fig. 3 compares the accuracy (left) and the number of iterations (right) of
various BCF configurations with $D_{p}$=$512$ and $F$=$2$. Dotted lines
indicate a less than $99\%$ factorization accuracy. Starting with binary SBC
vectors and the dot-product similarity metric, we can see that this BCF
configuration fails to solve any problem of size larger than $10^{3}$
accurately. The operational capacity increases to $4.2\cdot 10^{3}$ when
relaxing the sparsity constraint of binary SBCs by allowing for GSBC
representations inside BCF. However, the convergence speed is still low,
requiring almost as many searches as the brute-force approach. The
introduction of the $\ell_{\infty}$-based similarity increases the operational
capacity by more than an order of magnitude. We can also notice a drastic
reduction in the number of iterations necessary for converging to the correct
solution. For problem sizes up to $10^{4}$, BCF needs only $2$ iterations to
converge, the minimum possible number of iterations to detect convergence
reliably. However, as the problem size goes beyond $1.2\cdot 10^{5}$, BCF
starts encountering limit cycles and spurious fixed points, which hinder its
convergence to the correct solution [25]. To this end, we introduce the
threshold nonlinearity coupled with conditional random sampling. With these
new dynamics, BCF further increases the operational capacity by over an order
of magnitude to $5\cdot 10^{6}$.

Figure 4: Effect of the dimension $D_{p}$ on number of iterations for BCF with
$B$=4, $F$=2 (left) and $F$=3 (right).  Figure 5: Effect of the number of
blocks $B$ on number of iterations for BCF with $D$=512, $F$=2 (left) and
$F$=3 (right).

Next, we analyze BCF’s decoding performance for a varying number of blocks
($B$), vector dimensions ($D_{p}$), and numbers of factors ($F$). Fig. 4 shows
the number of iterations of BCF for $F$=2 (left) and $F$=3 (right) factors
when varying the vector dimension. For both two and three factors, the
operational capacity and convergence speed increase with growing vector
dimensionality. As we move from two to three factors, the operational capacity
remains approximately the same while the number of decoding iterations
increases. However, an increase in the number of iterations does not directly
lead to higher computational cost as each iteration requires fewer search
operations ($F\cdot\sum_{f}M_{f}$) for larger $F$ due to the $F$-root
dependence of $M_{f}$. For example, at $D_{p}$=$512$ and
$\prod_{f=1}^{F}M_{f}$=$10^{6}$, BCF at $F=2$ requires, on average, $15.73$
iterations corresponding to a total of $31,460$ searches, whereas at $F=3$ it
requires, on average, $85.17$ iterations and $25,551$ searches.

Fig. 5 shows BCF’s performance for a fixed $D_{p}$ while varying the number of
the blocks ($B$) for two and three factors. For a very small number of blocks
($B$=2), the operational capacity lies at approximately $10^{3}$ for both
$F$=2 and $F$=3. The operational capacity increases to around $5\cdot 10^{6}$
when $B$=4. Further increasing the number of blocks ($B\geq 8$) exhibits an
operational capacity beyond $10^{8}$, the largest problem size we measured.
The convergence speed peaks at $B$=4 and $B$=8 blocks, and gradually declines
as the vectors get denser. Overall, the experimental results shown in Fig. 4
and Fig. 5 demonstrate the broad applicability of our BCF: it accurately
solves factorization problems within the computational constraints for a wide
range of problem sizes, block sizes ($B\geq 4$), and number of factors
($F\in\\{2,3\\}$).

Finally, we compare our BCF with the state-of-the-art stochastic factorizer
[26] operating with dense bipolar vectors. We fix the problem size to $10^{6}$
and compare the number of iterations for three configurations according to
those featured in [26], namely $F$=2 with $D_{p}$=1024, $F$=3 with
$D_{p}$=1536, and $F$=4 with $D_{p}$=2048. We configure our BCF with $B$=4
blocks. Table II summarizes the results. Both factorizers achieve $>99\%$
accuracy across all configurations, whereby our BCF requires up to 6$\times$
fewer iterations.

TABLE II: Comparison between stochastic factorizer [26] and our BCF at problem size $10^{6}$.  |  | Number of iterations
---|---|---
$F$ | $D$ | Dense bipolar [26] | BCF ($B$=$4$)
2 | 1024 | 68.47 | 11.16
3 | 1536 | 72.48 | 52.91
4 | 2048 | 157.17 | 89.05

###  IV-G Ablation study

This section provides more insights into BCF’s two main hyperparameters: the
threshold ($T$) and the sampling width ($A$).

#### Effect of sampling width in an unconditional random sampler

The sampling width ($A$) determines how many codevectors will be randomly
sampled and bundled in case the threshold similarity activation results in an
all-zero vector. Intuitively, we expect too low sampling widths to result in a
slow walk over the space of possible solutions. Alternatively, suppose the
sampling width is too large (e.g., larger than the bundling capacity). In that
case, we expect high interference between the randomly sampled codevectors to
hinder the accuracy and convergence speed due to the limited bundling
capacity.

Figure 6: Number of iterations when BCF is configured as an unconditional
random sampler with varying sampling width ($A$). We set $B$=4, $F$=2, and
$M_{1}$=$M_{2}$=$M$=$1000$.

To experimentally demonstrate this effect, we run BCF with $F$=2 in an
operational mode that corresponds to unconditional random vector sampling.
Concretely, we fix the sampling width ($A$), generate the initial guess as a
bundling of $A$-many randomly selected codevectors, and set both the
sparsification threshold ($T$) and the convergence detection threshold
($T_{c}$) to the inverse sampling width ($1/A$). With this configuration, we
expect BCF to execute a random walk over the solution space with sampling
width determining the number of solutions that are simultaneously evaluated.
If the procedure samples the correct solution and the interference from
sampled incorrect solutions is low, the correct factor triggers the threshold,
and the factorization stops. As a result, at every iteration, we test
$M_{f}\cdot A^{F-1}$ combinations per factor $f$. The expected number of
iterations for this procedure is:

$\displaystyle\mathbb{E}[t]=\frac{\prod_{f=1}^{F}M_{f}}{(\sum_{f=1}^{F}M_{f})\cdot
A^{F-1}},$ (11)

where the numerator reflects the overall problem size, and the denominator the
number of combinations the random sampler tests per iteration. With $F$=2
factors and codebooks of equal size $M_{1}$=$M_{2}$=$M$, the expected number
of iterations equals $M/(2A)$.

Fig. 6 shows experimental results with this factorizer mode for $F$=2,
$M$=$1000$, varying $D_{p}$ between 512 and 1024. The expected number of
iterations corresponds to the expression $M/(2A)$. All presented
configurations reach $>99\%$ accuracy, but in a different number of
iterations. For small sampling widths, the empirical results match the
expectation. As the sampling width increases, the discrepancy between the
empirical and theoretical results grows, more evidently at the smaller
dimensions. The discrepancy could stem from the bundling capacity, i.e., the
number of retrievable elements, which decreases with a shrinking dimension.

#### Effect of sampling width ($A$) in BCF

In this set of experiments, we do not restrict the threshold to be $1/A$.
Instead, we run a grid search for each sampling width over threshold values
($T$) in $[0,1]$ and use the optimal value in our benchmarks.

Table III shows how the accuracy and the number of iterations change as we
vary the sampling width ($A$) in $\\{10,50,100,200,500,1000\\}$. As expected,
there is a sweet spot for sampling width, which in this setting lies at around
100. Smaller values of sampling widths do not negatively impact the accuracy,
but convergence speed does decrease. As we increase the sampling width beyond
100, the accuracy drops. Moreover, with a fine-tuned threshold value, we can
factorize product vectors significantly faster (15.73 iterations) than when
BCF is run in the unconditional random sampling mode (38.87 iterations).

TABLE III: BCF performance when varying the sampling width ($A$).
$D_{p}$=512, $F$=2, $M_{1}$=$M_{2}$=$1000.$

A | $T^{*}$ | Accuracy | Num. Iters.
---|---|---|---
10 | 0.00602 | 99.4% | 39.16
50 | 0.00641 | 99.4% | 17.86
100 | 0.00641 | 99.4% | 15.73
500 | 0.00722 | 98.6% | 24.25
1000 | 0.00441 | 46.9% | 276.78

#### Similarity metric

(a) $\ell_{\infty}$-based similarity. (b) Dot-product similarity.

Figure 7: Log-scale histograms of $\ell_{\infty}$-based and the dot-product
similarity values. BCF with $D_{p}$=512, $B$=4, $F$=2, $M_{1}$=$M_{2}$=200,
and $T$=0.

Here, we compare the $l_{\infty}$-based similarity with the dot-product
similarity by considering the similarity distributions of the associative
memory search inside BCF. We select a problem size that cannot be solved by
the dot-product similarity, but can be solved by the $s_{\infty}$-based
similarity. The threshold nonlinearity and conditional random sampling are
disabled. For $F$=2, $B$=4, and $D_{p}$=512, one such problem size is $4\cdot
10^{4}$. We execute the decoding for two iterations and show the resulting
histogram in Fig. 7. The $l_{\infty}$-based similarity tends to induce sparse
activations: most similarities have a value of 0 and will have no effect on
the weighted bundling of codevectors. Conversely, the dot-product similarity
exhibits a wider distribution with almost no zero-valued similarities.
Finally, the $l_{\infty}$-based similarity was able to find the correct
solution (similarity value of 1), whereas the dot-product similarity was not.

##  V Part II: Effective Replacement of Large FCLs with Block Code Factorizers

Figure 8: Replacement of a large FCL with our BCF (b) without or (c) with a
projection $\mathbf{W^{\prime}}$.

So far, we have applied our BCF on synthetic (i.e., exact) product vectors. In
this section, we present our second contribution, where we expand the
application of our BCF to classification tasks in deep CNNs. This is done by
replacing the large final FCL in CNNs with our BCF, as shown in Fig. 8.
Instead of training $C$ hyperplanes for $C$ classes, embodied in the trainable
weights $\mathbf{W}\in\mathbb{R}^{D_{i}\times D_{o}}$ of the FCL, where
$C$=$D_{o}$, we represent the classes with a fixed binary SBC product space
$\mathbf{P}\in\\{0,1\\}^{D_{p}\times D_{o}}$. The product space requires only
$B\cdot\sum_{f=1}^{F}M_{f}$ fixed integer values to be stored with the binary
SBC offset notation accounting for 256 values on ImageNet-1K with $B$=$4$ and
$M_{1}$=$M_{2}$=32. We provide two variants to interface the
$D_{i}$-dimensional output features of the CNN’s final convolutional layer
with our BCF, depicted in Fig. 8b and Fig. 8c. In the first variant, BCF is
directly interfaced with the CNN’s output features; hence, the dimensionality
becomes $D_{p}$=$D_{i}$. The second variant uses an intermediate, trainable
projection $\mathbf{W^{\prime}}\in\mathbb{R}^{D_{i}\times D_{p}}$, where
$D_{p}\ll D_{o}$, The number of parameters is significantly reduced in both
variants, by $D_{o}\cdot D_{i}$ without the projection, and by
$(D_{o}-D_{p})\cdot D_{i}$ with the projection.

###  V-A Casting classification as a factorization problem

First, we describe how the classification problem can be transformed into a
factorization problem. The codebooks and product space are naturally provided
if a class is a combination of multiple attribute values. For example, the
RAVEN dataset contains different objects formed by a combination of shape,
position, color, and size. Hence, we define four codebooks ($\mathbf{X}^{1}$,
$\mathbf{X}^{2}$, $\mathbf{X}^{3}$, and $\mathbf{X}^{4}$) where the size of
each codebook ($M_{f}$) corresponds to the number of values the individual
attribute can have [23] (e.g., the codebook $\mathbf{X}^{1}$ representing five
shapes has $M_{1}$=$5$ elements). The resulting product space is
$\mathbf{P}$=$\mathbf{X}^{1}\stackMath\mathbin{\stackinset{c}{0ex}{c}{0ex}{\ast}{\bigcirc}}\mathbf{X}^{2}\stackMath\mathbin{\stackinset{c}{0ex}{c}{0ex}{\ast}{\bigcirc}}\mathbf{X}^{3}\stackMath\mathbin{\stackinset{c}{0ex}{c}{0ex}{\ast}{\bigcirc}}\mathbf{X}^{4}$.

If no such semantic information is available, the codebooks and product space
are chosen arbitrarily. When targeting two factors, we first define a product
space
$\mathbf{P}$=$\mathbf{X}^{1}\stackMath\mathbin{\stackinset{c}{0ex}{c}{0ex}{\ast}{\bigcirc}}\mathbf{X}^{2}$
that contains $M_{1}\cdot M_{2}$ unique quasi-orthogonal product vectors. The
size of the product space is set to the number of classes $C$, such that each
product vector in $\mathbf{P}$ can be assigned to a unique class. For example,
for representing the $C$=$100$ classes in the CIFAR-100 dataset, we define a
product space with size $100$ using two codebooks of size
$M_{1}$=$M_{2}$=$\sqrt{C}$=$10$. Then, the product vector
$\mathbf{p}_{1}:=\mathbf{x}^{1}_{1}\stackMath\mathbin{\stackinset{c}{0ex}{c}{0ex}{\ast}{\bigcirc}}\mathbf{x}^{2}_{1}$
belongs to “class 1” and
$\mathbf{p}_{100}:=\mathbf{x}^{1}_{10}\stackMath\mathbin{\stackinset{c}{0ex}{c}{0ex}{\ast}{\bigcirc}}\mathbf{x}^{2}_{10}$
to “class 100”222If $\sqrt{C}$ is not an integer, we take the ceiling of
$\sqrt{C}$..

###  V-B Training CNNs with blockwise cross-entropy loss

After defining the product space, we train a function $f_{\theta}$ (e.g., a
CNN) with trainable parameters $\theta$ to map the input data (e.g., images)
to the target product vectors of the corresponding classes. Fig. 9a
illustrates the training procedure. Given a labeled training sample
$(\mathbf{I},y)$ containing the input image $\mathbf{I}\in\mathbb{R}^{c\times
h\times w}$ and the target label $y$, we first pass the image through the
function $f_{\theta}$, yielding $\mathbf{q}=f_{\theta}(\mathbf{I})$. Next, we
generate the target product vector by mapping the target label $y$ to the
factor indices ($f^{1}$ and $f^{2}$) and forming the corresponding product
$\mathbf{p}=\mathbf{x}^{1}_{f^{1}}\stackMath\mathbin{\stackinset{c}{0ex}{c}{0ex}{\ast}{\bigcirc}}\mathbf{x}^{2}_{f^{2}}$.

A typical loss function for binary sparse target vectors is the binary cross-
entropy loss in connection with the sigmoid nonlinearity. However, we
experienced a significant classification drop when using the binary cross-
entropy loss; e.g., the accuracy of MobileNetV2 on the ImageNet-1K dataset
dropped below 1% when using this loss function. To this end, we propose a
novel blockwise loss that computes the sum of per-block categorical cross-
entropy loss (CEL). For each block $b$, we extract the $L$-dimensional block
$\mathbf{q}_{b}:=\mathbf{q}[(b-1)L+1:bL]$ from the output features
$\mathbf{q}$ and the target index $\mathbf{\dot{p}}[b]$. Then, the blockwise
CEL is defined as:

Figure 9: Training and inference with BCF.

$\displaystyle\mathcal{L}\left(\mathbf{q},\dot{\mathbf{p}},s\right)=\frac{1}{B}\sum_{b=1}^{B}\mathcal{L}_{\mathrm{CEL}}\left(s\cdot\mathbf{q}_{b},\mathbf{\dot{p}}[b]\right),$
(12)

where $\mathcal{L}_{\mathrm{CEL}}$ is the categorical CEL, which combines the
softmax activation with the negative log-likelihood loss, and $s$ a trainable
inverse softmax temperature for improved training [45, 48, 54]. The loss
function $\mathcal{L}$ is minimized by batched stochastic gradient descent
(SGD).

###  V-C BCF-based inference

The BCF-based inference is illustrated in Fig. 9b. We pass a query image
($\mathbf{I}$) through the CNN, yielding the query product ($\mathbf{q}$),
which can be interpreted as a “noisy” version of the ground-truth product
vector $\mathbf{p}$. We then search for the product vector
$\hat{\mathbf{p}}\in\mathbf{P}$ with the highest similarity to $\mathbf{q}$.
One baseline is to compute the similarity between $\mathbf{q}$ and each
product vector in $\mathbf{P}$ in a brute-force manner; however, this requires
many similarity computations and the storage of each product vector in
$\mathbf{P}$. Instead, we search for the closest product vector by factorizing
the query product vector using BCF, shown in Fig. 9b.

We pass the output of the CNN through a blockwise softmax function with an
inverse softmax temperature $s_{F}$, which shapes and normalizes the blockwise
distribution of the query vector. The optimal inverse softmax temperature was
found to be $s_{F}$=$1.5$, based on a grid search on the ImageNet-1K training
set with MobileNetV2, and applied for all architectures.

TABLE IV: Comparison of approaches which replace the final FCL without any
projection layer ($D_{i}$=$D_{p}$). We report the average accuracy $\pm$ the
standard deviation over five runs with different seeds for the baseline and
our GSBCs.

|  |  | FCL replacement approach
---|---|---|---
|  |  |  |  | Bipolar dense | Our BCF ($B$=$4$)
| Dataset/
---
architecture
($D_{i}$, $D_{o}$) |  | Baseline
---
acc.
| Had.
---
acc.
| Id.
---
acc.
| BF
---
acc.
| Res.
---
acc.∗
| Avg.
---
iter.∗
| BF
---
acc.
| Fac.
---
acc.
| Avg.
---
iter.
| Param.
---
saving$\downarrow$
| FCL comp.
---
saving$\downarrow$
ImageNet-1K |  |  |  |  |  |  |  |  |  |  |  |
ShuffleNetV2 | (1024, 1k) | $69.22^{\pm 0.20}$ | $68.02$ | $67.62$ | $66.17$ | $54.54$ | $150$ | $65.09^{\pm 0.10}$ | $64.76^{\pm 0.13}$ | $7$ | $44.5\%$ | $55.2\%$
MobileNetV2 | (1280, 1k) | $71.57^{\pm 0.13}$ | $71.30$ | $70.72$ | $70.64$ | $60.83$ | $150$ | $70.00^{\pm 0.07}$ | $69.76^{\pm 0.13}$ | $6$ | $37.6\%$ | $61.6\%$
ResNet-18 | (512, 1k) | $70.39^{\pm 0.11}$ | N/A | N/A | $68.65$ | $54.17$ | $150$ | $68.44^{\pm 0.08}$ | $68.00^{\pm 0.07}$ | $7$ | $4.4\%$ | $55.2\%$
ResNet-50 | (2048, 1k) | $76.21^{\pm 0.28}$ | $75.30$ | $74.65$ | $75.80$ | $67.98$ | $150$ | $76.34^{\pm 0.04}$ | $76.25^{\pm 0.07}$ | $5$ | $8.0\%$ | $68.0\%$
CIFAR-100 |  |  |  |  |  |  |  |  |  |  |  |
ResNet-18 | (512, 100) | $78.10^{\pm 0.31}$ | $77.21$ | $76.56$ | $76.63$ | $71.15$ | $150$ | $77.31^{\pm 0.15}$ | $77.19^{\pm 0.17}$ | $2$ | $0.5\%$ | $60.0\%$
RAVEN |  |  |  |  |  |  |  |  |  |  |  |
ResNet-18 | (512, 4.2k) | $99.88^{\pm 0.01}$ | N/A | N/A | $99.89$ | $94.92$ | $45$ | $99.87^{\pm 0.01}$ | $99.82^{\pm 0.02}$ | $16$ | $16.2\%$ | $86.7\%$
p-value | – | – | $0.125$ | $0.125$ | $0.063$ | $0.031$ | – | $0.094$ | $0.063$ | – | – | –

  * Acc.= Accuracy (%); N/A= Not applicable; Had.= Reproduced Hadamard [45]; Id.= Reproduced Identity [40]; BF= Brute-force; Res.= Resonator nets [24]; Fac.= Block code factorizer whereby it sets $F$=$2$ for ImageNet-1K and CIFAR-100, and $F$=$4$ for RAVEN. p-value is determined by signed Wilcoxon test with respect to baseline accuracy.

  * ∗ Maximum number of iterations was increased to $N$=$150$ for better performance in the resonator nets that leads to 10$\times$ more operations than the brute-force search.

###  V-D Experimental Setup

#### Datasets

We evaluate our new method on three image classification benchmarks.
ImageNet-1K. The ImageNet-1K dataset [42] is a large-scale image
classification benchmark with colored images from $C$=$1000$ different
classes. The training set contains over $1.2$ M samples, and the validation
set includes $50,000$ samples ($50$ per class), all with a resolution of
$224\times 224$.
CIFAR-100. The CIFAR-100 dataset [55] contains colored images with a
resolution of $32\times 32$ from $C$=$100$ classes. The dataset provides 500
samples for training and 100 for testing per class.
RAVEN. The RAVEN dataset [41] contains Raven’s progressive matrices tests with
gray-scale images with a resolution of $160\times 160$. A test provides 8
context and 8 answer panels, each containing objects with the following
attributes: position, type, size, and color. In this work, we exclusively
target the recognition of single objects inside the panels. Therefore, we
extract all panels with single objects from the center, 2x2 grid, and 3x3 grid
constellation. The extraction gives us a dataset with $136,321$ panels for
training, $45,144$ for validation, and $45,144$ for testing. We combine the
positions from the different constellations, yielding 14 unique positions: 1
for the center, 4 for the 2x2 grid, and 9 for the 3x3 grid. Overall, this
dataset contains $C$=$4200$ attribute combinations (14 positions $\times$ 5
types $\times$ 6 sizes $\times$10 colors).

#### Architectures

ShuffleNetV2 [43], MobileNetV2 [44], ResNet-18, and ResNet-50 [56] serve as
baseline architectures. In addition to our BCF-based replacement approach, we
evaluate each architecture with the bipolar dense resonator [24, 25], the
Hadamard readout [45], and the Identity readout [40]. For the FCL replacement
strategies without the intermediate projection layer, we removed the
nonlinearity and batch norm of the last convolutional layer of all CNN
architectures. This significantly improved the accuracy of all replacement
strategies; e.g., the accuracy of MobileNetV2 with the Identity replacement
improved from $60.28\%$ to $70.72\%$ when removing the batch norm and the
ReLU6 of the last convolutional layer. All other architectural blocks remained
the same, including shortcuts in the last block of the ResNet-18 and
ResNet-50. To apply the Identity approach where $D_{i}\neq D_{o}$, we used an
identity matrix that reads out the first $D_{o}$ elements of the output
feature vector and ignores the remaining $D_{i}-D_{o}$ elements. We could not
adjust the dimension $D_{i}$ since it would have required additional
adaptations in the CNNs, e.g., a downsampling layer in the shortcut connection
of ResNet-50.

#### Training setup

The CNN models are implemented in PyTorch (version 1.11.0) and trained and
validated on a Linux machine using up to 4 NVIDIA Tesla V100 GPUs with 32 GB
memory. We train all CNN architectures with SGD with architecture-specific
hyperparameters, described in Appendix -A. Overall, for each architecture, we
use the same training configuration for the baseline and all replacement
strategies (i.e., Hadamard, Identity, resonator networks, and our BCF). We
repeat the main experiments five times with a different random seed and report
the average results and standard deviation to account for training
variability.

TABLE V: Classification accuracy when interfacing the last convolution layer
with BCF using a projection layer with $D_{p}$=$512$.

| Baseline | Our BCF ($D_{p}$=$512$, $B$=$4$)
---|---|---
| Dataset/
---
architecture
($D_{i}$, $D_{o}$) | # Param. | Acc. |  | BF
---
acc.
| Fac.
---
acc.
| Avg.
---
iter.
| Param.
---
saving$\downarrow$
| FCL comp.
---
saving$\downarrow$
ImageNet-1K |  |  |  |  |  |  |  |
ShuffleNetV2 | (1024, 1k) |  $2.3$ M | $69.22^{\pm 0.20}$ | $68.67^{\pm 0.11}$ | $68.41^{\pm 0.14}$ | $6$ | $21.7\%$ | $29.6\%$
MobileNetV2 | (1280, 1k) |  $3.4$ M | $71.57^{\pm 0.13}$ | $71.69^{\pm 0.11}$ | $71.49^{\pm 0.10}$ | $6$ | $18.4\%$ | $33.4\%$
ResNet-18 | (512, 1k) |  $11.5$ M | $70.39^{\pm 0.11}$ | $69.57^{\pm 0.17}$ | $69.19^{\pm 0.13}$ | $6$ | $2.2\%$ | $10.4\%$
ResNet-50 | (2048, 1k) |  $25.5$ M | $76.21^{\pm 0.28}$ | $76.72^{\pm 0.06}$ | $76.56^{\pm 0.08}$ | $5$ | $3.9\%$ | $40.8\%$
RAVEN |  |  |  |  |  |  |  |
ResNet-18 | (512, 4.2k) |  $13.3$ M | $99.88^{\pm 0.01}$ | $99.88^{\pm 0.00}$ | $99.85^{\pm 0.02}$ | $16$ | $14.2\%$ | $78.6\%$
p-value | – | – | – | $0.465$ | $0.313$ | – | – | –

###  V-E Comparative Results

Table IV compares the classification accuracy of the baseline with various
replacement approaches without projection, namely Hadamard [45], Identity
[40], bipolar dense [24], and our BCF. On ImageNet-1K, BCF reduces the total
number of parameters of deep CNNs by 4.4%–44.5%333The relative parameter
reduction depends on the size of the overall network and the final FCL, which
we replace with our method., while maintaining a high accuracy within $2.39\%$
across the majority of architectures, with the only exception of ShuffleNetV2
showing $4.46\%$ accuracy drop due to its very large FCL accounting for 44.5%
of total parameters. Our BCF matches the brute-force accuracy within $0.44\%$
in all architectures while requiring only $5$–$7$ iterations on average,
despite the query product vectors from the CNNs being “noisy.” Inspired by
extremely fast convergence on the synthetic experiments (see Fig. 3), we could
show that BCF can match the brute-force accuracy within $0.54\%$ when only
allowing up to $N$=$3$ iterations (see Appendix -D). This does not hold for
the bipolar dense resonators showing significant accuracy drop (up to
$16.22\%$), compared to the brute-force search, despite allowing a high number
of iterations ($N$=$150$) and conducting extensive hyperparameter tuning
across various loss functions, including arcface [57] (see Appendix -B).

TABLE VI: Classification accuracy (%) on ImageNet-1K for the baseline and the
block code-based replacement approaches ($F$=$2$) with different number of
blocks ($B$). Lower number of blocks ($B$) results in higher accuracy.

|  | ShuffleNetV2 | MobileNetV2 | ResNet-18 | ResNet-50
---|---|---|---|---|---
| Classification
---
approach
B | BF | Fac. | BF | Fac. | BF | Fac. | BF | Fac.
Baseline | – | $69.22^{\pm 0.20}$ | – | $71.57^{\pm 0.13}$ | – | $70.39^{\pm 0.11}$ | – | $76.21^{\pm 0.28}$ | –
GSBCs | 4 | $65.09^{\pm 0.10}$ | $64.76^{\pm 0.13}$ | $70.00^{\pm 0.07}$ | $69.76^{\pm 0.13}$ | $68.43^{\pm 0.08}$ | $68.00^{\pm 0.07}$ | $76.34^{\pm 0.04}$ | $76.25^{\pm 0.07}$
8 | $64.30$ | $63.65$ | $69.53$ | $69.20$ | $67.90$ | $67.76$ | $76.69$ | $76.48$
16 | $63.22$ | $62.04$ | $69.34$ | $68.83$ | $67.02$ | $64.98$ | $76.52$ | $76.27$
32 | $61.96$ | $59.74$ | $69.12$ | $68.35$ | $65.09$ | $61.39$ | $76.08$ | $75.62$

On CIFAR-100, BCF matches the baseline within $0.91\%$ with only 2 average
iterations; while on RAVEN, it requires a slightly higher number of iterations
($16$) due to the larger number of factors ($F$=$4$) and the asymmetric
codebook sizes. Across all datasets and architectures, our BCF reduces the
large FCL’s computational cost by $55.2$–$86.7\%$.

Considering the other FCL replacement approaches, Hadamard consistently
outperforms Identity. However, both the memory and computation requirements of
Hadamard are $\mathcal{O}(D_{i}\cdot D_{o})$, while our BCF reduces both of
them to $\mathcal{O}(D_{i}\cdot\sqrt{D_{o}})$, as $F$=$2$ and $N$=$3$ are
constant. Hence, Hadamard is ineffective for a large value of $D_{o}$.
Moreover, Identity is only competitive when $D_{i}$ is within the range of
$D_{o}$ (MobileNetV2 and ShuffleNetV2); for other combinations, either it is
not applicable (ResNet-18 where $D_{i}<D_{o}$), or ineffective (ResNet-50
where $D_{i}>D_{o}$).

We compare our approach to weight pruning techniques, which usually sparsify
the weights in all layers, whereas we focus on the final FCL due to its
dominance in compact networks. Such pruning can be similarly applied to
earlier layers in addition to our method. Pruning the final FCL of a
pretrained MobileNetV2 with iterative magnitude-based pruning [58] yields
significant accuracy degradation as soon as more than 95% of the weights are
set to zero. In contrast, our method remains accurate (69.76%) in high
sparsity regimes (i.e., 99.98% zero elements). See Appendix -F for more
details.

Furthermore, we compare our results with [48], which randomly initialize the
final FCL and keep it fixed during training. On CIFAR-100 with ResNet-18, they
could show that fixing the final FCL layer even slightly improves the accuracy
compared to the trainable FCL ($75.9\%$ vs. $74.9\%$; see their Table 1).
However, our BCF-based approach outperforms their fixed FCL approach
($77.19\%$) while reducing the memory requirements and the FCL compute cost.

Table V shows the performance of our BCF when using the projection layer
($D_{p}$=$512$). The projection layer improves the BCF-based accuracy in all
benchmarks, especially in cases where the BCF replacement approach faced
challenges (i.e., ShuffleNetV2). Overall, we reduce the total number of
parameters by 2.2%–21.7% while maintaining the accuracy within $1.2\%$,
compared to the baseline with trainable FCL.

###  V-F Ablation Study

We give further insights into the BCF-based classification by analyzing the
effect of the number of blocks, the projection dimension, the number of
factors, and the initialization of the CNN weights.

#### Number of blocks $B$

Table VI shows the brute-force and BCF classification accuracy for block codes
with different numbers of blocks. The brute-force accuracy degrades as the
number of blocks ($B$) increases, particularly in networks where the final FCL
is dominant (e.g., ShuffleNetV2). These experiments demonstrate that deep CNNs
are well-matched with very sparse vectors (e.g., $B$=4), and motivated us to
devise a BCF that can factorize product vectors with such a low number of
blocks. Our BCF achieves an accuracy within $0.43\%$ of the brute-force
accuracy for product vectors with $B$=4. For a larger number of blocks ($B\geq
8$), our BCF matches the brute-force accuracy within $3.7\%$. Note that BCF’s
hyperparameters were exclusively tuned for $B$=$4$, and then applied for other
blocks. Hence, BCF for $B$=$\\{8,16,32\\}$ could be further improved by
hyperparameter tuning.

#### Projection dimension $D_{p}$

We varied the projection dimension ($D_{p}$) from 128 (high reduction) to 1000
(no reduction since $D_{p}$=$D_{o}$) for MobileNetV2 on ImageNet-1K. With an
extremely low dimension ($D_{p}$=$128$), BCF shows a $2.86\%$ accuracy drop
compared to the baseline with trainable FCL while saving $32.8\%$ of the
parameters. When going to higher dimensions (e.g., $D_{p}$=768), BCF even
surpasses the baseline accuracy while saving $8.7\%$ of the parameters. See
Appendix -C.

#### Number of factors $F$

So far, we have evaluated BCF with two factors, each having codebooks of size
$M_{1}$=$M_{2}$=$32$ on the ImageNet-1K dataset. We demonstrate BCF’s
capability with $F$=$3$ codebooks of size $M_{f}$=$10$, which achieves similar
accuracy while requiring a higher number of iterations (11 vs. 6) than
$F$=$2$. However, since each iteration requires fewer search operations for
$F$=$3$ ($30$ vs. $64$ searches), the overall saving in computational
complexity of the FCL remains similar. See Appendix -E.

#### Initialize ResNet-18 with pretrained weights

Finally, we show that the training of BCF-based CNNs can be improved by
initializing their weights from a model that was pretrained on ImageNet-1K.
Table VII shows the positive impact of pretraining of ResNet-18 (with
projection) on ImageNet-1K. The pretraining improves the accuracy of BCF by
$0.62\%$, compared to the random initialization, when keeping the number of
epochs the same. Moreover, when reducing the number of training epochs to $75$
and $50$, BCF still yielded accurate predictions ($68.83\%$ and $68.05\%$).
This experiment shows that our BCF-based method can be applied with reduced
training cost if a pretrained model is available.

TABLE VII: Loading a pretrained ResNet-18 model improves accuracy and training
time. Classification accuracy (%) on ImageNet-1K using BCF with ResNet-18
(with projection $D_{p}$=$512$, $B$=$4$, $F$=$2$).

|  | Pretrained
---
model
| Training
---
epochs
| BF
---
acc.
| Fac.
---
acc.
Baseline | ✗ | 100 | $70.39^{\pm 0.11}$ | –
GSBCs | ✗ | 100 | $69.57^{\pm 0.17}$ | $69.10^{\pm 0.14}$
GSBCs | ✓ | 50 | $68.50^{\pm 0.14}$ | $68.05^{\pm 0.08}$
✓ | 75 | $69.21^{\pm 0.09}$ | $68.83^{\pm 0.07}$
✓ | 100 | $70.08^{\pm 0.16}$ | $69.72^{\pm 0.15}$

##  VI Conclusion

We proposed an iterative factorizer for generalized sparse block codes. Its
codebooks are randomly distributed high-dimensional binary sparse block codes,
whose number of blocks can be as low as four. The multiplicative binding among
the codebooks forms a quasi-orthogonal product space that represents a large
number of class categories, or combinations of attributes. As a use-case for
our factorizer, we also proposed a novel neural network architecture that
replaces trainable parameters in an FCL (aka classifier) with our factorizer,
whose reliable operation is verified by accurately classifying/disentangling
noisy query vectors generated from various CNN architectures. This quasi-
orthogonal product space not only reduces the memory footprint and
computational complexity of the networks working with it, but also can reserve
a huge representation space to prevent future classes/combinations from coming
into conflict with already assigned ones, thereby further promoting
interoperability in a continual learning setting.

## References

  * [1] I. Higgins, L. Matthey, A. Pal, C. Burgess, X. Glorot, M. Botvinick, S. Mohamed, and A. Lerchner, “beta-VAE: Learning basic visual concepts with a constrained variational framework,” in _International Conference on Learning Representations_ , 2017.
  * [2] S. van Steenkiste, F. Locatello, J. Schmidhuber, and O. Bachem, _Are Disentangled Representations Helpful for Abstract Visual Reasoning?_ , 2019.
  * [3] J. R. Manns and H. Eichenbaum, “Evolution of declarative memory,” _Hippocampus_ , vol. 16, no. 9, pp. 795–808, 2006.
  * [4] J. C. Whittington, T. H. Muller, S. Mark, G. Chen, C. Barry, N. Burgess, and T. E. Behrens, “The tolman-eichenbaum machine: Unifying space and relational memory through generalization in the hippocampal formation,” _Cell_ , vol. 183, no. 5, pp. 1249–1263.e23, 2020.
  * [5] R. Memisevic and G. E. Hinton, “Learning to Represent Spatial Transformations with Factored Higher-Order Boltzmann Machines,” _Neural Computation_ , vol. 22, no. 6, pp. 1473–1492, 06 2010.
  * [6] Y. Burak, U. Rokni, M. Meister, and H. Sompolinsky, “Bayesian model of dynamic image stabilization in the visual system,” _Proceedings of the National Academy of Sciences_ , vol. 107, no. 45, pp. 19 525–19 530, 2010.
  * [7] C. F. Cadieu and B. A. Olshausen, “Learning intermediate-level representations of form and motion from natural movies,” _Neural Computation_ , vol. 24, no. 4, pp. 827–866, 04 2012.
  * [8] A. G. Anderson, K. Ratnam, A. Roorda, and B. A. Olshausen, “High-acuity vision from retinal image motion,” _Journal of Vision_ , vol. 20, no. 7, pp. 34–34, 07 2020.
  * [9] P. Smolensky, “Tensor product variable binding and the representation of symbolic structures in connectionist systems,” _Artificial Intelligence_ , vol. 46, pp. 159–216, 1990.
  * [10] R. Jackendoff, _Foundations of Language: Brain, Meaning, Grammar, Evolution_. Oxford University Press, 2002.
  * [11] J. E. Hummel and K. J. Holyoak, “Distributed Representations of Structure: A Theory of Analogical Access and Mapping,” _Psychological Review_ , vol. 104, no. 3, pp. 427–466, 1997.
  * [12] P. Kanerva, “Dual Role of Analogy in the Design of a Cognitive Computer,” in _Advances in Analogy Research: Integration of Theory and Data from the Cognitive, Computational, and Neural Sciences_ , 1998, pp. 164–170.
  * [13] ——, “Pattern Completion with Distributed Representation,” in _International Joint Conference on Neural Networks_ , 1998, pp. 1416–1421.
  * [14] T. A. Plate, “Analogy Retrieval and Processing with Distributed Vector Representations,” _Expert Systems: The International Journal of Knowledge Engineering and Neural Networks_ , vol. 17, no. 1, pp. 29–40, 2000.
  * [15] R. W. Gayler and S. D. Levy, “A Distributed Basis for Analogical Mapping: New frontiers in Analogy Research,” in _New frontiers in Analogy Research, Second International Conference on the Analogy_ , 2009, pp. 165–174.
  * [16] R. W. Gayler, “Vector Symbolic Architectures Answer Jackendoff’s Challenges for Cognitive Neuroscience,” in _Joint International Conference on Cognitive Science (ICCS/ASCS)_ , 2003, pp. 133–138.
  * [17] T. A. Plate, “Holographic reduced representations,” _IEEE Transactions on Neural Networks_ , vol. 6, no. 3, pp. 623–641, 1995.
  * [18] ——, _Holographic Reduced Representations: Distributed Representation for Cognitive Structures_. Center for the Study of Language and Information, Stanford, 2003.
  * [19] P. Kanerva, “Hyperdimensional Computing: An Introduction to Computing in Distributed Representation with High-Dimensional Random Vectors,” _Cognitive Computation_ , vol. 1, no. 2, pp. 139–159, 2009.
  * [20] M. Ledoux, _The Concentration of Measure Phenomenon_. American Mathematical Society, 2001.
  * [21] G. Karunaratne, M. Schmuck, M. Le Gallo, G. Cherubini, L. Benini, A. Sebastian, and A. Rahimi, “Robust high-dimensional memory-augmented neural networks,” _Nature Communications_ , vol. 12, no. 1, Apr 2021.
  * [22] M. Hersche, G. Karunaratne, G. Cherubini, L. Benini, A. Sebastian, and A. Rahimi, “Constrained few-shot class-incremental learning,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , June 2022, pp. 9057–9067.
  * [23] M. Hersche, M. Zeqiri, L. Benini, A. Sebastian, and A. Rahimi, “A neuro-vector-symbolic architecture for solving Raven’s progressive matrices,” _Nature Machine Intelligence_ , 2023.
  * [24] E. P. Frady, S. J. Kent, B. A. Olshausen, and F. T. Sommer, “Resonator networks, 1: An efficient solution for factoring high-dimensional, distributed representations of data structures,” _Neural Computation_ , vol. 32, no. 12, pp. 2311–2331, 2020.
  * [25] S. J. Kent, E. P. Frady, F. T. Sommer, and B. A. Olshausen, “Resonator networks, 2: Factorization performance and capacity compared to optimization-based methods,” _Neural Computation_ , vol. 32, no. 12, pp. 2332–2388, 2020.
  * [26] J. Langenegger, G. Karunaratne, M. Hersche, L. Benini, A. Sebastian, and A. Rahimi, “In-memory factorization of holographic perceptual representations,” _Nature Nanotechnology_ , 2023.
  * [27] D. A. Rachkovskij and E. M. Kussul, “Binding and normalization of binary sparse distributed representations by context-dependent thinning,” _Neural Computation_ , vol. 13, no. 2, pp. 411–452, 2001.
  * [28] M. Laiho, J. H. Poikonen, P. Kanerva, and E. Lehtonen, “High-dimensional computing with sparse vectors,” in _2015 IEEE Biomedical Circuits and Systems Conference (BioCAS)_ , 2015.
  * [29] E. P. Frady, D. Kleyko, and F. T. Sommer, “Variable binding for sparse distributed representations: Theory and applications,” _IEEE Transactions on Neural Networks and Learning Systems_ , 2021.
  * [30] N. Y. Masse, G. C. Turner, and G. S. Jefferis, “Olfactory information processing in drosophila,” _Current Biology_ , vol. 19, no. 16, Aug 2009\.
  * [31] Y. Cui, S. Ahmad, and J. Hawkins, “The htm spatial pooler—a neocortical algorithm for online sparse distributed coding,” _Frontiers in Computational Neuroscience_ , vol. 11, 2017.
  * [32] D. Willshaw, O. P. Buneman, and H. C. Longuet-Higgins, “Non-holographic associative memory,” _Nature_ , vol. 222, no. 5197, pp. 960–962, Jun 1969\.
  * [33] B. A. Olshausen and D. J. Field, “Natural image statistics and efficient coding,” _Network: Computation in Neural Systems_ , vol. 7, no. 2, pp. 333–339, 1996.
  * [34] G. Bent, C. Simpkin, Y. Li, and A. Preece, “Hyperdimensional computing using time-to-spike neuromorphic circuits,” in _International Joint Conference on Neural Networks (IJCNN)_ , 2022.
  * [35] A. Renner, Y. Sandamirskaya, F. T. Sommer, and E. P. Frady, “Sparse vector binding on spiking neuromorphic hardware using synaptic delays,” in _International Conference on Neuromorphic Systems (ICONS)_ , 2022.
  * [36] G. Lample, A. Sablayrolles, M. A. Ranzato, L. Denoyer, and H. Jegou, “Large memory layers with product keys,” in _Advances in Neural Information Processing Systems_ , 2019.
  * [37] M. Geva, R. Schuster, J. Berant, and O. Levy, “Transformer feed-forward layers are key-value memories,” in _Conference on Empirical Methods in Natural Language Processing_ , 2021.
  * [38] J. Liu, W.-C. Chang, Y. Wu, and Y. Yang, “Deep learning for extreme multi-label text classification,” in _International ACM SIGIR Conference on Research and Development in Information Retrieval_ , 2017.
  * [39] A. Ganesan, H. Gao, S. Gandhi, E. Raff, T. Oates, J. Holt, and M. McLean, “Learning with holographic reduced representations,” in _Advances in Neural Information Processing Systems_ , 2021.
  * [40] Z. Qian, T. L. Hayes, K. Kafle, and C. Kanan, “Do we need fully connected output layers in convolutional networks?” _arXiv preprint arXiv:2004.13587_ , 2020.
  * [41] C. Zhang, F. Gao, B. Jia, Y. Zhu, and S.-C. Zhu, “Raven: A dataset for relational and analogical visual reasoning,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , June 2019\.
  * [42] J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei, “Imagenet: A large-scale hierarchical image database,” in _IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2009, pp. 248–255.
  * [43] N. Ma, X. Zhang, H.-T. Zheng, and J. Sun, “Shufflenet v2: Practical guidelines for efficient cnn architecture design,” in _Proceedings of the European Conference on Computer Vision (ECCV)_ , September 2018.
  * [44] M. Sandler, A. Howard, M. Zhu, A. Zhmoginov, and L.-C. Chen, “Mobilenetv2: Inverted residuals and linear bottlenecks,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , June 2018.
  * [45] E. Hoffer, I. Hubara, and D. Soudry, “Fix your classifier: the marginal value of training the last weight layer,” in _International Conference on Learning Representations_ , 2018.
  * [46] Z. Zhu, T. Ding, J. Zhou, X. Li, C. You, J. Sulam, and Q. Qu, “A geometric analysis of neural collapse with unconstrained features,” in _Advances in Neural Information Processing Systems_ , 2021.
  * [47] P. Mettes, E. van der Pol, and C. Snoek, “Hyperspherical prototype networks,” _Advances in Neural Information Processing Systems_ , vol. 32, 2019.
  * [48] G. Shalev, G. L. Shalev, and Y. Keshet, “Redesigning the classification layer by randomizing the class representation vectors,” _arXiv preprint arXiv:2011.08704_ , 2021.
  * [49] D. Kleyko, D. A. Rachkovskij, E. Osipov, and A. Rahimi, “A survey on hyperdimensional computing aka vector symbolic architectures, part i: Models and data transformations,” _ACM Comput. Surv._ , may 2022.
  * [50] V. Gripon and C. Berrou, “Sparse neural networks with large learning diversity,” _IEEE transactions on neural networks_ , vol. 22, no. 7, pp. 1087–1096, 2011.
  * [51] A. Knoblauch and G. Palm, “Iterative retrieval and block coding in autoassociative and heteroassociative memory,” _Neural Computation_ , vol. 32, no. 1, pp. 205–260, 2020.
  * [52] K. Schlegel, P. Neubert, and P. Protzel, “A comparison of vector symbolic architectures,” _Artificial Intelligence Review_ , vol. 55, no. 6, pp. 4523–4555, 2022.
  * [53] D. Kleyko, A. Rahimi, D. A. Rachkovskij, E. Osipov, and J. M. Rabaey, “Classification and recall with binary hyperdimensional computing: Tradeoffs in choice of density and mapping characteristics,” _IEEE Transactions on Neural Networks and Learning Systems_ , vol. 29, no. 12, 2018.
  * [54] T. R. Scott, A. C. Gallagher, and M. C. Mozer, “von mises-fisher loss: An exploration of embedding geometries for supervised learning,” in _Proceedings of the IEEE/CVF International Conference on Computer Vision (CVPR)_ , 2021.
  * [55] A. Krizhevsky, “Learning multiple layers of features from tiny images,” _University of Toronto_ , 2009.
  * [56] K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2016, pp. 770–778.
  * [57] J. Deng, J. Guo, N. Xue, and S. Zafeiriou, “Arcface: Additive angular margin loss for deep face recognition,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2019, pp. 4690–4699.
  * [58] M. Zhu and S. Gupta, “To prune, or not to prune: exploring the efficacy of pruning for model compression,” _arXiv preprint arXiv:1710.01878_ , 2017\.
  * [59] I. Loshchilov and F. Hutter, “Sgdr: Stochastic gradient descent with warm restarts,” _arXiv preprint arXiv:1608.03983_ , 2016.
  * [60] T. Zhuo and M. Kankanhalli, “Solving raven’s progressive matrices with neural networks,” _arXiv preprint arXiv:2002.01646_ , 2020.
  * [61] X. Zhang, R. Zhao, Y. Qiao, X. Wang, and H. Li, “Adacos: Adaptively scaling cosine logits for effectively learning deep face representations,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , June 2019.
  * [62] J. Schwarz, S. Jayakumar, R. Pascanu, P. E. Latham, and Y. Teh, “Powerpropagation: A sparsity inducing weight reparameterisation,” _Advances in Neural Information Processing Systems_ , vol. 34, pp. 28 889–28 903, 2021.

This appendix provides more details on the effective replacement of large FCLs
using the proposed BCF.

###  -A Overall CNN training setup

We train all CNN architectures with SGD with architecture-specific
hyperparameters, summarized in Table A1. The training setups for the different
networks mainly differ in the chosen learning rate schedule. ShuffleNetV2 was
trained for $400$ epochs using a learning rate initially set to 0.5 and
linearly decreased towards $0$ at every epoch. MobileNetV2 was trained with a
cosine learning rate schedule [59], where the learning rate is decreased based
on a cosine function (single cycle) from $0.04$ to $0$ within 150 epochs. An
additional warmup period of 5 epochs was used. ResNet-18 and ResNet-50 were
trained with an exponential decaying learning rate schedule. For training the
ResNet-18 on the RAVEN dataset, we started with a pre-trained model from the
ImageNet-1k dataset [60].

###  -B Loss functions for the bipolar dense resonator network integration

We evaluated different loss functions for replacing FCL with the bipolar dense
resonator networks. A standard cross entropy loss operating on the cosine
similarities between the query vector and the fixed bipolar vectors, scaled
with a trainable inverse softmax temperature $s$ [45], yielded good brute-
force accuracies but significant drops when integrating the resonator
networks. For example, when replacing the final FCL of ShuffleNetV2 on
ImageNet-1K, we achieved a brute-force accuracy of $66.14\%$ but a much lower
resonator network accuracy ($44.88\%$). Alternative adaptive cosine-based loss
functions, such as AdaCos [61], were ineffective too.

Instead, we found that the fixed but configurable arcface [57] loss function
is the most suitable for the resonator network integration. Arcface computes
the angle of the target logit, adds an additive angular margin ($m$) to the
target angle, and gets the target logit back again by the cosine function.
Finally, the logits are rescaled by a fixed scaling factor ($s$) before
applying the cross entropy loss. To find the optimal hyperparameters ($s,m$),
we conducted a grid search across a wide range of configurations
($s\in\\{1,10,30,50,70\\},m\in\\{0.0,0.05,0.1,0.15\\}$). On ImgeNet-1K, the
search yielded the parameters ($70,0.1$) for ShuffleNetV2, ($50,0.1$) for
MobileNetV2, ($70,0.1$) for ResNet-18, and ($70,0.1$) for ResNet-50. The
optimal parameters for the remaining datasets with ResNet-18 were ($30,0.1$)
on CIFAR-100 and ($10,0.1$) on RAVEN. The large margin separation
significantly increased the resonator network-based accuracy, e.g., by
$9.66\%$ for ShuffleNetV2 on ImageNet-1K.

TABLE A1: Hyperparamters for CNN training.

|  |  |  |  | Learning rate schedule
---|---|---|---|---|---
| Dataset/
---
architecture
Ep. | Bs. | Mmt. | Wd. |  | Init.
---
value
Type |  | Decay
---
rate
| Step
---
size
ImageNet-1K |  |  |  |  |  |  |  |
ShuffleNetV2 | 400 | 2048 | 4e-5 | 0.9 | 0.5 | lin | – | –
MobileNetV2 | 150 | 256 | 4e-5 | 0.9 | 0.04 | cos | – | –
ResNet-18 | 100 | 256 | 1e-4 | 0.9 | 0.1 | exp | 0.1 | 30
ResNet-50 | 100 | 256 | 1e-4 | 0.9 | 0.1 | exp | 0.1 | 30
CIFAR-100 |  |  |  |  |  |  |  |
ResNet-18 | 200 | 128 | 5e-4 | 0.9 | 0.1 | exp | 0.2 | 60
RAVEN |  |  |  |  |  |  |  |
ResNet-18 | 100 | 256 | 1e-4 | 0.9 | 0.1 | exp | 0.1 | 50

  * Ep.= Epochs; Bs.= Batch size; Mmt.= Momentum; Wd.= Weight decay.

###  -C Projection dimension $D_{p}$

The main results of BCF using the projection layer are reported for GSBC
vectors with a dimension of $D_{p}=512$. Here, we show that the dimension can
be flexibly varied, providing a trade-off between parameter (and therefore
computation) saving and accuracy. We varied the dimension $D_{p}$ from 128
(high reduction) to 1000 (no reduction since $D_{p}$=$D_{o}$) for MobileNetV2
on ImageNet-1K. The hyperparameters of BCF were kept the same for all $D_{p}$.
Table A2 shows the results. With an extremely low $D_{p}$=$128$, BCF shows
$2.86\%$ accuracy drop compared to the baseline with trainable FCL while
saving $32.8\%$ of the parameters. With a larger $D_{p}\geq 512$, it yields
iso-accuracy with the baseline while saving up to $18.4\%$ of the parameters.
With $D_{p}$=768, BCF eventually surpasses the accuracy of the baseline while
saving $8.7\%$ of the parameters.

TABLE A2: Classification accuracy (%) on ImageNet-1K when replacing the FCL in MobileNetV2 with BCF using a projection layer with variable $D_{p}$. The remaining configurations ($B$=$4$, $F$=$2$) are kept constant. | $D_{p}$ | BF | Fac. |  | Param.
---
saving$\downarrow$
Baseline | – | $71.57^{\pm 0.13}$ | – | $0.0\%$
GSBCs | $128$ | $70.55^{\pm 0.10}$ | $68.71^{\pm 0.12}$ | $32.8\%$
$256$ | $71.15^{\pm 0.07}$ | $70.64^{\pm 0.13}$ | $28.0\%$
$512$ | $71.69^{\pm 0.11}$ | $71.41^{\pm 0.10}$ | $18.4\%$
$768$ | $71.80^{\pm 0.09}$ | $71.64^{\pm 0.11}$ | $8.7\%$
$1000$ | $71.86^{\pm 0.16}$ | $71.56^{\pm 0.18}$ | $0.0\%$

###  -D Maximum number of iterations $N$

On ImageNet-1K, the maximum number of iterations of BCF with 2 codebooks is
set to $N=\lfloor C/(M_{1}+M_{2})\rfloor$=$15$. However, motivated by the
extremely fast convergence on the synthetic product vectors (see Fig. 3 in
main text), we show that the maximum number of iterations can be further
limited to only $3$ with negligible accuracy loss while reducing the
computational cost. Table A3 compares the performance on ImageNet-1K between
$N$=$15$ and $N$=$3$. Across all architectures, our BCF matches the brute-
force accuracy within $0.44\%$ with $N$=$15$ iterations, and within $0.54\%$
with $N$=$3$ iterations at maximum. In both cases, the average number of
iterations is lower than the maximum $N$; thus, the factorizer converges on
average before the maximum $N$ is reached.

TABLE A3: BCF-based replacement approach without and with projection ($D_{p}$=$512$) when allowing BCF a maximum of $N$=$15$ (standard) iterations, or $N$=$3$.  |  | GSBCs (B=4)
---|---|---
|  |  | BCF ($N$=$15$) | BCF ($N$=$3$)
|  | Baseline
---
acc.
| BF
---
acc.
Acc. |  | Avg.
---
iter.
Acc. |  | Avg.
---
iter.
No projection |  |  |  |  |  |
ShuffleNetV2 | $69.22^{\pm 0.20}$ | $65.09^{\pm 0.10}$ | $64.76^{\pm 0.13}$ | $7.3$ | $64.68^{\pm 0.15}$ | $2.4$
MobileNetV2 | $71.57^{\pm 0.13}$ | $70.00^{\pm 0.07}$ | $69.76^{\pm 0.13}$ | $6.2$ | $69.72^{\pm 0.13}$ | $2.3$
ResNet-18 | $70.39^{\pm 0.11}$ | $68.44^{\pm 0.08}$ | $68.00^{\pm 0.07}$ | $6.7$ | $67.90^{\pm 0.07}$ | $2.4$
ResNet-50 | $76.21^{\pm 0.28}$ | $76.34^{\pm 0.04}$ | $76.25^{\pm 0.07}$ | $4.8$ | $76.23^{\pm 0.07}$ | $2.2$
Projection |  |  |  |  |  |
ShuffleNetV2 | $69.22^{\pm 0.20}$ | $68.67^{\pm 0.11}$ | $68.41^{\pm 0.14}$ | $6.0$ | $68.33^{\pm 0.13}$ | $2.4$
MobileNetV2 | $71.57^{\pm 0.13}$ | $71.69^{\pm 0.11}$ | $71.49^{\pm 0.10}$ | $5.5$ | $71.44^{\pm 0.11}$ | $2.3$
ResNet-18 | $70.39^{\pm 0.11}$ | $69.57^{\pm 0.17}$ | $69.19^{\pm 0.13}$ | $6.2$ | $69.10^{\pm 0.14}$ | $2.4$
ResNet-50 | $76.21^{\pm 0.28}$ | $76.72^{\pm 0.06}$ | $76.56^{\pm 0.08}$ | $4.6$ | $76.54^{\pm 0.06}$ | $2.2$

###  -E Number of factors $F$

So far, we have evaluated BCF with two factors, each having codebooks of size
$M_{1}$=$M_{2}$=$32$ on the ImageNet-1K dataset. We demonstrate its capability
with $F$=$3$ codebooks of size $M_{f}$=$10$ each. Consequently, the maximum
number of iterations becomes $N$=$\lfloor 1000/30\rfloor$=$33$. Table A4
compares the classification accuracy of the factorizer for $F$=$2$ with
$F$=$3$. The factorizer with the higher number of factors achieves similar
accuracy while requiring higher iterations (11 vs. 6) compared to $F$=$2$.
However, since each iteration requires fewer search operations for $F$=$3$
($30$ vs. $64$ searches), the overall compute saving of the FCL remains
similar. Our BCF provides a time-space trade-off between the number of factors
while keeping the accuracy and the computational cost constant: a low number
of factors ($F$=$2$) requires more space to store the codebooks ($2\cdot
32$=$64$ codevectors) but features lower average iterations (6), whereas a
higher number of factors ($F$=$3$) requires less space ($3\cdot 10$=$30$
codevectors) but more iterations on average (11).

TABLE A4: Classification accuracy (%) on ImageNet-1K when replacing the FCL in
MobileNetV2 with BCF using a projection with $D_{p}$=$512$ and variable $F$.

| F | BF | Fac. |  | Avg.
---
iter.
| FCL comp.
---
saving$\downarrow$
Baseline | – | $71.57^{\pm 0.13}$ | – | – | $0.0\%$
GSBCs | $2$ | $71.69^{\pm 0.12}$ | $71.49^{\pm 0.10}$ | $6$ | $33.4\%$
$3$ | $71.61^{\pm 0.07}$ | $71.27^{\pm 0.10}$ | $11$ | $35.6\%$

###  -F Comparison with weight pruning

We compare our approach to weight pruning techniques, which mostly sparsify
the weights in all layers, whereas we focus on the final FCL due to its
dominance in compact networks. Such pruning can be similarly applied to
earlier layers in addition to our method. For a one-to-one comparison, we
prune the final FCL weights of a pretrained MobileNetV2 using iterative
magnitude-based pruning [58]. As shown in Table A5, the accuracy of magnitude-
based pruning method quickly degrades as soon as more than 95% of the weights
are set to zero. In fact, this susceptibility forced related works to prune
the final FCL only to 90% [62]. In contrast, our method remains accurate in
high sparsity regimes: the codebooks store only $B\cdot F\cdot M_{f}$=$4\cdot
2\cdot 32$=$256$ indices instead of $D_{p}\cdot C$ values (i.e., 99.98% zero
elements) with an achieved an accuracy of 69.76%.

TABLE A5: Comparison of BCF with pruning of final FCL weights of a pretrained MobileNetV2 on ImageNet-1K. Approach | Zero elements (%) | Accuracy (%)
---|---|---
Baseline | – | $71.57^{\pm 0.13}$
BCF | 99.98 | $69.76^{\pm 0.13}$
FCL pruning | 80.00 | 71.13
90.00 | 70.44
95.00 | 69.48
99.00 | 65.82
99.98 | 18.38