Efficient and non-parametric reasoning over user preferences

We consider the problem of modeling and reasoning about statements of ordinal preferences expressed by a user, such as monadic statement like “X is good,” dyadic statements like “X is better than Y,” etc. Such qualitative statements may be explicitly expressed by the user, or may be inferred from observable user behavior. This paper presents a novel technique for efficient reasoning about sets of such preference statements in a semantically rigorous manner. Specifically, we propose a novel approach for generating an ordinal utility function from a set of qualitative preference statements, drawing upon techniques from knowledge representation and machine learning. We provide theoretical evidence that the new method provides an efficient and expressive tool for reasoning about ordinal user preferences. Empirical results further confirm that the new method is effective on real-world data, making it promising for a wide spectrum of applications that require modeling and reasoning about user preferences.     

Region–based theory of discrete spaces: A proximity approach

We introduce Boolean proximity algebras as a generalization of Efremovič proximities which are suitable in reasoning about discrete regions. Following Stone’s representation theorem for Boolean algebras, it is shown that each such algebra is isomorphic to a substructure of a complete and atomic Boolean proximity algebra. Co-operation was supported by EC COST Action 274 “Theory and Applications of Relational Structures as Knowledge Instruments” (TARSKI), , and NATO Collaborative Linkage Grant PST.CLG 977641.     

Elimination in control theory

For nonlinear systems described by algebraic differential equations (in terms of “state” or “latent” variables) we examine the converse to realization,elimination, which consists of deriving an externally equivalent representation not containing the state variables. The elimination in general yields not only differential equations but also differentialinequations. We show that the application of differential algebraic elimination theory (which goes back to J.F. Ritt and A. Seidenberg) leads to aneffective method for deriving the equivalent representation. Examples calculated by a computer algebra program are shown. This paper was written while the author was with the Systems Division of the Laboratoire des Signaux et Systèmes in Gif-Sur-Yvette and was supported by the University of Orléans, France.     

Representation and uniformization of algebraic transductions

This paper explores different means of representation for algebraic transductions, i.e., word relations realized by pushdown transducers. The relevance of this work lies more in its point of view rather than any particular result. We are aiming at giving specific techniques for obtaining, or perhaps explaining, decompositions of algebraic (and incidentally, rational) relations, relying solely on their “machine” definition rather than some complex algebraic apparatus. From this point of view, we are hoping to have demystified the heavy formalism employed in the present literature. Some of the novelties of our work are: the use of “stack languages” and “embeddings,” which eliminate the need of arbitrary context-free languages in our characterizations, the study of uniformizations for algebraic transductions and the use of the so-called stack transductions for exposing the anatomy of pushdown transducers.This work was supported by the Natural Science and Engineering Research Council of Canada grants R220259 and OGP0041630.     

A new modal logic for reasoning about space: spatial propositional neighborhood logic

It is widely accepted that spatial reasoning plays a central role in artificial intelligence, for it has a wide variety of potential applications, e.g., in robotics, geographical information systems, and medical analysis and diagnosis. While spatial reasoning has been extensively studied at the algebraic level, modal logics for spatial reasoning have received less attention in the literature. In this paper we propose a new modal logic, called spatial propositional neighborhood logic (SpPNL for short) for spatial reasoning through directional relations. We study the expressive power of SpPNL, we show that it is able to express meaningful spatial statements, we prove a representation theorem for abstract spatial frames, and we devise a (non-terminating) sound and complete tableaux-based deduction system for it. Finally, we compare SpPNL with the well-known algebraic spatial reasoning system called rectangle algebra.      

Algebraic Composition of Function Tables

In general, a program is composed of smaller program segments using composition, conditional constructs or loop constructs. We present a theory which enables us to algebraically define and compute the composition of conditional expressions. The conditional expressions are represented using tabular notation. The formal definition of the composition allows us to compute the close form representation of the composition of tabular expressions. The presented approach is based on a many sorted algebra containing information preserving composition. This formal definition of composition is then “lifted” to an extended algebra containing tabular expressions. The presented theory provides very compact algorithms and proofs. Received July 1998 / Accepted in revised form January 2000     

Fuzzy knowledge representation and reasoning using a generalized fuzzy petri net and a similarity measure

In the study of weighted fuzzy production rules (WFPRs) reasoning, we often need to consider those rules whose consequences are represented by two or more propositions connected by “AND” or “OR”. To enhance the representation capability of those rules, this paper proposes two types of knowledge representation parameters, namely, the input weight and the output weight, for a rule. A Generalized Fuzzy Petri Net (GFPN) is also presented for WFPR reasoning. Furthermore, this paper gives a similarity measure to improve the evaluation method of WFPRs and the multilevel fuzzy reasoning in which the consequences and their certainty factors are deduced synchronously by using a GFPN.     

An anytime revision operator for large and uncertain geographic data sets

 The environmental data are in general imprecise and uncertain, but they are located in space and therefore obey to spatial constraints. The “spatial analysis” is a (natural) reasoning process through which geographers take advantage of these constraints to reduce this uncertainty and to improve their beliefs. Trying to automate this process is a really hard problem. We propose here the design of a revision operator able to perform a spatial analysis in the context of one particular “application profile”: it identifies objects bearing a same variable bound through local constraints. The formal background, on which this operator is built, is a decision algorithm from Reiter [9]; then the heuristics, which help this algorithm to become tractable on a true scale application, are special patterns for clauses and “spatial confinement” of conflicts. This operator is “anytime”, because it uses “samples” and works on small (tractable) blocks, it reaggregates the partial revision results on larger blocks, thus we name it a “hierarchical block revision” operator. Finally we illustrate a particular application: a flooding propagation. Of course this is among possible approaches of “soft-computing” for geographic applications. On leave at: Centre de Recherche en Géomatique Pavillon Casault, Université Laval Québec, Qc, Canada – G1K 7P4 Université de Toulon et du Var, Avenue de l'Université, BP 132, 83957 La Garde Cedex, France This work is currently supported by the European Community under the IST-1999-14189 project.     

Is There a Future for AI Without Representation?

This paper investigates the prospects of Rodney Brooks’ proposal for AI without representation. It turns out that the supposedly characteristic features of “new AI” (embodiment, situatedness, absence of reasoning, and absence of representation) are all present in conventional systems: “New AI” is just like old AI. Brooks proposal boils down to the architectural rejection of central control in intelligent agents—Which, however, turns out to be crucial. Some of more recent cognitive science suggests that we might do well to dispose of the image of intelligent agents as central representation processors. If this paradigm shift is achieved, Brooks’ proposal for cognition without representation appears promising for full-blown intelligent agents—Though not for conscious agents.     

Partial Functions in ACL2

We describe a method for introducing “partial functions” into ACL2, that is, functions not defined everywhere. The function “definitions” are actually admitted via the encapsulation principle: the new function symbol is constrained to satisfy the appropriate equation. This is permitted only when a witness function can be exhibited, establishing that the constraint is satisfiable. Of particular interest is the observation that every tail recursive definition can be witnessed in ACL2. We describe a macro that allows the convenient introduction of arbitrary tail recursive functions, and we discuss how such functions can be used to prove theorems about state machine models without reasoning about “clocks” or counting the number of steps until termination. Our macro for introducing “partial functions” also permits a variety of other recursive schemes, and we briefly illustrate some of them. This revised version was published online in August 2006 with corrections to the Cover Date.     

Simplicialization of digital volumes in 26-adjacency: Application to topological analysis

In this paper, we introduce a simple and original algorithm to compute a three-dimensional simplicial complex topologically equivalent to a 3D digital object V, according to the 26-adjacency. The use of this adjacency generates issues like auto-intersecting triangles that unnecessarily increase the dimensionality of the associated simplicial complex. To avoid these problems, we present an approach based on a modified Delaunay tetrahedralization of the digital object, that preserves its topological characteristics. Considering the resulting complex as an input in algebraic-topological format (fixing a ground ring for the coefficients), we develop propositions regardless of the adjacency considered. These potential applications are related to topological analysis like thinning, homology computation, topological characterization and control. Moreover, our technique is susceptible to be extended to higher dimensions. The article is published in the original. Jean-Luc Mari received his PhD degree in 2002. He has been an Associate Professor since 2003 in the Department of Computer Science at the Faculté des Sciences de Luminy (University of Marseilles). He is also a member of the Information and System Science Laboratory (LSIS), in the team “Image and Models” (Computer Graphics group). His research interests include geometrical modeling, model representation, implicit and subdivision surfaces, meshes, multiresolution, skeleton based objects and reconstruction. Pedro Real received his PhD degree in 1993. He has been an Associate Professor since 1995 in the Department of Applied Mathematics I at Higher Technical School of Computer Engineering (University of Seville, Spain). He is the main responsible of the andalusian research group “Computational Topology and Applied Mathematics.” His research interests include computational algebraic topology, topological analysis of digital images, algebraic pattern recognition and computational algebra.     

How “Authentic Intentionality” can be Enabled: a Neurocomputational Hypothesis

According to John Haugeland, the capacity for “authentic intentionality” depends on a commitment to constitutive standards of objectivity. One of the consequences of Haugeland’s view is that a neurocomputational explanation cannot be adequate to understand “authentic intentionality”. This paper gives grounds to resist such a consequence. It provides the beginning of an account of authentic intentionality in terms of neurocomputational enabling conditions. It argues that the standards, which constitute the domain of objects that can be represented, reflect the statistical structure of the environments where brain sensory systems evolved and develop. The objection that I equivocate on what Haugeland means by “commitment to standards” is rebutted by introducing the notion of “florid, self-conscious representing”. Were the hypothesis presented plausible, computational neuroscience would offer a promising framework for a better understanding of the conditions for meaningful representation.     

线型物体主方向关系推理的研究

线型物体主方向关系的推理研究是空间方向关系推理中的重要组成部分.在分析线型物体主方向关系模型的基础上,提出了线型物体主方向关系的投影区间矩形代数方法,从而实现了线型物体主方向关系的合理表示、基本推理运算以及线型物体主方向关系的凸关系判断.结合凸关系网络定理和路径一致性算法,提出了线型物体主方向关系网络一致性检验算法,给出了算法的正确性证明.     

利用线画图象二维串的图象理解方法

本文提出一种基于符号运算和面向规则线画图象的自动图象理解方法，方法用代数符号表达空间物体，用两个符号串描述物体在特定的投影空间上的相互关系，上方法所构造的代数系统规定了包括微分，腐蚀等等代数操作定义了若干条运算规则。利用这些操作和规则，可以实现对图象中物体的空间位置，运动趋势，自身大小的变化等等的自动分析。     

Grammar-based articulation for multimedia document design

This paper describes an approach to the problem of articulating multimedia information based on parsing and syntax-directed translation that uses Relational Grammars. This translation is followed by a constraint-solving mechanism to create the final layout. Grammatical rules provide the mechanism for mapping from a representation of the content and context of a presentation to forms that specify the media objects to be realized. These realization forms include sets of spatial and temporal constraints between elements of the presentation. Individual grammars encapsulate the “look and feel” of a presentation and can be used as generators of such a style. By making the grammars sensitive to the requirements of the output medium, parsing can introduce flexibility into the information realization process.     

Set-structured and cost-sharing heuristics for classical planning

Problem abstractions based on (either completely or partially) ignoring delete effects of the actions provide the basis for some seminal classical planning heuristics. However, the palette of the conceptual tools exploited by these heuristics remains rather limited. We study a framework for approximating the optimal cost solutions for problems with no delete effects that bridges between certain works on heuristic-search classical planning and on probabilistic reasoning. Our analysis results in developing a novel heuristic function that combines “informed” set-structured cost estimates and “conservative” action cost sharing. Our empirical comparative evaluation provides a clear evidence for the attractiveness of this heuristic estimate. In addition, we examine a (suggested before in the context of probabilistic reasoning) admissible heuristic based on a stronger variant of action cost sharing. We show that what is good for “typical” problems of probabilistic reasoning turns out not to be so for “typical” problems of classical planning, and provide a formal account for that difference.     

A Comparison of Inferences about Containers and Surfaces in Small-Scale and Large-Scale Spaces

Inference mechanisms about spatial relations constitute an important aspect of spatial reasoning as they allow users to derive unknown spatial information from a set of known spatial relations. When formalized in the form of algebras, spatial-relation inferences represent a mathematically sound definition of the behavior of spatial relations, which can be used to specify constraints in spatial query languages. Current spatial query languages utilize spatial concepts that are derived primarily from geometric principles, which do not necessarily match with the concepts people use when they reason and communicate about spatial relations. This paper presents an alternative approach to spatial reasoning by starting with a small set of spatial operators that are derived from concepts closely related to human cognition. This cognitive foundation comes from the behavior of image schemata, which are cognitive structures for organizing people's experiences and comprehension. From the operations and spatial relations of a small-scale space, a container–surface algebra is defined with nine basic spatial operators—inside, outside, on, off, their respective converse relations—contains, excludes, supports, separated_from, and the identity relation equal. The container–surface algebra was applied to spaces with objects of different sizes and its inferences were assessed through human-subject experiments. Discrepancies between the container–surface algebra and the human-subject testing appear for combinations of spatial relations that result in more than one possible inference depending on the relative size of objects. For configurations with small- and large-scale objects larger discrepancies were found because people use relations such as part of and at in lieu of in. Basic concepts such as containers and surfaces seem to be a promising approach to define and derive inferences among spatial relations that are close to human reasoning.