Relevance Reasoning explained

[jonnie]

Hello DSL,
I'd like to know a little bit more about how and where you do relevance reasoning.
I know the flags in network.h and I guess that for example relevance reasoning related to evidence will be executed during the call of SetEvidence.
- If I set evidence and activate relevance reasoning afterwards, will the relevance reasoning be executed then?
- Why does SetTarget take so long? Is there relevance reasoning executed or something else?
- What reasoning exactly takes place? I guess it's about d-separation, barren nodes, and nuisance nodes...
- What reasoning takes place about noisy-MAX definitions? (EnableNoisyMAXRelevance, where it says "Adam's noisy-MAX inference algorithm/improvements 11/04")
- What amount of relevance reasoning is executed during UpdateBeliefs?
- Do the relevance-based decomposition inference algorithms have their own relevance reasoning, or will they get helpless if I deactivate relevance reasoning from outside?
And one off-topic question while I'm at it: I noticed that setting the algorithm doesn't take any time (I thought that was where Lauritzen creates its join tree). Is the join tree of clustering algorithms already built during loading the file, or does it get rebuilt every time I call UpdateBeliefs?
Thanks so much in advance!

[shooltz]

- If I set evidence and activate relevance reasoning afterwards, will the relevance reasoning be executed then?

No, DSL_network::ActivateRelevance just sets the network flag; see network.h.

- Why does SetTarget take so long? Is there relevance reasoning executed or something else?

SetTarget is very simple and O(1). Did you measure the elapsed time with the profiler? If so and you've used sampling profiling, it may be so called 'skid'.

What amount of relevance reasoning is executed during UpdateBeliefs?

Quite a lot, actually. Depending on target set and evidence SMILE may split network into separate fragments, each will be processed separately to keep time/memory usage low. There's additional check for propagated evidence which is effective when you had deactivated the relevance in the network.

- Do the relevance-based decomposition inference algorithms have their own relevance reasoning, or will they get helpless if I deactivate relevance reasoning from outside?

Relevance-based decomposition is implemented in terms of SetTarget/inference calls. Essentially, it does SetTarget for the user (of course, original target set will be restored). Note that DSL_ALG_BN_LAURITZEN will try to fallback into decomposition mode if a) there's more than one target and b) triangulation results in a jointree size above preset threshold.

And one off-topic question while I'm at it: I noticed that setting the algorithm doesn't take any time (I thought that was where Lauritzen creates its join tree). Is the join tree of clustering algorithms already built during loading the file, or does it get rebuilt every time I call UpdateBeliefs?

It gets rebuilt each time, because the tree (or trees - due to relevance being able to split network sometimes) depend on targets and evidence. We do not store the jointree.

- What reasoning exactly takes place? I guess it's about d-separation, barren nodes, and nuisance nodes...
- What reasoning takes place about noisy-MAX definitions? (EnableNoisyMAXRelevance, where it says "Adam's noisy-MAX inference algorithm/improvements 11/04")

I'll forward these two questions. Somewhat unfortunately, that 'relevance' has two meanings in SMILE: a) the code which propagates evidence and invalidates node values when network structure and/or evidence set changes, and b) the code which simplifies network before running actual inference.

[adam]

- What reasoning takes place about noisy-MAX definitions? (EnableNoisyMAXRelevance, where it says "Adam's noisy-MAX inference algorithm/improvements 11/04")

Jonnie,

EnableNoisyMAXRelevance() enables an extra step in relevance. It is related to the noisy-OR/noisy-MAX definitions. When a noisy-OR/MAX node has evidence set to the absent state (more precisely to the distinguished state), the parent nodes become independent.

Originally when I tested this trick did not seem to really help with improving the the inference performance, so I abandoned the idea, but the code is still in SMILE. But recently, I've happened to have a large diagnostic model (BN2O) for which it seemed to actually help a lot. If you happen to use noisy-MAX with evidence you may consider testing if it brings performance improvements.

Cheers,
Adam

[jonnie]

Thanks a lot!
I'm sorry but I came up with a whole bunch of follow-up questions

'relevance' has two meanings in SMILE: a) the code which propagates evidence and invalidates node values when network structure and/or evidence set changes, and b) the code which simplifies network before running actual inference.

So there's propagate&invalidate, and then there's network simplification...
Do ActivateRelevance and EnableNoisyMAXRelevance enable/disable both of them? or which one?
When I call SetEvidence, does it only propagate&invalidate or also simplify? (I guess simplification is done within UpdateBeliefs only)
Is noisyMax relevance used in both propagate&invalidate and network simplification? or in which one?

SetTarget is very simple and O(1). Did you measure the elapsed time with the profiler? If so and you've used sampling profiling, it may be so called 'skid'.

What do you mean by skid?
Is it important to set targets first and evidence afterwards, or should it be done the other way round? Or does it not matter?
I measure the times of the different steps separately. I was already wondering if the time for setting targets gets wasted in my own code, but I only have a set<int> of the node handles that should be targets, I iterate over the network nodes, compare to the set<int>, and if it doesn't correspond I change the status. I do the same with evidence where I use a map<int, int> but setting targets takes about double the time! No matter which algorithm (sampling or clustering) is configured.

Depending on target set and evidence SMILE may split network into separate fragments

Not just for DSL_ALG_BN_RELEVANCEDECOMP and DSL_ALG_BN_RELEVANCEDECOMP2?

Note that DSL_ALG_BN_LAURITZEN will try to fallback into decomposition mode if a) there's more than one target and b) triangulation results in a jointree size above preset threshold.

Interesting! Can I see somehow from outside whether this happened or not?
Is that threshold hard-coded? Is it machine-dependent? Or can I set it through the API?

If you happen to use noisy-MAX with evidence you may consider testing if it brings performance improvements.

I did, and it does in some cases

[shooltz]

Do ActivateRelevance and EnableNoisyMAXRelevance enable/disable both of them? or which one?

ActivateRelevance only enables evidence propagation and value invalidation. EnableNoisyMAXRelevance is only used during simplification.

When I call SetEvidence, does it only propagate&invalidate or also simplify?

SetEvidence will cause propagation/invalidation. Simplification is only performed as part of inference.

What do you mean by skid?

See this link:
http://software.intel.com/en-us/article ... incorrect/

Is it important to set targets first and evidence afterwards, or should it be done the other way round? Or does it not matter?

Theoretically, there could be a performance benefit if you set targets first - evidence propagation may be faster. As always, this depends on the structure/parameters in the network.

I measure the times of the different steps separately. I was already wondering if the time for setting targets gets wasted in my own code, but I only have a set<int> of the node handles that should be targets, I iterate over the network nodes, compare to the set<int>, and if it doesn't correspond I change the status.

You can ClearAllTargets, then iterate over contents of your set<int>. However, even with hunders of nodes this should not be a significant part of the entire calculation.

I do the same with evidence where I use a map<int, int> but setting targets takes about double the time! No matter which algorithm (sampling or clustering) is configured.

The choice of inference algorithm has no influence on the time required to perform SetTarget call.

Depending on target set and evidence SMILE may split network into separate fragments

Not just for DSL_ALG_BN_RELEVANCEDECOMP and DSL_ALG_BN_RELEVANCEDECOMP2?

No, this happens for most of the inference algorithms as a preprocessing phase. The relevance decomposition algorithms take it one step further and call inference multiple times if target set can be split.

Note that DSL_ALG_BN_LAURITZEN will try to fallback into decomposition mode if a) there's more than one target and b) triangulation results in a jointree size above preset threshold.

Interesting! Can I see somehow from outside whether this happened or not?

No, there's no callback mechanism for this.

Is that threshold hard-coded? Is it machine-dependent? Or can I set it through the API?

The following network properties can be used to set the thresolds - they may change anytime, do not consider them to be oficially supported:

DSL_REL_DECOMP_THRESHOLD - unit: node count, default value: 32. This sets number of targets in the group for linear relevance decomposition. Example: you have network with 100 targets. If linear decomposition is used directly or as a fallback, there will be 4 target groups, three with 32 nodes and one with 4 nodes. Assignments are done on partial order basis

DSL_REL_DECOMP_THRESHOLD2 - unit: total size of jointree, as measured by number of entries in the cliques, default value 65536. This property applies to recursive decomposition. SMILE splits the target set in two, checks the jointree size for each half. If jointree size is below the value, inference runs. Otherwise the target subset is again split in two. This will continue until target subset contains single node.

DSL_REL_DECOMP_THRESHOLD3 - unit: total size of jointree, default value 0. This value controls the switch from linear to recursive decomposition inside linear decomp. Zero means that linear will use the thresold specified by DSL_REL_DECOMP_THRESHOLD2.

DSL_REL_DECOMP_DISABLE_FALLBACK - no unit. The presence of this property (regardless of its value) blocks the automatic fallback inside Lauritzen algorithm. If property is not present, the failure to triangulate the network using all targets at once will cause linear decomposition to run. In turn, linear can switch to recursive as described above.

[marek]

- What reasoning exactly takes place? I guess it's about d-separation, barren nodes, and nuisance nodes...
- What reasoning takes place about noisy-MAX definitions?

GeNIe and the underlying SMILE code support relevance reasoning as explained in my paper with Jaap Suermondt. You can download that paper from the following location:

http://www.pitt.edu/~druzdzel/ftp/relevance.pdf

There is an extended version of this paper, explaining a few additional techniques, that I will send you privately.
I hope this helps.
Cheers,

Marek

[jonnie]

Good evening,
I just wanted to say thanks to your detailed & exhaustive answers! These things really explain a lot of the behavior I'm observing and will help a lot in drawing conclusions as well.
Greetings, Johannes

Update:

I measure the times of the different steps separately. I was already wondering if the time for setting targets gets wasted in my own code, but I only have a set<int> of the node handles that should be targets, I iterate over the network nodes, compare to the set<int>, and if it doesn't correspond I change the status.

That was a mistake, I'm sorry. Setting targets takes about the same insignificant time as setting evidence (if relevance reasoning is disabled). So everything is alright