Sublinear Partition Estimation

Pushpendre Rastogi, Benjamin Van DurmearXiv 2015 · OpenReview

TL;DR

This paper tackles the computational bottleneck of calculating the partition function ($Z$) in large-scale neural network classification tasks. They introduce three novel sublinear estimation methods, leveraging approximate nearest neighbor search and kernel feature maps, which significantly outperform brute-force computation and offer a practical solution for models with ever-growing numbers of categories.

What Problem Does This Paper Address?

In many machine learning tasks, especially those involving large vocabularies or numerous categories (like image recognition or language modeling), neural networks output scores for each potential class. To convert these scores into probabilities, we need to compute the partition function ($Z$), which involves summing the exponentiated scores over all possible classes. As the number of classes ($N$) grows, this summation becomes computationally prohibitive, scaling linearly with $N$. This is a major hurdle for state-of-the-art models that are constantly expanding their categorical scope. The paper aims to find ways to estimate $Z$ much faster than brute-force summation, ideally in sublinear time with respect to $N$.

Methods

The authors propose three main approaches for sublinear estimation of the partition function:

  • MIMPS (MIPS Based Importance Sampling): This method leverages Maximum Inner Product Search (MIPS) algorithms to efficiently retrieve a set of $k$ "head" samples (those with the highest scores). It then estimates $Z$ by summing the exponentiated scores of these head samples and extrapolating for the remaining "tail" samples. This is an improvement over naive importance sampling, which suffers from high variance.
  • MINCE (MIPS Based NCE): This approach uses Noise-Contrastive Estimation (NCE), a technique that can estimate parameters of unnormalized distributions more efficiently than maximum likelihood. By combining MIPS for sampling from the true (unnormalized) distribution and a uniform noise distribution, MINCE aims to estimate $Z$.
  • FMBE (Feature Map Based Estimation): This method utilizes kernel feature maps. Kernels, like the exponential function used here, can be decomposed into a sum of products of feature functions. By approximating this sum with a finite number of feature maps, the computation of $Z$ can be reduced from $O(N)$ to $O(P)$, where $P$ is the number of feature maps, provided $P$ is significantly smaller than $N$.

Datasets

The paper uses a publicly available dataset of neural word embeddings:

  • 3 Million, 300-dimensional word vectors: This dataset, derived from a large corpus of news text, is used to simulate scenarios where the dot product between word vectors represents unnormalized log probabilities. For experiments, the first 100,000 vectors were used.

Additionally, for language modeling experiments, they use:

  • Penn Treebank Corpus (sections 0-20): Used for training a log-bilinear language model.
  • Penn Treebank Corpus (sections 21-22): Used as a test set for evaluating the language model and partition function estimation.

Key Insights and Ideas

  • The "curse of dimensionality" for partition functions: The core problem is that as the number of categories explodes, the direct computation of $Z$ becomes intractable, even with parallelization.
  • MIPS as a powerful tool: Algorithms for efficiently finding nearest neighbors (or in this case, highest inner product) are crucial for sampling from the high-probability regions of the score distribution, which is key to accurate estimation.
  • Tail estimation is critical: The paper highlights that for common words (or categories), the distribution of scores is flatter, meaning a larger number of "tail" samples are needed for accurate estimation. This is a significant challenge for simple extrapolation.
  • MIMPS emerges as a strong contender: Among the proposed methods, MIMPS, which combines MIPS with importance sampling, shows promising results, especially when a sufficient number of head samples are retrieved.
  • Noise and retrieval errors matter: Real-world applications involve noisy data and imperfect retrieval systems. The paper demonstrates how these factors impact the accuracy of the estimators, emphasizing the need for robust methods.

Key Results

  • Sublinear estimation is feasible: The proposed methods (MIMPS, MINCE, FMBE) demonstrate the ability to estimate $Z$ with significantly reduced computational cost compared to brute-force.
  • MIMPS shows competitive accuracy: With $k=100$ head samples and $l=100$ tail samples, MIMPS achieved a mean absolute relative error of only 7.1% in oracle experiments, retrieving only 0.1% of the vocabulary.
  • MINCE's performance is mixed: While MINCE shows promise, its performance is sensitive to the number of noise samples and can be high-error, especially when retrieval errors are introduced.
  • FMBE requires high dimensions: The feature map approach (FMBE) shows potential but requires a large number of dimensions to achieve reasonable accuracy, suggesting it might be less practical for current high-dimensional settings.
  • Language modeling validation: In end-to-end language modeling experiments, MIMPS with around 100 head and 100 tail samples provided better accuracy than the heuristic of assuming $Z=1$.

Limitations and Future Work

  • Theoretical analysis is challenging: The authors acknowledge that a rigorous theoretical analysis of the performance of these estimators, especially concerning the impact of nearest neighbor retrieval errors, is complex and deferred to future work.
  • FMBE's dimensionality requirement: The FMBE method's effectiveness is tied to the number of dimensions in the feature map, and current methods for generating these maps in high dimensions are not efficiently addressed.
  • Improving tail estimation: For common words with flat score distributions, more sophisticated tail modeling might be necessary to further reduce estimation error.
  • Exploring new kernel feature map generation: The paper suggests investigating newer methods for generating kernel feature maps that offer better theoretical guarantees.
  • Analyzing retrieval error impact: Further work is needed to understand how errors in nearest neighbor retrieval specifically affect the accuracy of partition function estimators, potentially by assuming parametric distributions for class scores.

Summary updated

Abstract

The output scores of a neural network classifier are converted to probabilities via normalizing over the scores of all competing categories. Computing this partition function, $Z$, is then linear in the number of categories, which is problematic as real-world problem sets continue to grow in categorical types, such as in visual object recognition or discriminative language modeling. We propose three approaches for sublinear estimation of the partition function, based on approximate nearest neighbor search and kernel feature maps and compare the performance of the proposed approaches empirically.
BibTeX
@misc{rastogi2015sublinear,
  author = {Pushpendre Rastogi and Benjamin Van Durme},
  title = {{Sublinear Partition Estimation}},
  year = {2015},
  eprint = {1508.01596},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1508.01596},
}
Figure