Overview of AutoFeed: An Unsupervised Learning System for Generating Webfeeds

Bora Gazen, Steven MintonAAAI 2006

Abstract

AutoFeed is an unsupervised learning system designed to automatically extract structured data from semi-structured websites without requiring manual labeling or site-specific training. By combining "hints" from a diverse set of specialized experts (analyzing URLs, layouts, and patterns), the system clusters pages and data into relational tables with performance comparable to labor-intensive supervised methods.

Introduction

The web is full of semi-structured data—think product catalogs, news feeds, or job listings—that is easy for humans to read but difficult for machines to parse into structured formats like RSS feeds. Traditionally, this is solved via wrapper induction, a supervised learning approach where a human manually marks up example pages to teach the system how to extract data.

However, supervised methods have two major drawbacks: they require significant human effort to create training sets, and the resulting "wrappers" are often brittle and site-specific. Previous attempts at unsupervised learning faced a "chicken and egg" problem: to learn the grammar of a page, you need a set of similar example pages, but to find those similar pages automatically, you usually need to understand their underlying grammar first. AutoFeed aims to break this cycle.

Methods: The Hint Framework and Probabilistic Clustering

AutoFeed shifts the focus from finding a single "perfect" extraction rule to a collaborative, probabilistic clustering approach. Its architecture relies on three main pillars:

  1. Heterogeneous Experts: Instead of one monolithic algorithm, the system uses a suite of specialized "experts." Each expert looks for a specific type of structure, such as URL naming schemes, HTML template patterns, list structures, or visual layouts.
  2. The "Hint" Framework: To allow these diverse experts to communicate, they all output their findings in a common language called "hints." A hint is a probabilistic observation that two items (either two pages or two pieces of data) belong in the same cluster.
  3. Probabilistic Clustering: The system treats the extraction task as a clustering problem. It uses a probabilistic model to evaluate different ways of grouping pages (into "page types") and tokens (into "database columns"). It employs a greedy "leader-follower" algorithm to find a locally optimal clustering that best satisfies the collective hints provided by the experts.
Figure 1: Mapping between relational database tables and web page hierarchies.

By tokenizing pages based on where experts see boundaries (like the start and end of a long URL), the system minimizes the search space and ensures that data isn't broken into meaningless fragments.

Datasets and Evaluation

The authors evaluated AutoFeed across three distinct domains to test its versatility:

  • E-Commerce: Seven retail websites originally used in SRI’s CALO project.
  • Electronic Journals: All pages from four different online academic journals.
  • Job Listings: Job posting pages from fifty different employers.

The system was evaluated by comparing its unsupervised output against the output of high-quality, manually-trained supervised wrappers for the same sites.

Key Insights: Relational Recovery

The core "aha moment" is that while any single expert might fail on a specific site, the combination of experts is robust. Sites are designed to be navigable by humans, which naturally creates multiple overlapping patterns (URL patterns, breadcrumbs, consistent CSS classes).

By reducing complex structural analysis to simple "hints" (A is like B), the authors created a framework where very different AI techniques (syntax, semantics, and pragmatics) can be combined without needing to understand each other's internal logic. The paper frames web extraction not just as "scraping" but as "recovering the underlying database." It assumes the website was likely generated from a relational database and attempts to reverse-engineer that original schema.

Key Results

AutoFeed demonstrated that unsupervised learning can achieve "near-perfect" extraction in many cases. As shown in Table 1, precision and recall remain high across diverse domains.

Table 1: Performance metrics of AutoFeed across Commerce, Journals, and Jobs domains.
  • Precision: In the E-commerce and Job Listing domains, precision was frequently 100%, meaning that when the system identified a data column (like "price" or "location"), it rarely included incorrect data.
  • Recall: For most fields, recall was high (90%–97%). However, it struggled slightly with specific elements, such as "links" in the journal domain, where recall dropped to 44% because the experts couldn't find enough consistent hints to group them.
  • Efficiency: Most importantly, the system achieved these results with zero training data, making it significantly more scalable than supervised wrapper induction.

Limitations and Future Work

While the extraction is unsupervised, a human is still required at the very end to look at the generated tables and decide which columns are actually useful for the final webfeed. Furthermore, the system's performance is strictly capped by the quality of its experts. If a site uses a highly unconventional layout that none of the experts recognize, the clustering will fail.

The current "leader-follower" algorithm is a greedy search, which can get stuck in local optima. The authors suggest that more sophisticated global optimization techniques could improve the clustering accuracy. Future work may also involve integrating existing techniques like grammar induction or automatic table analysis as additional "experts" to make the system even more robust.

Summary updated

BibTeX
@inproceedings{gazen2006overview,
  author = {Bora Gazen and Steven Minton},
  title = {{Overview of AutoFeed: An Unsupervised Learning System for Generating Webfeeds}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2006},
}
Figure