.. index:: Rebane-Pearl Polytree

.. _Rebane_Pearl_Polytree:

Rebane-Pearl Polytree
=====================

The Rebane-Pearl polytree algorithm constructs a polytree-shaped belief network approximation to a probability distribution (Rebane and Pearl, 1987).

The Rebane-Pearl algorithm is similar to the :ref:`Chow-Liu tree algorithm<chow_liu_tree>` for constructing the "best possible" tree-shaped belief network approximation to a probability distribution such that all edges are directed away from the root. Instead of constructing a tree-shaped belief network approximation, the algorithm constructs a polytree-shaped belief network.

Rebane-Pearl polytree recovery algorithm: The Chow-Liu algorithm constructs a simple tree structure (each node has one parent --- except the root). The Rebane-Pearl algorithm turns this tree into a polytree (each node can have multiple parents, but the underlying network structure is still a tree).

References
^^^^^^^^^^

* C. K. Chow, C. N. Liu (1968). *Approximating Discrete Probability Distributions with Dependence Trees*.
* G. Rebane, J. Pearl, (1987). *The recovery of causal polytrees from statistical data*.