Agnostic Classification of Markovian Sequences

Ran El-Yaniv, Shai Fine, Naftali TishbyNeurIPS 1997 · OpenReview

Introduction

This paper introduces a "model-free" approach to clustering sequences by leveraging the deep connection between data compression and statistical similarity. By developing a randomized algorithm to merge sequences into a "joint source," the authors create a universal distance metric that can categorize everything from European languages to protein families without any prior knowledge of the underlying data.

The Challenge of Unsupervised Sequence Classification

In machine learning, we often need to group similar sequences together—such as categorizing news articles by topic or grouping proteins by function. While supervised learning has a rigorous foundation in information theory, unsupervised classification (clustering) has historically relied on ad-hoc distance measures, like edit distance, which often lack a clear statistical justification.

A fundamental challenge is measuring the similarity between two sequences of discrete symbols without prior knowledge of their generative rules. Most methods require first "training" a model (like a Hidden Markov Model); however, if the model is misspecified, the resulting classification will be flawed. This paper seeks an agnostic method—one that makes minimal assumptions and works universally across different types of data.

Information-Theoretic Methodology

The authors propose a method based on three core information-theoretic ingredients:

  1. Likelihood as Similarity: Two sequences are considered similar if they are likely to have been generated by the same statistical source.
  2. Universal Compression: Instead of building a specific model, the authors use the Lempel-Ziv algorithm (the basis of ZIP files). Because universal compressors are asymptotically optimal, they can be used to estimate "cross-entropy"—essentially measuring how much extra space it takes to encode sequence A using the rules discovered in sequence B.
  3. The Sequence Merging Algorithm: This is the paper's primary innovation. To compare two sequences, the authors generate a third "representative" sequence that represents the most likely joint source of the two. They use a randomized algorithm that looks at the longest suffixes of the current generated string that appear in the original sequences to decide which character to add next.

By merging sequences, they can create "centroids" for clusters, allowing them to perform standard hierarchical clustering without ever defining a specific probability distribution.

Experimental Validation

The authors evaluated their agnostic approach on three distinct types of data:

  • Literary Text: Excerpts from Charles Dickens’ A Tale of Two Cities and Mark Twain’s The Prince and the Pauper.
  • Protein Sequences: A set of 60 proteins drawn from six distinct families (Chaperonin, MHC I, Cytochrome, Kinase, Globin Alpha, and Globin Beta).
  • Linguistic Excerpts: 1,500-character snippets from 18 different languages, including 16 Indo-European languages and two artificial languages (Esperanto and Klingon).

Key Insights

  • Compression is Learning: The paper reinforces the idea that "to compress is to understand." If a single algorithm can compress a merged sequence better than it can compress two separate sequences, those sequences must share statistical structures.
  • The "Twickens" Effect: By merging Dickens and Twain, the authors created a "joint source" text that stylistically sits between the two, demonstrating that their merging algorithm successfully captures local statistical flavors.
  • Beyond Biology: In the protein experiment, the agnostic measure discovered biological similarities that the standard Smith-Waterman algorithm missed, despite using zero biological knowledge (no amino acid substitution matrices or gap penalties).

Key Results

Language Clustering

The algorithm produced a hierarchical tree that almost perfectly matches the standard philological tree of languages. It correctly grouped the Romance languages together, the Germanic languages together, and successfully identified Klingon as a total outlier.

Hierarchical clustering tree of languages

Protein Classification

The 60x60 distance matrix clearly showed blocks of high similarity corresponding to the protein families. While it struggled slightly with the Kinase and Cytochrome families, it generally succeeded in identifying functional groups purely through string statistics.

Pairwise distances of protein sequences

Parameter-Free Operation

The most striking result is that the algorithm requires no tuning. It does not need to know the alphabet size or the "order" of the Markov process; it adapts entirely to the data provided.

Limitations and Future Directions

  • The Markov Assumption: The method assumes that sequences can be approximated by finite-order Markov sources. While this covers a lot of ground, it might struggle with data featuring extremely long-range dependencies that exceed the memory of the compression algorithm used.
  • Computational Overhead: While suffix trees make the implementation efficient, the process of merging and re-compressing sequences for every pair in a large dataset could be computationally expensive compared to simpler heuristics.
  • Future Directions: The authors suggest applying this to "spike trains" (neural activity data) and more complex text categorization tasks, hinting at a more complete analysis of the method's convergence properties in future work.

Summary updated

Abstract

Classification of finite sequences without explicit knowledge of their statistical nature is a fundamental problem with many important applications. We propose a new information theoretic approach to this problem which is based on the following ingredients: (i) se(cid:173) quences are similar when they are likely to be generated by the same source; (ii) cross entropies can be estimated via "universal compres(cid:173) sion"; (iii) Markovian sequences can be asymptotically-optimally merged. With these ingredients we design a method for the classification of discrete sequences whenever they can be compressed. We introduce the method and illustrate its application for hierarchical clustering of languages and for estimating similarities of protein sequences. 1
BibTeX
@inproceedings{elyaniv1997agnostic,
  author = {Ran El-Yaniv and Shai Fine and Naftali Tishby},
  title = {{Agnostic Classification of Markovian Sequences}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {1997},
  url = {https://openreview.net/forum?id=HybszYZ_-S},
}
Figure