Revisiting Output Coding for Sequential Supervised Learning

Guohua Hao, Alan FernIJCAI 2007 · OpenReview

Abstract

Markov models are commonly used for joint inference of label sequences. Unfortunately, inference scales quadratically in the number of labels, which is problematic for training methods where inference is repeatedly performed and is the primary computational bottleneck for large label sets. Recent work has used output coding to address this issue by converting a problem with many labels to a set of problems with binary labels. Models were independently trained for each binary problem, at a much reduced computational cost, and then combined for joint inference over the original labels. Here we revisit this idea and show through experiments on synthetic and benchmark data sets that the approach can perform poorly when it is critical to explicitly capture the Markovian transition structure of the large-label problem. We then describe a simple cascade-training approach and show that it can improve performance on such problems with negligible computational overhead.

Introduction

Sequence labeling is a fundamental task in machine learning, with applications ranging from natural language processing to bioinformatics. Conditional Random Fields (CRFs) and other Markovian models are typically preferred for these tasks because they capture dependencies between adjacent labels. However, the computational complexity of these models scales quadratically with the number of labels ($L^2$), making them impractical for large label sets.

Sequential Error-Correcting Output Coding (SECOC) was introduced to address this by reducing the multi-label problem into multiple independent binary classification tasks. While computationally efficient, this independence often results in a failure to capture the underlying Markovian structure. This paper investigates this failure and proposes Cascaded SECOC (c-SECOC), a method that restores structural awareness through a simple sequential training process.

Methodology

The core of the proposed approach lies in how the binary models are trained and utilized:

  • Independent SECOC (i-SECOC): A baseline where each bit of the output code is predicted by a separate model trained in isolation. These models are "blind" to each other, making it impossible for them to capture complex transition patterns.
  • Cascaded SECOC (c-SECOC): A sequential training regime where the predictions of previous binary models are used as additional input features for subsequent models in the cascade. This allows the model to "re-couple" the bits and recover transition information that was lost during decomposition.

The authors evaluate these strategies using Gradient-Tree Boosting (GTB) and the Voted Perceptron (VP) as base learners.

Experimental Results

The performance of c-SECOC was evaluated on the Nettalk phoneme recognition task (134 labels) and Noun Phrase Chunking (NPC).

Nettalk Performance

In the Nettalk experiments, the independent approach (i-SECOC) struggled significantly when the observation window was small, as it could not rely on local features to compensate for the lack of transition modeling. In contrast, c-SECOC showed dramatic improvements. By including just a few cascade features, the model's accuracy increased by over 10 percentage points, significantly outperforming the independent baseline.

Nettalk results: c-SECOC significantly outperforms independent SECOC (i-SECOC) and the i.i.d. baseline across different window sizes and base learners.

A major motivation for output coding is computational speed. The authors compared c-SECOC against Beam Search, a standard heuristic for speeding up inference in large-label CRFs. The results demonstrate that c-SECOC provides a superior accuracy-to-time trade-off, especially when paired with powerful non-linear learners like GTB.

Efficiency comparison: c-SECOC (GTB) achieves higher accuracy than Beam Search approximations within similar or shorter CPU timeframes.

Analysis: The Independence Trap

The paper provides a theoretical analysis of why independent models fail. For certain deterministic label sequences, independent models converge to a "coarse" prediction that lacks the necessary resolution to distinguish between states, effectively behaving like a random predictor. Cascading breaks this symmetry by providing the necessary context to resolve these ambiguities. However, the authors note that in tasks where input features are already highly descriptive (like NPC), the transition model is less critical, and basic SECOC may suffice.

Conclusion

Cascaded SECOC provides a robust and efficient alternative to standard CRFs for large-label sequence labeling problems. By re-introducing label dependencies through a simple feature cascade, it achieves high accuracy while maintaining the computational benefits of output coding. This approach is particularly effective when paired with non-linear base learners like Gradient-Tree Boosting, offering a practical path for scaling sequence models to hundreds of labels.

Summary updated

Abstract

Markov models are commonly used for joint inference of label sequences. Unfortunately, inference scales quadratically in the number of labels, which is problematic for training methods where inference is repeatedly preformed and is the primary computational bottleneck for large label sets. Recent work has used output coding to address this issue by converting a problem with many labels to a set of problems with binary labels. Models were independently trained for each binary problem, at a much reduced computational cost, and then combined for joint inference over the original labels. Here we revisit this idea and show through experiments on synthetic and benchmark data sets that the approach can perform poorly when it is critical to explicitly capture the Markovian transition structure of the large-label problem. We then describe a simple cascade-training approach and show that it can improve performance on such problems with negligible computational overhead.
BibTeX
@inproceedings{hao2007revisiting,
  author = {Guohua Hao and Alan Fern},
  title = {{Revisiting Output Coding for Sequential Supervised Learning}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2007},
  url = {https://openreview.net/forum?id=B14QimGuZB},
}
Figure