Related Experiment Video
Updated: Sep 30, 2026

A Practical Guide to Phylogenetics for Nonexperts
Published on: February 5, 2014
Bayesian A* tree search with expected O(N) node expansions: applications to road tracking
1Smith-Kettlewell Eye Research Institute, San Francisco, CA 94115, USA. coughlan@ski.org
Abstract:
Many perception, reasoning, and learning problems can be expressed as Bayesian inference. We point out that formulating a problem as Bayesian inference implies specifying a probability distribution on the ensemble of problem instances. This ensemble can be used for analyzing the expected complexity of algorithms and also the algorithm-independent limits of inference. We illustrate this problem by analyzing the complexity of tree search. In particular, we study the problem of road detection, as formulated by Geman and Jedynak (1996). We prove that the expected convergence is linear in the size of the road (the depth of the tree) even though the worst-case performance is exponential. We also put a bound on the constant of the convergence and place a bound on the error rates.
Related Concept Videos
Survival Tree
Building a Survival Tree
Constructing a survival tree begins...
Propagation of Uncertainty from Random Error
Binomial Expansion Using Pascal's Triangle
Heuristics
People often rely on heuristics when faced with an overload of information, limited time, low importance of the decision, limited information, or when a heuristic readily comes to mind. For...
Propagation of Uncertainty from Systematic Error
Expected Value