Craig A. Knoblock

JAAMAS Journal 2026 Journal Article

Hierarchical Wrapper Induction for Semistructured Information Sources

• Ion Muslea
• Steven Minton
• Craig A. Knoblock

Abstract With the tremendous amount of information that becomes available on the Web on a daily basis, the ability to quickly develop information agents has become a crucial problem. A vital component of any Web-based information agent is a set of wrappers that can extract the relevant data from semistructured information sources. Our novel approach to wrapper induction is based on the idea of hierarchical information extraction, which turns the hard problem of extracting data from an arbitrarily complex document into a series of simpler extraction tasks. We introduce an inductive algorithm, STALKER, that generates high accuracy extraction rules based on user-labeled training examples. Labeling the training data represents the major bottleneck in using wrapper induction techniques, and our experimental results show that STALKER requires up to two orders of magnitude fewer examples than other algorithms. Furthermore, STALKER can wrap information sources that could not be wrapped by existing inductive techniques.

IJCAI Conference 2021 Conference Paper

SPADE: A Semi-supervised Probabilistic Approach for Detecting Errors in Tables

• Minh Pham
• Craig A. Knoblock
• Muhao Chen
• Binh Vu
• Jay Pujara

Error detection is one of the most important steps in data cleaning and usually requires extensive human interaction to ensure quality. Existing supervised methods in error detection require a significant amount of training data while unsupervised methods rely on fixed inductive biases, which are usually hard to generalize, to solve the problem. In this paper, we present SPADE, a novel semi-supervised probabilistic approach for error detection. SPADE introduces a novel probabilistic active learning model, where the system suggests examples to be labeled based on the agreements between user labels and indicative signals, which are designed to capture potential errors. SPADE uses a two-phase data augmentation process to enrich a dataset before training a deep learning classifier to detect unlabeled errors. In our evaluation, SPADE achieves an average F1-score of 0. 91 over five datasets and yields a 10% improvement compared with the state-of-the-art systems.

IJCAI Conference 2017 Conference Paper

Learning with Previously Unseen Features

• Yuan Shi
• Craig A. Knoblock

We study the problem of improving a machine learning model by identifying and using features that are not in the training set. This is applicable to machine learning systems deployed in an open environment. For example, a prediction model built on a set of sensors may be improved when it has access to new and relevant sensors at test time. To effectively use new features, we propose a novel approach that learns a model over both the original and new features, with the goal of making the joint distribution of features and predicted labels similar to that in the training set. Our approach can naturally leverage labels associated with these new features when they are accessible. We present an efficient optimization algorithm for learning the model parameters and empirically evaluate the approach on several regression and classification tasks. Experimental results show that our approach can achieve on average 11. 2% improvement over baselines.

IJCAI Conference 2015 Conference Paper

An Iterative Approach to Synthesize Data Transformation Programs

• Bo Wu
• Craig A. Knoblock

Programming-by-Example approaches allow users to transform data by simply entering the target data. However, current methods do not scale well to complicated examples, where there are many examples or the examples are long. In this paper, we present an approach that exploits the fact that users iteratively provide examples. It reuses the previous subprograms to improve the efficiency in generating new programs. We evaluated the approach with a variety of transformation scenarios. The results show that the approach significantly reduces the time used to generate the transformation programs, especially in complicated scenarios.

IJCAI Conference 2013 Conference Paper

Discovering Alignments in Ontologies of Linked Data

• Rahul Parundekar
• Craig A. Knoblock
• José Luis Ambite

Recently, large amounts of data are being published using Semantic Web standards. Simultaneously, there has been a steady rise in links between objects from multiple sources. However, the ontologies behind these sources have remained largely disconnected, thereby challenging the interoperability goal of the Semantic Web. We address this problem by automatically finding alignments between concepts from multiple linked data sources. Instead of only considering the existing concepts in each ontology, we hypothesize new composite concepts, defined using conjunctions and disjunctions of (RDF) types and value restrictions, and generate alignments between them. In addition, our techniques provide a novel method for curating the linked data web by pointing to likely incorrect or missing assertions. Our approach provides a deeper understanding of the relationships between linked data sources and increases the interoperability among previously disconnected ontologies.

IJCAI Conference 2009 Conference Paper

• Matthew Michelson
• Craig A. Knoblock

Previous work on information extraction from unstructured, ungrammatical text (e. g. classified ads) showed that exploiting a set of background knowledge, called a “reference set, ” greatly improves the precision and recall of the extractions. However, finding a source for this reference set is often dif- ficult, if not impossible. Further, even if a source is found, it might not overlap well with the text for extraction. In this paper we present an approach to building the reference set directly from the text itself. Our approach eliminates the need to find the source for the reference set, and ensures better overlap between the text and reference set. Starting with a small amount of background knowledge, our technique constructs tuples representing the entities in the text to form a reference set. Our results show that our method outperforms manually constructed reference sets, since hand built reference sets may not overlap with the entities in the unstructured, ungrammatical text. We also ran experiments comparing our method to the supervised approach of Conditional Random Fields (CRFs) using simple, generic features. These results show our method achieves an improvement in F1-measure for 6/9 attributes and is competitive in performance on the others, and this is without training data. ∗ This research is based upon work supported in part by the National Science Foundation under award number IIS-0324955; in part by the Air Force Office of Scientific Research under grant number FA9550-07-1-0416; and in part by the Defense Advanced Research Projects Agency (DARPA) under Contract No. FA8750-07- D-0185/0004. The United States Government is authorized to reproduce and distribute reports for Governmental purposes not withstanding any copyright annotation thereon. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of any of the above organizations or any person connected with them. † Work done while at USC Information Sciences Institute.

AIJ Journal 2008 Journal Article

Speculative plan execution for information gathering

• Greg Barish
• Craig A. Knoblock

The execution performance of an information gathering plan can suffer significantly due to remote I/O latencies. A streaming dataflow model of execution addresses the problem to some extent, exploiting all natural opportunities for parallel execution, as allowed by the data dependencies in a plan. Unfortunately, plans that integrate information from multiple sources often use the results of one operation as the basis for forming queries to a subsequent operation. Such cases require sequential execution, an inefficiency that can erase prior gains made through techniques like streaming dataflow. To address this problem, we present a technique called speculative plan execution, an out-of-order method that capitalizes on knowledge gained from prior executions as a means for overcoming remaining data dependencies between plan operators. Our approach inserts additional plan operators that generate and confirm speculative results, while preserving the safety and fairness of overall execution. To increase the utility of speculative execution, we propose a method of value prediction that combines caching with the more effective and space-efficient techniques of classification and transduction. We present experimental results that demonstrate how the performance of information gathering plans can benefit from speculative execution and how its overall utility can be increased through our hybrid method of value prediction.

IJCAI Conference 2007 Conference Paper

• Mark J Carman
• Craig A. Knoblock

The Internet is full of information sources providing various types of data from weather forecasts to travel deals. These sources can be accessed via web-forms, Web Services or RSS feeds. In order to make automated use of these sources, one needs to first model them semantically. Writing semantic descriptions for web sources is both tedious and error prone. In this paper we investigate the problem of automatically generating such models. We introduce a framework for learning Datalog definitions for web sources, in which we actively invoke sources and compare the data they produce with that of known sources of information. We perform an inductive search through the space of plausible source definitions in order to learn the best possible semantic model for each new source. The paper includes an empirical evaluation demonstrating the effectiveness of our approach on real-world web sources.

AAAI Conference 2006 Conference Paper

Learning Blocking Schemes for Record Linkage

• Matthew Michelson
• Craig A. Knoblock

Record linkage is the process of matching records across data sets that refer to the same entity. One issue within record linkage is determining which record pairs to consider, since a detailed comparison between all of the records is impractical. Blocking addresses this issue by generating candidate matches as a preprocessing step for record linkage. For example, in a person matching problem, blocking might return all people with the same last name as candidate matches. Two main problems in blocking are the selection of attributes for generating the candidate matches and deciding which methods to use to compare the selected attributes. These attribute and method choices constitute a blocking scheme. Previous approaches to record linkage address the blocking issue in a largely ad-hoc fashion. This paper presents a machine learning approach to automatically learn effective blocking schemes. We validate our approach with experiments that show our learned blocking schemes outperform the ad-hoc blocking schemes of non-experts and perform comparably to those manually built by a domain expert.

IJCAI Conference 2003 Conference Paper

Active Learning with Strong and Weak Views: A Case Study on Wrapper Induction

• Ion Muslea
• Steven N Minton
• Craig A. Knoblock

Multi-view learners reduce the need for labeled data by exploiting disjoint sub-sets of features (views), each of which is sufficient for learning. Such algorithms assume that each view is a strong view (i. e. , perfect learning is possible in each view). We extend the multi-view framework by introducing a novel algorithm, Aggressive Co-Testing, that exploits both strong and weak views; in a weak view, one can learn a concept that is strictly more general or specific than the target concept. Aggressive Co-Testing uses the weak views both for detecting the most informative examples in the domain and for improving the accuracy of the predictions. In a case study on 33 wrapper induction tasks, our algorithm requires significantly fewer labeled examples than existing state-of-the-art approaches.

IJCAI Conference 2003 Conference Paper

Deploying Information Agents on the Web

• Craig A. Knoblock

The information resources on the Web are vast, but much of the Web is based on a browsing paradigm that requires someone to actively seek information. Instead, one would like to have information agents that continuously attend to one's personal information needs. Such agents need to be able to extract the relevant information from web sources, integrate data across sites, and execute efficiently in a networked environment. In this paper I describe the technologies we have developed to rapidly construct and deploy information agents on the Web. This includes wrapper learning to convert online sources into agent-friendly resources, query planning and record linkage to integrate data across different sites, and streaming dataflow execution to efficiently execute agent plans. I also describe how we applied this work within the Electric Elves project to deploy a set of agents for continuous monitoring of travel itineraries. We have developed a set of core technologies to simplify the task of building intelligent agents for gathering and monitoring information on the Web [Knoblock et al, 2003; 2001; Barish and Knoblock, 2()02al. The technologies include the ability to gather information from the Web, to link that information with related information, to build plans to integrate the various sources of data, and to efficiently execute these plans in the Web environment. We have applied these technologies to build agents for a variety of applications [Barish et al, 2000; Ambite et a/. , 20021, including an application for monitoring travel plans from online sources. Researchers have developed a variety of agents that have been deployed on the Web over the years. Some notable systems include the Internet Softbot [Etzioni and Weld, 1994], an agent that interacts with a range of Internet resources, BargainFinder [Krulwich, 19961, a comparison shopping agent for CDs, ShopBot [Perkowitz et a/. , 19971, a system for automatically locating and incorporating new stores into a comparison shopping agent, and Warren [Decker et al, 1997], a system for gathering data on a financial portfolio. There has also been a significant amount of research on the underlying technologies required for developing agents on the Internet [Levy and Weld, 2000]. As noted by Etzioni [1996], the Web provides a tremendous opportunity for building intelligent software agents. Yet, surprisingly few have seized this opportunity. This is almost certainly because there are many technical issues that must be addressed to build such agents. Our work is designed to address these issues and simplify the task of building agents for the Web. In this paper I first describe an example set of agents for monitoring travel plans. Then 1 will briefly describe the technologies that we have developed to gather data from web sources, link data across sources, generate plans to integrate the data, and efficiently execute these plans. Finally, I present directions for future research and conclusions. 2 Information Agents for Monitoring Travel As part of the Electric Elves project [Chalupsky et a/. , 2001; Ambite et al. , 20021 we have applied our agent technologies to build a set of agents for various tasks including tracking visitor schedules, monitoring meeting schedules, and monitoring a user's travel plans. In the case of monitoring travel plans, this task is particularly well-suited for applying agent technology for several reasons: a) this is a fairly compli- 1580 INVITED SPEAKERS

ICML Conference 2002 Conference Paper

Active + Semi-supervised Learning = Robust Multi-View Learning

• Ion Muslea
• Steven Minton
• Craig A. Knoblock

ICML Conference 2002 Conference Paper

Adaptive View Validation: A First Step Towards Automatic View Detection

• Ion Muslea
• Steven Minton
• Craig A. Knoblock

AAAI Conference 2002 Conference Paper

Getting from Here to There: Interactive Planning and Agent Execution for Optimizing Travel

• José Luis Ambite
• Craig A. Knoblock
• and Jean Oh

Planning and monitoring a trip is a common but complicated human activity. Creating an itinerary is nontrivial because it requires coordination with existing schedules and making a variety of interdependent choices. Once planned, there are many possible events that can affect the plan, such as schedule changes or flight cancellations, and checking for these possible events requires time and effort. In this paper, we describe how Heracles and Theseus, two information gathering and monitoring tools that we built, can be used to simplify this process. Heracles is a hierarchical constraint planner that aids in interactive itinerary development by showing how a particular choice (e. g. , destination airport) affects other choices (e. g. , possible modes of transportation, available airlines, etc.). Heracles builds on an information agent platform, called Theseus, that provides the technology for efficiently executing agents for information gathering and monitoring tasks. In this paper we present the technologies underlying these systems and describe how they are applied to build a state-of-the-art travel system.

ICAPS Conference 2002 Conference Paper

Speculative Execution for Information Gathering Plans

• Greg Barish
• Craig A. Knoblock

Although information gathering plans have enabled data from remote heterogeneous sources to be easily combined and queried, their execution performance suffers because access to remote sources is often slow. To address this problem, we have developed a method of speculative execution that increases the degree of run-time parallelism during plan execution. Our approach allows any information gathering plan to be automatically modified to support speculation in a manner that can lead to significant speedups, while ensuring that both safety and fairness are preserved. We demonstrate how speculative execution can be applied to a typical Internet information gathering plan to provide significant performance benefits.

AIJ Journal 2000 Journal Article

Flexible and scalable cost-based query planning in mediators: A transformational approach

• José Luis Ambite
• Craig A. Knoblock

The Internet provides access to a wealth of information. For any given topic or application domain there are a variety of available information sources. However, current systems, such as search engines or topic directories in the World Wide Web, offer only very limited capabilities for locating, combining, and organizing information. Mediators, systems that provide integrated access and database-like query capabilities to information distributed over heterogeneous sources, are critical to realize the full potential of meaningful access to networked information. Query planning, the task of generating a cost-efficient plan that computes a user query from the relevant information sources, is central to mediator systems. However, query planning is a computationally hard problem due to the large number of possible sources and possible orderings on the operations to process the data. Moreover, the choice of sources, data processing operations, and their ordering, strongly affects the plan cost. In this paper, we present an approach to query planning in mediators based on a general planning paradigm called Planning by Rewriting (PbR) (Ambite and Knoblock, 1997). Our work yields several contributions. First, our PbR-based query planner combines both the selection of the sources and the ordering of the operations into a single search space in which to optimize the plan quality. Second, by using local search techniques our planner explores the combined search space efficiently and produces high-quality plans. Third, because our query planner is an instantiation of a domain-independent framework it is very flexible and can be extended in a principled way. Fourth, our planner has an anytime behavior. Finally, we provide empirical results showing that our PbR-based query planner compares favorably on scalability and plan quality over previous approaches, which include both classical AI planning and dynamic-programming query optimization techniques.

ICAPS Conference 2000 Conference Paper

Learning Plan Rewriting Rules

• José Luis Ambite
• Craig A. Knoblock
• Steven Minton

Planning byRewriting (PbR) is a newparadigm forefficient high-quality plavningthat exploits plan rewriting rules and etficiel, t local search techniquesto tran~ form an easy-to-generate, butpossibly suboptimal, initial planintoa high-quality plan. Dcspitc theadvantages of PbRin termsof scalability, planquality, and anytime behavior, PbRrequires the user to define a set of domain-specific plan rewriting rules which can be difficult and time-consuming. This paper presents an approach to automatically learning the plaal rewriting rules basedon comparinginitial aJId oI>timai plans. Wereport results for several pla~nningdomains showingthat the learned rules are competitive with manually-specified ones, amdin several cases the lear. n~g zdgoritkmdiscovered novel rewriting rules.

AAAI Conference 1999 Short Paper

Learning to Handle Inconsistency for Multi-Source Integration

• Sheila Tejada
• Craig A. Knoblock
• Steven Minton
• University of Southern California

The goal of this research is to be able to create mapping constructs so that an information broker, like Ariadne, can use it to properly integrate data from inconsistent sources in an intelligent and efficient manner.

ICAPS Conference 1998 Conference Paper

Flexible and Scalable Query Planning in Distributed and Heterogeneous Environments

• José Luis Ambite
• Craig A. Knoblock

Wepresent the apphcationof the Planningby Rewriting (PbR)framework to queryplanningin distributed and heterogeneous environments. PbRis a new paradigmfor efficient high-qualityplanningthat exploits plan rewritingrules andefficient local search techniquesto transforman easy-to-generate, but possibly suboptimal, initial plan into a high-qualityplan. Theresulting planneris scalable, flexible, has anytime behavior, and, applied to queryplanning, yields a novel combinationof traditional query optimization with heterogeneous informationsourceselection. Queryplanners are the core componentof mediator systems, whichare becomingincreasingly important in a worldof interconnectedinformation, and constitute excellenttestbeds for planningtechnology.

AAAI Conference 1998 Conference Paper

Modeling Web Sources for Information Integration

• Craig A. Knoblock
• Jose Luis Ambite
• Pragnesh Jay Modi
• Andrew G. Philpot

The Web is based on a browsing paradigm that makes it difficult to retrieve and integrate data from multiple sites. y-k&y, the only w&y t; g & this is to bl_? ild_ specialized applications, which are time-consuming to develop and difficult to maintain. We are addressing this problem by creating the technology and tools for rapidly constructing information agents that extract, query, and integrate data from web sources. Our approach is based on a simple, uniform representation that makes it efficient to integrate multiple sources. Instead of building specialized algorithms for handling web sources, we have developed methods for mapping web sources into this uniform representation. This approach builds on work from knowledge representation, machine learning and automated planning. The re- =nltims amtom rxllprl Arinclnp rnak~. c it, fast, a. nd chc3. n y. .s"'*LD yJ" -. .. , ---__ ---------, -__- -__-__ __-_ -__- - ___-= to build new information agents that access existing web sources. Ariadne also makes it easy to maintain these agents and incorporate new sources as they become available.

ICAPS Conference 1996 Conference Paper

Building a Planner for Information Gathering: A Report from the Trenches

• Craig A. Knoblock

Information gathering requires locating and integrating data from a set of distributed information sources. These sources may contain overlapping data and can come from different types of sources, including traditional databases, knowledge bases, programs, and Web pages. In this paper we focus on the problem of how to apply a general-purpose planner to produce plans for information gathering. We identify the critical functionality of the basic planner, describe how the information gathering problem can be cast as a planning problem, and present our approach to efficiently generating high-quality plans in this application domain. The resulting information gathering planner is used as the query processor in the SIMS information mediator, which is being applied to provide access to data for transportation logistics and trauma care. We present empirical results in the transportation domain to demonstrate that this planner can efficiently produce information gathering plans on a set of example queries that were provided with the databases.

AIJ Journal 1995 Journal Article

Planning as refinement search: a unified framework for evaluating design tradeoffs in partial-order planning

• Subbarao Kambhampati
• Craig A. Knoblock
• Qiang Yang

Despite the long history of classical planning, there has been very little comparative analysis of the performance tradeoffs offered by the multitude of existing planning algorithms. This is partly due to the many different vocabularies within which planning algorithms are usually expressed. In this paper we show that refinement search provides a unifying framework within which various planning algorithms can be cast and compared. Specifically, we will develop refinement search semantics for planning, provide a generalized algorithm for refinement planning, and show that planners that search in the space of (partial) plans are specific instantiations of this algorithm. The different design choices in partial-order planning correspond to the different ways of instantiating the generalized algorithm. We will analyze how these choices affect the search space size and refinement cost of the resultant planner, and show that in most cases they trade one for the other. Finally, we will concentrate on two specific design choices, viz. , protection strategies and tractability refinements, and develop some hypotheses regarding the effect of these choices on the performance on practical problems. We will support these hypotheses with a series of focused empirical studies.

ICAPS Conference 1994 Conference Paper

Generating Parallel Execution Plans with a Partial-order Planner

• Craig A. Knoblock

Manyreal-world planning problems require generating plans that maximizethe parallelism inherent in a problem. There are a numberof partial-order planners that generate such plans; however, in most of these planners it is unclear under what conditions the resulting plans will be correct and whetherthe plaltner can evenfind a plan if one exists. This paperidentifies the underlying assumptionsabout whena partial plan can be executedin parallel, defines the classes of parallel plans that can be generatedby different partialorder planners, and describes the changes required to turn ucPoPinto a parallel execution planner. In "addition, we describe howthis planner can be applied to the problemof query access planning, where parallel execution produces substantial reductions in overall execution time.

ICML Conference 1994 Conference Paper

Rule Induction for Semantic Query Optimization

• Chun-Nan Hsu
• Craig A. Knoblock

AAAI Conference 1991 Conference Paper

Characterizing Abstraction Hierarchies for Planning

• Craig A. Knoblock

The purposes of this paper are threefold. The first is to provide a crisp formalization of ABSTRIPSstyle abstraction, since the lack of such formalizations has made it difficult to ascertain the uses and value of this type of abstraction in previous research. Second, we define the refinement relationship between solutions at different levels of the abstraction hierarchy. Such definitions are crucial to developing efficient search strategies with this type of hierarchical planning. And third, we provide a restriction on the abstraction mapping that provides a criterion for generating useful abstractions.

AAAI Conference 1991 Conference Paper

Integrating Abstraction and Explanation-Based Learning in PRODIGY

• Craig A. Knoblock

AAAI Conference 1991 Conference Paper

Search Reduction in Hierarchical Problem Solving

• Craig A. Knoblock

It has long been recognized that hierarchical problem solving can be used to reduce search. Yet, there has been little analysis of the problemsolving method and few experimental results. This paper provides the first comprehensive analytical and empirical demonstrations of the effectiveness of hierarchical problem solving. First, the paper shows analytically that hierarchical problem solving can reduce the size of the search space from exponential to linear in the solution length and identifies a sufficient set of assumptions for such reductions in search. Second, it presents empirical results both in a domain that meets all of these assumptions as well as in domains in which these assumptions do not strictly hold. Third, the paper explores the conditions under which hierarchical problem solving will be effective in practice.

AAAI Conference 1990 Conference Paper

Learning Abstraction Hierarchies for Problem Solving

• Craig A. Knoblock

The use of abstraction in problem solving is an effective approach to reducing search, but finding good abstractions is a difficult problem, even for people. This paper identifies a criterion for selecting useful abstractions, describes a tractable algorithm for generating them, and empirically demonstrates that the abstractions reduce search. The abstraction learner, called ALPINE, is integrated with the PRODIGY problem solver [Minton et ab. , 1989b, Carbonell et al. , 19901 and has been tested on large problem sets in multiple domains.

AIJ Journal 1989 Journal Article

Explanation-based learning:A problem solving perspective

• Steven Minton
• Jaime G. Carbonell
• Craig A. Knoblock
• Daniel R. Kuokka
• Oren Etzioni
• Yolanda Gil

This article outlines explanation-based learning (EBL) and its role in improving problem solving performance through experience. Unlike inductive systems, which learn by abstracting common properties from multiple examples, EBL systems explain why a particular example is an instance of a concept. The explanations are then converted into operational recognition rules. In essence, the EBL approach is analytical and knowledge-intensive, whereas inductive methods are empirical and knowledge-poor. This article focuses on extensions of the basic EBL method and their integration with the prodigy problem solving system. prodigy's EBL method is specifically designed to acquire search control rules that are effective in reducing total search time for complex task domains. Domain-specific search control rules are learned from successful problem solving decisions, costly failures, and unforeseen goal interactions. The ability to specify multiple learning strategies in a declarative manner enables EBL to serve as a general technique for performance improvement. prodigy's EBL method is analyzed, illustrated with several examples and performance results, and compared with other methods for integrating EBL and problem solving.