Discovering rules to design newspapers: An inductive constraint logic programming approach

Inductive logic programming combines both machine learning and logic programming techniques. ILP uses first-order predicate logic restricted to Horn clauses as an underlying language. Thus, programs induced by an ILP system inherit the classical limitations of PROLOG programs. Constraint logic programming avoids some of the limitations of logic programming, and so ILP aims to induce programs that employ this paradigm. Current ILP systems that induce constrained logic programs extend systems based on the normal semantics ofILP. In this article we introduce IC-Log, a new system that induces constrained logic programs and relies on an extension ofa nonmonotonic semantics-based system. We then present an application of IC-Log in the field ofcomputer-aided publishing.     

Symbolic constraints for meta-logic programming

Logic programming, with its declarative bias as well as unification and the direct representation of linguistic structures, is well qualified for meta-programming, i.e., programs working with representations of other programs as their data. However, constraint techniques seem necessary in order to fully exploit this paradigm. In the DEMOII system, the language of constraint handling rules (CHRs) has been used in order to provide a functionality that appears difficult to obtain without such means. For example, reversibility of a meta-interpreter, which can be obtained by means of constraints, turns it into a powerful program generator; in the same way, negation-as-failure implemented by means of constraints provides an incremental evaluation of integrity constraints. This paper focuses on the design of such constraints and their implementation by means of CHR.     

Programming languages for distributed applications

Much progress has been made in distributed computing in the areas of distribution structure, open computing, fault tolerance, and security. Yet, writing distributed applications remains difficult because the programmer has to manage models of these areas explicitly. A major challenge is to integrate the four models into a coherent development platform. Such a platform should make it possible to cleanly separate an application’s functionality from the other four concerns. Concurrent constraint programming, an evolution of concurrent logic programming, has both the expressiveness and the formal foundation needed to attempt this integration. As a first step, we have designed and built a platform that separates an application’s functionality from its distribution structure. We have prototyped several collaborative tools with this platform, including a shared graphic editor whose design is presented in detail. The platform efficiently implements Distributed Oz, which extends the Oz language with constructs to express the distribution structure and with basic primitives for open computing, failure detection and handling, and resource control. Oz appears to the programmer as a concurrent object-oriented language with dataflow synchronization. Oz is based on a higher-order, state-aware, concurrent constraint computation model. Seif Haridi, Ph.D.: He received his Ph.D. in computer science in 1981 from the Royal Institute of Technology, Sweden. After spending 18 months at IBM T. J. Watson Research Center, he moved to the Swedish Institute of Computer Science (SICS) to form a research lab on logic programming and parallel systems. Dr. Haridi is currently the research director of the Swedish Institute of Computer Science. He has been an active researcher in the area of logic and constraint programming and parallel processing since the beginning of the eighties. His earlier work includes contributions to the design of SICStus Prolog, various parallel Prolog systems and a class of scalable cache-coherent multiprocessors known as Cache-Only Memory Architecture (COMA). During the nineties most of his work focused on the design of multiparadigm programming systems based on Concurrent Constraint Programming (CCP). Currently, he is interested in programming systems and software methodology for distributed and agent-based applications. Peter Van Roy, Ph.D.: He obtained an engineering degree from the Vrije Universiteit Brussel (1983), Masters and Ph.D. degrees from the University of California at Berkeley (1984, 1990), and the Habilitation à Diriger des Recherches from Paris VII Denis Diderot (1996). He has made major contributions to logic language implementation. His research showed for the first time that Prolog can be implemented with the same execution efficiency as C. He was principal developer or codeveloper of Aquarius Prolog, Wild_Life, Logical State Threads, and FractaSketch. He joined the Oz project in 1994 and is currently working on Distributed Oz. His research interests are motivated by the desire to provide increased expressivity and efficiency to application developers. Per Brand: He is a researcher at the Swedish Institute of Computer Science. He has previously worked on the design and implementation of OR-parallel Prolog (the Aurora project) and optimized compilation techniques for Concurrent Constraint Programming Languages (in particular, AKL). He has been a member of the Distributed Oz design team since the project began. His research interests are focused on techniques, languages, and methodology for distributed programming. Christian Schulte: He studied computer science at the University of Karlsruhe, Germany, from 1987 to 1992 where he received his diploma. Since 1992 he has been a member of the Programming Systems Lab at DFKI. He is one of the principal designers of Oz. His research interests include design, implementation, and application of concurrent and distributed programming languages as well as constraint programming.     

A program specialiser for meta-level compositions of logic programs

Metal-level compositions of object logic programs are naturally implemented by means of meta-programming techniques. Metainterpreters defining program compositions however suffer from a computational overhead that is due partly to the interpretation layer present in all meta-programs, and partly to the specific interpretation layer needed to deal with program compositions. We show that meta-interpreters implementing compositions of object programs can be fruitfully specialised w.r.t. meta-level queries of the form Demo (E, G), where E denotes a program expression and G denotes a (partially instantiated) object level query. More precisely, we describe the design and implementation of declarative program specialiser that suitably transforms such meta-interpreters so as to sensibly reduce — if not to completely remove — the overhead due to the handling of program compositions. In many cases the specialiser succeeds in eliminating also the overhead due to meta-interpretation. Antonio Brogi, Ph.D.: He is currently assistant professor in the Department of Computer Science at the University of Pisa, Italy. He received his Laurea Degree in Computer Science (1987) and his Ph. D. in Computer Science (1993) from the University of Pisa. His research interests include programming language design and semantics, logic programming, deductive databases, and software coordination. Simone Contiero: He is currently a Ph. D. student at the Department of Computer Science, University of Pisa (Italy). He received his Laurea Degree in Computer Science from the University of Pisa in 1994. His research interests are in high-level programming languages, metaprogramming and logic-based coordination of software.     

From eager to lazy constrained data acquisition: A general framework

^*1 Constraint Satisfaction Problems (CSPs)¹⁷⁾ are an effective framework for modeling a variety of real life applications and many techniques have been proposed for solving them efficiently. CSPs are based on the assumption that all constrained data (values in variable domains) are available at the beginning of the computation. However, many non-toy problems derive their parameters from an external environment. Data retrieval can be a hard task, because data can come from a third-party system that has to convert information encoded with signals (derived from sensors) into symbolic information (exploitable by a CSP solver). Also, data can be provided by the user or have to be queried to a database. For this purpose, we introduce an extension of the widely used CSP model, called Interactive Constraint Satisfaction Problem (ICSP) model. The variable domain values can be acquired when needed during the resolution process by means of Interactive Constraints, which retrieve (possibly consistent) information. A general framework for constraint propagation algorithms is proposed which is parametric in the number of acquisitions performed at each step. Experimental results show the effectiveness of the proposed approach. Some applications which can benefit from the proposed solution are also discussed. This paper is an extended and revised version of the paper presented at IJCAI’99 (Stockholm, August 1999)⁴⁾. Paola Mello, Ph.D.: She received her degree in Electronic Engineering from University of Bologna, Italy, in 1982 and her Ph.D. degree in Computer Science in 1989. Since 1994 she is full Professor. She is enrolled, at present, at the Faculty of Engineering of the University of Bologna where she teaches Artificial Intelligence. Her research activity focuses around: programming languages, with particular reference to logic languages and their extensions towards modular and object-oriented programming; artificial intelligence; knowledge representation; expert systems. Her research has covered implementation, application and theoretical aspects and is presented in several national and international publications. She took part to several national (Progetti Finalizzati e MURST) and international (UE) research projects in the context of computational logic. Michela Milano, Ph.D.: She is a Researcher in the Department of Electronics, Computer Science and Systems at the University of Bologna. From the same University she obtained her master degree in 1994 and her Ph.D. in 1998. In 1999 she had a post-doc position at the University of Ferrara. Her research focuses on Artificial Intelligence, Constraint Satisfaction and Constraint Programming. In particular, she worked on using and extending the constraint-based paradigm for solving real-life problems such as scheduling, routing, object recognition and planning. She has served on the program committees of several international conferences in the area of Constraint Satisfaction and Programming, and she has served as referee in several related international journals. Marco Gavanelli: He is currently a Ph.D. Student in the Department of Engineering at the University of Ferrara, Italy. He graduated in Computer Science Engineering in 1998 at the University of Bologna, Italy. His research interest include Artificial Intelligence, Constraint Logic Programming, Constraint Satisfaction and visual recognition. He is a member of ALP (the Association for Logic Programming) and AI^*IA (the Italian Association for Artificial Intelligence). Evelina Lamma, Ph.D.: She got her degree in Electrical Engineering at the University of Bologna in 1985, and her Ph.D. in Computer Science in 1990. Her research activity centers on logic programming languages, Artificial Intelligence and software engineering. She was co-organizers of the 3rd International Workshop on Extensions of Logic Programming ELP92, held in Bologna in February 1992, and of the 6th Italian Congress on Artificial Intelligence, held in Bologna in September 1999. She is a member of the Executive Committee of the Italian Association for Artificial Intelligence (AI^*IA). Currently, she is Full Professor at the University of Ferrara, where she teaches Artificial Intelligence and Fondations of Computer Science. Massimo Piccardi, Ph.D.: He graduated in electronic engineering at the University of Bologna, Italy, in 1991, where he received a Ph.D. in computer science and computer engineering in 1995. He currently an assistant professor of computer science with the Faculty of Engineering at the University of Ferrara, Italy, where he teaches courses on computer architecture and microprocessor systems. Massimo Piccardi participated in several research projects in the area of computer vision and pattern recognition. His research interests include architectures, algorithms and benchmarks for computer vision and pattern recognition. He is author of more than forty papers on international scientific journals and conference proceedings. Dr. Piccardi is a member of the IEEE, the IEEE Computer Society, and the International Association for Pattern Recognition — Italian Chapter. Rita Cucchiara, Ph.D.: She is an associate professor of computer science at the Faculty of Engineering at the University of Modena and Reggio Emilia, Italy, where she teaches courses on computer architecture and computer vision. She graduated in electronic engineering at the University of Bologna, Italy, in 1989 and she received a Ph.D. in electronic engineering and computer science from the same university in 1993. From 1993 to 1998 she been an assistant professor of computer science with the University of Ferrara, Italy. She participated in many research projects, including a SIMD parallel system for vision in the context of an Italian advanced research program in robotics, funded by CNR (the Italian National Research Council). Her research interests include architecture and algorithms for computer vision and multimedia systems. She is author of several papers on scientific journals and conference proceedings. She is member of the IEEE, the IEEE Computer Society, and the International Association for Pattern Recognition — Italian Chapter.     

Logical foundations for representing object-oriented systems

Abstract

Object-oriented programming languages are designed for computing or simulating the behaviour of interacting objects, but their encapsulated contexts and procedural methods are not well suited to non-procedural techniques in theorem provers, optimizers, and automated design and analysis tools. Logic is the non-procedural system par excellence, but the predicate calculus notation for logic is awkward for representing and reasoning about encapsulated contexts. Conceptual graphs are a graphic system of logic that is better suited to O-O systems. First, they explicitly represent the contexts that are ignored or obscured in predicate calculus. Second, Peirce's rules of inference for reasoning with graphs are explicitly formulated in terms of contexts and the conditions for importing and exporting information from contexts. This article describes the context mechanisms of conceptual graphs, the rules of inference for reasoning with the graphs, and their use as a design language for object-oriented systems.     

ENHANCEMENT OF THE CAPABILITIES OF AN NMR IMAGING MACHINE USING EXPERT SYSTEMS

ABSTRACT

Practical effectiveness of NMR imaging in diagnostic medicine can be considerably upgraded by incorporating into the machine high-level intelligent software support. Partly because NMR imaging is a relatively new technology, knowledge acquisition is essentially related to incoming new experience. Therefore an expert system approach to NMR medical applications should rely on rule induction techniques based on a series of example expert decisions. The complete project consists of three main components: (1) a protocol expert system, (2) a diagnosis expert system, and (3) a vision system. Expert system prototypes regarding part 1 and 2 of this study were built indicating preliminary interesting results. These results justify our attempts aimed at the enhancement of NMR capabilities as a diagnostic tool and consequent commercial benefits.     

TaxoPublish: Towards a solution to automatically personalize taxonomies in e-catalogs

Taxonomies are utilized in e-catalogs to facilitate customers navigating through a marketplace with the help of hierarchically structured concepts. However, when entering the e-catalog, each customer is shown the identical taxonomy regardless their individual requirements. Customers are distracted when navigating to preferred concepts as those are siblings of not required concepts. Provided progress in dynamic taxonomies, catalog segmentation, and personalized directories lacks in a fully automatic support for modifying the taxonomy according to the user’s requirements. The existing works need an explicit user-query, are missing information about the domain, or require the modification through the provider. In this paper, TaxoPublish expert system based on logic programming is presented. The proposed system predicts the customers requirements for automatically modifying the taxonomy in B2B context. With TaxoPublish, retailers can now provide personalization in the form of personalized e-catalogs without any human effort, and without missing any information about the domain. TaxoPublish is using knowledge provided through a Customer Relationship Management system for predicting customers preferences, and knowledge of a Product Information Management system for performing taxonomic operations based on two novel types of taxonomic concepts. Through the usage of logic programming and the cross-platform database model, TaxoPublish can be applied as expert system over distributed and heterogeneous data warehouse architectures across various domains. The comprehensive experiments on two public and one private database show that TaxoPublish expert system is capable of fully-automatic taxonomy modification with an accuracy similar to the expert manual modifications.     

Cautious induction: An alternative to clause-at-a-time hypothesis construction in inductive logic programming

Hypotheses constructed by inductive logic programming (ILP) systems are finite sets of definite clauses. Top-down ILP systems usually adopt the following greedy clause-at-a-time strategy to construct such a hypothesis: start with the empty set of clauses and repeatedly add the clause that most improves the quality of the set. This paper formulates and analyses an alternative method for constructing hypotheses. The method, calledcautious induction, consists of a first stage, which finds a finite set of candidate clauses, and a second stage, which selects a finite subset of these clauses to form a hypothesis. By using a less greedy method in the second stage, cautious induction can find hypotheses of higher quality than can be found with a clause-at-a-time algorithm. We have implemented a top-down, cautious ILP system called CILS. This paper presents CILS and compares it to Progol, a top-down clause-at-a-time ILP system. The sizes of the search spaces confronted by the two systems are analysed and an experiment examines their performance on a series of mutagenesis learning problems. Simon Anthony, BEng.: Simon, perhaps better known as “Mr. Cautious” in Inductive Logic Programming (ILP) circles, completed a BEng in Information Engineering at the University of York in 1995. He remained at York as a research student in the Intelligent Systems Group. Concentrating on ILP, his research interests are Cautious Induction and developing number handling techniques using Constraint Logic Programming. Alan M. Frisch, Ph.D.: He is the Reader in Intelligent Systems at the University of York (UK), and he heads the Intelligent Systems Group in the Department of Computer Science. He was awarded a Ph. D. in Computer Science from the University of Rochester (USA) in 1986 and has held faculty positions at the University of Sussex (UK) and the University of Illinois at Urbana-Champaign (USA). For over 15 years Dr. Frisch has been conducting research on a wide range of topics in the area of automated reasoning, including knowledge retrieval, probabilistic inference, constraint solving, parsing as deduction, inductive logic programming and the integration of constraint solvers into automated deduction systems.     

Programmable applications: exploring the potential for language/interface symbiosis

Abstract

Programmable applications are software systems that seek to combine the learnability and accessibility of direct manipulation interfaces with the expressive power and range of programming languages. In this paper we explore techniques for creatively integrating language and interface constructs within programmable applications. Using SchemePaint—a programmable graphics application—as a source of examples, we demonstrate how an interface and language can combine symbolically and thereby provide powerful modes of expression within applications.     

Learning goal hierarchies from structured observations and expert annotations

We describe a relational learning by observation framework that automatically creates cognitive agent programs that model expert task performance in complex dynamic domains. Our framework uses observed behavior and goal annotations of an expert as the primary input, interprets them in the context of background knowledge, and returns an agent program that behaves similar to the expert. We map the problem of creating an agent program on to multiple learning problems that can be represented in a “supervised concept learning’’ setting. The acquired procedural knowledge is partitioned into a hierarchy of goals and represented with first order rules. Using an inductive logic programming (ILP) learning component allows our framework to naturally combine structured behavior observations, parametric and hierarchical goal annotations, and complex background knowledge. To deal with the large domains we consider, we have developed an efficient mechanism for storing and retrieving structured behavior data. We have tested our approach using artificially created examples and behavior observation traces generated by AI agents. We evaluate the learned rules by comparing them to hand-coded rules. Editor: Rui Camacho     

Machine learning for map interpretation: An intelligent tool for environmental planning

The design of a user interface integrating instruments for visual and textual representation and image interpretation is a relevant problem when developing an advisory system for environmental planning. Indeed, the user of the system needs a support to the interpretation of maps, that is, a tool that segments maps and automatically associates geometric regions on a map with those semantic labels useful for applying hints and advices suggested by the environmental planning system. In the article, we present the application of symbolic machine learning techniques to the interpretation of maps. Two inductive learning systems, namely, INDUBI/CSL and ATRE, have been used to complete the knowledge base of an expert system for environmental planning. The application described concerns the recognition of four environmental concepts that are relevant for environmental protection. The positive results obtained in two different experiments prove the strength of the adopted approach for the interpretation task.     

An abductive-based scheduler for air-crew assignment

This article presents the design and implementation of an air-crew assignment system, for producing and refining a solution to this problem, based on the artificial intelligence principles and techniques of abductive reasoning as captured by the framework of abductive logic programming (ALP). The system offers a high level of flexibility in addressing both the tasks of crew scheduling and rescheduling. Itcan be used to generate a valid and good quality initial solution and then help the human operators adjust and refine further this solution in order to meet extra requirements of the problem. These additional needs can arise either due to new foreseen requirements that the company wants to have or experiment with for a particular period in time, or due to unexpected events that have occurred while the solution (crew-roster) is in operation. This work shows the ability and flexibility of abduction, and, more specifically, of ALP, in tackling problems of this type with complex and changing requirements.     

Model-based remotely-sensed imagery interpretation

Abstract

We present a model-based remotely-sensed image interpretation expert system embeded in a knowledge-based geographic information system (K. BIS). The KBIS consists of four sub-systems: a pictorial data base system, an image interpretation expert system, a computer-aided planning system and a computer-aided cartographic system. The image interpretation expert system represents ecological knowledge and other expert knowledge by frames. Its reasoning process consists of a forward reasoning based on the Bayes classification of Landsat imagery, a backward reasoning using frame knowledge and reasoning using a spatial consistency model. A forest inventory study was conducted in Shaxian county, in the southern part of China, using this expert system. The results have shown a significant improvement. Building image interpretation expert systems within knowledge-based pictorial systems is very convenient and efficient because there are well-organized data, knowledge and procedures available.     

面向概念的通用知识获取系统

本文提出的面向概念的知识获取系统是一个能理解基本逻辑和自然语言的通用知识获取环境。系统结合了人工智能(ai)、面向对象的程序设计(oop)和逻辑程序设计(Lp)等技术。系统以概念为知识基元,由概念描述器(cd)予以描述。cd是一个类框架和类对象 的结构,它由一组概念特性和属性,逻辑约束和函数式等支持。这些特性可由具体的应用而赋于实际的含义。知识库中的概念集是一个层次式的继承网络。另外系统还附有一些语义子系统,如一阶逻辑系统和简单的自然语言系统,用以各种类型的语法检查及知识的冗余、互斥及非一致性检查。系统主     

An expert system for experimental design in off-line quality control

Abstract: Robust design is an efficient method for designing high quality products at low cost. The method examines the effect of a large number of design factors on the variability of a product's response due to various sources of disturbance. This effect can be observed efficiently by studying a large number of variables simultaneously through balanced, orthogonal array experiments, and by analyzing the resulting data using variance decomposition methods. In this paper we describe an expert system prototype for designing efficient experiments. Given the information on various parameters and their levels, the system designs an experiment using orthogonal arrays. This expert system is implemented in Prolog, which is a logic programming language for artificial intelligence research and expert systems development. The system was implemented under the P-Shell knowledge programming environment on UNIX.     

NEW METHODOLOGY TO FUZZY REASONING FOR RULE-BASED EXPERT SYSTEMS

Abstract

Much knowledge residing in the knowledge base of an expert system involves fuzzy concepts. A powerful expert system must have the capability of fuzzy reasoning. This paper presents a new methodology for dealing with fuzzy reasoning based on the matching function S. The single-input, single-output (SISO) fuzzy reasoning scheme and the multi-input, single-output (MISO) fuzzy reasoning schemes are discussed in detail. The proposed fuzzy reasoning methodology is conceptually clearer than the compositional rule of inference approach. It can provide an useful way for rule-based systems to deal with fuzzy reasoning.