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.

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.

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.

Prizes were awarded to students to encourage improved research. Michel Wermelinger, Universidade Nova de Lisboa, Portugal, was the winner of the best paper award for his work "Basic Conceptual Structure Theory," which provided a significant In "Representations Technology, Bangkok, Thailand, won Papers were presented by a number interest in the use of conceptual he Second International Conference (ICCS'94) was held at the of individuals and groups from graphs. The funds were made available University of Maryland, College several countries on the development through a grant from the American Park, Maryland, on August 16 to 20. and use of the conceptual Association for Artificial Intelligence The conference marked the tenth graph representational language. Sponsors included the University of Graph Workbench," chaired by Gerard vice-president of academic affairs, Paradigm Development Corp. in Urbana, Illinois, was the second She received her Ph.D. from the introduction, "Aristotelian and

The first session aimed to set the component being tested. The stage for the day's discussion by focusing variation in all three of these contexts on the issues surrounding the will lead to different types of and Verification of Knowledge-use of formal specification techniques The first paper, by Formal Specifications to Design Intelligence (AAAI-94) in Seattle, Lance Miller of SAIC, was entitled Verifiable Hybrid KBS" by Rose Gamble, Washington, marked the seventh This paper provided a with its specification, and (2) the The 1994 workshop was significant basis for the comparison of validation refinement of formal specifications in that there was a definitive move in and verification techniques to for their implementation. O'Leary, from the lows the possibility of constraining techniques for validating certain University of Southern California, the experts' choices to ensure that properties of KBSs. A paper by presented a paper on the relationship any new knowledge added is valid Alun Preece, Cliff Gossner, and T. between errors and size in KBSs. This and that the knowledge base structure Radhakrishnan (all from the University paper is among the first to address ensures the knowledge is of Aberdeen, Scotland) considered this important issue.

Several of the workshops have led to discourse? At what levels of the art in the field (Dale et al. 1992; generation is information processed on Natural Language Paris, Swartout, and Mann 1991; How can we generate to 24 June 1994 at the Nonantum The goal of this latest workshop multilingual texts efficiently? Inn on the seacoast in Kennebunkport, was to introduce new, cutting-edge The topics presented at the workshop Maine. Two invited speakers described subtopics such as evaluation, casual site contributed greatly to their perspectives on two areas outside explanation generation, and summarization the success of the workshop in stimulating the field that might become an occur with increasing frequency the exchange of ideas. Pustejovsky (Brandeis University) presented Different generator designers make that any individual generation his views on the richness of different choices, and the resulting project should define--in its own what can be encoded in what he calls systems are hard to compare.

Analogy has a rich history in Western civilization. Over the centuries, it has become reified in that analogical reasoning has sometimes been regarded as a fundamental cognitive process. In addition, it has become identified with a particular expressive format. The limitations of the modern view are illustrated by monster analogies, which show that analogy need not be regarded as something having a single form, format, or semantics. Analogy clearly does depend on the human ability to create and use well-defined or analytic formats for laying out propositions that express or imply meanings and perceptions. Beyond this dependence, research in cognitive science suggests that analogy relies on a number of genuinely fundamental cognitive capabilities, including semantic flexibility, the perception of resemblances and of distinctions, imagination, and metaphor. Extant symbolic models of analogical reasoning have various sorts of limitation, yet each model presents some important insights and plausible mechanisms. I argue that future efforts could be aimed at integration. This aim would include the incorporation of contextual information, the construction of semantic bases that are dynamic and knowledge rich, and the incorporation of multiple approaches to the problems of inference constraint.

Systems (QR '94) was held on 7-10 June A hot issue in cognitive modeling We received 53 submissions and is spatial and diagrammatic reasoning. The core issues of qualitative reasoning Hari Narayanan and his colleagues The eighth workshop was in Nara, included qualitative and (Advanced Research Laboratory, Japan, celebrating the community's causal modeling of the world, automated Hitachi Ltd.) exploited an architecture escape from a simple flip-flop behavior modeling, and qualitative of qualitative visual reasoning and its voyage to a more complex simulation. Interestingly, this transition attracted the attention of many participants. In fact, constructing a component-based sophistication to base qualitative several demonstrations, including model for the input-document handler reasoning on a firm ground. University) presented activity analysis, model abstraction that makes test Iwasaki and Farquhar and will be demonstrating how qualitative generation feasible for continuous held in Monterey, California.

How can an artificial agent react to a situation after performing the correct amount of thinking? My Ph.D. dissertation (Zilberstein 1993)2 presents a theoretical framework and a programming paradigm that provide an answer to this question.

We recently reported on the application of a machine-learning (ML) technique to automated flight control using a simulated F-16 combat plane (Michie and Camacho 1994). Subsequent tests of our data-induced flying model have broadly confirmed the reported results but have also identified a lack of robustness. We had underestimated the latter and now regard our report (Michie and Camacho 1994) as being, by omission, potentially misleading.