Copy Link
Add to Bookmark
Report
AIList Digest Volume 4 Issue 081
AIList Digest Saturday, 12 Apr 1986 Volume 4 : Issue 81
Today's Topics:
Bibliography - Technical Reports #4
----------------------------------------------------------------------
Date: WED, 10 JAN 84 17:02:23 CDT
From: E1AR0002%SMUVM1.BITNET@WISCVM.WISC.EDU
Subject: Technical Reports #4
%R CBM-TR-109
%T The Role of World Knowledge in Planning
%A N.S. Sridharan
%A C.F. Schmidt
%A J.L. Goodson
%D 1/82
%I Rutgers University, Department of Computer Science
%K AI09 common-sense
%X Common-sense planning demands a rich variety of world knowledge. We
have examined here the view that world knowledge can be structured to
form the interface between a hierarchy of action types and a hierarchy
of types of objects. World knowledge forming this interface includes
not only the traditional statements about preconditions and outcomes
of actions, but also the normal states of objects participating in the
actions and normative actions associated with the objects.
Common-sense plans are decomposed into goal-directed, preparation, and
the normative components. This has heuristic value and may serve to
simplify the planning algorithm. The algorithm invokes world
knowledge for goal customization, action specification, computation of
preconditions and outcomes, object selection, and for setting up
subgoals.
%R CBM-TR-110
%I Rutgers University, Department of Computer Science
%D 5/80
%T An Experimental Transformation of a Large Expert Knowledge
%A R.N. Goldberg
%A S.M. Weiss
%K internist AI01 AA01
%X An experiment is described in which a significant part of the
INTERNIST knowledge base for diagnosis in internal medicine is
translated into an EXPERT model. INTERNIST employs the largest and
broadest knowledge base of all the medical consultation systems which
have been developed in recent years. EXPERT is a general system for
designing consultation models. The translated model shows reasonable
competence in the final diagnostic classification of 431 test cases.
There are differences in the internal representation and reasoning
strategies of the two systems. However, when a knowledge base has
been encoded in a relatively uniform manner, this experiment
demonstrates the feasibility of transfer of knowledge between
large-scale expert systems.
%R CBM-TR-111
%I Rutgers University, Department of Computer Science
%D 6/80
%T A Process for Evaluating Tree-Consistency
%A J.L. Goodson
%X General knowledge about conceptual classes represented in a concept
hierarchy can provide a basis for various types of inferences about an
individual. However, the various sources of inference may not lead to
a consistent set of conclusions about the individual. This paper
provides a brief glimpse at how we represent beliefs about specific
individuals and conceptual knowledge, discusses some of the sources
of inference we have defined, and describes procedures and structures
that can be used to evaluate agreement among sources whose conclusions
can be viewed as advocating various values in a tree partition of
alternate values.
%R CBM-TR-112
%I Rutgers University, Department of Computer Science
%D 9/80
%T "A Methodology for the Construction of Natural
Language Front Ends for Medical Consultation System
%A V. Ciesielski
%D 1/82
%K AI01 AI02 AA01
%X A methodology for constructing natural language front ends for
Associational Knowledge type (AK-type) medical consultation systems is
described. AK-type consultation systems use associational knowledge
of the form "if A and B and C then conclude D with a weight of w" to
perform diagnostic reasoning. It is shown that the knowledge needed
to "understand" patient description is not the associational knowledge
in the consultation system but rather knowledge of structural
relations and the way they are expressed in surface language. The two
main structural relations involved are: (1) ATTRIBUTE of OBJECT =
VALUE. Surface forms of this relation are variants and augmentations
of the template "The X of Y is V". (2) OBJECT have-component
COMPONENT. Surface forms of this relation are variants and
augmentations of the template "The X has/contains/includes Y". This
kind of knowledge can be represented in the
Attribute-Component/Structured Object (AC/SO) package which was
developed as part of this research. The AC/SO package is given a
definition of the @u(concept) "PATIENT" for a disease area and the
corresponding lexicon.
%R DCS-TR-118
%I Rutgers University, Department of Computer Science
%D 9/82
%T Transformational Programming--Applications to Algorithms and
Systems
%A Robert Paige
%K AA08
%X Transformational programming is a nascent software development
methodology that promises to reduce programming labor, increase
program reliability, and improve program performance. Our research
centers around a prototype transformational programming system called
RAPTS (Rutgers Abstract Program Transformation System), developed
during the past several years at Laboratory for Computer Science
Research. Experiments in RAPTS with algorithm derivations are
expected to lead to pragmatic applications to algorithm design,
program development, and large system construction.
%R DCS-TR-115
%I Rutgers University, Department of Computer Science
%D 4/82
%T A Survey of Research in Strategy Acquisition
%A R. Keller
%D 7/82
%X This paper surveys literature in the area of strategy acquisition for
artificial and human problem solving systems. A unifying view of the
term "strategy" is suggested which places strategies along a continuum
from abstract to concrete. Major concerns of strategy acquisition
research are described, including (i) strategic component learning,
(ii) strategy applicability recognition, (iii) strategy customization
and (iv) strategy transformation. Various researchers' approaches to
these issues are reviewed and open problems are discussed.
%R DCS-TR-114
%I Rutgers University, Department of Computer Science
%D 3/82
%T The Control of Inferencing in Natural Language Understanding
%A Abe Lockman
%A David Klappholz
%K AI02
%X The understanding of a natural language text requires that a reader
(human or computer program) be able to resolve ambiguities at the
syntactic and lexical levels; it also requires that a reader be able
to recover that part of the meaning of a text which is over and above
the collection of meanings of its individual sentences taken in
isolation.
%X The satisfaction of this requirement involves complex inferencing from
a large database of world-knowledge. While human readers seem able to
perform this task easily, the designer of computer programs for
natural language understanding faces the serious difficulty of
algorithmically defining precisely the items of world-knowledge
required at any point in the processing, i.e., the problem of
@i[controlling inferencing]. This paper discusses the problems
involved in such control of inferencing; an approach to their solution
is presented, based on the notion of determining where each successive
sentence "fits" into the text as a whole.
%R DCS-TR-113
%I Rutgers University, Department of Computer Science
%D 4/82
%T Consistent-Labeling Problems and Their Algorithms: Part II
%A B. Nudelo
%D 10/82
%K AI14 AI10 AI03 inter-variable compatibility
%X A new parameter is introduced to characterize a type of search
problem of broad relevance in Artificial Intelligence, Operations
Research and Symbolic Logic. This paramater, which we call
inter-variable @b[compatibility] is particularly important in that
complexity analyses incorporating it are able to capture the
dependence of problem complexity on search order used by an algorithm.
Thus compatibility-based theories can provide a theoretical basis for
the extraction of heuristics for choosing good search orderings - a
long-sought goal for such problems, since it can lead to significant
savings during search. We carry out expected complexity analyses for
the traditional Backtrack algorithm as well as for two more recent
algorithms that have been found empirically to be significant
improvements, Forward Checking and word-wise Forward Checking. We
extract compatibility-based ordering-heuristics from the theory for
Forward Checking. Preliminary experimental results are presented
showing the large savings that result from their use. Similar savings
can be expected for other algorithms when heuristics taking account of
inter-variable compatibilities are used. Our compatibility-based
theories also provide a more precise way of predicting which algorithm
is best for a given problem.
%A B. Nudel
%T Understand Consistent-Labelling Problems and Their Algorithms and
Their Algorithms: Part I
%R DCS-TR-112
%D (forthcoming)
%I Rutgers University, Department of Computer Science
%K AI14 AI10 AI03
%R DCS-TR-109
%I Rutgers University, Department of Computer Science
%D 12/81
%T Equations - The "Improved Constraint Satisfaction Algorithms
using Inter-Variable Compatibilities"
%A B. Nudel
%K consistent labeling AI03
%X This report addresses the problem of improving algorithms for solving
@b(consistent-labeling) (also called @b(constraint-satisfaction)
problems. The concept of @b(compatibility) between variables in such
problems is introduced. How to obtain compatibilities analytically
and empirically is discussed, and various compatibility-based
heuristics (as well as some useful but less effective non
compatibility-based heuristics) are developed to improve a version of
the Waltz algorithm which was found best of a set of consistent-labeling
problem algorithms tested by Haralick [5]. Empirical results with
these heuristics are very encouraging, with over an order of magnitude
improvement in performance with respect to the basic algorithm on a
set of randomly generated consistent-labeling problems.
%R DCS-TR-107
%D 10/81
%I Rutgers University, Department of Computer Science
%T Note on Learning in MDS Based on Predicate Signatures
%A C.V. Srinivasan
%K AI06 AI04
%X This note illustrates a simple learning scheme in the context of two
examples. In the first example the system learns the distinguishing
features of the letters in the English alphabet, where each letter is
described in terms of a relational system of features. In the second
example the domain is a set of family relationships. In this case the
system identifies invariant properties like
"father.father=grandfather" that exist in the domain.
.sp 1
In both examples the system first creates an abstraction of the given
set of relations and uses the abstraction to identify invariant (or
distinguishing) features of the given set of relations. The
abstraction scheme is based on the concept of "predicate signatures"
that is described in the note.
.sp 1
The method is a general one. It can be used to identify large classes
of invariant (or distinguishing) features of sets of objects where
each object is described in terms of a set of relations that hold true
for the object.
%R DCS-TR-106
%I Rutgers University, Department of Computer Science
%D 10/81
%T Knowledge Representation and Problem Solving in MDS
%A C. V. Srinivasan
%K AI11
%X This work presents a new approach for using a first order theory to
generate procedures for solving goal satisfaction problems without
using general theorem proving. The core of the problem solving system
has three basic components: an inferencing mechanism based on
@u(residues), a control structure for "means-end" analysis that uses
@u(natural deduction), and a generalization scheme that is based on
the structure of statements in the domain theory itself.
.sp 1
The work represents a beginning in the development of knowledge based
systems that can generate their own problem solving programs, evolve
with experience and adapt to a changing domain theory.
%R DCS-TR-95
%D 10/80
%I Rutgers University, Department of Computer Science
%T A Mini-Max Problem
%A W.L. Steiger
%K AI03
%X Determine an algorithm, better than complete enumeration, for the
following problem: given a non-negative integer matrix, permute the
entries in each column independently so as to minimize the largest row
sum. This problem had arisen in determining an optimal scheduling
for a factory work force.
%R DCS-TR-92
%D 4/80
%T Average Case Behavior of the Alpha-Beta Tree Pruning Algorithm
%A George Shrier
%D 1/82
%I Rutgers University, Department of Computer Science
%K AI03
%R DCS-TM-15
%I Rutgers University, Department of Computer Science
%D 3/81
%T Some Experiments in Abstraction of Relational Characteristics
%A R.M. Keller
%A D.J. Nagel
%K AA09 AI01 AI04
%X Two experiments performed in knowledge-based inference are discussed in this
paper. The experiments are directed at abstracting
structural regularities and patterns inherent in a database of binary
relations. A novel graph representation to facilitate abstraction is
used in approaching some classical problem areas. This representation
is compact and powerful, and an efficient algorithm has been developed
to help control the exhaustive nature of certain types of inductive
problems.
.sp 1
One area of experimentation concerns the discovery of intensionally definable re
lations in a
family database. Another is the recognition of alphabetic characters
using directional relations defined for points on a grid. Within a
test bed system, KBLS, a scheme for computing abstractions is briefly
summarized, and implications for future extensions are discussed in
light of experimental results.
%R DCS-TM-16
%I Rutgers University, Department of Computer Science
%D 3/83
%T Solving the Plane Geometry Problem by Learning
%A Liben Xu
%K AI01 AA13 AI14
%X The top-down technique for solving a geometry problem is described.
The top-down method uses "general rules," they are obtained by
learning. This report focuses on general heuristics to obtain the
general rules for solving a geometry problem.
%R DCS-TR-89
%D 5/80
%I Rutgers University, Department of Computer Science
%T Parts I, II, III of KNOWLEDGE BASED LEARNING SYSTEMS DS + CVS = A
Proposal for Research CVS = An Intro. to the Meta-Theory & Logical
Foundations
%A D. Sandford
%K AI01 AI04
%X Current state of the art experience in designing domain specific,
intelligent, automated problem solving systems argues convincingly
that: Firstly, large amounts of what is known as domain dependent or
domain specific knowledge is crucial to achieving acceptable
efficiency in realistic problem solving situations; and secondly that
the task of implementing such systems "from scratch" is such a
formidable one that it has impeded experimental research into the
nature and role of domain specific knowledge in problem solving.
.sp 1
This project is directed towards attaining an understanding of the
processes and types of organizations required for an automated system
to be able to learn for itself the relevant domain dependent
knowledge from its experience with the domain. The research is based
on a meta-theory of knowledge based learning systems, systems that can
discover domain knowledge and use it to solve problems in a domain.
The research project will employ both experimentation with implemented
systems and theoretical analysis of systems. The goals are to shed
light on both the detailed mechanisms by which domain dependent
knowledge increases search efficiency, and to understand the type of
innate biases that an automated system needs, to be able to analyze a
domain and discover the appropriate domain knowledge. The research is
based on a meta-theory of systems that are both knowledge based
systems and learning systems.
.sp 1
The research focuses on two kinds of systems: Systems that can build
and use empirical theories of domains, and systems that use Axiomatic
theories and theorem proving. The nature of domain knowledge and ways
of using it in both these systems are investigated.
------------------------------
End of AIList Digest
********************
