A Joint Information Model for N-Best Ranking

Patrick Pantel, Vishnu VyasCOLING 2008

TL;DR

This paper introduces a novel "Joint Information Ranking" (JIR) model that improves the quality of n-best lists by considering the information overlap between candidate explanations. Unlike traditional methods that rank items independently, JIR models the joint information content of a set of explanations, leading to more informative and human-preferred results for tasks like explaining term similarity.

What Problem Does This Paper Address?

Many applications, from search engines to recommendation systems, present users with an "n-best list" – a ranked set of the top n results. A key challenge in generating these lists is that individual results might be relevant, but the set as a whole might be redundant or lack overall informativeness. For instance, when explaining why a group of words are similar, a list of properties might contain many overlapping or similar explanations. The paper focuses on the specific task of selecting the best n semantic properties to explain the similarity of a set of terms, where the goal is to choose a concise set that maximally reduces a user's uncertainty about the original query. Existing methods often treat each potential explanation independently, missing the opportunity to leverage the collective information and reduce redundancy.

Methods

The core contribution is the Joint Information Ranking (JIR) model. JIR is based on information theory, specifically aiming to minimize the conditional information $I(Q|R')$, which represents the remaining uncertainty about the query $Q$ given the set of selected properties $R'$. This is achieved by iteratively selecting properties that contribute the most new information to the growing set, effectively reducing redundancy.

The paper contrasts JIR with a baseline Expected Independent Information Ranking (EIIR) model. EIIR uses pointwise mutual information (pmi) to measure the association between a property and each term in the query set independently, then averages these scores. JIR, on the other hand, considers the properties jointly.

Candidate properties are extracted by analyzing syntactic dependencies in a large corpus. For a given set of similar terms, the system identifies common dependency links (e.g., "shredded," "eat," "import" for "apple" and "beef") which form the candidate explanations.

Datasets

The paper uses corpus statistics extracted from the TREC-9 and TREC-2002 Aquaint collections, approximately 600 million words, for training the models and computing probabilities. For evaluation, they used 100 randomly chosen concepts from the CBC collection, each consisting of 1628 clusters of nouns. For each concept, they randomly selected 2-3 noun instances to form query sets. The evaluation involved 500 test cases annotated by two human judges.

Key Insights and Ideas

  • Joint Information is Key: The central idea is that the collective information of a set of explanations is more valuable than the sum of independent explanations. Redundant properties offer diminishing returns.
  • Uncertainty Reduction as a Metric: The paper frames the problem as reducing a user's uncertainty about the original query. A better set of explanations is one that makes it easier to reconstruct or understand the query.
  • Information Theory for Ranking: Applying information-theoretic principles (specifically conditional self-information) provides a principled way to model and optimize for joint information content.
  • Human Preference Aligns with Joint Information: Empirical results strongly suggest that humans prefer explanation sets generated by the joint model, indicating that this approach captures a crucial aspect of human judgment for clarity and informativeness.

Key Results

  • Human judges significantly preferred the JIR model over the independent EIIR model.
  • In cases where one list was preferred over the other (50.0% ± 3.1% of the time), the JIR lists were preferred 76.6% ± 5.2% of the time, with 95% confidence.
  • The JIR model's superiority was more pronounced for larger explanation set sizes (n ≥ 3), aligning with the intuition that redundancy is more problematic when more items are presented.
  • Qualitative analysis showed that JIR's ability to avoid redundant properties (like "pink" and "yellow" when "flowering" already captures a key aspect) led to more informative sets.

Limitations and Future Work

  • Computational Complexity: The brute-force optimal solution for JIR involves checking all subsets of properties, which is computationally expensive. The paper uses a greedy suboptimal solution, which performed well but could be further optimized.
  • Corpus Dependence: The quality of extracted properties depends on the corpus used. The paper acknowledges that their method might miss some correct semantic properties or extract non-semantic ones.
  • Future Work: The authors plan to investigate other joint models using latent semantic analysis, explore heuristic algorithms for optimizing the JIR objective function, and apply the JIR method to other ranking tasks like keyword search and recommendation systems. They also plan to compare their method with diversity-based ranking techniques like Maximal Marginal Relevance (MMR).

Summary updated

BibTeX
@inproceedings{pantel2008joint,
  author = {Patrick Pantel and Vishnu Vyas},
  title = {{A Joint Information Model for N-Best Ranking}},
  booktitle = {International Conference on Computational Linguistics},
  year = {2008},
}
Figure