Bounds on the number of inference functions of a graphical model

Details Bounds on the number of inference functions of a graphical model Bounds on the number of inference functions of a graphical model

2006-10-06

arxiv.org/abs/math/0610233v1

Mathematics

Combinatorics

19 pages, 7 figures

Scientific paper

Directed and undirected graphical models, also called Bayesian networks and Markov random fields, respectively, are important statistical tools in a wide variety of fields, ranging from computational biology to probabilistic artificial intelligence. We give an upper bound on the number of inference functions of any graphical model. This bound is polynomial on the size of the model, for a fixed number of parameters, thus improving the exponential upper bound given by Pachter and Sturmfels. We also show that our bound is tight up to a constant factor, by constructing a family of hidden Markov models whose number of inference functions agrees asymptotically with the upper bound. Finally, we apply this bound to a model for sequence alignment that is used in computational biology.

Affiliated with

Also associated with

No associations

Rating

Bounds on the number of inference functions of a graphical model 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 Bounds on the number of inference functions of a graphical model, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bounds on the number of inference functions of a graphical model will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-489661