bluuebunny/crossref_metadata_2025 huggingface dataset:
What is a heuristic?
Authors: Romanycia Marc H. J. , Pelletier Francis Jeffry
Published: April 2007

From the mid‐1950's to the present the notion of a heuristic has played a crucial role in the AI researchers’ descriptions of their work. What has not been generally noticed is that different researchers have often applied the term to rather different aspects of their programs. Things that would be called a heuristic by one researcher would not be so called by others. This is because many heuristics embody a variety of different features, and the various researchers have emphasized different ones of these features as being essential to being a heuristic. This paper steps back from any particular research program and investigates the question of what things, historically, have been thought to be central to the notion of a heuristic and which ones conflict with others. After analyzing the previous definitions and examining current usage of the term, a synthesizing definition is provided. The hope is that with this broader account of ‘heuristic’ in hand, researchers can benefit more fully from the insights of others, even if those insights are couched in a somewhat alien vocabulary.
Possible events, actual events, and robots
Authors: Haas Andrew
Published: April 2007

To plan means reasoning about possible actions, but a robot must also reason about actual events. This paper proposes a formal theory about actual and possible events. It presents a new modal logic as a notation for this theory and a technique for planning in the modal logic using a first‐order theorem prover augmented with simple modal reasoning. This avoids the need for a general modal‐logic theorem prover. Adding beliefs to this theory raises an interesting problem for which the paper offers a tentative solution.
Analysis by synthesis in computational vision with application to remote sensing
Authors: Woodham R.J. , Catanzariti E. , Mackworth A.K.
Published: April 2007

The central problem in vision is to determine scene properties from image properties. This is difficult because the problem, formally posed, is underconstrained. Methods that infer scene properties from images make assumptions about how the world determines what we see. In remote sensing, some of these assumptions can be dealt with explicitly. Available scene knowledge, in the form of a digital terrain model and a ground cover map, is used to synthesize an image for a given date and time. The synthesis process assumes that the surface is a perfectly diffuse or “lambertian” reflector. A scene radiance equation is described based on simple models of direct solar irradiance, diffuse sky irradiance, and atmospheric path radiance. Parameters of the model are estimated from the real image. A statistical comparison of the real image and the synthetic image is used to judge how well the model represents the mapping from scene to image.

The methods presented for image synthesis are similar to those used in computer graphics. The motivation, however, is different. In graphics, the goal is to produce an effective rendering of the scene for a human viewer. Here, the goal is to predict properties of real images. In vision, one must deal with a confounding of effects due to surface shape, surface material, illumination, shadows, and atmosphere. These effects often detract from, rather than enhance, the determination of invariant scene characteristics.
Generating paraphrases from meaning‐text semantic networks
Authors: Boyer Michel , Lapalme Guy
Published: April 2007

This paper describes a first attempt to base a paraphrase generation system upon Meľčuk and Žolkovskij's linguistic meaning‐text (MT) model whose purpose is to establish correspondences between meanings, represented by networks, and (ideally) all synonymous texts having this meaning. The system described here contains a Prolog implementation of a small explanatory and combinatorial dictionary (the MT lexicon) and, using unification and backtracking, generates from a given network the sentences allowed by the dictionary and the lexical transformations of the model. The passage from a net to the final texts is done through a series of transformations of intermediary structures that closely correspond to MT utterance representations (semantic, deep‐syntax, surface‐syntax, and morphological representations). These are graphs and trees with labeled arcs. The Prolog unification (equality predicate) was extended to extract information from these representations and build new ones. The notion of utterance path, used by many authors, is replaced by that ofcovering by defining subnetworks.
Toward a computational interpretation of situation semantics1
Authors: Lespérance Yves
Published: April 2007

Situation semantics proposes novel and attractive treatments for several problem areas of natural language semantics, such as efficiency (context sensitivity) and prepositional attitude reports. Its focus on the information carried by utterances makes the approach very promising for accounting for pragmatic phenomena. However, situation semantics seems to oppose several basic assumptions underlying current approaches to natural language processing and the design of intelligent systems in general. It claims that efficiency undermines the standard notions of logical form, entailment, and proof theory, and objects to the view that mental processes necessarily involve internal representations. The paper attempts to clarify these issues and discusses the impact of situation semantics’ criticisms for natural language processing, knowledge representation, and reasoning. I claim that the representational approach is the only currently practical one for the design of large intelligent systems, but argue that the representations used should be efficient in order to account for the system's embedding in its environment. The paper concludes by stating some constraints that a computational interpretation of situation semantics should obey and discussing remaining problems.
Unrestricted gapping grammars1
Authors: Popowich Fred P.
Published: April 2007

Since Colmerauer's introduction of metamorphosis grammars (MGs), with their associated type‐O‐like grammar rules, there has been a desire to allow more general rule formats in logic grammars. Gap symbols were added to the MG rule by Pereira, resulting in extraposition grammars (XGs). Gaps, which are referenced by gap symbols, are sequences of zero or more unspecified symbols which may be present anywhere in a sentence or in a sentential form. However, XGs imposed restrictions on the position of gap symbols and on the contents of gaps. With the introduction of gapping grammars (GGs) by Dahl, these restrictions were removed but the rule was still required to possess a nonterminal symbol as the first symbol on the left‐hand side. This restriction is removed with the introduction of unrestricted gapping grammars. FIGG, a flexible implementation of gapping grammars, possesses a bottom‐up parser which can process a large subset of unrestricted gapping grammars. It can be used to examine the usefulness of unrestricted GGs for describing phenomena of natural languages such as free word order and partially free word/constituent order. Unrestricted gapping grammars, as implemented in FIGG, can also be used to describe grammars (or metagrammars) that utilize the gap concept, such as Gazdar's generalized phrase structure grammars.
Natural language understanding and Montague grammar1, 2
Authors: Halvorsen Per‐Kristian
Published: April 2007

This paper reevaluates some of the contributions of Montague grammar in view of the increasing importance of computational considerations in linguistic theory and the demand for linguistic theories that can provide support in the design of natural language systems. It also considers Montague grammar in relation to work on lexical semantics and semantic nets. In this perspective the techniques of Montague grammar for systematically linking syntactic form and a model‐theoretic semantics emerge as the most significant feature of the theory, while a number of the specific semantic assumptions recede in importance. Yet, with different ways of thinking about the structure mapping between levels of linguistic form and interpretations (e.g., constraint systems), we can also implement this connection using different techniques from what Montague had at his disposal.
COACH: A tutor based on active schemas
Authors: Gentner Donald R.
Published: April 2007

The Coach system, a computer simulation of a human tutor, was constructed with the goal of obtaining a better understanding of how a tutor interprets the student's behavior, diagnoses difficulties, and gives advice. Coach gives advice to a student who is learning a simple computer programming language. Its intelligence is based on a hierarchy of active schemas that represent the tutor's general concepts and on more specific information represented in a semantic network. The coordination of conceptually guided and data‐driven processing enables the Coach system to interpret student behavior, recognize errors, and give advice to the student.
Knowledge sources for an intelligent algebra tutor
Authors: Bregar William S. , Farley Arthur M. , Bayley Garland
Published: April 2007

The focus of this paper is on the underlying knowledge base for an intelligent tutorial system for high‐school algebra problems. We present a model of problem solving flexible enough to account for a variety of problem‐solving behaviors and general enough to allow new problem domains to be defined easily. The model is based upon the analysis of protocols between students and expert tutors. We show how student errors can be monitored and remediated using the model, and we provide an approach to understanding problem difficulty that can be used to generate challenging problems and also provides a mechanism for planning their solution.
Recognition algorithms for the connection machine
Authors: Flynn Anita M. , Harris John G.
Published: April 2007

This paper describes an object recognition algorithm both on a sequential machine and on a single instruction multiple data (SIMD) parallel processor such as the MIT connection machine. The problem, in the way it is presently formulated on a sequential machine, is essentially a propagation of constraints through a tree of possibilities in an attempt to prune the tree to a small number of leaves. The tree can become excessively large, however, and so implementations on massively parallel machines are sought in order to speed up the problem. Two fast parallel algorithms are described here, a static algorithm and a dynamic algorithm. The static algorithm reformulates the problem by assigning every leaf in the completely expanded unpruned tree to a separate processor in the connection machine. Then pruning is done in nearly constant time by broadcasting constraints to the entire SIMD array. This parallel version is shown to run three to four orders of magnitude faster than the sequential version. For large recognition problems which would exceed the capacity of the machine, a dynamic algorithm is described which performs a series of loading and pruning steps, dynamically allocating and deallocating processors through the use of the connection machine's global router communications mechanism.
Using knowledge generated in heuristic search for nonchronological backtracking
Authors: Dhar Vasant
Published: April 2007

Problem solvers that use heuristics to guide choices often run into untenable situations that can be characterized as overconstrained. When this happens, the problem must be able to identify the right culprit from among its heuristic choices in order to avoid a potentially explosive search. In this paper, we present a solution to this for a certain class of problems where the justifications associated with choice points involve an explicit assessment of the pros and cons of choosing each alternative relative to its competitors. We have designed a problem solver that accumulates such knowledge about the pros and cons of alternative selections at choice points during heuristic search, which it updates in light of an evolving problem situation. Whenever untenable situations arise, this preserved knowledge is used to determine the most appropriate backtracking point. By endowing the backtracker with access to this domain‐specific knowledge, a highly contextual approach to reasoning in backtracking situations can be achieved.
A framework for computing extrasentential references
Authors: Strzalkowski Tomek , Cercone Nick
Published: April 2007

We are concerned with developing a computational method for selecting possible antecedents of referring expressions over sentence boundaries. Our stratified model which uses a Λ‐categorial language for meaning representation incorporates valuable features of Fregean‐type semantics (a la Lewis, Montague, Partee, and others) along with features of situation semantics developed by Barwise and Perry. We consider a series of selected two‐sentence stories which we use to illustrate referential interdependencies between sentences. We explain the conditions under which such dependencies arise, explain the conditions under which various translations can be performed, and formalize a set of rules which specify how to compute the reference. We restrict our discussion to two‐sentence stories to avoid most of the problems inherent in where to look for the reference, that is, how to determine the proper antecedent. We restrict our considerations in this paper to situations where a reference, if it can be computed at all, has a unique antecedent. Thus we consider examples such as John wants to catch a fish. He (John) wants to eat it. and John interviewed a man. The man killed him (John). We then summarize the transformation which encompasses these rules and relate it to the stratified model. We discuss three aspects of this transformation that merit special attention from the computational viewpoint and summarize the contributions we have made. We also discuss the computational characteristics of the stratified model in general and present our ideas for a computer realization; there is no implementation of the t“ratified model at this time.
A hybrid, decidable, logic‐based knowledge representation system1
Authors: Patel‐Schneider Peter F.
Published: April 2007

The major problem with using standard first‐order logic as a basis for knowledge representation systems is its undecidability. A variant of first‐order tautological entailment, a simple version of relevance logic, has been developed that has decidable inference and thus overcomes this problem. However, this logic is too weak for knowledge representation and must be strengthened. One way to strengthen the logic is to create a hybrid logic by adding a terminological reasoner. This must be done with care to retain the decidability of the logic as well as its reasonable semantics. The result, a stronger decidable logic, is used in the design of a hybrid, decidable, logic‐based knowledge representation system.
Patterns of interaction in rule‐based expert system programming
Authors: Raatz Stan , Drastal George
Published: April 2007

We study the effect of adding a rule to a rule‐based heuristic classification expert system, in particular, a rule that causes an unforeseen interaction with rules already in the rule set. We show that it is possible for such an interaction to occur between sets of rules, even when no interaction is present between any pair of rules contained in these sets. A method is presented that identifies interactions between sets of rules, and an analysis is given which relates these interactions to rule‐based programming practices which help to maintain die integrity of the knowledge base. We argue mat the method is practical, given some reasonable assumptions on the knowledge base.
Pragmatic modeling: toward a robust natural language interface
Authors: Carberry Sandra
Published: April 2007

One of the most important ways in which an information‐provider can assimilate an information‐seeking dialogue is by inferring the underlying task‐related plan motivating the information‐seeker's queries. This paper presents a strategy for hypothesizing and tracking the changing task‐level goals of an information‐seeker and building a model of his task‐related plan as the dialogue progresses.

Naturally occurring utterances are often imperfect. The information‐provider often appears to use acquired knowledge about the information‐seeker's underlying task‐related plan to remedy many of the information‐seeker's faulty utterances and enable the dialogue to continue without interruption. This paper presents a strategy for understanding one kind of defective utterance. Our approach relies on the information‐seeker's inferred task‐related plan as the primary mechanism for suggesting how an utterance should be understood, thereby considering only interpretations that are relevant to what the information‐seeker is trying to accomplish. If multiple interpretations are suggested, relevance to the current focus of attention in the dialogue and similarity to the information‐seeker's actual utterance are used to select the interpretation that is most likely to represent his intended meaning or satisfy his needs.
A discussion of a report by Ehud Shapiro
Authors: Banerji Ranan B.
Published: April 2007

The paper is an annotated summary of Ehud Shapiro's report, “The Induction of Theories from Facts.” In the view of this author, Shapiro's report forms a very good foundation for work in the field of learning. It gives a clear definition of the term “learning” in a way which both is intuitively acceptable and renders learning algorithms amenable to precise analysis. It also establishes a paradigm for learning algorithms which is precise enough that it can serve as a benchmark for future development as well as for the analysis of presently available algorithms.
A reasoning‐based approach to machine learning
Authors: Purswani Krish , Rendell Larry
Published: April 2007

This paper describes a novel approach to machine learning, based on the principle of learning by reasoning. Current learning systems have significant limitations such as brittleness, i.e., the deterioration of performance on a different domain or problem and lack of power required for handling real‐world learning problems. The goal of our research was to develop an approach in which many of these limitations are overcome in a unified, coherent and general framework. Our learning approach is based on principles of reasoning, such as the discovery of the underlying principle and the recognition of the deeper basis of similarity, which is somewhat akin to human learning. In this paper, we argue the importance of these principles and tie the limitations of current systems to the lack of application of these principles. We then present the technique developed and illustrate it on a learning problem not directly solvable by previous approaches.
Considerations on default logic: an alternative approach1
Authors: Łukaszewicz Witold
Published: April 2007

In the following paper we analyze Reiter's default logic and suggest modifying the notion of an extension for default theories. This modification leads to two important properties which are not guaranteed in Reiter's formalism: the existence of extensions and semimonotonicity.
Learning and discovery: one system's search for mathematical knowledge
Authors: Epstein Susan L.
Published: April 2007

The Graph Theorist, GT, is a system that performs mathematical research in graph theory. From the definitions in its input knowledge base, GT constructs examples of mathematical concepts, conjectures and proves mathematical theorems about concepts, and discovers new concepts. Discovery is driven both by examples and by definitional form. The discovery processes construct a semantic net that links all of GT's concepts together.

Each definition is an algebraic expression whose semantic interpretation is a stylized algorithm to generate a class of graphs correctly and completely. From a knowledge base of these concept definitions, GT is able to conjecture and prove such theorems as “The set of acyclic, connected graphs is precisely the set of trees” and “There is no odd‐regular graph on an odd number of vertices.” GT explores new concepts either to develop an area of knowledge or to link a newly acquired concept into a pre‐existing knowledge base. New concepts arise from the specialization of an existing concept, the generalization of an existing concept, and the merger of two or more existing concepts. From an initial knowledge base containing only the definition of “graph,” GT discovers such concepts as acyclic graphs, connected graphs, and bipartite graphs.
Discussion of Cheeseman's An inquiry into computer understanding
Authors: Kanal Laveen , Perlis Donald
Published: April 2007

We discuss some points on which we agree, and others on which we disagree, with Cheeseman's target article. Particular agreements include the need for an eclectic approach; disagreements include the misleading distinction between probabilistic and logical reasoning regarding the notion of truth, and also some matters of nonmonotonicity.
OBADE: cognitive modelling with objects
Authors: Darcel Nelly , Escarabajal Marie‐Cl.
Published: April 2007

We realize a computer simulation of children's reasoning in arithmetic word problem solving. The model parses the terms provided to the system in natural language and, while it performs this task, it tries to build its representation of the described situation by the way that the child elaborates a mental problem representation. This image results from three components: semantic knowledge, text comprehension process, and problem‐solving strategies.

We emphasize the adequacy, on one hand, between the knowledge representation and manipulation by an object formalism and, on the other hand, between the structure and the use of knowledge interacting in this application.

The specific aspect of our model is that the internal representation is realized in an object‐oriented language whose main properties are accurately exploited. This choice allows one to combine the descriptive characteristics of each piece of knowledge with its implication in the progress of the process.

The program is supported by the analysis of individual protocols of some children: they allow us to hypothesize on the way the children modify their problem representation during the solving task.

We describe the main objects of the model. Then we simulate on the terms of a problem, the way that the process is driven by expectations of contextually relevant information.
On fuzzy syllogisms
Authors: Dubois Didier , Prade Henri
Published: April 2007

This paper provides a systematic treatment of possibly imprecisely or vaguely specified numerical quantifiers in default syllogisms, following an approach initiated by Zadeh. The obtained propagation rules are derived from simple properties of relative cardinality or, equivalently, conditional probability. Uncertainty in the description of numerical quantifiers is handled using possibility theory and, particularly, fuzzy arithmetic. The advantages of this default reasoning method are its ability to model any kind of quantifier and to build new defaults by chaining existing ones, in a rigorous manner. This approach also emphasizes the difference between two types of uncertain pieces of knowledge, i.e., conjectures versus general rules.
A question‐answering system for the French Yellow Pages
Authors: Herman P. , Sabah G. , Vilnat A.
Published: April 2007

This paper describes a dialogue‐based system which is intended as an intelligent natural language interface to the French Yellow Pages. We do not assume that the user knows how the Yellow Pages are organized, and we paraphrase his request, if necessary, so as to better search for the desired information. We do, however, assume that the reason the user is on line is to find an address and phone number for some supplier.

There are three basic modules used in our system: parser, dialogue manager, and generator. The first two exist (and are constantly being extended); the generation module is still only a set of functional specifications which will be outlined later in this article.
Processing of unknown words in a natural language question‐answering system
Authors: Fournier J. P. , Herman P. , Sabah G. , Vilnat A. , Burgaud N. , Gilloux M.
Published: April 2007

We have developed a prototype of a question‐answering system which is intended to interact with an untrained user to give him information about the Yellow Pages of the French phone directory. We don't detail here the description of the system, because it is done in another paper in the same issue: “A question‐answering system for the French Yellow Pages”.

In this paper we first present a typology of the different kinds of unforeseen situations the system may have to handle while interacting with an untrained user. Then, we detail different strategies we have developed to solve these problems, more specifically to correct misspelt words and to deal with the properly typed, but unknown, words. These mechanisms have been integrated into the parser, and try to maintain, as long as possible, its determinism.
Machine learning research at the Laboratoire de Recherche en Informatique at Orsay, France
Authors: Cornuejols Antoine P.
Published: April 2007

This article provides a brief account with sketchy technical details of the major directions in machine learning research done at the Laboratoire de recherche en informatique (LRI) at Orsay University in France. References contain publications giving details on the projects described in this paper and on closely related works.

Our research has several objectives: looking for a sound basis of the process of generalization from examples, using this to study conceptual clustering with automatic synthesis of descriptors; studying the nature and goodness of an explanation in the context of apprentice systems; and developing experimental learning systems based on these principles applied to various practical domains. The approach taken by our research group has evolved with time but is still mainly based on learning of concepts from examples using logic representations and techniques. It corresponds to a major goal of our group: to give a clear and rigorous picture, if not a theory, of the topics under investigation. Several aspects are persued at the same time: concept learning by generalization, developments of explanation‐based learning techniques, analogy reasoning, and automatic tuning of the description language. These different directions are related to or stimulated by different domains of tasks: learning of rule bases, games, computer‐aided teaching, learning in noisy environments, and so on. They are described in this article in the light of the main directions. The goal of a complete universal integrated system is still a far cry ahead, but as states a famous Chinese proverb: “The end lies in the way”.
Multivalued logics: a uniform approach to reasoning in artificial intelligence
Authors: Ginsberg Matthew L.
Published: April 2007

This paper describes a uniform formalization of much of the current work in artificial intelligence on inference systems. We show that many of these systems, including first‐order theorem provers, assumption‐based truth maintenance systems (atmss), and unimplemented formal systems such as default logic or circumscription, can be subsumed under a single general framework.

We begin by defining this framework, which is based on a mathematical structure known as abilattice.We present a formal definition of inference using this structure and show that this definition generalizes work involving atmss and some simple nonmonotonic logics.

Following the theoretical description, we describe a constructive approach to inference in this setting; the resulting generalization of both conventional inference and atmss is achieved without incurring any substantial computational overhead. We show that our approach can also be used to implement a default reasoner, and discuss a combination of default and atms methods that enables us to formally describe an “incremental” default reasoning system. This incremental system does not need to perform consistency checks before drawing tentative conclusions, but can instead adjust its beliefs when a default premise or conclusion is overturned in the face of convincing contradictory evidence. The system is therefore much more computationally viable than earlier approaches.

Finally, we discuss the implementation of our ideas. We begin by considering general issues that need to be addressed when implementing a multivalued approach such as that we are proposing, and then turn to specific examples showing the results of an existing implementation. This single implementation is used to solve a digital simulation task using first‐order logic, a diagnostic task using atmss as suggested by de Kleer and Williams, a problem in default reasoning as in Reiter's default logic or McCarthy's circumscription, and to solve the same problem more efficiently by combining default methods with justification information. All of these applications use the same general‐purpose bilattice theorem prover and differ only in the choice of bilattice being considered.
Hierarchical planning involving deadlines, travel time, and resources
Authors: Dean Thomas , Firby R. James , Miller David
Published: April 2007

This paper describes a planning architecture that supports a form of hierarchical planning well suited to applications involving deadlines, travel time, and resource considerations. The architecture is based upon a temporal database, a heuristic evaluator, and a decision procedure for refining partial plans. A partial plan consists of a set of tasks and constraints on their order, duration, and potential resource requirements. The temporal database records the partial plan that the planner is currently working on and computes certain consequences of that information to be used in proposing methods to further refine the plan. The heuristic evaluator examines the space of linearized extensions of a given partial plan in order to reject plans that fail to satisfy basic requirements (e.g., hard deadlines and resource limitations) and to estimate the utility of plans that meet these requirements. The information provided by the temporal database and the heuristic evaluator is combined using a decision procedure that determines how best to refine the current partial plan. Neither the temporal database nor the heuristic evaluator is complete and, without reasonably accurate information concerning the possible resource requirements of the tasks in a partial plan, there is a significant risk of missing solutions. A specification language that serves to encode expectations concerning the duration and resource requirements of tasks greatly reduces this risk, enabling useful evaluations of partial plans. Details of the specification language and examples illustrating how such expectations are exploited in decision making are provided.
Learning and classification of monotonic ordinal concepts
Authors: Ben‐David Arie , Sterling Leon , Pao Yoh‐Han
Published: April 2007

Ordinal reasoning plays a major role in human cognition. This paper identifies an important class of classification problems of patterns taken from ordinal domains and presents efficient, incremental algorithms for learning the classification rules from examples. We show that by adopting a monotonicity assumption of the output with respect to the input, inconsistencies among examples can be easily detected and the number of possible classification rules substantially reduced. By adopting a conservative classification criterion, the required number of rules further decreases. The monotonicity and conservatism of the classification also enable the resolution of conflicts among inconsistent examples and the graceful handling of don't knows and don't cares during the learning and classification phases. Two typical examples in which the suggested classification model works well are given. The first example is taken from the financial domain and the second from machining.
An investigation of modal structures as an alternative semantic basis for epistemic logics
Authors: Hamilton Sharon J. , Delgrande James P.
Published: April 2007

In the past, Kripke structures have been used to specify the semantic theory of various modal logics. More recently, modal structures have been developed as an alternative to Kripke structures for providing the semantics of such logics. While these approaches are equivalent in a certain sense, it has been argued that modal structures provide a more appropriate basis for representing the modal notions of knowledge and belief. Since these notions, rather than the traditional notions of necessity and possibility, are of particular interest to artificial intelligence, it is of interest to examine the applicability and versatility of these structures. This paper presents an investigation of modal structures by examining how they may be extended to account for generalizations of Kripke structures. To begin with, we present an alternative formulation of modal structures in terms of trees; this formulation emphasizes the relation between Kripke structures and modal structures, by showing how the latter may be obtained from the former by means of a three‐step transformation. Following this, we show how modal structures may be extended to represent generalizations of possible worlds, and to represent generalizations of accessibility between possible worlds. Lastly, we show how modal structures may be used in the case of a full first‐order system. In all cases, the extensions are shown to be equivalent to the corresponding extension of Kripke structures.
Qualitative data modeling: application of a mechanism for interpreting graphical data
Authors: McIlraith Sheila A.
Published: April 2007

This paper describes a qualitative technique for interpreting graphical data. Given a set of numerical observations regarding the behaviour of a system, its attributes can be determined by plotting the data and qualitatively comparing the shape of the resulting graph with graphs of system behaviour models. Qualitative data modeling incorporates techniques from pattern recognition and qualitative reasoning to characterize observed data, generate hypothetical interpretations, and select models that best fit the shape of the data. Domain‐specific knowledge may be used to substantiate or refute the likelihood of hypothesized interpretations. The basic data modeling technique is domain independent and is applicable to a wide range of problems. It is illustrated here in the context of a knowledge‐based system for well test interpretation.
Discontinuous grammars1,2
Authors: Dahl Verónica
Published: April 2007

This article ties together previously scattered research on discontinuous grammars—logic grammars in which non‐explicit sequences of symbols can be alluded to in the rules and sometimes repositioned by them. After an introduction, we define them formally, present their background, and provide intuitive insight into their use. Next, we examine several motivating arguments, from both formal and natural language processing viewpoints, and we discuss the static discontinuity family of these grammars, in which (a) the nonexplicit strings are not allowed to move and (b) linguistic constraints specifically designed to suit, in particular, Government and Binding theory can be defined modularly and statically in terms of node domination in parse trees and are enforced dynamically. Finally, we discuss implementation issues, related work, and extensions.
A note on evidence and confirmation in machine learning
Authors: Delgrande James P.
Published: April 2007

This paper addresses the problem in inductive generalization of determining when a general hypothesis is supported by a particular instance. If we accept that, first, some facts do indeed support a general hypothesis and, second, that an instance that supports a hypothesis also supports all logical consequences of the hypothesis, then unintuitive and problematic results are immediately forthcoming. These assumptions lead, for example, to the conclusion that a blue Honda is confirming evidence for the hypothesis that ravens are black. This problem is variously known as the paradoxes of confirmation or Hempel's paradox. In this paper I develop a formal characterization of the problem. The assumption that whatever supports all classical consequences of the hypothesis is rejected. Rather, I argue that a weaker notion of consequence should be adopted for determining what consequences of a hypothesis are supported by the same evidence. An extant formal system for learning from examples is used to address these problems of evidential support, and it is shown that in this framework the problems do not arise.
Moments and points in an interval‐based temporal logic
Authors: Allen James F. , Hayes Patrick J.
Published: April 2007

This paper develops and explores a first‐order theory of time that appears useful as an underlying framework for a wide range of practical applications in artificial intelligence (AI). In particular, it presents a concise, formal axiomatization of “interval‐based” time as described by Allen and then explores the relationship between interval‐based and point‐based temporal theories in detail. This analysis should be useful to both theoretical and practical work in AI that involves the representation of time, since it shows what distinctions are actually substantive and what arise merely from formalisms being notational variants of one another.
A predictive approach for the generation of rhetorical devices
Authors: ZUKERMAN INGRID
Published: April 2007

Human discourse is fraught with rhetorical devices such as contradictions, illustrations, and analogies. These rhetorical devices carry important information which a listener uses to speed up the comprehension process. In this paper, we present a taxonomy of rhetorical devices commonly used in tutoring environment, and model the meaning of a class of rhetorical devices in terms of their anticipated effect on a listener's knowledge. These predictions are then used in planning computer‐generated discourse. As a testbed for our ideas, a system called WISHFUL is being implemented to generate commentaries in the domain of high‐school algebra within the framework of an intelligent tutoring system.
Exact and approximate reasoning about temporal relations1
Authors: Van Beek Peter , Cohen Robin
Published: April 2007

Allen gives an algebra for representing qualitative temporal information about the relationships between pairs of intervals. In this paper, we address a fundamental reasoning task that arises in applications of the algebra: Given (possibly indefinite) knowledge about the relationships between intervals, find all feasible relationships between two intervals. We call this the minimal labels problem. Finding the minimal labels can be viewed as computing the deductive consequences of our knowledge. Determining exact solutions to this problem has been shown to be (almost assuredly) intractable. Allen gives an approximation algorithm based on constraint propagation. We present new approximation algorithms; determine analytically under what conditions the algorithms are exact; and examine, through some computational experiments, the quality of the approximate solutions produced by the algorithms. We also give a simple test for predicting when the approximation algorithms will and will not produce good quality approximations. Finally, we survey three example applications of the interval algebra chosen from the literature to show where the results of this paper could be useful.
Reversible logic grammars for natural language parsing and generation
Authors: Strzalkowski Tomek
Published: April 2007

The use of a single grammar in natural language parsing and generation is most desirable for a variety of reasons, including efficiency, perspicuity, integrity, robustness, and a certain amount of elegance. These characteristics have been noted before by several researchers, but it was only recently that more serious attention started to be paid to the problem of creating a bidirectional system for natural language processing. In this paper we discuss a somewhat more radical version of the problem: given a parser for a language, can we reverse it so that it becomes an efficient generator for the same language? Furthermore, since both the parser and the generator are based upon the same grammar, are there any normalization conditions upon the form of the grammar that must be met in order to assure the maximum efficiency of the reversed program? Can other grammars be transformed into the normal form? We describe the results of an experiment with PROLOG‐based logic grammar which has been derived from a substantial‐coverage string grammar for English. We present an alogorithm for automated inversion of a unification parser into an efficient unification generator, using the collections of minimal sets of essential arguments for predicates. We discuss the scope of the present version of the algorithm and then point out several possible avenues for extension. We also outline a preliminary solution to the question of grammar's “normal form” and suggest a handful of normalizing transformations that can be used to enhance the efficiency of the generator. This research interacts closely with a Japanese‐English machine translation project at New York University, for which the first implementation of the inversion algorithm has been prepared.
Lp, a logic for representing and reasoning with statistical knowledge
Authors: Bacchus Fahiem
Published: April 2007

This paper presents a logical formalism for representing and reasoning with statistical knowledge. One of the key features of the formalism is its ability to deal with qualitative statistical information. It is argued that statistical knowledge, especially that of a qualitative nature, is an important component of our world knowledge and that such knowledge is used in many different reasoning tasks. The work is further motivated by the observation that previous formalisms for representing probabilistic information are inadequate for representing statistical knowledge. The representation mechanism takes the form of a logic that is capable of representing a wide variety of statistical knowledge, and that possesses an intuitive formal semantics based on the simple notions of sets of objects and probabilities defined over those sets. Furthermore, a proof theory is developed and is shown to be sound and complete. The formalism offers a perspicuous and powerful representational tool for statistical knowledge, and a proof theory which provides a formal specification for a wide class of deductive inferences. The specification provided by the proof theory subsumes most probabilistic inference procedures previously developed in AI. The formalism also subsumes ordinary first‐order logic, offering a smooth integration of logical and statistical knowledge.
Learning hard concepts through constructive induction: framework and rationale
Authors: RENDELL LARRY , SESHU RAJ
Published: April 2007

The intrinsic accuracy of an inductive problem is the accuracy achieved by exhaustive table look‐up. Intrinsic accuracy is the upper bound for any inductive method. Hard concepts are concepts that have high intrinsic accuracy, but which cannot be learned effectively with traditional inductive methods. To learn hard concepts, we must use constructive induction ‐ methods that create new features. We use measures of concept dispersion to explore (conceptually and empirically) the inherent weaknesses of traditional inductive approaches. These structural defects are buried in the design of the algorithms and prevent the learning of hard concepts. After studying some examples of successful and unsuccessful feature construction (“success” being defined here in terms of accuracy), we introduce a single measure of inductive difficulty that we call variation. We argue for a specific approach to constructive induction that reduces variation by incorporating various kinds of domain knowledge. All of these kinds of domain knowledge boil down to utility invariants, i.e., transformations that group together non‐contiguous portions of feature space having similar class‐membership values. Utility invariants manifest themselves in various ways: in some cases they exist in the user's stock of domain knowledge, in other cases they may be discovered via methods we describe.
Markov analysis of qualitative dynamics1
Authors: DOYLE JON , SACKS ELISHA P.
Published: April 2007

Common sense sometimes predicts events to be likely or unlikely rather than merely possible. We extend methods of qualitative reasoning to predict the relative likelihoods of possible qualitative behaviors by viewing the dynamics of a system as a Markov chain over its transition graph. This involves adding qualitative or quantitative estimates of transition probabilities to each of the transitions and applying the standard theory of Markov chains to distinguish persistent states from transient states and to calculate recurrence times, settling times, and probabilities for ending up in each state. Much of the analysis depends solely on qualitative estimates of transition probabilities, which follow directly from theoretical considerations and which lead to qualitative predictions about entire classes of systems. Quantitative estimates for specific systems are derived empirically and lead to qualitative and quantitative conclusions, most of which are insensitive to small perturbations in the estimated transition probabilities. The algorithms are straightforward and efficient.
Egomotion perception using visual tracking
Authors: BANDOPADHAY AMIT , BALLARD DANA H.
Published: April 2007

The ability of a biological organism to visually track a perceptually significant feature in its environment has been argued to be an important feedback mechanism guiding locomotion. This paper analyzes the constraints available from the visual motion stimuli in the context of tracking. Our aim is to show that the act of tracking simplifies the decoding of egomotion parameters from motion stimuli. The constraints obtainable under tracking are utilized to analyze a possible egomotion decoding strategy for a binocular robot eye system, modeled after the human ocular tracking (smooth pursuit) mechanism. The main result of the paper is in the derivation of a closed‐form solution of the egomotion parameters using feedback information concerning the movement of the tracking motors over time. The theoretical results are verified by experiments. We believe that the active tracking approach presented here is a more simple, practical, and manageable technique in a robot navigation setting, compared to passive methods.
The NIKL experience1
Authors: SCHMOLZE JAMES G. , MARK WILLIAM S.
Published: April 2007

NIKL was the successor to KL‐ONE, the first knowledge representation system to implement “term subsumption” semantics. The primary goals for NIKL were to improve the expressivity and efficiency of KL‐ONE. In the process of developing and using NIKL as the primary representational vehicle for several applications, important new representational needs were identified and addressed, and issues both theoretical and practical in knowledge representation were formulated. In this paper, we present the core of NIKL by way of description, examples, and a model theoretic semantics. We describe the motivations behind the major NIKL design decisions, and discuss NIKL'S capabilities and limitations as a working representation system.