Fast Algorithms for Learning with Long N-grams via Suffix Tree Based Matrix Multiplication

Hristo S. Paskov, John C. Mitchell, Trevor J. HastieUAI 2015 · OpenReview

Abstract

This paper introduces a novel framework that allows machine learning models to utilize very long (or even all possible) $N$-grams without the typical memory explosion. By leveraging the topological structure of suffix trees, the authors enable matrix-vector multiplication—the core operation of most learning algorithms—in time and space that is strictly linear relative to the size of the original text corpus, regardless of $N$. This approach effectively "cures" the curse of dimensionality for $N$-gram models, enabling the use of rich contextual information previously considered computationally prohibitive.

Introduction

$N$-grams (sequences of $N$ words or characters) are fundamental to natural language processing and computational biology. While unigrams ($N=1$) and bigrams ($N=2$) are standard, longer $N$-grams capture significantly richer context. However, the computational cost of using long $N$-grams is immense. A document of $n$ words can contain up to $O(Kn)$ distinct $N$-grams of length up to $K$. For large datasets, the resulting feature matrix becomes too massive for standard RAM, and operations like Gradient Descent become impossibly slow. Consequently, most researchers cap $N$ at a small value, potentially losing valuable information.

Methodology

The authors' key insight is that $N$-gram matrices possess massive algebraic redundancy that can be exploited using Suffix Trees. They propose that the physical structure of the tree is the algebraic structure of the $N$-gram matrix.

1. Redundancy Removal

Many different $N$-grams always co-occur in the same documents (e.g., in the word "learning," the $N$-grams "learn" and "learni" might always appear together). These belong to the same "equivalence class." The authors replace the massive $N$-gram matrix with a much smaller Node Matrix ($\mathcal{X}$) where each column represents one of these classes.

2. Recursive Multiplication

The columns of the Node Matrix have a recursive relationship defined by the suffix tree's topology. This allows matrix-vector multiplications ($Xw$ and $X^Ty$) to be performed using simple top-down or bottom-up traversals of the tree, avoiding the need to ever materialize the full, dense matrix.

3. Specialized Data Structures

Two specific structures are introduced to optimize this process:

  • DFPT (Depth-First Preprocessing Tree): A memory-efficient format for storing the corpus and filtering features.
  • BFMT (Breadth-First Multiplication Tree): A structure optimized for the linear memory sweeps required during high-speed multiplication.

Experimental Results

The framework was evaluated on diverse datasets, including BeerAdvocate reviews (1 GB), NCBI journal articles (3 GB), DNA sequence data from the 1000 Genomes Project, and Amazon sentiment analysis tasks.

Figure 1: Matrix memory utilization across different representations as a function of maximum N-gram length. The BFMT approach maintains significantly lower memory requirements even as N increases to $10^5$.

Key Findings

  • Massive Compression: On DNA data, the Suffix Tree-based representation (BFMT) required 4,600 times less memory than a naive $N$-gram matrix. As shown in the figure above, the memory utilization for BFMT remains nearly constant even as the maximum $N$-gram length reaches $10^5$.
  • Extreme Speedups: The multiplication algorithm was four orders of magnitude faster than naive sparse multiplication on DNA data.
  • Improved Accuracy: In sentiment analysis, prediction accuracy consistently improved as $N$ increased from 1 to 5, proving that long $N$-grams contain useful signals that were previously too expensive to extract.
  • Implicit Normalization: The authors demonstrated how to perform complex operations like mean-centering and column normalization implicitly within tree traversals, maintaining efficiency.

Discussion and Future Work

By treating the suffix tree as the matrix itself, this framework makes training models with millions of features practical on standard hardware. However, some limitations remain. The current implementation is single-threaded, though the authors note that tree traversals are inherently parallelizable. Additionally, building the initial Suffix Array/Tree remains the most memory-intensive preprocessing step. Future research may focus on more memory-efficient ways to build the DFPT directly and exploring automated feature selection for specific long $N$-gram tasks.

Summary updated

BibTeX
@inproceedings{paskov2015fast,
  author = {Hristo S. Paskov and John C. Mitchell and Trevor J. Hastie},
  title = {{Fast Algorithms for Learning with Long N-grams via Suffix Tree Based Matrix Multiplication}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2015},
  url = {https://openreview.net/forum?id=xbz9LM7ZLFD},
}
Figure