Fast approximation of Kullback-Leibler distance for dependence trees and hidden Markov models

Research output: Contribution to journalArticlepeer-review

Abstract

We present a fast algorithm to approximate the Kullback-Leibler distance (KLD) between two dependence tree models. The algorithm uses the "upward" (or "forward") procedure to compute an upper bound for the KLD. For hidden Markov models, this algorithm is reduced to a simple expression. Numerical experiments show that for a similar accuracy, the proposed algorithm offers a saving of hundreds of times in computational complexity compared to the commonly used Monte Carlo method. This makes the proposed algorithm important foe real-time applications, such as image retrieval.

Original languageEnglish (US)
Pages (from-to)115-118
Number of pages4
JournalIEEE Signal Processing Letters
Volume10
Issue number4
DOIs
StatePublished - Apr 2003

Keywords

  • Dependence tree models
  • Hidden Markov models
  • Kullback-Leibler distance

ASJC Scopus subject areas

  • Signal Processing
  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'Fast approximation of Kullback-Leibler distance for dependence trees and hidden Markov models'. Together they form a unique fingerprint.

Cite this