Tesi di Dottorato

Permanent URI for this communityTesi di Dottorato

Browse

Search Results

Now showing 1 - 10 of 12

Tools and Techniques for Easing the Application of Answer Set Programming
(2018-01-19) Fuscà, Davide; Leone, Nicola; Calimeri, Francesco; Perri, Simona
Answer Set Programming (ASP) is a well-established declarative problem solving paradigm; it features high expressiveness and the ability to deal with incomplete knowledge, so it became widely used in AI and it is now recognized as a powerful tool for knowledge representation and reasoning (KRR). Thanks to the expressive language and the availability of diverse robust systems, Answer Set Programming has recently gained popularity and has been applied fruitfully to a wide range of domains. This made clear the need for proper tools and interoperability mechanisms that ease the development of ASP-based applications. Also, the spreading of ASP from a strictly theoretical ambit to more practical aspects requires additional features for easing the interoperability and integration with other software; furthermore, improving the performance of actual ASP system is crucial for allowing the use of the potential of ASP in new practical contexts. The contribution of this thesis aims at addressing such challenges; we introduce new tools and techniques for easing the application of ASP. In particular, we present EMBASP: a framework for the integration of ASP in external systems for general applications to different platforms and ASP reasoners. The framework features explicit mechanisms for two-way translations between strings recognisable by ASP solvers and objects in the programming language. Furthermore, we define proper means for handling external computations in ASP programs, and implement a proper framework for explicit calls to Python scripts via external atoms into the ASP grounder I-DLV. We also define and implement, into the same system, an additional framework for creating ad-hoc directives for interoperability and make use of it for providing some ready-made ones for the connection with relational and graph databases. Eventually, we work at improving the ASP computation, and present two new ASP systems: DLV2 and I-DLV+MS. DLV2 updates DLV with modern evaluation techniques, combining I-DLV with the solver wasp, while I-DLV+MS is a new ASP system that integrates I-DLV, with an automatic solver selector for inductively choose the best solver, depending on some inherent features of the instantiation produced by I-DLV.
3d web-based parallel applications for the numerical modeling of natural phenomena
(2014-11-28) Parise, Roberto; Leone, Nicola; D'Ambrosio, Donato; Spataro, William
In this thesis, I designed and implemented three new web applications tai- lored for the Cellular Automata (CA) simulation models SCIDDICA-k1, SCIARA-fv3 and ABBAMPAU, making use of the GoogleWeb Toolkit frame- work and WebGL. Moreover, I have contributed to the optimizations of the numerical models mentioned above and I also developed part of a library, called OpenCAL, for developing CA simulation models in C/C++. In this case, my most signi - cant contribution regarded the support given to the parallelization through the OpenCL standard, in order to facilitate with a few lines of codes, the par- allelization for the execution on any device, especially on General Purpose Computation with Graphics Processing Units (GPGPU). The development of the web applications involved the implementation of strategies so that optimizing the server load in the connections' management and enhancing the real time visualization of maps on devices of any kind, even mobile. As regards the OpenCAL library, the tests performed on a test models has shown signi cant performance improvements in terms of speedup, thanks also to the use of some new optimization strategies. In this way, the validity of the use of graphics processing units as alternative to more expensive hardware solutions for the parallelization of CA models has been con rmed.
Computational tasks in answer set programming: algorithms and implementation
(2014-12-01) Dodaro, Carmine; Leone, Nicola; Ricca, Francesco
L’Answer Set Programming (ASP) è un paradigma di programmazione dichiarativa basato sulla semantica dei modelli stabili. L’idea alla base di ASP è di codificare un problema computazionale in un programma logico i cui modelli stabili, anche detti answer set, corrispondono alle soluzioni del problema. L’espressività di ASP ed il numero crescente delle sue applicazioni hanno reso lo sviluppo di nuovi sistemi ASP un tema di ricerca attuale ed importante. La realizzazione di un sistema ASP richiede di implementare soluzioni efficienti per vari task computazionali. Questa tesi si occupa delle problematiche relative alla valutazione di programmi proposizionali, ed in particolare affronta i task di model generation, answer set checking, optimum answer set search e cautious reasoning. La combinazione dei primi due task corrisponde alla computazione degli answer set. Infatti, il task di model generation consiste nel generare dei modelli del programma in input, mentre il task di answer set checking ha il compito di verificare che siano effettivamente modelli stabili. Il primo task è correlato alla risoluzione di formule SAT, ed è implementato -nelle soluzioni moderne- con un algoritmo di backtracking simile al Conflict-Driven Clause Learning (CDCL); il secondo è risolto applicando una riduzione al problema dell’insoddisfacibilità di una formula SAT. In presenza di costrutti di ottimizzazione l’obiettivo di un sistema ASP è l’optimum answer set search, che corrisponde a calcolare un answer set che minimizza il numero di violazioni dei cosiddetti weak constraint presenti nel programma. Il cautious reasoning è il task principale nelle applicazioni dataoriented di ASP, e corrisponde a calcolare un sottoinsieme degli atomi che appartengono a tutti gli answer set di un programma. Si noti che tutti questi task presentano una elevata complessità computazionale. I contributi di questa tesi sono riassunti di seguito: (I) è stato studiato il task di model generation ed è stata proposta per la sua risoluzione una combinazione di tecniche che sono state originariamente utilizzate per risolvere il problema SAT; (II) è stato proposto un nuovo algoritmo per l’answer set checking che minimizza l’overhead dovuto all’esecuzione di chiamate multiple ad un oracolo co-NP. Tale algoritmo si basa su una strategia di valutazione incrementale ed euristiche progettate specificamente per migliorare l’efficienza della risoluzione di tale problema; (III) è stata proposta una famiglia di algoritmi per il calcolo di answer set ottimi di programmi con weak constraint. Tali soluzioni sono state ottenute adattando algoritmi proposti per risolvere il problema MaxSAT; (IV) è stato introdotto un nuovo framework di algoritmi anytime per il cautious reasoning in ASP che estende le proposte esistenti ed include un nuovo algoritmo ispirato a tecniche per il calcolo di backbone di teorie proposizionali. Queste tecniche sono state implementate in wasp 2, un nuovo sistema ASP per programmi proposizionali. L’efficacia delle tecniche proposte e l’efficienza del nuovo sistema sono state valutate empiricamente su istanze utilizzate nella competizioni per sistemi ASP e messe a disposizione sul Web.
Tecniche per la valutazione distribuita di programmi logici
(2014-11-30) Barilaro, Rosamaria; Leone, Nicola; Terracina, Giorgio
Recent developments in IT, and in particular the expansion of networking technologies, have made quite common the availability of software architectures where data sources are distributed across multiple (physically-di erent) sites. As a consequence, the number of applications requiring to e ciently query and reason on natively distributed data is constantly growing. In this thesis we focus on the context in which it is necessary to combine data natively resides on di erent, autonomous and distributed sources and it is appropriate to deal with reasoning task to extract knowledge from the data, via deductive database techniques [1]. The aim is distributed evaluation of logic programs through an optimization strategy that minimizes the cost of the local process and data transmission. We considered that a single logic rule can be seen as a conjunctive query (possibly with negation), whose result must be stored in the head predicate. Then, starting from the conjunctive query optimization techniques, the idea is to extend the best results of these to evaluation of logic programs. In this context the methods based on structural analysis of the queries seem particularly promising. Indeed, logical rules often contain multiple interactions interactions among join variables [2]. In the case of simple queries (acyclic) there are several algorithms that ensure execution time with a polynomial upper bound. Structural methods [3, 4, 5, 6] attempt to propagate the good results of acyclic queries to larger classes of these, whose structure is cyclic, but with a low \degree of cyclicity". The Hypertree Decomposition technique [6] appears to be the most powerful since generalizes strongly all other structural methods and guarantees improved response times for each class of queries. Decomposition can be interpreted as an execution plan for the query, which rst requires the evaluation of the join associated with each cluster, and then requires the processing of the resulting join tree using a bottom-up approach. We used a weighted extension of Hypertree Decomposition [7] that combine structural analysis with evaluation of relevant quantitative information about the data, such as the number of tuples in relations, the selectivity of attributes and so on, and calculates minimum decompositions w.r.t. a cost function. We suitably modi ed this method in order to estimate the cost of data transmission between di erent sites resulting from the distribution of the sources and the correct evaluation of negation in rule bodies. According decomposition the query is transformed into a (tree-like) set of sub-queries which also allows the parallel evaluation of independent sub-query. We used parallel techniques combined with techniques for query optimization. We have adopted DLVDB [8, 9, 10, 11] as core reasoning engine, which allows to evaluate logic programs directly on database and combines appropriately expressive power of logic programming systems and the e cient data management of DBMSs. The interaction with databases is achieved by means ODBC connections, therefore, in case of distributed computing on network it allows to transparently access di erent sources and to express very simply distributed queries. We have implemented a prototype that we used to conduct the experiments. The preliminary results are very encouraging and showed the validity of the approach.
Datalog with existential quantifiers: an optimal trade-off between expressiveness and scalability
(2012-11-11) Veltri, Pierfrancesco; Leone, Nicola; Terracina, Giorgio
Ontologies and rules play a central role in the development of the Semantic Web. Recent research in this context focuses especially on highly scalable formalisms for the Web of Data, which may highly benefit from exploiting database technologies. In particular, Datalog∃ is the natural extension of Datalog, allowing existentially quantified variables in rule heads. This language is highly expressive and enables easy and powerful knowledge-modeling, but the presence of existentially quantified variables makes reasoning over Datalog∃ undecidable, in the general case. The results in this thesis enable powerful, yet decidable and efficient reasoning (query answering) on top of Datalog∃ programs. On the theoretical side, we define the class of parsimonious Datalog∃ programs, and show that it allows of decidable and efficiently-computable reasoning. Unfortunately, we can demonstrate that recognizing parsimony is undecidable. However, we single out Shy, an easily recognizable fragment of parsimonious programs, that significantly extends both Datalog and Linear Datalog∃. Moreover, we show that Shy preserves the same (data and combined) complexity of query answering over Datalog, although the addition of existential quantifiers. On the practical side, we implement a bottom-up evaluation strategy for Shy programs inside the DLV system, enhancing the computation by a number of optimization techniques. The resulting system is called DLV∃– a powerful system for answering conjunctive queries over Shy programs, which is profitably applicable to ontology-based query answering. Moreover, we design a rewriting method extending the well-known Magic-Sets technique to any Datalog∃ program. We demonstrate that our rewriting method preserves query equivalence on Datalog∃, and can be safely applied to Shy programs. We therefore incorporate the Magic- Sets method in DLV∃. Finally, we carry out an experimental analysis assessing the positive impact of Magic-Sets on DLV∃, and the effectiveness of the enhanced DLV∃ system compared to a number of state-of-the-art systems for ontologybased query answering.
Integrated development environment for answer set programming
(2012-11-30) Reale, Kristian; Leone, Nicola; Ricca, Francesco
Answer Set Programming (ASP) is a truly-declarative programming paradigm proposed in the area of non-monotonic reasoning and logic programming. The successful application of ASP in a number of advanced projects, has renewed the interest in ASP-based systems for developing real-world applications. Nonethe- less, to boost the adoption of ASP-based technologies in the scientific commu- nity and especially in industry, it is important to provide effective programming tools, supporting the activities of researchers and implementors, and simplifying user interactions with ASP solvers. In the last few years, several tools for ASP- program development have been proposed, including (more or less advanced) editors and debuggers. However, ASP still lacks an Integrated Development Environment (IDE) supporting the entire life-cycle of ASP development, from (assisted) programs editing to application deployment. In this thesis we present ASPIDE, a comprehensive IDE for ASP. It inte- grates a cutting-edge editing tool (featuring dynamic syntax highlighting, on- line syntax correction, auto-completion, code-templates, quick-fixes, refactoring, etc.) with a collection of user-friendly graphical tools for program composi- tion, debugging, profiling, database access, solver execution configuration and output-handling. A comprehensive feature-wise comparison with existing environments for developing logic programs is also reported in this thesis, which shows that ASPIDE is a step forward in the present state of the art of tools for ASP programs development.
Parallel evaluation of ASP programs:techniques and implementation
(2011-11-30) Sirianni, Marco; Ricca, Francesco; Leone, Nicola
Answer Set Programming (ASP) is a purely declarative programming paradigm based on nonmonotonic reasoning and logic programming. The idea of ASP is to represent a given computational problem by a logic program such that its answer sets correspond to solutions, and then, use an answer set solver to find such solutions. The ASP language is very expressive and allows the representation of high-complexity problems (i.e., every problem in the second level of the polynomial hierarchy); unfortunately, the expressive power of the language comes at the price of an elevated cost of answer set computation. Even if this fact has initially discouraged the development of ASP system, nowadays several implementations are available, and the interest for ASP is growing in the scientific community as well as in the field of industry. In the last few years, significant technological enhancements have been achie- ved in the design of computer architectures, with a move towards the adoption of multi-core microprocessors. As a consequence, Symmetric Multi-Processing (SMP) has become available even on non-dedicated machines. Indeed, at the time of writing, the majority of computer systems and even laptops are equipped with (at least one) dual-core processor. However, in the ASP context, the avail- able systems were not designed to exploit parallel hardware; thus significant improvements can be obtained by developing ASP evaluation techniques that allow the full exploitation of the computational resources offered by modern hardware architectures. The evaluation of ASP programs is traditionally carried out in two steps. In the first step an input program P undergoes the so-called instantiation process, which produces a program P0 semantically equivalent to P but not containing any variable; in turn, P0 is evaluated by using a backtracking search algorithm in the second step. The aim of this thesis is the design and the assessment of a number of par- allel techniques devised for both steps of the evaluation of ASP programs. In particular, a three-level parallel instantiation technique is presented for improv- ing the efficiency of the instantiation process which might become a bottleneck in common situations, especially when huge input data has to been dealt with. Moreover, a parallel multi-heuristics search algorithm and a parallel lookahead technique have been conceived for optimizing the second phase of the evaluation. The mentioned parallel techniques has been implemented in the state-of-the- art ASP system DLV. An extensive experimental analysis has been carried out in order to assess the performance of the implemented prototypes. Experimental results have confirmed the efficiency of the implementation and the effectiveness of those techniques.
GAMON discovering M-of-N hypotheses for text classification by a lattice-based genetic algorithm
(2013-11-12) Pietramala, Adriana; Leone, Nicola; Rullo, Pasquale
Lo sviluppo delle moderne tecnologie informatiche, nonch´e la diffusione dei servizi per il Web, ha portato ad una considerevole produzione di informazioni e dati di diversa natura: documenti testuali (dati non strutturati), basi di dati (dati strutturati) e pagine Html (dati semi-strutturati). La disponibilit` a, sempre pi`u crescente, di considerevoli quantit`a di dati ha posto, di conseguenza, il problema della loro memorizzazione, della loro organizzazione e del loro reperimento. Inoltre, se non ci fossero strumenti idonei a trattare le sole informazioni di interesse, tutti questi dati rischierebbero di essere inutilizzabili. Le informazioni, infatti, rappresentano il punto di partenza per l’estrazione di conoscenza, attivit`a che, in passato, ha fatto riferimento all’analisi e all’interpretazione manuale, fondata sull’attivit`a di uno o pi`u esperti addetti a prendere le decisioni sul caso corrente. L’analisi manuale, chiaramente, presenta molteplici aspetti negativi. Prima tra tutti essa `e caratterizzata da lunghi tempi di analisi e da alti costi di realizzazione; infine, risulta altamente soggettiva e in accurata. Tali aspetti negativi vengono ulteriormente aggravati dall’enorme mole di dati da dover trattare. Aggregare, classificare e recuperare le informazioni di interesse con tempestivit`a, efficacia e a costi ridotti `e sicuramente pi`u vantaggioso rispetto ai tradizionali approcci di analisi manuale. In particolare, la possibilit`a di poter classificare automaticamente enormi quantit`a di documenti, potendoli poi ritrovare facilmente sulla base dei concetti espressi e sulle tematiche trattate, piuttosto che affidarsi ad un’analisi manuale, `e una necessit`a che viene sentita non solo dalla comunit`a scientifico/accademica, ma anche da quella aziendale, commerciale e finanziaria. Il Text Classification (TC) o Text Categorization `e una disciplina che coniuga diverse aree di ricerca, dall’Information Retrieval (IR), al Machine Learning (ML), al Natural Language Processing (NLP) e mira alla costruzione di sistemi per la classificazione automatica dei dati in categorie tematiche di interesse. In particolare, nel TC, i dati sono costituiti da una collezione di documenti testuali non strutturati, i quali vengono suddivisi in gruppi sulla base del contenuto, attraverso l’assegnamento del testo ad una o pi`u categorie tematiche predefinite. Le prime ricerche nell’ambito del TC risalgono all’inizio degli anni ‘60. Tuttavia, `e solo nell’ultimo decennio che tale problema sta suscitando un interesse crescente sia nel settore della ricerca scientifica che in contesti industriali. Possibili applicazioni del TC spaziano dall’indicizzazione automatica di articoli scientifici, all’organizzazione delle e-mail, al filtraggio dello spam, ecc. Negli ultimi decenni, sono stati proposti un gran numero di sistemi per la classificazione di documenti testuali suddivisibili, principalmente, in tre macro-tipologie sulla base dell’approccio seguito nella costruzione dei classificatori: • approccio di tipo Expert Systems (ES); • approccio di tipo Machine Learning (ML); • approccio di tipo Ibrido. Ibrido. Il primo approccio, affermatosi all’inizio degli anni ’60 prevede l’impiego di esperti di dominio (classificazione manuale) nella definizione dei classificatori per le categorie di interesse. Questo tipo di approccio ha consentito la definizione di classificatori molto efficaci. Di contro, per`o, l’approccio di tipo ES presenta due svantaggi principali: risulta molto dispendioso in termini di risorse umane utilizzate e poco flessibile. Infatti, nel momento in cui cambia il contesto di riferimento, i nuovi classificatori devono essere nuovamente definiti manualmente. Per questo motivo, a partire dagli anni ’90, l’approccio di tipo ES `e stato quasi completamente sostituito dall’approccio di tipo ML, il cui obiettivo principale non `e la definizione dei classificatori, quanto la costruzione di sistemi in grado di generare automaticamente i classificatori. Pi`u in particolare, nell’ambito di questo paradigma, l’obiettivo `e la definizione di sistemi capaci di apprendere automaticamente le caratteristiche di una o pi`u categorie, sulla base di un insieme di documenti precedentemente classificati (training set). Questo approccio presenta numerosi vantaggi rispetto a quello di tipo Expert Systems. I sistemi di apprendimento, infatti, mostrano generalmente un’elevata efficacia, consentono un considerevole risparmio in termini di risorse umane impiegate nel processo di definizione dei classificatori e garantiscono una immediata portabilit`a verso nuovi domini. Negli ultimi anni sono stati proposti svariati sistemi per la classificazione automatica di documenti testuali basati, essenzialmente, su processi di tipo induttivo. Tali sistemi sfruttano, generalmente, misure statistiche e, talvolta, vengono importati nell’ambito del TC da altre aree dell’Information Retrieval e del Data Mining. Un esempio emblematico `e il caso delle Support Vector Machine (SVM) utilizzate, dapprima, per la risoluzione di problemi di regressione e, attualmente, considerate allo stato dell’arte per il Text Categorization. Un posto di rilievo nel paradigma dell’induzione di classificatori `e occupato dagli algoritmi di apprendimento ”a regole” o ”rule-based”, dove i classificatori vengono specificati come insiemi di regole. Tali classificatori hanno la propriet`a desiderabile di essere comprensibili da un lettore umano, mentre la maggior parte degli altri approcci esistenti, come SVM e Neural Network, producono classificatori che difficilmente un lettore umano riesce ad interpretare. Classificatori con queste caratteristiche vengono spesso chiamati di tipo black-box. Infine, l’approccio di tipo Ibrido combina il metodo Expert System con quello Machine Learning, per ottenere un sistema di categorizzazione che sfrutta sia i benefici derivanti da una conoscenza di dominio, sia i benefici derivanti dalla costruzione di sistemi automatici. Ultimamente, la comunit`a scientifica sta adottando tecniche di TC sempre pi`u innovative che, generalmente, si discostano di molto dagli approcci classici di tipo deterministico. In effetti, una recente tendenza nell’ambito del TC `e quella di sfruttare tecniche di apprendimento basate su metaeuristiche, come gli Algoritmi Evoluzionistici o Genetici. Tecniche di questo tipo sono, general mente, costituite da tre componenti essenziali: • un insieme di soluzioni candidate, chiamato popolazione, costituito da individui o cromosomi. Questi evolvono durante un certo numero di iterazioni (generazioni) generando, alla fine dell’evoluzione, la soluzione migliore; • una funzione obiettivo, chiamata funzione di fitness, usata per assegnare a ciascun individuo un peso (score) che indica la bont`a dell’individuo stesso; • un meccanismo evolutivo, basato su operatori evoluzionistici come crossover, mutazione ed elitismo, che consentono di modificare il materiale genetico degli individui che costituiscono la popolazione. Approcci di questo tipo introducono notevoli vantaggi rispetto alle tecniche classiche. Ad esempio, il meccanismo evolutivo `e noto per essere un metodo robusto e di successo, infatti, `e utilizzato per la risoluzione di molti problemi di ottimizzazione intrinsecamente difficili da risolvere. Inoltre, il meccanismo evolutivo riduce sensibilmente lo spazio di ricerca delle soluzioni ammissibili e molte tecniche evolutive riescono a risolvere problemi complessi senza conoscere il preciso metodo di soluzione. In questo lavoro di tesi proponiamo un modello di classificazione a regole, denominato GAMoN, basato sull’utilizzo di Algoritmi Genetici per l’induzione delle regole di classificazione. Un classificatore H generato dal sistema GAMoN per una data categoria c assume la forma di una disgiunzione di atomi Hic del tipo:Hc = H1 c ∨ · · · ∨ Hr c dove ciascun atomo Hic `e una quadrupla < Pos,Neg,mi, ni >, dove: • Pos = {t1, .., tn} `e l’insieme dei termini positivi, ovvero l’insieme dei termini che sono rappresentativi per la categoria c di riferimento; • Neg = {tn+1, , tn+m} `e l’insieme dei termini negativi, ovvero l’insieme dei termini che sono indicativi della non appartenenza alla categoria; • mi e ni sono numeri naturali, chiamati soglie, tali che mi >= 0 e ni > 0. Intuitivamente, il significato attribuito a ciascun atomo Hic `e il seguente: “classifica il generico documento d sotto la categoria c se almeno mi termini positivi compaiono in d e meno di ni termini negativi compaiono in d”. Infatti, il linguaggio delle ipotesi introdotto da GAMoN `e chiamato MofN+, una estensione dei classificatori di tipo MofN con la componente dei termini negativi. Da qui nasce l’acronimo “GAMoN”, che sta ad indicare un sistema di classificazione testuale basato su “Algoritmi Genetici” di tipo “M of N”. GAMoN `e un sistema di classificazione che nasce come estensione di “Olex-GA”, un modello di classificazione “a regole” basato sul paradigma evoluzionistico e realizzato in precedenti lavori di ricerca. Un classificatore generato da GAMoN coincide con quello di Olex-GA quando mi=1 e ni = 1. Infatti, un classificatore Olex-GA assume il significato “se almeno uno dei termini positivi t1, ..., tn appare nel documento d e nessuno dei termini negativi tn+1, , tn+m appare in d, allora classifica d sotto la categoria c”. Il sistema GAMoN `e stato testato su 13 corpora di benchmark (Reuters-21578, Ohsumed, OH5, OH0, OH10, OH15, Blogs Gender, Ohscale, 20 Newsgroups, Cade, SRAA, ODP e Market) e messo a confronto con altri 5 sistemi di classificazione: BioHEL [18, 48] e Olex-GA [101], che sono sistemi di classificazione a-regole basati sul paradigma evoluzionistico; Ripper [37] e C4.5 [105], che sono sistemi di classificazione a-regole non evoluzionistici; infine, SMO che `e una implementazione di SVM lineare [76]. Gli studi sperimentali mettono in evidenza come GAMoN induca classificatori che sono, al tempo stesso, accurati e compatti. Tale propriet`a `e stata osservata su tutti i corpora utilizzati nella sperimentazione, dove GAMoN ha mostrato sempre un comportamento uniforme. Poich´e i corpora utilizzati si riferiscono a contesti applicativi notevolmente diversi, possiamo affermare che GAMoN ha dato prova di essere un sistema robusto. Complessivamente, GAMoN ha dimostrato un buon bilanciamento tra accuratezza e complessit`a del modello generato; inoltre, `e risultato molto efficiente per la classificazione di corpora di grandi dimensioni. Il seguito della tesi `e organizzato in tre parti principali di seguito elencate: • nella Parte I verr`a definito formalmente il problema del Text Categorization e verranno rivisitati i principali contesti applicativi nei quali sono sfruttate tecniche di questo tipo; • nella Parte II verranno presentati diversi metodi e sistemi di classificazione documentale, al fine di realizzare una valutazione comparativa delle loro peculiarit`a nell’ambito della tematica di interesse; • nella Parte III verr`a presentato dettagliatamente il sistema GAMoN. In particolare, verranno riportate alcune definizioni formali quali, ad esempio, il linguaggio e lo spazio delle ipotesi, gli operatori di crossover utilizzati dal sistema e verranno descritti e mostrati i risultati sperimentali ottenuti, attraverso un’analisi comparativa con i sistemi di learning s`u citati
Capitulation and stabilization in various aspects of Iwasawa theory for Zp-extensions
(2013-11-25) Caldarola, Fabio; Bandini, Andrea; Leone, Nicola
Answer Set Programming with Functions
(2014-04-01) Cozza, Susanna; Leone, Nicola
L’Answer Set Programming (ASP) [Gelfond and Lifschitz, 1988; 1991] `e un formalismo che si `e affermato, in questi ultimi anni, come potente strumento di programmazione dichiarativa per la rappresentazione della conoscenza e per il ragionamento non monotono. La semantica su cui `e basato (denominata semantica answer set) estende la semantica dei modelli stabili (usata per i programmi logici ‘normali’) all’ambito della Programmazione Logica Disgiuntiva (PLD), in cui oltre alla negazione non monotona `e consentito anche l’uso della disgiunzione nella testa delle regole. Nell’ambito dell’ASP, un determinato problema computazionale viene rappresentato tramite un programma PLD che pu`o avere zero o pi`u modelli alternativi chiamati answer sets, ognuno dei quali corrisponde ad una possibile visione del dominio modellato. I linguaggi ASP consentono di rappresentare, in maniera semplice e naturale [Eiter et al., 2000], varie forme di ragionamento non monotono, planning, problemi diagnostici e, pi`u in generale, problemi di elevata complessit`a computazionale [Baral and Gelfond, 1994; Lobo et al., 1992;Wolfinger, 1994; Minker, 1994; Lifschitz, 1996; Eiter et al., 1999; Baral, 2003]. Dopo i primi sistemi sperimentali sul calcolo dei modelli stabili [Bell et al., 1994; Subrahmanian et al., 1995], attualmente sono disponibili un buon numero di sistemi che supportano in maniera efficiente l’ASP [Gebser et al., 2007a; Leone et al., 2006; Janhunen et al., 2006; Lierler, 2005; Lin and Zhao, 2004; Simons et al., 2002; Anger et al., 2001; East and Truszczy´nski, 2001; Egly et al., 2000]. Tra questi, quelli di maggiore successo sono: DLV [Leone et al., 2006], GnT [Janhunen et al., 2006] (estensione PLD del pi`u conosciuto Smodels [Simons et al., 2002]), e pi`u di recente clasp [Gebser et al., 2007a]. Tutto ci`o, se da un lato ha consentito l’impiego dell’ASP in contesti reali, dall’altro ha messo in evidenza le limitazioni dei sistemi attualmente disponibili. Uno dei principali limiti `e dato dall’inadeguato supporto a termini complessi quali funzioni, liste, set ed in generale costrutti che consentano, in maniera diretta, il ragionamento su strutture dati ricorsive e domini infiniti. Infatti, anche se la semantica answer set `e stata definita per linguaggi del primo ordine ‘generali’ quindi con anche termini funzionali, i sistemi ASP esistenti, sono essenzialmente basati su linguaggi senza funzioni. L’esigenza di estendere la PLD con un adeguato supporto ai termini funzionali `e percepita fortemente dalla comunit`a scientifica ASP, come testimoniato dai numerosi contributi pubblicati recentemente su questo tema [Lin andWang, 2008; Simkus and Eiter, 2007; Baselice et al., 2007; Bonatti, 3 2004; Syrj¨anen, 2001]. Tuttavia, non `e stato ancora proposto un linguaggio sufficientemente soddisfacente dal punto di vista linguistico (che abbia espressivit`a elevata) ed anche adatto ad essere integrato nei sistemi ASP esistenti. Infatti, attualmente nessun sistema ASP consente un uso effettivo di termini funzionali. I simboli di funzione o sono del tutto banditi dal linguaggio oppure sono soggetti a forti vincoli sintattici che non ne consentono l’uso in ambito ricorsivo. Obiettivo di questo lavoro di tesi `e il superamento di tali limitazioni. Il contributo del lavoro `e sia teorico che pratico ed ha portato all’implementazione di un sistema ASP che supporta adeguatamente i termini complessi: funzioni ma anche liste ed insiemi. Il principale contributo teorico riguarda la definizione formale di una nuova classe di programmi PLD: i programmi finitamente ground (FG). Tale classe supporta in maniera completa i simboli di funzione (essi sono ammessi anche in caso di regole ricorsive) e gode di alcune rilevanti propriet`a computazionali. Viene infatti dimostrato che, per tutti i programmi appartenenti alla classe, la valutazione secondo un approccio bottom-up, consente il calcolo effettivo degli answer set e di conseguenza, sia le query ground che le query non ground sono decidibili, qualsiasi sia la forma di ragionamento scelto (coraggioso o scettico). Un ulteriore risultato riguarda l’espressivit`a di questa classe: viene dimostrato che, qualsiasi funzione calcolabile pu`o essere espressa tramite un programma FG. Chiaramente, questo implica che il problema di riconoscere se un programma appartiene o meno alla classe, risulta essere indecidibile (in particolare, semidecidibile). Poich´e per alcuni utenti/applicazioni `e necessario avere una garanzia ‘‘a priori’’ della terminazione del programma, si `e ritenuto utile identificare una sottoclasse dei programmi FG, per la quale anche il problema del riconoscimento sia decidibile. Alcune condizioni sintattiche sono quindi state individuate come caratterizzanti per la nuova classe: i programmi a dominio finito (FD). La classe dei programmi FG `e, per alcuni aspetti, complementare alla classe dei programmi finitari [Bonatti, 2004]. La prima segue un approccio bottom-up, mentre la seconda top-down. Le due classi risultano essere incomparabili, nel senso che esistono dei programmi che appartengono alla prima ma non alla seconda e viceversa. Al fine di rendere valutabili secondo l’approccio bottom-up i programmi finitari, ampliando cos`ı la classe dei programmi FG, si `e fatto ricorso alla tecnica dei Magic Sets. Tale tecnica, nata nell’ambito delle Basi di Dati Deduttive a scopo di ottimizzazione, consiste in un metodo di riscrittura che simula la valutazione top-down di una query, modificando il programma originale e ag4 giungendo nuove regole che limitano la computazione ai dati rilevanti ai fini della query. Un opportuno adeguamento dell’algoritmo di riscrittura Magic Sets `e stato definito per le query finitamente ricorsive (le query il cui programma ‘rilevante’ `e finitario ed `e positivo). Dato un programma P ed una query ground finitamente ricorsiva Q, i seguenti risultati sono stati dimostrati riguardo il programma riscritto RW(Q;P): la sua dimensione `e lineare rispetto alla dimensione dell’input; risulta essere del tutto equivalente a quello originario ai fini della risposta alla query e soprattutto, tale programma `e FG, quindi pu`o essere valutato bottom-up (contrariamente al programma originale). Oltre ai contributi teorici sinora descritti, questa tesi presenta anche i risultati di un’attivit`a pi`u pratica, di tipo implementativo e di sperimentazione. Tale attivit`a `e stata svolta utilizzando DLV come sistema ASP di riferimento ed ha avuto come obiettivo l’estensione del linguaggio con simboli di funzione e pi`u in generale termini complessi quali liste e set. Un primo passo in questa direzione `e stata la realizzazione del supporto a funzioni esterne (plug-in). L’utente del sistema pu`o definire dei propri particolari predicati esterni (identificati tramite il prefisso ‘#’), implementati come funzioni C++ ed utilizzabili all’interno di un programma DLV. Ad ogni predicato esterno #p di arit`a n deve essere associata almeno una funzione C++ p0, detta ‘oracolo’. Tale funzione, della cui definizione `e responsabile l’utente, deve restituire un valore booleano e deve avere esattamente n argomenti. Un atomo ground #p(a1; : : : ; an) sar`a vero se e solo se il valore restituito dalla funzione p0(a1; : : : ; an) `e vero. Gli argomenti di una funzione oracolo possono essere sia di input che di output: ad argomenti di input corrispondono termini costanti o a cui `e gi`a stato assegnato un valore (termini ‘bound’) nel relativo predicato esterno, ad argomenti di output corrispondono termini variabili non legati ad alcun valore (termini ‘unbound’). L’introduzione delle funzioni esterne nel sistema DLV ha come conseguenza la possibilit`a di introdurre nuove costanti simboliche nel programma logico (Value Invention) e quindi rendere eventualmente infinito l’universo di Herbrand. Di conseguenza, per i programmi con Value Invention, non `e pi`u garantita la terminazione. Sono state quindi individuate un insieme di condizioni sintattiche tali da garantire la propriet`a di ‘istanziazione finita’ e quindi la terminazione, per un programma logico con funzioni esterne. Un riconoscitore di programmi logici che rispettano tali condizioni `e stato inoltre implementato ed integrato in DLV. Sfruttando le possibilit`a offerte dai predicati esterni, `e stato realizzato il sup5 porto a termini complessi di tipo funzionale. In pratica, in presenza di termini funzionali, una regola DLV viene ‘riscritta’ in maniera tale da tradurre la presenza del simbolo di funzione, nell’invocazione di un opportuno predicato esterno; questo si occupa poi della costruzione del termine complesso o, viceversa, dell’estrazione degli argomenti da esso. Il risultato ottenuto `e che i programmi FG, descritti in precedenza, sono pienamente supportati dal sistema. Un riconoscitore sintattico per i programmi a dominio finito consente di individuare ‘‘a priori’’ quei programmi la cui terminazione non `e garantita. A discrezione dell’utente, `e possibile disabilitare tale riconoscitore e sfruttare in pieno l’espressivit`a dei programmi FG, rinunciando per`o alla garanzia di terminazione. Il linguaggio effettivamente supportato dal sistema, oltre ai termini funzionali, prevede anche altre due tipologie di termini complessi: liste e set. Realizzati sfruttando lo stesso framework usato per le funzioni, liste e set sono stati corredati da una ricca libreria di funzioni di manipolazione che rendono ll loro uso molto agevole. Grazie a tali estensioni, il linguaggio di DLV `e diventato sempre pi`u adatto alla codifica immediata e compatta di problemi di rappresentazione della conoscenza. In sintesi, i contributi principali di questo lavoro di tesi sono: – la definizione formale della classe dei programmi finitamente ground; cio`e una nuova classe di programmi logici disgiuntivi che consente l’uso dei simboli di funzione (eventualmente con ricorsione) e che gode di rilevanti propriet` a computazionali quali: l’elevata espressivit`a, la computabilit`a bottomup degli answer set e quindi la decidibilit`a del ragionamento, anche in caso di query non ground; – l’utilizzo della tecnica dei Magic Sets per la riscrittura di programmi finitari positivi che non risultano appartenere alla classe dei programmi finitamente ground, ma sui quali `e comunque possibile valutare bottom-up delle query ground, grazie ad un’opportuna trasformazione del programma stesso; – la realizzazione di un sistema il cui linguaggio, oltre a supportare pienamente la classe dei programmi finitamente ground, consente l’integrazione nel programma logico di sorgenti computazionali esterne e l’utilizzo agevole di termini complessi quali liste e set; – la comparazione del nostro lavoro, in particolar modo con i programmi finitari, ma anche con altri approcci proposti in letteratura per l’estensione dei sistemi ASP con simboli di funzione

Tesi di Dottorato

Browse

Filters

Settings

Sort By

Results per page

Search Results