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!
Relevance Reasoning explained
-
- Site Admin
- Posts: 1419
- Joined: Mon Nov 26, 2007 5:51 pm
Re: Relevance Reasoning explained
No, DSL_network::ActivateRelevance just sets the network flag; see network.h.jonnie wrote:- If I set evidence and activate relevance reasoning afterwards, will the relevance reasoning be executed then?
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'.- Why does SetTarget take so long? Is there relevance reasoning executed or something else?
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.What amount of relevance reasoning is executed during UpdateBeliefs?
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.- Do the relevance-based decomposition inference algorithms have their own relevance reasoning, or will they get helpless if I deactivate relevance reasoning from outside?
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.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?
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.- 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")
Re: Relevance Reasoning explained
Jonnie,jonnie wrote: - What reasoning takes place about noisy-MAX definitions? (EnableNoisyMAXRelevance, where it says "Adam's noisy-MAX inference algorithm/improvements 11/04")
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
Re: Relevance Reasoning explained
Thanks a lot!
I'm sorry but I came up with a whole bunch of follow-up questions
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?
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.
Is that threshold hard-coded? Is it machine-dependent? Or can I set it through the API?
I'm sorry but I came up with a whole bunch of follow-up questions
So there's propagate&invalidate, and then there's network simplification...'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.
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?
What do you mean by skid?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'.
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.
Not just for DSL_ALG_BN_RELEVANCEDECOMP and DSL_ALG_BN_RELEVANCEDECOMP2?Depending on target set and evidence SMILE may split network into separate fragments
Interesting! Can I see somehow from outside whether this happened or not?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.
Is that threshold hard-coded? Is it machine-dependent? Or can I set it through the API?
I did, and it does in some casesIf you happen to use noisy-MAX with evidence you may consider testing if it brings performance improvements.
-
- Site Admin
- Posts: 1419
- Joined: Mon Nov 26, 2007 5:51 pm
Re: Relevance Reasoning explained
ActivateRelevance only enables evidence propagation and value invalidation. EnableNoisyMAXRelevance is only used during simplification.Do ActivateRelevance and EnableNoisyMAXRelevance enable/disable both of them? or which one?
SetEvidence will cause propagation/invalidation. Simplification is only performed as part of inference.When I call SetEvidence, does it only propagate&invalidate or also simplify?
See this link:What do you mean by skid?
http://software.intel.com/en-us/article ... incorrect/
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.Is it important to set targets first and evidence afterwards, or should it be done the other way round? Or does it not matter?
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 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.
The choice of inference algorithm has no influence on the time required to perform SetTarget call.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.
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.Not just for DSL_ALG_BN_RELEVANCEDECOMP and DSL_ALG_BN_RELEVANCEDECOMP2?Depending on target set and evidence SMILE may split network into separate fragments
No, there's no callback mechanism for this.Interesting! Can I see somehow from outside whether this happened or not?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.
The following network properties can be used to set the thresolds - they may change anytime, do not consider them to be oficially supported:Is that threshold hard-coded? Is it machine-dependent? Or can I set it through the API?
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.
-
- Site Admin
- Posts: 430
- Joined: Tue Dec 11, 2007 4:24 pm
Re: Relevance Reasoning explained
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:- 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?
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
Re: Relevance Reasoning explained
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 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:
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 alrightI 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.