Research On Optimal Tree Decomposition Of Bayesian Networks

Optimal tree decomposition is one of basic problems in the research about Bayesian networks beacause it is closely related to both theoretical and practical aspects about Bayesian networks, and it occupies an important position in theory of computation. According to three different optimization goals:minimum width, minimum weighted width and minimum state space size of join tree, there are three kinds of tree decomposition problems:treewidth, weighted treewidth and treecost, where treewidth is a classical problem in the research area of graph theory.Although there is a long history about the research on treewidth, no work has been appeared to discuss completely, strictly and generally over all the three problems, especially over the relationship among elimination ordering, triangulation and tree decomposition, In existing solutions to these problems, heuristics and stochasitic optimization are two main methods. Heuristics are very suit to get feasilbe solutions online. On the other hand, stochastic methods are able to achieve near-to-optimal solutions offline. However, resluts given by existing heuristics are usually very worse and not stable in face of various cases. Stochastic approaches to the treecost problem often give better results but still neither good nor stable enough yet. And most stochastic approaches to the treewidth problem are very time-consuming. Existing algorithms are not practical in real application.On one hand, in view of set theory and graph theory, this paper gives definintion of subset family evaluation function and its stability, and elaborates theoretically the relationship among elimination ordering, triangulation and tree decomposition on this basis. On the other hand, in aims to make improve on existing algorithms, this paper perfoms research from the aspects of heuristics, iterative local search and stochastic methods and presents some effective algorithms and algorithmic framework. The main work of this paper is as follows.1. Based on the presentation of subset family evaluation function, this paper gives a strict and general elaboration about the relationship among optimal triangulation, optimal elimination ordering and optimal tree decomposition. Treewidth, weighted treewidth and treecost problems are defined formaly via three subset family evaluation functions of fmax_size,fmax_weight andftotal_weight.In a further step, this paper also explains some basic things about tree decomposition of Bayesian network, such as the the preprocessing method of reducing simplicial nodes.2. To solve the treecost problem, this paper provides some novel algorithms and algorithmic frameworks.(1) Firstly, the heuristics and iterative search methods are investigated. To overcome the shortcoming of instability of existing heuristics, five new heuristics, MinFillWeightProduct, MinLinearWeightSum, MinLBWeightSum, MinLBFillWeightSum and MinLBFillWeightProduct, are presented. In addition, an iterative local search method named IRT and a multi-heuristic-based greedy method named kHR are proposed. In a further step, based on properties of tree decomposition of Bayesian network, an efficient approach named FAST-IRT, which is equivalent to but more fast than IRT, is provided. The equivalence between IRT and FAST-IRT is also proved formally. Experiments on typical Bayesian network benchmarks show that all these heuristics and iterative methods are more superior to existing heuristics on the whole and very suitable to online problem-solving. More better results can be obtained by combining these heuristics and iterative methods with other methods, such as the stochastic methods proposed in this paper.(2) Secondly, to improve existing stochastic methods, two ant colony approaches are developed for the treecost problem. MMMAS-SA is a hybrid max-min ant system. To increasing global searching ability, MMMAS uses pseudo-random-proportional rule to construct a feasible solution, adjusts the lower pheromone limit in the runng process to make ants explore more regions in the searching space, and adopts a kind of combined simulated annealing scheme to improve ant colony's exploitation ability. MHC-ACS is an adaptive multi-heuristic ant colony system. It makes full use of the advantages of heuristics, selects appropriate heuristics adaptively, and applies a quantitative control over the heuristics dynamicly. All these mechanisms assure heuristics to be incorporated into MHC-ACS to a great extent. Experimental results on some representative Bayesian networks indicate that MMMAS-SA and MHC-ACS are effective methods for the treecost problem. They can achieve good results in a shor time and presents better robustness than other stochastic optimization methods for the treecost problem.(3)Thirdly, this paper applies cooperative coevolutionary framework to the treecost problem for the first time and proposes two cooperative coevolutionary frameworks named FGCC and VNGCC respectively. Three optimizers-DGHGA, MDPSO and DDE, are constructed for FGCC and VNGCC frameworks. DGHGA introduces heuristics into its genetic evolution procedure. It uses a multiple-heuristic mutation operation to improve its robustness. In order to avoid premature convergence, DGHGA detects the states of stagnation and convergence by measuring population diversity via an efficient method. MDPSO operates particles'positions and velocities in a discrete manner. It also applies an improved mutation operation to to endow each particle with the ability of global search. To prevent the particles to be trapped in the local optimum, MDPSO resets the particles on the global best-so-far position. DDE is a discrete version of traditional DE algorithm performing the operations between individuals via the method of swap sequence. It runs with few parameters and possesses the feature of strong self-organization. Tests manifest that all the 18 algorithms utilizing FGCC or VNGCC framework can solve the treecost problems effectively. This work lays a solid foundation for the possible solution of treecost problem by utilizing the distribution and parallel characteristics of cooperative coevolution mechanism.3. To make up the shortfall of long running time of existing stochastic methods for the treewidth problem, this paper proposes an improved discrete ABC algorithm named IDABC. IDABC finds treewidth in the discrete search space composed by elimination orderings. It improves traditional ABC algorithm by adding backup food sources, special employees, iterative searching onlookers, heuristic searching onlookers and intelligent onlookers to the bee colony to enhance the global search ability. By comparison with some recent iterative local search method and stochastic optimization methods on DIMACS becnchmarks, IDABC presented its high efficiency, robustness and comparability to other existing approaches.Optimal tree decomposition is an important area for research about Bayesian network. Especially, the treewidth problem is also a key topic in graph theory and computation theory. The research work about tree decomposition of Bayesian network, both in theoretical aspect and in algorithmic aspect, has a long history. However, the solution to this problem is neither mature nor perfect enough. The subset-family-evaluation-function-based framework presented in this paper characterize tree decomposition problem in a high level and and has a strong generality so it is of proper theoretical significance. On the other hand, this paper presents some research work about heuristics, iterative search and swarm intelligence methods for the tree decomposition problem. These methods provide useful novel ways for online and offfline solving of the tree decomposition of Bayesian network and possess good application values.