Polytrees

October 17, 2026

The discrete Bayes filter ran Pearl’s rule on a chain: $\mathrm{BEL} = \alpha \lambda \pi$, with $\pi$ arriving from the one node above and $\lambda$ from the one node below. A polytree is the same thing with the counts relaxed. Nodes may have several parents and several children, and the only condition is that the undirected skeleton has no cycles, so between any two nodes there is exactly one path.

$\pi$ and $\lambda$ do not change meaning. What changes is that $\pi$ now has to combine what several parents say, and $\lambda$ has to combine what several children say. Everything else on this page follows from those two sums, and most of it follows from one of them.

A robot deciding what has gone wrong with it. A wet floor makes the wheels slip, fog makes the lidar and the camera noisy, slipping wheels or a bad lidar lose the pose, and a lost pose aborts the mission. Seven nodes, six edges, one connected skeleton, so exactly a tree.

Combining several parents, and several children

$\lambda$ is the easy one. Evidence below a node arrives through its children independently, because in a polytree the subtrees below different children do not touch. So they multiply:

where $\delta_e$ is the node’s own evidence, a point mass when it is set and all ones when it is free.

$\pi$ is the one that costs something. A node’s parents can be in any combination, and the conditional table is defined on those combinations, so the sum runs over all of them:

That product is the reason polytree inference is cheap in the number of nodes and expensive in the number of parents: linear in the graph, exponential in the widest conditional table. Seven binary nodes with at most two parents is nothing, and the tool settles in at most six sweeps over every evidence set it can be given.

λ travels upward

On a chain the backward direction never came up, because the filter only ever asked about the present. Here it is unavoidable: belief at a root depends on what was observed at a leaf, and the only way up is a message.

A node sends each parent what it and everything below it have to say about that parent:

Read the inner sum carefully, because the whole page turns on it. The message $X$ sends to parent $u_i$ marginalises over the other parents, weighted by what those parents currently believe. A node with one parent has no other parents, the product is empty, and the message is what a chain passes. A node with two parents sends each one a message that depends on the other.

Instantiating a node cuts the graph

Set a node and its evidence factor becomes a point mass. Two things follow immediately:

Downward, the message it sends its children is that point mass. It no longer mentions $\pi$, so nothing above the node reaches anything below it. Set pose lost and the mission abort sits at 90%, which is just $P(\text{abort} \mid \text{pose lost})$, whether the floor is wet, dry, or unmentioned.

Upward, the message it sends a parent is $P(x^\ast \mid u)$, summed against the other parents’ $\pi$. That still mentions them. So an observed node with one parent is a barrier, and an observed node with two parents is a junction that has just been wired together.

The first is the familiar case and the second is not, which is why the usual statement of d-separation has three rules where the algebra has one.

Three shapes, one rule

Every path through a node takes one of three shapes, and in a polytree there is only the one path to check.

With nothing observed, 6 of the 21 pairs are independent, and they are exactly the pairs with one node on the wet-floor side and the other on the fog side, since every route between those two groups runs through the collider.

Set each node in turn and count what changes among the pairs that are still unobserved:

Five of the seven nodes cannot couple anything, whatever they are set to. Observing them only ever cuts routes. The two that can are the collider and the node hanging below it, and the six pairs they couple are every pair that was independent in the first place.

Explaining away

Watch wheel slip while the collider is open. It starts at 18.0%, and losing the pose raises it to 50.1% along with the lidar, because something caused the loss and these are the two candidates. Now confirm the lidar is noisy and wheel slip falls to 29.4%. The lidar accounts for the pose loss, so the floor no longer has to.

Deny the lidar instead and wheel slip goes to 86.8%. Same evidence at the collider, opposite conclusion about a node it does not touch.

Nothing joins those two nodes. There is no arrow, no shared parent, and with the collider unobserved there is no dependence at all. All of it is the $\prod_{k \ne i} \pi_X(u_k)$ in the upward message: the lidar’s $\pi$ is sitting inside the $\lambda$ that the pose node sends to the wheel slip node, and setting the lidar changes it.

A descendant counts too

The collider does not have to be the node that was observed. Mission abort hangs below it, and observing the abort is evidence about the pose, which is enough to couple the pose’s parents.

Set mission abort alone and wheel slip reads 44.0%. Confirm the lidar and it falls to 28.4%, the same effect one step further away.

Set the abort on its own and the counter reads 0 of 15. One observation, at a leaf, touching no node directly except its own parent, and nothing left unobserved in the network is independent of anything else.

Why the skeleton has to be cycle-free

Two routes between a pair of nodes and the argument above collapses. The product over children assumed the subtrees below them do not touch, and the sweep assumed a message cannot come back round and be counted as fresh evidence. With a cycle, both fail: the same observation arrives twice, the sweeps may still settle, and the numbers still look like probabilities.

Gaussian belief propagation runs it on a graph full of cycles anyway, because robots ranging to each other have no choice about it, and measures what the loops cost. The short answer is that the means survive and the uncertainties do not.

The code

The two sums, and the evidence factor that makes a node a barrier.

// A node's own evidence as a factor over its states: a point mass when
// it is set, all ones when it is free. The only place instantiation
// enters, and everything else is a consequence of it sitting here.
std::vector<double> evidenceFactor(int states, int observed) {
    if (observed < 0) return std::vector<double>(states, 1.0);
    std::vector<double> f(states, 0.0);
    f[observed] = 1.0;
    return f;
}

// lambda: the node's evidence times what every child says. Children
// multiply because in a polytree the subtrees below them do not touch.
std::vector<double> lambdaOf(int states, int observed,
                             const std::vector<std::vector<double>>& fromChildren) {
    std::vector<double> lam = evidenceFactor(states, observed);
    for (const auto& m : fromChildren) {
        for (int s = 0; s < states; s++) lam[s] *= m[s];
    }
    return lam;
}

// pi: a sum over every configuration of the parents, weighted by the
// table and by what each parent is saying. `configs` lists the parent
// state indices per row of `cpt`, last parent varying fastest; a root
// has one empty row and the sum collapses to its prior.
std::vector<double> piOf(int states,
                         const std::vector<std::vector<int>>& configs,
                         const std::vector<std::vector<double>>& cpt,
                         const std::vector<std::vector<double>>& fromParents) {
    std::vector<double> pi(states, 0.0);
    for (std::size_t c = 0; c < configs.size(); c++) {
        double w = 1.0;
        for (std::size_t i = 0; i < configs[c].size(); i++) w *= fromParents[i][configs[c][i]];
        if (w == 0.0) continue;
        for (int s = 0; s < states; s++) pi[s] += w * cpt[c][s];
    }
    return pi;
}

// The message to parent i, marginalising over the other parents weighted
// by what they believe. That product is why observing a node with two
// parents couples them: drop the k != i and a collider stops explaining
// anything away.
std::vector<double> lambdaToParent(std::size_t i, int parentStates, int states,
                                   const std::vector<double>& lambda,
                                   const std::vector<std::vector<int>>& configs,
                                   const std::vector<std::vector<double>>& cpt,
                                   const std::vector<std::vector<double>>& fromParents) {
    std::vector<double> out(parentStates, 0.0);
    for (std::size_t c = 0; c < configs.size(); c++) {
        double inner = 0.0;
        for (int s = 0; s < states; s++) inner += lambda[s] * cpt[c][s];
        if (inner == 0.0) continue;
        double w = 1.0;
        for (std::size_t k = 0; k < configs[c].size(); k++) {
            if (k != i) w *= fromParents[k][configs[c][k]];
        }
        out[configs[c][i]] += w * inner;
    }
    return out;
}

// The message to child j, leaving out what that child already said.
std::vector<double> piToChild(std::size_t j, int states, int observed,
                              const std::vector<double>& pi,
                              const std::vector<std::vector<double>>& fromChildren) {
    const std::vector<double> ev = evidenceFactor(states, observed);
    std::vector<double> out(states);
    for (int s = 0; s < states; s++) {
        double v = pi[s] * ev[s];
        for (std::size_t k = 0; k < fromChildren.size(); k++) {
            if (k != j) v *= fromChildren[k][s];
        }
        out[s] = v;
    }
    return out;
}

// BEL = alpha * lambda * pi.
std::vector<double> belief(const std::vector<double>& lambda, const std::vector<double>& pi) {
    std::vector<double> b(pi.size());
    double total = 0.0;
    for (std::size_t s = 0; s < pi.size(); s++) {
        b[s] = lambda[s] * pi[s];
        total += b[s];
    }
    if (!(total > 0.0)) return std::vector<double>(pi.size(), 1.0 / pi.size());
    for (double& v : b) v /= total;
    return b;
}

Explore further

• Hover any node with nothing set. Two groups fade: the wet-floor side and the fog side are independent, because the only route between them goes through an unobserved collider.
• Click fog, then hover the lidar. The camera fades. Click fog twice more to release it and the camera comes back, with the lidar now moving whenever the camera does.
• Click pose lost, then hover the wheel slip. Nothing fades at all on the lidar side any more. Setting one node made two halves of the graph relevant to each other.
• With the pose lost, click the lidar to yes and watch wheel slip fall from 50% to 29%. Click again for no and watch it jump to 87%.
• Click mission abort on its own and read the independent-pairs counter: 0 of 15. Then click the lidar and watch wheel slip fall, with the collider itself never observed.
• Turn on show π and λ and click a node. Every $\pi$ leaving it becomes 1.00 or 0.00, which is the point mass that makes it a barrier. The $\lambda$ values above it keep moving.
• Count the sweeps as you add evidence. It never exceeds six, and the graph is six edges wide, because each sweep carries every message exactly one edge further.