use std::collections::{HashMap, HashSet};
use std::sync::Arc;
use std::time::Instant;
use burn::tensor::Tensor;
use burn::tensor::backend::Backend;
use indicatif::{ParallelProgressIterator, ProgressBar, ProgressStyle};
use rayon::prelude::*;
use crate::learning::Loss;
use crate::mdd::arena::{MddCompilationConfig, compile_constraints};
use crate::mdd::wmc::log_wmc_and_gradient;
use crate::mdd::{CompiledConstraint, MddArena};
use crate::modelling::Problem;
use super::utils::{blend_with_current, gumbel_softmax};
use crate::neural::consformer::ConsFormerBatch;
const WMC_EPS: f64 = 1e-6;
fn log_add_exp(a: f64, b: f64) -> f64 {
let largest = a.max(b);
largest + ((a - largest).exp() + (b - largest).exp()).ln()
}
fn layer_weights_from_probs(
constraint: &CompiledConstraint,
real_problem: &Problem,
probs_for_sample: &[f32],
domain_size: usize,
) -> Vec<Vec<f64>> {
let num_layers = constraint.order.len();
let mut weights: Vec<Vec<f64>> = Vec::with_capacity(num_layers);
for layer in 0..num_layers {
let variable = constraint.decision_at_layer(layer);
let mut layer_weights = vec![0.0; domain_size];
for (raw_value, w) in layer_weights.iter_mut().enumerate() {
if real_problem[variable].in_domain(raw_value as isize) {
*w = probs_for_sample[variable.0 * domain_size + raw_value] as f64;
}
}
weights.push(layer_weights);
}
weights
}
fn mdd_loss_and_gradient(
constraint: &CompiledConstraint,
real_problem: &Problem,
probs_for_sample: &[f32],
domain_size: usize,
grad: &mut [f32],
) -> f64 {
let weights = layer_weights_from_probs(constraint, real_problem, probs_for_sample, domain_size);
let (log_wmc, gradient) = log_wmc_and_gradient(constraint, &weights);
let log_total = log_add_exp(log_wmc, WMC_EPS.ln());
let chain = -(log_wmc - log_total).exp();
for (layer, layer_gradient) in gradient.iter().enumerate() {
let variable = constraint.decision_at_layer(layer);
for (raw_value, &g) in layer_gradient.iter().enumerate() {
if real_problem[variable].in_domain(raw_value as isize) {
grad[variable.0 * domain_size + raw_value] += (chain * g) as f32;
}
}
}
-log_total
}
fn sample_loss_and_gradient(
constraints: &[CompiledConstraint],
real_problem: &Problem,
probs_for_sample: &[f32],
number_vars: usize,
domain_size: usize,
) -> (f64, Vec<f32>) {
let mut grad = vec![0.0f32; number_vars * domain_size];
let mut loss_sum = 0.0;
for constraint in constraints {
loss_sum += mdd_loss_and_gradient(
constraint,
real_problem,
probs_for_sample,
domain_size,
&mut grad,
);
}
let denom = constraints.len().max(1) as f64;
let loss = loss_sum / denom;
for g in &mut grad {
*g /= denom as f32;
}
(loss, grad)
}
pub struct DecomposedMddLoss {
compilation: MddCompilationConfig,
domain_size: usize,
arena: MddArena,
problems: Vec<Arc<Problem>>,
compiled: HashMap<usize, Vec<CompiledConstraint>>,
}
impl DecomposedMddLoss {
pub fn new(compilation: MddCompilationConfig, domain_size: usize) -> Self {
Self {
compilation: MddCompilationConfig {
max_width: usize::MAX,
..compilation
},
domain_size,
arena: MddArena::new(),
problems: Vec::new(),
compiled: HashMap::new(),
}
}
fn compile(&mut self, problems: &[Arc<Problem>]) {
let mut seen = HashSet::new();
let unique: Vec<Arc<Problem>> = problems
.iter()
.filter(|problem| seen.insert(Self::key(problem)))
.cloned()
.collect();
let progress = ProgressBar::new(unique.len() as u64);
progress.set_style(
ProgressStyle::with_template(
"{msg} [{elapsed_precise}] [{bar:40.cyan/blue}] {pos}/{len} ({eta})",
)
.expect("hard-coded progress bar template should always be valid"),
);
progress.set_message("Compiling MDDs");
let start = Instant::now();
let compiled: Vec<Vec<CompiledConstraint>> = crate::utils::worker_pool().install(|| {
unique
.par_iter()
.progress_with(progress.clone())
.map(|problem| {
compile_constraints(problem, &self.arena, &self.compilation, self.domain_size)
})
.collect()
});
progress.finish_and_clear();
crate::diagnostics::data_log!(
"mdd_compilation",
num_problems = unique.len(),
elapsed_s = start.elapsed().as_secs_f64(),
);
self.compiled = unique.iter().map(Self::key).zip(compiled).collect();
self.problems = unique;
}
fn key(problem: &Arc<Problem>) -> usize {
Arc::as_ptr(problem) as usize
}
fn compiled_for(&self, problem: &Arc<Problem>) -> &[CompiledConstraint] {
match self.compiled.get(&Self::key(problem)) {
Some(constraints) => constraints,
None => panic!(
"DecomposedMddLoss was given a problem it has not compiled: `prepare` must be \
called with every training and validation problem"
),
}
}
}
impl DecomposedMddLoss {
fn wmc_loss<B: Backend>(
&self,
probs: Tensor<B, 3>,
batch: &ConsFormerBatch<B>,
) -> Tensor<B, 1> {
let device = probs.device();
let [batch_size, number_vars, domain_size] = probs.dims();
let probs_data: Vec<f32> = probs
.clone()
.into_data()
.to_vec::<f32>()
.expect("probs should convert to f32");
let compiled: Vec<&[CompiledConstraint]> = batch
.problems
.iter()
.map(|problem| self.compiled_for(problem))
.collect();
let results: Vec<(f64, Vec<f32>)> = crate::utils::worker_pool().install(|| {
compiled
.par_iter()
.zip(batch.problems.par_iter())
.enumerate()
.map(|(i, (constraints, real_problem))| {
let start = i * number_vars * domain_size;
let sample_probs = &probs_data[start..start + number_vars * domain_size];
sample_loss_and_gradient(
constraints,
real_problem,
sample_probs,
number_vars,
domain_size,
)
})
.collect()
});
let loss_value: f64 = results.iter().map(|(loss, _)| loss).sum::<f64>() / batch_size as f64;
let mut grad_data = vec![0.0f32; batch_size * number_vars * domain_size];
for (i, (_, grad)) in results.iter().enumerate() {
let start = i * number_vars * domain_size;
for (j, &g) in grad.iter().enumerate() {
grad_data[start + j] = g / batch_size as f32;
}
}
let grad_tensor: Tensor<B, 3> = Tensor::<B, 1>::from_data(grad_data.as_slice(), &device)
.reshape([batch_size, number_vars, domain_size]);
let loss_tensor: Tensor<B, 1> = Tensor::from_data([loss_value as f32].as_slice(), &device);
(grad_tensor * (probs.clone() - probs.detach()))
.sum()
.reshape([1])
+ loss_tensor
}
}
impl<B: Backend> Loss<B, ConsFormerBatch<B>> for DecomposedMddLoss {
fn prepare(&mut self, problems: &[Arc<Problem>]) {
self.compile(problems);
}
fn loss(&self, logits: Tensor<B, 3>, batch: &ConsFormerBatch<B>) -> Tensor<B, 1> {
let probs = gumbel_softmax(logits);
let probs = blend_with_current(probs, batch.assignments.clone(), batch.var_masks.clone());
self.wmc_loss(probs, batch)
}
}
#[cfg(test)]
mod compile_tests {
use super::*;
use crate::constraints::{all_different, among, not_equals, sum};
fn brute_force_wmc(
constraint: &CompiledConstraint,
real_problem: &Problem,
probs: &[f64],
domain_size: usize,
) -> f64 {
let num_layers = constraint.order.len();
let mut weights = Vec::with_capacity(num_layers);
for layer in 0..num_layers {
let variable = constraint.decision_at_layer(layer);
let mut layer_weights = vec![0.0; domain_size];
for (raw_value, w) in layer_weights.iter_mut().enumerate() {
if real_problem[variable].in_domain(raw_value as isize) {
*w = probs[variable.0 * domain_size + raw_value];
}
}
weights.push(layer_weights);
}
crate::mdd::wmc::wmc(constraint, &weights)
}
#[test]
fn compile_constraints_matches_brute_force_for_not_equals() {
let mut problem = Problem::default();
let x = problem.add_variable(vec![0, 1, 2]);
let y = problem.add_variable(vec![0, 1, 2]);
not_equals(&mut problem, x, y);
let problem = Arc::new(problem);
let domain_size = 3;
let arena = MddArena::new();
let mdds = compile_constraints(
&problem,
&arena,
&MddCompilationConfig::default(),
domain_size,
);
assert_eq!(mdds.len(), 1);
assert_eq!(mdds[0].number_layers() - 1, 2);
let probs: Vec<f64> = vec![
0.2, 0.5, 0.3, 0.1, 0.3, 0.6, ];
let wmc = brute_force_wmc(&mdds[0], &problem, &probs, domain_size);
let mut brute = 0.0;
for xv in 0..domain_size {
for yv in 0..domain_size {
if xv != yv {
brute += probs[xv] * probs[domain_size + yv];
}
}
}
assert!((wmc - brute).abs() < 1e-9, "wmc={wmc} brute={brute}");
}
#[test]
fn compile_constraints_matches_brute_force_for_all_different_permutation() {
let mut problem = Problem::default();
let vars = problem.add_variables(3, vec![0, 1, 2]);
all_different(&mut problem, vars.clone());
let problem = Arc::new(problem);
let domain_size = 3;
let arena = MddArena::new();
let mdds = compile_constraints(
&problem,
&arena,
&MddCompilationConfig::default(),
domain_size,
);
assert_eq!(mdds.len(), 1);
assert_eq!(mdds[0].number_layers() - 1, 3);
let probs: Vec<f64> = vec![
0.5, 0.3, 0.2, 0.2, 0.2, 0.6, 0.1, 0.4, 0.5, ];
let wmc = brute_force_wmc(&mdds[0], &problem, &probs, domain_size);
let mut brute = 0.0;
for a in 0..domain_size {
for b in 0..domain_size {
for c in 0..domain_size {
if a != b && b != c && a != c {
brute += probs[a] * probs[domain_size + b] * probs[2 * domain_size + c];
}
}
}
}
assert!((wmc - brute).abs() < 1e-9, "wmc={wmc} brute={brute}");
}
#[test]
fn compile_constraints_matches_brute_force_for_sum() {
let mut problem = Problem::default();
let vars = problem.add_variables(3, vec![0, 1, 2]);
sum(&mut problem, vars.clone(), 3);
let problem = Arc::new(problem);
let domain_size = 3;
let arena = MddArena::new();
let mdds = compile_constraints(
&problem,
&arena,
&MddCompilationConfig::default(),
domain_size,
);
let probs: Vec<f64> = vec![
0.5, 0.3, 0.2, 0.2, 0.2, 0.6, 0.1, 0.4, 0.5, ];
let wmc = brute_force_wmc(&mdds[0], &problem, &probs, domain_size);
let mut brute = 0.0;
for a in 0..domain_size {
for b in 0..domain_size {
for c in 0..domain_size {
if a + b + c == 3 {
brute += probs[a] * probs[domain_size + b] * probs[2 * domain_size + c];
}
}
}
}
assert!((wmc - brute).abs() < 1e-9, "wmc={wmc} brute={brute}");
}
#[test]
fn compile_constraints_matches_brute_force_for_among() {
let mut problem = Problem::default();
let vars = problem.add_variables(3, vec![0, 1, 2]);
among(&mut problem, vars.clone(), vec![1, 2], 1, 2);
let problem = Arc::new(problem);
let domain_size = 3;
let arena = MddArena::new();
let mdds = compile_constraints(
&problem,
&arena,
&MddCompilationConfig::default(),
domain_size,
);
let probs: Vec<f64> = vec![
0.5, 0.3, 0.2, 0.2, 0.2, 0.6, 0.1, 0.4, 0.5, ];
let wmc = brute_force_wmc(&mdds[0], &problem, &probs, domain_size);
let mut brute = 0.0;
for a in 0..domain_size {
for b in 0..domain_size {
for c in 0..domain_size {
let count = [a, b, c].iter().filter(|&&v| v == 1 || v == 2).count();
if (1..=2).contains(&count) {
brute += probs[a] * probs[domain_size + b] * probs[2 * domain_size + c];
}
}
}
}
assert!((wmc - brute).abs() < 1e-9, "wmc={wmc} brute={brute}");
}
#[test]
fn unsat_constraint_gets_zero_wmc() {
let mut problem = Problem::default();
let vars = problem.add_variables(3, vec![0, 1]);
all_different(&mut problem, vars.clone());
let problem = Arc::new(problem);
let domain_size = 2;
let arena = MddArena::new();
let mdds = compile_constraints(
&problem,
&arena,
&MddCompilationConfig::default(),
domain_size,
);
let probs: Vec<f64> = vec![0.5, 0.5, 0.5, 0.5, 0.5, 0.5];
assert_eq!(
brute_force_wmc(&mdds[0], &problem, &probs, domain_size),
0.0
);
}
#[test]
#[should_panic(expected = "out of the nominal")]
fn compile_constraints_panics_when_domain_size_is_too_small() {
let mut problem = Problem::default();
let x = problem.add_variable(vec![0, 1, 2]);
let y = problem.add_variable(vec![0, 1, 2]);
not_equals(&mut problem, x, y);
let problem = Arc::new(problem);
let arena = MddArena::new();
compile_constraints(&problem, &arena, &MddCompilationConfig::default(), 2);
}
#[test]
fn compiling_many_problems_matches_compiling_each_alone() {
let mut problems = Vec::new();
for domain_max in 0isize..40 {
let mut problem = Problem::default();
let domain: Vec<isize> = (0..=(domain_max % 5 + 2)).collect();
let vars = problem.add_variables(3, domain);
all_different(&mut problem, vars.clone());
not_equals(&mut problem, vars[0], vars[1]);
problems.push(Arc::new(problem));
}
let domain_size = 7;
let mut loss_fn = DecomposedMddLoss::new(MddCompilationConfig::default(), domain_size);
loss_fn.compile(&problems);
assert_eq!(loss_fn.compiled.len(), problems.len());
for problem in &problems {
let expected = compile_constraints(
problem,
&MddArena::new(),
&MddCompilationConfig::default(),
domain_size,
);
let actual = loss_fn.compiled_for(problem);
assert_eq!(actual.len(), expected.len());
for (a, e) in actual.iter().zip(expected.iter()) {
assert_eq!(a.number_layers(), e.number_layers());
assert_eq!(a.number_nodes(), e.number_nodes());
assert_eq!(a.number_edges(), e.number_edges());
}
}
}
#[test]
fn a_problem_given_twice_is_compiled_once() {
let mut problem = Problem::default();
let vars = problem.add_variables(3, vec![0, 1, 2]);
all_different(&mut problem, vars);
let problem = Arc::new(problem);
let mut loss_fn = DecomposedMddLoss::new(MddCompilationConfig::default(), 3);
loss_fn.compile(&[Arc::clone(&problem), Arc::clone(&problem)]);
assert_eq!(loss_fn.compiled.len(), 1);
assert_eq!(loss_fn.compiled_for(&problem).len(), 1);
}
#[test]
#[should_panic(expected = "has not compiled")]
fn scoring_a_problem_that_was_not_prepared_panics() {
let build = || {
let mut problem = Problem::default();
let x = problem.add_variable(vec![0, 1, 2]);
let y = problem.add_variable(vec![0, 1, 2]);
not_equals(&mut problem, x, y);
Arc::new(problem)
};
let mut loss_fn = DecomposedMddLoss::new(MddCompilationConfig::default(), 3);
loss_fn.compile(&[build()]);
loss_fn.compiled_for(&build());
}
}
#[cfg(test)]
mod loss_tests {
use std::sync::Arc;
use burn::backend::ndarray::{NdArray, NdArrayDevice};
use burn::data::dataloader::batcher::Batcher;
use burn::data::dataset::Dataset;
use crate::constraints::{all_different, not_equals};
use crate::mdd::MddArena;
use crate::mdd::arena::MddCompilationConfig;
use crate::modelling::Problem;
use burn::tensor::Int;
use super::*;
use crate::neural::consformer::{ConsFormerBatcher, ConsFormerDataset};
fn two_sample_batch<B: Backend>(
device: &B::Device,
mask_fraction: f64,
) -> (ConsFormerBatch<B>, DecomposedMddLoss) {
let mut problems = Vec::new();
for _ in 0..2 {
let mut problem = Problem::default();
let vars = problem.add_variables(3, vec![0, 1, 2]);
all_different(&mut problem, vars.clone());
not_equals(&mut problem, vars[0], vars[1]);
problems.push(Arc::new(problem));
}
let mut loss_fn = DecomposedMddLoss::new(MddCompilationConfig::default(), 3);
loss_fn.compile(&problems);
let dataset = ConsFormerDataset::<B>::new(problems, device);
let samples: Vec<_> = (0..dataset.len())
.map(|i| dataset.get(i).unwrap())
.collect();
let batcher = ConsFormerBatcher {
mask_fraction,
destroy: None,
};
(batcher.batch(samples, device), loss_fn)
}
fn brute_force_not_equals(probs: &[f64], domain_size: usize) -> f64 {
let mut brute = 0.0;
for a in 0..domain_size {
for b in 0..domain_size {
if a != b {
brute += probs[a] * probs[domain_size + b];
}
}
}
brute
}
fn brute_force_all_different_permutation(probs: &[f64], domain_size: usize) -> f64 {
let mut brute = 0.0;
for a in 0..domain_size {
for b in 0..domain_size {
for c in 0..domain_size {
if a != b && b != c && a != c {
brute += probs[a] * probs[domain_size + b] * probs[2 * domain_size + c];
}
}
}
}
brute
}
fn plain_average(wmcs: &[f64]) -> f64 {
let loss_sum: f64 = wmcs.iter().map(|&wmc| -(wmc + WMC_EPS).ln()).sum();
loss_sum / (wmcs.len().max(1) as f64)
}
#[test]
fn sample_loss_and_gradient_matches_brute_force_average() {
let mut problem = Problem::default();
let vars = problem.add_variables(3, vec![0, 1, 2]);
all_different(&mut problem, vars.clone());
not_equals(&mut problem, vars[0], vars[1]);
let problem = Arc::new(problem);
let mut loss_fn = DecomposedMddLoss::new(MddCompilationConfig::default(), 3);
loss_fn.compile(&[Arc::clone(&problem)]);
let mdds = loss_fn.compiled_for(&problem);
let probs: Vec<f32> = vec![0.2, 0.5, 0.3, 0.1, 0.3, 0.6, 0.4, 0.4, 0.2];
let (loss, _grad) = sample_loss_and_gradient(mdds, &problem, &probs, 3, 3);
let probs_f64: Vec<f64> = probs.iter().map(|&v| v as f64).collect();
let not_equals_wmc = brute_force_not_equals(&probs_f64, 3);
let all_different_wmc = brute_force_all_different_permutation(&probs_f64, 3);
let expected = plain_average(&[not_equals_wmc, all_different_wmc]);
assert!(
(loss - expected).abs() < 1e-6,
"got {loss} expected {expected}"
);
}
#[test]
fn sample_loss_and_gradient_matches_finite_differences() {
let mut problem = Problem::default();
let vars = problem.add_variables(3, vec![0, 1, 2]);
all_different(&mut problem, vars.clone());
not_equals(&mut problem, vars[0], vars[1]);
let problem = Arc::new(problem);
let mut loss_fn = DecomposedMddLoss::new(MddCompilationConfig::default(), 3);
loss_fn.compile(&[Arc::clone(&problem)]);
let mdds = loss_fn.compiled_for(&problem);
let probs: Vec<f32> = vec![0.2, 0.5, 0.3, 0.1, 0.3, 0.6, 0.4, 0.4, 0.2];
let (base_loss, grad) = sample_loss_and_gradient(mdds, &problem, &probs, 3, 3);
let eps = 1e-4f32;
for i in 0..probs.len() {
let mut bumped = probs.clone();
bumped[i] += eps;
let (bumped_loss, _) = sample_loss_and_gradient(mdds, &problem, &bumped, 3, 3);
let finite_diff = (bumped_loss - base_loss) / eps as f64;
assert!(
(finite_diff - grad[i] as f64).abs() < 1e-2,
"index {i}: analytic={} finite_diff={finite_diff}",
grad[i],
);
}
}
#[test]
fn mdd_wmc_loss_averages_per_sample_then_per_batch() {
let device = NdArrayDevice::default();
let domain_size = 3;
let (batch, loss_fn) = two_sample_batch::<NdArray>(&device, 0.0);
let per_sample_probs: Vec<Vec<f64>> = vec![
vec![0.2, 0.5, 0.3, 0.1, 0.3, 0.6, 0.4, 0.4, 0.2],
vec![0.6, 0.3, 0.1, 0.2, 0.2, 0.6, 0.5, 0.25, 0.25],
];
let flat: Vec<f32> = per_sample_probs
.iter()
.flatten()
.map(|&v| v as f32)
.collect();
let probs: Tensor<NdArray, 3> =
Tensor::<NdArray, 1>::from_data(flat.as_slice(), &device).reshape([2, 3, domain_size]);
let loss = loss_fn.wmc_loss(probs, &batch);
let loss_value: f32 = loss.into_data().to_vec::<f32>().unwrap()[0];
let mut expected_per_sample = Vec::new();
for probs in &per_sample_probs {
let not_equals_wmc = brute_force_not_equals(probs, domain_size);
let all_different_wmc = brute_force_all_different_permutation(probs, domain_size);
expected_per_sample.push(plain_average(&[not_equals_wmc, all_different_wmc]));
}
let expected = expected_per_sample.iter().sum::<f64>() / expected_per_sample.len() as f64;
assert!(
(loss_value as f64 - expected).abs() < 1e-4,
"got {loss_value} expected {expected}"
);
}
#[test]
fn mdd_wmc_loss_gradient_matches_finite_differences_via_autodiff() {
use burn::backend::Autodiff;
type ADBackend = Autodiff<NdArray>;
let ad_device = NdArrayDevice::default();
let plain_device = NdArrayDevice::default();
let domain_size = 3;
let (batch_ad, loss_ad) = two_sample_batch::<ADBackend>(&ad_device, 0.0);
let (batch_plain, loss_plain) = two_sample_batch::<NdArray>(&plain_device, 0.0);
let flat: Vec<f32> = vec![
0.2, 0.5, 0.3, 0.1, 0.3, 0.6, 0.4, 0.4, 0.2, 0.6, 0.3, 0.1, 0.2, 0.2, 0.6, 0.5, 0.25,
0.25,
];
let probs_ad: Tensor<ADBackend, 3> =
Tensor::<ADBackend, 1>::from_data(flat.as_slice(), &ad_device)
.reshape([2, 3, domain_size])
.require_grad();
let loss = loss_ad.wmc_loss(probs_ad.clone(), &batch_ad);
let grads = loss.backward();
let grad = probs_ad
.grad(&grads)
.expect("probs should have a gradient after backward()");
let grad_values: Vec<f32> = grad.into_data().to_vec::<f32>().unwrap();
let base_tensor: Tensor<NdArray, 3> =
Tensor::<NdArray, 1>::from_data(flat.as_slice(), &plain_device).reshape([
2,
3,
domain_size,
]);
let base_loss_tensor = loss_plain.wmc_loss(base_tensor, &batch_plain);
let base_loss: f64 = base_loss_tensor.into_data().to_vec::<f32>().unwrap()[0] as f64;
let eps = 1e-4f32;
for i in 0..flat.len() {
let mut bumped = flat.clone();
bumped[i] += eps;
let bumped_tensor: Tensor<NdArray, 3> =
Tensor::<NdArray, 1>::from_data(bumped.as_slice(), &plain_device).reshape([
2,
3,
domain_size,
]);
let bumped_loss_tensor = loss_plain.wmc_loss(bumped_tensor, &batch_plain);
let bumped_loss: f64 =
bumped_loss_tensor.into_data().to_vec::<f32>().unwrap()[0] as f64;
let finite_diff = (bumped_loss - base_loss) / eps as f64;
assert!(
(finite_diff - grad_values[i] as f64).abs() < 1e-2,
"index {i}: analytic={} finite_diff={finite_diff}",
grad_values[i],
);
}
}
#[test]
fn loss_backpropagates_through_gumbel_and_blend() {
use burn::backend::Autodiff;
use burn::tensor::Distribution;
type ADBackend = Autodiff<NdArray>;
let device = NdArrayDevice::default();
let (batch, loss_fn) = two_sample_batch::<ADBackend>(&device, 1.0);
let logits: Tensor<ADBackend, 3> =
Tensor::random([2, 3, 3], Distribution::Uniform(-1.0, 1.0), &device).require_grad();
let loss = loss_fn.loss(logits.clone(), &batch);
let loss_value: f32 = loss.clone().into_data().to_vec::<f32>().unwrap()[0];
assert!(
loss_value.is_finite(),
"loss should be finite, got {loss_value}"
);
let grads = loss.backward();
let grad = logits
.grad(&grads)
.expect("logits should have a gradient after backward()");
assert_eq!(grad.dims(), [2, 3, 3]);
let grad_values: Vec<f32> = grad.into_data().to_vec::<f32>().unwrap();
assert!(
grad_values.iter().all(|v| v.is_finite()),
"every gradient entry should be finite"
);
assert!(
grad_values.iter().any(|&v| v != 0.0),
"gradient should not be identically zero"
);
}
#[test]
fn loss_stays_finite_when_a_pinned_assignment_violates_a_constraint() {
use burn::backend::Autodiff;
type ADBackend = Autodiff<NdArray>;
let device = NdArrayDevice::default();
let mut problem = Problem::default();
let x = problem.add_variable(vec![0, 1, 2]);
let y = problem.add_variable(vec![0, 1, 2]);
not_equals(&mut problem, x, y);
let problem = Arc::new(problem);
let mut loss_fn = DecomposedMddLoss::new(MddCompilationConfig::default(), 3);
loss_fn.compile(&[Arc::clone(&problem)]);
let dataset = ConsFormerDataset::<ADBackend>::new(vec![problem], &device);
let samples: Vec<_> = (0..dataset.len())
.map(|i| dataset.get(i).unwrap())
.collect();
let batcher = ConsFormerBatcher {
mask_fraction: 0.0,
destroy: None,
};
let batch = batcher.batch(samples, &device);
let assignments: Tensor<ADBackend, 2, Int> =
Tensor::<ADBackend, 1, Int>::from_data([0i64, 0i64].as_slice(), &device)
.reshape([1, 2]);
let batch = ConsFormerBatch {
assignments,
..batch
};
let logits: Tensor<ADBackend, 3> = Tensor::zeros([1, 2, 3], &device).require_grad();
let loss = loss_fn.loss(logits.clone(), &batch);
let loss_value: f32 = loss.clone().into_data().to_vec::<f32>().unwrap()[0];
assert!(
loss_value.is_finite(),
"loss should be finite, got {loss_value}"
);
assert!(
(loss_value as f64 - (-(WMC_EPS).ln())).abs() < 1e-3,
"an unconditionally-violated constraint should read back as -log(WMC_EPS), got {loss_value}",
);
let grads = loss.backward();
let grad = logits
.grad(&grads)
.expect("logits should have a gradient after backward()");
let grad_values: Vec<f32> = grad.into_data().to_vec::<f32>().unwrap();
assert!(
grad_values.iter().all(|v| v.is_finite()),
"every gradient entry should be finite even when a constraint is unconditionally violated -- got {:?}",
grad_values,
);
}
#[test]
fn layer_weights_from_probs_masks_out_a_given_values_forbidden_domain() {
let domain_size = 4;
let mut problem = Problem::default();
let vars = problem.add_variables(4, (0..domain_size as isize).collect());
all_different(&mut problem, vars.clone());
crate::modelling::equal(&mut problem, vars[0], 2);
let problem = Arc::new(problem);
let arena = MddArena::new();
let constraint = problem
.iter_constraints()
.next()
.expect("problem must have exactly one constraint");
let constraint = crate::mdd::arena::compile_constraint(
&arena,
&problem,
constraint,
&crate::mdd::heuristics::OrderingHeuristic::MinDomMaxLinked,
&crate::mdd::arena::nominal_domain(domain_size),
usize::MAX,
);
let probs_for_sample: Vec<f32> = vec![0.25; 4 * domain_size];
let weights =
layer_weights_from_probs(&constraint, &problem, &probs_for_sample, domain_size);
let given_layer = (0..constraint.order.len())
.find(|&l| constraint.decision_at_layer(l) == vars[0])
.expect("vars[0] must be in the compiled constraint's scope");
assert_eq!(
weights[given_layer],
vec![0.0, 0.0, 0.25, 0.0],
"a given position's weight vector must be zero everywhere but its one allowed value"
);
let wmc = crate::mdd::wmc::wmc(&constraint, &weights);
let mut brute = 0.0;
for a in 0..domain_size {
for b in 0..domain_size {
for c in 0..domain_size {
let full = [2usize, a, b, c];
let vals: std::collections::HashSet<usize> = full.iter().copied().collect();
if vals.len() == 4 {
brute += 0.25f64.powi(4);
}
}
}
}
assert!(
(wmc - brute).abs() < 1e-9,
"wmc={wmc} brute={brute} -- masked wmc must match assignments honouring the given"
);
}
#[test]
fn log_add_exp_matches_the_direct_sum_and_survives_extremes() {
assert!((log_add_exp(0.3f64.ln(), 0.2f64.ln()) - 0.5f64.ln()).abs() < 1e-12);
assert!((log_add_exp(-2000.0, 1e-6f64.ln()) - 1e-6f64.ln()).abs() < 1e-12);
assert_eq!(log_add_exp(f64::NEG_INFINITY, 1e-6f64.ln()), 1e-6f64.ln());
}
}