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-01-01
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.
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.
