The bag-of-repeats representation of documents

Matthias GalléSIGIR 2013 · OpenReview

Abstract

n-gram representations of documents may improve over a simple bag-of-word representation by relaxing the independence assumption of word and introducing context. However, this comes at a cost of adding features which are non-descriptive, and increasing the dimension of the vector space model exponentially. We present new representations that avoid both pitfalls. They are based on sound theoretical notions of stringology, and can be computed in optimal asymptotic time with algorithms using data structures from the suffix family. While maximal repeats have been used in the past for similar tasks, we show how another equivalence class of repeats -- largest-maximal repeats -- obtain similar or better results, with only a fraction of the features. This class acts as a minimal generative basis of all repeated substrings. We also report their use for topic modeling, showing easier to interpret models.
BibTeX
@inproceedings{galle2013bag,
  author = {Matthias Gallé},
  title = {{The bag-of-repeats representation of documents}},
  booktitle = {International ACM SIGIR Conference on Research and Development in Information Retrieval},
  year = {2013},
  url = {https://openreview.net/forum?id=SkNMFH-Obr},
}

Loading related content...

Figure