Generative Pseudo-Inverse Memory
Authors: Kha Pham
Hung Le
Man Ngo
Truyen Tran
Bao Ho
Svetha Venkatesh
Venue: ICLR 2022 Poster (2022)

Abstract: We propose Generative Pseudo-Inverse Memory (GPM), a class of deep generative memory models that are fast to write in and read out. Memory operations are recast as seeking robust solutions of linear systems, which naturally lead to the use of matrix pseudo-inverses. The pseudo-inverses are iteratively approximated, with practical computation complexity of almost $O(1)$. We prove theoretically and verify empirically that our model can retrieve exactly what have been written to the memory under mild conditions. A key capability of GPM is iterative reading, during which the attractor dynamics towards fixed points are enabled, allowing the model to iteratively improve sample quality in denoising and generating. More impressively, GPM can store a large amount of data while maintaining key abilities of accurate retrieving of stored patterns, denoising of corrupted data and generating novel samples. Empirically we demonstrate the efficiency and versatility of GPM on a comprehensive suite of experiments involving binarized MNIST, binarized Omniglot, FashionMNIST, CIFAR10 & CIFAR100 and CelebA.

Published as a conference paper at ICLR 2022
GENERATIVE
MEMORY
Kha Pham Hung Le Man Ngo ? Truyen Tran , Bao Ho and Svetha Venkatesh
1 Applied Artificial Intelligence Institute, Deakin University
2 Faculty of Mathematics and Computer Science, VNUHCM-University of Science
3 Vietnam Institute for Advanced Study in Mathematics
1 (phti, thai. truyen.tran, svetha. venkatesh @ddekiin edu. adu.au, au,
2 anmanghcmus edu. vn, bao@viasm. edu. vn
ABSTRACT
We propose Generative Pseudo-Inverse Memory (GPM), class of deep generative memory models that are fast to write in and read out. Memory operations are recast as seeking robust solutions of linear systems, which naturally lead to the use matrix pscudo-inverses. The pseudo-inverses are itcratively approximated, with practical computation complexity of almost (11). We prove theoretically and verify empirically that our model can retrieve exactly what have been written to the memory under mild conditions. A key capability of GPM is iterative reading, during which the attractor dynamics towards fixed points are enabled, allowing the model iteratively improve sample quality in denoising and generating. More impressively, GPM can store large amount of data while maintaining key abilities of accurate retrieving of stored patterns, denoising of corrupted data and generating novel samples. Empirically we demonstrate the efficiency and versatility of GPM on a comprehensive suite of experiments involving binarized MNIST, binarized Omniglot, FashionMNIST, CIFARIO & CIFARI00 and CelebA.
INTRODUCTION
Memory is central to intelligence by facilitating information compression, reconstruction, manipula- tion, and generation. The processing speed and storage capacity of the working memory are known to correlate with reasoning capacity (Jensen and Munro, 1979; Kyllonen and Christal, 1990). Recent work in machine learning has explored slot-based external memory to augment neural networks (Graves et al., 2016; Le et al., 2019) in which memory reads and writes proceed sequentially through attention mechanism, making training and pattern retrieval difficult for very long sequences. Global self-attention techniques (Ramsauer et al., 2021) create short-cuts in information paths, hence easier to train, but require large memory and computation for long sequences.
Different from slot-based memories, Kanerva Machines (Wu et al., 2018a;b) ative memory inspired by Kanerva's sparse distributed memory (Kanerva, 1984). Here memory update/retrieval and addressing mechanism are treated as Bayesian inference where posteriors are updated when a new data episode arrives. This iterative and dynamic inference handles noisy inputs better due the convergence of the attractor dynamics fixed points (Wu et al., 2018b). However, these models suffer from slow processing speed, which originates from the sequential writing mech- anism. This slowness prevents the model adapt to large batch of data, thus makes it difficult to conduct experiments on memory storage capacity. On the other side, one cannot ensure theoretically how well those models retrieve information. This creates an obstacle for theoretical research on the efficiency of memory models.
class of gener-
To overcome these challenges we propose new model called Generative Pseudo-Inverse Memory (GPM), which is illustrated in Fig. I. GPM reformulates the Bayesian updates of memory and address as finding least-square solutions to linear systems. Among these solutions, the smallest norm is found through applying the Moore-Penrose pseudo-in pseudo-inverse inverse of matrices (Ben-Israel and Greville, 2001). This helps us achieve rapid and accurate memory read/write. Moreover, our model is able to not only store and retrieve information perfectly under ideal conditions but also generate samples based

---

Published as a conference paper at ICLR 2022
M
encodder
cnicoder
Z
Z
W
M
W
decoder
X,
lincar relation
dynamic addressing
write
read
(b)
Figure 1: (a) Folded writing-reading mechanism of GPM. Red arrows indicates operations of computing the pscudo-inverses. The memory M, the weight W and the data Z interact in a dynamic way, where W is dynamically computed based on Z and M and (assume that) Z depends linearly on W and M. (b) Unfolded mechanism of GPM. Orange boxes and circles contain trainable parameters of GPM. The green circle consists of variational part for the generative scheme. Red arrows are operations of computing the pseudo-inverses. During writing, the episode X is encoded as Z. Using Z and prior memory Mo. we compute the writing weight Wo and then use Wo to write Z into the memory. The result of writing phase is the posterior memory M. In reading, the query X, encoded Zy Note that the encoder in the reading phase needs not be identical to the encoder in writing phase. The reading weight is computed based on Z, and the posterior M. The memory read-out Zr is simply the matrix product between W and M. Finally, Z,- goes through the decoder to produce the output X, of the reading phase. If iterative reading is included, X. will hecome the next query and he fed back to the encoder for next reading step. In training, we use the same encoder for writing and reading, the query X, is identical with X and reading non-iterative.
on written data. This coincides with recent inspiring results from functional neuroimaging (Addis et al., 2007; Okuda et al., 2003; Schacter et al., 2012), which showed that memory not only helps us memorize but also supports imagining. We derive energy function for GPM and show that its updates seek to locate local minima of the energy. This dynamic enables GPM to perform iterative reading improve sample quality during denoising and generating. Finally, GPM can store large amount of data (up to a dataset) while still maintaining key capabilities. We validate these theoretical insights through a comprehensive suite of experiments on binarized MNIST (LeCun et al., 2010). binarized Omniglot (Burda et al., 2016), FashionMNIST (Xiao et al., 2017), CIFARIO & CIFAR 100 (Krizhevsky, 2009) and CelebA (Liu et al., 2015), demonstrating superior results.
MODEL
Consider a data episode of length T and let X denote the episode data matrix of T rows, where the i-th row of X is the i-th item of the episode. Throughout this paper, we refer to the episode as its associated episode matrix. We aim to compress the episode into a fixed-size memory for later reconstruction and generation processes. We maintain a memory matrix M, which is deterministic real matrix of size K C' with trainable initialization Mg. For convention, Mo may be considered as the common prior memory containing information of the whole dataset while M is the posterior memory dependent on the episode.
Remark. In this paper, we reuse classical terms "prior memory" and "posterior memory", which are frequently used in prior works where the memory is modeled distribution. In this paper, however, we only consider deterministic memories with an exception when we introduce the optimization problem corresponding to the Bayesian inference (Eq. (3)). Hence, "prior memory" and "posterior memory" should be interpreted as the memory before and after data arrive, respectively.
In order to write to and read from the memory, we additionally define the writing weight matrix Wo and reading weight matrix W, both of size T x K. We treat the reading weight W as a random variable, hence inducing the generative capability of the model. For simplicity, the prior p (vec (W)) of W is the standard Gaussian N (0, IT*x) while the posterior y (vec (W)) is N (W, ITxkk where the mean Win is adapted to each episode and ow learnable parameter. Read-outs from the memory are matrix products between the reading weight and the posterior memory.
We note that weights here dynamic and unrelated to neural network parameters. The term "dynamic" means the writing/reading weights of input not only depend its own but also the episade it helongs
2

---

Published as a conference paper at ICLR 2022
Let co(-) be the (neural) encoder and do(.) be the decoder parameterized by 6. In the following we drop the explicit subscript 9 for clarity. We further let Z denote the T x C' encoding matrix of of X. During training, the model can only observe a noisy version of Z, which we denote by Ze- Specifically. z + &, where E~ (O I is the observation noise. We assume that the observed data Ze depends linearly on the weights and the memories: Zg WoMo and Ze- WM, which we refer as linear assumptions over Ze.
the episode X, i.. Z e(X) where e(.) is applied to each
2.1
OBJECTIVE FUNCTION
Given the memory M. we aim to maximize the conditional log-likelihood In (x [M). It is difficult maximize In p
X [M) directly, so instead maximize its evidence lower bound L, where
C = Eggw) Inp(X/W, M) (x (p)lp())ppWW
The first term in L usually called the negative reconstruction loss, while the second term is the Kullback-Leibler divergence between the posterior q( (W) and the prior p( ()) of the reading weight.
Details of derivation will be given in Appendix
In our model, we use the encoding matrix Z as the data to be written to the memory instead of the original episode X. Therefore, we would like Z to "good" representation of X. We quantify this goodness by the usual auto-encoder loss AAE = Ex In (d (d (e(X))). Thus during training, we will maximize the objective function:
O C CAE.
2.2
GENERATIVE PSEUDO-INVERSS MEMORY
In our model, the posterior memory, the writing weight and the reading weight are all dynamic (i.e. depending on the data episode). Hence it is necessary to understand the motivations and computation methods introduced in the following.
Intuition
Only in this part, we will consider probabilistic memories to have unified settings with previous Bayesian- baaee works such as the Kanerva Machines (Wu et al., 2018a;;; Marblestone et al., 2020). When the observed data Ze arrive, the Kanerva Machines apply the Bayesian inference process to obtain the posterior memory from a given (trainable) prior distribution. It is well-known that the posterior mean is the Bayes estimator with respect the squared error risk (Jaynes, 2003). Formally, given the observed data Zę and the writing weight Wa. the posterior memory mean M is the solution of the optimization problem
min EE (IM- M Ze, Wo
where I|-IF= is the Frobenius norm. With the linear assumption over Ze and an additional linear assumption over M, Eq. (3) has a unique and explicit solution (see Appendix H).
The solution M of Eq. (3) tends to preserve information from Mg- However, in practice, what appears in the prior memory might be blurry information. Forcing the short-term memory M to be close to Mg may prevent M from storing sufficient information, leading to incorrect read-out.
Memory inference
From now we will only consider deterministic memories. We propose weighted version of the optimization problem (3) to help improve read-out accuracy. Our proposed optimization problem is
min W (M M. M
(4)
Intuitively, if M is solution of Eq. (4), then WoM is close to WoMo, which is equal to Ze due to the linear assumption over Zç. In other words, the read-out after writing (i.e. W,M) is similar the data written to the memory (i.e. Zę). Substitute W,M, Zg. Eq. (4) becomes
min W Ze 1 M
(5)
3

---

Published as a conference paper at ICLR 2022
Any solution of Eq. (5) is called the least-square solution of the linear system WoM Zg. However, Eq. (5) may admit more than one least-square solution, thus we are interested the least-square solution that has the smallest norm, i.c. the minimum-norm seast-square solution. The minimum- norm condition may help to regularize in the sense that the posterior memory should contain as little redundant information as possible. It can be proved that M W Zg is the minimum-norm least-square solution of the system WoM Zg (Ben-Israel and Greville, 2001), where W the pseudo-inverse of Wo- The pseudo-inverse of matrix is applicable to classical associative memory which involves finding linear mapping from imput to output (Stiles and Denq, 1985; Yen and Michel, 1991). Readers are referred to Appendix D for more mathematical properties of the pseudo-inverse.
Computing writing and reading weights (dynamic addressing)
The discussion so far is about seeking the posterior memory M given the data Z and the writing weight Wa. In our settings, all weights are dynamic and they depend on either the prior memory and data (during writing) or the posterior memory and the query (during reading). Formally written, we need to determine the writing weight Wn (given prior memory M, and noisy data Zę) and reading weight W (given posterior memory M and query Z) Ideally, Wo and W should satisfy WoM, = Ze and WM = Zg = Z, according to the linear assumptions over Zę- The minimum- norm least- solutions of those linear systems are Wo = ZeM and W = ZM*, where Mr and M are pseudo-inverses of Mo and M, respectively. While least-square condition is obvious since we would like to find solutions Wo and W that best fit the systems, explanation for the minimum-norm condition will be given in Appendix J.
Computing pseudo-inverse,
We do not always have explicit formula for the pseudo-inverse, and even in such cases, the formula may consist of inverse matrices which are expensive to compute. Ben-Israel and Cohen (1966) provide with an iterative way to approximate the pseudo-inverse, stated in the following theorem:
Theorem 2.1. (Ben-Cohen algorithm) Given real matrix D and an initial matrix Do of the same size with the transpose D The sequence {Di h22 defined recursively as D 2D; D,DD, will converge to the pseudo-inverse of D. With appropriate Do, the sequence will converge quadratically.
Ben-Cohen algorithm allows to compute the matrix pseudo-inverse efficiently with nearly O(1) time complexity in practice (see Section 3.5 for experimental results). For simplicity, we set the initial term Do = aD where is hyper-parameter dependent on the dataset. Deeper analysis of the initial condition for Ben-Cohen algorithm will be given Appendix G.
Algorithm We are now ready to present the Generative Pseudo-Inverse Memory (GPM) in full. Assume that the observation noise & is sampled from (O, I Algorithm illustrates a single training step of GPM. All pseudo-inverses
approximated by the Ben-Cohen algorithm.
2.2.1 REMARK: RELATION WITH EXISTING ALGORITHMS
Several properties of GPM are worth highlighting. GPM can be viewed 2-step EM algorithm (Dempster et al., 1977). Details are given in Appendix J. Moreover, noiseless setting, i.e., E 5 0, GPM and Dynamic Kanerva Machine (DKM) (Wu et al., 2018b) coincide. In DKM, solving W is related to minimizing DKL. (g(W) Ip( W X, M)), which is equivalent to the optimization problem
min (I w
WM] + W 1
This problem has a solution W. ZM (MMT + - According to Theorem D.5, W converges to W ZM+ as oe - 0. Note that w' is actually the reading weight of GPM.
2.3
ERROR BOUND
Using pseudo-inverses in Algorithm 1, we establish an error bound for the memory read-out, as stated in the following theorem:
In general (e.g. when the query is noisy version of Z), the same dynamic addressing holds.
4

---

Published as a conference paper at ICLR 2022
Algorithm 1 Single training step of Generative Pseudo-Inverse Memory Sample an episode X of length T'. Writing
1. Compute episode embedding e(X).
2. Randomize noise & from N (0, o2
I/ simulate observed data
3. Compute weight Wo M.
II dynamic addressing
4. Compute posterior memory M W Ze.
complete writing phase
Reading
1. Compute episode embedding = e(X).
similar role with Z in Figure lb
2. Compute weight mean W = ZM+
// dynamic addressing
3. Sample W ~ W. W
Il variational schema generating samples // similar role with Z, in Figure 1b complete reading phase, no iterative reading
4. Compute read-out rend-au WM.
5. Compute reconstruction X = (Zread-out)-
Updating model parameters
1. Compute the objective O 0=6 C Can using obtained terms from previous steps.
2. Update parameters via gradient ascent to maximize O.
Theorem 2.2. Let |1-112 denote the spectral norm.
Suppose there exist a, 8 e [0, 1) such that
I - Ze ll2 S a and || Ze 112 S B.
Then WM = Z(I + E), where E is the error matrix satisfying
El12 S 8 - l1
l+a I-a'
Corollary 2.3. Assume that rank Wo rank Zę
T, i.e. rows of Wo and Z are linearly
independent. Then WM Z.
Proofs are given in Appendix E. Theorem 2.2 and Corollary 2.3 establish that the error of memory retrieval can be bounded by other errors only dependent on the data Z and writing weight Wo. When rows of Wo and Ze are linearly independent, the retrieval is perfect. The trainable prior memory Mo helps the model balance approximation errors when ideal conditions are not met.
Corollary 2.3 also suggests that retrieval may still accurate if rows Wn n and Z are sufficiently linearly independent. A well-known property high dimensional space is that two arbitrary vectors are likely to be orthogonal (Gorban and Tyukin, 2018). Thus we can expect that GPM will still work fairly well when T' >> max CJ. i.c. the episode length is much greater than the number of memory slots and size of embedding vectors. Empirical evidences will be given in Section 3.4.
2.4 ATTRACTOR DYNAMICS
We demonstrate that GPM inherits properties of energy-based models. The key property of models induced from dynamical systems is iterative reading, i.e. iteratively reproduce the correct pattern from a partially broken query. With fixed memory M, the energy function of GPM can be defined as a function of two variables x and w:
Exx, -n:x== = M) + |e(xx) WM
+r.
20
Here we replaced z by e(x) and note that the residual is constant after training. Denote (W;, the pair weight and reading output the i-th iterative reading step. The output x; is iteratively fed back to the model until convergence. With x; the query for (i + 1)-th step, solving for w;+1 minimizes ||e(x)
2 which indicates E(x, w;+1) > E(x,, w,). With W in hand, the way train the model encourages X;+1 to maximize the likelihood
M). If it is the case, (x w ) > E Exx, W.+1) and therefore E(x+11, w++1) > E(x,, w.). In ideal cases, (x, will converge local minimum associated with stored pattern in the energy landscape.
5

---

Published as a conference paper at ICLR 2022
Binarized MNIST 28 28 (nats/image) 87.86
Binarized Omniglot 28 28 (nats/image) 104.75 103.38
CIEARIO
32 x 32 (bits/dim) 6.3
Method
VAE (Kingma Welling, 2014)
IWAE (Burda et al., 2016)
85,32
Improved decoders
VAXet (Sadeghi al., 2019)
78.00
2,90
MAE (Ma et al., 2019)
77.98
89.09
2.95
DRAW (Gregor et al., 2015)
87.4
96.5
3.58
MatNet (Bachman, 2016)
78.5
89.5
3.24
Richer priors
Ordered ACN (Graves ct al., 2018)
73.9
3.07
VLAE (Chen 2017)
78.53
102.11
2.95
VampPrior (Tomezak and Welling, 2018)
78.45
89.76
Memory models
VMA (Borsschei 2017)
103.6
KM (Wu et al., 20)
68.3
4.37"
DNC (Graves et al., 2016)
100
DKM (Wa et al., 8h)
75.3
77.2
4.79
Kunerva++ (Ramapuram et al., 2021)
41.58
66.24
3.28
GPM (ours)
4.03
Table I: Negative evidence lower bound of test likelihood (lower is better). Figure 12 Wu et al. (2018a).
Training ELBO, estimated from
In practice, the system might not converge to a stored pattern but spurious state, which is local minimum different from stored patterns. Even with simple neural networks in low dimensional space, spurious local minima also exist (Safran and Shamir, 2018). This phenomenon is not expected when retrieving, but it may help generate new images as demonstrated in Section 3.3.
3 EXPERIMENTS
We examine GPM on common generative memory benchmarking datasets including binarized MNIST (LeCun al., 2010), binarized Omniglot (Burda al., 2016), FashionMNIST (Xiao et al., 2017), CIFAR10, CIFAR100 (Krizhevsky, 2009) and CelebA (Liu et al., 2015). To prove the effectiveness of our memory model, we only use simple encoders and decoders. The details image preprocessing, network architecture and training procedure are given in Appendix C. Codes are available at
We compare our model to recent generative memory models such as Kanerva Machine (KM), Dynamic Kanerva Machine (DKM) and Kanerva++. In GPM, most of the parameters come from the encoder and the decoder since the trainable prior memory Mo and the weight variance ow only account for only KC + 1 parameters. Hence, the number of parameters of GPM is comparable to other baselines with similar architectures of encoder and decoder.
3.1 RECONSTRUCTION
In this task, validate the memory model's ability reconstruct image data. For each dataset, sample 32 images to form the episode as the input to the memory models during both encoding and decoding phases. We then train all the models to optimize the objective in Eq. (2) for 10,000-15,000 iterations, depending on the dataset. Table 1 reports the negative evidence lower bound (Eq. (1)) of datasets, including the binarized MNIST, binarized Omniglot
GPM and that of other baselines and CIFAR10. Results for the FashionMNNIST, CIFARIO0 and CelebA datasets are reported in Table Appendix For binarized datasets, we see significant improvement in the ELBO: 31.48 nats/image compared to current state-of-the-art 41 .588 nats/images MNIST dataset and 25.68 nats/image compared current state-of-the-art 66. 66.24 nats/image on Omniglot dataset. On RGB datasets, GPM shows competitive result. We note that for complex image data, the role of the encoder and decoder is very important and GPM's ones are simpler than those of Kanerva++. Hence, we underperform Kanerva++ CIFAR10 dataset. However, compared to models with similar encoder-decoder like KM and DKM, GPM performs much better, which indicates the benefit of our pseudo-inverse memory mechanisms.
To verify that our GPM supports exact memory retrieval, we measure the cosine similarity between the data written the memory and memory read-out's of GPM in Omniglot task (see Fig. 6 of

---

Published as a conference paper at ICLR 2022
salt & pepper noise (15%)
block noise (12
12)
rotation noise (30")
1'
8
7'
16
7
4
T 8
T'
16
7' 4
8
7
16
GPM (ours)
40.59% %
37.75%
16.89%
57.42%
40.10%
18.69%
66.09%
57.55%
39.98%
(Wu et al., 2018h)
5.20%
1.24%
0.61%
7.18%
2.10%
1.18%
7.67%
4.33%
1.79%
Table 2:
Denoising success rate on binarized Omniglot dataset. A denoising process is successful if it can retrieve the original image with at most 1% error, which is equivalent to 7 pixels.
Appendix). As expected, GPM almost retrieves exactly what was written to the memory (average similarity s 1), which is much better than that of Dynamic Kanerva Machine (0.82).
3.2 DENOISING
The denoising capability of a memory model resembles human's ability to retrieve old memories with blurry clues. This process can be implemented using iterative reading, where in each step the model adds some more details to the image to reconstruct the original picture from a noisy query image. Illustration for the denoising process of GPM given in Appendix B.
To measure the denoising capability of GPM and DKM, we run denoising experiments with different episode lengths, types of noise and levels of noise on the binarized Omniglot dataset. We the Hamming distance to measure the error between denoised images and correct ones, In all experiments, we run iterative reading for 20 steps. We report results for the case T = 16 in Fig. while results for other cases can be found in Fig. 8 of Appendix. Overall, GPM achieves a significantly better performance than that of DKM. Remarkably, GPM maintains a clear performance gap when the episode lengths or the level of noise vary. To better quantify the difference, we reported the denoising success rate of GPM and DKM in Table 2. Here we consider denoising process to be successful if can recover the original image with at most 1% error, which is equivalent to at most 7 pixels for the Omniglot dataset. The results show that GPM also outperforms DKM in all cases with a performance gap ranging from 15% to 58%.
salt & pepper noise
block noise
rotation noise
80
Hamming error
72.6
76.25
78.54
60
6..00
63.6
68.55
56.73
35
60
50.55
65.72
60
06.54
50
50
50
DKM
41.42
40
GPM
36.6
30
30
29.59
.2
23.79
19.51
DKM GPM
DKM
20
20
10
13
10
7.53
10
10.2
GPM
5%
10%
15%
20%
6%565
9
12
15
15"
30'
45'
Figure 2: Hamming error measuring the denoising capibility of GPM and DKM (lower is better) with T 16 on Omniglot dataset. We test denoising capability of both models with different types of noise (salt & pepper noise, block noise, rotation noise) and levels of noise (5% 20% salt & pepper noise, block noise with block size from 6 6 15 x 15, rotation noise with rotation angle from 15p to 15
3.3 GENERATION
We illustrate the ability to generate new images of GPM using Omniglot and CIFARIO images in Fig. 3a. The generation process consists of 2 main steps: (1) sample images to form episode and write it to the memory; (2) sample w ~ p(w) (w is a vector of size 1 x K) and take z = wM to be the read-out vector. The generated images will be improved via iterative reading. We observe that GPM can generate images that do not appear in the written episode. This phenomenon can be viewed in Fig. 3a-left, where we compare generated patterns with their most similar ones in terms of Hamming distance. Here the generated images with additional details are generally different from their nearest neighbors. More interestingly. in Fig. 3a-right, we can see a generated aircraft image that inherits the background of the frog image (the 3rd row). Theoretically speaking, these new images are formed from spurious local minima, as discussed in Section 2.4.
3.4
GPM AS A HUGE STORAGE
We conduct experiments to test the memory capacity of GPM. The experiments still revolve around reconstructing, denoising and generating images, yet on larger episode length. We use the whole Omniglot dataset with 24, 345 training images to train GPM for around 24, 000 iterations for all
7

---

Published as a conference paper at ICLR 2022
(b)
lterations
iterations
3
D8A GPM-TH3N GPM, THI
T- K--44
Lime ($)
0.35
UB
4
4
4
08
112 0.25
3 13 approximation steps
Figure 3: (a) GPM's generated samples, Images in the box are nearest images in the episode compared with final generated images on their left. Left: Omniglot patterns. Distance between images is measured by the Hamming distance. Right: CIFARJO images. Images in the leftmost the episode written memory. Fach image is repeated 3 times help the generations better. We use Fuclidean metric measure distance hetween images. (b) Running time per iteration. Left: Running time per iteration comparison between GPM and DKM. GPM has a time complexity of almost O(1) with respect to the episode size and memory size. Right: Running time per iteration of GPM with different number of pseudo-inverse approximation steps.
experiments. For convention, denote the T-GPM as the GPM trained episodes of length T. Results are shown in Fig. 4.
In the reconstruction experiment, we keep the memory size fixed and increase the episode length from minimum (equivalent to the number of memory slots) to maximum (24, 345, which the whole set of training images). We run the experiment with two memory configurations: 8 x 100 and 32 x 100. With the same episode length, the 32 x 100 memory always performs better, which is reasonable since bigger memory enables better storage capability. We also observe more interesting phenomenon in both configurations: from certain point, the reconstruction loss seems to be stable even when we double the episode length. This agrees with earlier discussion in Section 2.2, where we argue that GPM can handle big episodes thanks to the orthogonality of random vectors in high-dimensional space.
We also test the denoising and generating capabilities of GPM when trained with large episode size. We are curious whether GPM can keep these abilities (to some extent) when storing lots of information. We use the 24, 345-GPM with 32 x 100 memory in these experiments. At test time, we first write the whole test set of 8070 images to the memory and keep this posterior memory fixed, then either imput noisy queries for denoising sample from the memory for generating images. Despite the huge amount of information compressed into the memory, the model can still denoise and generate images with moderate quality. The average Hamming error when denoising is 97.08, which is approximately 12.4% of the total pixels.
We note that other baselines such KM and DKM are inapplicable such large-scale scenario due to their slow memory mechanisms. In contrast, GPM can be trained efficiently even with episodes of 24, 345 images. More experiments regarding this point conducted in the next section. iterations
iterations
120
recon. loss
100
t
52 100
20
100
5
log2(episade length)
(a)
(b)
(c)
Figure 4: (a) Reconstruction loss of GPM with fixed memory size and increasing episode length. (b) Denoising salt and pepper noise (5%) of the 24, 345 with 32 x 100 memory. Patterns in the first column are original ones; patterns in blue are noisy queries; following columns are denoising process during iterative reading. (c) Generated patterns of the 24, 315M-M with 32 x 100 memory. Patterns in the orange box are closest. patterns written to the memory compared with generated patterns on their left.
3.5 ABLATION: RUNNING TIME
GPM is designed to avoid the computation complexity O(K3) of inverting matrices and (TT) of online Bayesian inference. We conduct experiments to show the time efficiency of GPM compared to DKM in practice. All operations are computed on a single GPU. We use the inverse function of Pytorch 1.8.0 (Paszke al., 2017) for batch matrix inverse. Results are shown in Fig. 3b.
8

---

Published as a conference paper at ICLR 2022
In the first experiment, we GPM with 7 approximation steps for the pseudo -nveerss and compare the running time against DKM in different cases of episode and memory size. As expected, the running time of DKM increases as the memory size K increases while GPM maintains almost the same performance. Moreover, we can see a problem of Bayesian update on the running time: if we double the episode size and keep the same memory size, the running time also doubles. In contrast, it only yields a modest increase in the running time of GPM.
In the second experiment, we would like to see how the number of pseudo-inverse approximation
steps affects the running time of GPM in two cases: T = 64, K = 64 and T = 128, K = 64. The running time curves in the two cases share a similar trend: they depend linearly on the number of approximation steps. Hence, it is important to choose an appropriate initial term for the approximation sequence to reduce the number of approximation steps. More discussion given in Appendix G.
4 RELATED WORK
Memories are known to be critical to tasks that demand long-term dependencies (Hochreiter and Schmidhuber, 1997; Graves et al., 2016; Santoro et al., 2016; Vaswani et al., 2017; Le al., 2019; Munkhdalai et al., 2019). When all stored data are available to retrieve through attention mechanism (Sukhbaatar et al., 2015; Vaswani et al., 2017), we indeed perform retrieval over a content-addresssabe memory such Hopfield networks (Hopfield, 1982; Ramsauer et al., 202 1) and Kanerva's a sparse distributed memory (SDM) (Kanerva, 1984; Bricken and Pehlevan, 2021).
These works are primarily designed for storing and retrieval of patterns, mostly in deterministic manner, and thus less concerned about noise and data generation (Le et al., 2018). Kanerva machines (Wu et al., 2018a), inspired by the addressing mechanism of SDM, are generative memory models which fill these gaps. Here memory update/retrieval and addressing mechanism are treated as Bayesian inference where posteriors dynamic inference handles noisy inputs better due to the convergence of the attractor dynamics to fixed points (Wu et al., 2018b). The Kanerva machines thus belong a class of latent variable models with very expressive latent prior. These generalize Variational AutoEncoders (VAE) (Kingma and Welling, 2014), deep encoder-decoder neural networks that can generate high-quality data in high dimensional space. VAEs are very powerful when equipped with a high-capacity decoder (Gregor et al., 2015; Bachman, 2016; Ma et al., 2019; Sadeghi et al., 2019) and a expressive prior (Chen et al., 2017; Graves et al., 2018; Tomezak and Welling, 2018) 8). Here memory-bass priors in Kanerva machines offer a systematic approach to bring more representation power to VAEs.
updated when new data episode arrives. This iterative and
However, Bayesian inference in the original Kanerva machines is expensive. To address this drawback, Marblestone et al. (2020) introduced the Product Kanerva Machine to reduce the heavy cost of inverting matrices in the original model. An enhanced variant known Kanerva+ (Ramapuram et al., 2021) uses a more powerful encoder and regional memory writing-reading to help improve both the retrieval accuracy and training time.
Our work takes a radically alternative view in that we treat memory update as seeking least-square solutions to linear systems. This permits the use of fast matrix useudo-inverse for the memory operations (Ben-Israel and Greville, 2001). Indeed the pseudo-inverse has been studied in the associative memory literature. Examples include Kohohen-type linear associative memory, which can be referred as a pseudo-inverse neural network (Kohonen, 2012). Personnaz et al. (1986) proposed the projection rule (other than Hebb's learning rule in standard Hopfield Network) involving matrix secudo-inversed to guarantee perfect storage and retrieval. However, the equilibrium point produced by the projection rule may not be asymptotically stable the sense that adding new vectors may affect the existing equilibria in the network. To overcome this problem, Yen and Michel (1991) introduced learning and forgetting algorithm with efficient computation. As far as we are aware, the pseudo-inverse is not commonly used in deep memory networks partly because of the difficulty to compute it exactly, although several attempts have been made to improve the computation efficiency (Greville, 1960; Ben-Israel and Cohen, 1966; Courrieu, 2008; Toutounian and Ataei, 2009).
DISCUSSION
We have proposed Generative Pseudo-Inverse Memory (GPM) to overcome crucial limitations of previous generative memory models. GPM is not only able to operate fast but also store a large amount of data at time while maintaining abilities of denoising corrupted patterns and generating

---

Published as a conference paper at ICLR 2022
novel patterns. We derived associated energy function and showed that iterative updates in GPM induce attractor dynamics converging toward fixed points. We demonstrated these capacities on an extensive set of experiments, obtaining superior results.
These new capacities of GPM as a generative memory open up new exciting rooms of investigation. primary direction is positioning GPM as working memory whose size and processing speed known to critical for high-level reasoning (Kyllonen and Christal, 1990), i.e., the capacity to deduce new knowledge through manipulating the old. Here the query encoder will support arbitrary query format, and the decoder will support answer generation. As GPM is designed for episodic handling, streaming data can be periodically cached through local registers before sending to GPM, as suggested in slot-based memories (Le et al., 2019). Finally, GPM may offer fast episodic learning and generative exploration in RI. agents.
REFERENCES
D. Addis, Alana T. Wong. and D. Schacter. Remembering the past and imagining the future: Common and distinct neural substrates during event construction and claboration. Neuropsychologia, 45: 1363-1377, 2007.
Philip Bachman. An architecture for deep, hierarchical generative models. In NIPS, 2016.
S. Banach. Sur les opérations dans les ensembles abstraits et leur application aux équations intégrales. Fundamenta Mathematicae, 3:133-181 1922.
A. Ben-Israel and D. Cohen. On iterative computation of generalized inverses and associated projections. SIAM Journal on Numerical Analysis, 3:410-419, 1966.
A. Ben-Israel and T. Greville. Generalized inverses: theory and applications. 2001.
Jörg Bornschein, Andriy Mnih, Daniel Zoran, and Danilo Rezende. Variational memory addressing in generative models. Advances Neural Information Processing Systems, pages 3920-3929, 2017.
Trenton Bricken and Cengiz Pehlevan. Attention approximates sparse distributed memory. NeurIPS, abs/21 1105499, 2021.
Yuri Burda, Roger B. Grosse, and R. Salakhutdinov. Importance weighted autoencoders. ICLR, 2016.
Xi Chen, Diederik P Kingma, Tim Salimans, Yan Duan, Prafulla Dhariwal, John Schulman, Ilya Sutskever, and Pieter Abbeel. Variational lossy autoencoder. ICLR, 2017.
Pierre Courrieu. Fast computation of moore-penrose inverse matrices. arXiv preprint arXiv:0804.4809 2008.
A. Dempster, N. Laird, and D. Rubin. Maximum likelihood from incomplete data via the em algorithm. 1977.
Alexander N. Gorban and Ivan Y. Tyukin. Blessing dimensionality; mathematical foundations of the statistical physics of data. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 376, 2018
Alex Graves, Greg Wayne, Malcolm Reynolds, Tim Harley, Ivo Danihelka, Agnieszka Grabska- Barwińska, Sergio Gómez Colmenarejo, Edward Grefenstette, Tiago Ramalho, John Agapiou, et al. Hybrid computing using neural network with dynamic external memory. Nature, 538(7626): 471-476, 2016.
Alex Graves, Jacob Menick, and Aaron van den Oord. Associative compression networks for representation learning. arXiv preprint arXiv: Te04.04470000 2018.
K. Gregor, Ivo Danihelka, A. Graves, Danilo Jimenez Rezende, and Daan Wierstra. Draw: A recurrent neural network for image generation. ICML, 2015.
TNE Greville. Some applications of the pseudoinverse of matrix, SIAM review, 2(1):15-22, 1960.
10

---

Published as a conference paper at ICLR 2022
Kaiming He, X. Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 770-778, 2016.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9()): 7735-1780, 1997.
John Hopfield. Neural networks and physical systems with emergent collective computational abilities. Proceedings of the national academy of sciences, 79(8):2554-2555 -5588, 1982.
Edwin Jaynes. Probability theory: The logic of science. Cambridge university press, 2003.
A. Jensen and Ella Munro. Reaction time, movement time, and intelligence. Intelligence, 3:121-126, 1979.
P. Kanerva. Self-propagating search: a unified theory of memory (address decoding, cerebellum). 1984.
Diederik P. Kingma and M. Welling, Auto-encoding variational bayes. ICLR, 2014.
Teuvo Kohonen. Self-organization and associative memory, volume 8. Springer Science & Business Media, 2012.
A. Krizhevsky. Learning multiple layers of features from tiny images. 2009.
Kyllonen and E. Christal. Reasoning ability (little more than) working-memop capacity?! Intelligence, 14:389 1.3, 1990.
Hung Le, Truyen Tran, Thin Nguyen, and Svetha Venkatesh. Variational memory encoder-decoder. In NeurIPS, pages 1515-1525, 2018.
Hung Le, Truyen Tran, and Svetha Venkatesh. Learning to remember more with less memorization. In ICLR 2019: Proceedings of the 7th International Conference on Learning Representations, 2019.
Yann LeCun, Corinna Cortes, and CJ Burges. Mnist handwritten digit database. ATT Labs [Online]. Available: htp::/yann. wewphyannneccun...m www.lllcccc....te...... cow/exdb/niisstt 2, 2010.
Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang. Deep learning face attributes in the wild. In
Proceedings of International Conference on Computer Vision (ICCV), December 2015.
Xuezhe Ma, Chunting Zhou, and E. Hovy. Mae: Mutual posteriorr-diverenne regularization for
variational autoencoders. ICI.R, 2019.
Adam Marblestone, Yan Wu, and Greg Wayne. Product kanerva machines: Factorized bayesian memory. arXiv preprint arXiv:2002.02385, 2020.
Tsendsuren Munkhdalai, Alessandro Sordoni, Tong Wang, and Adam Trischler. Metaleamed neural memory. NeurIPS, 2019.
J. Okuda, T. Fujii, H. Ohtake, T. Tsukiura, K. Tanji, Kyoko Suzuki, R. Kawashima, H. Fukuda, M. Itoh, and A. Yamadori. Thinking of the future and past: the roles of the frontal pole and the medial temporal lobes. Neurolmage, 19: 19:1369-1380, 2003.
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. 2017.
Personnaz, Guyon, and G Dreyfus. Collective computational properties of neural networks: New learning mechanisms. Physical Review A, 34(5):4217, 1986.
Prajit Ramachandran, Barret Zoph, and Quoe V. Le. Swish: a self-gated activation function. arXiv: Neural and Evolutionary Computing, 2017.
11

---

Published as a conference paper at ICLR 2022
Jason Ramapuram, Yan Wu, and Alexandros Kalousis. Kanerva++: extending the kanerva machine with differentiable, locally block allocated latent memory. ICLR, 2021.
Hubert Ramsauer, Bernhard Schäfl, Johannes Lehner, Philipp Seidl, Michael Widrich, Thomas Adler, Lukas Gruber, Markus Holzleitner, Milena Pavlović, Geir Kjetil Sandve, al. Hopfield networks is all you need. arXiv preprint trXiv:2008.02211 2020.
Hubert Ramsauer, Bernhard Schäfl, Johannes Lehner, Philipp Seidl, Michael Widrich, Lukas Gruber, Markus Holzleitner, Thomas Adler, David Kreil, Michael K Kopp. al. Hopfield networks is all you need. In International Conference Learning Representations, 2021.
S.M Rump. Verified bounds for singular values, in particular for the spectral norm of matrix and its inverse. Bit Numer Math 51, 3674384, 2011.
Hossein Sadeghi, Evgeny Andriyash, Walter Vinci, Lorenzo Buffoni, and Mohammad H Amin. Pixelvac++: Improved pixelvae with discrete prior. arXiv preprint arXiv:1908. 09948, 2019.
Itay Safran and O. Shamir. Spurious local minima are common two-layer relu neural networks. ICML., 2018
Tim Salimans, A. Karpathy, Xi Chen, and Diederik P. Kingma. Pixelenn++: Improving the pixelenn with discretized logistic mixture likelihood and other modifications. ArXiv, 0abs/1701.005111 2017.
Adam Santoro, Sergey Bartunov, Matthew Botvinick, Daan Wierstra, and Timothy Lillicrap. Meta- learning with memory-augmentte neural networks. In International conference on machine learning, pages 1842-1850. PMLR, 2016.
D. Schacter, D. Addis, D. Hassabis, Victoria C. Martin, R. N. Spreng. and K. Szpunar. The future of memory: Remembering, imagining, and the brain. Neuron, 76:677-694, 2012.
Söderström and G. Stewart, On the numerical properties of an iterative method for computing the mooreâpenrose generalized inverse. SIAM Journal Numerical Analysis, 11:61-74, 1974.
G. S. Stiles and Dong-Lih Denq. On the effect of noise on the moore-penrose generalized inverse associative memory. IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-7: 358-360, 1985.
Sainbayar Sukhbaatar, Arthur Szlam, Jason Weston, and Rob Fergus. End-to-end memory networks. NIPS, 2015.
Jakub Tomezak and Max Welling. Vae with vampprior. In International Conference Artificial Intelligence and Statistics, pages 1214-1212 1223. PMLR, 2018
F Toutounian and A Ataci. A new method for computing moore-penrose inverse matrices. Journal of Computational and applied Mathematics, 228(1):1224417 2009.
Ashish Vaswani, Noam M. Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. ArXiv, abs/1706.03362, 2017.
Yan Wu, Greg Wayne, A. Graves, and T. Lillicrap. The kanerva machine: A generative distributed memory. ICLR, 2018a.
Yan Wu, Greg Wayne, Karol Gregor, and Timothy Lillicrap. Learning attractor dynamics for generative memory. NewrIPS, 2018b.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnis mnist: a novel image dataset for benchmarking machine learning algorithms. ArXiv, abs/1 708.07777,,
G. Yen and A. Michel. A learning and forgetting algorithm in associative memories: results involving pseudo-inverses. IEEE Transactions on Circuits and Systems, 38:1193-1205 1991.
12

---

Published as a conference paper at ICLR 2022
APPENDIX
A RECONSTRUCTIONS
We provide visualizations for the reconstructions of GPM on numerous datasets in Figure 5. We also provide empirical evidence to show that the optimization problem associated with GPM (Eq. (4)) more direct than DKM (Eq. (3)) in Figure (6): the cosine similarity between stored vectors and read-out's of GPM is nearly 1, which is much better than DKM (around 0.82). We report the ELBO of DKM and GPM over datasets, including FashionMNIST, CIFARIO0 and CelebA in Table 3.
X
H
X
H
B
5
2
N
E
5
8
N
x
8
7
8
K
1
(a)
(b)
(c)
(d)
Figure 5: Reconstructions of GPM. Left: original images. Right: reconstructions. (a) Omniglot (b) CIFARIO
(c) CIFAR100 (d) CelebA
B DENOISING
We demonstrate denoising capibility of GPM in Fig. 7. The denoising process consists of two steps: first write the correct patterns into the memory, then read from the memory using noisy queries. The image will be completed during iterative reading. We also report the full results of the denoising experiment described in Section 3.2 in Figure 8.
13

---

Published as a conference paper at ICLR 2022
Figure 6: Average cosine similarity between exact data and read-out's ' in DKM and GPM. Train and test Omniglot dataset.
Fashion MNIST
CTEAR100
CelebA 192 192 (bits/dim)
28 28
32 32
Method
(bits/dim)
(bits/dim)
DKM (Wu et al., 2018b)
3.97
4.88
4.71
Kanerva++ (Ramapuram al., 2021)
3.40
GPM (ours)
3.96
4.05
4.63
Table 3: Negarive evidence lower bound of test likelihood (lower better) on FashionMNIST, CIFAR 100 and
CelchA datasets. Our implementation.
C TRAINING DETAILS
The encoder consists of layers, each of which a convolution layer with x filter with stride followed by Resnet block with bottleneck (He et al., 2016). The decoder is simply mirror of the encoder with transpose convolutional layer. We use the swish activation function (Ramachandran al., 2017) non-line non-linear layers. For binarized datasets, we use 16 filters for all convnets; for real-valued datasets, we use 256 filters to adapt with the complexity of the data.
The Omniglot is dataset with great diversity, consists of 1623 different classes and 20 images in each class. Following settings in (Burda et al., 2016), the dataset is splitted into 24,345 training and 8,070 test examples. We use 32 100 memory for this dataset. The data noise when writing sampled from (0, 0.5² At each training step, randomly sample 32 images to form episode. We run the Ben-Cohen algorithm for steps to approximate the pseudo-inverses, with the initial term 10 times the transpose of the matrix which we want to calculate the pseudo-inverse. We use the Bernoulli likelihood for all binarized datasets.
For realevalued datasets, other settings are the same with the Omniglot dataset, except for the initial terms of the Ben-Coher algorithm: 10-1 times the transpose of the matrix when approximating pseudo-inverse of the weight matrix and 10-5 times the transpose of the matrix when approximating pseudo-inverse of the memory. We the discretized mixture of logisties (Salimans et al., 2017) for the output distribution.
128 x 512 memory with data noise sampled from (00 I). All
In all experiments, we use the Adam optimizer with learning rate varying from 5 10-5 to 5 10-4 depending on the dataset. We use weight decay of 10-3 along with gradient clipping threshold 10. For real-valued datasets, we additionally use scheduler to reduce the learning rate by 0.99995 after each training epoch. We train all models for 500-1000 epochs with exception 30 epochs for CelebA dataset.
D PROPERTIES OF PSEUDO-INVERSE
In this section, we outline the definition and some important properties of the pseudo-inverse of matrix. Most of the proofs of following propositions and theorems can be found in (Ben-Israel and Greville, 2001).
Definition D.1. For every real matrix A (square or rectangular), there is a unique matrix Y satisfying all following conditions: AYA A, YAY Y, (AY)" AY and (YA) T YA, where denotes the transpose of a matrix. The matrix Y called the pseudo-inee inverse of A, denoted by +
If A is square matrix and non-singular, then A is the inverse A 1 of A. If A is rectangular of size m x n, then A is of size n x m. The following propositions shows some important relations between A and A +
14

---

Published as a conference paper at ICLR 2022
K6
H2
16
%
E5
14
82
16
iterations
8
12
12
12
16
16
144
14
14
16
14
A
1
16
(b)
(c)
iterations
(d)
(e)
Figure 7: Retrieving pattern with noisy query during iterative reading. Top rows correct patterns; rows in the boxes corrupted patterns; following rows retrieval process with iterative reading. (a) Salt and pepper noise (15%). (b) Block noise (12 12 block) cover a part of the correct pattern. Rotation noise (rotation angle uniformly selected from -45 to 45 degrees). (d) Gaussian noise with standard deviation 0.5. (e) Illustration of energy decrease during retrieving Omniglol patterns. Although sometimes the energy diverges and iterative reading leads to meaningless pattern, overall, the energy decreases during iterations.
salt & pepper noise
block noise
rotation noise
D01
614
Hommingg STOP
T-4
3g1
314
325
12
Homming
T-x
8
121
1N
606
12
664
024
Hanming oner
T-16
170 5+4
25-35
Figure Hamming error measaring the denoising capibility of GPM and DKM (lower is better). Experiments are conducted on binarized Omniglot dataset. We test denoising capability of both models with different types of noise (salt & pepper noise, block noise, rotation noise) and levels of noise (5% 20% salt & pepper noise, block noise with block size from 6 6 15 x 15, rotation noise with rotation angle from 15" to 45%).
Proposition D.2. Let A be real matrix. Then
15

---

Published as a conference paper at ICLR 2022
1. A A+A= = I, if and only if rankA (i.e. columns of A are linearly independent), where I, is the n x n identity matrix;
2. AA+ Im if and only rankA m (i.e. rows of A linearly independent), where Im
is the m identity matrix.
Proposition D.3. For every real matrix A:
1. (A (A+)* = A;
2. A + = (A+);
3. A = (ATA) A = AT
A and B are square invertible matrices such that AB also invertible, then we have the well- known property (AB) = --'' The same property does not always hold for pseudo-inge inverse. However, with
sufficient condition of independence, we will get the desired property.
Proposition D.4. If A has linearly independent columns or B has linearly independent rows, then (AB)* = A
+Ilm) always Theorem D.5. For any real matrix of size n, the limit lim A (AAT a
exists. Moreover, lim A (AAA + = A+. a o'00
The concept of pseudo-inverse arose when ones tried to solve the linear system Ax = b, where b is some vector with appropriate size. When the system has no solution, it is reasonable to find some vector x that minimizes the Euclidean norm of the residual = Ax. Any solution of the optimization problem minx |b Ax||F (where ||-I|x is the Frobenius norm) is called the least- square solution of the system Ax = b. can be proven that x = A is a least-square solution. Moreover, among the least-square solutions of system Ax b, A b is the one of minimum Euclidean norm, i.e. the minimum-norn least-square solution. This result can be generalized as in the following proposition.
Proposition D.6. Lei A, B,D D be real matrices with appropriate size. The minimum-norm least- square solution of the system AXB X A D
E PROOFS OF THEORETICAL RESULTS ON ERROR BOUNDS
We provide the proofs for Theorem 2.2 and Corollary 2.3.
Proof Theorem 2.2. For convention, let us denote Ew, Wo W Following Algorithm 1,
we get
WM ZZ, WoW, Z₃
ZzZ (I+ Ew. kw.,)zg )Zg
z + (Z 4e 1) + Z Ew, Zg|
Since || Z 2/ S a. by (Rump, 2011, 1, Lemma 2.2), it follows
IZella S / a and |2
Vi Since ||-1|2 multiplicative norm, finally have
(z Z5 - I) + Ew, Ze
z ZE
I
12
+
1 Ew. Ws/
1
|E 1l,
1-a'
which is our desired result.
Proof of Corallary 2.3: This is a special case of Theorem 2.2. When rows of Wa and Z are independent, W, W = and Z which leads to Ew, = 0 and = 0.
F ITERATIVE READING FROM THE VIEW OF FIXED POINT
In addition to the discussion in Section 2.4, we can alternatively think about the attractor as the fixed point of the reading operation. Assume that the current query is q and the next query is determined
16

---

Published as a conference paper at ICLR 2022
by 91+1 f(qe), where ff represents for the reading operation. If {qr} converges to q", then q' = =(q"), which means q is a fixed point of the model is well rell-trained, stored patterns are fixed points of f. (Banach, 1922) provides sufficient condition for iterative sequence to converge to fixed point. Roughly speaking, if q" a fixed point of f such that [T ) < (where is the Jacobian of /) and the whole sequence (qi (22 locates in small neighborhood of q" then q q" This result demonstrates the ability to converge to a correct pattern given a good enough initial query. Similar spurious local minima in the energy landscape. there also exists many spurious fixed points in the f landscape (see Fig. 9). This phenomenon is not expected when retrieving, but it may be helpful case we want to generate new images as demonstrated Section 3.3. pettern
point average pallem
I ml T.
m
m
(+)
Figure 9: The three cases of fixed points. (a) Fixed point is single pattern: patterns are stored if they are well separated. Each pattern has single fixed point z; close it. (b) Fixed point is average of similar patterns: 2; and zy similar each other and not well separated. The fixed point m. is spuruous fixed point that is to the mean m, of the similar patterns. (c) Fixed point is average of patterns: no pattern well separated from the others. A single glohal fixed point m. exists that is close to the arithmetic mean m. of all patterns. Images and caption are taken from (Ramsauer et al., 2020).
G INITIAL CONDITION FOR BEN-COHEN ALGORITHM
Suppose A is a real matrix. With 0 < a 2, where is the largest eigenvalue of AAT, the sequence defined as A, = aA A, 2A, A,AA, will converge to A (Ben-Israel and Cohen, 1966). This choice of initial term may lead slow convergence when the condition number <(A) = ||||2||A* I]2 is large (Söderström and Stewart, 1974). If we start with an An such that AgA (AaA) and Ag is already close A for example Ag A ATAAA OI) where 5 > 0 and small enough, then {A,)20 converges quadratically to A + However, this requires us to
calculate the inverse of AA + SI, which we tend to completely avoid in GPM. Therefore we keep the original setting Ben-Cohen for the initial term and let the model adapt with the approximation error.
H SOLUTION OF BAYESIAN UPDATE OPTIMIZATION PROBLEM
Let Mg, M denote random variables of the prior and posterior memory, respectively, and suppose that both have matrix Gaussian distributions. Specifically, M, ~ (RR. Uo. I) and M ~ NRR,, U, Given the prior Mg, the to-be-written data Z and the writing weight Wo. the optimization problem
minE A.B
(I|M- Moll
s.t. M AZ + and Z = WoMo +
has unique solution M ~ N(R, U, where
R Ro U 0 WT (W.U,W, + Ex) (Z- WR)
and U U U WT (WoU, + -ee)) WoU..
where Eg is diagonal matrix whose diagonal elements are og.
I DERIVATION FOR EVIDENCE LOWER BOUND
The evidence lower bound of the conditional log-likelihood p p(X]M) can be derived
17

---

Published as a conference paper at ICLR 2022
p W)
[n)(X By(w)
In
((W)
(X|W. M)P ((M)
[g(w)
In
P ()(()
= L + (P
RELATION WITH EM ALGORITHM
We show that GPM can be viewed 2-step EM algorithm (Dempster et al., 1977). Let us remind ourselves the log-likelihood approximation derived in Section 2.1: Inp(X|M) = By(w) In p] M) (Pk)(( + DKL (x)) W M)).
(8)
Keeping p (vec W)) ~ / (0, I) in mind, we can rewrite the conditional log- ligeliiklihood as
M) w I, + IZ WM 2
+
(9)
20
where R is residual term that is independent W. From the perspective EM algorithm and Eq. ((9)), Algorithm can be thought as 2-step process to maximize the log-likel;hood:
1. Keeping the likelihood unchanged and tightening the bound by minimizing I WM
2. Maximizing (,() In p(X W, M), i.e. the negative reconstruction loss.
Note that in training, maximize the evidence lower bound LT Ey In (x M) (g (KL))(W))lpl (P)))(() instead of (w) (X M). Therefore, for the maximum values of fT and Eyww, ( M) to as close as possible, we look for W that minimizes DRL(a (l W)). Since p (vee(W)) ~ 'N' (0,I), this is equivalent to seeking W with mini- mum norm. This fits with the step of finding the weight matrix W in the reading phase, where we determine W = ZM+, which the least-square minimum-norm solution of the linear system WM
18


Reviews:
[{"review_id": "psQXzrwC4jb", "reviewer": "Reviewer_DcwF", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "## Strengths\n   - The proposed method seems to perform much better than competing methods on the toy experiments\n\n## Weaknesses\n   - In my opinion, the authors don't provide a clear enough review of the relevant literature. The only section with some detail on related work is section 2.2.1, and connections are only drawn to DKMs and the EM algorithm. Given that GPM is compared against several methods in Table 1, none of which are described in any depth besides KMs and DKMs it would be useful to provide some context for these methods.\n   - Some of the comparisons in Table 1 seem a little strange. For example, every method in the \"Improved decoders\" section outperforms GPM in terms of negative ELBO on CIFAR-10, which is arguably a more relevant (though still toy) problem. Based on this, I would expect that these methods would outperform GPM on CIFAR-100 and CelebA too, however, these numbers were omitted from the table and instead GPM was proclaimed as the best. I think if the authors want to compare against these methods, then either they should include results for the other datasets as well, omit the comparison or not conclude GPM as the best on datasets on which performance metrics for the other methods are unavailable.\n   - It is unclear to me what is being reported as negative ELBO in Table 1 for the memory models. Is it the quantity from Eq (1) or Eq (2)?\n   - I find the results for VAEs, IWAEs and the \"Richer priors\" section in Table 1 superfluous, can the authors clarify why these were included?\n   - My current understanding is that the \"only\" difference from DKMs is that GPM optimizes the objective in Eq (4) instead of Eq (3) and uses fast approximations to the pseudo-inverses of matrices involved in the memory update step. Given this, it is unclear to me how the large improvements reported in Table 1 from DKM to GPM can arise. Could the authors comment on this?\n   - Apart from Figure 1, every figure needs improvement. Especially in Figure 4, without zooming heavily the axes are completely unreadable. In my opinion, Figure 3 and Figure 4b and 4c are trying to show too much and the result is cluttered. I think it would be more valuable to include fewer rows with larger images.\n\n### Minor items\n   - in the paragraph below Eq 1 the sentence contains a mistake, the KL in Eq is from $q(W)$ to $p(W)$ and not from $p(W)$ to $q(W)$\n   - I believe that on a few occasions the authors use the word \"quantize\" to mean \"quantify\"\n", "summary_of_the_paper": "The authors propose a novel deep generative memory model called Generative Pseudo-inverse Memory (GPM) that extends Dynamic Kanerva Machines (DKM, [1]). These models are both deep generative models that maintain a hidden state similar to recurrent neural networks called memory and have ways of writing into and reading from this memory. A key limitation of DKMs is that the time complexity of updating the memory scales cubically in the memory dimensionality and linearly in the episode length. The authors observe that by slightly altering the optimization objective that GPM has to solve, under mild assumptions the memory update can be performed much more efficiently, allowing them to write entire datasets into the memory of the GPM with little computational cost.\n\nThe authors perform some experiments on some toy datasets to validate their method and obtain good results against related methods.\n\n[1] Y. Wu, G. Wayne, K. Gregor, and T. Lillicrap. Learning attractor dynamics for\ngenerative memory. NeurIPS 2018", "summary_of_the_review": "I believe that the theoretical contributions of the paper with respect to DKMs is good if perhaps a bit incremental, however, I found the empirical results questionable.\nIf the authors can address my questions I will consider raising my score.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "iGdtU5gsReq", "reviewer": "Reviewer_NH7Y", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "(i) The overall conceptualization presented here is neat. The authors propose an efficient implementation for their algorithm, demonstrate performance on a variety of tasks both quantitatively and qualitatively. \n\n(ii) The text, however, is a bit hard to follow at times and needs to be severely improved both clarity-wise and grammatically.\n(a) I found the various usages of \"prior memories\" and \"posterior memories\" confusing. To me, it seemed to imply that probability densities were explicitly defined on the memories (i.e. Ms). But it turns out that the parameterization was actually on the read in/out weights (Ws) which implicitly defined distributions on the memories. Furthermore in the section \"Memory inference\" the authors switch to considering deterministic memories. In general, it would be much appreciated if the authors clarified if/when they are estimating true posterior densities.\n\n(b) There are also terminologies presented in the main body of the paper (such as \"temporary readout\") that are barely re-used throughout the article. It might be better to avoid these (at least while presenting the core ideas) to improve readability. \n\n(c) In Equation 3, Z is presented as a linear function of M_0, but Z is in fact a function of X from Figure 1. Could the authors clarify this mismatch?\n\n(d) The paper can benefit from a thorough grammatical check and proofreading. Examples include:\nPg 1 \"This dynamics enables GPM...\" --> These dynamics enable GPM...\nPg 2 \"dependent of the episode\" --> dependent on the episode\nPg 5 \"Detail is given in Appendix J\" --> Details are given in Appendix J\n\n(iii) This study also warrants proper comparisons to modern variational approaches. The empirical evaluations presented in the study only reports metrics from classic approaches. Is there a reason why Table 1 is incomplete? Also, the functional benefits of the proposed approach versus variational methods aren't detailed explicitly. On a more general note, a dedicated literature review will greatly help.\n\n(iv) One of the main claims of the paper is the reformulation of the Bayesian update as finding the least-squares solution to a linear system. This equivalence isn't explicitly proven though. It would be a worthy addition to the main text.\n\n(v) Could the authors include any quantification of \"fixed-point\" behavior?", "summary_of_the_paper": "The authors propose Generative Pseudo-Inverse Memory (GPM), a family of generative models that offer read and write operations of constant time complexity. Encoding new memories and decoding data from memories are postulated as Bayesian updates for which an equivalent minimization problem is proposed. This minimization problem essentially amounts to solving a linear system of equations, which can be efficiently done via computing matrix pseudo inverses. The authors demonstrate the utility of GPM on a variety of applications such as image denoising, image generation, and storage retrieval. ", "summary_of_the_review": "This is a neat and well-thought-out idea. However, as I've expressed in the main review, some of the claims need further justification and the paper clarity needs to be improved. I am willing to update my score if the authors are able to provide a convincing response!", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "6xxbW5PK3I_", "reviewer": "Reviewer_m6LR", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength\n- The general memory model (e.g., for episodic or working memory) is an important topic in achieving human-like general AI. \n- The paper is well-written and adequately clear (but can be improved).\n- The experiment is performed thoroughly. \n- It shows clear advantages to the previous works.\n- It also provides theoretic analysis on error bound.\n\nWeakness\n- The explanation can be improved for the readers who are not familiar with the previous works of KMs. For example, each line of Algo 1. can more explicitly explained. \n- The meanings of \"temporary read-out\" and \"dynamic\" weight were not clear in the beginning.\n- In introduction, it says \"Importantly, our model ... not only store and retrieve ... but also generate ...\" This sounds like a feature of only the proposed model, but the previous works can also do this. \n\nMinor\n- It may be beyond the scope of the paper, but showing the actual benefit of this memory in an RL agent will make the paper more complete.", "summary_of_the_paper": "The paper proposes a new memory model following the research line of Kanerva Machine, DKM, and Kanerva++. The proposed model reformulates the Bayesian updates of memory and address as finding least-square solution to linear systems. This requires matrix inversion operations and the authors proposed to approximate it iteratively by using Ben-Cohen algorithm for pseudo-inverse matrix. It results in a memory read/write system that is rapid/accurate and can store large batch of data. The evaluation is performed thoroughly on various datasets including binarized MNIST, binarized Omniglot, Fashion MNIST, CIFAR10/100, CelebA. It shows the superiority of the proposed method in negative ELBO of test likelihood, denoising success rate and hamming error, generation, memory capacity, and run-time per iteration. \n", "summary_of_the_review": "The paper tackles an important problem and is well and clearly written (but clarity can be improved). The proposed idea is valid and interesting. The experiment clearly shows the superiority of the proposed method in rapid memory read/wright, memory capacity, and de-noising, and generation, etc. The proposed method is also supported by a theoretic analysis on error bound.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors present a new memory-augmented neural network that is related to the Kanerva machine of Wu et. al.  The reviewers considered the ideas in the paper novel and interesting, but were concerned about presentation issues and literature review.  The authors have improved both... however- authors: please even under limited space constraints, make more room for related work!  Clarifying your contribution in the context of the literature is critical for reader understanding, and neglecting this almost had your paper rejected out of hand.  

I am voting to accept
Decision: Accept (Poster)