Jointree and triangulation heuristic(s)

The front end.
Post Reply
Bramm
Posts: 4
Joined: Wed Jan 23, 2013 3:10 pm

Jointree and triangulation heuristic(s)

Post by Bramm »

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
shooltz[BayesFusion]
Site Admin
Posts: 1417
Joined: Mon Nov 26, 2007 5:51 pm

Re: Jointree and triangulation heuristic(s)

Post by shooltz[BayesFusion] »

Bramm wrote:The big question is where in the network this can best be done.
That depends on the structure of your network.
Is there some way I can see what jointree GeNIe/SMILE builts up or aims to built up for my model in the background?
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.
Can I find somewhere what triangulation heuristic(s) is(are) used?
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.
Bramm
Posts: 4
Joined: Wed Jan 23, 2013 3:10 pm

Re: Jointree and triangulation heuristic(s)

Post by Bramm »

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:
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)
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?

Kind regards.
shooltz[BayesFusion]
Site Admin
Posts: 1417
Joined: Mon Nov 26, 2007 5:51 pm

Re: Jointree and triangulation heuristic(s)

Post by shooltz[BayesFusion] »

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.
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.

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.

One more question though regarding the error message "Error (-42): UpdateBeliefs fails - network structure is too complex" I get.
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.

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).
Bramm
Posts: 4
Joined: Wed Jan 23, 2013 3:10 pm

Re: Jointree and triangulation heuristic(s)

Post by Bramm »

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.
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.
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...?

Cheers.
shooltz[BayesFusion]
Site Admin
Posts: 1417
Joined: Mon Nov 26, 2007 5:51 pm

Re: Jointree and triangulation heuristic(s)

Post by shooltz[BayesFusion] »

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...?
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.

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.
Bramm
Posts: 4
Joined: Wed Jan 23, 2013 3:10 pm

Re: Jointree and triangulation heuristic(s)

Post by Bramm »

Clear, Cheers!
Post Reply