Learning Distributed Representations for Structured Output Prediction

Vivek Srikumar, Christopher D. Manning

Overview

This paper introduces DISTRO (DIStributed STRuctured Output), a framework that fundamentally changes how we treat output labels in structured prediction tasks. Traditionally, machine learning models treat output labels as discrete, independent units. DISTRO moves away from this by representing labels as dense vectors and using tensor products to model their combinations. This approach allows semantically similar labels to share statistical strength, leading to better generalization and higher accuracy in tasks like document classification and part-of-speech (POS) tagging.

The Problem with Discrete Labels

In modern machine learning, it is standard practice to represent inputs (like words or images) as dense vectors or embeddings rather than sparse one-hot encodings. This allows models to inherently understand that "cat" and "kitten" are related concepts. However, the outputs—the labels we are trying to predict—have largely remained discrete atoms.

The authors argue that this is a significant missed opportunity. For instance, in a document classification task like the 20 Newsgroups dataset, the labels comp.os.mswindows.misc and comp.sys.mac.hardware are clearly related. Yet, standard models treat them as entirely distinct entities with no shared parameters. This problem compounds in structured prediction (such as sequence labeling), where transitions between labels (e.g., Adjective $\to$ Noun) are treated as unique events, even if the specific tags vary only slightly. The core gap addressed by this paper is the lack of a unified mechanism to exploit label similarity within complex output structures.

The DISTRO Framework

To solve this, the authors propose redefining how feature vectors are built for structured prediction:

  1. Label Vectors: Every label in the vocabulary is assigned a $d$-dimensional unit vector. These vectors are collected into a continuous label matrix $A$.
  2. Tensor Product Composition: To represent a "part" of a structure (like a transition in a sequence), the model computes the tensor product of the involved label vectors and the input features. This mathematically conjoins the labels, allowing the model to learn from the interactions between their distributed meanings rather than just looking up a static weight.
Tensor product composition for feature vectors
  1. Joint Learning: The model jointly learns both the classification weights ($w$) and the label vectors ($A$).
  2. Nuclear Norm Regularization: To encourage the model to share information across labels, a rank penalty (using the nuclear norm) is applied to the label matrix. This forces the labels into a lower-dimensional subspace where they must overlap and share characteristics, effectively discovering a label hierarchy from the data.
  3. Optimization: Because the joint objective is not convex, the authors employ an alternating minimization strategy: they fix the labels to update the weights using Stochastic Gradient Descent (SGD), and then fix the weights to update the labels using a proximal gradient method.

Key Results

The authors evaluated DISTRO on three distinct tasks: 20 Newsgroups (multiclass document classification), Penn Treebank (English POS tagging), and CoNLL 2007 (Basque POS tagging). DISTRO consistently outperformed standard Structural SVM baselines across the board.

  • Document Classification: DISTRO achieved 84.0% accuracy compared to the baseline's 81.4%. Interestingly, even when the label vectors were forced down to just 10 dimensions, the model nearly matched the baseline, proving that labels do not need to be fully independent to be highly effective.
Classification accuracy on 20 Newsgroups
  • English POS Tagging: Accuracy improved to 96.7% (from 96.2%). The authors noted that performance plateaued once the label matrix reached a rank of 20, suggesting the 45 English POS tags can be effectively represented in a much smaller semantic space.
  • Basque POS Tagging: The model saw a nearly 1% absolute improvement (92.4% vs 91.5%), a significant gain given the high complexity of Basque morphology and its fine-grained set of 64 labels.

Insights and Limitations

The primary takeaway is that labels aren't atoms; they carry semantic weight. By treating them as continuous vectors, models can generalize from frequently seen transitions to similar, rarely seen ones. The authors successfully demonstrate that the standard Structural SVM is merely a special case of DISTRO where label vectors are fixed as one-hot encodings.

However, the approach does have limitations:

  • Non-Convexity & Initialization: The joint optimization of weights and label vectors is non-convex. While it converges well in practice, it lacks global optimality guarantees and is sensitive to random initialization (requiring the discarding of "ill-behaved" starting points).
  • Dimensionality Scaling: While tensor products are mathematically elegant, the size of the feature vector grows exponentially with the number of labels in a "part" ($d^m$). This makes scaling to very high-order models (like trigram or quadrigram transitions) computationally challenging without further approximations.

Summary updated

Abstract

In recent years, distributed representations of inputs have led to performance gains in many applications by allowing statistical information to be shared across inputs. However, the predicted outputs (labels, and more generally structures) are still treated as discrete objects even though outputs are often not discrete units of meaning. In this paper, we present a new formulation for structured prediction where we represent individual labels in a structure as dense vectors and allow semantically similar labels to share parameters. We extend this representation to larger structures by defining compositionality using tensor products to give a natural generalization of standard structured prediction approaches. We define a learning objective for jointly learning the model parameters and the label vectors and propose an alternating minimization algorithm for learning. We show that our formulation outperforms structural SVM baselines in two tasks: multiclass document classification and part-of-speech tagging.
BibTeX
@inproceedings{srikumar2014learning,
  author = {Vivek Srikumar and Christopher D. Manning},
  title = {{Learning Distributed Representations for Structured Output Prediction}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2014},
}
Figure