Mathematics – Probability
Scientific paper
2011-04-14
Mathematics
Probability
The paper was presented at VOCAL 2010 in Veszprem, Hungary
Scientific paper
In an earlier paper we introduced a special kind of k-width junction tree, called k-th order t-cherry junction tree in order to approximate a joint probability distribution. The approximation is the best if the Kullback-Leibler divergence between the true joint probability distribution and the approximating one is minimal. Finding the best approximating k-width junction tree is NP-complete if k>2. In our earlier paper we also proved that the best approximating k-width junction tree can be embedded into a k-th order t-cherry junction tree. We introduce a greedy algorithm resulting very good approximations in reasonable computing time. In this paper we prove that if the Markov network underlying fullfills some requirements then our greedy algorithm is able to find the true probability distribution or its best approximation in the family of the k-th order t-cherry tree probability distributions. Our algorithm uses just the k-th order marginal probability distributions as input. We compare the results of the greedy algorithm proposed in this paper with the greedy algorithm proposed by Malvestuto in 1991.
Kovacs Edith
Szantai Tamas
No associations
LandOfFree
Discovering a junction tree behind a Markov network by a greedy algorithm does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Discovering a junction tree behind a Markov network by a greedy algorithm, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Discovering a junction tree behind a Markov network by a greedy algorithm will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-166754