logaritmisk
48a6049dc6
Smallest-scope realisation of spec §"Built-in schedules" Damped: a ConvergenceOptions::alpha field plumbed through run_chain to a new Gaussian::damp_natural helper applied inside TruncFactor and MarginFactor's propagate. alpha=1.0 default keeps every existing golden bit-equal; alpha<1.0 stabilises oscillating fixed-point loops on hard graphs. Defers Schedule trait integration, nat-param convergence switch, oscillation auto-detect, Residual/OneShot, and Synergy/ScoreFactor — each gets its own future plan.
321 lines
12 KiB
Markdown
321 lines
12 KiB
Markdown
# Damped EP — Game-Local Damping
|
||
|
||
## Summary
|
||
|
||
Add an opt-in EP damping knob to within-game inference. Users set
|
||
`ConvergenceOptions::alpha < 1.0` to damp message updates and stabilise
|
||
oscillating fixed-point loops on hard graphs. `alpha = 1.0` (the default)
|
||
is bit-equal to today.
|
||
|
||
This is the smallest-scope realisation of the spec's `Damped` schedule:
|
||
**game-local**, not plumbed through the `Schedule` trait. The `Schedule`
|
||
trait is shipped infrastructure that `run_chain` does not currently call;
|
||
wiring `Schedule` into game inference is a separate future task. This
|
||
design touches only what the user can actually reach via `GameOptions`.
|
||
|
||
## Scope
|
||
|
||
### What ships
|
||
|
||
1. New field `ConvergenceOptions::alpha: f64` (default `1.0`).
|
||
2. `run_chain` reads `options.convergence.{epsilon, max_iter, alpha}`
|
||
instead of the hardcoded `1e-6` / `10` / undamped — fixes the existing
|
||
latent bug where the first two were already on `GameOptions` but never
|
||
read by inference.
|
||
3. `Gaussian::damp_natural(self, new, alpha) -> Gaussian` — public helper
|
||
computing `α·new + (1−α)·self` in natural-parameter space.
|
||
4. `TruncFactor` and `MarginFactor` gain inherent
|
||
`propagate_with_alpha(&mut self, vars, alpha) -> (f64, f64)`. Their
|
||
`Factor::propagate` impls become one-line delegations passing
|
||
`alpha = 1.0`.
|
||
5. `DiffFactor::propagate` (game-private enum at `src/game.rs:20-54`)
|
||
gains an `alpha: f64` parameter and dispatches into the underlying
|
||
factor's `propagate_with_alpha`.
|
||
|
||
### What does not ship
|
||
|
||
- No `Damped` impl in `src/schedule.rs`. The `Schedule` trait stays as
|
||
it is; integration with `run_chain` is a separate task.
|
||
- No nat-param convergence switch. `(|Δmu|, |Δsigma|)` stays the
|
||
delta basis (matches today). The spec's "stopping in natural-param
|
||
space" wants its own design pass and test re-tuning.
|
||
- No oscillation auto-detect. `alpha` is user-supplied and constant for
|
||
the duration of a `run_chain` call.
|
||
- No `Residual`, `OneShot`, or `SynergyFactor` / `ScoreFactor` work —
|
||
separate future plans.
|
||
|
||
## Design
|
||
|
||
### `ConvergenceOptions::alpha`
|
||
|
||
```rust
|
||
// src/convergence.rs
|
||
#[derive(Clone, Copy, Debug)]
|
||
pub struct ConvergenceOptions {
|
||
pub max_iter: usize,
|
||
pub epsilon: f64,
|
||
pub alpha: f64,
|
||
}
|
||
|
||
impl Default for ConvergenceOptions {
|
||
fn default() -> Self {
|
||
Self {
|
||
max_iter: crate::ITERATIONS,
|
||
epsilon: crate::EPSILON,
|
||
alpha: 1.0,
|
||
}
|
||
}
|
||
}
|
||
```
|
||
|
||
`alpha = 1.0` ⇒ undamped (bit-equal to today). Recommended starting
|
||
point if a graph oscillates: `0.5`–`0.7`. Values approaching `0.0` make
|
||
each step tinier and slow convergence; `alpha = 0.0` is degenerate
|
||
(factor never updates). Validation in `run_chain`:
|
||
|
||
```rust
|
||
debug_assert!(
|
||
opts.convergence.alpha > 0.0 && opts.convergence.alpha <= 1.0,
|
||
"convergence alpha must be in (0.0, 1.0]"
|
||
);
|
||
```
|
||
|
||
### `Gaussian::damp_natural`
|
||
|
||
```rust
|
||
impl Gaussian {
|
||
/// EP damping in natural-parameter space: `α·new + (1−α)·self`.
|
||
///
|
||
/// Used by within-game schedules to stabilise oscillating fixed-point
|
||
/// loops on hard graphs. `alpha = 1.0` returns `new` exactly;
|
||
/// `alpha < 1.0` shrinks each per-step update.
|
||
pub fn damp_natural(self, new: Gaussian, alpha: f64) -> Gaussian {
|
||
Gaussian::from_natural(
|
||
alpha * new.pi() + (1.0 - alpha) * self.pi(),
|
||
alpha * new.tau() + (1.0 - alpha) * self.tau(),
|
||
)
|
||
}
|
||
}
|
||
```
|
||
|
||
Public on `Gaussian`. The name encodes the WHY (EP damping); the doc
|
||
comment fixes the math. No new dependency.
|
||
|
||
The existing `Mul<f64> for Gaussian` is **distribution scaling**
|
||
(`sigma → sigma·|scalar|`), not nat-param interpolation, so it can't be
|
||
reused here.
|
||
|
||
### `TruncFactor::propagate_with_alpha`
|
||
|
||
```rust
|
||
impl TruncFactor {
|
||
pub(crate) fn propagate_with_alpha(
|
||
&mut self,
|
||
vars: &mut VarStore,
|
||
alpha: f64,
|
||
) -> (f64, f64) {
|
||
let marginal = vars.get(self.diff);
|
||
let cavity = marginal / self.msg;
|
||
|
||
if self.evidence_cached.is_none() {
|
||
self.evidence_cached = Some(cavity_evidence(cavity, self.margin, self.tie));
|
||
}
|
||
|
||
let trunc = approx(cavity, self.margin, self.tie);
|
||
let new_msg = trunc / cavity;
|
||
|
||
let damped = self.msg.damp_natural(new_msg, alpha);
|
||
let old_msg = self.msg;
|
||
self.msg = damped;
|
||
|
||
// marginal_new = cavity * stored_msg (NOT cavity * new_msg with damping)
|
||
vars.set(self.diff, cavity * damped);
|
||
|
||
old_msg.delta(damped)
|
||
}
|
||
}
|
||
|
||
impl Factor for TruncFactor {
|
||
fn propagate(&mut self, vars: &mut VarStore) -> (f64, f64) {
|
||
self.propagate_with_alpha(vars, 1.0)
|
||
}
|
||
}
|
||
```
|
||
|
||
Two important points:
|
||
|
||
- The variable receives `cavity * damped` (i.e. `cavity * self.msg`),
|
||
not `trunc`. With `alpha = 1.0` these are equal (since
|
||
`cavity * new_msg = trunc` by construction), so today's behaviour is
|
||
preserved bit-equal. With `alpha < 1.0` the marginal reflects the
|
||
partially-applied update.
|
||
- The reported delta is `old_msg.delta(damped)` — delta of the actually
|
||
stored message, not of the raw `new_msg`. This is the textbook EP
|
||
damping convention: the convergence loop measures the trajectory it
|
||
is actually walking.
|
||
|
||
`MarginFactor` follows the same shape, with its own
|
||
`propagate_with_alpha` body (the existing `propagate` math, with the
|
||
`damp_natural` step inserted in the same place and the var write
|
||
switched to `cavity * damped`).
|
||
|
||
### `DiffFactor::propagate` signature
|
||
|
||
```rust
|
||
// src/game.rs
|
||
impl DiffFactor {
|
||
pub(crate) fn propagate(
|
||
&mut self,
|
||
vars: &mut VarStore,
|
||
alpha: f64,
|
||
) -> (f64, f64) {
|
||
match self {
|
||
Self::Trunc(f) => f.propagate_with_alpha(vars, alpha),
|
||
Self::Margin(f) => f.propagate_with_alpha(vars, alpha),
|
||
}
|
||
}
|
||
}
|
||
```
|
||
|
||
`DiffFactor` is `pub(crate)` and only used inside `run_chain`, so the
|
||
signature change has no public-API impact.
|
||
|
||
### `run_chain` changes
|
||
|
||
Inside `Game::run_chain` (`src/game.rs:236-348`):
|
||
|
||
1. Capture `let alpha = opts.convergence.alpha;` once at the top
|
||
(avoids repeated `opts.convergence.alpha` lookups in the hot loop).
|
||
2. Replace the loop guard
|
||
`while tuple_gt(step, 1e-6) && iter < 10`
|
||
with
|
||
`while tuple_gt(step, opts.convergence.epsilon) && iter < opts.convergence.max_iter`.
|
||
3. Replace each `lf.propagate(&mut arena.vars)` call site (three of
|
||
them: forward sweep, backward sweep, `n_diffs == 1` special case)
|
||
with `lf.propagate(&mut arena.vars, alpha)`.
|
||
|
||
The threading of `opts: &GameOptions` into `run_chain` is the only
|
||
new caller obligation. Today `run_chain` doesn't take `opts`; the two
|
||
callers (`likelihoods`, `likelihoods_scored`) currently invoke it
|
||
without options. Both will need to pass the options through. The
|
||
`Game<'a, T, D>` struct does not currently hold `GameOptions`; the
|
||
options are constructed and discarded around the call to
|
||
`{ranked,scored}_with_arena`. So:
|
||
|
||
- `Game::ranked_with_arena` and `Game::scored_with_arena` already
|
||
receive `p_draw` / `score_sigma` as scalar params; we extend them to
|
||
accept `&ConvergenceOptions` (or the full `&GameOptions`) too.
|
||
- `likelihoods` / `likelihoods_scored` either store the options on
|
||
`Game` or accept them as method parameters and forward to
|
||
`run_chain`.
|
||
|
||
The simplest plumbing: store `convergence: ConvergenceOptions` as a
|
||
field on `Game<'a, T, D>` and `OwnedGame<T, D>` populated at
|
||
construction time. Then `run_chain` can read it from `&self`.
|
||
|
||
## Convergence semantics
|
||
|
||
With `alpha < 1.0` the per-step update shrinks; convergence may take
|
||
more iterations to reach the same `epsilon` threshold. Users who damp
|
||
should also raise `max_iter` accordingly. Documentation example:
|
||
|
||
```rust
|
||
let mut opts = GameOptions::default();
|
||
opts.convergence.alpha = 0.5;
|
||
opts.convergence.max_iter = 30;
|
||
```
|
||
|
||
## Testing strategy
|
||
|
||
### Regression net (no new file)
|
||
|
||
The existing 88 lib tests and 27 integration tests are the bit-equal
|
||
regression net. With `alpha = 1.0` (the default), every assertion must
|
||
pass unchanged. If any test fails, the damping path leaked into the
|
||
undamped trajectory.
|
||
|
||
### New tests
|
||
|
||
1. **`Gaussian::damp_natural` arithmetic**
|
||
(`src/gaussian.rs` test mod):
|
||
- `α = 1.0` returns `new` exactly (bit-equal `pi` and `tau`).
|
||
- `α = 0.0` returns `self` exactly.
|
||
- `α = 0.5`: pi and tau are exact midpoints in nat-param space.
|
||
- Three asserts, no new file.
|
||
|
||
2. **`TruncFactor::propagate_with_alpha` shrinks the step**
|
||
(`src/factor/trunc.rs` test mod):
|
||
- Set up a TruncFactor step. Run `propagate_with_alpha(α=1.0)` once,
|
||
record `delta_undamped` and the resulting `self.msg`.
|
||
- Reset to a fresh factor at the same starting state. Run
|
||
`propagate_with_alpha(α=0.5)` once, record `delta_damped` and
|
||
`damped_msg`.
|
||
- Assert: `damped_msg.pi()` equals `0.5 * undamped_msg.pi() + 0.5 * initial_msg.pi()` within 1e-12 (and same for `tau`).
|
||
- Assert: `delta_damped.0 <= delta_undamped.0` (mu-delta is no larger; the relationship is monotone in `α` but not strictly `0.5×` for the `delta()` function which is `(|Δmu|, |Δsigma|)`).
|
||
|
||
3. **`MarginFactor::propagate_with_alpha` parity**
|
||
(`src/factor/margin.rs` test mod):
|
||
- Same shape as #2, on a `MarginFactor` step.
|
||
|
||
4. **`run_chain` honours `ConvergenceOptions::max_iter`**
|
||
(in an existing or new game-level test):
|
||
- Construct a 4-team ranked game that normally converges in ~5 iterations.
|
||
- Set `opts.convergence.max_iter = 1`. Assert the per-iteration
|
||
`step` returned (or observable indirectly via posterior delta vs.
|
||
the converged answer) is non-zero — i.e. the loop stopped early.
|
||
- Set `opts.convergence.max_iter = 30`. Assert posteriors match the
|
||
baseline within `epsilon`.
|
||
|
||
5. **Damping default is `1.0` and produces bit-equal output**
|
||
(smoke test, can be a single assertion in an existing test):
|
||
- `assert_eq!(ConvergenceOptions::default().alpha, 1.0);`
|
||
- Existing goldens prove the bit-equality.
|
||
|
||
No oscillation-stabilisation test (would require constructing a
|
||
pathological graph specifically to oscillate; out of scope for a
|
||
minimal ship).
|
||
|
||
## Verification gates
|
||
|
||
Per task:
|
||
|
||
```bash
|
||
cargo +nightly fmt
|
||
cargo clippy --all-targets -- -D warnings
|
||
cargo test --lib
|
||
cargo test
|
||
```
|
||
|
||
All must succeed. Test count grows by exactly the new tests above
|
||
(roughly +5–8 lib tests).
|
||
|
||
## Risks
|
||
|
||
- **Marginal-update change is subtle.** Switching the variable write
|
||
from `trunc` to `cavity * damped` is intentionally a no-op when
|
||
`alpha = 1.0` (since `cavity * new_msg = trunc`), but it changes the
|
||
arithmetic path. If `Gaussian` arithmetic has any non-associativity
|
||
in floating-point that the old form happened to dodge, goldens could
|
||
shift by 1 ULP. Mitigation: TDD — write the regression test (run all
|
||
existing tests with `alpha = 1.0`) **first**, before changing the
|
||
variable-write line.
|
||
- **`run_chain` signature change ripples to two callers.** Trivial
|
||
but must be done atomically with the field addition on `Game` /
|
||
`OwnedGame`.
|
||
- **`alpha` validation only in debug builds.** A release build will
|
||
silently accept `alpha = 0.0` or `alpha > 1.0` and produce nonsense.
|
||
This matches the existing pattern (`debug_assert!` for input
|
||
validation in `Game::ranked_with_arena`); upgrading to `Result` is
|
||
out of scope.
|
||
|
||
## Out-of-scope follow-ups (logged for future plans)
|
||
|
||
- Wire `Schedule` into `run_chain` (so `Damped` lands as a real
|
||
`Schedule` impl alongside `EpsilonOrMax`).
|
||
- Switch convergence check to `(|Δpi|, |Δtau|)` per spec
|
||
§"Stopping in natural-param space".
|
||
- Oscillation auto-detect (engage `alpha < 1.0` only after N
|
||
non-monotone steps).
|
||
- `Residual` schedule (priority queue).
|
||
- `SynergyFactor`, `ScoreFactor` (new EP factor types).
|