Inductive logic programming for gene regulation prediction

We present a systems biology application of ILP, where the goal is to predict the regulation of a gene under a certain condition from binding site information, the state of regulators, and additional information. In the experiments, the boosted Tilde model is on par with the original model by Middendorf et al. based on alternating decision trees (ADTrees), given the same information. Adding functional categorizations and protein-protein interactions, however, it is possible to improve the performance substantially. We believe that decoding the regulation mechanisms of genes is an exciting new application of learning in logic, requiring data integration from various sources and potentially contributing to a better understanding on a system level. Editors: Stephen Muggleton, Ramon Otero, Simon Colton.     

Inductive logic programming for relational knowledge discovery

Inductive logic programming (ILP) is concerned with the induction of logic programs from examples and background knowledge. In ILP, the shift of attention from program synthesis to knowledge discovery resulted in advanced techniques that are practically applicable for discovering knowledge in relational databases. This paper gives a brief introduction to ILP, presents selected ILP techniques for relational knowledge discovery and reviews selected ILP applications. Nada Lavrač, Ph.D.: She is a senior research associate at the Department of Intelligent Systems, J. Stefan Institute, Ljubljana, Slovenia (since 1978) and a visiting professor at the Klagenfurt University, Austria (since 1987). Her main research interest is in machine learning, in particular inductive logic programming and intelligent data analysis in medicine. She received a BSc in Technical Mathematics and MSc in Computer Science from Ljubljana University, and a PhD in Technical Sciences from Maribor University, Slovenia. She is coauthor of KARDIO: A Study in Deep and Qualitative Knowledge for Expert Systems, The MIT Press 1989, and Inductive Logic Programming: Techniques and Applications, Ellis Horwood 1994, and coeditor of Intelligent Data Analysis in Medicine and Pharmacology, Kluwer 1997. She was the coordinator of the European Scientific Network in Inductive Logic Programming ILPNET (1993–1996) and program cochair of the 8th European Machine Learning Conference ECML’95, and 7th International Workshop on Inductive Logic Programming ILP’97. Sašo Džeroski, Ph.D.: He is a research associate at the Department of Intelligent Systems, J. Stefan Institute, Ljubljana, Slovenia (since 1989). He has held visiting researcher positions at the Turing Institute, Glasgow (UK), Katholieke Universiteit Leuven (Belgium), German National Research Center for Computer Science (GMD), Sankt Augustin (Germany) and the Foundation for Research and Technology-Hellas (FORTH), Heraklion (Greece). His research interest is in machine learning and knowledge discovery in databases, in particular inductive logic programming and its applications and knowledge discovery in environmental databases. He is co-author of Inductive Logic Programming: Techniques and Applications, Ellis Horwood 1994. He is the scientific coordinator of ILPnet2, The Network of Excellence in Inductive Logic Programming. He was program co-chair of the 7th International Workshop on Inductive Logic Programming ILP’97 and will be program co-chair of the 16th International Conference on Machine Learning ICML’99. Masayuki Numao, Ph.D.: He is an associate professor at the Department of Computer Science, Tokyo Institute of Technology. He received a bachelor of engineering in electrical and electronics engineering in 1982 and his Ph.D. in computer science in 1987 from Tokyo Institute of Technology. He was a visiting scholar at CSLI, Stanford University from 1989 to 1990. His research interests include Artificial Intelligence, Global Intelligence and Machine Learning. Numao is a member of Information Processing Society of Japan, Japanese Society for Artificial Intelligence, Japanese Cognitive Science Society, Japan Society for Software Science and Technology and AAAI.     

Multimodal logic programming

We give a framework for developing the least model semantics, fixpoint semantics, and SLD-resolution calculi for logic programs in multimodal logics whose frame restrictions consist of the conditions of seriality (i.e. ) and some classical first-order Horn clauses. Our approach is direct and no special restriction on occurrences of □_i and _i is required. We apply our framework for a large class of basic serial multimodal logics, which are parameterized by an arbitrary combination of generalized versions of axioms T, B, 4, 5 (in the form, e.g. 4:□_i→□_j□_k) and I:□_i→□_j. Another part of the work is devoted to programming in multimodal logics intended for reasoning about multidegree belief, for use in distributed systems of belief, or for reasoning about epistemic states of agents in multiagent systems. For that we also use the framework, and although these latter logics belong to the mentioned class of basic serial multimodal logics, the special SLD-resolution calculi proposed for them are more efficient.     

Probabilistic logic programming

Of all scientific investigations into reasoning with uncertainty and chance, probability theory is perhaps the best understood paradigm. Nevertheless, all studies conducted thus far into the semantics of quantitative logic programming have restricted themselves to non-probabilistic semantic characterizations. In this paper, we take a few steps towards rectifying this situation. We define a logic programming language that is syntactically similar to the annotated logics of Blair et al., 1987 and Blair and Subrahmanian, 1988, 45–73) but in which the truth values are interpreted probabilistically. A probabilistic model theory and fixpoint theory is developed for such programs. This probabilistic model theory satisfies the requirements proposed by Fenstad (in “Studies in Inductive Logic and Probabilities” (R. C. Jeffrey, Ed.), Vol. 2, pp. 251–262, Univ. of California Press, Berkeley, 1980) for a function to be called probabilistic. The logical treatment of probabilities is complicated by two facts: first, that the connectives cannot be interpreted truth-functionally when truth values are regarded as probabilities; second, that negation-free definite-clause-like sentences can be inconsistent when interpreted probabilistically. We address these issues here and propose a formalism for probabilistic reasoning in logic programming. To our knowledge, this is the first probabilistic characterization of logic programming semantics.     

Nonmonotonic logic programming

This paper provides a survey of the state of the art in nonmonotonic logic programming. In particular, it surveys advances in the declarative semantics of logic programs, in query processing procedures for nonmonotonic logic programs, and in recent extensions of the nonmonotonic logic programming paradigm     

Autoepistemic logic programming

An autoepistemic logic programming language is derived from a subset of a three-valued autoepistemic logic, called 3AEL. Autoepistemic programs generalize several ideas underlying logic programming: stable, supported, and well-founded models, Fitting's semantics, Kunen's semantics, and abductive frameworks can all be captured through simple autoepistemic translations; moreover, SLDNF-resolution and a generate-and-test method for stable semantics are generalized to provide sound and complete proof methods for autoepistemic programs. These methods extend existing proof methods for 3AEL. Thus autoepistemic logic programming, besides contributing to the understanding of 3AEL, can be seen as a unifying framework for the theory of logic programs. It should also be regarded as a first step toward a flexible environment where different forms of inference can be formally integrated.This paper is an extended version of [8]. I am grateful to my advisor, Giorgio Levi, to Paolo Mancarella, who read the first version of the paper, and to the anonymous referees, whose comments led to sensible improvements.     

Support logic programming

This article describes a support logic programming system which uses a theory of support pairs to model various forms of uncertainty. It should find application to designing expert systems and is of a query language type like Prolog. Uncertainty associated with facts and rules is represented by a pair of supports and uses ideas from Zadeh's fuzzy set theory and Shafer's evidence theory. A calculus is derived for such a system and various models of interpretation given. the article provides a form of knowledge representation and inference under uncertainty suitable for expert systems and a closed world assumption is not assumed. Facts not in the knowledge base are uncertain rather than assumed to be false.     

Relevant logic programming

In this paper we present a fragment of (positive) relevant logic which can be computed by a straightforward extension to SLD resolution while allowing full nesting of implications. These two requirements lead quite naturally to a fragment in which the major feature is an ambiguous user-level conjunction which is interpreted intensionally in query positions and extensionally in assertion positions. These restrictions allow a simple and efficient extension to SLD resolution (and more particularly, the PROLOG evaluation scheme) with quite minor loss in expressive power.     

Inductive genetic programming with decision trees

This article proposes a study of inductive Genetic Programming with Decision Trees (GPDT). The theoretical underpinning is an approach to the development of fitness functions for improving the search guidance. The approach relies on analysis of the global fitness landscape structure with a statistical correlation measure. The basic idea is that the fitness landscape could be made informative enough to enable efficient search navigation. We demonstrate that by a careful design of the fitness function the global landscape becomes smoother, its correlation increases, and facilitates the search. Another claim is that the fitness function has not only to mitigate navigation difficulties, but also to guarantee maintenance of decision trees with low syntactic complexity and high predictive accuracy.     

Neural fuzzy logic programming

A foundational development of propositional fuzzy logic programs is presented. Fuzzy logic programs are structured knowledge bases including uncertainties in rules and facts. The precise specifications of uncertainties have a great influence on the performance of the knowledge base. It is shown how fuzzy logic programs can be transformed to neural networks, where adaptations of uncertainties in the knowledge base increase the reliability of the program and are carried out automatically.     

Beyond multi-adjoint logic programming

In ‘multi-adjoint logic programming’, MALP in brief, each fuzzy logic program is associated with its own ‘multi-adjoint lattice’ for modelling truth degrees beyond the simpler case of true and false, where a large set of fuzzy connectives can be defined. On this wide repertoire, it is crucial to connect each implication symbol with a proper conjunction thus conforming constructs of the form (←_i, &_i) called ‘adjoint pairs’, whose use directly affects both declarative and operational semantics of the MALP framework. In this work, we firstly show how the strong dependence of adjoint pairs can be largely weakened for an interesting ‘sub-class’ of MALP programs. Then, we reason in a similar way till conceiving a ‘super-class’ of fuzzy logic programs beyond MALP, which definitively drops out the need for using adjoint pairs, since the new semantics behaviour relies on much more relaxed lattices than multi-adjoint ones.     

Set based logic programming

In a previous paper (Blair et al. 2001), the authors showed that the mechanism underlying Logic Programming can be extended to handle the situation where the atoms are interpreted as subsets of a given space X. The view of a logic program as a one-step consequence operator along with the concepts of supported and stable model can be transferred to such situations. In this paper, we show that we can further extend this paradigm by creating a new one-step consequence operator by composing the old one-step consequence operator with a monotonic idempotent operator (miop) in the space of all subsets of X, 2 ^X . We call this extension set based logic programming. We show that such a set based formalism for logic programming naturally supports a variety of options. For example, if the underlying space has a topology, one can insist that the new one-step consequence operator always produces a closed set or always produces an open set. The flexibility inherent in the semantics of set based logic programs is due to both the range of natural choices available for specifying the semantics of negation, as well as the role of monotonic idempotent operators (miops) as parameters in the semantics. This leads to a natural type of polymorphism for logic programming, i.e. the same logic program can produce a variety of outcomes depending on the miop associated with the semantics. We develop a general framework for set based programming involving miops. Among the applications, we obtain integer-based representations of real continuous functions as stable models of a set based logic program.      

Temporal disjunctive logic programming

In this paper we introduce the logic programming languageDisjunctive Chronolog which combines the programming paradigms of temporal and disjunctive logic programming. Disjunctive Chronolog is capable of expressing dynamic behaviour as well as uncertainty, two notions that are very common in a variety of real systems. We present the minimal temporal model semantics and the fixpoint semantics for the new programming language and demonstrate their equivalence. We also show how proof procedures developed for disjunctive logic programs can be easily extended to apply to Disjunctive Chronolog programs. Manolis Gergatsoulis, Ph.D.: He received his B.Sc. in Physics in 1983, the M.Sc. and the Ph.D. degrees in Computer Science in 1986 and 1995 respectively all from the University of Athens, Greece. Since 1996 he is a Research Associate in the Institute of Informatics and Telecommunications, NCSR ‘Demokritos’, Athens. His research interests include logic and temporal programming, program transformations and synthesis, as well as theory of programming languages. Panagiotis Rondogiannis, Ph.D.: He received his B.Sc. from the Department of Computer Engineering and Informatics, University of Patras, Greece, in 1989, and his M.Sc. and Ph.D. from the Department of Computer Science, University of Victoria, Canada, in 1991 and 1994 respectively. From 1995 to 1996 he served in the Greek army. From 1996 to 1997 he was a visiting professor in the Department of Computer Science, University of Ioannina, Greece, and since 1997 he is a Lecturer in the same Department. In January 2000 he was elected Assistant Professor in the Department of Informatics at the University of Athens. His research interests include functional, logic and temporal programming, as well as theory of programming languages. Themis Panayiotopoulos, Ph.D.: He received his Diploma on Electrical Engineering from the Department of Electrical Engineering, National Technical Univesity of Athens, in 1984, and his Ph.D. on Artificial Intelligence from the above mentioned department in 1989. From 1991 to 1994 he was a visiting professor at the Department of Mathematics, University of the Aegean, Samos, Greece and a Research Associate at the Institute of Informatics and Telecommunications of “Democritos” National Research Center. Since 1995 he is an Assistant Prof. at the Department of Computer Science, University of Piraeus. His research interests include temporal programming, logic programming, expert systems and intelligent agent architectures.     

Tableaux for logic programming

We present a logic programming language, which we call Proflog, with an operational semantics based on tableaux and a denotational semantics based on supervaluations. We show the two agree. Negation is well behaved, and semantic noncomputability issues do not arise. This is accomplished essentially by dropping a domain closure requirement. The cost is that intuitions developed through the use of classical logic may need modification, though the system is still classical at a level once removed. Implementation problems are discussed very briefly; the thrust of the paper is primarily theoretical.Research partly supported by NSF Grant CCR-9104015.     

Integrating answer set programming and constraint logic programming

We introduce a knowledge representation language ${\cal AC(C)}$ extending the syntax and semantics of ASP and CR-Prolog, give some examples of its use, and present an algorithm, $\mathcal{AC}\!solver$ , for computing answer sets of ${\cal AC(C)}$ programs. The algorithm does not require full grounding of a program and combines “classical” ASP solving methods with constraint logic programming techniques and CR-Prolog based abduction. The ${\cal AC(C)}$ based approach often allows to solve problems which are impossible to solve by more traditional ASP solving techniques. We believe that further investigation of the language and development of more efficient and reliable solvers for its programs can help to substantially expand the domain of applicability of the answer set programming paradigm.     

Translations and similarity-based logic programming

In order to provide approximate reasoning capabilities, in Gerla G, Sessa MI (1999) Chen G, Ying M, Cai K-Y (Eds) Fuzzy Logic and Soft computing, 19–31, Kluwer Academic Publishers, Boston an extension of Logic Programming has been proposed. Logic programs on function-free languages are considered, and approximate and imprecise information are represented by introducing a similarity relation ? in the set of predicate names and object names of the language. The inference system exploits the classical resolution rule of the Logic Programming paradigm. Moreover, the notion of fuzzy least Herbrand model is also provided. In this paper, by introducing the general notion of structural translation of languages, we generalize these results to the case of logic programs with function symbols. Some properties of the similarity relations are also proven.