Inference in PRM


1. Probabilistic inference

Probabilistic inference is a family of algorithms used to compute probability values of the form \(P(Q=q|E=e)\) where \(Q\) is a set of random variables called the query and \(e\) is a set of observations of the realizations called evidence. \(P(Q=q|E=e)\) is the mathematical version of the question “What is the probability of q knowing e?". And what is known also by posterior distribution.

There exist many algorithms in this field; the most common families are exact and approximate inference:

Exact inference:
  • Enumeration algorithms
  • Variable elimination
  • Junction trees
  • Belief propagation
 Approximate inference:
  • Loopy belief and generalized propagation
  • Sampling methods: likelihood weighting, Markov chain Monte Carlo...
  • Variational approximation

In order to improve the performance of inference and make it adequate to prm, we exploit the following properties:

  • Exploit Independence: Independence and conditional independence are traditionally exploited by BNs. The inference algorithm should have similar properties to traditional BN algorithms when run on BN models.

  • Exploit Low-Level Structure: In Bayesian networks, the conditional probability distribution over a variable given its parents is traditionally represented as a table. Researchers have studied more compact representations, such as noisyor and context specific independence. Special purpose inference algorithms have been designed for these structures (Heckerman and Breese (1994), Poole and Zhang (2003)). Because of IBAL’s programming language constructs, it is easy to describe such structures - easier, in fact, than describing full conditional probability tables. The inference algorithm should be able to take a representation that elucidates the low-level structure and automatically provide benefits from exploiting the structure.

  • Exploit Larger High-Level Structure: models can often be decomposed into weakly interacting components. It was discovered for OOBNs (Pfeffer and al (1999),Wuillemin and Torti (2012),Torti et al. (2013)) that exploiting such high-level structure is a big win. In particular, the different components tend to be largely decoupled from one another, and they can be separated by a small interface that renders them conditionally independent of each other. IBAL represents high-level structure using functions. The inference algorithm should take advantage of the decoupling of the internals of functions from the remainder of the model.

  • Exploit Repetition: Many frameworks such as SCFGs and HMMs involve many repeated computations (Torti et al. (2011)). In IBAL, the same function can be applied many times, and this should be exploited to avoid repeated computation.

  • Exploit the Query: Often, one describes a very complex or infinite probabilistic model, but asks a query that only requires a small portion of the model. This is the process, for example, for SCFGs: the grammar can generate arbitrarily long sentences, but only a finite generation process is needed to generate a particular finite sentence. IBAL should use the query to consider only the parts of the generation process that are necessary for producing the result.

  • Exploit Support of Variable: When a model contains variables, its behavior depends on their values. The support of a variable is the set of values it can take with positive probability. Taking the support into account can simplify inference, by restricting the set of inputs that need to be considered. It can turn a potentially infinite inference into a finite one.

  • Exploit Evidence: If we have observations in the program, they can be used to further limit the set of values variables can take, and to restrict the possible computations. For example, suppose we have a model in which a string is generated by a grammar that can generate arbitrarily long strings, and then observe that the string has length at most four. We can use this observation to restrict the portion of the grammar that needs to be examined.
Class inheritance
The printers example

Bibliography

D. Heckerman and J.S. Breese. Causal independence for probability assessment and inference using bayesian networks. The Knowledge Engineering Review, 26(6):826–831, 1994. ↩

A. Pfeffer and al. Spook: a system for probabilistic object-oriented knowledge representation. In Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI-99), volume 18, 541–550. 1999. ↩

D. Poole and N. L. Zhang. Exploiting contextual independence in probabilistic inference. Journal of Artificial Intelligence Research, 18:263–313, 2003. ↩

Lionel Torti, Christophe Gonzales, and Pierre-Henri Wuillemin. Patterns Discovery for Efficient Structured Probabilistic Inference. In SUM 2011 - 5th International Conference on Scalable Uncertainty Management, volume 6929 of Lecture Notes in Computer Science, 247–260. Springer, October 2011. URL: http://www-desir.lip6.fr/~gonzales/research/publications/sum11a.pdf, doi:10.1007/978-3-642-23963-2_20. ↩

Lionel Torti, Christophe Gonzales, and Pierre-Henri Wuillemin. Speeding-up Structured Probabilistic Inference using Pattern Mining. International Journal of Approximate Reasoning, 54(7):900–918, September 2013. URL: http://www-desir.lip6.fr/~gonzales/research/publications/ijar13-2.pdf, doi:10.1016/j.ijar.2013.03.005. ↩

Pierre-Henri Wuillemin and Lionel Torti. Structured Probabilistic Inference. International Journal of Approximate Reasoning, 53(7):946–968, October 2012. doi:10.1016/j.ijar.2012.04.004. ↩