Learning on relational data is a relevant task in the machine learning community. Extracting information from structured data is a non-trivial task due to the combinatorial complexity of the domain and the necessity to construct methods that work on collections of values of different sizes rather than fixed representations. Relational data can naturally be interpreted as graphs, a class of flexible and expressive structures that can model data from diverse domains,from biology to social interactions. Graphs have been used in a huge variety of contexts, such as molecular modelling, social networks, image processing and recommendation systems. In this manuscript, we tackle some challenges in learning on relational data by developing new learning methodologies. Specifically, in our first contribution, we introduce a new class of metrics for relational data based on relational features extraction technique called Type ExtensionTrees. This class of metrics defines the (dis)similarity of two nodes in a graph by exploiting the nested structure of their relational neighborhood at different depth steps. In our second contribution, we developed a new strategy to collect the information of multisets of data values by introducing a new framework of learnable aggregators called Learning Aggregation Functions.We provide a detailed description of the methodologies and an extensive experimental evaluation on synthetic and real world data to assess the expressiveness of the proposed models. A particular focus is given to the application of these methods to the recommendation systems domain, exploring the combination of the proposed methods with recent techniques developed for Constructive Preference Elicitation and Group Recommendation tasks.

Linked Data (LD) follows the web in providing low barriers to publication, and in deploying web-scale keyword search as a central way of identifying relevant data. As in the web, searchesinitially identify results in broadly the form in which they were published, and the published form may be provided to the user as the result of a search. This will be satisfactory in some cases, but the diversity of publishers means that the results of the search may be obtained from many different sources, and described in many different ways. As such, there seems to bean opportunity to add value to search results by providing userswith an integrated representation that brings together features from different sources. This involves an on-the-fly and automated data integration process being applied to search results, which raises the question as to what technologies might bemost suitable for supporting the integration of LD searchresults. In this thesis we take the view that the problem of integrating LD search results is best approached by assimilating different forms ofevidence that support the integration process. In particular, thisdissertation shows how Statistical Relational Learning (SRL) formalisms (viz., Markov Logic Networks (MLN) and Probabilistic Soft Logic (PSL)) can beexploited to assimilate different sources of evidence in a principledway and to beneficial effect for users. Specifically, in this dissertation weconsider syntactic evidence derived from LD search results and from matching algorithms, semantic evidence derived from LD vocabularies, and user evidence,in the form of feedback. This dissertation makes the following key contributions: (i) a characterisation of key features of LD search results that are relevant to their integration, and a description of some initial experiences in the use of MLN for interpreting search results; (ii)a PSL rule-base that models the uniform assimilation of diverse kinds of evidence;(iii) an empirical evaluation of how the contributed MLN and PSL approaches perform in terms of their ability to infer a structure for integrating LD search results;and (iv) concrete examples of how populating such inferred structures for presentation to the end user is beneficial, as well as guiding the collection of feedbackwhose assimilation further improves search results presentation.

abstract: Knowledge Representation (KR) is one of the prominent approaches to Artificial Intelligence (AI) that is concerned with representing knowledge in a form that computer systems can utilize to solve complex problems. Answer Set Programming (ASP), based on the stable model semantics, is a widely-used KR framework that facilitates elegant and efficient representations for many problem domains that require complex reasoning. However, while ASP is effective on deterministic problem domains, it is not suitable for applications involving quantitative uncertainty, for example, those that require probabilistic reasoning. Furthermore, it is hard to utilize information that can be statistically induced from data with ASP problem modeling. This dissertation presents the language LP^MLN, which is a probabilistic extension of the stable model semantics with the concept of weighted rules, inspired by Markov Logic. An LP^MLN program defines a probability distribution over "soft" stable models, which may not satisfy all rules, but the more rules with the bigger weights they satisfy, the bigger their probabilities. LP^MLN takes advantage of both ASP and Markov Logic in a single framework, allowing representation of problems that require both logical and probabilistic reasoning in an intuitive and elaboration tolerant way. This dissertation establishes formal relations between LP^MLN and several other formalisms, discusses inference and weight learning algorithms under LP^MLN, and presents systems implementing the algorithms. LP^MLN systems can be used to compute other languages translatable into LP^MLN. The advantage of LP^MLN for probabilistic reasoning is illustrated by a probabilistic extension of the action language BC+, called pBC+, defined as a high-level notation of LP^MLN for describing transition systems. Various probabilistic reasoning about transition systems, especially probabilistic diagnosis, can be modeled in pBC+ and computed using LP^MLN systems. pBC+ is further extended with the notion of utility, through a decision-theoretic extension of LP^MLN, and related with Markov Decision Process (MDP) in terms of policy optimization problems. pBC+ can be used to represent (PO)MDP in a succinct and elaboration tolerant way, which enables planning with (PO)MDP algorithms in action domains whose description requires rich KR constructs, such as recursive definitions and indirect effects of actions. / Dissertation/Thesis / Doctoral Dissertation Computer Science 2019

In this dissertation, I explored relational learning via latent variable models. Traditional machine learning algorithms cannot handle many learning problems where there is a need for modeling both relations and noise. Statistical relational learning approaches emerged to handle these applications by incorporating both relations and uncertainties in these problems. Latent variable models are one of the successful approaches for statistical relational learning. These models assume a latent variable for each entity and then the probability distribution over relationships between entities is modeled via a function over latent variables. One important example of relational learning via latent variables is text data modeling. In text data modeling, we are interested in modeling the relationship between words and documents. Latent variable models learn this data by assuming a latent variable for each word and document. The co-occurrence value is defined as a function of these random variables. For modeling co-occurrence data in general (and text data in particular), we proposed latent logistic allocation (LLA). LLA outperforms the-state-of-the-art model --- latent Dirichlet allocation --- in text data modeling, document categorization and information retrieval. We also proposed query-based visualization which embeds documents relevant to a query in a 2-dimensional space. Additionally, I used latent variable models for other single-relational problems such as collaborative filtering and educational data mining. To move towards multi-relational learning via latent variable models, we propose latent feature networks (LFN). Multi-relational learning approaches model multiple relationships simultaneously. LFN assumes a component for each relationship. Each component is a latent variable model where a latent variable is defined for each entity and the relationship is a function of latent variables. However, if an entity participates in more than one relationship, then it will have a separate random variable for each relationship. We used LFN for modeling two different problems: microarray classification and social network analysis with a side network. In the first application, LFN outperforms support vector machines --- the best propositional model for that application. In the second application, using the side information via LFN can drastically improve the link prediction task in a social network.

Many real-world problems involve data that both have complex structures and uncertainty. Statistical relational learning (SRL) is an emerging area of research that addresses the problem of learning from these noisy structured/relational data. Markov logic networks (MLNs), sets of weighted first-order logic formulae, are a simple but powerful SRL formalism that generalizes both first-order logic and Markov networks. MLNs have been successfully applied to a variety of real-world problems ranging from extraction knowledge from text to visual event recognition. Most of the existing learning algorithms for MLNs are in the generative setting: they try to learn a model that is equally capable of predicting the values of all variables given an arbitrary set of evidence; and they do not scale to problems with thousands of examples. However, many real-world problems in structured/relational data are discriminative--where the variables are divided into two disjoint sets input and output, and the goal is to correctly predict the values of the output variables given evidence data about the input variables. In addition, these problems usually involve data that have thousands of examples. Thus, it is important to develop new discriminative learning methods for MLNs that are more accurate and more scalable, which are the topics addressed in this thesis. First, we present a new method that discriminatively learns both the structure and parameters for a special class of MLNs where all the clauses are non-recursive ones. Non-recursive clauses arise in many learning problems in Inductive Logic Programming. To further improve the predictive accuracy, we propose a max-margin approach to learning weights for MLNs. Then, to address the issue of scalability, we present CDA, an online max-margin weight learning algorithm for MLNs. Ater [sic] that, we present OSL, the first algorithm that performs both online structure learning and parameter learning. Finally, we address an issue arising in applying MLNs to many real-world problems: learning in the presence of many hard constraints. Including hard constraints during training greatly increases the computational complexity of the learning problem. Thus, we propose a simple heuristic for selecting which hard constraints to include during training. Experimental results on several real-world problems show that the proposed methods are more accurate, more scalable (can handle problems with thousands of examples), or both more accurate and more scalable than existing learning methods for MLNs. / text

Un réseau logique de Markov est formé de clauses en logique du premier ordre auxquelles sont associés des poids. Cette thèse propose plusieurs méthodes pour l’apprentissage de la structure de réseaux logiques de Markov (MLN) à partir de données relationnelles. Ces méthodes sont de deux types, un premier groupe reposant sur les techniques de propositionnalisation et un second groupe reposant sur la notion de Graphe des Prédicats. L’idée sous-jacente aux méthodes à base de propositionnalisation consiste à construire un jeu de clauses candidates à partir de jeux de littéraux dépendants. Pour trouver de tels jeux, nous utilisons une méthode de propositionnalisation afin de reporter les informations relationnelles dans des tableaux booléens, qui serviront comme tables de contingence pour des test de dépendance. Nous avons proposé deux méthodes de propositionnalisation, pour lesquelles trois algorithmes ont été développés, qui couvrent les problèmes d’appprentissage génératif et discriminant. Nous avons ensuite défini le concept de Graphe des Prédicats qui synthétise les relations binaires entre les prédicats d’un domaine. Des clauses candidates peuvent être rapidement et facilement produites en suivant des chemins dans le graphe puis en les variabilisant. Nous avons développé deux algorithmes reposant sur les Graphes des Prédicats, qui couvrent les problèmes d’appprentissage génératif et discriminant. / A Markov Logic Network is composed of a set of weighted first-order logic formulas. In this dissertation we propose several methods to learn a MLN structure from a relational dataset. These methods are of two kinds: methods based on propositionalization and methods based on Graph of Predicates. The methods based on propositionalization are based on the idea of building a set of candidate clauses from sets of dependent variable literals. In order to find such sets of dependent variable literals, we use a propositionalization technique to transform relational information in the dataset into boolean tables, that are then provided as contingency tables for tests of dependence. Two propositionalization methods are proposed, from which three learners have been developed, that handle both generative and discriminative learning. We then introduce the concept of Graph of Predicates, which synthethises the binary relations between the predicates of a domain. Candidate clauses can be quickly and easily generated by simply finding paths in the graph and then variabilizing them. Based on this Graph, two learners have been developed, that handle both generative and discriminative learning.

A maior parte dos mapas empregados em tarefas de navegação por robôs móveis representam apenas informações espaciais do ambiente. Outros tipos de informações, que poderiam ser obtidos dos sensores do robô e incorporados à representação, são desprezados. Hoje em dia é comum um robô móvel conter sensores de distância e um sistema de visão, o que permitiria a princípio usá-lo na realização de tarefas complexas e gerais de maneira autônoma, dada uma representação adequada e um meio de extrair diretamente dos sensores o conhecimento necessário. Uma representação possível nesse contexto consiste no acréscimo de informação semântica aos mapas métricos, como por exemplo a segmentação do ambiente seguida da rotulação de cada uma de suas partes. O presente trabalho propõe uma maneira de estruturar a informação espacial criando um mapa semântico do ambiente que representa, além de obstáculos, um vínculo entre estes e as imagens segmentadas correspondentes obtidas por um sistema de visão omnidirecional. A representação é implementada por uma descrição relacional do domínio, que quando instanciada gera um campo aleatório condicionado, onde são realizadas as inferências. Modelos que combinam probabilidade e lógica de primeira ordem são mais expressivos e adequados para estruturar informações espaciais em semânticas. / Most maps used in navigational tasks by mobile robots represent only environmental spatial information. Other kinds of information, that might be obtained from the sensors of the robot and incorporated in the representation, are negleted. Nowadays it is common for mobile robots to have distance sensors and a vision system, which could in principle be used to accomplish complex and general tasks in an autonomously manner, given an adequate representation and a way to extract directly from the sensors the necessary knowledge. A possible representation in this context consists of the addition of semantic information to metric maps, as for example the environment segmentation followed by an attribution of labels to them. This work proposes a way to structure the spatial information in order to create a semantic map representing, beyond obstacles, an anchoring between them and the correspondent segmented images obtained by an omnidirectional vision system. The representation is implemented by a domains relational description that, when instantiated, produces a conditional random field, which supports the inferences. Models that combine probability and firstorder logic are more expressive and adequate to structure spatial in semantic information.

A maior parte dos mapas empregados em tarefas de navegação por robôs móveis representam apenas informações espaciais do ambiente. Outros tipos de informações, que poderiam ser obtidos dos sensores do robô e incorporados à representação, são desprezados. Hoje em dia é comum um robô móvel conter sensores de distância e um sistema de visão, o que permitiria a princípio usá-lo na realização de tarefas complexas e gerais de maneira autônoma, dada uma representação adequada e um meio de extrair diretamente dos sensores o conhecimento necessário. Uma representação possível nesse contexto consiste no acréscimo de informação semântica aos mapas métricos, como por exemplo a segmentação do ambiente seguida da rotulação de cada uma de suas partes. O presente trabalho propõe uma maneira de estruturar a informação espacial criando um mapa semântico do ambiente que representa, além de obstáculos, um vínculo entre estes e as imagens segmentadas correspondentes obtidas por um sistema de visão omnidirecional. A representação é implementada por uma descrição relacional do domínio, que quando instanciada gera um campo aleatório condicionado, onde são realizadas as inferências. Modelos que combinam probabilidade e lógica de primeira ordem são mais expressivos e adequados para estruturar informações espaciais em semânticas. / Most maps used in navigational tasks by mobile robots represent only environmental spatial information. Other kinds of information, that might be obtained from the sensors of the robot and incorporated in the representation, are negleted. Nowadays it is common for mobile robots to have distance sensors and a vision system, which could in principle be used to accomplish complex and general tasks in an autonomously manner, given an adequate representation and a way to extract directly from the sensors the necessary knowledge. A possible representation in this context consists of the addition of semantic information to metric maps, as for example the environment segmentation followed by an attribution of labels to them. This work proposes a way to structure the spatial information in order to create a semantic map representing, beyond obstacles, an anchoring between them and the correspondent segmented images obtained by an omnidirectional vision system. The representation is implemented by a domains relational description that, when instantiated, produces a conditional random field, which supports the inferences. Models that combine probability and firstorder logic are more expressive and adequate to structure spatial in semantic information.

Cette thèse se focalise sur l'analyse de données structurées en graphes, un format de données répandu dans le monde réel. Le raisonnement dans ces données est un enjeu clé en apprentissage automatique, avec des applications allant de la classification de nœuds à la prédiction de liens. On distingue deux approches majeures pour le raisonnement dans les données en graphes : l'apprentissage relationnel statistique et l'apprentissage profond. L'apprentissage relationnel statistique construit des modèles graphiques probabilistes, efficaces pour capturer des dépendances complexes et intégrer des connaissances préexistantes, comme les règles logiques. Des méthodes notables incluent les réseaux logiques de Markov et les champs aléatoires conditionnels. L'apprentissage profond, quant à lui, se base sur l'apprentissage de représentations pertinentes des données observées pour une compréhension et un raisonnement rapides. Les réseaux neuronaux pour graphes (GNN) représentent un outil de pointe dans ce domaine. La combinaison de l'apprentissage relationnel statistique et de l'apprentissage profond offre une perspective enrichie sur le raisonnement, promettant un cadre plus robuste et efficace. Cette thèse explore cette combinaison, en développant des méthodes qui intègrent les deux approches. L'apprentissage profond renforce l'efficacité de l'apprentissage et de l'inférence dans l'apprentissage relationnel statistique, tandis que ce dernier affine les prédictions de l'apprentissage profond. Ce cadre intégré est appliqué à un éventail de tâches de raisonnement sur les graphes, démontrant son efficacité et ouvrant la voie à des recherches futures pour des cadres de raisonnement encore plus robustes. / This thesis centers on the analysis of graph-structured data, a ubiquitous data format in the real world. Reasoning within graph-structured data has long been a fundamental problem in machine learning, with applications spanning from node classification to link prediction. There are two principal approaches to tackle reasoning within graph-structured data: statistical relational learning and deep learning. Statistical relational learning techniques construct probabilistic graphical models based on observed data, excelling at capturing intricate dependencies of available evidence while accommodating prior knowledge, such as logic rules. Notable methods include Markov logic networks (MLNs) and conditional random fields (CRFs). In contrast, deep learning models harness the capability to learn meaningful representations from observed data, using these representations to rapidly comprehend and reason over the data. Graph neural networks (GNNs) have emerged as prominent tools in the realm of deep learning, achieving state-of-the-art results across a spectrum of tasks. Statistical relational learning and deep learning offer distinct perspectives on reasoning. Intuitively, combining these paradigms promises to create a more robust framework that inherits expressive power, efficiency, and the ability to model joint dependencies while simultaneously acquiring representations for more effective reasoning. In pursuit of this vision, this thesis explores the concept, developing methods that seamlessly integrate deep learning and statistical relational learning. Specifically, deep learning enhances the efficiency of learning and inference within statistical relational learning, while statistical relational learning, in turn, refines the predictions generated by deep learning to improve the accuracy. This integrated paradigm is applied across a diverse range of reasoning tasks on graphs. Empirical results demonstrate the effectiveness of this paradigm, encouraging further exploration to yield more robust reasoning frameworks.

Several real world tasks involve data that is uncertain and relational in nature. Traditional approaches like first-order logic and probabilistic models either deal with structured data or uncertainty, but not both. To address these limitations, statistical relational learning (SRL), a new area in machine learning integrating both first-order logic and probabilistic graphical models, has emerged in the recent past. The advantage of SRL models is that they can handle both uncertainty and structured/relational data. As a result, they are widely used in domains like social network analysis, biological data analysis, and natural language processing. Bayesian Logic Programs (BLPs), which integrate both first-order logic and Bayesian net- works are a powerful SRL formalism developed in the recent past. In this dissertation, we develop approaches using BLPs to solve two real world tasks – plan recognition and machine reading. Plan recognition is the task of predicting an agent’s top-level plans based on its observed actions. It is an abductive reasoning task that involves inferring cause from effect. In the first part of the dissertation, we develop an approach to abductive plan recognition using BLPs. Since BLPs employ logical deduction to construct the networks, they cannot be used effectively for abductive plan recognition as is. Therefore, we extend BLPs to use logical abduction to construct Bayesian networks and call the resulting model Bayesian Abductive Logic Programs (BALPs). In the second part of the dissertation, we apply BLPs to the task of machine reading, which involves automatic extraction of knowledge from natural language text. Most information extraction (IE) systems identify facts that are explicitly stated in text. However, much of the information conveyed in text must be inferred from what is explicitly stated since easily inferable facts are rarely mentioned. Human readers naturally use common sense knowledge and “read between the lines” to infer such implicit information from the explicitly stated facts. Since IE systems do not have access to common sense knowledge, they cannot perform deeper reasoning to infer implicitly stated facts. Here, we first develop an approach using BLPs to infer implicitly stated facts from natural language text. It involves learning uncertain common sense knowledge in the form of probabilistic first-order rules by mining a large corpus of automatically extracted facts using an existing rule learner. These rules are then used to derive additional facts from extracted information using BLP inference. We then develop an online rule learner that handles the concise, incomplete nature of natural-language text and learns first-order rules from noisy IE extractions. Finally, we develop a novel approach to calculate the weights of the rules using a curated lexical ontology like WordNet. Both tasks described above involve inference and learning from partially observed or incomplete data. In plan recognition, the underlying cause or the top-level plan that resulted in the observed actions is not known or observed. Further, only a subset of the executed actions can be observed by the plan recognition system resulting in partially observed data. Similarly, in machine reading, since some information is implicitly stated, they are rarely observed in the data. In this dissertation, we demonstrate the efficacy of BLPs for inference and learning from incomplete data. Experimental comparison on various benchmark data sets on both tasks demonstrate the superior performance of BLPs over state-of-the-art methods. / text