PaperlayerView exact revision on arXiv

Source-linked AI summary

Supervised Learning with Quantum-Inspired Tensor Networks

E. Miles Stoudenmire, David J. Schwab

arXiv:1605.05775v2stat.MLcond-mat.str-elcs.LG

TL;DR

The paper addresses how tensor-network optimization can support supervised learning with very large feature spaces. It parameterizes classifying models with matrix product states and obtains a 0.97% MNIST test error, while discussing model structure and a possible generative interpretation.

  • Problem

    The paper asks how tensor-network representations and optimization methods can be adapted to supervised learning with expressive, exponentially large feature spaces.

  • Method

    The paper directly optimizes class weight vectors represented as matrix product states, using tensor-network sweeping and singular-value decompositions to preserve the MPS form.

  • Results

    0.97% MNIST test error was obtained with maximum MPS bond dimension m = 120 after three sweeps.

  • Takeaways & Limitations

    Tensor-network parameterization supports expressive nonlinear kernel models with optimization cost linear in training-set size and evaluation cost independent of training-set size.

Abstract

from arXiv · show

Tensor networks are efficient representations of high-dimensional tensors which have been very successful for physics and mathematics applications. We demonstrate how algorithms for optimizing such networks can be adapted to supervised learning tasks by using matrix product states (tensor trains) to parameterize models for classifying images. For the MNIST data set we obtain less than 1% test set classification error. We discuss how the tensor network form imparts additional structure to the learned model and suggest a possible generative interpretation.

I. INTRODUCTION

The paper adapts tensor-network methods to supervised learning by representing exponentially large feature-space weights as efficiently optimized matrix product states. It uses a tensor-product feature map for inputs and explores the resulting model's computational and interpretive structure.

  • I. INTRODUCTION: Tensor networks avoid the curse of dimensionality by representing high-order tensors with low-order tensors connected through a specific contraction geometry.
  • I. INTRODUCTION: The proposed approach approximates the optimal weight vector as a contracted sequence of low-order tensors, optimized directly rather than through a dual representation.
  • I. INTRODUCTION: Direct tensor-network optimization scales linearly with training-set size, while evaluating an input is independent of training-set size.
  • I. INTRODUCTION: The model uses matrix product states, or tensor trains, which approximate an order-N tensor by contracting a chain of N lower-order tensors.
  • I. INTRODUCTION: The paper tests MNIST and two-dimensional toy data, then examines the realized function class and a possible generative interpretation.
  • I. INTRODUCTION: Each input component is mapped to a d-dimensional unit-norm vector, and the full input becomes a rank-1 tensor product in a d^N-dimensional space.
  • I. INTRODUCTION: For grayscale images, each pixel is mapped to a normalized local vector whose tensor product represents the full image.
  • I. INTRODUCTION: The tensor-product feature map defines a kernel composed of one local kernel per input component, without assuming prior relationships between components.

III. MULTIPLE LABEL CLASSIFICATION

For multi-class learning, the paper assigns one label-indexed weight function to each class and predicts the label with the largest absolute decision value.

  • III. MULTIPLE LABEL CLASSIFICATION: The multi-class model uses a one-versus-all strategy with decision functions indexed by label ℓ.
  • III. MULTIPLE LABEL CLASSIFICATION: The predicted label is the ℓ whose decision function has the largest magnitude, |f ℓ(x)|.
  • III. MULTIPLE LABEL CLASSIFICATION: Because the feature map is shared across classes, the label dependence resides in the weight vector W ℓ.
  • III. MULTIPLE LABEL CLASSIFICATION: The decision function f ℓ(x) is obtained by evaluating the overlap between the class weight tensor and the input feature tensor.

IV. MPS APPROXIMATION

The paper approximates the high-order weight tensor with an MPS, enabling local optimization of classifier weights while controlling model complexity through bond dimensions and truncation. A DMRG-inspired sweeping algorithm updates neighboring tensors, restores MPS form by SVD, and advances projected inputs efficiently.

  • MPS approximation: Tensor networks represent exponentially large high-order tensors with fewer parameters whose number grows polynomially with input size.Different network structures impose different implicit assumptions about correlations among local indices.
  • MPS approximation: MPS approximate the label-indexed weight tensor as a contracted chain of lower-order tensors controlled by bond dimension m.For sufficiently large m, an MPS can represent any tensor, and components can be recovered through sequential matrix products.
  • MPS approximation: The label index can move between neighboring MPS tensors by contracting them and applying an SVD without changing the represented weight tensor.This relocation supports optimization at successive bonds.
  • Sweeping optimization: The algorithm sweeps along the MPS, optimizing two neighboring tensors at a time to minimize the classification cost.The two-tensor strategy also enables adaptive changes to the MPS bond dimension.
  • Sweeping optimization: Each local update forms a bond tensor, projects training inputs through fixed MPS wings, computes the decision function, and applies a gradient correction.The projected input is a four-index tensor that supports efficient local gradient computation.
  • Sweeping optimization: After updating Bℓ, an SVD restores MPS form, moves the label index to the next site, and truncates all but the m largest singular values.The truncation controls computational cost and can provide an optimal approximation under the stated unitary-tensor conditions.
  • Adaptive compression: The new bond dimension can be chosen adaptively from the number of singular values above a preset threshold, compressing the model by bond while preserving the optimal decision function.Projected inputs are advanced one site rather than recomputed fully, keeping each local step independent of input-space size.
  • Computational considerations: The algorithm scales as d^3 m^3 N N_L N_T, and its cost is dominated by the number of training inputs N_T.Initial experiments combining stochastic gradient descent with MPS sweeping reached single-digit classification errors but did not match full-gradient accuracy.

VI. MNIST HANDWRITTEN DIGIT TEST

The MPS classifier was evaluated on MNIST after reducing images to 14 × 14 pixels and using a zig-zag one-dimensional pixel ordering. Training converged quickly, and the largest tested bond dimension achieved 0.97% test error.

  • VI. MNIST HANDWRITTEN DIGIT TEST: MNIST images were reduced from 28 × 28 to 14 × 14 pixels by averaging clusters of four pixels.This reduced training time but discarded some image information.
  • VI. MNIST HANDWRITTEN DIGIT TEST: A zig-zag ordering mapped spatially neighboring pixels to nearby positions along the one-dimensional MPS path.The ordering was chosen to keep neighboring pixels close on average.
  • VI. MNIST HANDWRITTEN DIGIT TEST: The sweeping algorithm typically required only two or three sweeps for good convergence.Afterward, test error rates changed by only hundredths of a percent.
  • VI. MNIST HANDWRITTEN DIGIT TEST: 0.97% test error was obtained at maximum bond dimension m = 120 after three sweeps.The corresponding training error was 0.05%, with 97 test and 32 training images misclassified.

VII. TWO-DIMENSIONAL TOY MODEL

The toy-model study uses two-dimensional inputs drawn from labeled distributions and varies the local feature-space dimension d to examine model flexibility. For d > 2, the local feature map is generalized to a normalized d-component vector.

  • VII. TWO-DIMENSIONAL TOY MODEL: The toy models use two-dimensional inputs from distributions PA(x1, x2) and PB(x1, x2), with training points labeled A or B.The inputs are restricted to the unit square.
  • VII. TWO-DIMENSIONAL TOY MODEL: Training points are mapped to tensors before the label-specific tensor components are optimized by gradient descent.The optimized components are indexed by s1s2 for each label.
  • VII. TWO-DIMENSIONAL TOY MODEL: The main control parameter is the local-index dimension d.For d = 2 the feature map follows Eq. 3, while d > 2 uses a normalized d-component generalization.

A. Regularizing By Local Dimension d

Toy models show that local dimension d controls the balance between regularization and flexibility. Small d can follow the optimal boundary in overlapping data, while larger d produces increasingly complex boundaries and can fit nonlinear structure with some overfitting.

  • A. Regularizing By Local Dimension d: For overlapping Gaussian classes, the d = 2 model closely matches the theoretically optimal decision boundary despite necessarily misclassifying some non-separable training points.The optimal boundary is defined by PA(x1, x2) = PB(x1, x2).
  • A. Regularizing By Local Dimension d: d = 3 begins to show overfitting, while d = 6 produces a highly irregular boundary that reflects sampled points more than the underlying distribution.The finite local dimension still appears to provide some regularization at d = 6.
  • B. Non-Linear Decision Boundary: For a non-overlapping interlocking spiral distribution, d = 10 classified all 500 sampled training points correctly.The learned model nevertheless showed some overfitting near regions with unusually many or few samples.

VIII. INTERPRETING TENSOR NETWORK MODELS

The paper examines which functions the tensor-product feature map and tensor-network weights can represent. Complete local bases can represent any square-integrable function, whereas finite-dimensional grayscale feature maps impose functional restrictions.

  • A. Representational Power: With a tensor-product feature map and unrestricted weight tensor, a complete local basis yields a complete basis over the N-dimensional input space.Under this completeness condition, f(x) can be any square-integrable function.
  • A. Representational Power: For binary images, each input selects one weight-tensor component, allowing f(x) to be an arbitrary function over the set of black-and-white images.This follows because the selected components are independent when W has no further approximation.
  • A. Representational Power: For grayscale images and finite d, f(x) cannot be arbitrary over the full image space.With d = 2, varying one pixel while holding the others fixed gives a cos(π/2 xj) + b sin(π/2 xj).

B. Implicit Feature and Kernel Selection

The MPS parameterization decomposes the decision function into a learned reduced feature map followed by a core-tensor decision function. Orthogonal site tensors project the exponentially large feature vector into a smaller orthonormal subspace.

  • MPS decomposition: The MPS is decomposed around a central core tensor, with left- and right-orthogonal site tensors on either side.The orthogonality conditions are U†U = I and VV† = I, and the form can be obtained using tensor contractions and SVD operations.
  • Reduced feature map: The decision function first maps x into the large feature space Φ(x), then contracts with U and V tensors to produce a smaller feature vector ˜Φ(x), and finally contracts with the core tensor.The intermediate feature vector has m^2 components rather than the d^N components of the original feature space.
  • Reduced feature map: Orthogonality makes the core-tensor indices label an orthonormal basis for a subspace of the original feature space.The reduced feature vector ˜Φ(x) is the projection of Φ(x) into this subspace.
  • Implicit feature selection: Training an MPS model uncovers a relatively small set of important features while learning a decision function based only on those reduced features.The same feature-combination interpretation can be applied at any MPS bond, where tensors form linear combinations of local and previously constructed features.

C. Generative Interpretation

The paper explores interpreting squared MPS decision functions as class-conditional probability distributions, subject to orthogonality and normalization conditions on the feature map. A toy-data experiment finds that sufficient training data can recover the probabilistic model that generated the samples.

  • Interpretation: The generative interpretation treats |fℓ(x)|^2 as a probability distribution over inputs x for class ℓ.This interpretation is motivated by the connection between MPS and quantum-system wavefunctions.
  • Conditions: A consistent probability interpretation requires normalized weights and a feature map whose components satisfy orthogonality and normalization conditions under an integration measure.The local feature functions must be orthonormal with respect to dµ(x), and the local vectors must also be normalized for every input.
  • Conditions: The standard local feature map does not satisfy the required orthogonality condition, while an alternative map suitable for those conditions is anti-periodic on grayscale inputs and induces a periodic probability distribution.The paper therefore distinguishes mathematical suitability for the generative interpretation from suitability for grayscale pixels.
  • Toy experiment: The toy experiment samples labels and inputs from a hidden model, trains an MPS model with a log-likelihood cost, and compares the learned and exact distributions using KL divergence.The sampled inputs follow p(x|ℓ) = |fℓ(x)|^2/Pℓ for the selected label.
  • Toy experiment: Given enough training data, the learning process can eventually recapture the original probabilistic model that generated the data.Average KL divergence is plotted against the number of sampled training points with a σ/√Ns fit.

IX. DISCUSSION

The discussion presents MPS tensor networks as a framework for multi-class supervised learning with favorable scaling and learned structural regularization. It also identifies open questions about network choice, optimization, and the effects of regularization.

  • Discussion: The framework applies quantum-inspired tensor networks, specifically MPS, to multi-class supervised learning tasks.The authors note that PEPS may be more suitable for explicitly two-dimensional systems and could offer superior performance.
  • Discussion: Determining the best tensor network for a given domain remains an open problem, while classical coarse-graining methods offer related alternatives.The paper argues that very high-dimensional feature spaces may help produce sensitivity to high-order feature correlations.
  • Discussion: Tensor-network parameterization makes optimization cost linear in training-set size and evaluation cost independent of training-set size despite an exponentially large feature space.The discussion identifies mini-batches, momentum, adaptive learning rates, and unsupervised initialization as possible optimization improvements.
  • Discussion: The tensor-network parameterization reduces the number of parameters, but its regularization effects for specific learning tasks remain insufficiently understood.The authors also suggest adding weight decay or L1 penalties and note good generalization without explicit parameter regularization.
  • Discussion: A related MPS-based framework for parameterizing supervised learning models was published by Novikov et al. while the manuscript was being finalized.

Appendix B: Higher-Dimensional Local Feature Map

The appendix generalizes the normalized local feature map beyond d = 2 by constructing higher-dimensional components from powers of sine and cosine. Larger local dimension provides richer functional bases and sensitivity to smaller input variations.

  • Construction: Each input component xj is mapped to a normalized d-component vector φsj(xj), with the d = 2 case serving as the starting point.The local vectors are chosen to have unit norm so the tensor-product feature map can be used with physics-inspired tensor-network methods.
  • Construction: For larger d, the construction defines θj = πxj/2 and expands the identity cos^2(θj) + sin^2(θj) = 1 using binomial coefficients.The resulting definition reduces to the d = 2 case and guarantees that the squared local components sum to one.
  • Expressivity: Increasing d adds more components to the local feature vector and introduces higher-frequency sine and cosine terms.The larger local dimension also gives the weight tensor more components.
  • Expressivity: For larger d, the decision functions use a more complete functional basis and can respond to smaller variations in x.
Loading 1605.05775v2…