Source-linked AI summary
Unsupervised Generative Modeling Using Matrix Product States
Zhao-Yu Han, Jun Wang, Heng Fan, Lei Wang, Pan Zhang
TL;DR
The paper addresses unsupervised learning of joint data distributions for sample generation by introducing an MPS-based Born Machine. It trains the MPS with a DMRG-like likelihood procedure and uses direct sampling, finding generalization on MNIST while exposing limitations from system size, representation, and image correlations.
Problem
Unsupervised generative modeling must learn joint data distributions and generate samples, motivating alternatives that connect probabilistic modeling with quantum-state representations.
Method
The paper represents probabilities as squared MPS wavefunction amplitudes and learns the tensors through negative-log-likelihood optimization resembling DMRG.
Results
The model generated and reconstructed data across Bars-and-Stripes, random binary patterns, and MNIST, with MNIST reconstructions indicating learned features beyond memorized training instances.
Takeaways & Limitations
MPS offers a quantum-inspired generative model combining adaptive representation, tractable probability computation, and direct sampling for generative and inference tasks.
Takeaways & Limitations
The model’s memory capability worsens with larger systems at fixed Dmax, especially for long-range-correlated data, though increasing Dmax can compensate.
Abstract
from arXiv · showhide
Generative modeling, which learns joint probability distribution from data and generates samples according to it, is an important task in machine learning and artificial intelligence. Inspired by probabilistic interpretation of quantum physics, we propose a generative model using matrix product states, which is a tensor network originally proposed for describing (particularly one-dimensional) entangled quantum states. Our model enjoys efficient learning analogous to the density matrix renormalization group method, which allows dynamically adjusting dimensions of the tensors and offers an efficient direct sampling approach for generative tasks. We apply our method to generative modeling of several standard datasets including the Bars and Stripes, random binary patterns and the MNIST handwritten digits to illustrate the abilities, features and drawbacks of our model over popular generative models such as Hopfield model, Boltzmann machines and generative adversarial networks. Our work sheds light on many interesting directions of future exploration on the development of quantum-inspired algorithms for unsupervised machine learning, which are promisingly possible to be realized on quantum devices.
I. INTRODUCTION
The paper develops an MPS-based Born Machine for learning data distributions and generating samples, drawing on connections between generative modeling, statistical physics, and quantum probability.
- Motivation: Generative modeling learns data probability distributions so new samples can be generated from them.The paper frames this as an unsupervised-learning task with applications including representation learning and missing-data problems.
- Quantum connection: Quantum mechanics motivates modeling probabilities as squared wavefunction amplitudes, leading to the Born Machine formulation.The model uses P(v) proportional to |Ψ(v)|^2, with normalization supplied by the summed squared amplitudes.
- Matrix product states: Matrix product states are one-dimensional tensor networks with established applications in quantum many-body modeling and machine learning.The same representation is also known as tensor train decomposition in applied mathematics.
- Contribution: The proposed model learns distributions with an algorithm resembling DMRG, adaptively increasing MPS bond dimensions to strengthen learning capacity.The paper positions this approach against statistical-physics models such as the Hopfield and inverse Ising models.
- Contribution: Direct sampling makes MPS generation more efficient than Boltzmann-machine sampling and supports reconstruction and denoising from noisy inputs.Boltzmann machines typically generate samples through Markov Chain Monte Carlo, whereas the MPS procedure samples directly.
- Evaluation: Experiments cover Bars-and-Stripes, random binary patterns, and MNIST to demonstrate the model’s abilities, features, and drawbacks.The paper uses these datasets for proof-of-principle evaluation, capacity illustration, and generalization-related reconstruction.
A. Matrix Product States
The paper parameterizes a probability wavefunction with an MPS and trains it by data-based likelihood optimization, using canonicalization and DMRG-like tensor updates for tractable computation.
- A. Matrix Product States: The wavefunction is parameterized as an MPS whose tensors contract across virtual indices to produce Ψ(v).Each A(k)^v_k is a D_k−1 by D_k matrix, with D_0 = D_N closing the trace.
- A. Matrix Product States: Increasing bond dimensions expands the MPS ability to represent complicated functions, while limited dimensions impose an entanglement-based inductive bias.The entanglement entropy obeys S ≤ ln(D_k), and unrestricted bond dimensions can represent any N-bit probability distribution.
- A. Matrix Product States: Canonical forms simplify normalization and partition-function computation by exploiting MPS gauge freedom.Mixed-canonical form makes tensors on opposite sides of a selected site left- and right-canonical, respectively.
- B. Learning MPS from Data: Training adjusts MPS parameters by minimizing negative log-likelihood, which is equivalent to minimizing KL divergence from the empirical distribution.The gradient is computed on merged adjacent tensors, followed by decomposition and repeated pairwise updates.
- B. Learning MPS from Data: The optimization resembles two-site DMRG and can dynamically adjust bond dimensions to allocate resources to important data features.Unlike classic DMRG, the loss is data-dependent averaged NLL rather than energy, and machine-learning optimizers are used.
- B. Learning MPS from Data: The data-oriented algorithm is straightforward to parallelize across samples, with a GPU implementation at least 100 times faster than CPU on full MNIST.Identical, independent operations over samples provide the batch-level parallelism.
C. Generative Sampling
After training, the canonical MPS generates samples sequentially from marginal and conditional probabilities, while the same contraction machinery supports inference, reconstruction, and denoising.
- Direct sampling: The model generates samples independently after training, avoiding the MCMC procedure commonly used by energy-based models.The partition function is exactly computable in the MPS representation, enabling direct sampling.
- Direct sampling: Sampling begins at one boundary by drawing a bit from its marginal probability, then proceeds successively through conditional probabilities.Given sampled bits on the right, the next bit is drawn according to P(v_k−1|v_k,...,v_N).
- Direct sampling: Canonicalization makes boundary marginals easy to evaluate as squared norms divided by the normalization factor.For the final bit, P(v_N) = |x_vN|^2/Z after gauging the preceding tensors left-canonical.
- Direct sampling: The sequential procedure strictly obeys the MPS probability distribution because each bit is sampled from the corresponding conditional distribution.The construction repeatedly updates the contracted vector after fixing each sampled bit.
- Inference: MPS sampling also handles partially observed inputs, although canonicalization may be less helpful when unknown segments lie between known bits.Marginal probabilities remain tractable through efficient contraction of ladder-shaped tensor networks.
D. Features of the model and algorithms
The MPS model combines explicit tractable probabilities with efficient training and sampling, while its computational cost depends polynomially on system size and maximal bond dimension.
- Model features: MPS provides an explicit tractable probability density alongside efficient learning and inference.This combination is identified as the model’s most significant feature.
- Complexity: O(|T|NDmax^3) is the training complexity for system size N, dataset size |T|, and maximal bond dimension Dmax.The stated scaling includes the full training dataset and prescribed maximal bond dimension.
- Complexity: O(NDmax^2) is the sampling complexity when all sampled bits connect to the boundaries.Conditional sampling with specified segments instead scales as O(NDmax^3).
1. Theoretical Understanding of the Expressive Power
MPS expressibility is controlled by bond dimensions, which can adapt during learning to allocate capacity across data features. Its tensor-network structure supports efficient optimization and exact likelihood-based training, while its representational power remains bounded by entanglement-related constraints.
- Representational basis: Bond dimensions bound the MPS’s ability to capture entanglement entropy and therefore its representational power.This theoretical connection from quantum physics motivates MPS as a generative model.
- Scope of expressibility: For two-dimensional images, exact representation may require exponentially large bond dimensions as resolution increases, although affordable dimensions may suffice for short-range correlations.The expected computational scaling is polynomial for datasets with short-range correlations.
- Adaptive expressibility: Two-site optimization dynamically adjusts bond dimensions, allocating computational resources to important bonds with essential data features.The required bond dimensions may be inhomogeneous across realistic datasets.
- Adaptive expressibility: Bond-dimension adjustment follows singular-value distributions and reflects the MPS’s low-entanglement inductive bias.This adaptive mechanism differs from models whose architecture remains fixed while only parameters are tuned.
- Adaptive expressibility: Adaptive bond dimensions let MPS representational power grow as training reveals the data, analogous to structural learning in probabilistic graphical models.The comparison concerns adaptive expressibility rather than an identical optimization procedure.
- Exact training: MPS training can optimize negative log-likelihood directly using unbiased likelihood and gradient estimates, unlike RBM methods relying on approximate gradients.Exact normalization and gradients also make training easier to monitor with exact NLL.
4. Efficient Direct Sampling
MPS directly samples from its learned probability distribution while retaining a tractable partition function, avoiding MCMC’s slow mixing. Bars-and-Stripes experiments show exact memorization and sampling consistent with the uniform training distribution.
- Sampling mechanism: Direct MPS sampling avoids the slow-mixing problem of MCMC, whose random walks can become trapped and produce long-time correlation fluctuations.MCMC proposes random bit flips and accepts or rejects samples using probability ratios.
- Comparison with RBM: Unlike RBM sampling in the fully memorized case, MPS directly generates a training sample without requiring an MCMC direction that increases sampling probability.The RBM cannot generate samples in this example because no such direction exists.
- Sampling mechanism: MPS combines efficient direct sampling with a tractable partition function, while dynamically adjusting expressibility more flexibly than structurally constrained graphical models.Its sampling algorithm is formally similar to autoregressive sampling.
- Conditional generation: MPS can sample with arbitrary prior information, including fixed bits, supporting image reconstruction and denoising.This reverse-conditioning capability is contrasted with GAN latent-space sampling.
- Bars and Stripes: In the Bars-and-Stripes dataset, MPS training memorizes the 30 shown images while suppressing the probability of unshown images toward zero.The dataset contains 30 equally probable 4 × 4 binary images.
- Bars and Stripes: The trained MPS reaches the minimum Bars-and-Stripes cost, ln(30), within 1 × 10^-10 after four batch-gradient-descent loops.The learned bond dimensions also preserve dataset symmetries and attain the minimum required dimensions for exact representation.
- Bars and Stripes: 1.10 × 10^-5: the sampling log-likelihood ratio statistic G^2 for 10^6 generated samples, with p-value 0.820 indicating consistency with uniform sampling.The samples were independent and all were training images.
B. Random patterns
For random binary patterns, MPS capacity grows with maximal bond dimension but degrades with system size, especially for long-range correlations.
- L = ln |T | when the training set is no larger than Dmax, indicating exact memorization of all training patterns.With more patterns than the fixed bond dimension can support, L exceeds ln |T | and generations usually deviate from training patterns.
- L increases continuously beyond the exact-memory regime, unlike the abrupt retrieval-to-spin-glass transition reported for the Hopfield model.
- Larger Dmax enables exact memorization of more patterns and lowers L for a fixed training-set size.Increasing Dmax increases the model’s parameter count and capacity.
- In principle, unrestricted bond dimensions give MPS infinite capacity, while Hopfield and inverse Ising models have capacity proportional to system size.The paper notes that increasing MPS bond dimensions is analogous to increasing hidden variables in other generative models.
- With Dmax fixed, L increases linearly with system size N for 100 random patterns, indicating worse memory capability as the system grows.The limitation is attributed to difficulty maintaining joint distributions, particularly for long-range-correlated data; increasing Dmax can compensate.
C. MNIST dataset of handwritten digits
On binarized, flattened MNIST images, increasing MPS bond dimension improves likelihood and sample clarity, while learned bond dimensions and reconstruction quality reflect spatial correlations.
- Model capacity: Increasing Dmax lowers final L toward ln |T | and produces clearer generated MNIST images.At Dmax = 100, some crucial handwritten-digit features already emerge, although some images remain unclear.
- Model capacity: Dmax = 800 yields training NLL 16.8, with large bond dimensions concentrated in the image center and along edges mediating row correlations.Top and bottom edges have small dimensions because their pixels are inactive, whereas left and right edges remain large despite being white.
- Generated samples: Generated samples learn blank margins and pen-stroke structure, but many are not recognizable digits; a few are recognizable.The authors report that unsupervised generation requires much larger bond dimensions than a related discriminative task.
- Image reconstruction: Conditional direct sampling reconstructs training images almost identically from columns, while row reconstruction makes reasonable deviations such as bending a “1” into a “7”.
2. Generalization Ability
The MPS generalizes beyond its training images, with performance depending on training-set size, training duration, and the spatial range of learned correlations.
- On held-out MNIST images, reconstruction indicates that the MPS learns dataset features rather than merely memorizing training instances.
- After 11 training loops, column reconstruction already has similar quality, but row reconstruction remains worse than after 251 loops because longer-range inter-row correlations are learned later.
- Figure 7 evaluates the same 104 test images using rescaled 14 × 14 images across training sets of 10^3, 10^4, and 6 × 10^4 images.
- For |T| = 10^3, test L falls to about 40.26 before rising quickly, whereas for |T| = 10^4 it reaches 33.65 and increases slowly to 34.18.
- For |T| = 6 × 10^4, test L continues decreasing through 75 training loops, while larger training sets reduce the best test NLL.
- The authors interpret early overfitting on smaller datasets as worsening generalization, while larger training sets constrain memorization and enhance generalization.
IV. SUMMARY AND OUTLOOK
The paper presents MPS as a tensor-network generative model with adaptive learning and direct sampling, while identifying representation, data-type, and image-correlation limitations alongside possible quantum-device implementations.
- The model represents an unlabeled-data probability distribution as a matrix product state, providing adaptive and efficient learning together with direct sampling.
- Because probabilities use squared tensor-network amplitudes, MPS signs are redundant but may increase entanglement and required bond dimensions during optimization.
- Continuous-data performance depends on the chosen local feature map, leaving substantial exploration for continuous inputs; colored images can encode RGB values on three physical legs per tensor.
- For two-dimensional images, MPS may struggle to represent long-range correlations between neighboring pixels, motivating more expressive networks such as PEPS.
- PEPS handles two-dimensional correlations but sacrifices convenient contraction properties because exact contraction is #P hard.
- Quantum devices may eventually implement quantum-inspired generative models without the large-bond-dimension and high-contraction-complexity problems encountered in classical simulation.
Appendix A: Canonical conditions for MPS and computation of the partition function
Canonical forms exploit MPS gauge freedom to simplify normalization and partition-function computation through local tensor operations.
- MPS gauge freedom permits inserting identity matrices on bonds without changing the represented state.
- A tensor is left-canonical when its contracted tensor-product condition equals the identity, with an analogous right-canonical condition.
- Canonicalization is local, and the MPS normalization is particularly easy to compute in mixed-canonical form.
- Mixed-canonical form makes tensors left-canonical to one side of a selected site and right-canonical to the other while leaving the selected tensor unrestricted.
- Even without canonical form, the normalization factor Z remains efficiently computable when contractions are ordered appropriately.
Appendix B: DMRG-like Gradient Descent algorithm for learning
The learning algorithm combines DMRG-like two-site updates, gradient descent, SVD truncation, and canonicalization to adapt bond dimensions and allocate resources to learned correlations.
- The method dynamically adjusts bond dimensions during optimization, allocating resources to spatial regions with stronger correlations.
- Training initializes small random bond dimensions, canonicalizes the MPS, and sweeps back and forth across bonds similarly to two-site DMRG.
- Each merged tensor is updated by gradient descent to decrease the negative log-likelihood cost function.
- When gradients become small near a plateau or saddle point, the learning rate is increased so update norms depend on contracted-tensor dimensions.
- SVD decomposes the updated order-4 tensor, and singular values below the cutoff ratio ϵ_cut are truncated to control bond dimensions.
- The retained SVD factors are assigned according to sweep direction so the MPS remains in mixed-canonical form.