Inference algorithms in SMILE

[jonnie]

Hello,
I want to ask some questions regarding the inference algorithms in Smile, since the documentation is a bit incomplete at times.

Sources of information about the Smile inference algorithms are:

Documentation:
http://genie.sis.pitt.edu/wiki/Applicat ... _a_Network
http://genie.sis.pitt.edu/wiki/Referenc ... SL_network (scroll down to SetDefaultBNAlgorithm)

constants.h in the C++ API; excerpt:

Code: Select all

// BN algorithms
#define DSL_ALG_BN_LAURITZEN              0
#define DSL_ALG_BN_HENRION                1
#define DSL_ALG_BN_PEARL                  2
#define DSL_ALG_BN_LSAMPLING              3
#define DSL_ALG_BN_SELFIMPORTANCE         4
#define DSL_ALG_BN_HEURISTICIMPORTANCE    5
#define DSL_ALG_BN_BACKSAMPLING           6
#define DSL_ALG_BN_AISSAMPLING            7
#define DSL_ALG_BN_EPISSAMPLING           8
#define DSL_ALG_BN_LBP					  9
#define DSL_ALG_BN_LAURITZEN_OLD          10
#define DSL_ALG_BN_RELEVANCEDECOMP          11
#define DSL_ALG_BN_RELEVANCEDECOMP2       12
#define DSL_ALG_HBN_HEPIS					13
#define DSL_ALG_HBN_HLW						14
#define DSL_ALG_HBN_HLBP					15
#define DSL_ALG_HBN_HLOGICSAMPLING			16
// ID algorithms
#define DSL_ALG_ID_COOPERSOLVING          0
#define DSL_ALG_ID_SHACHTER               1

Network.java of the JSmile wrapper API for Java; excerpt:

Code: Select all

// Bayesian network algoritm types
public class BayesianAlgorithmType 
{
	public static final int Lauritzen            = 0;
	public static final int Henrion              = 1;
	public static final int Pearl                = 2;
	public static final int LSampling            = 3;
	public static final int SelfImportance       = 4;
	public static final int HeuristicImportance  = 5;
	public static final int BackSampling         = 6;
	public static final int AisSampling          = 7;
	public static final int EpisSampling         = 8;
	public static final int LBP                  = 9;
}
// Influence diagram algoritm types
public class InfluenceDiagramAlgorithmType 
{
	public static final int PolicyEvaluation  = 0;
	public static final int FindBestPolicy    = 1;
}

There's several issues:

• It's difficult and time-consuming to find information about all the different algorithms
• The ID algorithms have different names in C++ and Java; I guess that confuses some people
• BN-algorithms 10-12 and the HBN-algorithms are not available in Java.

So, this leaves me scratching my head! If someone can help me please post an answer
My questions are:

• I guess DSL_ALG_BN_LBP means Loopy Belief Propagation. However, it's nowhere stated clearly, so is that correct?
• Which algorithms are exact, which are approximate? I guess algorithms named *Sampling and *Importance are approximate, as is LBP; and Lauritzen is exact. Correct? What about the others?
• Why are some algorithms not available in Java? Are they in beta stadium or something like that?
• What does "HBN" mean? A guess could be that the H stands for hybrid, that is, they are for networks with continuous nodes...
• Can someone provide a short description (one or two lines) for each algorithm to describe what they do?

As I said, wading through all the papers is quite problematic (also see this post http://genie.sis.pitt.edu/forum/viewtopic.php?f=2&t=942). I'd edit the wiki to add what I found out, but it's not editable by the general public.

Thanks for reading & helping

[Martijn]

Hi Jonnie,

Sorry for the long wait on this one. Tying up loose ends as much as possible.

Answering in the same order as asked

The issues:
- I've added references in the documentation for the papers in the two wiki pages you have mentioned now have links to the papers
- Good point, the name difference is a little bit confusing but they usually are just with the DSL_ALG_BN part, I also suspect this to not have problem when compiling the library
- Algorithm # 10 is an old implementation of Lauritzen and shouldn't be used anymore (hence it's absence in the wrapper), not sure about # 11 and 12, presumably there was never a dire need to add them to the wrapper

Questions
- That's correct DSL_ALG_BN_LBP is Loopy belief propagation.
- Exact: # 0,2(works only for polytrees), 10,11,12 Approximate: # 1,3,4,5,6,7,8,9,13,14,15,16 Where 13-16 are for hybrid networks
- Java wrapper isn't really developed very actively, mostly algorithms were just added when needed.
- Correct, HBN stands for hybrid Bayesian network.
- Algorithm descriptions, see below:

0. Lauritzen's clustering algorithm, creates join tree for inference.
1. Henrion's probabilistic logic sampling algorithm, Generates 'x' samples by going through the nodes of the (partially ordered) network. Samples are then used to calculate the (posterior) distributions.
2. Pearl's inference algorithm for polytrees like Lauritzen based on message passing, but now messages are passed between the original nodes and not clique nodes of a join tree
3. Likelihood Sampling, more efficient than #1 no samples are thrown away. Samples are generated with evidence set and are then weighted by the probability of the evidence.
4. Importance Sampling algorithm by Shachter & Peot. this one uses the self-importance distribution
5. Importance Sampling algorithm by Shachter & Peot. this one uses the heuristic-importance distribution (and makes use of Pearl's polytree algorithm as part of the calculation)
6. Backwards sampling algorithm: samples from the evidence nodes up.
7. AIS sampling: Adaptive Importance Sampling. First the importance function is learned using about 25,000 samples . Then importance sampling is done as usual.
8. EPIS sampling: Estimated Posterior Importance Sampling algorithm: uses loopy belief propagation to compute an estimate of the posterior probability over all nodes of the network and then uses importance sampling to refine this estimate
9. Pearl's loopy belief propagation basically same as #2, i.e. message passing among nodes but this time without the polytree constraint, meaning that it is no longer exact, you now have to wait for convergence of the messages.
10. Old implementation of Lauritzen's algorithm, don't use.
11. Form of relevance reasoning for Lauritzen's clustering algorithm. In this case Linear decomposition.
12. Form of relevance reasoning for Lauritzen's clustering algorithm. Does a recusive decomposition, when things get to complex it falls back to linear decomposition.

Algorithms for hybrid inference
13. HEPIS sampling, version of EPIS sampling for HBNs
14. HLW sampling, version of Logic Weighting sampling for HBNs
15. HLBP, version of Loopy Belief propagation for HBNs
16.HLOGICSAMPLING, version of Logic Sampling for HBNs

Hope this helps.

Best,

Martijn

[jonnie]

Thank you, that helps very much indeed!