Scalable Probabilistic Inductive Logic Programming for Big Data

La dimensione dei dati disponibili su Internet e in vari campi è in costante aumento. Questo porta al fenomeno cosidetto big data. Poiché questi dati provengono da fonti diverse e sono eterogenei, sono intrinsecamente caratter- izzati da incompletezza e/o incertezza. Per gestire tali dati, i sistemi devono essere non solo in grado di rappresentare l’incertezza, ma anche abbastanza scalabili per gestire dati in costante aumento. I sistemi basati sulla logica forniscono potenti strumenti per rappresentare, ragionare e apprendere dai dati caratterizzati da incertezza. La Semantica distribuzionale (SD) è un formal- ismo ben noto per rappresentare dati caratterizzati da incertezza. Fornisce un potente strumento per combinare logica e probabilità. Programmi che seguono questo formalismo sono chiamati Programmi Logici Probabilistici (PLP). Molti linguaggi seguono la SD, come i Programmi Logici con Disgiunzioni Annotate (PLDA) e ProbLog. Inoltre, sono stati implementati sistemi all’avanguardia per l’apprendimento dei parametri, EMBLEM e LFI-ProbLog, e della struttura, SLIPCOVER e ProbFOIL+ di programmi in tali linguaggi. Questi sistemi offrono buone prestazioni in termini di accuratezza ma soffrono ancora di prob- lemi di scalabilità. In questa tesi, affrontiamo questi problemi proponendo due linguaggi sotto la SD in cui il ragionamento e l’apprendimento sono veloci. Innanzitutto proponiamo un linguaggio, chiamato Liftable Probabilistic Logic Programs (LPLP), in cui l’inferenza è eseguita ad alto livello, cioè gruppi di individui sono considerati complessivamente anziché uno per uno. Poi proponiamo l’algoritmo, LIFTCOVER per LIFTed slipCOVER, che apprende la struttura di LPLP dai dati. Due versioni di LIFTCOVER sono state proposte: il primo, LIFTCOVER-EM, utilizza l’algoritmo Expectation Maximization (EM) come sub-routine per l’apprendimento dei parametri e il secondo, LIFTCOVER- LBFGS, utilizza un metodo di ottimizzazione chiamato BFGS a memoria limitata. Nella seconda parte presentiamo un’estensione del linguaggio LPLP, chiam- ato Hierarchical Probabilistic Logic Programs (HPLP), in cui le clausole e i predicati sono organizzati gerarchicamente. Un programma in questa linguaggio può essere convertito in una serie di Circuiti Aritmetici (CA) o reti neurali profonde e l’inferenza viene fatta valutando gli CA. La tesi descrive come eseguire l’inferenza e l’apprendimento negli HPLP. Per apprendere i parametri degli HPLP dai dati, abbiamo proposto l’algoritmo, Parameter learning for HIerarchical probabilistic Logic programs (PHIL). Due varianti di PHIL, Deep PHIL (DPHIL) ed EM PHIL (EMPHIL) e le loro versioni regolarizzate sono state presentate. Inoltre, abbiamo proposto l’algoritmo SLEAHP, per Structure LEArning of Hierarchical Probabilistic logic programming, per apprendere sia la struttura che i parametri di HPLP dai dati. Tutti questi algoritmi sono stati esperimentati su problemi del mondo reale e le loro prestazioni, in termini di tempo, sono migliori dello stato dell’arte ottenendo soluzioni di qualità paragonabile.

The size of the data available on the Internet and in various fields is constantly increasing. This lead to the phenomenon called big data. Since these data come from different sources and are heterogeneous, they are intrinsically characterized by incompleteness and/or uncertainty. In order to manage such data, systems have to be not only able to represent uncertainty but also scalable enough to deal with ever-increasing data. Systems based on logic provide powerful tools for representing, reasoning and learning from data characterized by uncertainty. The Distributions Semantics (DS) is a well known formalism for representing data characterized by uncertainty. It provides a powerful tool for combining logic and probability. Programs following this formalism are called Probabilistic Logic Programs (PLPs). Many languages follow the DS, such as Logic Program with Annotated Disjunctions (LPADs) and ProbLog. Moreover, state of the art systems for learning either the parameters, EMBLEM and LFI-ProbLog, or the structure, SLIPCOVER and ProbFOIL+, have been implemented. These systems provide good performance in terms of accuracy but still suffer from scalability problems. In this thesis, we address these problems by proposing two languages under the DS in which reasoning and learning are cheaper. We first present a language, Liftable Probabilistic Logic Programs (LPLPs), in which inference is performed at a lifted level, i.e groups of individuals are considered as a whole instead of one by one. Then we propose the algorithm, LIFTCOVER for LIFTed slipCOVER, that learns the structure of LPLPs from data. Two versions of LIFTCOVER are proposed: the first, LIFTCOVER- EM, uses the Expectation Maximization (EM) algorithm as a sub-routine for parameter learning and the second, LIFTCOVER-LBFGS, uses an optimization method called Limited memory BFGS. In the second part we present an extension of the language of LPLPs, called Hierarchical Probabilistic Logic Programs (HPLPs), in which clauses and predicates are hierarchically organized. A program in this language can be converted to a set of Arithmetic Circuits (ACs) or deep neural networks and inference is done by evaluating the ACs. We describe how to perform inference and learning in HPLPs. To learn the parameters of HPLPs from data, we propose the algorithm, Parameter learning for HIerarchical probabilistic Logic programs (PHIL). Two variants of PHIL, Deep PHIL (DPHIL) and EM PHIL (EMPHIL), and their regularized versions are presented. We also propose an algorithm, SLEAHP for Structure LEArning of Hierarchical Probabilistic logic programming, for learning both the structure and the parameters of HPLPs from data. All these algorithms were tested on real world problems and their perfor- mances, in terms of time, were better than the state of the art while obtaining solutions of comparable quality.