Tese de mestrado integrado. Engenharia Informática e Computação. Faculdade de Engenharia. Universidade do Porto. 2010

We investigate principles of rationality based on symmetry in Polyadic Pure Inductive Logic. The aim of Pure Inductive Logic (PIL) is to determine how to assign probabilities to sentences of a language being true in some structure on the basis of rational considerations. This thesis centres on principles arising from instances of symmetry for sentences of first-order polyadic languages. We begin with the recently introduced Permutation Invariance Principle (PIP), and find that it is determined by a finite number of permutations on a finite set of formulae. We test the consistency of PIP with established principles of the subject and show, in particular, that it is consistent with Super Regularity. We then investigate the relationship between PIP and the two main polyadic principles thus far, Spectrum Exchangeability and Language Invariance, and discover there are close connections. In addition, we define the key notion of polyadic atoms as the building blocks of polyadic languages. We explore polyadic generalisations of the unary principle of Atom Exchangeability and prove that PIP is a natural extension of Atom Exchangeability to polyadic languages. In the second half of the thesis we investigate polyadic approaches to the unary version of Constant Exchangeability as invariance under signatures. We first provide a theory built on polyadic atoms (for binary and then general languages). We introduce the notion of a signature for non-unary languages, and principles of invariance under signatures, independence, and instantial relevance for this context, as well as a binary representation theorem. We then develop a second approach to these concepts using elements as alternative building blocks for polyadic languages. Finally, we introduce the concepts of homomorphisms and degenerate probability functions in Pure Inductive Logic. We examine which of the established principles of PIL are preserved by these notions, and present a method for reducing probability functions on general polyadic languages to functions on binary languages.

This thesis investigates ways of incorporating reasoning by analogy into Pure (Unary) Inductive Logic. We start with an analysis of similarity as distance, noting that this is the conception that has received most attention in the literature so far. Chapter 4 looks in some detail at the consequences of adopting Hamming Distance as our measure of similarity, which proves to be a strong requirement. Chapter 5 then examines various adaptations of Hamming Distance and proposes a subtle modification, further-away-ness, that generates a much larger class of solutions.

We investigate the Principle of Predicate Exchangeability in the framework of Pure Inductive Logic. While this principle was known to Rudolf Carnap, who started research in Inductive Logic, the principle has been somewhat neglected in the past. After providing the framework of Pure Inductive Logic, we will show Representation Theorems for probability functions satisfying Predicate Exchangeability, filling the gap in the list of Representation Theorems for functions satisfying certain rational principles. We then introduce a new principle, called the Principle of Strong Predicate Exchangeability, which is weaker than the well-known Principle of Atom Exchangeability, but stronger than Predicate Exchangeability and give examples of functions that satisfy this principle. Finally, we extend the framework of Inductive Logic to Second Order languages, which allows for increasing a rational agent’s expressive strength. We introduce Wilmers’ Principle, a rational principle that rational agents might want to adopt in this extended framework, and give a representation theorem for this principle.

La programmation par contraintes permet de modéliser des problèmes et offre des méthodes de résolution efficaces. Cependant, sa complexité augmentant ces dernières années, son utilisation, notamment pour modéliser des problèmes, est devenue limitée à des utilisateurs possédant une bonne expérience dans le domaine. Cette thèse s’inscrit dans un cadre visant à automatiser la modélisation. Les techniques existantes ont montré des résultats encourageants mais certaines exigences rendent leur utilisation encore problématique. Dans une première partie, nous proposons de dépasser une limite existante qui réside dans la nécessité pour l’utilisateur de fournir des solutions du problème qu’il veut modéliser. En remplacement, il nous fournit des solutions de problèmes proches, c’est-à-dire de problèmes dont la sémantique de fond est la même mais dont les variables et leur domaine peuvent changer. Pour exploiter de telles données, nous proposons d’acquérir, grâce à des techniques de programmation logique inductive, un modèle plus abstrait que le réseau de contraintes. Une fois appris, ce modèle est ensuite transformé pour correspondre au problème initial que souhaitait résoudre l’utilisateur. Nous montrons également que la phase d’apprentissage se heurte à des limites pathologiques et qui nous ont contraints à développer un nouvel algorithme pour synthétiser ces modèles abstraits. Dans une seconde partie, nous nous intéressons à la possibilité pour l’utilisateur de ne pas donner d’exemples du tout. En partant d’un CSP sans aucune contrainte, notre méthode consiste à résoudre le problème de l’utilisateur de manière classique. Grâce à un arbre de recherche, nous affectons progressivement des valeurs aux variables. Quand notre outil ne peut décider si l’affectation partielle courante est correcte ou non, nous demandons à l’utilisateur de guider la recherche sous forme de requêtes. Ces requêtes permettent de trouver des contraintes à ajouter aux modèles du CSP et ainsi améliorer la recherche. / Constraint programming allows to model many kind of problems with efficient solving methods. However, its complexity has increased these last years and its use, notably to model problems, has become limited to people with a fair expertise in the domain. This thesis deals with automating the modeling task in constraint programming. Methods already exist, with encouraging results, but many requirements are debatable. In a first part, we propose to avoid the limitation consisting, for the user, in providing solutions of the problem she aims to solve. As a replacement of these solutions, the user has to provide solutions of closed problem, i.e problem with same semantic but where variables and domains can be different. To handle this kind of data, we acquire, thanks to inductive logic programming, a more abstract model than the constraint network. When this model is learned, it is translated in the very constraint network the user aims to model. We show the limitations of learning method to build such a model due to pathological problems and explain the new algorithm we have developed to build these abstract models. In a second part, we are interesting in the possibility to the user to not provide any examples. Starting with a CSP without constraints, our method consists in solving the problem the user wants in a standard way. Thanks to a search tree, we affect to each variable a value. When our tool cannot decide if the current partial affectation is correct or not, we ask to the user, with yes/no queries, to guide the search. These queries allow to find constraints to add to the model and then to improve the quality of the search.

In the past decade, fast advancements have been made in the sequencing, digitalization and collection of the biological data. However the bottleneck remains at the point of analysis and extraction of patterns from the data. We have developed a method that is aimed at widening this bottleneck by automating the knowledge extraction from the biological data. Our approach is aimed at discovering patterns in a set of DNA sequences based on the location of transcription factor binding sites or any other biological markers with the emphasis of discovering relationships. A variety of statistical and computational methods exists to analyze such data. However, they either require an initial hypothesis, which is later tested, or classify the data based on its attributes. Our approach does not require an initial hypothesis and the classification it produces is based on the relationships between attributes. The value of such approach is that is is able to uncover new knowledge about the data by inducing a general theory based on basic known rules. The core of our approach lies in an inductive logic programming engine, which, based on positive and negative examples as well as background knowledge, is able to induce a descriptive, human-readable theory, describing the data. An application provides an end-to-end analysis of DNA sequences. A simple to use Web interface accepts a set of related sequences to be analyzed, set of negative example sequences to contrast the main set (optional), and a set of possible genetic markers as position-specific scoring matrices. A Java-based backend formats the sequences, determines the location of the genetic markers inside them and passes the information to the ILP engine, which induces the theory. The model, assumed in our background knowledge, is a set of basic interactions between biological markers in any DNA sequence. This makes our approach applicable to analyze a wide variety of biological problems, including detection of cis-regulatory modules and analysis of ChIP-Sequencing experiments. We have evaluated our method in the context of such applications on two real world datasets as well as a number of specially designed synthetic datasets. The approach has shown to have merit even in situations when no significant classification could be determined.

In the past decade, fast advancements have been made in the sequencing, digitalization and collection of the biological data. However the bottleneck remains at the point of analysis and extraction of patterns from the data. We have developed a method that is aimed at widening this bottleneck by automating the knowledge extraction from the biological data. Our approach is aimed at discovering patterns in a set of DNA sequences based on the location of transcription factor binding sites or any other biological markers with the emphasis of discovering relationships. A variety of statistical and computational methods exists to analyze such data. However, they either require an initial hypothesis, which is later tested, or classify the data based on its attributes. Our approach does not require an initial hypothesis and the classification it produces is based on the relationships between attributes. The value of such approach is that is is able to uncover new knowledge about the data by inducing a general theory based on basic known rules. The core of our approach lies in an inductive logic programming engine, which, based on positive and negative examples as well as background knowledge, is able to induce a descriptive, human-readable theory, describing the data. An application provides an end-to-end analysis of DNA sequences. A simple to use Web interface accepts a set of related sequences to be analyzed, set of negative example sequences to contrast the main set (optional), and a set of possible genetic markers as position-specific scoring matrices. A Java-based backend formats the sequences, determines the location of the genetic markers inside them and passes the information to the ILP engine, which induces the theory. The model, assumed in our background knowledge, is a set of basic interactions between biological markers in any DNA sequence. This makes our approach applicable to analyze a wide variety of biological problems, including detection of cis-regulatory modules and analysis of ChIP-Sequencing experiments. We have evaluated our method in the context of such applications on two real world datasets as well as a number of specially designed synthetic datasets. The approach has shown to have merit even in situations when no significant classification could be determined.

In the past decade, fast advancements have been made in the sequencing, digitalization and collection of the biological data. However the bottleneck remains at the point of analysis and extraction of patterns from the data. We have developed a method that is aimed at widening this bottleneck by automating the knowledge extraction from the biological data. Our approach is aimed at discovering patterns in a set of DNA sequences based on the location of transcription factor binding sites or any other biological markers with the emphasis of discovering relationships. A variety of statistical and computational methods exists to analyze such data. However, they either require an initial hypothesis, which is later tested, or classify the data based on its attributes. Our approach does not require an initial hypothesis and the classification it produces is based on the relationships between attributes. The value of such approach is that is is able to uncover new knowledge about the data by inducing a general theory based on basic known rules. The core of our approach lies in an inductive logic programming engine, which, based on positive and negative examples as well as background knowledge, is able to induce a descriptive, human-readable theory, describing the data. An application provides an end-to-end analysis of DNA sequences. A simple to use Web interface accepts a set of related sequences to be analyzed, set of negative example sequences to contrast the main set (optional), and a set of possible genetic markers as position-specific scoring matrices. A Java-based backend formats the sequences, determines the location of the genetic markers inside them and passes the information to the ILP engine, which induces the theory. The model, assumed in our background knowledge, is a set of basic interactions between biological markers in any DNA sequence. This makes our approach applicable to analyze a wide variety of biological problems, including detection of cis-regulatory modules and analysis of ChIP-Sequencing experiments. We have evaluated our method in the context of such applications on two real world datasets as well as a number of specially designed synthetic datasets. The approach has shown to have merit even in situations when no significant classification could be determined.

Σε αυτήν την εργασία μελετάται ο Επαγωγικός Λογικός Προγραμματισμός μέσα απο το πρίσμα της μάθησης της Γραμματικής της αγγλικής γλώσσας. Ο λόγος που επιλέχθηκε αυτό το πρόβλημα είναι ότι εξομοιώνει, μέχρι ενός σγημείου, τον τρόπο που τα παιδιά μαθαίνουν να μιλούν κάποια γλώσσα, υπό την έννοια ότι μαθαίνουν να μιλάνε χωρίς να έρθουν σε επαφή με τους κανόνες – τη γραμματική – της γλώσσας, αλλά από την επαφή τους με τα με τα ερεθίσματα – τα παραδείγματα – που έχουν από τον περίγυρό τους. / This paper is about Inductive Logic Programming through the prism of a problem. In our case Grammar Learning.

We propose and investigate several new principles of rational reasoning within the framework of Pure Inductive Logic, PIL, where probability functions defined on the sentences of a first-order language are used to model an agent's beliefs. The Elephant Principle is concerned with how learning, modelled by conditioning, may be uniquely `remembered'. The Perspective Principle requires that, from a given prior, conditioning on statistically similar experiences should result in similar assignments, and is found to be a necessary condition for Reichenbach's Axiom to hold. The Abductive Inference Principle and some variations are proposed as possible formulations of a restriction of C.S. Peirce's notion of hypothesis in the context of PIL, though characterization results obtained for these principles suggest that they may be too strong. The Finite Values Property holds when a probability function takes only finitely many values when restricted to sentences containing only constant symbols from some fixed finite set. This is shown to entail a certain systematic method of assigning probabilities in terms of possible worlds, and it is considered in this light as a possible principle of inductive reasoning. Classification results are given, stating which members of certain established families of probability functions satisfy each of these new principles. Additionally, we define the theory of a principle P of PIL to be the set of those sentences which are assigned probability 1 by every probability function which satisfies P. We investigate the theory of the established principle of Spectrum Exchangeability by finding separately the theories of heterogeneous and homogeneous functions. The theory of Spectrum Exchangeability is found to be equal to the theory of finite structures. The theory of Johnson's Sufficientness Postulate is also found. Consequently, we find that Spectrum Exchangeability, Johnson's Sufficientness Postulate and the Finite Values Property are all inconsistent with the principle of Super-Regularity: that any consistent sentence should be assigned non-zero probability.