Factorizers for distributed sparse block codes

3.1.Factorizing distributed representations

The resonator network [7,23] avoids brute-force search through the combinatorial space of possible factorization solutions by exploiting the search in superposition capability of VSAs. The iterative search process converges empirically by finding correct factors under operational capacity constraints [23]. 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 [7]. Alternatively, the resonator network can also factorize complex-valued product vectors representing a scene encoded via a template-based VSA encoding [47] or convolutional sparse coding [28]. However, the resonator network suffers from a relatively low operational capacity (i.e., the maximum factorizable problem size given a certain vector dimensionality), and the limit cycles that impact convergence. To overcome these two limitations, a stochastic in-memory factorizer [31] 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 avoiding the limit cycles and reducing the convergence time compared to the resonator network.

Nevertheless, we observed that the accuracy of both the resonator network and the stochastic factorizer notably drops (by as much as 16.22%) when they are queried with product vectors generated from deep CNNs processing natural images (see Table 4). This challenge motivated us to switch to alternative block code representations instead of dense bipolar, 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 2). Interestingly, it only requires two iterations to converge for problems with a search space as large as 104.

3.2.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 [35], or 37% of MobileNetV2 [50] for ImageNet-1K. This dominant parameter count is more prominent in lifelong continual learning models, where the number of classes quickly exceeds a thousand and increases over time [16].

To reduce the training complexity associated with FCLs, various techniques have been proposed to fix their weight matrix during training. Examples include replacing the FCL with a Hadamard matrix [20], or a cheaper Identity matrix [42], or vertices of a simplex equiangular tight frame [62]. 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., Di=Do. Methods that simply draw class vectors randomly distributed over a hypersphere [37,54] were proposed to address this limitation. However, these methods still need to store the individual class vectors, which imposes the FCL’s conventional cost of O(Di·Do) for memory storage and compute complexity during training and inference.

Our BCF with two factors can reduce the memory and compute complexity to O(Di·Do). This is done by using randomly-drawn distributed binary SBCs that form an intermediate product vector space whose dimensionality (Dp) is notably lower than the number of classes (Dp≪Do), 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 Dp=Di), 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.

4.1.Generalized sparse block codes (GSBCs)

Like binary SBCs, GSBCs divide the Dp-dimensional vectors into B blocks of equal length L=Dp/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 R+, and each block has a unit ℓ1-norm. Binary SBCs satisfy both constraints and are valid GSBCs. Figure 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. Neural networks can produce such GSBC product vectors. Besides their benefits in the integration with neural networks, the GSBC representations inside BCF enable more accurate and faster factorization.

Fig. 1.

Block code factorizer (BCF) for F=2 factors. It can factorize both synthetic binary SBC product vectors and GSBC product vectors (p) which might result from a neural network mapping.

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 ℓ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 ℓ1-norm.

ℓ∞-Based similarity We propose a novel similarity measure based on the ℓ∞-norm of the elementwise difference between two GSBC vectors xi and xj:

For any GSBC vectors a and b, it holds that 0⩽ℓ∞(a−b)⩽1. Therefore, our novel similarity metric satisfies 0⩽s∞(a,b)⩽1, whereby equality on the right-hand side holds if, and only if, a=b. Table 1 compares the operations of the GSBCs with respect to the binary SBCs.

4.2.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 4.6.

Given two codebooks,11 X1:={xi1}i=1M1 and X2:={xi2}i=1M2, and a product vector p=xi1⊛xj2 formed by binding two factors from the codebooks, we aim to find the estimate factors xˆ1∈X1 and xˆ2∈X2 that satisfy

4.3.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 xˆ1(0) and 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⩾1, the estimate factors from the previous iteration t−1 are unbound from the product vector by using blockwise circular correlation:

Step 2: Similarity search. Next, we query the associative memory, containing the codebook Xf for factor f, with the unbound factor estimates. We deploy our novel ℓ∞-based similarity as an effective associative search. At iteration t, this yields a vector of similarity scores af(t)∈RMf for each factor f. The i-th element in af(t) is computed as:

Step 3: Sparse activation and conditional random sampling. Recent work on stochastic factorizers [31] 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∈R+. Similarity values that are larger than the threshold propagate forward, whereas lower ones get zeroed out:

This nonlinearity allows us to focus on the most promising solutions by discarding the presumably 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:

The novel threshold and conditional sampling mechanisms are simple and interpretable, and they lead to faster convergence. The stochastic factorizer [31] 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 (i.e., the maximum number of vectors that can be bundled and reliably retrieved). Section 4.7 provides empirical insights.

Step 4: Weighted bundling. Finally, we generate the next factor estimate xˆf(t) as the normalized weighted bundling of the factor’s codevectors:

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 [31]:

Fig. 2.

Optimal threshold and sampling width found using Bayesian optimization with Dp=512, B=4, and F=2.

4.4.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 c⋆=(T⋆,A⋆), corresponding to the optimal threshold and sampling width. As an automatic hyperparameter search method, we employ Bayesian optimization [55].

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′=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, Dp, ∏f=1FMf, B), we run a separate hyperparameter search, each of which tests 200 different hyperparameter combinations restricted to the domains A∈[0,Mf] and T∈[0,1]. Finally, we select the hyperparamters with the lowest error rate at the default maximum number of iterations (N).

Figure 2 shows the resulting threshold (T) and sampling width (A) over various problem sizes for Dp=512, B=4, and F=2. For a range of problem sizes (103–105), BCF does not require the threshold and sampling dynamics: it sets the threshold and the sampling width to 0. For larger problem sizes (>105), 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. 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, Dp, B) and might stem from the limited bundling capacity.

4.5.Experimental setup

Fig. 3.

Factorization accuracy (left) and number of iterations (right) of various BCF configurations on synthetic (i.e., exact) product vectors for different problem sizes (∏f=1FMf). We set Dp=512, F=2, and B=4. The maximum operational capacity is marked with an x. 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, Dp, ∏f=1FMf, 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% [23].

4.6.Comparative results

Figure 3 compares the accuracy (left) and the number of iterations (right) of various BCF configurations with Dp=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 103 accurately. The operational capacity increases to 4.2·103 when relaxing the sparsity constraint of binary SBCs by allowing for GSBC representations inside BCF. However, the required iterations are still high, requiring almost as many searches as the brute-force approach. The introduction of the ℓ∞-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 104, 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·105, BCF encounters limit cycles and spurious fixed points, hindering its convergence to the correct solution [23]. 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·106.

Fig. 4.

Effect of the dimension Dp on the number of iterations for BCF with B=4, F=2 (left) and F=3 (right).

Fig. 5.

Effect of the number of blocks B on the 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 (Dp), and numbers of factors (F). Figure 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 similarity computations (F·∑fMf) for larger F due to the F-root dependence of Mf. For example, at Dp=512 and ∏f=1FMf=106, 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.

Figure 5 shows BCF’s performance for a fixed Dp 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 103 for both F=2 and F=3. The operational capacity increases to around 5·106 when B=4. Further increasing the number of blocks (B⩾8) exhibits an operational capacity beyond 108, the largest problem size we measured. The convergence speed peaks at B=4 and B=8 blocks, gradually decreasing 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⩾4), and number of factors (F∈{2,3}).

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

4.7.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 thresholded similarity is 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.

Fig. 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 M1=M2=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 (Tc) 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 Mf·AF−1 combinations per factor f. The expected number of iterations for this procedure is:

Figure 6 shows experimental results with this factorizer mode for F=2, M=1000, varying Dp 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 3 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 lies at around 100 in this setting. 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 notably faster (15.73 iterations) than when BCF is run in the unconditional random sampling mode (38.87 iterations).

Similarity metric 

Fig. 7.

Log-scale histograms of ℓ∞-based and dot-product similarities. BCF with Dp=512, B=4, F=2, M1=M2=200, and T=0.

Here, we compare the ℓ∞-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 ℓ∞-based similarity. The threshold nonlinearity and conditional random sampling are disabled. For F=2, B=4, and Dp=512, one such problem size is 4·104. We execute the decoding for two iterations and show the resulting histogram in Fig. 7. The ℓ∞-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 ℓ∞-based similarity found the correct solution (similarity value of 1), whereas the dot-product similarity did not.

5.1.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 (X1, X2, X3, and X4) where the size of each codebook (Mf) corresponds to the number of values the individual attribute can have [18] (e.g., the codebook X1 representing five shapes has M1=5 elements). The resulting product space is P=X1⊛X2⊛X3⊛X4.

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 P=X1⊛X2 that contains M1·M2 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 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 M1=M2=C=10. Then, the product vector p1:=x11⊛x12 belongs to “class 1” and p100:=x101⊛x102 to “class 100”.22

Fig. 9.

Training and inference with BCF.

5.2.Training CNNs with blockwise cross-entropy loss

After defining the product space, we train a function fθ (e.g., a CNN) with trainable parameters θ to map the input data (e.g., images) to the target product vectors of the corresponding classes. Figure 9a illustrates the training procedure. Given a labeled training sample (I,y) containing the input image I∈Rc×h×w and the target label y, we first pass the image through the function fθ, yielding q=fθ(I). Next, we generate the target product vector by mapping the target label y to the factor indices (f1 and f2) and forming the corresponding product p=xf11⊛xf22.

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 notable 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 qb:=q[(b−1)L+1:bL] from the output features q and the target index p˙[b]. Then, the blockwise CEL is defined as:

5.3.BCF-based inference

The BCF-based inference is illustrated in Fig. 9b. We pass a query image (I) through the CNN, yielding the query product (q), which can be interpreted as a “noisy” version of the ground-truth product vector p. We then search for the product vector pˆ∈P with the highest similarity to q. One baseline is to compute the similarity between q and each product vector in P in a brute-force manner; however, this requires many similarity computations and the storage of each product vector in 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 sF, which shapes and normalizes the blockwise distribution of the query vector. The optimal inverse softmax temperature was found to be sF=1.5, based on a grid search on the ImageNet-1K training set with MobileNetV2, and applied for all architectures.

5.4.Experimental setup

Datasets We evaluate our new method on three image classification benchmarks.

ImageNet-1K. The ImageNet-1K dataset [3] 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×224.

CIFAR-100. The CIFAR-100 dataset [27] contains colored images with a resolution of 32×32 from C=100 classes. The dataset provides 500 samples for training and 100 for testing per class.

RAVEN. The RAVEN dataset [59] contains Raven’s progressive matrices tests with gray-scale images with a resolution of 160×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, 2 × 2 grid, and 3 × 3 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 2 × 2 grid, and 9 for the 3 × 3 grid. Overall, this dataset contains C=4200 attribute combinations (14 positions × 5 types × 6 sizes × 10 colors).

Architectures ShuffleNetV2 [35], MobileNetV2 [50], ResNet-18, and ResNet-50 [15] serve as baseline architectures. In addition to our BCF-based replacement approach, we evaluate each architecture with the bipolar dense resonator [7,23], the Hadamard readout [20], and the Identity readout [42]. 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 notably 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 Di≠Do, we used an identity matrix that reads out the first Do elements of the output feature vector and ignores the remaining Di−Do elements. We could not adjust the dimension Di 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.1. 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.

5.5.Comparative results

Table 4 compares the classification accuracy of the baseline with various replacement approaches without projection, namely Hadamard [20], Identity [42], bipolar dense [7], and our BCF. On ImageNet-1K, BCF reduces the total number of parameters of deep CNNs by 4.4%–44.5%,33 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 A.4). This does not hold for the bipolar dense resonators showing notable 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 [4] (see Appendix A.2).

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 O(Di·Do), while our BCF reduces both to O(Di·Do), as F=2 and N=3 are constant. Hence, Hadamard is ineffective for a large value of Do. Moreover, Identity is only competitive when Di is within the range of Do (MobileNetV2 and ShuffleNetV2); for other combinations, either it is not applicable (ResNet-18 where Di<Do), or ineffective (ResNet-50 where Di>Do).

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 [61] yields notable 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 A.6 for more details.

Furthermore, we compare our results with [54], 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 5 shows the performance of our BCF when using the projection layer (Dp=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.

5.6.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 6 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⩾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 Dp We varied the projection dimension (Dp) from 128 (high reduction) to 1000 (no reduction since Dp=Do) for MobileNetV2 on ImageNet-1K. With an extremely low dimension (Dp=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., Dp=768), BCF even surpasses the baseline accuracy while saving 8.7% of the parameters. See Appendix A.3.

Number of factors F So far, we have evaluated BCF with two factors, each having codebooks of size M1=M2=32 on the ImageNet-1K dataset. We demonstrate BCF’s capability with F=3 codebooks of size Mf=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 A.5.

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 7 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.