Among the graph structures underlying Probabilistic Graphical Models, trees are valuable tools for modeling several interesting problems, such as linguistic parsing, phylogenetic analysis, and music harmony analysis. In this paper we introduce CDoT, a novel exact algorithm for answering Maximum a Posteriori queries on tree structures. We discuss its properties and study its asymptotic complexity; we also provide an empirical assessment of its performances, showing that the proposed algorithm substantially improves over a dynamic programming based competitor.

CDoT: Optimizing MAP Queries on Trees

ESPOSITO, Roberto;RADICIONI, DANIELE PAOLO;VISCONTI, ALESSIA
2013

Abstract

Among the graph structures underlying Probabilistic Graphical Models, trees are valuable tools for modeling several interesting problems, such as linguistic parsing, phylogenetic analysis, and music harmony analysis. In this paper we introduce CDoT, a novel exact algorithm for answering Maximum a Posteriori queries on tree structures. We discuss its properties and study its asymptotic complexity; we also provide an empirical assessment of its performances, showing that the proposed algorithm substantially improves over a dynamic programming based competitor.
XIIIth International Conference of the Italian Association for Artificial Intelligence
Torino, Italy
December 4-6, 2013
AI*IA 2013: Advances in Artificial Intelligence
Springer International Publishing
LNAI 8249
481
492
9783319035239
Esposito, Roberto; Radicioni, DANIELE PAOLO; Visconti, Alessia
File in questo prodotto:
File Dimensione Formato  
esposito13cdot.pdf

Accesso riservato

Tipo di file: PREPRINT (PRIMA BOZZA)
Dimensione 250.95 kB
Formato Adobe PDF
250.95 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2318/147283
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact