Stefano Bragaglia MSc Thesis, awarded as Best Italian thesis in AI 2009/2010

  • Published on
    07-May-2015

  • View
    183

  • Download
    0

Embed Size (px)

DESCRIPTION

My MSc Thesis (only in Italian) introduces Logic Programs with Annotated Disjunction (LPADs) a Prolog's probabilistic extension, and my work on CPLINT (https://sites.google.com/a/unife.it/ml/cplint) to reason on them. My goal was to implement and test several approximated algorithms to balance speed and accuracy when solving probabilistic problems. It was awarded by the Italian Association for Artificial Intelligence (AIxIA) as the best Italian thesis in Artificial Intelligence of 2009/2010.

Transcript

<ul><li>1.Universit` degli Studi di Bologna a ` FACOLTA DI INGEGNERIA Corso di Laurea in Ingegneria Informatica Intelligenza ArticialeRAGIONAMENTO CON PROGRAMMAZIONE LOGICA A DISGIUNZIONE ANNOTATATesi di laurea di:Relatore:Stefano BragagliaChiar. mo Prof. Ing.Paola Mello Correlatori:Dott. Ing. Dott. Ing.Fabrizio RiguzziFederico ChesaniAnno Accademico 2008-2009 Sessione I</li></ul><p>2. Universit` degli Studi di Bologna a ` FACOLTA DI INGEGNERIA Corso di Laurea in Ingegneria Informatica Intelligenza ArticialeRAGIONAMENTO CON PROGRAMMAZIONE LOGICA A DISGIUNZIONE ANNOTATATesi di laurea di:Relatore:Stefano BragagliaChiar. mo Prof. Ing.Paola Mello Correlatori:Dott. Ing. Dott. Ing.Fabrizio RiguzziFederico ChesaniAnno Accademico 2008-2009 Sessione I 3. Indice Introduzione51 ProbLog91.1Programmi ProbLog . . . . . . . . . . . . . . . . . . . . . . .91.1.1Cenni di Programmazione Logica . . . . . . . . . . .91.1.2Sintassi e semantica del linguaggio ProbLog . . . . .10Calcolo delle probabilit` di successo . . . . . . . . . . . . . . a111.2.1Espressioni booleane e forme normali . . . . . . . . .111.2.2Interrogazioni ProbLog come formule DNF . . . . . .131.2.3Diagrammi decisionali binari . . . . . . . . . . . . . .151.2.4Calcolo della probabilit` delle formule DNF . . . . . a171.3Esempio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .181.4Riepilogo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .211.22 LPAD232.1Programmi LPAD . . . . . . . . . . . . . . . . . . . . . . . . .232.1.1Cenni di Programmazione Logica . . . . . . . . . . .232.1.2Sintassi e semantica del linguaggio degli LPAD . . .25Calcolo delle probabilit` di successo . . . . . . . . . . . . . . a272.2.1Interrogazioni sugli LPAD come formule DNF . . . .272.2.2Calcolo della probabilit` delle formule DNF . . . . . a272.3Esempio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .282.4Riepilogo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .312.2 4. 2INDICE3 Algoritmi esistenti333.1Cenni architetturali . . . . . . . . . . . . . . . . . . . . . . . .333.2Algoritmi ProbLog . . . . . . . . . . . . . . . . . . . . . . . .363.2.1Inferenza esatta . . . . . . . . . . . . . . . . . . . . . .363.2.2Inferenza approssimata con bound sulla probabilit` . a373.2.3Inferenza approssimata ai risultati migliori . . . . . .383.2.4Inferenza approssimata con approccio statistico . . .39Algoritmi LPAD . . . . . . . . . . . . . . . . . . . . . . . . . .403.3.1Inferenza esatta con risoluzione SLDNF . . . . . . . .40Riepilogo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .423.3 3.44 Estensioni proposte454.1Algoritmo esatto . . . . . . . . . . . . . . . . . . . . . . . . .454.2Algoritmo iterativo con vincolo sulla probabilit` . . . . . . . a464.3Algoritmo approssimato Best-First . . . . . . . . . . . . . . .474.4Algoritmo approssimato K-Best . . . . . . . . . . . . . . . . .484.5Algoritmo approssimato K-First . . . . . . . . . . . . . . . . .504.6Algoritmo stocastico Monte Carlo . . . . . . . . . . . . . . .514.7Algoritmo stocastico Monte Carlo con memoria . . . . . . .534.8Riepilogo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .555 Esperimenti 5.157Gra a percorsi paralleli . . . . . . . . . . . . . . . . .585.1.2Gra a percorsi ramicati . . . . . . . . . . . . . . . .625.1.3Gra a percorsi ridondanti . . . . . . . . . . . . . . .68Test su dataset reali . . . . . . . . . . . . . . . . . . . . . . . .835.2.1Dataset di dati biologici . . . . . . . . . . . . . . . . .835.2.2 5.3575.1.15.2Test sintetici . . . . . . . . . . . . . . . . . . . . . . . . . . . .Dataset di reti sociali . . . . . . . . . . . . . . . . . . .84Riepilogo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .88Conclusioni89Ringraziamenti93 5. INDICE3Bibliograa95Elenco degli algoritmi99Elenco delle gure101Elenco delle tabelle103 6. 4INDICE 7. Introduzione Fin dai primi anni 50, la possibilit` di combinare logica e probabilit` a a ha affascinato loso ed esperti di intelligenza articiale [Car50, Gai64, ` SK66, Hal90]. Negli ultimi ventanni, questo campo di ricerca e stato oggetto di rinnovato interesse grazie al lavoro svolto da molte Universit` a e Centri di Ricerca nel campo dellApprendimento Relazionale Statistico [GT07] e della Programmazione Logica Induttiva Probabilistica [RFKM08]. I numerosi formalismi che combinano aspetti statistici a quelli relazionali proposti in questi anni, come ad esempio SLP [Mug00], PLP [Dan91], PHA [Poo93], PRISM [SK97], pD [Fuh00] ed ICL [Poo97], ne sono un esempio. Nei casi considerati, si consegue questo risultato semplicemente associando dei valori di probabilit` alle formule logiche dei programmi ed a imponendo opportuni vincoli su di loro. In SLP, ad esempio, le clausole che deniscono lo stesso predicato devono essere mutuamente esclusive. In PRISM e PHA, invece, le probabilit` possono essere associate solamente a ai fatti e si introducono nuovi vincoli per evitare che certe combinazioni di fatti siano contemporaneamente vere. In pD, inne, non si impongono vincoli esterni ma il motore inferenziale su cui si basa ha limitazioni cos` forti che gli consente di risolvere solamente problemi di piccole dimensioni. Questo lavoro si ispira a due importanti formalismi: ProbLog e i Programmi Logici a Disgiunzione Annotata, o LPAD. Il primo nasce dalla necessit` di analizzare gra biologici di grandi dimensioni in cui gli archi a sono etichettati con valori di probabilit` , mentre il secondo per modellare a generici sistemi causali. ` ProbLog rappresenta lestensione probabilistica di Prolog piu sempli- 8. 6Introduzionece che si possa realizzare. In pratica consente di etichettare le regole di un programma logico con valori di probabilit` indipendenti tra di loro. a Il contributo innovativo dato da ProbLog consiste nellintroduzione di un metodo in due fasi per il calcolo della probabilit` di successo di una intera rogazione. Nella prima raccoglie tutte le spiegazioni dellinterrogazione grazie al meccanismo di risoluzione SLD di Prolog, quindi converte questo risultato in una espressione booleana in Forma Normale Disgiuntiva, o formula DNF; poi, nella seconda fase, calcola la probabilit` di questa a espressione mediante luso di Diagrammi Decisionali Binari, o BDD (dal` linglese Binary Decision Diagrams). Questo metodo puo essere abbina` to ad algoritmi di inferenza sia esatti che approssimati ed e in grado di affrontare problemi di milioni di nodi e di archi. Gli LPAD, invece, sono un formalismo particolarmente interessante per la versatilit` della sintassi e per la semplicit` e la chiarezza della sea a mantica che rende i propri programmi molto leggibili ed equivalenti ad altri famosi sistemi probabilistici. Diversamente da quelle dei programmi ` ProbLog, le clausole degli LPAD possono essere disgiuntive ed e possibile associare una probabilit` ad ogni singolo atomo presente nelle loro teste. a Come i programmi ProbLog, gli LPAD assegnano un valore di probabilit` a alle interrogazioni logiche e utilizzano un interprete top-down derivato dal motore inferenziale di Prolog per determinare le spiegazioni dellinterrogazione ed un software di gestione dei BDD per calcolarne la probabilit` a equivalente. Gli LPAD implementano inoltre un metodo alternativo per il calcolo della probabilit` con il quale la parte di programma esplorato dal a meccanismo di risoluzione SLDNF viene convertito in una rete bayesiana ` ma sfortunatamente non e altrettanto efcace. Con questo lavoro vogliamo costruire un sistema che combini i vantaggi derivanti dalladozione del linguaggio LPAD e della risoluzione SLDNF introdotti in [Rig07] e i miglioramenti tecnologici in ambiente ProbLog presentati in [KCR+ 08]. In particolare abbiamo presentato un algoritmo di risoluzione esatto che coniuga la essibilit` degli LPAD con le innovazioa ni dellinterprete ProbLog e diversi algoritmi euristici che implementano molte soluzioni complementari. Tra questi citiamo un algoritmo basato su 9. 7approccio iterativo semplice (Depth-Iterative), tre algoritmi euristici (BestFirst, K-Best e K-First) e gli ultimi due basati su approccio probabilistico (due varianti di Monte Carlo). Inoltre abbiamo condotto diversi esperimenti sia su dataset articiali che su gra biologici e reti sociali. Rispetto allalgoritmo esatto, gli algoritmi statistici si sono dimostrati particolarmente efcaci in ogni contesto, mentre quelli approssimati sono stati condizionati dai limiti tecnologici dellinterprete Prolog adottato e sebbene abbiano mostrato importanti margini di miglioramento, non hanno potuto esprimere tutto il loro potenziale. ` La tesi e organizzata come segue. Nel capitolo 1 si introduce ProbLog, un primo formalismo basato sulla conoscenza incerta. Dopo una breve introduzione su alcune nozioni preliminari e sui concetti cardine su cui si basa, si descrive la sintassi e la semantica dei suoi programmi ed il corrispondente metodo di risoluzione. Allo stesso modo, nel capitolo 2 si presentano gli LPAD, un altro formalismo di conoscenza incerta. Anche in questo caso, dopo averne descritto le caratteristiche principali, se ne analizza la sintassi, la semantica ed i metodi di risoluzione che utilizza. Nel capitolo 3, invece, si descrivono ed analizzano tutti gli algoritmi utilizzati dai pacchetti software precedentemente introdotti evidenziandone, in particolar modo, pregi e difetti. Nel capitolo 4 si espongono le estensioni realizzate in ambiente YAP-Prolog come miglioramento degli algoritmi esistenti e le motivazioni che ne hanno suggerito ladozione, mentre nel capitolo 5 si presentano i risultati degli esperimenti condotti con dati sintetici e database reali su tali applicazioni. Inne si espongono le conclusioni a ` cui si e pervenuti e si delineano i possibili sviluppi futuri. 10. 8Introduzione 11. Capitolo 1 ProbLog In questo primo capitolo verranno dapprima richiamati i concetti preliminari e la terminologia propri della Programmazione Logica e successivamente si introdurr` ProbLog ([DRKT07], [KCR+ 08]), unimportante estensione probabia listica di Prolog. Nel seguito tratteremo la sintassi e la semantica di questo linguaggio e, dopo aver introdotto le espressioni booleane in forma normale disgiunta ed i diagrammi decisionali binari, mostreremo come sia possibile convertire in una formula DNF qualsiasi interrogazione ProbLog e come sia possibile valutarne la probabilit` . I concetti appena introdotti verranno ulteriormente chiariti a nellesempio che conclude il capitolo.1.1 Programmi ProbLog 1.1.1 Cenni di Programmazione Logica Di seguito sono riportate alcune denizioni preliminari di Programmazione Logica, con riferimento a [Llo87]. ` Un generico programma logico T e un insieme di formule, dette clausole, espresse nella forma h b1 , . . . , b m 12. 10ProbLog` in cui h e un atomo e b1 , . . . , bm sono i suoi letterali. h e b1 , . . . , bm sono detti rispettivamente testa e corpo della clausola. Se il corpo non contiene ` letterali negativi, la clausola si dice denita. Se il corpo e vuoto, la clau` sola prende il nome di fatto. La sola formula b1 , . . . , bm e nota come interrogazione o goal. Un termine, un atomo, un letterale o una clausola si dicono ground se ` non contengono alcuna variabile. Una sostituzione e un assegnamento di termini a variabili: = {V1 /t1 , . . . , Vn /tn }. Lapplicazione di una sostituzione ad un termine, un atomo, un letterale o una clausola C si indica con C e consiste nella sostituzione delle variabili che compaiono in C ed in con ` i termini specicati in . C rappresenta una istanza di C. Se C e ground, ` C e una istanza ground di C.1.1.2 Sintassi e semantica del linguaggio ProbLog ` ` ProbLog e stato pensato come lestensione probabilistica di Prolog piu semplice che si possa realizzare. Per questo motivo la sintassi dei pro` grammi ProgLog e quasi del tutto identica a quella dei programmi Prolog. ` In particolare, un generico programma ProbLog e composto da un insieme di fatti etichettati con probabilit` pi :: ci e da un insieme di clausole denite. a ` Ogni fatto ci e vero con probabilit` pi . Inoltre si presume che tutti i fatti a siano mutualmente indipendenti. Si noti che le clausole denite permettono di aggiungere conoscenza di fondo arbitraria e ci si riferisce a loro come BK (dallinglese background knowledge). Ad ogni programma ProbLog corrisponde un grafo probabilistico che ` puo essere utilizzato per campionare i sottogra decidendo arbitrariamente se includere o escludere ogni arco del grafo. In pratica un programma ProbLog T = {p1 :: c1 , , pn :: cn } BK denisce una distribuzione di probabilit` sui sottoprogrammi L LT = {c1 , , cn } tale che a P (L|T ) =pi ci L(1 pi ). ci LT L` Ora ci si puo chiedere quale sia la probabilit` che esista un percorso tra a 13. 1.2 Calcolo delle probabilit` di successo a11due nodi qualsiasi del grafo probabilistico che equivale a chiedersi quale sia la probabilit` che un sottografo campionato a caso contenga un pera ` corso diretto o uno o piu percorsi indiretti (o una combinazione qualsiasi di questi) tra i due nodi in esame. Formalmente, la probabilit` di successo a ` Ps (q|T ) di una interrogazione q in un programma ProbLog T e denita come P (q|L) P (L|T )Ps (q|T ) = LLTin cui P (q|L) = 1 se esiste una sostituzione tale che L BK |= q o P (q|L) = 0 in caso contrario. Di conseguenza, la probabilit` di una dimostrazione specica, anche a ` detta spiegazione, e quella di campionare un programma logico L che contiene tutti i fatti richiesti da quella spiegazione o dimostrazione. La proba` bilit` esplicativa Px (q|T ) e denita come la probabilit` della spiegazione o a a ` della dimostrazione piu probabile dellinterrogazione q Px (q|T ) = max P (e|T ) = max eE(q)eE(q)pi ci e` in cui E(q) e linsieme di tutte le spiegazioni per linterrogazione q.1.2 Calcolo delle probabilit` di successo a 1.2.1 Espressioni booleane e forme normali ` La logica proposizionale e quella branca della matematica che ha a che fare con i valori di verit` . Date le costanti logiche vero 1 e falso 0, si dice vaa riabile booleana o variabile proposizionale una qualsiasi variabile in grado di assumere una costante logica qualsiasi come valore. Una generica espres` sione booleana t e denita come composizione di variabili booleane median` te gli operatori binari di congiunzione (il cui simbolo e o ), e di disgiunzione ( o +) e loperatore unario di negazione ( o un tratto orizzontale posto sopra alla variabile negata). 14. 12ProbLogPer ogni possibile assegnamento dei valori di verit` alle variabili che vi a compaiono, il valore di una espressione booleana t si calcola in base al contenuto delle tabelle di verit` standard. Linsieme dei valori di verit` si indica a a generalmente con B = {0, 1}. Dato un qualsiasi criterio di ordinamento delle ` variabili di una espressione booleana t, lespressione booleana stessa puo essere vista come una funzione suriettiva f : Bn B in cui n esprime il numero di variabili che compaiono in t. Si noti che il criterio di ordinamen`...</p>