Abstract
Information extraction (IE) from unstructured, ungrammatical text—such as online classifieds and auction listings—poses a significant challenge for traditional natural language processing tools. This paper introduces a novel method for automatically constructing "reference sets" (structured lists of entities and attributes) directly from the target data. By utilizing a minimal amount of "seed" knowledge (e.g., a list of brand names), the proposed system discovers complex hierarchies and specific model details within the text. Experimental results across three domains—cars, laptops, and skis—demonstrate that these data-driven reference sets often outperform manually curated external databases by providing superior coverage of niche and secondary market terms.
The Challenge of Unstructured Data
Extracting structured information from platforms like Craigslist or eBay is notoriously difficult. Unlike formal documents, these posts lack standard grammar, rendering standard NLP tools ineffective. Furthermore, inconsistent HTML structures prevent the reliable use of wrapper induction.
A common solution involves using external "reference sets" to identify known entities. For instance, knowing that "Civic" is a model of "Honda" allows a system to extract these attributes from a messy advertisement. However, external databases (like Edmunds.com) frequently suffer from coverage issues, missing older models, niche brands, or the specific slang prevalent in user-generated content.
Seed-Based Reference Set Construction
To address the coverage gap, this research proposes building reference sets from the target text itself using a small set of high-level "seeds" (e.g., "Dell," "Honda," or "Rossignol"). The approach centers on three core components:
- Entity Trees: The system constructs hierarchical structures where seeds serve as roots (e.g., Make → Model → Trim).
- Subsumption Heuristic: To determine hierarchical relationships, the algorithm uses a conditional probability rule. A word $x$ is considered a parent of $y$ if $P(x|y)$ is high (whenever the model appears, the make usually does too) and $P(y|x)$ is relatively low (the make appears in many contexts without that specific model).
- Iterative Refinement: The system identifies "general tokens"—terms like "LE" or "DX" that apply to multiple models—and iteratively links them to the correct parents in the hierarchy.
Evaluation and Datasets
The method was evaluated on three real-world datasets:
- Cars: 2,568 Craigslist posts (Attributes: make, model, trim).
- Laptops: 2,921 Craigslist posts (Attributes: maker, model, model number).
- Skis: 4,981 eBay posts (Attributes: brand, model, model spec).
The seed-based approach was compared against manually scraped reference sets, an unconstrained automated version of the algorithm, and supervised Conditional Random Fields (CRFs).
Key Results and Insights
- Coverage Trumps Cleanliness: Reference sets built from messy, real-world posts consistently led to better extraction than "clean" professional databases. This is particularly evident in highly specific attributes; for laptop model numbers, the seed-based method achieved an F1-measure of 49.17, compared to just 11.23 for the manual set.
- Efficiency of Seeds: The method leverages "cheap" knowledge (popular brands) to discover "hard" knowledge (exhaustive model lists) that is otherwise difficult to aggregate.
- Competitive Performance: The seed-based method outperformed manually constructed sets on 5 out of 9 attributes and remained competitive on 7 out of 9. Notably, it also outperformed supervised CRFs on a majority of attributes without requiring expensive labeled training data.
Conclusion and Future Work
While the system successfully discovers entity clusters, it currently requires human intervention to map discovered tree levels to specific attribute names (e.g., labeling a level as "Model"). Additionally, attributes lacking a clear hierarchical structure, such as a car's "Year," remain difficult to extract via the subsumption heuristic. Future research may involve integrating "top-down" knowledge from web services to further enrich the discovered reference sets.
Summary updated