Discriminative Learning over Constrained Latent Representations

Ming-Wei Chang, Dan Goldwasser, Dan Roth, Vivek SrikumarNAACL 2010 · OpenReview

Abstract

This paper proposes a general learning framework for a class of problems that require learning over latent intermediate representations. Many natural language processing (NLP) decision problems are defined over an expressive intermediate representation that is not explicit in the input, leaving the algorithm with both the task of recovering a good intermediate representation and learning to classify correctly. Most current systems separate the learning problem into two stages by solving the first step of recovering the intermediate representation heuristically and using it to learn the final classifier. This paper develops a novel joint learning algorithm for both tasks, that uses the final prediction to guide the selection of the best intermediate representation. We evaluate our algorithm on three different NLP tasks -- transliteration, paraphrase identification and textual entailment -- and show that our joint method significantly improves performance.

Introduction: The Latent Representation Bottleneck

High-level Natural Language Processing (NLP) tasks, such as paraphrase identification or textual entailment, often rely on underlying structures that are not explicitly labeled in the training data. For instance, to determine if two sentences are paraphrases, a model must typically establish an alignment between their constituent words and phrases. These alignments serve as latent representations.

Historically, these problems have been tackled using a two-stage pipeline:

  1. Generation: A heuristic or separate model identifies the "best" latent representation (e.g., word alignment).
  2. Classification: A classifier is trained using features extracted from this fixed representation.
Example of latent word alignment between two sentences in a paraphrase task.

The fundamental flaw in this approach is the disconnect between the two stages. A linguistically "correct" alignment might not be the most informative one for the specific classification task. By fixing the representation early, the model cannot use the final task's feedback to refine its internal understanding, often leading to suboptimal performance.

The LCLR Framework

To address this, we introduce the Learning Constrained Latent Representations (LCLR) framework. LCLR treats the discovery of latent structures and the final classification as a single, joint optimization problem.

Joint Optimization and Constraints

Instead of assuming a fixed latent structure, LCLR searches for the representation that best supports the final classification label. For a positive instance (e.g., a confirmed paraphrase), the model seeks any valid alignment that justifies that label.

To ensure these latent structures remain linguistically plausible, we utilize Integer Linear Programming (ILP). This allows the injection of domain-specific "hard constraints"—for example, preventing a single word in one sentence from mapping to an excessive number of words in another.

Learning Algorithm

The joint objective is non-convex, characterized as a "minimization of a maximization." We employ an iterative algorithm that alternates between:

  1. Finding the optimal latent representation for positive examples given current weights.
  2. Updating model weights to better distinguish between positive and negative classes.

For negative examples, the model must ensure that no valid alignment allows the instance to be classified as positive. To manage the computational complexity of this search, we use a cutting-plane algorithm with a caching mechanism to avoid redundant calculations.

Experimental Evaluation

We evaluated LCLR across three distinct NLP domains to prove its generality:

  1. Transliteration Discovery: Identifying English-Hebrew name pairs.
  2. Recognizing Textual Entailment (RTE): Using the RTE-5 challenge dataset.
  3. Paraphrase Identification: Using the standard MSR Paraphrase corpus and an "Extended" version with artificially lengthened sentences to increase alignment difficulty.

Results and Discussion

LCLR consistently outperformed traditional two-stage "Alignment + Learning" baselines across all tasks.

Comparison of LCLR against various baselines on the MSR Paraphrase corpus and the Extended dataset.
  • Transliteration: Accuracy improved from 80.0% to 92.3%, and Mean Reciprocal Rank (MRR) rose from 85.7 to 95.4.
  • Textual Entailment: LCLR achieved 66.8% accuracy, significantly exceeding the TAC 2009 median of 61.5%.
  • Paraphrase Identification: As shown in the results table, LCLR reached 76.41% accuracy on the standard MSR corpus. Notably, on the "Extended" dataset, the performance gap between LCLR and the two-stage baseline widened, demonstrating that joint learning becomes increasingly critical as the search space for latent representations grows.

Conclusion

The LCLR framework demonstrates that the final classification label is a powerful signal for structuring internal representations. By allowing the task feedback to guide the discovery of "hidden" structures, models can learn more robust and task-relevant features. While the non-convex nature of the objective requires careful initialization and ILP inference adds computational cost, the significant performance gains across diverse tasks validate the joint learning approach.

Summary updated

Abstract

This paper proposes a general learning framework for a class of problems that require learning over latent intermediate representations. Many natural language processing (NLP) decision problems are defined over an expressive intermediate representation that is not explicit in the input, leaving the algorithm with both the task of recovering a good intermediate representation and learning to classify correctly. Most current systems separate the learning problem into two stages by solving the first step of recovering the intermediate representation heuristically and using it to learn the final classifier. This paper develops a novel joint learning algorithm for both tasks, that uses the final prediction to guide the selection of the best intermediate representation. We evaluate our algorithm on three different NLP tasks -- transliteration, paraphrase identification and textual entailment -- and show that our joint method significantly improves performance.
BibTeX
@inproceedings{chang2010discriminative,
  author = {Ming-Wei Chang and Dan Goldwasser and Dan Roth and Vivek Srikumar},
  title = {{Discriminative Learning over Constrained Latent Representations}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2010},
  url = {https://openreview.net/forum?id=HJWsc7-_Wr},
}
Figure