HyperEmbed: Tradeoffs Between Resources and Performance in NLP Tasks with Hyperdimensional Computing Enabled Embedding of n-gram Statistics

Pedro Alonso, Kumar Shridhar, Denis Kleyko, Evgeny Osipov, Marcus Liwicki

TL;DR

This paper introduces HyperEmbed, a novel method for representing n-gram statistics in NLP tasks using Hyperdimensional Computing (HDC). HyperEmbed offers a significant reduction in computational resources (memory and time) compared to traditional n-gram representations, achieving comparable or even better performance on various NLP classification tasks. This work opens up possibilities for more efficient and sustainable NLP model development.

What Problem Does This Paper Address?

The paper tackles the growing computational cost and environmental impact of modern NLP models, particularly those based on Deep Learning. While these models achieve high performance, their resource demands (memory, processing power, energy) are becoming prohibitive. The authors focus on improving the efficiency of NLP algorithms by re-examining a well-established technique: n-gram statistics. Traditional n-gram representations can lead to exponentially growing feature vector sizes with increasing n-gram length, making them computationally expensive. The paper aims to find a way to represent these n-gram statistics more efficiently without sacrificing classification accuracy.

Methods

The core of the paper is the HyperEmbed method, which leverages Hyperdimensional Computing (HDC) to create distributed representations of n-gram statistics. Instead of using sparse, high-dimensional vectors where each dimension corresponds to a specific n-gram (conventional n-gram statistics), HyperEmbed maps these n-grams into dense, high-dimensional vectors (HD vectors). This is achieved by:

  • Assigning random HD vectors to individual symbols (characters or words).
  • Using HDC operations (bundling, binding, permutation) to combine these symbol vectors based on their position and occurrence within an n-gram.
  • Bundling the resulting HD vectors for all observed n-grams in a text to create a single, dense HD vector representing the entire text's n-gram statistics.

This approach allows for a fixed-dimensionality representation, independent of the n-gram size, thus decoupling representation size from n-gram complexity. The paper also explores Subword Semantic Hashing (SemHash) and Byte Pair Encoding (BPE) as alternative methods for creating subword representations, which are then compared to the proposed HyperEmbed approach.

Datasets

The paper evaluates HyperEmbed on four datasets:

  • Chatbot Corpus: A small dataset of questions posed to a Telegram chatbot about public transport in Munich.
  • Ask Ubuntu Corpus: A small dataset of questions and answers from the StackExchange platform.
  • Web Applications Corpus: A small dataset of questions and answers from the StackExchange platform related to web applications.
  • 20 News Groups Corpus: A large, well-known dataset comprising news articles from 20 different categories.

The first three datasets are referred to as "small" and were augmented to ensure balanced class sizes. The 20NewsGroups dataset was used to evaluate performance on a larger scale.

Key Insights and Ideas

  • Decoupling Representation Size from n-gram Complexity: The most significant insight is that HDC allows for the creation of fixed-size representations of n-gram statistics, regardless of the n-gram length. This directly addresses the scalability issue of traditional n-gram methods.
  • Resource Efficiency is Achievable: HyperEmbed demonstrates substantial reductions in memory usage and training/testing times, often by orders of magnitude, without a significant drop in classification performance.
  • Tradeoffs are Possible and Valuable: The paper highlights that there's a clear tradeoff between the dimensionality of the HD vectors and the computational resources required. Higher dimensionality generally leads to better performance up to a point, but at the cost of increased resources. This allows for tuning based on specific application needs.
  • HDC as a General-Purpose Embedding Technique: The success across various classifiers and datasets suggests that HDC-based embedding of n-gram statistics is a versatile and promising approach for NLP.
  • BPE and SemHash as Viable Alternatives: While HyperEmbed is the focus, the paper also shows that BPE and SemHash can provide comparable or slightly better F1 scores than SemHash alone, with some computational benefits, though generally less dramatic than HyperEmbed.

Key Results

  • Significant Resource Reduction: For the 20NewsGroups dataset, memory reduction was up to ~100x and train/test speed-ups were over 100x for some classifiers with HD vectors. For smaller datasets, memory reduction was around 6x and speed-ups were around 4x.
  • Comparable Performance: HyperEmbed achieved F1 scores comparable to conventional n-gram statistics, and in some cases, even slightly improved performance. For example, on the AskUbuntu dataset, MLP achieved 99% of the conventional n-gram statistics F1 score with significantly reduced resources.
  • Dimensionality Matters (Up to a Point): For MLP, F1 scores generally increased with HD vector dimensionality, plateauing around 512-1024 dimensions for small datasets and 4096 for the 20NewsGroups dataset. Beyond these points, performance either saturated or degraded.
  • Classifier Sensitivity: The effectiveness of HyperEmbed varied across classifiers. Classifiers that rely on local feature information (like RF and BNB) sometimes showed a larger performance drop compared to those that can handle distributed representations better.
  • BPE vs. SemHash: Using BPE before SemHash showed comparable F1 scores to SemHash alone but with about 2x better speed-ups and memory reduction, attributed to smaller n-gram statistics.

Limitations and Future Work

  • Implementation Inefficiency: The authors acknowledge that their Python implementation of HD vector formation was inefficient, particularly due to the use of numpy.roll for cyclic shifts. They suggest that a faster implementation (e.g., in Matlab or optimized C++) is feasible and would further improve the observed speed-ups.
  • Defining Objective Functions for Tradeoffs: A key challenge identified is the lack of an objective function to objectively determine when a performance/resource tradeoff is acceptable. The authors suggest defining a "utility function" that assigns costs to performance gains and resource savings, but this would be application-specific.
  • State-of-the-Art Comparison: The results on the 20NewsGroups dataset were not state-of-the-art compared to models like BERT. However, the paper's focus was on demonstrating the resource efficiency of n-gram embedding via HDC, not on achieving absolute SOTA performance.
  • Future Work: The authors suggest exploring the use of binarized classifiers with HD vectors for further inference step improvements and revisiting random projection techniques for NLP scenarios. They also propose the development of utility functions for objective tradeoff analysis.

Summary updated

Abstract

Recent advances in Deep Learning have led to a significant performance increase on several NLP tasks, however, the models become more and more computationally demanding. Therefore, this paper tackles the domain of computationally efficient algorithms for NLP tasks. In particular, it investigates distributed representations of n-gram statistics of texts. The representations are formed using hyperdimensional computing enabled embedding. These representations then serve as features, which are used as input to standard classifiers. We investigate the applicability of the embedding on one large and three small standard datasets for classification tasks using nine classifiers. The embedding achieved on par F1 scores while decreasing the time and memory requirements by several times compared to the conventional n-gram statistics, e.g., for one of the classifiers on a small dataset, the memory reduction was 6.18 times; while train and test speed-ups were 4.62 and 3.84 times, respectively. For many classifiers on the large dataset, memory reduction was ca. 100 times and train and test speed-ups were over 100 times. Importantly, the usage of distributed representations formed via hyperdimensional computing allows dissecting strict dependency between the dimensionality of the representation and n-gram size, thus, opening a room for tradeoffs.
BibTeX
@inproceedings{alonso2021hyperembed,
  author = {Pedro Alonso and Kumar Shridhar and Denis Kleyko and Evgeny Osipov and Marcus Liwicki},
  title = {{HyperEmbed: Tradeoffs Between Resources and Performance in NLP Tasks with Hyperdimensional Computing Enabled Embedding of n-gram Statistics}},
  booktitle = {IJCNN},
  year = {2021},
  doi = {10.1109/ijcnn52387.2021.9534359},
}
Figure