Hi,
I currently have a network in GeNIe that is too complex for the clustering algorithm (needs too much memory). Since approximation and relevance-based decomposition are not feasible options, I'm aiming too reduce the complexity of the network structure. The big question is where in the network this can best be done. Is there some way I can see what jointree GeNIe/SMILE builts up or aims to built up for my model in the background? Can I find somewhere what triangulation heuristic(s) is(are) used?
Cheers!
Bram
Jointree and triangulation heuristic(s)
-
- Site Admin
- Posts: 1417
- Joined: Mon Nov 26, 2007 5:51 pm
Re: Jointree and triangulation heuristic(s)
That depends on the structure of your network.Bramm wrote:The big question is where in the network this can best be done.
We have a function pointer which (if not null) is invoked after successful triangulation with basic statistics describing the created jointree. However, it does not give info on actual jointree structure. It's also not invoked when triangulation fails.Is there some way I can see what jointree GeNIe/SMILE builts up or aims to built up for my model in the background?
The heuristic is a simple greedy one step ahead search. The clique selected is the one with the smallest potential matrix (i.e. the one with lowest element count resulting from multiplying the outcome counts of clique nodes). Note that triangulation and all subsequent steps are performed on the jointree resulting from the output from the relevance layer. The relevance output is affected by target and evidence sets.Can I find somewhere what triangulation heuristic(s) is(are) used?
Re: Jointree and triangulation heuristic(s)
Cheers for that!
It's unfortunate though that the jointree is not available for the user. I think it can give useful information on where in the network (structural) simplification would be most effective (and the jointree must be available in the background already). Hugin software help out a little since it offers both a view of the jointree and a clique size triangulation heuristic. Yet due to arbitrariness in the triangulation heuristic and jointree derivation there is no guarantee this jointree will (strongly) resemble the one in GeNIe/SMILE, as I understand it. And, on top of that, Hugin won't show the jointree if the use of it would take up too much memory in evidence propagation, which is the main problem in the first place here.
One more question though regarding the error message "Error (-42): UpdateBeliefs fails - network structure is too complex" I get. I read in a different post:
Kind regards.
It's unfortunate though that the jointree is not available for the user. I think it can give useful information on where in the network (structural) simplification would be most effective (and the jointree must be available in the background already). Hugin software help out a little since it offers both a view of the jointree and a clique size triangulation heuristic. Yet due to arbitrariness in the triangulation heuristic and jointree derivation there is no guarantee this jointree will (strongly) resemble the one in GeNIe/SMILE, as I understand it. And, on top of that, Hugin won't show the jointree if the use of it would take up too much memory in evidence propagation, which is the main problem in the first place here.
One more question though regarding the error message "Error (-42): UpdateBeliefs fails - network structure is too complex" I get. I read in a different post:
Does this mean that the jointree found would take up too much memory, so no memory blocks are allocated at all? Or is this message returned when triangulation has failed? Or can it occur in both situations?Error -42 comes from the triangulation phase. If you receive this error no memory blocks for cliques/sepsets have been allocated yet. OTOH, if you get std::bad_alloc it's likely that you'll get memory leaks (due to substantial amounts of legacy code in SMILE)
Kind regards.
-
- Site Admin
- Posts: 1417
- Joined: Mon Nov 26, 2007 5:51 pm
Re: Jointree and triangulation heuristic(s)
We're using an approach which is quite different. As I understand, Hugin creates the jointree for the network and transforms it for each evidence set. GeNIe/SMILE creates a temporary forest of jointrees for each evidence/target set. I'm using the term forest, because our relevance layer can split the network into disjoint fragments if it's possible. These fragments are processed sequentially, each with its own jointree.Bramm wrote:It's unfortunate though that the jointree is not available for the user. I think it can give useful information on where in the network (structural) simplification would be most effective (and the jointree must be available in the background already). Hugin software help out a little since it offers both a view of the jointree and a clique size triangulation heuristic.
However, I agree that some form of callback mechanism into jointree creation could be usueful. Without this in place, I can only recommend setting single target at a time over the set of nodes you're interested in, and updating the network. This may give you a somewhat limited insight into the cause of the structural complexity. You can also send your network or its obfuscated counterpart to me - I'll pass it to people who can help. To obfuscate the model, see GeNIe's Network menu.
Things have changed (for the better) since that post. Jointree-related code catches the std::bad_alloc now and there should be no memory leaks.One more question though regarding the error message "Error (-42): UpdateBeliefs fails - network structure is too complex" I get.
Final note: clustering will automatically switch to relevance-based decomposition if there's more than one target node (or there are no explicit target nodes).
Re: Jointree and triangulation heuristic(s)
Thanks. I hadn't realised relevance-based decomposition was running in the background as we have not set any target nodes.
Thanks also for the offer on distributing an obfuscated version of the model. As a matter of fact we already have used that functionality and sent the model to some BN experts. At the moment we conduct the usual tricks for model simplification, complemented by a trial-and-error approach for the less obvious structural simplifications (informed by a Hugin jointree for a slightly simpler version of the model). It would be great though if the trial-and-error part of this process could be replaced by a more intelligent one, also taking proposed future extensions to the model in mind.
Cheers.
Thanks also for the offer on distributing an obfuscated version of the model. As a matter of fact we already have used that functionality and sent the model to some BN experts. At the moment we conduct the usual tricks for model simplification, complemented by a trial-and-error approach for the less obvious structural simplifications (informed by a Hugin jointree for a slightly simpler version of the model). It would be great though if the trial-and-error part of this process could be replaced by a more intelligent one, also taking proposed future extensions to the model in mind.
It's good to read that the memory leaks have been fixed. Question remains though what exactly can be causing the Error (-42) to pop up then : failed triangulation, too large jointrees in the forrest memory-wise, both, other...?shooltz wrote:Things have changed (for the better) since that post. Jointree-related code catches the std::bad_alloc now and there should be no memory leaks.
Cheers.
-
- Site Admin
- Posts: 1417
- Joined: Mon Nov 26, 2007 5:51 pm
Re: Jointree and triangulation heuristic(s)
Triangulation fails when it detects that total size of all cliques determined so far exceeds the memory address space limit. In such case the program returns with -42.Bramm wrote:Question remains though what exactly can be causing the Error (-42) to pop up then : failed triangulation, too large jointrees in the forrest memory-wise, both, other...?
If triangulation completes, the jointree creation starts. Due to heap fragmentation or other OS-related factors any allocation for clique/sepset can fail. std::alloc is thrown by C++ runtime; SMILE catches the exception and returns -42.
Logically, both are the same errors, so the status code is also the same.
Note that evidence greatly influences the workload for the clustering and, depending on the structure and parameters in the model, can reduce or increase the memory pressure in clustering.
Re: Jointree and triangulation heuristic(s)
Clear, Cheers!