#![deny(missing_docs)]
#![warn(clippy::missing_docs_in_private_items)]
use crate::mdd::wmc::log_wmc_and_gradient;
use crate::mdd::{CompiledConstraint, Mdd};
use crate::modelling::ValueIndex;
const LOG_ZERO: f64 = -745.0;
fn safe_ln(p: f64) -> f64 {
if p > 0.0 { p.ln() } else { LOG_ZERO }
}
fn normalize_or_uniform(mut weights: Vec<f64>, domain_size: usize) -> Vec<f64> {
let total: f64 = weights.iter().sum();
if total <= 0.0 {
return vec![1.0 / domain_size as f64; domain_size];
}
for w in &mut weights {
*w /= total;
}
weights
}
fn check_inputs(
mdds: &[CompiledConstraint],
probs: &[Vec<f64>],
assignment: &[ValueIndex],
decided: &[bool],
) {
let num_vars = probs.len();
assert_eq!(
assignment.len(),
num_vars,
"belief_propagation: `assignment` has {} entries for {num_vars} variables",
assignment.len()
);
assert_eq!(
decided.len(),
num_vars,
"belief_propagation: `decided` has {} entries for {num_vars} variables",
decided.len()
);
for (var, row) in probs.iter().enumerate() {
assert!(
!row.is_empty(),
"belief_propagation: the prior of variable {var} is empty"
);
assert!(
row.iter().all(|p| p.is_finite() && *p >= 0.0),
"belief_propagation: the prior of variable {var} has a negative or non-finite \
weight: {row:?}"
);
assert!(
!decided[var] || assignment[var].0 < row.len(),
"belief_propagation: variable {var} is decided at value {} but its prior has only {} \
values",
assignment[var].0,
row.len()
);
}
for (mdd_index, mdd) in mdds.iter().enumerate() {
for layer in 0..mdd.number_decisions() {
let var = mdd.decision_at_layer(layer).0;
assert!(
var < num_vars,
"belief_propagation: MDD {mdd_index} branches on variable {var} but only \
{num_vars} priors were given"
);
}
}
}
fn build_var_to_mdds(mdds: &[CompiledConstraint], num_vars: usize) -> Vec<Vec<(usize, usize)>> {
let mut var_to_mdds: Vec<Vec<(usize, usize)>> = vec![Vec::new(); num_vars];
for (mdd_index, mdd) in mdds.iter().enumerate() {
for layer in 0..mdd.number_decisions() {
let variable = mdd.decision_at_layer(layer);
var_to_mdds[variable.0].push((mdd_index, layer));
}
}
var_to_mdds
}
fn log_combine_and_normalize(log_combined: Vec<f64>) -> Vec<f64> {
let max_log = log_combined
.iter()
.copied()
.fold(f64::NEG_INFINITY, f64::max);
let mut combined: Vec<f64> = log_combined.iter().map(|&l| (l - max_log).exp()).collect();
let total: f64 = combined.iter().sum();
for c in &mut combined {
*c /= total;
}
combined
}
fn one_hot(value: ValueIndex, domain_size: usize) -> Vec<f64> {
let mut weights = vec![0.0; domain_size];
weights[value.0] = 1.0;
weights
}
fn mdd_local_beliefs(mdd: &Mdd, messages: &[Vec<f64>]) -> Vec<Vec<f64>> {
log_wmc_and_gradient(mdd, messages)
.1
.into_iter()
.zip(messages)
.map(|(weights, m)| normalize_or_uniform(weights, m.len()))
.collect()
}
fn cavity_message(marginal: &[f64], local_belief: &[f64]) -> Vec<f64> {
let weights: Vec<f64> = marginal
.iter()
.zip(local_belief)
.map(|(&m, &l)| (safe_ln(m) - safe_ln(l)).exp())
.collect();
normalize_or_uniform(weights, marginal.len())
}
pub fn belief_propagation(
mdds: &[CompiledConstraint],
probs: &[Vec<f64>],
assignment: &[ValueIndex],
decided: &[bool],
iterations: usize,
) -> Vec<Vec<f64>> {
let num_vars = probs.len();
check_inputs(mdds, probs, assignment, decided);
let var_to_mdds = build_var_to_mdds(mdds, num_vars);
let priors: Vec<Vec<f64>> = (0..num_vars)
.map(|var| {
if decided[var] {
one_hot(assignment[var], probs[var].len())
} else {
probs[var].clone()
}
})
.collect();
let mut messages: Vec<Vec<Vec<f64>>> = mdds
.iter()
.map(|mdd| {
(0..mdd.number_decisions())
.map(|layer| priors[mdd.decision_at_layer(layer).0].clone())
.collect()
})
.collect();
let mut local_beliefs: Vec<Vec<Vec<f64>>> = mdds
.iter()
.map(|mdd| {
(0..mdd.number_decisions())
.map(|layer| vec![1.0; probs[mdd.decision_at_layer(layer).0].len()])
.collect()
})
.collect();
let mut marginal: Vec<Vec<f64>> = priors.clone();
for _ in 0..iterations {
for (mdd_index, mdd) in mdds.iter().enumerate() {
local_beliefs[mdd_index] = mdd_local_beliefs(mdd, &messages[mdd_index]);
}
let mut log_marginal: Vec<Vec<f64>> = priors
.iter()
.map(|p| p.iter().map(|&v| safe_ln(v)).collect())
.collect();
for var in 0..num_vars {
if decided[var] {
continue;
}
for &(mdd_index, layer) in &var_to_mdds[var] {
let belief = &local_beliefs[mdd_index][layer];
for (d, log_d) in log_marginal[var].iter_mut().enumerate() {
*log_d += safe_ln(belief[d]);
}
}
}
marginal = log_marginal
.into_iter()
.map(log_combine_and_normalize)
.collect();
for var in 0..num_vars {
for &(mdd_index, layer) in &var_to_mdds[var] {
messages[mdd_index][layer] = if decided[var] {
priors[var].clone()
} else {
cavity_message(&marginal[var], &local_beliefs[mdd_index][layer])
};
}
}
}
marginal
}
#[cfg(test)]
mod tests {
use super::*;
use crate::constraints::{all_different, gcc, not_equals, sum};
use crate::mdd::Compiler;
use crate::mdd::heuristics::{
CompilationHeuristic, MergeHeuristic, OrderingHeuristic, SelectHeuristic,
};
use crate::modelling::{ConstraintIndex, Problem};
use rand::rngs::StdRng;
use rand::{RngExt, SeedableRng};
use std::sync::Arc;
fn build_mdd(problem: Arc<Problem>, constraints: &[ConstraintIndex]) -> CompiledConstraint {
let mut compiler = Compiler::new(
problem,
CompilationHeuristic {
ordering: OrderingHeuristic::MinDomMaxLinked,
merge: MergeHeuristic::LessRelaxed,
selection: SelectHeuristic::Greedy,
},
constraints,
);
compiler.refine(usize::MAX);
CompiledConstraint::from_mdd(compiler.into_mdd())
}
#[test]
fn belief_propagation_indexes_messages_by_mdd_layer_not_by_global_variable_id() {
let mut problem = Problem::default();
let _w = problem.add_variable(vec![0, 1, 2, 3, 4]);
let x = problem.add_variable(vec![0, 1]);
let y = problem.add_variable(vec![0, 1]);
not_equals(&mut problem, x, y);
let problem = Arc::new(problem);
let constraints: Vec<ConstraintIndex> = problem.iter_constraints().collect();
let mdd = build_mdd(problem.clone(), &constraints);
let mdds = vec![mdd];
let probs = vec![vec![0.2; 5], vec![0.9, 0.1], vec![0.9, 0.1]];
let assignment = vec![ValueIndex(0); 3];
let decided = vec![false; 3];
let marginals = belief_propagation(&mdds, &probs, &assignment, &decided, 1);
assert!((marginals[x.0][0] - 0.5).abs() < 1e-9, "{marginals:?}");
assert!((marginals[x.0][1] - 0.5).abs() < 1e-9, "{marginals:?}");
assert!((marginals[y.0][0] - 0.5).abs() < 1e-9, "{marginals:?}");
assert!((marginals[y.0][1] - 0.5).abs() < 1e-9, "{marginals:?}");
}
#[test]
fn zero_iterations_returns_probs_unchanged() {
let mut problem = Problem::default();
let x = problem.add_variable(vec![0, 1]);
let y = problem.add_variable(vec![0, 1]);
not_equals(&mut problem, x, y);
let problem = Arc::new(problem);
let constraints: Vec<ConstraintIndex> = problem.iter_constraints().collect();
let mdd = build_mdd(problem.clone(), &constraints);
let mdds = vec![mdd];
let probs = vec![vec![0.9, 0.1], vec![0.3, 0.7]];
let assignment = vec![ValueIndex(0); 2];
let decided = vec![false; 2];
let marginals = belief_propagation(&mdds, &probs, &assignment, &decided, 0);
assert_eq!(marginals, probs);
}
#[test]
fn single_not_equals_mdd_with_symmetric_conflicting_prior_becomes_uniform_after_one_iteration()
{
let mut problem = Problem::default();
let x = problem.add_variable(vec![0, 1]);
let y = problem.add_variable(vec![0, 1]);
not_equals(&mut problem, x, y);
let problem = Arc::new(problem);
let constraints: Vec<ConstraintIndex> = problem.iter_constraints().collect();
let mdd = build_mdd(problem.clone(), &constraints);
let mdds = vec![mdd];
let probs = vec![vec![0.9, 0.1], vec![0.9, 0.1]];
let assignment = vec![ValueIndex(0); 2];
let decided = vec![false; 2];
let marginals = belief_propagation(&mdds, &probs, &assignment, &decided, 1);
assert_eq!(marginals.len(), 2);
for marginal in &marginals {
assert!((marginal[0] - 0.5).abs() < 1e-9, "{marginals:?}");
assert!((marginal[1] - 0.5).abs() < 1e-9, "{marginals:?}");
}
}
#[test]
fn deciding_one_variable_clamps_it_and_propagates_as_hard_evidence_to_the_other() {
let mut problem = Problem::default();
let x = problem.add_variable(vec![0, 1]);
let y = problem.add_variable(vec![0, 1]);
not_equals(&mut problem, x, y);
let problem = Arc::new(problem);
let constraints: Vec<ConstraintIndex> = problem.iter_constraints().collect();
let mdd = build_mdd(problem.clone(), &constraints);
let mdds = vec![mdd];
let probs = vec![vec![0.9, 0.1], vec![0.9, 0.1]];
let mut assignment = vec![ValueIndex(0); 2];
assignment[x.0] = ValueIndex(0);
let mut decided = vec![false; 2];
decided[x.0] = true;
let marginals = belief_propagation(&mdds, &probs, &assignment, &decided, 1);
assert!((marginals[x.0][0] - 1.0).abs() < 1e-9, "{marginals:?}");
assert!((marginals[x.0][1] - 0.0).abs() < 1e-9, "{marginals:?}");
assert!((marginals[y.0][0] - 0.0).abs() < 1e-9, "{marginals:?}");
assert!((marginals[y.0][1] - 1.0).abs() < 1e-9, "{marginals:?}");
}
#[test]
fn uninformative_mdds_leave_the_marginal_close_to_the_prior_after_any_number_of_iterations() {
let probs = vec![vec![0.7, 0.2, 0.1]];
for count in [1, 5] {
let mdds: Vec<CompiledConstraint> = (0..count)
.map(|_| {
let mut problem = Problem::default();
let x = problem.add_variable(vec![0, 1, 2]);
gcc(&mut problem, vec![x], vec![]);
let problem = Arc::new(problem);
let constraints: Vec<ConstraintIndex> = problem.iter_constraints().collect();
build_mdd(problem, &constraints)
})
.collect();
for iterations in [1, 3] {
let assignment = vec![ValueIndex(0)];
let decided = vec![false];
let marginals =
belief_propagation(&mdds, &probs, &assignment, &decided, iterations);
assert_eq!(marginals.len(), 1);
for d in 0..3 {
assert!(
(marginals[0][d] - probs[0][d]).abs() < 1e-6,
"count={count}, iterations={iterations}, d={d}, marginals={marginals:?}"
);
}
}
}
}
fn not_equals_inputs() -> (Vec<CompiledConstraint>, Vec<Vec<f64>>) {
let mut problem = Problem::default();
let x = problem.add_variable(vec![0, 1]);
let y = problem.add_variable(vec![0, 1]);
not_equals(&mut problem, x, y);
let problem = Arc::new(problem);
let constraints: Vec<ConstraintIndex> = problem.iter_constraints().collect();
(
vec![build_mdd(problem, &constraints)],
vec![vec![0.5, 0.5], vec![0.5, 0.5]],
)
}
#[test]
#[should_panic(expected = "`assignment` has 1 entries for 2 variables")]
fn an_assignment_of_the_wrong_length_panics() {
let (mdds, probs) = not_equals_inputs();
belief_propagation(&mdds, &probs, &[ValueIndex(0)], &[false; 2], 1);
}
#[test]
#[should_panic(expected = "`decided` has 3 entries for 2 variables")]
fn a_decided_mask_of_the_wrong_length_panics() {
let (mdds, probs) = not_equals_inputs();
belief_propagation(&mdds, &probs, &[ValueIndex(0); 2], &[false; 3], 1);
}
#[test]
#[should_panic(expected = "the prior of variable 1 is empty")]
fn an_empty_prior_panics() {
let (mdds, mut probs) = not_equals_inputs();
probs[1] = vec![];
belief_propagation(&mdds, &probs, &[ValueIndex(0); 2], &[false; 2], 1);
}
#[test]
#[should_panic(expected = "the prior of variable 0 has a negative or non-finite weight")]
fn a_negative_prior_weight_panics() {
let (mdds, mut probs) = not_equals_inputs();
probs[0] = vec![1.5, -0.5];
belief_propagation(&mdds, &probs, &[ValueIndex(0); 2], &[false; 2], 1);
}
#[test]
#[should_panic(expected = "the prior of variable 0 has a negative or non-finite weight")]
fn a_nan_prior_weight_panics() {
let (mdds, mut probs) = not_equals_inputs();
probs[0] = vec![f64::NAN, 0.5];
belief_propagation(&mdds, &probs, &[ValueIndex(0); 2], &[false; 2], 1);
}
#[test]
#[should_panic(expected = "variable 1 is decided at value 2 but its prior has only 2 values")]
fn a_decided_value_outside_its_prior_panics() {
let (mdds, probs) = not_equals_inputs();
belief_propagation(
&mdds,
&probs,
&[ValueIndex(0), ValueIndex(2)],
&[false, true],
1,
);
}
#[test]
#[should_panic(expected = "MDD 0 branches on variable 1 but only 1 priors were given")]
fn an_mdd_over_a_variable_without_prior_panics() {
let (mdds, probs) = not_equals_inputs();
belief_propagation(&mdds, &probs[..1], &[ValueIndex(0)], &[false], 1);
}
#[test]
fn an_unsatisfiable_mdd_sends_no_information() {
let (mdds, probs) = not_equals_inputs();
let marginals = belief_propagation(&mdds, &probs, &[ValueIndex(0); 2], &[true, true], 2);
for marginal in &marginals {
assert!((marginal[0] - 1.0).abs() < 1e-12, "{marginals:?}");
assert!(marginal[1] < 1e-12, "{marginals:?}");
}
}
fn exact_marginals(problem: &Problem, priors: &[Vec<f64>]) -> Vec<Vec<f64>> {
let sizes: Vec<usize> = priors.iter().map(Vec::len).collect();
let mut marginals: Vec<Vec<f64>> = sizes.iter().map(|&n| vec![0.0; n]).collect();
let mut assignment = vec![0isize; sizes.len()];
loop {
if problem.is_solution(&assignment) {
let weight: f64 = assignment
.iter()
.enumerate()
.map(|(var, &value)| priors[var][value as usize])
.product();
for (var, &value) in assignment.iter().enumerate() {
marginals[var][value as usize] += weight;
}
}
let mut var = 0;
while var < sizes.len() {
assignment[var] += 1;
if (assignment[var] as usize) < sizes[var] {
break;
}
assignment[var] = 0;
var += 1;
}
if var == sizes.len() {
break;
}
}
marginals
.into_iter()
.map(|row| {
let total: f64 = row.iter().sum();
row.into_iter().map(|w| w / total).collect()
})
.collect()
}
#[test]
fn with_a_single_constraint_one_round_gives_the_exact_marginals() {
type Build = fn(&mut Problem) -> Vec<crate::modelling::VariableIndex>;
let cases: [(&str, Build); 3] = [
("all_different", |problem| {
let vars = problem.add_variables(4, vec![0, 1, 2]);
all_different(problem, vars[..3].to_vec());
vars
}),
("sum", |problem| {
let vars = problem.add_variables(4, vec![0, 1, 2]);
sum(problem, vars[..3].to_vec(), 3);
vars
}),
("gcc", |problem| {
let vars = problem.add_variables(4, vec![0, 1, 2]);
gcc(problem, vars.clone(), vec![(0, 1, 2), (1, 0, 1), (2, 1, 3)]);
vars
}),
];
let mut rng = StdRng::seed_from_u64(7);
for (name, build) in cases {
let mut problem = Problem::default();
build(&mut problem);
let problem = Arc::new(problem);
let constraints: Vec<ConstraintIndex> = problem.iter_constraints().collect();
let mdds = vec![build_mdd(problem.clone(), &constraints)];
let n = problem.number_variables();
for decide_first in [false, true] {
for _ in 0..10 {
let probs: Vec<Vec<f64>> = (0..n)
.map(|_| {
let weights: Vec<f64> =
(0..3).map(|_| rng.random_range(0.05..1.0)).collect();
let total: f64 = weights.iter().sum();
weights.into_iter().map(|w| w / total).collect()
})
.collect();
let mut assignment = vec![ValueIndex(0); n];
let mut decided = vec![false; n];
let mut reference_priors = probs.clone();
if decide_first {
assignment[0] = ValueIndex(1);
decided[0] = true;
reference_priors[0] = one_hot(ValueIndex(1), 3);
}
let expected = exact_marginals(&problem, &reference_priors);
for iterations in [1, 3] {
let marginals =
belief_propagation(&mdds, &probs, &assignment, &decided, iterations);
for var in 0..n {
for value in 0..3 {
assert!(
(marginals[var][value] - expected[var][value]).abs() < 1e-9,
"{name}, decided={decide_first}, iterations={iterations}, \
variable {var}, value {value}: got {marginals:?}, \
expected {expected:?}"
);
}
}
}
}
}
}
}
}