Steven Minton

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.

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

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.

AAAI Conference 1996 Conference Paper

Is There Any Need for Domain-Dependent Control Information?: A Reply

• Steven Minton

In this paper, we consider the role that domaindependent control knowledge plays in problem solving systems. Ginsberg and Geddis (Ginsberg & Geddis 1991) have claimed that domaindependent control information has no place in declarative systems; instead, they say, such information should be derived from declarative facts about the domain plus domain-independent principles. We dispute their conclusion, arguing that it is impractical to generate control knowledge solely on the basis of logical derivations. We propose that simplifying abstractions are crucial for deriving control knowledge, and, as a result, empirical utility evaluation of the resulting rules will frequently be necessary to validate the utility of derived control knowledge. We ihustrate our arguments with examples from two implemented systems.

AAAI Conference 1994 Conference Paper

Small is Beautiful: A Brute-Force Approach to Learning First-Order Formulas

• Steven Minton

We describe a method for learning formulas in firstorder logic using a brute-force, smallest-first search. The method is exceedingly simple. It generates all irreducible well-formed formulas up to a fixed size and tests them against a set of examples. Although the method has some obvious limitations due to its computational complexity, it performs surprisingly well on some tasks. This paper describes experiments with two applications of the method in the MULTI-TACsystem, a program synthesizer for constraint satisfaction problems. In the first application, axioms are learned, and in the second application, search control rules are learned. We describe these experiments, and consider why searching the space of small formulas makes sense in our applications.

IJCAI Conference 1993 Conference Paper

An Analytic Learning System for Specializing Heuristics

• Steven Minton

This paper describes how meta-level theories are used for analytic learning in M U L T I - T A C. M U L T I - T A C operationalizes generic heuristics for constraint-satisfaction problems, in order to create programs that are tailored to specific problems. For each of its generic heuristics, M U L T I - T A C has a meta-theory specifically designed for operationalising that heuristic. We present examples of the specialisation process and discuss how the theories influence the tractability of the learning process. We also describe an empirical study showing that the specialised programs produced by M U L T I - T A C compare favorably to hand-coded programs.

AAAI Conference 1993 Conference Paper

Integrating Heuristics for Constraint Satisfaction Problems: A Case Study

• Steven Minton

This paper describes a set of experiments with a system that synthesizes constraint satisfaction programs. The system, MULTI-TAC, is a CSP “expert” that can specialize a library of generic algorithms and methods for a particular application. MULTI-TAC not only proposes domain-specific versions of its generic heuristics, but also searches for the best combination of these heuristics and integrates them into a complete problem-specific program. We demonstrate MULTI-TAC'S capabilities on a combinatorial problem, “Minimum Maximal Matching”, and show that MULTI-TAC can synthesize programs for this problem that are on par with hand-coded programs. In synthesizing a program, MULTI-TAC bases its choice of heuristics on the instance distribution, and we show that this capability has a significant impact on the results.

AIJ Journal 1992 Journal Article

Minimizing conflicts: a heuristic repair method for constraint satisfaction and scheduling problems

• Steven Minton
• Mark D. Johnston
• Andrew B. Philips
• Philip Laird

The paper describes a simple heuristic approach to solving large-scale constraint satisfaction and scheduling problems. In this approach one starts with an inconsistent assignment for a set of variables and searches through the space of possible repairs. The search can be guided by a value-ordering heuristic, the min-conflicts heuristic, that attempts to minimize the number of constraint violations after each step. The heuristic can be used with a variety of different search strategies. We demonstrate empirically that on the n-queens problem, a technique based on this approach performs orders of magnitude better than traditional backtracking techniques. We also describe a scheduling application where the approach has been used successfully. A theoretical analysis is presented both to explain why this method works well on certain types of problems and to predict when it is likely to be most effective.

IJCAI Conference 1991 Conference Paper

Commitment Strategies in Planning: A Comparative Analysis

• Steven Minton
• John Bresina
• Mark

In this paper we compare the utility of different commitment strategies in planning. Under a "least commitment strategy", plans are represented as partial orders and operators are ordered only when interactions are detected. We investigate claims of the inherent advantages of planning with partial orders, as compared to planning with total orders. By focusing our analysis on the issue of operator ordering commitment, we are able to carry out a rigorous comparative analysis of two planners. We show that partial-order planning can be more efficient than total-order planning, but we also show that this is not necessarily so.

AIJ Journal 1990 Journal Article

Quantitative results concerning the utility of explanation-based learning

• Steven Minton

In order to solve problems effectively, a problem solver must be able to exploit domain-specific search control knowledge. Although previous research has demonstrated that explanation-based learning is a viable approach for acquiring such knowledge, in practice the control knowledge learned via EBL may not be useful. To be useful, the cumulative benefits of applying the knowledge must outweigh the cumulative costs of testing whether the knowledge is applicable. Unlike most previous systems that use EBL, the PRODIGY system evaluates the costs and benefits of the control knowledge it learns. Furthermore, the system produces useful control knowledge by actively searching for “good” explanations—explanations that can be profitably employed to control problem solving. This paper summarizes a set of experiments measuring the effectiveness of PRODIGY's EBL method (and its components) in several different domains.

AAAI Conference 1990 Conference Paper

Solving Large-Scale Constraint-Satisfaction and Scheduling Problems Using a Heuristic Repair Method

• Steven Minton
• Andrew B. Philips

This paper describes a simple heuristic method for solving large-scale constraint satisfaction and scheduling problems. Given an initial assignment for the variables in a problem, the method operates by searching though the space of possible repairs. The search is guided by an ordering heuristic, the min-conflicts heuristic, that attempts to minimize the number of constraint violations after each step. We demonstrate empirically that the method performs orders of magnitude better than traditional backtracking techniques on certain standard problems. For example, the one million queens problem can be solved rapidly using our approach. We also describe practical scheduling applications where the method has been suc-. cessfully applied. A theoretical analysis is presented to explain why the method works so well on certain types of problems and to predict when it is likely to be most effective.

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.

AAAI Conference 1988 Conference Paper

Quantitative Results Concerning the Utility of Explanation-Based Learning

• Steven Minton

IJCAI Conference 1987 Conference Paper

Strategies for Learning Search Control Rules: An Explanation-based Approach

• Steven Minton
• Jaime G. Carbonell

AAAI Conference 1984 Conference Paper

Constraint-Based Generalization: LeaMing Game-Playing Plans from Single Examples

• Steven Minton

Constraint-based Generalization is a technique for deducing generalizations from a single example. We show how this technique can be used for learning tactical combinations in games and discuss an implementation which learns forced wins in tic-tat-toe, go-moku, and chess. ’