| Graphical models are increasingly popular tools for modeling problems involving uncertainty. They deal with uncertainty by modeling and reasoning about degrees of uncertainty explicitly based on probability theory. Practical models based on graphical models often reach the size of hundreds of variables. Although a number of ingenious inference algorithms have been developed, the problem of exact belief updating in graphical models is NP-hard. Approximate inference schemes may often be the only feasible alternative for large and complex models. The family of stochastic sampling algorithms is a promising subclass of approximate algorithms. Since previous stochastic sampling algorithms cannot converge to reasonable estimates of the posterior probabilities within a reasonable amount of time, in cases with very unlikely evidence, we cannot use the results. This thesis addresses this problem by proposing some new sampling algorithms to do the approximate inference.; First, an adaptive importance sampling algorithm for Bayesian networks, AIS-BN, was developed. It shows promising convergence rates even under extreme conditions and seems to outperform the existing sampling algorithms consistently. Second, some tighter stopping rules were developed. Based on these stopping rules, two distribution-independent algorithms (the SA-μ and SA-σ algorithms) to estimate the mean of bounded random variables, one with and one without the knowledge of variance, were proposed. These two algorithms guarantee that the estimate is within the desired precision. Third, confidence inference, which can be used to calculate the probabilistic accuracy of estimate, was discussed. The new developed AISBN-μ and AISBN-σ algorithms have the attractive property of not only allowing the user to know whether approximating an inference requires a prohibitive amount of computation after a number of samples are obtained, but also allowing the user to try to avoid the prohibitive amount of computation using some other heuristic methods in AIS-BN when it happens. Last, in cases with likely evidence or with good importance sampling functions, Latin hypercube sampling and quasi-Monte Carlo methods to improve most of the current available algorithms further were developed. The experimental results show that these two methods can significantly improve the performance of sampling algorithms. |
