Information about Intelligent Bias of Network Structures in the Hierarchical BOA

Published on July 22, 2009

Author: pelikan

Source: slideshare.net

One of the primary advantages of estimation of distribution algorithms (EDAs) over many other stochastic optimization techniques is that they supply us with a roadmap of how they solve a problem. This roadmap consists of a sequence of probabilistic models of candidate solutions of increasing quality. The first model in this sequence would typically encode the uniform distribution over all admissible solutions whereas the last model would encode a distribution that generates at least one global optimum with high probability. It has been argued that exploiting this knowledge should improve EDA performance when solving similar problems. This paper presents an approach to bias the building of Bayesian network models in the hierarchical Bayesian optimization algorithm (hBOA) using information gathered from models generated during previous hBOA runs on similar problems. The approach is evaluated on trap-5 and 2D spin glass problems.

Motivation Outline hBOA Biasing Experiments Conclusions Motivation In optimization, always looking to solve harder problems hBOA can solve a broad class of problems robustly and fast Scalability isn’t always enough Much work has been done in speeding up hBOA Sporadic Model-Building Parallelization Others M. Hauschild and M. Pelikan University of Missouri - St. Louis Intelligent Bias of Network Structures in the Hierarchical BOA

Motivation Outline hBOA Biasing Experiments Conclusions Motivation Each run of an EDA leaves us with a tremendous amount of information The algorithm decomposes the problem for us Left with a series of models Methods have been developed to exploit this information Require hand-inspection Very sensitive to parameters Wanted to develop a method that is less sensitive to parameters M. Hauschild and M. Pelikan University of Missouri - St. Louis Intelligent Bias of Network Structures in the Hierarchical BOA

Motivation Outline hBOA Biasing Experiments Conclusions Outline hBOA Biasing hBOA Structural Priors in Bayesian Networks Split Probability Matrix SPM-based Bias Test Problems Experiments Trap-5 2D Ising Spin Glasses Conclusions M. Hauschild and M. Pelikan University of Missouri - St. Louis Intelligent Bias of Network Structures in the Hierarchical BOA

Motivation Outline hBOA Biasing Experiments Conclusions hierarchical Bayesian Optimization Algorithm (hBOA) Pelikan, Goldberg, and Cantú-Paz; 2001 Uses Bayesian network with local structures to model solutions Acyclic directed Graph String positions are the nodes Edges represent conditional dependencies Where there is no edge, implicit independence Niching to maintain diversity M. Hauschild and M. Pelikan University of Missouri - St. Louis Intelligent Bias of Network Structures in the Hierarchical BOA

Motivation Outline hBOA Biasing Experiments Conclusions hBOA Two Components Structure Edges determine dependencies Majority of time spent here Parameters Conditional probabilities depending on parents Example - p(Accident|Wet Road, Speed) Network built greedily, one edge at a time Metric punishes complexity M. Hauschild and M. Pelikan University of Missouri - St. Louis Intelligent Bias of Network Structures in the Hierarchical BOA

Motivation Outline hBOA Biasing Experiments Conclusions hBOA M. Hauschild and M. Pelikan University of Missouri - St. Louis Intelligent Bias of Network Structures in the Hierarchical BOA

Motivation Outline hBOA Biasing Experiments Conclusions hBOA M. Hauschild and M. Pelikan University of Missouri - St. Louis Intelligent Bias of Network Structures in the Hierarchical BOA

Motivation Outline hBOA Biasing Experiments Conclusions hBOA M. Hauschild and M. Pelikan University of Missouri - St. Louis Intelligent Bias of Network Structures in the Hierarchical BOA

Motivation Outline hBOA Biasing Experiments Conclusions hBOA M. Hauschild and M. Pelikan University of Missouri - St. Louis Intelligent Bias of Network Structures in the Hierarchical BOA

Motivation Outline hBOA Biasing Experiments Conclusions hBOA M. Hauschild and M. Pelikan University of Missouri - St. Louis Intelligent Bias of Network Structures in the Hierarchical BOA

Motivation Outline hBOA Biasing Experiments Conclusions hBOA M. Hauschild and M. Pelikan University of Missouri - St. Louis Intelligent Bias of Network Structures in the Hierarchical BOA

Motivation Outline hBOA Biasing Experiments Conclusions Structural Priors Bayesian-Dirichlet metric for network B and data set D with prior knowledge ξ is p(B|ξ)p(D|B, ξ) p(B|D, ξ) = · (1) p(D|ξ) where p(B|ξ) is the prior probability of network structure. Bias towards simpler models is given by p(B|ξ) = c2−0.5( i |Li |)log2 N , (2) where N is the population and i |Li | is the number of leaves. Want to modify this based on prior information M. Hauschild and M. Pelikan University of Missouri - St. Louis Intelligent Bias of Network Structures in the Hierarchical BOA

Motivation Outline hBOA Biasing Experiments Conclusions Biasing M. Hauschild and M. Pelikan University of Missouri - St. Louis Intelligent Bias of Network Structures in the Hierarchical BOA

Motivation Outline hBOA Biasing Experiments Conclusions Split Probability Matrix Lets bias towards same number of splits Use split probability matrix to store our prior knowledge 4-dimensional matrix of size n × n × d × e where n is the problem size, d is maximum number of splits, and e is the maximum generation S stores, for each possible pair of decision variables, the conditional probability of a split between them (by gen.) In our sampling we use a threshold of 90% for e M. Hauschild and M. Pelikan University of Missouri - St. Louis Intelligent Bias of Network Structures in the Hierarchical BOA

Motivation Outline hBOA Biasing Experiments Conclusions SPM-Based Bias No splits One split 1 1 0.5 1 2 2 0.8 100 3 100 3 4 5 0.4 4 5 node j node j 6 2 4 6 6 2 4 6 0.6 200 0.3 200 0.4 0.2 300 300 0.2 0.1 400 0 400 0 100 200 300 400 100 200 300 400 node i node i M. Hauschild and M. Pelikan University of Missouri - St. Louis Intelligent Bias of Network Structures in the Hierarchical BOA

Motivation Outline hBOA Biasing Experiments Conclusions SPM-Based Bias Want to deﬁne our own prior probability Prior probability of network structure: n p(B|ξ) = p(Ti ). (3) i=1 For a particular decision tree Ti , p(Ti ) is given by: p(Ti ) = κ qi,j,k (i,j), (4) j=i where qi,j,k (i,j) denotes the probability that there are at least k(i, j) splits on Xj in decision trees for Xi . κ is used to tune the effect of prior information. M. Hauschild and M. Pelikan University of Missouri - St. Louis Intelligent Bias of Network Structures in the Hierarchical BOA

Motivation Outline hBOA Biasing Experiments Conclusions SPM-Based Bias Consider evaluation of split on Xj in Ti given k − 1 splits Gains in log-likelihood after a split without considering prior information: δi,j = log2 p(D|B , ξ) − log2 p(D|B, ξ) − 0.5log2N. (5) where B is the network before the split and B is after. SPM used to compute gains after a split: δi,j = log2 p(D|B , ξ) − log2 p(D|B, ξ) + κ log2 Si,j,k (i,j),g (6) This bias can still be overcome M. Hauschild and M. Pelikan University of Missouri - St. Louis Intelligent Bias of Network Structures in the Hierarchical BOA

Motivation Outline hBOA Biasing Experiments Conclusions Trap-5 Partition binary string into disjoint groups of 5 bits 5 if ones = 5 trap5 (ones) = , (7) 4 − ones otherwise Total ﬁtness is sum of single traps Global Optimum: String 1111...1 Local Optimum: 00000 in any partition M. Hauschild and M. Pelikan University of Missouri - St. Louis Intelligent Bias of Network Structures in the Hierarchical BOA

Motivation Outline hBOA Biasing Experiments Conclusions 2D Ising Spin Glass Origin in physics Spins arranged on a 2D grid Each spin sj can have two values: +1 or -1 Each connection i, j has a weight Jij . Set of weights speciﬁes one instance. Energy is given by... E (C) = si Ji,j sj , (8) i,j M. Hauschild and M. Pelikan University of Missouri - St. Louis Intelligent Bias of Network Structures in the Hierarchical BOA

Motivation Outline hBOA Biasing Experiments Conclusions 2D Ising Spin Glass Problem is to ﬁnd the values of the spins so energy is minimized Very hard for most optimization techniques Extremely large number of local optima Decomposition of bounded order is insufﬁcient Solvable in polynomial time by analytical techniques hBOA has been shown emperically to solve it in polynomial time A deterministic hill-climber(DHC) is used to improve the quality of evaluated solutions M. Hauschild and M. Pelikan University of Missouri - St. Louis Intelligent Bias of Network Structures in the Hierarchical BOA

Motivation Outline hBOA Biasing Experiments Conclusions Experiments on Trap-5 Need to learn SPM from sample Show effects of SPM using various κ Problem sizes from n = 50 to n = 175 SPM learned from 10 bisection runs of 10 runs each Used to bias model building in another 10 bisection runs Threshold of 90% Varied κ from 0.05 to 3 M. Hauschild and M. Pelikan University of Missouri - St. Louis Intelligent Bias of Network Structures in the Hierarchical BOA

Motivation Outline hBOA Biasing Experiments Conclusions Speedups on Trap-5, κ = 1 Execution Speedup Evaluation Speedup Execution Time Speedup 7 4 Evaluation Speedup 6 5 3 4 3 2 2 1 1 50 75 100 125 150 175 50 75 100 125 150 175 Problem Size Problem Size Reduction in Bits Examined 80 Reduction Factor 60 40 20 0 50 75 100 125 150 175 Problem Size M. Hauschild and M. Pelikan University of Missouri - St. Louis Intelligent Bias of Network Structures in the Hierarchical BOA

Motivation Outline hBOA Biasing Experiments Conclusions Effects of κ on Trap-5 of n = 100 Execution Time Evaluations 4 15 x 10 15 Execution Time Evaluations 10 10 5 5 0 0 0.05 1 2 3 0.05 1 2 3 κ κ Bits Examined 7 x 10 10 Bits Examined 5 0 0.25 1 2 3 κ M. Hauschild and M. Pelikan University of Missouri - St. Louis Intelligent Bias of Network Structures in the Hierarchical BOA

Motivation Outline hBOA Biasing Experiments Conclusions Experiments on 2D Ising Spin Glass Need to learn SPM from sample Show effects of SPM using various κ 100 instances of 3 different sizes Cross-validation SPM learned from 90 instances, used to solve remaining 10 Repeated 10 times Threshold of 90% Varied κ from 0.05 to 3 M. Hauschild and M. Pelikan University of Missouri - St. Louis Intelligent Bias of Network Structures in the Hierarchical BOA

Motivation Outline hBOA Biasing Experiments Conclusions Speedups on 2D Ising spin glass Speedups obtained using SPM bias where κ = 1 size Exec. speedup Eval. Speedup Bits Exam. 16 × 16 1.16 0.87 1.5 20 × 20 1.42 0.96 1.84 24 × 24 1.56 0.98 2.03 M. Hauschild and M. Pelikan University of Missouri - St. Louis Intelligent Bias of Network Structures in the Hierarchical BOA

Motivation Outline hBOA Biasing Experiments Conclusions Effects of κ on 2D Ising spin glass 16 × 16 20 × 20 8 40 Execution Time Execution Time 6 30 4 20 2 10 0 5 0.05 1 2 3 0.05 1 2 3 κ κ 24 × 24 200 Execution Time 150 100 50 0 0.05 1 2 3 κ M. Hauschild and M. Pelikan University of Missouri - St. Louis Intelligent Bias of Network Structures in the Hierarchical BOA

Motivation Outline hBOA Biasing Experiments Conclusions Effects of κ on 2D Ising spin glass 16 × 16 20 × 20 5000 8000 7000 Evaluations Evaluations 4000 6000 5000 3000 4000 2000 3000 0.05 1 2 3 0.05 1 2 3 κ κ 24 × 24 4 x 10 2 Evaluations 1.5 1 0.5 0.05 1 2 3 κ M. Hauschild and M. Pelikan University of Missouri - St. Louis Intelligent Bias of Network Structures in the Hierarchical BOA

Motivation Outline hBOA Biasing Experiments Conclusions Effects of κ on 2D Ising spin glass 16 × 16 20 × 20 8 8 x 10 x 10 2 8 Bits Examined Bits Examined 1.5 6 1 4 0.5 2 0.05 1 2 3 0.05 1 2 3 κ κ 24 × 24 9 x 10 4 Bits Examined 3 2 1 0.05 1 2 3 κ M. Hauschild and M. Pelikan University of Missouri - St. Louis Intelligent Bias of Network Structures in the Hierarchical BOA

Motivation Outline hBOA Biasing Experiments Conclusions Effects of κ on 2D Ising spin glass κ that led to maximum speedup size κ Exec. speedup Eval. Speedup Bits Exam 16 × 16 0.75 1.24 0.96 1.66 20 × 20 1.25 1.44 0.94 1.85 24 × 24 1 1.56 0.98 2.03 M. Hauschild and M. Pelikan University of Missouri - St. Louis Intelligent Bias of Network Structures in the Hierarchical BOA

Motivation Outline hBOA Biasing Experiments Conclusions Conclusions Unlike many EAs, we are left with a series of models Many ways to try and exploit this information Proposed a method to bias network structure in hBOA Led to speedups from 3.5-6 on Trap-5 and up to 1.5 on 2D Ising spin glasses This is only one way Can be extended to many other problems M. Hauschild and M. Pelikan University of Missouri - St. Louis Intelligent Bias of Network Structures in the Hierarchical BOA

Motivation Outline hBOA Biasing Experiments Conclusions Conclusions Efﬁciency enhancements work together Parallelization 50 Hybridization 2 Soft bias from past runs 1.5 Evaluation Relaxation 1.1 Total 165 M. Hauschild and M. Pelikan University of Missouri - St. Louis Intelligent Bias of Network Structures in the Hierarchical BOA

Motivation Outline hBOA Biasing Experiments Conclusions Any Questions? M. Hauschild and M. Pelikan University of Missouri - St. Louis Intelligent Bias of Network Structures in the Hierarchical BOA

Intelligent Bias of Network Structures in the Hierarchical BOA Mark Hauschild Missouri Estimation of Distribution Algorithms Laboratory (MEDAL) Dept. of ...

Read more

Intelligent bias of network structures in the hierarchical BOA Hauschild, Mark W.; Pelikan, Martin Intelligent Bias of Network Structures in the ...

Read more

... to bias the building of Bayesian network models in ... of Network Structures in the Hierarchical BOA} ... networks with local structure ...

Read more

Abstract. One of the primary advantages of estimation of distribution algorithms (EDAs) over many other stochastic optimization techniques is that they ...

Read more

Searching for phrase hierarchical BOA (changed automatically) ... Intelligent bias of network structures in the hierarchical BOA. GECCO : 2009:

Read more

Using Previous Models to Bias Structural Learning in the Hierarchical BOA ... model, model structure, ...

Read more

... Hierarchical BOA solves ising spin glasses and MAXSAT, ... Martin Pelikan, Intelligent bias of network structures in the hierarchical BOA, ...

Read more

... Analyzing Probabilistic Models in Hierarchical ... Analyzing Probabilistic Models in Hierarchical BOA ... Intelligent Bias of Network Structures ...

Read more

Transfer Learning, Soft Distance-Based Bias, ... Intelligent bias of network structures in the ... Soft Distance-Based Bias, and the Hierarchical BOA

Read more

## Add a comment