La ricerca si occuperà di studiare metodologie che permetteranno di sviluppare modelli di apprendimento automatico per una particolare classe di dati, gli alberi, che viene utilizzata per rappresentare efficacemente relazioni gerarchiche nei contenuti digitali.

PI: Davide Bacciu

Dipartimento: Dipartimento di Informatica
Data inizio: 23/09/2015
Data fine: 23/09/2018 (prorogato di 12 mesi: 23/09/2019)
Durata: 36 mesi
Costo del progetto: 318.560 €
Finanziamento ministeriale: 318.560 €

Abstract

A tree provides an effective representation of hierarchical composite data: it allows describing both the atomic information units as well as how they interact and relate to form the compound. Hierarchically structured information is commonly found as the result of natural and artificial processes. The availability of methodological instruments for the adaptive processing of tree data is of paramount importance to realize flexible and innovative applications. This has motivated a considerable research effort in Machine Learning (ML) for structured data which has yielded to the development of several adaptive models for classification, regression, and clustering of trees, with impacting applications, e.g., in chemistry, biology and natural language processing.

Nevertheless, a fundamental research question has been left open and mostly unexplored: learning non-isomorph tree transductions. A transduction manipulates the relational knowledge underlying structured data to transform an input tree into a new piece of (dependant) structured information. It characterizes as a generalization of supervised learning to the structured domain, where the target tree represents the prediction associated to the input tree. Non-isomorph transductions are the most complex and general form of tree transformations. They place no constraints on the properties of the input and target structures which are allowed to have different sizes and connectivity patterns.

The ultimate LIST-IT objective is the design and development of the first ML approach to learning non-isomorph structured transductions from unconstrained pairs of tree data. Approaches in literature are either limited to isomorph transformations (equivalent to simple node relabeling) or they rely on the availability of a pre-defined structural alignment between the input and target trees, such as in synchronous grammars. LIST-IT addresses these limitations by putting forward an innovative approach based on the composition of probabilistic tree models within a joint generative process. It seeks flexible and generalizable transductions by composing the generative process of an input-driven Markov model with the expressivity of a mixture of trees distribution. The former captures the structural properties of the input trees into the Markov state space, while its hidden states generate the parameters of the mixture distributions encoding the output trees. Non-parametric Bayesian techniques are used to enhance generality of the generative process.

LIST-IT is expected to introduce methodological advancements that will open new scientific perspectives in terms of ML models for graphs transduction. These are also intended to have a ground-breaking impact on the next generation of AI, machine vision and information retrieval applications. The ability to effectively process the textual and visual content in its structured representation is bound to be essential for the success of these applications. LIST-IT will provide the essential learning machinery to model and efficiently address the computational challenges underpinning such applications through the use of non-isomorph tree transductions. By allowing a complete data-driven acquisition of general classes of non-isomorph transductions, LIST-IT models will allow surpassing legacy non-adaptive solutions relying on the availability of costly, human-defined procedural knowledge.

Two impacting real-world applications will serve to measure LIST-IT impact and performance
- addressing question-answering task by learning parse tree transductions;
- visual content annotation by multi-modal transductions between hierarchical image representations and annotation parse trees (see image).
Applications will avail of off-the-shelf components to generate structured representation, e.g. image Treebank repository, NLP and image parsers. A LIST-IT toolkit will be openly available to foster research in the area and promote project visibility.