On Conceptual Labeling of a Bag of Words

Xiangyan Sun, Yanghua Xiao, Haixun Wang, Wei Wang

Introduction

In Natural Language Processing (NLP), text is frequently represented as a "bag of words"—a collection of symbols that lack explicit semantic structure. While vector embeddings capture some relationships, they do not provide high-level, human-readable summaries. This paper introduces Conceptual Labeling (CL), a method to automatically summarize these collections into a small set of interpretable concepts. For instance, the set {china, japan, korea} might be labeled as "asian country."

The Challenge of Granularity and Relationships

Effective conceptual labeling faces two primary hurdles:

  1. Granularity: A label must be specific enough to be useful. While "country" is technically correct for {china, japan}, "asian country" is a superior label because it captures the shared geographic context.
  2. Relationship Diversity: Words are not always direct instances of a concept. In the set {population, gdp, location}, the words are attributes of a "country" rather than instances. Traditional taxonomies often fail to bridge this gap.

Methodology: MDL and Probase

The authors frame conceptual labeling as a data compression problem governed by the Minimum Description Length (MDL) principle. The goal is to find a set of labels that minimizes the total "cost" (in bits) required to describe both the labels themselves and the original words given those labels.

Probase Integration

The system leverages Probase, a massive semantic network containing over 3 million concepts. Probase provides "typicality" scores, which quantify the strength of association between words and concepts.

Probabilistic Modeling

A noisy-or model integrates two relationship types:

  • isA: Instance-of relationships (e.g., apple is a fruit).
  • isPropertyOf: Attribute-of relationships (e.g., gdp is a property of country).

Optimization

To navigate the vast search space of Probase, the authors employ a greedy search strategy. Starting from an empty set, the algorithm iteratively moves, removes, or replaces concepts to find the configuration that minimizes the MDL score. A tunable parameter, $\alpha$, allows users to balance between label minimality (broader concepts) and coverage (more specific concepts).

Experimental Evaluation

The approach was tested against a Clustering-then-Conceptualization (CC) baseline using three datasets:

  1. Synthetic Data: 1,000 bags of words generated from Probase to establish ground truth.
  2. Flickr Data: Real-world image tags assigned by users.
  3. Wikipedia Data: Latent topics extracted via Latent Dirichlet Allocation (LDA).

Key Results

The MDL-based models (MDL-2P and MDL-NML) significantly outperformed the baseline across all metrics.

Performance comparison on synthetic data showing precision, recall, and F-score across varying concept counts ($n_c$), instances ($n_i$), and noise ($n_n$).

On synthetic data, the MDL approach maintained high precision and recall even as noise levels increased. In contrast, the CC baseline's performance degraded rapidly as the number of concepts and noise increased.

Human Evaluation

Human volunteers rated the generated labels on a scale of 0 (misleading) to 3 (perfect). The MDL models achieved scores nearly double those of the baseline, indicating a strong alignment with human intuition.

Human evaluation scores for Flickr and Wikipedia datasets, comparing the CC baseline with MDL-2P and MDL-NML models.

Conclusion

By treating labeling as a compression task, the MDL framework naturally implements Occam's Razor, selecting the simplest set of concepts that adequately explain the data. The inclusion of attribute relationships and the ability to handle outliers make it a robust tool for summarizing unstructured text. Future work may extend this to handle more complex linguistic structures beyond nouns and attributes.

Summary updated

Abstract

In natural language processing and information retrieval, the bag of words representation is used to implicitly represent the meaning of the text. Implicit semantics, however, are insufficient in supporting text or natural language based interfaces, which are adopted by an increasing number of applications. Indeed, in applications ranging from automatic ontology construction to question answering, explicit representation of semantics is starting to play a more prominent role. In this paper, we introduce the task of conceptual labeling (CL), which aims at generating a minimum set of conceptual labels that best summarize a bag of words. We draw the labels from a data driven semantic network that contains millions of highly connected concepts. The semantic network provides meaning to the concepts, and in turn, it provides meaning to the bag of words through the conceptual labels we generate. To achieve our goal, we use an information theoretic approach to trade-off the semantic coverage of a bag of words against the minimality of the output labels. Specifically, we use Minimum Description Length (MDL) as the criteria in selecting the best concepts. Our extensive experimental results demonstrate the effectiveness of our approach in representing the explicit semantics of a bag of words.
BibTeX
@inproceedings{sun2015conceptual,
  author = {Xiangyan Sun and Yanghua Xiao and Haixun Wang and Wei Wang},
  title = {{On Conceptual Labeling of a Bag of Words}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure