Introduction
In the early 1990s, the rapid expansion of networked information resources—often referred to as the "information superhighway"—began to outpace the ability of human programmers to manually catalog and integrate them. For a software agent to be truly autonomous and useful, it must interact with a variety of information resources, such as online directories or system commands. Traditionally, this required a human to write a "wrapper" for every new database, explicitly defining the semantic meaning of each data field (e.g., defining that "Field 1" is a surname).
Perkowitz and Etzioni (1994) addressed this bottleneck by proposing a method for automated discovery. Their goal was to enable an agent to encounter an undocumented database and autonomously determine the meaning of its fields, transforming raw data into structured, actionable tools without human intervention. This approach moves away from the impossible task of manually mapping the entire internet, favoring agents that can dynamically learn to use tools as they encounter them.
The Correspondence Heuristic
The core of the proposed framework is the correspondence heuristic. This approach leverages the overlap between an agent's internal "world model" (its existing knowledge base) and the raw data returned by a database query.
The heuristic operates on a simple premise: if an agent queries a database and recognizes a specific token in the output, it can use its internal knowledge about that token to infer the meaning of the field. For example, if an agent queries a directory and receives the token "Etzioni," it consults its world model. If the model identifies "Etzioni" as a lastname, the agent hypothesizes that the database field containing that token represents the lastname predicate.
Formalization and Predicate Mismatch
The authors formalize this process using logical determinations. They posit that if two records share the same value in a specific syntactic position, they likely share the same semantic property within the agent's model. This allows the agent to generalize from a few recognized tokens to the entire structure of the database.
However, real-world data is rarely a perfect 1:1 match for an agent's internal schema. To address "predicate mismatch," the authors employ a technique similar to spreading activation. If a database links a person directly to a "Mail Stop" code, but the agent's model only knows the relationships Person -> Department and Department -> Mail Stop, the agent searches for a chain of relationships in its knowledge base to bridge the gap. This allows the agent to interpret complex, indirect relationships that were not explicitly predefined.
Evaluation: Learning from System Resources
The authors tested their approach on several common networked and system resources of the era:
- staffdir: The University of Washington's internal personnel directory.
- ls: The standard Unix command for listing directory contents.
- finger: A Unix protocol used to exchange user information and status.
By treating these as query/response databases with tabular output, the agent successfully learned to map syntactic fields to semantic predicates. While the evaluation was a proof-of-concept, it demonstrated that an agent could bootstrap its understanding of new tools using its existing knowledge. The agent effectively separated the problem into learning the syntax (how fields are ordered) and the semantics (what those fields mean).
Key Insights and Limitations
The primary insight of this work is that knowledge serves as a bootstrap. An agent does not require a manual if it possesses a "dictionary" of the world; it can use known entities to decode unknown structures.
Despite its success, the method has notable limitations:
- Syntactic Complexity: The initial model assumes simple, ordered-field syntax. The authors acknowledged that future work would need to handle more complex formats, such as keyword-based syntax.
- Model Dependency: The agent's learning capability is strictly bounded by the breadth of its internal world model. If the agent does not already recognize the tokens it receives, the correspondence heuristic cannot be applied.
- Scalability: While effective for small-scale system tools, the authors' ultimate goal was extending this logic to the "World Wide Web," requiring programs that could traverse and interpret the web automatically.
Conclusion
Perkowitz and Etzioni's work laid the groundwork for autonomous resource discovery. By moving away from static, hard-coded wrappers and toward dynamic, knowledge-based learning, they envisioned a future where software agents could navigate and utilize the expanding digital landscape with minimal human oversight.
Summary updated