Search through systematic set enumeration
ScholarlyCommons (University of Pennsylvania)Published 25 October 1992Open access
Ron Rymon
Citations334
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
The Set-Enumerations (SE)tree is presented as a vehicle for representing sets and/or enumerating them in a best-first fashion and its usefulness as the basis for a unifying search-based framework for domains where minimal (maximal) elements of a power set are targeted.
Abstract
In many problem domains, solutions take the form of unordered sets. We present the Set-Enumerations (SE)-tree - a vehicle for representing sets and/or enumerating them in a best-first fashion. We demonstrate its usefulness as the basis for a unifying search-based framework for domains where minimal (maximal) elements of a power set are targeted, where minimal (maximal) partial instantiations of a set of variables are sought, or where a composite decision is not dependent on the order in which its primitive component-decisions are taken. Particular instantiations of SE-tree-based algorithms for some AI problem domains are used to demonstrate the general features of the approach. These algorithms are compared theoretically and empirically with current algorithms.
Keywords
Computer Science
Machine LearningInduction of Decision Trees
14,815 Citations1986J. R. Quinlan
This paper summarizes an approach to synthesizing decision trees that has been used in a variety of systems, and it describes one such system, ID3, in detail, which is described in detail.
Reducibility among Combinatorial Problems
10,823 Citations1972Richard M. Karp
Artificial IntelligenceA theory of diagnosis from first principles
2,897 Citations1987Raymond Reiter
The theory accommodates diagnostic reasoning in a wide variety of practical settings, including digital and analogue circuits, medicine, and database updates, and reveals close connections between diagnostic reasoning and nonmonotonic reasoning.
Society for Industrial and Applied Mathematics eBooksData Structures and Network Algorithms
2,067 Citations1983Robert E. Tarjan
This paper presents a meta-trees tree model that automates the very labor-intensive and therefore time-heavy and therefore expensive process of manually selecting trees to grow in a graph.
Sorting and Searching
1,536 Citations1973Donald E. Knuth
Machine LearningLearning Decision Lists
761 Citations1987Ronald L. Rivest
This paper introduces a new representation for Boolean functions, called decision lists, and shows that they are efficiently learnable from examples, and strictly increases the set of functions known to be polynomially learnable, in the sense of Valiant (1984).
Generating production rules from decision trees
474 Citations1987J. R. Quinlan
This paper describes a technique for transforming such trees to small sets of production rules, a common formalism for expressing knowledge in expert systems, and provides a way of combining different decision trees for the same classification domain.
Artificial IntelligenceThe computational complexity of abduction
413 Citations1991Tom Bylander, Dean Allemang +2 more
This paper focuses on one type of abduction in which the best explanation is the most plausible combination of hypotheses that explains all the data, and presents several computational complexity results demonstrating that thistype of abduction is intractable (NP-hard) in general.
Machine LearningBoolean Feature Discovery in Empirical Learning
398 Citations1990Giulia Pagallo, David Haussler
Two new methods that adaptively introduce relevant features while learning a decision tree from examples are presented, showing empirically that these methods outperform a standard decision tree algorithm for learning small random DNF functions when the examples are drawn at random from the uniform distribution.
International Joint Conference on Artificial IntelligenceDiagnosis with behavioral modes
357 Citations1989Johan de Kleer, Brian C. Williams
Artificial IntelligenceA correction to the algorithm in reiter's theory of diagnosis
309 Citations1989Russell Greiner, Barbara A. Smith +1 more
A revised algorithm is presented and a proof of its correctness is presented that shows that some diagnoses can be missed under certain conditions.
Information SciencesA formal model of diagnostic inference. I. Problem formulation and decomposition
162 Citations1985James A. Reggia, Dana Nau +1 more
A new model of diagnostic problem solving based on a generalization of the set-covering problem is introduced, which directly addresses the issue of multiple simultaneous causative disorders, and can serve as a theoretical basis for expert systems for diagnostic problems solving.
Focusing on probable diagnoses
152 Citations1991Johan de Kleer
The diverse origins of this combinatorial explosion are analyzed, and the resulting computational architecture for model-based diagnosis provides orders of magnitude performance improvement on large examples, making model- based approach practical for devices consisting of on the order of 3000 components.
IEEE Transactions on Electronic ComputersGeneralization of Consensus Theory and Application to the Minimization of Boolean Functions
148 Citations1967Pierre Tison
The consensus is extended from two to any number of terms, and it is shown that any prime implicant of a Boolean function is a generalized consensus; therefore the algorithm for the determination of the consensus relations can be used for finding theprime implicants.
Journal of Symbolic ComputationAn incremental method for generating prime implicants/implicates
129 Citations1990Alex Kean, George Tsiknis
The correctness proof and complexity analysis of the incremental method and the role of prime implicants in the CMS is mentioned and the intricacy of subsumptions in the incremental process is examined.
Lecture notes in computer scienceCharacterizing diagnoses
105 Citations1990Johan de Kleer, Alan K. Mackworth +1 more
This paper proposes a new concept, that of kernel diagnosis, which is free of the problems of minimal diagnosis, and proposes to restrict the axioms used to describe the system to ensure that the concept of minimal treatment is adequate.
Artificial intelligenceAn Improved Incremental Algorithm for Generating Prime Implicates
72 Citations1999Johan de Kleer
A method based on a simplification of Kean and Tsiknis' algorithm using an entirely different data structure to represent the data base of clauses which produces an improvement in running time on all known examples with a dramatic improvement inrunning time on larger examples.
IEEE Transactions on Information TheoryDecision tree design from a communication theory standpoint
71 Citations1988R.M. Goodman, Padhraic Smyth
A communication theory approach to decision tree design based on a top-town mutual information algorithm that is equivalent to a form of Shannon-Fano prefix coding, and several fundamental bounds relating decision-tree parameters are derived.
What should be minimized in a decision tree
69 Citations1990Usama M. Fayyad, Keki B. Irani
Results suggest that the number of leaves in a decision tree is the important measure to minimize, and can be used as a basis for a methodology for formally proving that one decision tree generation algorithm is better than another.
Elsevier eBooksAn SE-tree based Characterization of the Induction Problem
63 Citations1993Ron Rymon
This paper proposes a new structure, called SE-tree, as a more general alternative to decision trees, used in induction programs both as the basis for their search, and as a representation of their classifier solution.
Reduced complexity rule induction
63 Citations1991Sholom M. Weiss, Nitin Indurkhya
It is shown that far simpler decision rules can be found with predictive performance that exceeds those previously reported for various learning models, including neural nets and decision trees.
National Conference on Artificial IntelligenceFocusing the ATMS
55 Citations1988Kenneth D. Forbus, Johan de Kleer
A new strategy, the implied-by strategy, for using the ATMS that efficiently supports problem solving in domains which are infinite and where the inference engine must retain tight control in the course of problem solving.
International Joint Conference on Artificial IntelligenceRepresenting diagnostic knowledge for probabilistic Horn abduction
47 Citations1991David C. Poole
Three-dimensional models might be appropriate models to study the transport of various drugs and nanocarriers through the healthy and diseased BBB and the immunoarsonoliposomes can be potentially used as anticancer agents due to good tolerance of the in vitro BBB model to their toxic effect.
Computer Methods and Programs in BiomedicineA problem decomposition method for efficient diagnosis and interpretation of multiple disorders
37 Citations1991Thomas D. Wu
Experimental results indicate that symptom decomposition yields substantial increases in performance compared to existing methods for multidisorder diagnosis and offers a new type of decision-support task called symptom interpretation.
ScholarlyCommons (University of Pennsylvania)Convex spaces as an order theoretic basis for problem-solving
15 Citations1992Teow-Hin Ngair
This thesis advocates that ordered structures play an important role in many problem domains and focuses on the study of an ordered structure called a convex space, which helps answer some of the important questions concerning problem solving tasks in the fields of Artificial Intelligence and Database Systems.
Diagnosing multiple failures using knowledge of component states
12 Citations2003Lester J. Holtzblatt
A prototype, called the generic model-based diagnostic system (GMODS), has been implemented to detect and diagnose failures in launch system hardware at the Kennedy Space Center, and prunes suspects by using knowledge of the failed-state behavior of components.