Algorithms and dependencies

AbstractAlgorithm

Supertype of every algorithm. An algorithm selects which rules run and carries their parameters, which a rule reads through its algo slot. It is not an inference scheme: belief propagation, variational message passing and their structured forms all come from the factorisation, under one DefaultAlgorithm.

A custom algorithm is either a rule switcher, when someone wants a different set of rules, or a node's own algorithm, when the node needs one. It comes in two kinds:

• a direct subtype of AbstractAlgorithm stands alone: only its own rules and dependencies apply to it;
• a subtype of DefaultAlgorithmExtension extends the default: where it defines no rule or dependencies of its own, those of DefaultAlgorithm apply.

An algorithm with parameters stores them as fields, and a rule reads them from its algo slot.

struct MyVMP{T} <: AbstractAlgorithm
    iterations::Int
    tolerance::T
end

@define_message_update_rule(
    node = MyNode, target = :out, algorithm = MyVMP,
    args = (q[:in]::Any,),
    body = (algo, args) -> solve(args.q[:in]; maxiter = algo.iterations, tol = algo.tolerance),
)

See also ispure, @define_dependencies.

DefaultAlgorithm()

The algorithm every node runs under unless it declares its own: Bethe free energy minimisation. Whether a rule behaves as belief propagation, variational message passing or their structured form depends on the factorisation, through the engine's default dependency scheme, not on the algorithm. A rule that omits algorithm belongs to its node's default, default_algorithm(node), which is this unless the node declares otherwise.

default_algorithm(node) -> AbstractAlgorithm

The algorithm value rules for node run under unless a call or a graph gives another: the node's declared algorithm, instantiated, and DefaultAlgorithm() for a node that declares none. A rule that omits algorithm is defined for its type.

DefaultAlgorithmExtension

Supertype of the algorithms that extend DefaultAlgorithm. Resolution looks for the extension's own rule first and falls back to the default's, and likewise for dependencies. A rule reached through that fallback receives DefaultAlgorithm() in its algo slot, the algorithm it was written for. The fallback is a second lookup, not dispatch on a supertype: if default rules dispatched on an abstract type, an extension's rule with broader inputs than a default one would be ambiguous with it, and resolution must never throw.

struct MyRules <: DefaultAlgorithmExtension end   # override some rules, inherit the rest

ispure(algorithm::Type{<:AbstractAlgorithm}) -> Bool
ispure(algorithm::AbstractAlgorithm) -> Bool

Whether rules under this algorithm are pure unless they say otherwise. An impure algorithm adds a method, MessagePassingRulesBase.ispure(::Type{<:MyAlgorithm}) = false, which covers each MyAlgorithm{T} of a parametric one as well.

Pure means that a call has no effect anyone outside it can observe, apart from its result; it does not mean that the rule writes nothing. A pure rule may allocate intermediate arrays, write the output buffer an in-place rule is given (the buffer is handed over to hold the result), reuse its own scratch, which nothing else reads, draw from ctx.rng, which its caller owns, and warn or log. A rule is impure if it mutates an input, mutates its algorithm (a cache kept in a field, say), writes a global variable, a file or other state that later code reads, or carries its own random number generator in its algorithm.

Purity is declared, not proved: the default is true. A rule may override its algorithm with pure = false, and an engine auditing purity must read the rule's own flag, so the override cannot hide impurity. Purity is an audit policy, for threading and for finding side effects; it says nothing about whether a rule can be differentiated, which is tested separately.

@define_dependencies(node = ..., algorithm = ..., dependencies = [...], free_energy_partition = [...])

Declare what node's rules consume under algorithm, target by target, in place of the default scheme, where the inputs follow the factorisation. It is for an algorithm whose rules ignore the factorisation, such as a node's own or one of its variants. The macro takes keyword arguments only; node, algorithm and dependencies are required. An unknown or repeated keyword is an error at definition time, naming the valid ones.

A node declares the same for its default algorithm with @define_factor_node's own dependencies keyword, in the same vocabulary. dependencies_spec returns what was declared.

Required keywords

• node: the node, as declared with @define_factor_node.

• algorithm: the algorithm the declaration is for, a type, or a value whose type is used. With a parametric type T, algorithm = T covers every T{…}.

• dependencies: what each target's rule consumes.

  A vector of target => (inputs...) pairs, one per target whose inputs are declared: dependencies = [:out => (m[:μ], q[:v]), :μ => (m[:out], q[:v])]. A target is :out, or (:m, k) for every member of the group m, binding k for the inputs to select by. The inputs are written as in a rule's args, without types:

  • m[:μ], q[:μ]: the message or the marginal of a single interface;
  • q[:y, :x], or q[(:y, :x)]: the joint marginal of a cluster, its members in interface order; q[(:in,)] is the joint over the group in;
  • for a group: m[:in...] (every member), m[:in][k] (the target's own member), m[:in][!k] (all but it), or m[:in][select_group_members(f; arity)] (the members f(k) returns, always arity of them, see select_group_members);
  • default: the default scheme's inputs for that target, which follow the factorisation (the messages of the target's own cluster, the marginals of the others). :a => (default, q[:a]) is the default scheme's inputs plus q(a), and :y => (default,) the default scheme alone. An input listed beside default is a single interface's message or marginal, placed among the default scheme's in interface order, and consumed without being scored.

  A target with no inputs is target => (). Every target a graph connects must be declared: one left out is an error when an engine activates the node, so write target => (default,) for one that follows the default scheme. The inputs are subscribed to in the order written, which under variational message passing is the update schedule: it changes how fast a node converges, not where to. The declaration is checked against the node's interfaces when it is loaded: unknown names, a group written as a single interface or the other way round, a target or an input given twice, and a cluster out of interface order are errors.

Optional keywords

• free_energy_partition: the clusters the free energy is computed over, a vector of tuples of interface names covering every interface exactly once: [(:out, :μ), (:τ,)]. A group's name stands for all its members. What a rule consumes need not be a block of it: a marginal consumed but outside the partition is never scored. The engine refuses a graph whose factorisation is not this partition, block for block. Default: none, and the partition is the graph's factorisation.

Example

# Declared on the parametric `MixtureBP`, so it covers every product strategy:
@define_dependencies(
    node = Mixture,
    algorithm = MixtureBP,
    dependencies = [
        :out => (m[:switch], m[:inputs...]),
        :switch => (m[:out], m[:inputs...]),
        (:inputs, k) => (m[:out], m[:switch]),
    ],
)

DependenciesSpec

What a node's rules consume under one algorithm, target by target, and optionally the partition the free energy is computed over, as @define_dependencies or @define_factor_node's dependencies keyword declares it and dependencies_spec returns it. Fields:

• node, algorithm: the node, and the algorithm type the declaration is for;
• targets: one TargetDependencies per declared target;
• partition: the free-energy partition, a tuple of member tuples, or nothing, and the engine derives it from the factorisation. Read it with free_energy_partition.

The two are separate: a rule may consume a marginal that is not a block of the partition, and that marginal is never scored. Read a target's inputs with target_dependencies and extends_default_scheme. It shows itself as a table of targets and their inputs.

dependencies_spec(node, algorithm) -> Union{DependenciesSpec, Nothing}

The DependenciesSpec declared for node under algorithm, a value, or nothing when none is declared and the engine's default scheme applies. A DefaultAlgorithmExtension that declares none gets the declaration for DefaultAlgorithm, if any.

free_energy_partition(spec::DependenciesSpec) -> Union{Tuple, Nothing}

The partition the free energy is computed over, as declared with free_energy_partition: a tuple of blocks, each a tuple of interface names, covering every interface once, a group's name standing for all its members. nothing when none is declared, and the partition is the graph's factorisation. An engine refuses a graph whose factorisation is not this partition.

TargetDependencies

The inputs one target consumes, one entry of a DependenciesSpec. Fields:

• edge::Symbol: the target interface, or the group for an indexed target;
• indexed::Bool: true for a group's members, declared (:m, k) => (...), whose inputs may select by k; false for a single interface, declared :out => (...);
• inputs: the Dependencys, in the order declared, which is the order an engine subscribes to them;
• default::Bool: true when the target was declared with default among its inputs: it consumes the default scheme's inputs, which follow the factorisation, and inputs are added to them.

target_dependencies(declaration::DependenciesSpec, target) -> Union{Tuple, Nothing}

The Dependencys target, a Target or an IndexedTarget, consumes under declaration, in the order declared, or nothing when the declaration does not list the target. For a target declared with default, only the inputs added to the default scheme's (extends_default_scheme).

extends_default_scheme(declaration::DependenciesSpec, target) -> Bool

Whether target was declared with default, so that it consumes the engine's default scheme's inputs plus those target_dependencies lists. false for a target the declaration does not list.

Dependency

One input a target consumes, as a dependency declaration lists it. Fields:

• container::Symbol: :m for a message, :q for a marginal;
• key: the interface's or group's name, or, for a cluster's joint, the tuple of its members, each an interface's name or a group member by its index, (:out, (:T, 1));
• selector::DependencySelector: what it takes of the interface, a DependencySelector; SingleInterface for an interface or a cluster.

DependencySelector

Supertype of how a Dependency selects from its interface: the interface itself (SingleInterface), or, for a group, all members (AllGroupMembers), the member aligned with the target (AlignedGroupMember), all but that one (AllGroupMembersButSelf), or the members a function picks (CustomGroupSelector, made by select_group_members). An engine reads a group selection through selected_indices and selection_arity.

SingleInterface()

The DependencySelector of a single interface, m[:μ], or of a cluster's joint, q[:y, :x]: the whole of what the key names.

AllGroupMembers()

The DependencySelector of every member of a group, m[:in...]: all n of a group of n, whatever the target.

AlignedGroupMember()

The DependencySelector of the member with the target's index, m[:in][k] for the indexed target (:m, k): one member. Needs an indexed target.

AllGroupMembersButSelf()

The DependencySelector of every member but the one with the target's index, m[:in][!k]: n - 1 of a group of n, none of a group of one. Needs an indexed target.

CustomGroupSelector{F}

The DependencySelector select_group_members(f; arity) makes: the members f(k) returns for target index k, always arity of them. Fields: f and arity.

select_group_members(f; arity::Integer) -> CustomGroupSelector

A custom group selector, written m[:in][select_group_members(f; arity)] in a dependency declaration: f(k) returns the member indices, a tuple or anything Tuple converts, for target index k, always arity of them. The arity is static, so an engine knows how many inputs to wait for before it calls f.

Throws

selected_indices throws an ArgumentError when f returns another number of indices.

julia> using MessagePassingRulesBase: select_group_members, selected_indices

julia> previous = select_group_members(k -> (k - 1,); arity = 1);

julia> selected_indices(previous, 3, 4)
(2,)

selected_indices(selector::DependencySelector, k, n) -> Tuple

The member indices selector picks from a group of n for target index k, in order. A selection of no members is an empty tuple; an engine must treat it as satisfied, never wait on it. Not defined for SingleInterface, which selects no members.

Throws

ArgumentError for a CustomGroupSelector whose function returns other than its arity.

Examples

julia> using MessagePassingRulesBase: selected_indices, AllGroupMembersButSelf, select_group_members

julia> selected_indices(AllGroupMembersButSelf(), 2, 4)
(1, 3, 4)

julia> selected_indices(AllGroupMembersButSelf(), 1, 1)
()

julia> selected_indices(select_group_members(k -> (mod1(k - 1, 3),); arity = 1), 1, 3)
(3,)

selection_arity(selector::DependencySelector, n) -> Int

How many members selector picks from a group of n, for any target index: n for AllGroupMembers, 1 for AlignedGroupMember, n - 1 for AllGroupMembersButSelf, the declared arity for a CustomGroupSelector. Not defined for SingleInterface.

initial_messages(node) -> Tuple

The messages node seeds its interfaces with, as name => message pairs: for a rule that reads the message on its own edge, the value it starts from. The engine sets each on the node's inbound message of that interface at activation, unless one was set there already, so a user's initialisation wins. Empty unless declared.