On the role of noise in factorizers for disentangling distributed representations

Authors: geethan  karunaratne
michael  hersche
abu  sebastian
abbas  rahimi
Venue: NeurIPS_cc_2024_Workshop_MLNCP
Published: 2024-09-11 04:01:19

Abstract: One can exploit the compute-in-superposition capabilities of vector-symbolic architectures (VSA) to efficiently factorize high-dimensional distributed representations to the constituent atomic vectors. Such factorizers however suffer from the phenomenon of limit cycles. Applying noise during the iterative decoding is one mechanism to address this issue. In this paper, we explore ways to further relax the noise requirement by applying noise only at the time of VSA's reconstruction codebook initialization. While the need for noise during iterations proves analog in-memory computing systems to be a natural choice as an implementation media, the adequacy of initialization noise allows digital hardware to remain equally indispensable. This broadens the implementation possibilities of factorizers. Our study finds that while the best performance shifts from initialization noise to iterative noise as the number of factors increases from 2 to 4, both extend the operational capacity by at least $50\times$ compared to the baseline factorizer resonator networks. Our code is available at: https://github.com/IBM/in-memory-factorizer

Main paper: 
 introduction: 
 Some basic Visual perception tasks, such as disentangling static elements from moving objects in a dynamic scene and enabling the understanding of object persistence, depend upon the factorization problem [1] [2] [3] [4] . The principle of factorization extends to auditory perception, e.g. separating individual voices or instruments from a complex soundscape [5] . Factorization also plays a key role in higher-level cognitive tasks. Understanding analogies for example requires decomposing the underlying relationships between different concepts or situations [6] [7] [8] [9] [10] . While biological neural circuits solve the above challenges deftly, factorization remains a problem unsolvable within polynomial time complexity [11] . Outside the biological domain, factorization is at the core of many rapidly developing fields. In robotics, factorization can enable robots to 1) understand their environment by parsing visual scenes and identifying objects, locations, and relationships [12] , and 2) plan and execute tasks by decomposing complex actions into a simple sequence of steps. Factorizing semi-primes has implications for cryptography and coding theory [13] . Factorization helps develop more transparent and explainable AI systems [14] , by decomposing complex decision processes into understandable components.Vector-symbolic architectures (VSA) [15] [16] [17] [18] is an emerging computing paradigm that can represent and process a combination of attributes using high-dimensional holographic vectors. Unlike the traditional methods where information might be stored in specific locations (e.g., a single bit representing a value), VSA distributes the information across the entire vector signifying a holographic nature. This means if some components of the vector are corrupted or lost, the overall information can still be recovered due to the distributed nature of the encoding. This makes VSA an ideal candidate for realization on low signal-to-noise ratio in-memory computing fabrics based on e.g., resistive RAMs [19, 20] and phase-change memory [21] . In high-dimensional spaces, randomly generated vectors are very likely to be nearly orthogonal aka quasi-orthogonal. This crucial property allows efficient and robust representation of a vast number of different concepts in VSA with minimal interference using these nearly orthogonal vectors as building blocks. More details on the background of VSA are provided in Appendix 5.1, and interested readers can refer to survey [22, 23] .A typical algebraic operation for combining F different attributes in an object is to element-wise multiply associated D-dimensional holographic vectors. Due to the properties of high-dimensional spaces, this operation tends to produce unique representations for different attribute combinations. A deep convolutional neural network can be trained to generate these product vectors approximately [14] by taking the raw image of the object. The inverse of the binding problem becomes the factorization problem which is the disentangling of an exact product vector or, as in the latter case, an inexact product vector, into its constituent attribute vectors. While binding is a straightforward calculation, factorization involves searching for the correct combination of attributes among an exponentially large space of possibilities.Resonator network [24, 25] , a type of factorizer, built upon the VSA computing paradigm, introduces a promising approach to perform rapid and robust factorization. Resonator networks employ an iterative, parallel search strategy over high-dimensional vector data structures called codebooks, leveraging the properties of high-dimensional spaces to explore the search space efficiently and converge on a query's most likely attribute combinations. However, the original resonator networks face some critical limitations. First, the decoding of multiple bound representations in superposition poses a challenge due to the noise amplifications introduced in traditional explaining-away methods. Therefore, a recent work [26] expanded the pure sequential explaining-away approach by performing multiple decodings in parallel using a dedicated query sampler, which improved the number of decodable bound representations.As a second limitation, resonator networks' iterative search strategy limit cycles poses an obstacle to effective functioning. As one potential remedy to break free of limit cycles during the iterative decoding, the IN-MEMORY FACTORIZER (IMF) [27] harnesses the intrinsic stochastic noise of analog in-memory computing (IMC). Together with an additional nonlinearity in the form of a computationally cheap thresholding function on the similarity estimates, IMF solves significantly larger problem sizes compared to the original resonator networks. Indeed, more recent advancements on resonator networks [28] make also use of nonlinearities in the form of ReLU and exponentiation and noise on the similarity estimates. In this case, the noise has to be generated by a dedicated noise source (e.g., a random number generator) at every decoding iteration. IMF however does not need such an additional noise source thanks to the IMC's intrinsic noise; yet, its performance relies on the availability of underlying hardware with specific noise levels across decoding iterations.In this article, we explore novel factorizers with alternative noise requirements to mitigate limit cycles. In particular, we propose ASYMMETRIC CODEBOOK FACTORIZER (ACF), where codebooks are initialized with some noisy perturbations and the same instance of noise used across iterations providing a relaxed noise requirement to circumvent limit cycles. We conceptualize a purely digital factorizer design that can provide energy efficiency gains by eliminating data conversions. We find that compared to the baseline resonator network [24] , the variants embracing noise, IMF, and ACF, always perform better in terms of operational capacity and require fewer iterations to converge at different sizes of search spaces. 
background: resonator networks: 
 The resonator network is an iterative algorithm designed to factorize high-dimensional vectors [24] . Essential to the operation of resonator networks are codebooks, which serve as repositories of quasiorthogonal high-dimensional vectors called codevectors, with each codevector representing a distinct attribute value. For instance, in a system designed for visual object recognition, 3 separate codebooks might store representations for shapes (like circles, squares, triangles), colors (red, green, blue), and positions (top left, bottom right, center) each having 3 distinct possibilities for the attribute values. See Fig. 1 . The number of potential combinations of these codevectors to form product vectors grows M F with respect to the number of attributes (i.e., factors F ) and attribute values (i.e., codebook size M ) exponentially. However, the dimensionality (D) of these vectors is usually fixed to several hundred leading to (D << M F ), searching for the specific combination of codevectors that compose a given product vector becomes computationally expensive, presenting a hard combi- Taking the product vector as input, and starting from initial estimate vectors the factorizer undergoes unbinding (UB), associative search (AS), attention activation (AA), and reconstruction (RC) phases to iteratively refine the estimate. AS and RC take the biggest share of the computing and memory. They map to a predominantly MVM operation.natorial search problem. Thanks to the quasi-orthogonal property of codevectors however, resonator networks can rapidly navigate the vast search space.Starting with an initial estimate for each factor, and the product vector, it updates the estimates one factor at a time. It achieves this by first "unbinding"(UB) or removing the influence of the estimated values of all but the selected factor from the product vector. In the context of bipolar spaces, where codevector components are +1 or -1, unbinding is accomplished through elementwise multiplication. Secondly, the unbound vector is compared against all codevectors within the corresponding codebook using an associative search (AS), typically a series of cosine similarity or dot products that can be formulated as a matrix-vector-multiplication (MVM) operation. The associative search outputs an attention vector of length M , measuring how the unbound vector aligns with the codevectors. Thirdly, the attention vector is passed through an optional attention activation (AA) function. This allows us to filter out uninteresting codevectors. Fourthly, using activated attentions as weights, codevectors are superimposed to reconstruct a new estimate vector. This reconstruction (RC) operation is an MVM operation with the transpose of the codebook itself acting as the reconstruction matrix and the activated attention acting as the vector. The four phases are repeated, refining the estimates for each factor with each iteration until the resonator network converges to a solution representing the most probable factorization of the product vector.This can be mathematically formulated as follows:Let us consider a three-factor (F = 3) problem with the factors originating from three codebooks:A = { a (1) , a (2) , • • • , a (M ) } , B = { b (1) , b (2) , • • • , b (M ) } , C = { c (1) , c (2) , • • • , c (M ) } , each with D dimensional bipolar codevectors A, B, C ∈ { -1, +1 } D×M .Let the estimate for each factor be represented using â, b, ĉ respectively, and the product vector denoted with x, then for the first factor, unbinding of other factors is given by: ã = x ⊘ b ⊘ ĉ. Based on the unbound vector ã of the first factor, AS, AA, and RC phases can be written as in the following equations respectively.EQUATIONWhere t, α, f, sign stands for iteration number, attention vector, activation function, and signum function respectively. A similar approach can be followed to compute the next estimate vector of the other factors b, ĉ. 
breaking free from limit cycles with noise: 
 As we discussed, resonator networks operate iteratively, progressively refining their estimates for each factor by comparing them to codebook entries. However, during this iterative process, the network can get trapped in a repeating sequence of states. Then the network's estimate for a factor oscillates between a small set of codevectors without ever settling on the true factor. This phenomenon, referred to as a limit cycle, can prevent the network from reaching the optimal solution.The emergence of limit cycles can be attributed to the symmetric and deterministic nature of the codebooks used in the AS and RC phases of the baseline resonator network's (BRN) [24, 25] search procedure. This deterministic behavior is particularly problematic when the search space is large and contains many local minima, which can trap the network's updates in a repeating pattern. When a resonator network gets stuck in a limit cycle, it fails to converge to the correct factorization, even if given an unlimited number of iterations. This lack of convergence can significantly impact the network's accuracy and efficiency, rendering it ineffective for tasks that require precise factorization. Introducing stochasticity into the network's update rules can help it break free from deterministic limit cycles. This is a crucial finding that not only pushes the factorizers' operational capacity but also shifts the hardware landscape they thrive. In particular, there is a potential for leveraging the intrinsic randomness associated with memristive devices in IMC implementations of factorizers as prescribed in IMF [27] . An example implementation is illustrated in Fig. 2(a) . The codevectors of a codebook are programmed along the columns of the crossbar arrays. In the first crossbar used for the AS phase, the inputs are passed through the west side digital to analog converters (DACs), and the resulting currents/charges are collected on the south periphery and converted back to the digital domain using the analog to digital converters (ADCs). After activating the resulting attentions, the sparse attention vector is input through the south-side DACs for the RC phase. The resulting currents/charges are collected through the east side periphery and converted to digital using ADCs before converting via signum function to the next estimate vector.The memory devices used in these arrays are fabricated using phase-change memory (PCM) technology and exhibit natural variations in their behavior forming a near-Gaussian distribution of the attention result as seen in Fig. 2(c ). This can be expressed in an approximated form as α a (t) = ã(t)A T + n. Where n is the M -dimensional noise vector sampled from i.i.d. Gaussian distribution n ∼ N (0, σ • I M ) and σ denotes the standard deviation of the noise, which ranges around 0.01 in a recent large-scale chip based on phase-change memory devices [29] . As seen in Sec. 4, this σ value falls in the useful noise range enabling escaping repeating patterns and exploring a wider range of solutions.Even if an arbitrary number of iterations are allowed, a deterministic digital design with unperturbed symmetric codebooks fails to achieve the accuracy of the IMF due to its susceptibility to limit cycles. Stochasticity, as a key operation to eliminate limit cycles, has significant added costs in terms of energy and area in mature digital hardware implementation. For example, generating Gaussian noise involves several expensive floating point operations such as exponentiation and multiplication.We explore the possibility of inserting the noise into the codebooks at the time of initialization. If the same noise is added to both copies of the codebook it would still keep the same quasi-orthogonal relationship of the codevectors and would not change the dynamics of the factorizer. Instead, we propose perturbing only a single copy of the codebook using a randomly generated bitflip mask. Fig. 2 (b) shows perturbing the codebook used in the RC phase by applying a bit flip mask BF M ∈ { -1, +1 } D×M of certain sparsity as shown in Eq. 4. We call this type of model an Asymmetric Codebook Factorizer (ACF).EQUATIONWhere u ∼ U(0, 1) ∈ [0, 1] D×M is a noise matrix sampled from the uniform distribution. The sparsity r is a hyperparameter that can be optimally obtained using a hyperparameter search scheme. The perturbed codebook for the RC phase A RC is calculated by element-wise multiplication between BF M and the codebook as shown in Eq. 4. As r increases the factorizer starts losing its ability to converge and iterate on the correct solution. However, with the presence of the convergence detection circuit detailed in Appendix 5.2, the need to resonate is not essential. Similarly, codebooks that are not bipolar in nature [30] can be perturbed using an appropriate random function.Apart from noise, another known approach to solving limit cycles and converge faster to the right solution involves non-linear activation functions. One such activation function, employed both in IMF and ACF, uses a threshold to sparsify the attention vector. It is explained further in Appendix 5.3. 
results and discussion: 
 We conduct software experiments to measure the operational capacity and other behaviors of different variants of factorizers, namely the BRN, IMF, and ACF. Operational capacity is defined as the maximum size of the search space that can be handled with more than 99% accuracy while requiring fewer iterations than what a brute force approach would have taken. A brute force approach would in the worst case find the correct factors in M F steps.The results are presented in Fig. 3 . We consider 3 cases for the number of factors F = {2, 3, 4}. The dimensions of the codevectors for these cases are set based on the minimum dimensions reported in the BRN, namely D = 1000, 1500, 2000 respectively for F = 2, 3, 4 respectively. For each case, we span the search space size starting from 10 4 up to a maximum of 10 11 until the operational capacity is reached. At each search space size, we conduct 5000 trials factorizing randomly sampled product vectors. We calculate the average accuracy and the average number of iterations.The BRN reaches its capacity at approximately 10 5 , 10 6 , and 10 7 for F = 2, 3, 4 cases respectively. Although the accuracy momentarily dropped slightly below 99% in a few search space sizes between 10 5 and 10 6 at F = 2, IMF does not reach the operational capacity for all search space sizes tested.For ACF, we observe the reaching of the operational capacity at > 5 × 10 9 for F = 4. In the other two cases, ACF did not reach the operational capacity point for the search space sizes tested. The momentary drop in accuracy and rise in iterations in certain search spaces can be attributed to inadequate hyperparameter exploration. The optimum hyperparameter setting we achieved during our experiments is further detailed in Appendix 5.4Both IMF and ACF exhibit better performance in terms of operational capacity and the number of iterations compared to the BRN. In theory, the IMF has better control over noise as it is applied over the iterations. This becomes clear in the F = 4 case where it outperforms ACF by achieving greater operational capacity. ACF however edges over IMF in the F = 2 case where there are fewer interactions among factors.Fig. 3 : The number of iterations (top row) and accuracy (bottom row) for three variants of the factorizer: baseline resonator (in blue) [24] , in-memory factorizer (in orange) [27] , and our asymmetric codebook factorizer (in green). The left, center, and right column results correspond to 2,3, and 4-factor scenarios, respectively. The regions that meet operational capacity criteria (i.e. ≥99% accuracy) are plotted with solid lines while other regions are plotted with dotted lines.Another aspect to consider is the hardware design costs. As shown in Fig. 2 , IMF achieves area efficiency with a single copy of codebooks in a crossbar array and achieves energy efficiency by performing arithmetic operations implicitly using device physics. ACF on the other hand has explicit multipliers and adders but saves the bulk of the energy spent on converting data from digital to analog and vice versa several times per decoding iteration. As a consequence of the converter-less design, ACF can operate faster, with several nanoseconds per iteration as opposed to several microseconds. Thus ACF can achieve more iterations per unit period of time.The principles used in the IMF and ACF are not mutually exclusive. While in this work we study and compare their standalone performance, there is no reason that prevents them from being employed in unison. One possible realization of this involves perturbing the target conductance values corresponding to the codebook values before they get programmed into the analog memory devices in the IMF. Incorporating both sources of notice may result in a synergistic effect enabling higher operational capacity factorizers. 
conclusion: 
 In conventional wisdom, stochasticity and noise are considered a bane in computing. We demonstrate that factorizers grounded on VSAs empower a new computing paradigm that embraces noise to push the limits of operational capacity. We discuss two variants, the first harnessing intrinsic noise in analog in-memory computing during MVM operation, the second initializing the codebooks with noisy perturbations yielding a model that widely appeals to deterministic digital design systems. While there are tradeoffs, both these variants empirically outperform the baseline resonator networks in multiple facets. When combined with appropriate hardware designs, they provide promising directions to solve factorization problems in large-scale search spaces within reasonable timescales. 
 
 Appendix:  



Reviews: review: title: title: Breaking limit cycles with noise
main_review: main_review: The authors found that introducing stochasticity using noise into the network's update rules can help breaking free from deterministic limit cycles. It may be worth checking whether chaotic dynamics would also contribute to this effect [a].
[a] T. L. Carroll and L. M. Pecora, Using chaos to keep period-multiplied systems in phase, Physical Review E 48, 2426 (1993).
title: title: Recommendation for acceptance
main_review: main_review: The authors propose a novel approach for factorization in vector-symbolic architecture (VSA) on digital memory devices, mainly aiming at mitigating the limit cycle problem in VSA, which traps the procedure to an undesired local minima. Specifically, they devised a noise injection procedure for a digital memory device involving asymmetric random bit flip, an alternative source of stochasticity to the intrinsic noise utilized to solve factorization by analog memory devices in an existing algorithm. They demonstrated by numerical experiments that the proposed algorithm can perform better when the number of factors is small compared to the existing noise induction method. VSA is an active area of research because it is well suited for non-von-Neumann computing paradigms such as neuromorphic hardware and is expected to be one of the platforms for AI tasks in such platforms. Factorization and its performance are essential parts of VSA because they ensure we can effectively obtain the desired outcome from highly parallel computation that is natural to VSA. As such, I recommend acceptance of this work in MLNCP. That being said, I have a small number of questions and comments that, if addressed, would improve the work's readability. 

1) In section 4, the authors show the results of their experiments on BRN, IMF, and ACF. It would help the paper's readability if there was an explanation about whether the experiment was done as a software simulation or on physical hardware.

2) In lines 197-203, the authors discuss the advantage of using digital hardware to overcome digital-to-analog conversion overhead. Because Fig. 3 compares three algorithms based on iteration counts and accuracy, this may hinder readers from understanding the potential of AFC against IMF. It would help understand the advantage of ACF if the expected real-time execution time comparison against IMF is depicted somewhere.

3) In lines 204-209, the authors suggest using IMF and ACF together to make it more performant. It will help readability if the authors explain in what measure the combination becomes "more performant," such as operation capacity, number of iterations, or accuracy.