title: Operations for Learning with Graphical Models

abstract:
  This paper is a multidisciplinary review of empirical, statistical learning
from a graphical model perspective. Well-known examples of graphical models
include Bayesian networks, directed graphs representing a Markov chain, and
undirected networks representing a Markov field. These graphical models are
extended to model data analysis and empirical learning using the notation of
plates. Graphical operations for simplifying and manipulating a problem are
provided including decomposition, differentiation, and the manipulation of
probability models from the exponential family. Two standard algorithm schemas
for learning are reviewed in a graphical framework: Gibbs sampling and the
expectation maximization algorithm. Using these operations and schemas, some
popular algorithms can be synthesized from their graphical specification. This
includes versions of linear regression, techniques for feed-forward networks,
and learning Gaussian and discrete Bayesian networks from data. The paper
concludes by sketching some implications for data analysis and summarizing how
some popular algorithms fall within the framework presented. The main original
contributions here are the decomposition techniques and the demonstration that
graphical models provide a framework for understanding and developing complex
learning algorithms.


title: Total-Order and Partial-Order Planning: A Comparative Analysis

abstract:
  For many years, the intuitions underlying partial-order planning were largely
taken for granted. Only in the past few years has there been renewed interest
in the fundamental principles underlying this paradigm. In this paper, we
present a rigorous comparative analysis of partial-order and total-order
planning by focusing on two specific planners that can be directly compared. We
show that there are some subtle assumptions that underly the wide-spread
intuitions regarding the supposed efficiency of partial-order planning. For
instance, the superiority of partial-order planning can depend critically upon
the search strategy and the structure of the search space. Understanding the
underlying assumptions is crucial for constructing efficient planners.


title: Solving Multiclass Learning Problems via Error-Correcting Output Codes

abstract:
  Multiclass learning problems involve finding a definition for an unknown
function f(x) whose range is a discrete set containing k &gt 2 values (i.e., k
``classes''). The definition is acquired by studying collections of training
examples of the form [x_i, f (x_i)]. Existing approaches to multiclass learning
problems include direct application of multiclass algorithms such as the
decision-tree algorithms C4.5 and CART, application of binary concept learning
algorithms to learn individual binary functions for each of the k classes, and
application of binary concept learning algorithms with distributed output
representations. This paper compares these three approaches to a new technique
in which error-correcting codes are employed as a distributed output
representation. We show that these output representations improve the
generalization performance of both C4.5 and backpropagation on a wide range of
multiclass learning tasks. We also demonstrate that this approach is robust
with respect to changes in the size of the training sample, the assignment of
distributed representations to particular classes, and the application of
overfitting avoidance techniques such as decision-tree pruning. Finally, we
show that---like the other methods---the error-correcting code technique can
provide reliable class probability estimates. Taken together, these results
demonstrate that error-correcting output codes provide a general-purpose method
for improving the performance of inductive learning programs on multiclass
problems.


title: A Domain-Independent Algorithm for Plan Adaptation

abstract:
  The paradigms of transformational planning, case-based planning, and plan
debugging all involve a process known as plan adaptation - modifying or
repairing an old plan so it solves a new problem. In this paper we provide a
domain-independent algorithm for plan adaptation, demonstrate that it is sound,
complete, and systematic, and compare it to other adaptation algorithms in the
literature. Our approach is based on a view of planning as searching a graph of
partial plans. Generative planning starts at the graph's root and moves from
node to node using plan-refinement operators. In planning by adaptation, a
library plan - an arbitrary node in the plan graph - is the starting point for
the search, and the plan-adaptation algorithm can apply both the same
refinement operators available to a generative planner and can also retract
constraints and steps from the plan. Our algorithm's completeness ensures that
the adaptation algorithm will eventually search the entire graph and its
systematicity ensures that it will do so without redundantly searching any
parts of the graph.


title:
Truncating Temporal Differences: On the Efficient Implementation of
  TD(lambda) for Reinforcement Learning

abstract:
  Temporal difference (TD) methods constitute a class of methods for learning
predictions in multi-step prediction problems, parameterized by a recency
factor lambda. Currently the most important application of these methods is to
temporal credit assignment in reinforcement learning. Well known reinforcement
learning algorithms, such as AHC or Q-learning, may be viewed as instances of
TD learning. This paper examines the issues of the efficient and general
implementation of TD(lambda) for arbitrary lambda, for use with reinforcement
learning algorithms optimizing the discounted sum of rewards. The traditional
approach, based on eligibility traces, is argued to suffer from both
inefficiency and lack of generality. The TTD (Truncated Temporal Differences)
procedure is proposed as an alternative, that indeed only approximates
TD(lambda), but requires very little computation per action and can be used
with arbitrary function representation methods. The idea from which it is
derived is fairly simple and not new, but probably unexplored so far.
Encouraging experimental results are presented, suggesting that using lambda
&gt 0 with the TTD procedure allows one to obtain a significant learning
speedup at essentially the same cost as usual TD(0) learning.


title: On the Informativeness of the DNA Promoter Sequences Domain Theory

abstract:
  The DNA promoter sequences domain theory and database have become popular for
testing systems that integrate empirical and analytical learning. This note
reports a simple change and reinterpretation of the domain theory in terms of
M-of-N concepts, involving no learning, that results in an accuracy of 93.4% on
the 106 items of the database. Moreover, an exhaustive search of the space of
M-of-N domain theory interpretations indicates that the expected accuracy of a
randomly chosen interpretation is 76.5%, and that a maximum accuracy of 97.2%
is achieved in 12 cases. This demonstrates the informativeness of the domain
theory, without the complications of understanding the interactions between
various learning algorithms and the theory. In addition, our results help
characterize the difficulty of learning using the DNA promoters theory.


title:
Cost-Sensitive Classification: Empirical Evaluation of a Hybrid Genetic
  Decision Tree Induction Algorithm

abstract:
  This paper introduces ICET, a new algorithm for cost-sensitive
classification. ICET uses a genetic algorithm to evolve a population of biases
for a decision tree induction algorithm. The fitness function of the genetic
algorithm is the average cost of classification when using the decision tree,
including both the costs of tests (features, measurements) and the costs of
classification errors. ICET is compared here with three other algorithms for
cost-sensitive classification - EG2, CS-ID3, and IDX - and also with C4.5,
which classifies without regard to cost. The five algorithms are evaluated
empirically on five real-world medical datasets. Three sets of experiments are
performed. The first set examines the baseline performance of the five
algorithms on the five datasets and establishes that ICET performs
significantly better than its competitors. The second set tests the robustness
of ICET under a variety of conditions and shows that ICET maintains its
advantage. The third set looks at ICET's search in bias space and discovers a
way to improve the search.


title:
Rerepresenting and Restructuring Domain Theories: A Constructive
  Induction Approach

abstract:
  Theory revision integrates inductive learning and background knowledge by
combining training examples with a coarse domain theory to produce a more
accurate theory. There are two challenges that theory revision and other
theory-guided systems face. First, a representation language appropriate for
the initial theory may be inappropriate for an improved theory. While the
original representation may concisely express the initial theory, a more
accurate theory forced to use that same representation may be bulky,
cumbersome, and difficult to reach. Second, a theory structure suitable for a
coarse domain theory may be insufficient for a fine-tuned theory. Systems that
produce only small, local changes to a theory have limited value for
accomplishing complex structural alterations that may be required.
Consequently, advanced theory-guided learning systems require flexible
representation and flexible structure. An analysis of various theory revision
systems and theory-guided learning systems reveals specific strengths and
weaknesses in terms of these two desired properties. Designed to capture the
underlying qualities of each system, a new system uses theory-guided
constructive induction. Experiments in three domains show improvement over
previous theory-guided systems. This leads to a study of the behavior,
limitations, and potential of theory-guided constructive induction.


title: Using Pivot Consistency to Decompose and Solve Functional CSPs

abstract:
  Many studies have been carried out in order to increase the search efficiency
of constraint satisfaction problems; among them, some make use of structural
properties of the constraint network; others take into account semantic
properties of the constraints, generally assuming that all the constraints
possess the given property. In this paper, we propose a new decomposition
method benefiting from both semantic properties of functional constraints (not
bijective constraints) and structural properties of the network; furthermore,
not all the constraints need to be functional. We show that under some
conditions, the existence of solutions can be guaranteed. We first characterize
a particular subset of the variables, which we name a root set. We then
introduce pivot consistency, a new local consistency which is a weak form of
path consistency and can be achieved in O(n^2d^2) complexity (instead of
O(n^3d^3) for path consistency), and we present associated properties; in
particular, we show that any consistent instantiation of the root set can be
linearly extended to a solution, which leads to the presentation of the
aforementioned new method for solving by decomposing functional CSPs.


title: Adaptive Load Balancing: A Study in Multi-Agent Learning

abstract:
  We study the process of multi-agent reinforcement learning in the context of
load balancing in a distributed system, without use of either central
coordination or explicit communication. We first define a precise framework in
which to study adaptive load balancing, important features of which are its
stochastic nature and the purely local information available to individual
agents. Given this framework, we show illuminating results on the interplay
between basic adaptive behavior parameters and their effect on system
efficiency. We then investigate the properties of adaptive load balancing in
heterogeneous populations, and address the issue of exploration vs.
exploitation in that context. Finally, we show that naive use of communication
may not improve, and might even harm system efficiency.


title: Provably Bounded-Optimal Agents

abstract:
  Since its inception, artificial intelligence has relied upon a theoretical
foundation centered around perfect rationality as the desired property of
intelligent systems. We argue, as others have done, that this foundation is
inadequate because it imposes fundamentally unsatisfiable requirements. As a
result, there has arisen a wide gap between theory and practice in AI,
hindering progress in the field. We propose instead a property called bounded
optimality. Roughly speaking, an agent is bounded-optimal if its program is a
solution to the constrained optimization problem presented by its architecture
and the task environment. We show how to construct agents with this property
for a simple class of machine architectures in a broad class of real-time
environments. We illustrate these results using a simple model of an automated
mail sorting facility. We also define a weaker property, asymptotic bounded
optimality (ABO), that generalizes the notion of optimality in classical
complexity theory. We then construct universal ABO programs, i.e., programs
that are ABO no matter what real-time constraints are applied. Universal ABO
programs can be used as building blocks for more complex systems. We conclude
with a discussion of the prospects for bounded optimality as a theoretical
basis for AI, and relate it to similar trends in philosophy, economics, and
game theory.


title: Pac-Learning Recursive Logic Programs: Efficient Algorithms

abstract:
  We present algorithms that learn certain classes of function-free recursive
logic programs in polynomial time from equivalence queries. In particular, we
show that a single k-ary recursive constant-depth determinate clause is
learnable. Two-clause programs consisting of one learnable recursive clause and
one constant-depth determinate non-recursive clause are also learnable, if an
additional ``basecase'' oracle is assumed. These results immediately imply the
pac-learnability of these classes. Although these classes of learnable
recursive programs are very constrained, it is shown in a companion paper that
they are maximally general, in that generalizing either class in any natural
way leads to a computationally difficult learning problem. Thus, taken together
with its companion paper, this paper establishes a boundary of efficient
learnability for recursive logic programs.


title: Pac-learning Recursive Logic Programs: Negative Results

abstract:
  In a companion paper it was shown that the class of constant-depth
determinate k-ary recursive clauses is efficiently learnable. In this paper we
present negative results showing that any natural generalization of this class
is hard to learn in Valiant's model of pac-learnability. In particular, we show
that the following program classes are cryptographically hard to learn:
programs with an unbounded number of constant-depth linear recursive clauses;
programs with one constant-depth determinate clause containing an unbounded
number of recursive calls; and programs with one linear recursive clause of
constant locality. These results immediately imply the non-learnability of any
more general class of programs. We also show that learning a constant-depth
determinate program with either two linear recursive clauses or one linear
recursive clause and one non-recursive clause is as hard as learning boolean
DNF. Together with positive results from the companion paper, these negative
results establish a boundary of efficient learnability for recursive
function-free clauses.


title: FLECS: Planning with a Flexible Commitment Strategy

abstract:
  There has been evidence that least-commitment planners can efficiently handle
planning problems that involve difficult goal interactions. This evidence has
led to the common belief that delayed-commitment is the "best" possible
planning strategy. However, we recently found evidence that eager-commitment
planners can handle a variety of planning problems more efficiently, in
particular those with difficult operator choices. Resigned to the futility of
trying to find a universally successful planning strategy, we devised a planner
that can be used to study which domains and problems are best for which
planning strategies. In this article we introduce this new planning algorithm,
FLECS, which uses a FLExible Commitment Strategy with respect to plan-step
orderings. It is able to use any strategy from delayed-commitment to
eager-commitment. The combination of delayed and eager operator-ordering
commitments allows FLECS to take advantage of the benefits of explicitly using
a simulated execution state and reasoning about planning constraints. FLECS can
vary its commitment strategy across different problems and domains, and also
during the course of a single planning problem. FLECS represents a novel
contribution to planning in that it explicitly provides the choice of which
commitment strategy to use while planning. FLECS provides a framework to
investigate the mapping from planning domains and problems to efficient
planning strategies.


title:
Induction of First-Order Decision Lists: Results on Learning the Past
  Tense of English Verbs

abstract:
  This paper presents a method for inducing logic programs from examples that
learns a new class of concepts called first-order decision lists, defined as
ordered lists of clauses each ending in a cut. The method, called FOIDL, is
based on FOIL (Quinlan, 1990) but employs intensional background knowledge and
avoids the need for explicit negative examples. It is particularly useful for
problems that involve rules with specific exceptions, such as learning the
past-tense of English verbs, a task widely studied in the context of the
symbolic/connectionist debate. FOIDL is able to learn concise, accurate
programs for this problem from significantly fewer examples than previous
methods (both connectionist and symbolic).


title:
Building and Refining Abstract Planning Cases by Change of
  Representation Language

abstract:
  ion is one of the most promising approaches to improve the performance of
problem solvers. In several domains abstraction by dropping sentences of a
domain description -- as used in most hierarchical planners -- has proven
useful. In this paper we present examples which illustrate significant
drawbacks of abstraction by dropping sentences. To overcome these drawbacks, we
propose a more general view of abstraction involving the change of
representation language. We have developed a new abstraction methodology and a
related sound and complete learning algorithm that allows the complete change
of representation language of planning cases from concrete to abstract.
However, to achieve a powerful change of the representation language, the
abstract language itself as well as rules which describe admissible ways of
abstracting states must be provided in the domain model. This new abstraction
approach is the core of Paris (Plan Abstraction and Refinement in an Integrated
System), a system in which abstract planning cases are automatically learned
from given concrete cases. An empirical study in the domain of process planning
in mechanical engineering shows significant advantages of the proposed
reasoning from abstract cases over classical hierarchical planning.


title: Using Qualitative Hypotheses to Identify Inaccurate Data

abstract:
  Identifying inaccurate data has long been regarded as a significant and
difficult problem in AI. In this paper, we present a new method for identifying
inaccurate data on the basis of qualitative correlations among related data.
First, we introduce the definitions of related data and qualitative
correlations among related data. Then we put forward a new concept called
support coefficient function (SCF). SCF can be used to extract, represent, and
calculate qualitative correlations among related data within a dataset. We
propose an approach to determining dynamic shift intervals of inaccurate data,
and an approach to calculating possibility of identifying inaccurate data,
respectively. Both of the approaches are based on SCF. Finally we present an
algorithm for identifying inaccurate data by using qualitative correlations
among related data as confirmatory or disconfirmatory evidence. We have
developed a practical system for interpreting infrared spectra by applying the
method, and have fully tested the system against several hundred real spectra.
The experimental results show that the method is significantly better than the
conventional methods used in many similar systems.


title: An Integrated Framework for Learning and Reasoning

abstract:
  Learning and reasoning are both aspects of what is considered to be
intelligence. Their studies within AI have been separated historically,
learning being the topic of machine learning and neural networks, and reasoning
falling under classical (or symbolic) AI. However, learning and reasoning are
in many ways interdependent. This paper discusses the nature of some of these
interdependencies and proposes a general framework called FLARE, that combines
inductive learning using prior knowledge together with reasoning in a
propositional setting. Several examples that test the framework are presented,
including classical induction, many important reasoning protocols and two
simple expert systems.


title: Diffusion of Context and Credit Information in Markovian Models

abstract:
  This paper studies the problem of ergodicity of transition probability
matrices in Markovian models, such as hidden Markov models (HMMs), and how it
makes very difficult the task of learning to represent long-term context for
sequential data. This phenomenon hurts the forward propagation of long-term
context information, as well as learning a hidden state representation to
represent long-term context, which depends on propagating credit information
backwards in time. Using results from Markov chain theory, we show that this
problem of diffusion of context and credit is reduced when the transition
probabilities approach 0 or 1, i.e., the transition probability matrices are
sparse and the model essentially deterministic. The results found in this paper
apply to learning approaches based on continuous optimization, such as gradient
descent and the Baum-Welch algorithm.


title: Improving Connectionist Energy Minimization

abstract:
  Symmetric networks designed for energy minimization such as Boltzman machines
and Hopfield nets are frequently investigated for use in optimization,
constraint satisfaction and approximation of NP-hard problems. Nevertheless,
finding a global solution (i.e., a global minimum for the energy function) is
not guaranteed and even a local solution may take an exponential number of
steps. We propose an improvement to the standard local activation function used
for such networks. The improved algorithm guarantees that a global minimum is
found in linear time for tree-like subnetworks. The algorithm, called activate,
is uniform and does not assume that the network is tree-like. It can identify
tree-like subnetworks even in cyclic topologies (arbitrary networks) and avoid
local minima along these trees. For acyclic networks, the algorithm is
guaranteed to converge to a global minimum from any initial state of the system
(self-stabilization) and remains correct under various types of schedulers. On
the negative side, we show that in the presence of cycles, no uniform algorithm
exists that guarantees optimality even under a sequential asynchronous
scheduler. An asynchronous scheduler can activate only one unit at a time while
a synchronous scheduler can activate any number of units in a single time step.
In addition, no uniform algorithm exists to optimize even acyclic networks when
the scheduler is synchronous. Finally, we show how the algorithm can be
improved using the cycle-cutset scheme. The general algorithm, called
activate-with-cutset, improves over activate and has some performance
guarantees that are related to the size of the network's cycle-cutset.


title:
Learning Membership Functions in a Function-Based Object Recognition
  System

abstract:
  Functionality-based recognition systems recognize objects at the category
level by reasoning about how well the objects support the expected function.
Such systems naturally associate a ``measure of goodness'' or ``membership
value'' with a recognized object. This measure of goodness is the result of
combining individual measures, or membership values, from potentially many
primitive evaluations of different properties of the object's shape. A
membership function is used to compute the membership value when evaluating a
primitive of a particular physical property of an object. In previous versions
of a recognition system known as Gruff, the membership function for each of the
primitive evaluations was hand-crafted by the system designer. In this paper,
we provide a learning component for the Gruff system, called Omlet, that
automatically learns membership functions given a set of example objects
labeled with their desired category measure. The learning algorithm is
generally applicable to any problem in which low-level membership values are
combined through an and-or tree structure to give a final overall membership
value.


title: Flexibly Instructable Agents

abstract:
  This paper presents an approach to learning from situated, interactive
tutorial instruction within an ongoing agent. Tutorial instruction is a
flexible (and thus powerful) paradigm for teaching tasks because it allows an
instructor to communicate whatever types of knowledge an agent might need in
whatever situations might arise. To support this flexibility, however, the
agent must be able to learn multiple kinds of knowledge from a broad range of
instructional interactions. Our approach, called situated explanation, achieves
such learning through a combination of analytic and inductive techniques. It
combines a form of explanation-based learning that is situated for each
instruction with a full suite of contextually guided responses to incomplete
explanations. The approach is implemented in an agent called Instructo-Soar
that learns hierarchies of new tasks and other domain knowledge from
interactive natural language instructions. Instructo-Soar meets three key
requirements of flexible instructability that distinguish it from previous
systems: (1) it can take known or unknown commands at any instruction point;
(2) it can handle instructions that apply to either its current situation or to
a hypothetical situation specified in language (as in, for instance,
conditional instructions); and (3) it can learn, from instructions, each class
of knowledge it uses to perform tasks.


title: Set Theory for Verification: II. Induction and Recursion

abstract:
  A theory of recursive definitions has been mechanized in Isabelle's
Zermelo-Fraenkel (ZF) set theory. The objective is to support the formalization
of particular recursive definitions for use in verification, semantics proofs
and other computational reasoning. Inductively defined sets are expressed as
least fixedpoints, applying the Knaster-Tarski Theorem over a suitable set.
Recursive functions are defined by well-founded recursion and its derivatives,
such as transfinite recursion. Recursive data structures are expressed by
applying the Knaster-Tarski Theorem to a set, such as V[omega], that is closed
under Cartesian product and disjoint sum. Worked examples include the
transitive closure of a relation, lists, variable-branching trees and mutually
recursive trees and forests. The Schr\"oder-Bernstein Theorem and the soundness
of propositional logic are proved in Isabelle sessions.


title: A Concrete Final Coalgebra Theorem for ZF Set Theory

abstract:
  A special final coalgebra theorem, in the style of Aczel's, is proved within
standard Zermelo-Fraenkel set theory. Aczel's Anti-Foundation Axiom is replaced
by a variant definition of function that admits non-well-founded constructions.
Variant ordered pairs and tuples, of possibly infinite length, are special
cases of variant functions. Analogues of Aczel's Solution and Substitution
Lemmas are proved in the style of Rutten and Turi. The approach is less general
than Aczel's, but the treatment of non-well-founded objects is simple and
concrete. The final coalgebra of a functor is its greatest fixedpoint. The
theory is intended for machine implementation and a simple case of it is
already implemented using the theorem prover Isabelle.


title: OPUS: An Efficient Admissible Algorithm for Unordered Search

abstract:
  OPUS is a branch and bound search algorithm that enables efficient admissible
search through spaces for which the order of search operator application is not
significant. The algorithm's search efficiency is demonstrated with respect to
very large machine learning search spaces. The use of admissible search is of
potential value to the machine learning community as it means that the exact
learning biases to be employed for complex learning tasks can be precisely
specified and manipulated. OPUS also has potential for application in other
areas of artificial intelligence, notably, truth maintenance.


title:
Vision-Based Road Detection in Automotive Systems: A Real-Time
  Expectation-Driven Approach

abstract:
  The main aim of this work is the development of a vision-based road detection
system fast enough to cope with the difficult real-time constraints imposed by
moving vehicle applications. The hardware platform, a special-purpose massively
parallel system, has been chosen to minimize system production and operational
costs. This paper presents a novel approach to expectation-driven low-level
image segmentation, which can be mapped naturally onto mesh-connected massively
parallel SIMD architectures capable of handling hierarchical data structures.
The input image is assumed to contain a distorted version of a given template;
a multiresolution stretching process is used to reshape the original template
in accordance with the acquired image content, minimizing a potential function.
The distorted template is the process output.


title: Generalization of Clauses under Implication

abstract:
  In the area of inductive learning, generalization is a main operation, and
the usual definition of induction is based on logical implication. Recently
there has been a rising interest in clausal representation of knowledge in
machine learning. Almost all inductive learning systems that perform
generalization of clauses use the relation theta-subsumption instead of
implication. The main reason is that there is a well-known and simple technique
to compute least general generalizations under theta-subsumption, but not under
implication. However generalization under theta-subsumption is inappropriate
for learning recursive clauses, which is a crucial problem since recursion is
the basic program structure of logic programs. We note that implication between
clauses is undecidable, and we therefore introduce a stronger form of
implication, called T-implication, which is decidable between clauses. We show
that for every finite set of clauses there exists a least general
generalization under T-implication. We describe a technique to reduce
generalizations under implication of a clause to generalizations under
theta-subsumption of what we call an expansion of the original clause. Moreover
we show that for every non-tautological clause there exists a T-complete
expansion, which means that every generalization under T-implication of the
clause is reduced to a generalization under theta-subsumption of the expansion.


title: Decision-Theoretic Foundations for Causal Reasoning

abstract:
  We present a definition of cause and effect in terms of decision-theoretic
primitives and thereby provide a principled foundation for causal reasoning.
Our definition departs from the traditional view of causation in that causal
assertions may vary with the set of decisions available. We argue that this
approach provides added clarity to the notion of cause. Also in this paper, we
examine the encoding of causal relationships in directed acyclic graphs. We
describe a special class of influence diagrams, those in canonical form, and
show its relationship to Pearl's representation of cause and effect. Finally,
we show how canonical form facilitates counterfactual reasoning.


title: Translating between Horn Representations and their Characteristic Models

abstract:
  Characteristic models are an alternative, model based, representation for
Horn expressions. It has been shown that these two representations are
incomparable and each has its advantages over the other. It is therefore
natural to ask what is the cost of translating, back and forth, between these
representations. Interestingly, the same translation questions arise in
database theory, where it has applications to the design of relational
databases. This paper studies the computational complexity of these problems.
Our main result is that the two translation problems are equivalent under
polynomial reductions, and that they are equivalent to the corresponding
decision problem. Namely, translating is equivalent to deciding whether a given
set of models is the set of characteristic models for a given Horn expression.
We also relate these problems to the hypergraph transversal problem, a well
known problem which is related to other applications in AI and for which no
polynomial time algorithm is known. It is shown that in general our translation
problems are at least as hard as the hypergraph transversal problem, and in a
special case they are equivalent to it.


title: Statistical Feature Combination for the Evaluation of Game Positions

abstract:
  This article describes an application of three well-known statistical methods
in the field of game-tree search: using a large number of classified Othello
positions, feature weights for evaluation functions with a
game-phase-independent meaning are estimated by means of logistic regression,
Fisher's linear discriminant, and the quadratic discriminant function for
normally distributed features. Thereafter, the playing strengths are compared
by means of tournaments between the resulting versions of a world-class Othello
program. In this application, logistic regression - which is used here for the
first time in the context of game playing - leads to better results than the
other approaches.


title: Rule-based Machine Learning Methods for Functional Prediction

abstract:
  We describe a machine learning method for predicting the value of a
real-valued function, given the values of multiple input variables. The method
induces solutions from samples in the form of ordered disjunctive normal form
(DNF) decision rules. A central objective of the method and representation is
the induction of compact, easily interpretable solutions. This rule-based
decision model can be extended to search efficiently for similar cases prior to
approximating function values. Experimental results on real-world data
demonstrate that the new techniques are competitive with existing machine
learning and statistical methods and can sometimes yield superior regression
performance.


title:
The Design and Experimental Analysis of Algorithms for Temporal
  Reasoning

abstract:
  Many applications -- from planning and scheduling to problems in molecular
biology -- rely heavily on a temporal reasoning component. In this paper, we
discuss the design and empirical analysis of algorithms for a temporal
reasoning system based on Allen's influential interval-based framework for
representing temporal information. At the core of the system are algorithms for
determining whether the temporal information is consistent, and, if so, finding
one or more scenarios that are consistent with the temporal information. Two
important algorithms for these tasks are a path consistency algorithm and a
backtracking algorithm. For the path consistency algorithm, we develop
techniques that can result in up to a ten-fold speedup over an already highly
optimized implementation. For the backtracking algorithm, we develop variable
and value ordering heuristics that are shown empirically to dramatically
improve the performance of the algorithm. As well, we show that a previously
suggested reformulation of the backtracking search problem can reduce the time
and space requirements of the backtracking search. Taken together, the
techniques we develop allow a temporal reasoning component to solve problems
that are of practical size.


title:
Well-Founded Semantics for Extended Logic Programs with Dynamic
  Preferences

abstract:
  The paper describes an extension of well-founded semantics for logic programs
with two types of negation. In this extension information about preferences
between rules can be expressed in the logical language and derived dynamically.
This is achieved by using a reserved predicate symbol and a naming technique.
Conflicts among rules are resolved whenever possible on the basis of derived
preference information. The well-founded conclusions of prioritized logic
programs can be computed in polynomial time. A legal reasoning example
illustrates the usefulness of the approach.


title: Logarithmic-Time Updates and Queries in Probabilistic Networks

abstract:
  Traditional databases commonly support efficient query and update procedures
that operate in time which is sublinear in the size of the database. Our goal
in this paper is to take a first step toward dynamic reasoning in probabilistic
databases with comparable efficiency. We propose a dynamic data structure that
supports efficient algorithms for updating and querying singly connected
Bayesian networks. In the conventional algorithm, new evidence is absorbed in
O(1) time and queries are processed in time O(N), where N is the size of the
network. We propose an algorithm which, after a preprocessing phase, allows us
to answer queries in time O(log N) at the expense of O(log N) time per evidence
absorption. The usefulness of sub-linear processing time manifests itself in
applications requiring (near) real-time response over large probabilistic
databases. We briefly discuss a potential application of dynamic probabilistic
reasoning in computational biology.


title: Quantum Computing and Phase Transitions in Combinatorial Search

abstract:
  We introduce an algorithm for combinatorial search on quantum computers that
is capable of significantly concentrating amplitude into solutions for some NP
search problems, on average. This is done by exploiting the same aspects of
problem structure as used by classical backtrack methods to avoid unproductive
search choices. This quantum algorithm is much more likely to find solutions
than the simple direct use of quantum parallelism. Furthermore, empirical
evaluation on small problems shows this quantum algorithm displays the same
phase transition behavior, and at the same location, as seen in many previously
studied classical search methods. Specifically, difficult problem instances are
concentrated near the abrupt change from underconstrained to overconstrained
problems.


title: Mean Field Theory for Sigmoid Belief Networks

abstract:
  We develop a mean field theory for sigmoid belief networks based on ideas
from statistical mechanics. Our mean field theory provides a tractable
approximation to the true probability distribution in these networks; it also
yields a lower bound on the likelihood of evidence. We demonstrate the utility
of this framework on a benchmark problem in statistical pattern
recognition---the classification of handwritten digits.


title: Improved Use of Continuous Attributes in C4.5

abstract:
  A reported weakness of C4.5 in domains with continuous attributes is
addressed by modifying the formation and evaluation of tests on continuous
attributes. An MDL-inspired penalty is applied to such tests, eliminating some
of them from consideration and altering the relative desirability of all tests.
Empirical trials show that the modifications lead to smaller decision trees
with higher predictive accuracies. Results also confirm that a new version of
C4.5 incorporating these changes is superior to recent approaches that use
global discretization and that construct small trees with multi-interval
splits.


title: Active Learning with Statistical Models

abstract:
  For many types of machine learning algorithms, one can compute the
statistically `optimal' way to select training data. In this paper, we review
how optimal data selection techniques have been used with feedforward neural
networks. We then show how the same principles may be used to select data for
two alternative, statistically-based learning architectures: mixtures of
Gaussians and locally weighted regression. While the techniques for neural
networks are computationally expensive and approximate, the techniques for
mixtures of Gaussians and locally weighted regression are both efficient and
accurate. Empirically, we observe that the optimality criterion sharply
decreases the number of training examples the learner needs in order to achieve
good performance.


title: A Divergence Critic for Inductive Proof

abstract:
  Inductive theorem provers often diverge. This paper describes a simple
critic, a computer program which monitors the construction of inductive proofs
attempting to identify diverging proof attempts. Divergence is recognized by
means of a ``difference matching'' procedure. The critic then proposes lemmas
and generalizations which ``ripple'' these differences away so that the proof
can go through without divergence. The critic enables the theorem prover Spike
to prove many theorems completely automatically from the definitions alone.


title: Practical Methods for Proving Termination of General Logic Programs

abstract:
  Termination of logic programs with negated body atoms (here called general
logic programs) is an important topic. One reason is that many computational
mechanisms used to process negated atoms, like Clark's negation as failure and
Chan's constructive negation, are based on termination conditions. This paper
introduces a methodology for proving termination of general logic programs
w.r.t. the Prolog selection rule. The idea is to distinguish parts of the
program depending on whether or not their termination depends on the selection
rule. To this end, the notions of low-, weakly up-, and up-acceptable program
are introduced. We use these notions to develop a methodology for proving
termination of general logic programs, and show how interesting problems in
non-monotonic reasoning can be formalized and implemented by means of
terminating general logic programs.


title: Iterative Optimization and Simplification of Hierarchical Clusterings

abstract:
  Clustering is often used for discovering structure in data. Clustering
systems differ in the objective function used to evaluate clustering quality
and the control strategy used to search the space of clusterings. Ideally, the
search strategy should consistently construct clusterings of high quality, but
be computationally inexpensive as well. In general, we cannot have it both
ways, but we can partition the search so that a system inexpensively constructs
a `tentative' clustering for initial examination, followed by iterative
optimization, which continues to search in background for improved clusterings.
Given this motivation, we evaluate an inexpensive strategy for creating initial
clusterings, coupled with several control strategies for iterative
optimization, each of which repeatedly modifies an initial clustering in search
of a better one. One of these methods appears novel as an iterative
optimization strategy in clustering contexts. Once a clustering has been
constructed it is judged by analysts -- often according to task-specific
criteria. Several authors have abstracted these criteria and posited a generic
performance task akin to pattern completion, where the error rate over
completed patterns is used to `externally' judge clustering utility. Given this
performance task, we adapt resampling-based pruning strategies used by
supervised learning systems to the task of simplifying hierarchical
clusterings, thus promising to ease post-clustering analysis. Finally, we
propose a number of objective functions, based on attribute-selection measures
for decision-tree induction, that might perform well on the error rate and
simplicity dimensions.


title: Further Experimental Evidence against the Utility of Occam's Razor

abstract:
  This paper presents new experimental evidence against the utility of Occam's
razor. A~systematic procedure is presented for post-processing decision trees
produced by C4.5. This procedure was derived by rejecting Occam's razor and
instead attending to the assumption that similar objects are likely to belong
to the same class. It increases a decision tree's complexity without altering
the performance of that tree on the training data from which it is inferred.
The resulting more complex decision trees are demonstrated to have, on average,
for a variety of common learning tasks, higher predictive accuracy than the
less complex original decision trees. This result raises considerable doubt
about the utility of Occam's razor as it is commonly applied in modern machine
learning.


title: Least Generalizations and Greatest Specializations of Sets of Clauses

abstract:
  The main operations in Inductive Logic Programming (ILP) are generalization
and specialization, which only make sense in a generality order. In ILP, the
three most important generality orders are subsumption, implication and
implication relative to background knowledge. The two languages used most often
are languages of clauses and languages of only Horn clauses. This gives a total
of six different ordered languages. In this paper, we give a systematic
treatment of the existence or non-existence of least generalizations and
greatest specializations of finite sets of clauses in each of these six ordered
sets. We survey results already obtained by others and also contribute some
answers of our own. Our main new results are, firstly, the existence of a
computable least generalization under implication of every finite set of
clauses containing at least one non-tautologous function-free clause (among
other, not necessarily function-free clauses). Secondly, we show that such a
least generalization need not exist under relative implication, not even if
both the set that is to be generalized and the background knowledge are
function-free. Thirdly, we give a complete discussion of existence and
non-existence of greatest specializations in each of the six ordered languages.


title: Reinforcement Learning: A Survey

abstract:
  This paper surveys the field of reinforcement learning from a
computer-science perspective. It is written to be accessible to researchers
familiar with machine learning. Both the historical basis of the field and a
broad selection of current work are summarized. Reinforcement learning is the
problem faced by an agent that learns behavior through trial-and-error
interactions with a dynamic environment. The work described here has a
resemblance to work in psychology, but differs considerably in the details and
in the use of the word ``reinforcement.'' The paper discusses central issues of
reinforcement learning, including trading off exploration and exploitation,
establishing the foundations of the field via Markov decision theory, learning
from delayed reinforcement, constructing empirical models to accelerate
learning, making use of generalization and hierarchy, and coping with hidden
state. It concludes with a survey of some implemented systems and an assessment
of the practical utility of current methods for reinforcement learning.


title:
Adaptive Problem-solving for Large-scale Scheduling Problems: A Case
  Study

abstract:
  Although most scheduling problems are NP-hard, domain specific techniques
perform well in practice but are quite expensive to construct. In adaptive
problem-solving solving, domain specific knowledge is acquired automatically
for a general problem solver with a flexible control architecture. In this
approach, a learning system explores a space of possible heuristic methods for
one well-suited to the eccentricities of the given domain and problem
distribution. In this article, we discuss an application of the approach to
scheduling satellite communications. Using problem distributions based on
actual mission requirements, our approach identifies strategies that not only
decrease the amount of CPU time required to produce schedules, but also
increase the percentage of problems that are solvable within computational
resource limitations.


title: A Formal Framework for Speedup Learning from Problems and Solutions

abstract:
  Speedup learning seeks to improve the computational efficiency of problem
solving with experience. In this paper, we develop a formal framework for
learning efficient problem solving from random problems and their solutions. We
apply this framework to two different representations of learned knowledge,
namely control rules and macro-operators, and prove theorems that identify
sufficient conditions for learning in each representation. Our proofs are
constructive in that they are accompanied with learning algorithms. Our
framework captures both empirical and explanation-based speedup learning in a
unified fashion. We illustrate our framework with implementations in two
domains: symbolic integration and Eight Puzzle. This work integrates many
strands of experimental and theoretical work in machine learning, including
empirical learning of control rules, macro-operator learning, Explanation-Based
Learning (EBL), and Probably Approximately Correct (PAC) Learning.


title: 2Planning for Contingencies: A Decision-based Approach

abstract:
  A fundamental assumption made by classical AI planners is that there is no
uncertainty in the world: the planner has full knowledge of the conditions
under which the plan will be executed and the outcome of every action is fully
predictable. These planners cannot therefore construct contingency plans, i.e.,
plans in which different actions are performed in different circumstances. In
this paper we discuss some issues that arise in the representation and
construction of contingency plans and describe Cassandra, a partial-order
contingency planner. Cassandra uses explicit decision-steps that enable the
agent executing the plan to decide which plan branch to follow. The
decision-steps in a plan result in subgoals to acquire knowledge, which are
planned for in the same way as any other subgoals. Cassandra thus distinguishes
the process of gathering information from the process of making decisions. The
explicit representation of decisions in Cassandra allows a coherent approach to
the problems of contingent planning, and provides a solid base for extensions
such as the use of different decision-making procedures.


title: A Principled Approach Towards Symbolic Geometric Constraint Satisfaction

abstract:
  An important problem in geometric reasoning is to find the configuration of a
collection of geometric bodies so as to satisfy a set of given constraints.
Recently, it has been suggested that this problem can be solved efficiently by
symbolically reasoning about geometry. This approach, called degrees of freedom
analysis, employs a set of specialized routines called plan fragments that
specify how to change the configuration of a set of bodies to satisfy a new
constraint while preserving existing constraints. A potential drawback, which
limits the scalability of this approach, is concerned with the difficulty of
writing plan fragments. In this paper we address this limitation by showing how
these plan fragments can be automatically synthesized using first principles
about geometric bodies, actions, and topology.


title: On Partially Controlled Multi-Agent Systems

abstract:
  Motivated by the control theoretic distinction between controllable and
uncontrollable events, we distinguish between two types of agents within a
multi-agent system: controllable agents, which are directly controlled by the
system's designer, and uncontrollable agents, which are not under the
designer's direct control. We refer to such systems as partially controlled
multi-agent systems, and we investigate how one might influence the behavior of
the uncontrolled agents through appropriate design of the controlled agents. In
particular, we wish to understand which problems are naturally described in
these terms, what methods can be applied to influence the uncontrollable
agents, the effectiveness of such methods, and whether similar methods work
across different domains. Using a game-theoretic framework, this paper studies
the design of partially controlled multi-agent systems in two contexts: in one
context, the uncontrollable agents are expected utility maximizers, while in
the other they are reinforcement learners. We suggest different techniques for
controlling agents' behavior in each domain, assess their success, and examine
their relationship.


title: Spatial Aggregation: Theory and Applications

abstract:
  Visual thinking plays an important role in scientific reasoning. Based on the
research in automating diverse reasoning tasks about dynamical systems,
nonlinear controllers, kinematic mechanisms, and fluid motion, we have
identified a style of visual thinking, imagistic reasoning. Imagistic reasoning
organizes computations around image-like, analogue representations so that
perceptual and symbolic operations can be brought to bear to infer structure
and behavior. Programs incorporating imagistic reasoning have been shown to
perform at an expert level in domains that defy current analytic or numerical
methods. We have developed a computational paradigm, spatial aggregation, to
unify the description of a class of imagistic problem solvers. A program
written in this paradigm has the following properties. It takes a continuous
field and optional objective functions as input, and produces high-level
descriptions of structure, behavior, or control actions. It computes a
multi-layer of intermediate representations, called spatial aggregates, by
forming equivalence classes and adjacency relations. It employs a small set of
generic operators such as aggregation, classification, and localization to
perform bidirectional mapping between the information-rich field and
successively more abstract spatial aggregates. It uses a data structure, the
neighborhood graph, as a common interface to modularize computations. To
illustrate our theory, we describe the computational structure of three
implemented problem solvers -- KAM, MAPS, and HIPAIR --- in terms of the
spatial aggregation generic operators by mixing and matching a library of
commonly used routines.


title: A Hierarchy of Tractable Subsets for Computing Stable Models

abstract:
  Finding the stable models of a knowledge base is a significant computational
problem in artificial intelligence. This task is at the computational heart of
truth maintenance systems, autoepistemic logic, and default logic.
Unfortunately, it is NP-hard. In this paper we present a hierarchy of classes
of knowledge bases, Omega_1,Omega_2,..., with the following properties: first,
Omega_1 is the class of all stratified knowledge bases; second, if a knowledge
base Pi is in Omega_k, then Pi has at most k stable models, and all of them may
be found in time O(lnk), where l is the length of the knowledge base and n the
number of atoms in Pi; third, for an arbitrary knowledge base Pi, we can find
the minimum k such that Pi belongs to Omega_k in time polynomial in the size of
Pi; and, last, where K is the class of all knowledge bases, it is the case that
union{i=1 to infty} Omega_i = K, that is, every knowledge base belongs to some
class in the hierarchy.


title: Shellsort with three increments

abstract:
  A perturbation technique can be used to simplify and sharpen A. C. Yao's
theorems about the behavior of shellsort with increments $(h,g,1)$. In
particular, when $h=\Theta(n^{7/15})$ and $g=\Theta(h^{1/5})$, the average
running time is $O(n^{23/15})$. The proof involves interesting properties of
the inversions in random permutations that have been $h$-sorted and $g$-sorted.


title:
Accelerating Partial-Order Planners: Some Techniques for Effective
  Search Control and Pruning

abstract:
  We propose some domain-independent techniques for bringing well-founded
partial-order planners closer to practicality. The first two techniques are
aimed at improving search control while keeping overhead costs low. One is
based on a simple adjustment to the default A* heuristic used by UCPOP to
select plans for refinement. The other is based on preferring ``zero
commitment'' (forced) plan refinements whenever possible, and using LIFO
prioritization otherwise. A more radical technique is the use of operator
parameter domains to prune search. These domains are initially computed from
the definitions of the operators and the initial and goal conditions, using a
polynomial-time algorithm that propagates sets of constants through the
operator graph, starting in the initial conditions. During planning, parameter
domains can be used to prune nonviable operator instances and to remove
spurious clobbering threats. In experiments based on modifications of UCPOP,
our improved plan and goal selection strategies gave speedups by factors
ranging from 5 to more than 1000 for a variety of problems that are nontrivial
for the unmodified version. Crucially, the hardest problems gave the greatest
improvements. The pruning technique based on parameter domains often gave
speedups by an order of magnitude or more for difficult problems, both with the
default UCPOP search strategy and with our improved strategy. The Lisp code for
our techniques and for the test problems is provided in on-line appendices.


title: Cue Phrase Classification Using Machine Learning

abstract:
  Cue phrases may be used in a discourse sense to explicitly signal discourse
structure, but also in a sentential sense to convey semantic rather than
structural information. Correctly classifying cue phrases as discourse or
sentential is critical in natural language processing systems that exploit
discourse structure, e.g., for performing tasks such as anaphora resolution and
plan recognition. This paper explores the use of machine learning for
classifying cue phrases as discourse or sentential. Two machine learning
programs (Cgrendel and C4.5) are used to induce classification models from sets
of pre-classified cue phrases and their features in text and speech. Machine
learning is shown to be an effective technique for not only automating the
generation of classification models, but also for improving upon previous
results. When compared to manually derived classification models already in the
literature, the learned models often perform with higher accuracy and contain
new linguistic insights into the data. In addition, the ability to
automatically construct classification models makes it easier to comparatively
analyze the utility of alternative feature representations of the data.
Finally, the ease of retraining makes the learning approach more scalable and
flexible than manual methods.


title: Mechanisms for Automated Negotiation in State Oriented Domains

abstract:
  This paper lays part of the groundwork for a domain theory of negotiation,
that is, a way of classifying interactions so that it is clear, given a domain,
which negotiation mechanisms and strategies are appropriate. We define State
Oriented Domains, a general category of interaction. Necessary and sufficient
conditions for cooperation are outlined. We use the notion of worth in an
altered definition of utility, thus enabling agreements in a wider class of
joint-goal reachable situations. An approach is offered for conflict
resolution, and it is shown that even in a conflict situation, partial
cooperative steps can be taken by interacting agents (that is, agents in
fundamental conflict might still agree to cooperate up to a certain point). A
Unified Negotiation Protocol (UNP) is developed that can be used in all types
of encounters. It is shown that in certain borderline cooperative situations, a
partial cooperative agreement (i.e., one that does not achieve all agents'
goals) might be preferred by all agents, even though there exists a rational
agreement that would achieve all their goals. Finally, we analyze cases where
agents have incomplete information on the goals and worth of other agents.
First we consider the case where agents' goals are private information, and we
analyze what goal declaration strategies the agents might adopt to increase
their utility. Then, we consider the situation where the agents' goals (and
therefore stand-alone costs) are common knowledge, but the worth they attach to
their goals is private information. We introduce two mechanisms, one 'strict',
the other 'tolerant', and analyze their affects on the stability and efficiency
of negotiation outcomes.


title: Learning First-Order Definitions of Functions

abstract:
  First-order learning involves finding a clause-form definition of a relation
from examples of the relation and relevant background information. In this
paper, a particular first-order learning system is modified to customize it for
finding definitions of functional relations. This restriction leads to faster
learning times and, in some cases, to definitions that have higher predictive
accuracy. Other first-order learning systems might benefit from similar
specialization.


title: MUSE CSP: An Extension to the Constraint Satisfaction Problem

abstract:
  This paper describes an extension to the constraint satisfaction problem
(CSP) called MUSE CSP (MUltiply SEgmented Constraint Satisfaction Problem).
This extension is especially useful for those problems which segment into
multiple sets of partially shared variables. Such problems arise naturally in
signal processing applications including computer vision, speech processing,
and handwriting recognition. For these applications, it is often difficult to
segment the data in only one way given the low-level information utilized by
the segmentation algorithms. MUSE CSP can be used to compactly represent
several similar instances of the constraint satisfaction problem. If multiple
instances of a CSP have some common variables which have the same domains and
constraints, then they can be combined into a single instance of a MUSE CSP,
reducing the work required to apply the constraints. We introduce the concepts
of MUSE node consistency, MUSE arc consistency, and MUSE path consistency. We
then demonstrate how MUSE CSP can be used to compactly represent lexically
ambiguous sentences and the multiple sentence hypotheses that are often
generated by speech recognition algorithms so that grammar constraints can be
used to provide parses for all syntactically correct sentences. Algorithms for
MUSE arc and path consistency are provided. Finally, we discuss how to create a
MUSE CSP from a set of CSPs which are labeled to indicate when the same
variable is shared by more than a single CSP.


title: Exploiting Causal Independence in Bayesian Network Inference

abstract:
  A new method is proposed for exploiting causal independencies in exact
Bayesian network inference. A Bayesian network can be viewed as representing a
factorization of a joint probability into the multiplication of a set of
conditional probabilities. We present a notion of causal independence that
enables one to further factorize the conditional probabilities into a
combination of even smaller factors and consequently obtain a finer-grain
factorization of the joint probability. The new formulation of causal
independence lets us specify the conditional probability of a variable given
its parents in terms of an associative and commutative operator, such as
``or'', ``sum'' or ``max'', on the contribution of each parent. We start with a
simple algorithm VE for Bayesian network inference that, given evidence and a
query variable, uses the factorization to find the posterior distribution of
the query. We show how this algorithm can be extended to exploit causal
independence. Empirical studies, based on the CPCS networks for medical
diagnosis, show that this method is more efficient than previous methods and
allows for inference in larger networks than previous algorithms.


title:
Quantitative Results Comparing Three Intelligent Interfaces for
  Information Capture: A Case Study Adding Name Information into an Electronic
  Personal Organizer

abstract:
  Efficiently entering information into a computer is key to enjoying the
benefits of computing. This paper describes three intelligent user interfaces:
handwriting recognition, adaptive menus, and predictive fillin. In the context
of adding a personUs name and address to an electronic organizer, tests show
handwriting recognition is slower than typing on an on-screen, soft keyboard,
while adaptive menus and predictive fillin can be twice as fast. This paper
also presents strategies for applying these three interfaces to other
information collection domains.


title: Characterizations of Decomposable Dependency Models

abstract:
  Decomposable dependency models possess a number of interesting and useful
properties. This paper presents new characterizations of decomposable models in
terms of independence relationships, which are obtained by adding a single
axiom to the well-known set characterizing dependency models that are
isomorphic to undirected graphs. We also briefly discuss a potential
application of our results to the problem of learning graphical models from
data.


title: Mechanizing Set Theory: Cardinal Arithmetic and the Axiom of Choice.

abstract:
  Fairly deep results of Zermelo-Frenkel (ZF) set theory have been mechanized
using the proof assistant Isabelle. The results concern cardinal arithmetic and
the Axiom of Choice (AC). A key result about cardinal multiplication is K*K =
K, where K is any infinite cardinal. Proving this result required developing
theories of orders, order-isomorphisms, order types, ordinal arithmetic,
cardinals, etc.; this covers most of Kunen, Set Theory, Chapter I. Furthermore,
we have proved the equivalence of 7 formulations of the Well-ordering Theorem
and 20 formulations of AC; this covers the first two chapters of Rubin and
Rubin, Equivalents of the Axiom of Choice, and involves highly technical
material. The definitions used in the proofs are largely faithful in style to
the original mathematics.


title: Improved Heterogeneous Distance Functions

abstract:
  Instance-based learning techniques typically handle continuous and linear
input values well, but often do not handle nominal input attributes
appropriately. The Value Difference Metric (VDM) was designed to find
reasonable distance values between nominal attribute values, but it largely
ignores continuous attributes, requiring discretization to map continuous
values into nominal values. This paper proposes three new heterogeneous
distance functions, called the Heterogeneous Value Difference Metric (HVDM),
the Interpolated Value Difference Metric (IVDM), and the Windowed Value
Difference Metric (WVDM). These new distance functions are designed to handle
applications with nominal attributes, continuous attributes, or both. In
experiments on 48 applications the new distance metrics achieve higher
classification accuracy on average than three previous distance functions on
those datasets that have both nominal and continuous attributes.


title:
SCREEN: Learning a Flat Syntactic and Semantic Spoken Language Analysis
  Using Artificial Neural Networks

abstract:
  Previous approaches of analyzing spontaneously spoken language often have
been based on encoding syntactic and semantic knowledge manually and
symbolically. While there has been some progress using statistical or
connectionist language models, many current spoken- language systems still use
a relatively brittle, hand-coded symbolic grammar or symbolic semantic
component. In contrast, we describe a so-called screening approach for learning
robust processing of spontaneously spoken language. A screening approach is a
flat analysis which uses shallow sequences of category representations for
analyzing an utterance at various syntactic, semantic and dialog levels. Rather
than using a deeply structured symbolic analysis, we use a flat connectionist
analysis. This screening approach aims at supporting speech and language
processing by using (1) data-driven learning and (2) robustness of
connectionist networks. In order to test this approach, we have developed the
SCREEN system which is based on this new robust, learned and flat analysis. In
this paper, we focus on a detailed description of SCREEN's architecture, the
flat syntactic and semantic analysis, the interaction with a speech recognizer,
and a detailed evaluation analysis of the robustness under the influence of
noisy or incomplete input. The main result of this paper is that flat
representations allow more robust processing of spontaneous spoken language
than deeply structured representations. In particular, we show how the
fault-tolerance and learning capability of connectionist networks can support a
flat analysis for providing more robust spoken-language processing within an
overall hybrid symbolic/connectionist framework.


title: A Uniform Framework for Concept Definitions in Description Logics

abstract:
  Most modern formalisms used in Databases and Artificial Intelligence for
describing an application domain are based on the notions of class (or concept)
and relationship among classes. One interesting feature of such formalisms is
the possibility of defining a class, i.e., providing a set of properties that
precisely characterize the instances of the class. Many recent articles point
out that there are several ways of assigning a meaning to a class definition
containing some sort of recursion. In this paper, we argue that, instead of
choosing a single style of semantics, we achieve better results by adopting a
formalism that allows for different semantics to coexist. We demonstrate the
feasibility of our argument, by presenting a knowledge representation
formalism, the description logic muALCQ, with the above characteristics. In
addition to the constructs for conjunction, disjunction, negation, quantifiers,
and qualified number restrictions, muALCQ includes special fixpoint constructs
to express (suitably interpreted) recursive definitions. These constructs
enable the usual frame-based descriptions to be combined with definitions of
recursive data structures such as directed acyclic graphs, lists, streams, etc.
We establish several properties of muALCQ, including the decidability and the
computational complexity of reasoning, by formulating a correspondence with a
particular modal logic of programs called the modal mu-calculus.


title: Lifeworld Analysis

abstract:
  We argue that the analysis of agent/environment interactions should be
extended to include the conventions and invariants maintained by agents
throughout their activity. We refer to this thicker notion of environment as a
lifeworld and present a partial set of formal tools for describing structures
of lifeworlds and the ways in which they computationally simplify activity. As
one specific example, we apply the tools to the analysis of the Toast system
and show how versions of the system with very different control structures in
fact implement a common control structure together with different conventions
for encoding task state in the positions or states of objects in the
environment.


title:
Query DAGs: A Practical Paradigm for Implementing Belief-Network
  Inference

abstract:
  We describe a new paradigm for implementing inference in belief networks,
which consists of two steps: (1) compiling a belief network into an arithmetic
expression called a Query DAG (Q-DAG); and (2) answering queries using a simple
evaluation algorithm. Each node of a Q-DAG represents a numeric operation, a
number, or a symbol for evidence. Each leaf node of a Q-DAG represents the
answer to a network query, that is, the probability of some event of interest.
It appears that Q-DAGs can be generated using any of the standard algorithms
for exact inference in belief networks (we show how they can be generated using
clustering and conditioning algorithms). The time and space complexity of a
Q-DAG generation algorithm is no worse than the time complexity of the
inference algorithm on which it is based. The complexity of a Q-DAG evaluation
algorithm is linear in the size of the Q-DAG, and such inference amounts to a
standard evaluation of the arithmetic expression it represents. The intended
value of Q-DAGs is in reducing the software and hardware resources required to
utilize belief networks in on-line, real-world applications. The proposed
framework also facilitates the development of on-line inference on different
software and hardware platforms due to the simplicity of the Q-DAG evaluation
algorithm. Interestingly enough, Q-DAGs were found to serve other purposes:
simple techniques for reducing Q-DAGs tend to subsume relatively complex
optimization techniques for belief-network inference, such as network-pruning
and computation-caching.


title:
Connectionist Theory Refinement: Genetically Searching the Space of
  Network Topologies

abstract:
  An algorithm that learns from a set of examples should ideally be able to
exploit the available resources of (a) abundant computing power and (b)
domain-specific knowledge to improve its ability to generalize. Connectionist
theory-refinement systems, which use background knowledge to select a neural
network's topology and initial weights, have proven to be effective at
exploiting domain-specific knowledge; however, most do not exploit available
computing power. This weakness occurs because they lack the ability to refine
the topology of the neural networks they produce, thereby limiting
generalization, especially when given impoverished domain theories. We present
the REGENT algorithm which uses (a) domain-specific knowledge to help create an
initial population of knowledge-based neural networks and (b) genetic operators
of crossover and mutation (specifically designed for knowledge-based networks)
to continually search for better network topologies. Experiments on three
real-world domains indicate that our new algorithm is able to significantly
increase generalization compared to a standard connectionist theory-refinement
system, as well as our previous algorithm for growing knowledge-based networks.


title: Flaw Selection Strategies for Partial-Order Planning

abstract:
  Several recent studies have compared the relative efficiency of alternative
flaw selection strategies for partial-order causal link (POCL) planning. We
review this literature, and present new experimental results that generalize
the earlier work and explain some of the discrepancies in it. In particular, we
describe the Least-Cost Flaw Repair (LCFR) strategy developed and analyzed by
Joslin and Pollack (1994), and compare it with other strategies, including
Gerevini and Schubert's (1996) ZLIFO strategy. LCFR and ZLIFO make very
different, and apparently conflicting claims about the most effective way to
reduce search-space size in POCL planning. We resolve this conflict, arguing
that much of the benefit that Gerevini and Schubert ascribe to the LIFO
component of their ZLIFO strategy is better attributed to other causes. We show
that for many problems, a strategy that combines least-cost flaw selection with
the delay of separable threats will be effective in reducing search-space size,
and will do so without excessive computational overhead. Although such a
strategy thus provides a good default, we also show that certain domain
characteristics may reduce its effectiveness.


title: A Complete Classification of Tractability in RCC-5

abstract:
  We investigate the computational properties of the spatial algebra RCC-5
which is a restricted version of the RCC framework for spatial reasoning. The
satisfiability problem for RCC-5 is known to be NP-complete but not much is
known about its approximately four billion subclasses. We provide a complete
classification of satisfiability for all these subclasses into polynomial and
NP-complete respectively. In the process, we identify all maximal tractable
subalgebras which are four in total.


title:
A New Look at the Easy-Hard-Easy Pattern of Combinatorial Search
  Difficulty

abstract:
  The easy-hard-easy pattern in the difficulty of combinatorial search problems
as constraints are added has been explained as due to a competition between the
decrease in number of solutions and increased pruning. We test the generality
of this explanation by examining one of its predictions: if the number of
solutions is held fixed by the choice of problems, then increased pruning
should lead to a monotonic decrease in search cost. Instead, we find the
easy-hard-easy pattern in median search cost even when the number of solutions
is held constant, for some search methods. This generalizes previous
observations of this pattern and shows that the existing theory does not
explain the full range of the peak in search cost. In these cases the pattern
appears to be due to changes in the size of the minimal unsolvable subproblems,
rather than changing numbers of solutions.


title: Eight Maximal Tractable Subclasses of Allen's Algebra with Metric Time

abstract:
  This paper combines two important directions of research in temporal
resoning: that of finding maximal tractable subclasses of Allen's interval
algebra, and that of reasoning with metric temporal information. Eight new
maximal tractable subclasses of Allen's interval algebra are presented, some of
them subsuming previously reported tractable algebras. The algebras allow for
metric temporal constraints on interval starting or ending points, using the
recent framework of Horn DLRs. Two of the algebras can express the notion of
sequentiality between intervals, being the first such algebras admitting both
qualitative and metric time.


title:
Defining Relative Likelihood in Partially-Ordered Preferential
  Structures

abstract:
  Starting with a likelihood or preference order on worlds, we extend it to a
likelihood ordering on sets of worlds in a natural way, and examine the
resulting logic. Lewis earlier considered such a notion of relative likelihood
in the context of studying counterfactuals, but he assumed a total preference
order on worlds. Complications arise when examining partial orders that are not
present for total orders. There are subtleties involving the exact approach to
lifting the order on worlds to an order on sets of worlds. In addition, the
axiomatization of the logic of relative likelihood in the case of partial
orders gives insight into the connection between relative likelihood and
default reasoning.


title: Towards Flexible Teamwork

abstract:
  Many AI researchers are today striving to build agent teams for complex,
dynamic multi-agent domains, with intended applications in arenas such as
education, training, entertainment, information integration, and collective
robotics. Unfortunately, uncertainties in these complex, dynamic domains
obstruct coherent teamwork. In particular, team members often encounter
differing, incomplete, and possibly inconsistent views of their environment.
Furthermore, team members can unexpectedly fail in fulfilling responsibilities
or discover unexpected opportunities. Highly flexible coordination and
communication is key in addressing such uncertainties. Simply fitting
individual agents with precomputed coordination plans will not do, for their
inflexibility can cause severe failures in teamwork, and their
domain-specificity hinders reusability. Our central hypothesis is that the key
to such flexibility and reusability is providing agents with general models of
teamwork. Agents exploit such models to autonomously reason about coordination
and communication, providing requisite flexibility. Furthermore, the models
enable reuse across domains, both saving implementation effort and enforcing
consistency. This article presents one general, implemented model of teamwork,
called STEAM. The basic building block of teamwork in STEAM is joint intentions
(Cohen & Levesque, 1991b); teamwork in STEAM is based on agents' building up a
(partial) hierarchy of joint intentions (this hierarchy is seen to parallel
Grosz & Kraus's partial SharedPlans, 1996). Furthermore, in STEAM, team members
monitor the team's and individual members' performance, reorganizing the team
as necessary. Finally, decision-theoretic communication selectivity in STEAM
ensures reduction in communication overheads of teamwork, with appropriate
sensitivity to the environmental conditions. This article describes STEAM's
application in three different complex domains, and presents detailed empirical
results.


title: Identifying Hierarchical Structure in Sequences: A linear-time algorithm

abstract:
  SEQUITUR is an algorithm that infers a hierarchical structure from a sequence
of discrete symbols by replacing repeated phrases with a grammatical rule that
generates the phrase, and continuing this process recursively. The result is a
hierarchical representation of the original sequence, which offers insights
into its lexical structure. The algorithm is driven by two constraints that
reduce the size of the grammar, and produce structure as a by-product. SEQUITUR
breaks new ground by operating incrementally. Moreover, the method's simple
structure permits a proof that it operates in space and time that is linear in
the size of the input. Our implementation can process 50,000 symbols per second
and has been applied to an extensive range of real world sequences.


title: Analysis of Three-Dimensional Protein Images

abstract:
  A fundamental goal of research in molecular biology is to understand protein
structure. Protein crystallography is currently the most successful method for
determining the three-dimensional (3D) conformation of a protein, yet it
remains labor intensive and relies on an expert's ability to derive and
evaluate a protein scene model. In this paper, the problem of protein structure
determination is formulated as an exercise in scene analysis. A computational
methodology is presented in which a 3D image of a protein is segmented into a
graph of critical points. Bayesian and certainty factor approaches are
described and used to analyze critical point graphs and identify meaningful
substructures, such as alpha-helices and beta-sheets. Results of applying the
methodologies to protein images at low and medium resolution are reported. The
research is related to approaches to representation, segmentation and
classification in vision, as well as to top-down approaches to protein
structure prediction.


title:
Storing and Indexing Plan Derivations through Explanation-based Analysis
  of Retrieval Failures

abstract:
  Case-Based Planning (CBP) provides a way of scaling up domain-independent
planning to solve large problems in complex domains. It replaces the detailed
and lengthy search for a solution with the retrieval and adaptation of previous
planning experiences. In general, CBP has been demonstrated to improve
performance over generative (from-scratch) planning. However, the performance
improvements it provides are dependent on adequate judgements as to problem
similarity. In particular, although CBP may substantially reduce planning
effort overall, it is subject to a mis-retrieval problem. The success of CBP
depends on these retrieval errors being relatively rare. This paper describes
the design and implementation of a replay framework for the case-based planner
DERSNLP+EBL. DERSNLP+EBL extends current CBP methodology by incorporating
explanation-based learning techniques that allow it to explain and learn from
the retrieval failures it encounters. These techniques are used to refine
judgements about case similarity in response to feedback when a wrong decision
has been made. The same failure analysis is used in building the case library,
through the addition of repairing cases. Large problems are split and stored as
single goal subproblems. Multi-goal problems are stored only when these smaller
cases fail to be merged into a full solution. An empirical evaluation of this
approach demonstrates the advantage of learning from experienced retrieval
failure.


title:
A Model Approximation Scheme for Planning in Partially Observable
  Stochastic Domains

abstract:
  Partially observable Markov decision processes (POMDPs) are a natural model
for planning problems where effects of actions are nondeterministic and the
state of the world is not completely observable. It is difficult to solve
POMDPs exactly. This paper proposes a new approximation scheme. The basic idea
is to transform a POMDP into another one where additional information is
provided by an oracle. The oracle informs the planning agent that the current
state of the world is in a certain region. The transformed POMDP is
consequently said to be region observable. It is easier to solve than the
original POMDP. We propose to solve the transformed POMDP and use its optimal
policy to construct an approximate policy for the original POMDP. By
controlling the amount of additional information that the oracle provides, it
is possible to find a proper tradeoff between computational time and
approximation quality. In terms of algorithmic contributions, we study in
details how to exploit region observability in solving the transformed POMDP.
To facilitate the study, we also propose a new exact algorithm for general
POMDPs. The algorithm is conceptually simple and yet is significantly more
efficient than all previous exact algorithms.


title: Dynamic Non-Bayesian Decision Making

abstract:
  The model of a non-Bayesian agent who faces a repeated game with incomplete
information against Nature is an appropriate tool for modeling general
agent-environment interactions. In such a model the environment state
(controlled by Nature) may change arbitrarily, and the feedback/reward function
is initially unknown. The agent is not Bayesian, that is he does not form a
prior probability neither on the state selection strategy of Nature, nor on his
reward function. A policy for the agent is a function which assigns an action
to every history of observations and actions. Two basic feedback structures are
considered. In one of them -- the perfect monitoring case -- the agent is able
to observe the previous environment state as part of his feedback, while in the
other -- the imperfect monitoring case -- all that is available to the agent is
the reward obtained. Both of these settings refer to partially observable
processes, where the current environment state is unknown. Our main result
refers to the competitive ratio criterion in the perfect monitoring case. We
prove the existence of an efficient stochastic policy that ensures that the
competitive ratio is obtained at almost all stages with an arbitrarily high
probability, where efficiency is measured in terms of rate of convergence. It
is further shown that such an optimal policy does not exist in the imperfect
monitoring case. Moreover, it is proved that in the perfect monitoring case
there does not exist a deterministic policy that satisfies our long run
optimality criterion. In addition, we discuss the maxmin criterion and prove
that a deterministic efficient optimal strategy does exist in the imperfect
monitoring case under this criterion. Finally we show that our approach to
long-run optimality can be viewed as qualitative, which distinguishes it from
previous work in this area.


title: Mechanizing Coinduction and Corecursion in Higher-order Logic

abstract:
  A theory of recursive and corecursive definitions has been developed in
higher-order logic (HOL) and mechanized using Isabelle. Least fixedpoints
express inductive data types such as strict lists; greatest fixedpoints express
coinductive data types, such as lazy lists. Well-founded recursion expresses
recursive functions over inductive data types; corecursion expresses functions
that yield elements of coinductive data types. The theory rests on a
traditional formalization of infinite trees. The theory is intended for use in
specification and verification. It supports reasoning about a wide range of
computable functions, but it does not formalize their operational semantics and
can express noncomputable functions also. The theory is illustrated using
finite and infinite lists. Corecursion expresses functions over infinite lists;
coinduction reasons about such functions.


title: Generic Automatic Proof Tools

abstract:
  This book chapter establishes connections between the interactive proof tool
Isabelle and classical tableau and resolution technology. Isabelle's classical
reasoner is described and demonstrated by an extended case study: the
Church-Rosser theorem for combinators. Compared with other interactive theorem
provers, Isabelle's classical reasoner achieves a high degree of automation.


title: When Gravity Fails: Local Search Topology

abstract:
  Local search algorithms for combinatorial search problems frequently
encounter a sequence of states in which it is impossible to improve the value
of the objective function; moves through these regions, called plateau moves,
dominate the time spent in local search. We analyze and characterize plateaus
for three different classes of randomly generated Boolean Satisfiability
problems. We identify several interesting features of plateaus that impact the
performance of local search algorithms. We show that local minima tend to be
small but occasionally may be very large. We also show that local minima can be
escaped without unsatisfying a large number of clauses, but that systematically
searching for an escape route may be computationally expensive if the local
minimum is large. We show that plateaus with exits, called benches, tend to be
much larger than minima, and that some benches have very few exit states which
local search can use to escape. We show that the solutions (i.e., global
minima) of randomly generated problem instances form clusters, which behave
similarly to local minima. We revisit several enhancements of local search
algorithms and explain their performance in light of our results. Finally we
discuss strategies for creating the next generation of local search algorithms.


title: Bidirectional Heuristic Search Reconsidered

abstract:
  The assessment of bidirectional heuristic search has been incorrect since it
was first published more than a quarter of a century ago. For quite a long
time, this search strategy did not achieve the expected results, and there was
a major misunderstanding about the reasons behind it. Although there is still
wide-spread belief that bidirectional heuristic search is afflicted by the
problem of search frontiers passing each other, we demonstrate that this
conjecture is wrong. Based on this finding, we present both a new generic
approach to bidirectional heuristic search and a new approach to dynamically
improving heuristic values that is feasible in bidirectional search only. These
approaches are put into perspective with both the traditional and more recently
proposed approaches in order to facilitate a better overall understanding.
Empirical results of experiments with our new approaches show that
bidirectional heuristic search can be performed very efficiently and also with
limited memory. These results suggest that bidirectional heuristic search
appears to be better for solving certain difficult problems than corresponding
unidirectional search. This provides some evidence for the usefulness of a
search strategy that was long neglected. In summary, we show that bidirectional
heuristic search is viable and consequently propose that it be reconsidered.


title: Incremental Recompilation of Knowledge

abstract:
  Approximating a general formula from above and below by Horn formulas (its
Horn envelope and Horn core, respectively) was proposed by Selman and Kautz
(1991, 1996) as a form of ``knowledge compilation,'' supporting rapid
approximate reasoning; on the negative side, this scheme is static in that it
supports no updates, and has certain complexity drawbacks pointed out by
Kavvadias, Papadimitriou and Sideri (1993). On the other hand, the many
frameworks and schemes proposed in the literature for theory update and
revision are plagued by serious complexity-theoretic impediments, even in the
Horn case, as was pointed out by Eiter and Gottlob (1992), and is further
demonstrated in the present paper. More fundamentally, these schemes are not
inductive, in that they may lose in a single update any positive properties of
the represented sets of formulas (small size, Horn structure, etc.). In this
paper we propose a new scheme, incremental recompilation, which combines Horn
approximation and model-based updates; this scheme is inductive and very
efficient, free of the problems facing its constituents. A set of formulas is
represented by an upper and lower Horn approximation. To update, we replace the
upper Horn formula by the Horn envelope of its minimum-change update, and
similarly the lower one by the Horn core of its update; the key fact which
enables this scheme is that Horn envelopes and cores are easy to compute when
the underlying formula is the result of a minimum-change update of a Horn
formula by a clause. We conjecture that efficient algorithms are possible for
more complex updates.


title: Monotonicity and Persistence in Preferential Logics

abstract:
  An important characteristic of many logics for Artificial Intelligence is
their nonmonotonicity. This means that adding a formula to the premises can
invalidate some of the consequences. There may, however, exist formulae that
can always be safely added to the premises without destroying any of the
consequences: we say they respect monotonicity. Also, there may be formulae
that, when they are a consequence, can not be invalidated when adding any
formula to the premises: we call them conservative. We study these two classes
of formulae for preferential logics, and show that they are closely linked to
the formulae whose truth-value is preserved along the (preferential) ordering.
We will consider some preferential logics for illustration, and prove syntactic
characterization results for them. The results in this paper may improve the
efficiency of theorem provers for preferential logics.


title: Linear probing and graphs

abstract:
  Mallows and Riordan showed in 1968 that labeled trees with a small number of
inversions are related to labeled graphs that are connected and sparse. Wright
enumerated sparse connected graphs in 1977, and Kreweras related the inversions
of trees to the so-called ``parking problem'' in 1980. A~combination of these
three results leads to a surprisingly simple analysis of the behavior of
hashing by linear probing, including higher moments of the cost of successful
search.


title: Synthesizing Customized Planners from Specifications

abstract:
  Existing plan synthesis approaches in artificial intelligence fall into two
categories -- domain independent and domain dependent. The domain independent
approaches are applicable across a variety of domains, but may not be very
efficient in any one given domain. The domain dependent approaches need to be
(re)designed for each domain separately, but can be very efficient in the
domain for which they are designed. One enticing alternative to these
approaches is to automatically synthesize domain independent planners given the
knowledge about the domain and the theory of planning. In this paper, we
investigate the feasibility of using existing automated software synthesis
tools to support such synthesis. Specifically, we describe an architecture
called CLAY in which the Kestrel Interactive Development System (KIDS) is used
to derive a domain-customized planner through a semi-automatic combination of a
declarative theory of planning, and the declarative control knowledge specific
to a given domain, to semi-automatically combine them to derive
domain-customized planners. We discuss what it means to write a declarative
theory of planning and control knowledge for KIDS, and illustrate our approach
by generating a class of domain-specific planners using state space
refinements. Our experiments show that the synthesized planners can outperform
classical refinement planners (implemented as instantiations of UCP,
Kambhampati & Srivastava, 1995), using the same control knowledge. We will
contrast the costs and benefits of the synthesis approach with conventional
methods for customizing domain independent planners.


title:
Cached Sufficient Statistics for Efficient Machine Learning with Large
  Datasets

abstract:
  This paper introduces new algorithms and data structures for quick counting
for machine learning datasets. We focus on the counting task of constructing
contingency tables, but our approach is also applicable to counting the number
of records in a dataset that match conjunctive queries. Subject to certain
assumptions, the costs of these operations can be shown to be independent of
the number of records in the dataset and loglinear in the number of non-zero
entries in the contingency table. We provide a very sparse data structure, the
ADtree, to minimize memory use. We provide analytical worst-case bounds for
this structure for several models of data distribution. We empirically
demonstrate that tractably-sized data structures can be produced for large
real-world datasets by (a) using a sparse tree structure that never allocates
memory for counts of zero, (b) never allocating memory for counts that can be
deduced from other counts, and (c) not bothering to expand the tree fully near
its leaves. We show how the ADtree can be used to accelerate Bayes net
structure finding algorithms, rule learning algorithms, and feature selection
algorithms, and we provide a number of empirical results comparing ADtree
methods against traditional direct counting approaches. We also discuss the
possible uses of ADtrees in other machine learning methods, and discuss the
merits of ADtrees in comparison with alternative representations such as
kd-trees, R-trees and Frequent Sets.