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.
Titolo: | CDoT: Optimizing MAP Queries on Trees |
Autori Riconosciuti: | |
Autori: | Esposito, Roberto; Radicioni, DANIELE PAOLO; Visconti, Alessia |
Data di pubblicazione: | 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. |
Editore: | Springer International Publishing |
Titolo del libro: | AI*IA 2013: Advances in Artificial Intelligence |
Volume: | LNAI 8249 |
Pagina iniziale: | 481 |
Pagina finale: | 492 |
Nome del convegno: | XIIIth International Conference of the Italian Association for Artificial Intelligence |
Luogo del convegno: | Torino, Italy |
Anno del convegno: | December 4-6, 2013 |
Digital Object Identifier (DOI): | 10.1007/978-3-319-03524-6_41 |
ISBN: | 9783319035239 |
Appare nelle tipologie: | 04A-Conference paper in volume |
File in questo prodotto:
File | Descrizione | Tipologia | Licenza | |
---|---|---|---|---|
esposito13cdot.pdf | PREPRINT (PRIMA BOZZA) | Accesso riservato | Utenti riconosciuti Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.