Next: Glue

Stochastic Sampling

Description
- What is importance sampling? Importance sampling (IS) is a type of approximate infererence algorithm for Bayesian networks. Usually, the importance sampling algorithm is given an evidence file in which the states of certain nodes are already given. Using this evidence file and the conditional probability table of each node, the program generates sample instantiations of the network (i.e., defines the state of each node in the network). From these sample instantiations, it can find the approximate probabilities of each state for each node in the network. The accuracy of the importance sampling algorithm can then be determined by comparing these approximate probabilities to the exact probabilities, as found in the LS module. (Please see our references.)
- Parameters used: Each importance sampling algorithm can either be run graphically or from the command line. If running from the command line, we require that the sampling_method, evidence_filename, casenumber, and network_stem parameters be set in the parameters file. (See Setting environment variables for more information on where input files should be located and what format they should take.) The sampling_method parameter refers to the selected type of importance sampling:
  Forward Sampling -> -f
  Logic Sampling -> -l
  Self-Importance Sampling -> -sis
  Adaptive Importance Sampling -> -ais
  
  The evidence_filename parameter refers to the name of the evidence file, and casenumber refers to how many samples will be taken. The network_stem parameter refers to the filestem of the xml file you will be using. For example, if you wanted to use asia.xml, network_stem should be set to "asia." Once again, you can obtain more information on parameters on the setting environment variables page.
- Output: The results of the root-mean-squared-error between the approximate probabilities and the exact probabilities are printed to a file called "printings.txt," with one value per sample taken. One value will be printed per line. This output file can be easily graphed by opening it in Excel and using the "chart" utility. You can view examples of these charts in the different "example" sections below.
Forward Sampling
- References:
  Cheng, J. and Druzdzel, M. (2000). AIS-BN: An adaptive importance sampling algorithm for evidential reasoning in large Bayesian networks. Journal of Artificial Intelligence Research, 13, 155-188.
  Dagum, P. and Luby, M. (1997). An optimal approximation algorithm for Bayesian inference. Artificial Intelligence, 93, 1-27.
  Fung, R. and Chang, K.-C. (1989). Weighing and integrating evidence for stochastic simulation in Bayesian networks. In Uncertainty in Artificial Intelligence 5, pp. 209-219 New York, N.Y. Elsevier Science Publishing Company, Inc.
  Shachter, R., and Peot, M. (1989). Simulation approaches to general probabilistic inference on belief networks. In Uncertainty in Artificial Intelligence 5, pp. 221-231 New York, N.Y. Elsevier Science Publishing Company, Inc.
- How it works: Forward sampling gets samples by instantiating each node of the network (using the likelihood of each state given the state of the parent nodes) in topological order. In this sampling process, evidence nodes are automatically instantiated to the value given in the evidence file. It then computes a "likelihood weighting" for each sample generated based on the probabilistic likelihood of the states of the evidence nodes. This likelihood weighting is then used in computing the approximate probabilities.
- Example: First make sure the parameters are appropriately set in the .var file (see above). Next, run forward sampling by typing
```
 D:\bnj>java stochasticsampling/InferentialBBN varFile.var
```
  at the command line within the stochasticsampling directory, where varFile.var is the parameters file. You may need to set your input paths if your input files or the parameters file is not in the stochasticsampling directory.
  Below is the graph of the RMSE values from running forward sampling on the Asia network with 5000 samples. Remember, each importance sampling algorithm outputs the RMSE values to a file called printings.txt, which can be opened in Excel.
Logic Sampling
- References:
  Cheng, J. and Druzdzel, M. (2000). AIS-BN: An adaptive importance sampling algorithm for evidential reasoning in large Bayesian networks. Journal of Artificial Intelligence Research, 13, 155-188.
  Henrion, M. (1988). Propogating uncertainty in Bayesian networks by probabilistic logic sampling. In Uncertainty in Artificial Intelligence 2, pp. 149-163 New York, N.Y. Elsevier Science Publishing Company, Inc.
- How it works: Logic sampling gets samples by instantiating each node of the network (using the likelihood of each state given the state of the parent nodes) in topological order. Evidence nodes are sampled just like query nodes. In the end, samples are discarded if the instantiation of the evidence nodes does not match the evidence file. Approximate probabilities are computed by looking at how many times each state for each node appeared in the satisfactory samples.
- Example: First make sure the parameters are appropriately set in the .var file (see above). Next, run logic sampling by typing
```
 D:\bnj>java stochasticsampling/InferentialBBN varFile.var
```
  at the command line within the stochasticsampling directory, where varFile.var is the parameters file. You may need to set your input paths if your input files or the parameters file is not in the stochasticsampling directory.
  Below is the graph of the RMSE values from running logic sampling on the Asia network with 5000 samples. Remember, each importance sampling algorithm outputs the RMSE values to a file called printings.txt, which can be opened in Excel.
Self-Importance Sampling
- References:
  Cheng, J. and Druzdzel, M. (2000). AIS-BN: An adaptive importance sampling algorithm for evidential reasoning in large Bayesian networks. Journal of Artificial Intelligence Research, 13, 155-188.
  Shachter, R., and Peot, M. (1989). Simulation approaches to general probabilistic inference on belief networks. In Uncertainty in Artificial Intelligence 5, pp. 221-231 New York, N.Y. Elsevier Science Publishing Company, Inc.
- How it works: Self-importance sampling gets samples by instantiating each node of the network (using the likelihood of each state given the state of the parent nodes) in topological order. In this sampling process, evidence nodes are automatically instantiated to the value given in the evidence file. (MORE TO COME)
- Example: First make sure the parameters are appropriately set in the .var file (see above). Next, run self-importance sampling by typing
```
 D:\bnj>java stochasticsampling/InferentialBBN varFile.var
```
  at the command line within the stochasticsampling directory, where varFile.var is the parameters file. You may need to set your input paths if your input files or the parameters file is not in the stochasticsampling directory.
  Below is the graph of the RMSE values from running self-importance sampling on the Asia network with 5000 samples. Remember, each importance sampling algorithm outputs the RMSE values to a file called printings.txt, which can be opened in Excel.
Adaptive Importance Sampling
- References:
  Cheng, J. and Druzdzel, M. (2000). AIS-BN: An adaptive importance sampling algorithm for evidential reasoning in large Bayesian networks. Journal of Artificial Intelligence Research, 13, 155-188.
- How it works: Adaptive importance sampling gets samples by instantiating each node of the network (using the likelihood of each state given the state of the parent nodes) in topological order. In this sampling process, evidence nodes are automatically instantiated to the value given in the evidence file. After each casenumber/10 samples, the approximate probabilities for those samples are used to update the conditional probability tables. This allows the probabilities for each node to change from the instantiation of evidence nodes.
- Example: First make sure the parameters are appropriately set in the .var file (see above). Next, run adaptive importance sampling by typing
```
 D:\bnj>java stochasticsampling/InferentialBBN varFile.var
```
  at the command line within the stochasticsampling directory, where varFile.var is the parameters file. You may need to set your input paths if your input files or the parameters file is not in the stochasticsampling directory.
  Below is the graph of the RMSE values from running adaptive importance sampling on the Asia network with 5000 samples. Remember, each importance sampling algorithm outputs the RMSE values to a file called printings.txt, which can be opened in Excel.

KDD-Tools
Fri June 28 2002