PAPER Structure Learning of Bayesian Networks Using Dual Genetic Algorithm

格式：pdf
大小：521.79 KB
文档页数：12

32IEICE TRANS.INF.&SYST.,VOL.E91–D,NO.1JANUARY2008PAPERStructure Learning of Bayesian Networks Using Dual Genetic Algorithm∗Jaehun LEE†,Wooyong CHUNG†,Nonmembers,and Euntai KIM††a),MemberSUMMARY A new structure learning approach for Bayesian networks (BNs)based on dual genetic algorithm(DGA)is proposed in this paper. An individual of the population is represented as a dual chromosome com-posed of two chromosomes.Theﬁrst chromosome represents the ordering among the BN nodes and the second represents the conditional dependen-cies among the ordered BN nodes.It is rigorously shown that there is no BN structure that cannot be encoded by the proposed dual genetic encod-ing and the proposed encoding explores the entire solution space of the BN structures.In contrast with existing GA-based structure learning methods, the proposed method learns not only the topology of the BN nodes,but also the ordering among the BN nodes,thereby,exploring the wider solu-tion space of a given problem than the existing method.The dual genetic operators are closed in the set of the admissible individuals.The proposed method is applied to real-world and benchmark applications,while its ef-fectiveness is demonstrated through computer simulation.key words:Bayesian network,genetic algorithms,structure learning,dual chromosomes1.IntroductionThe Bayesian network(BN)is one of the most popular for-malisms for reasoning under uncertainty in Artiﬁcial Intel-ligence(AI).The BN is a graphical model that denotes joint probabilistic distribution among variables of interest based on the variables’probabilistic relationships.The structure of the BN is represented as a directed acyclic graph(DAG). In a DAG,each node represents a variable that takes on a value over both continuous and discrete data set of domain and is connected with its parent’s nodes.Each arc repre-sents the conditional dependency between the two nodes so connected.With the development of large-scale database systems,the BN has become a popular knowledge represen-tational scheme for probabilistic knowledge in data mining and knowledge discovery[1]–[3].In building the BN,which represents the conditional dependencies in a database of cases,the problem of search-ing for the structure of the BN is both important and diﬃ-cult.A large number of possible DAG structures could be determined from a small number of nodal connections.To Manuscript received July27,2006.Manuscript revised June25,2007.†The authors are with the CILAB,School of Electrical and Electronic Engineering,Yonsei University,134,Shinchon-Dong, Sudaemun-ku,Seoul120–749,Korea.††The author is with the School of Electrical and Electronic En-gineering,Yonsei University,134,Shinchon-Dong,Sudaemun-ku, Seoul120–749,Korea.∗This work was supported by the Ministry of Commerce,In-dustry and Energy of Korea(HISP).a)E-mail:etkim@yonsei.ac.krDOI:10.1093/ietisy/e91–d.1.32solve this problem,several methods have been reported[4]–[10]for the structure learning of the BN.The most popu-lar method for BN structure learning from a database is the K2algorithm[10].The K2algorithm assumes that an order-ing on the variables is given and searches for an appropriate structure heuristically.But this method is heuristic and does not guarantee that an optimal structure will be found.On the other hand,GAs have been successfully applied to various optimization problems in real world applications. They are well suited to the exploration of complex search spaces.As an alternative scheme to K2,the learning meth-ods based on the GAs have been reported[7]–[9],[11],[12]. The GA,however,is not a ready made optimization tool for BN structure learning.The plain GA cannot be applied to the structure learning of BN and there is no general way toﬁnd the optimal structure in the entire DAG space be-cause the plain genetic operations are not closed in the set of the possible BN structures.Thus,in the existing meth-ods,the GAs also restrict the ordering on the variables,in which initially a search is conducted for the solution in the directed graph space,including cyclic and acyclic,and then the cyclic solutions are removed.In this paper,a new structure learning method of the BNs based on a dual genetic algorithm(DGA)is proposed. In the proposed method,a BN structure is represented as paired chromosomes.One represents the ordering among the BN nodes and the other represents conditional depen-dencies among the ordered BN nodes.In contrast with the existing GA-based structure learning methods of the BN[7],the proposed method learns not only the topologies of the BN nodes,but also the ordering among the BN nodes, thereby,exploring the entire solution space of a given prob-lem.The proposed method is somewhat similar to[18]but the contribution of this paper is twofold:(1)It is rigorously shown that the dual chromosome can represent all the possi-ble BN structures,thereby exploring the entire BN structure space and(2)the proposed method uses slightly diﬀerent genetic operators from[18].This paper is organized as follows.In Sect.2,a brief introduction to BNs and GAs is given.In Sect.3,the DGA for structure learning of the BN is proposed and the new genetic operations are introduced.In Sect.4,the proposed method is applied to real-world and benchmark problems:a database of virtual home network systems[13],a database of car diagnosis problems as suggested by Norsys[14],and a database of ALARM networks constructed by Beinlinch et al.[10].Finally,some conclusions are drawn in Sect.5.Copyright c 2008The Institute of Electronics,Information and Communication EngineersLEE et al.:STRUCTURE LEARNING OF BAYESIAN NETWORKS USING DUAL GENETIC ALGORITHM332.Preliminary Fundamentals:Bayesian Networks andGenetic Algorithms 2.1Bayesian NetworkThe Bayesian network and associated schemes constitute a probabilistic framework for reasoning under uncertainty and in recent years have gained popularity in the community of artiﬁcial intelligence.The BN is composed of a network structure and a set of parameters associated with the struc-ture.The structure of the BN is a directed acyclic graph (DAG),in which each node represents a random variable that can take on a ﬁnite set of values and each arc repre-sents the conditional dependency (topology)between the two nodes [15].In this paper,we assume that each node takes only discrete values.To specify the BN completely in conjunction with the DAG,the user must give prior probabilities for all root nodes (nodes with no predecessors)and conditional probabilities for all the other nodes.The joint probability of any particu-lar instantiation of all n variables in the BN can be calculated withP (U )=iP (A i |pa (A i ))(1)where U =A 1,A 2,···,A n represents n nodes of the BN andpa (A i )is the parent set of the variable A i .For example,the probability of the BN shown in Fig.1is computed by:P (U )=P (A 1)P (A 2)P (A 3)P (A 4|A 1,A 2)·P (A 5|A 2,A 3)P (A 6|A 4)P (A 7|A 5)(2)The process of building the BN can be separated into two tasks:structure learning and parameter learning.Struc-ture learning is a search for an appropriate structure for the BN such that the BN accommodates the given set of sam-ples.Parameter learning is computation of the conditional probabilities for the given BN structure such that the output of the BN approximates the distribution of the given set of samples.The most popular parameter learning method is the expectation maximization (EM)algorithm [16].In this paper,the focus is structure learning of the BN and build-ing an appropriate BN structure such that the BN structure accommodates the given set ofsamples.Fig.1An example of a Bayesian network.2.2Genetic AlgorithmsThe genetic algorithm (GA)is the implementation of a bi-ological metaphor.In the algorithm,learning is viewed asa competition among a population of evolving individuals.The ﬁtness,or goodness,of each individual is evaluated and,according to the computed ﬁtness value,it is determined which one will survive in the next generation.Through op-erations analogous to gene transfer in sexual reproduction,a new population of candidate solutions is created [17].The general procedure for GA is summarized as follows.An ini-tial population of individuals called chromosomes is created by random selection and the goodness of each individual is evaluated by a ﬁtness function.Then,a new population of reproduced individuals is selected according to the ﬁt-ness values.In the selection,the individuals with high ﬁt-ness values are more likely to reproduce o ﬀspring than those with low ﬁtness values.Finally,the selected individuals are mated with others and sometimes mutated.If the new pop-ulation includes an individual that produces a satisfactory performance or ﬁtness level,then the algorithm stops and the problem is solved.If not,then the algorithm is repeated until a termination condition is satisﬁed.The pseudo code of a simple genetic algorithm (SGA)is shown below:procedure SGA()initialize(Population);evaluate(Population);While (Not termination-condition)DoMatingPool=reproduce(Population);MutationPool=crossover(MatingPool);Population =mutation(MutationPool);evaluate(Population);end end3.Structure Learning of Bayesian Networks Based onthe Dual Genetic Algorithm In this section,a new approach for structure learning of BNs based on the dual genetic algorithm is proposed.The pro-posed method explores a wider solution space than the ex-isting GA-based structure learning method.3.1The Conventional Method for BN Structure Learning In this subsection,the conventional method that uses the GA for the structure learning of the BN is explained brieﬂy [7].The BN structure with n variables is represented by an n ×n connectivity matrix C =(c i ,j ),wherec i ,j = 1if i is a parent of j0otherwise(3)and each individual of the population is encoded as a chro-mosome,34IEICE TRANS.INF.&SYST.,VOL.E91–D,NO.1JANUARY2008 c1,1c1,2···c1,n c2,1c2,2···c2,n···c n,1c n,2···c n,n(4)With this representation,the plain crossover and mutationoperators would produce illegal BN structures.In the pre-vious method,to overcome this problem,the connectivitymatrix was assumed to be upper triangular and the connec-tivity matrix,⎛⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎝0c1,2c1,3···c1,n−1c1,n00c2,3···c2,n−1c2,n..................000···0c n−1,n000 (00)⎞⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎠(5)was encoded as a chromosome,X=c1,2···c1,n c2,3···c2,n···c n−2,n−1c n−2,n c n−1,n(6) In other words,the ordering among the variables of the BN wasﬁxed and a node A i was allowed to have another node A j as a parent node only if the node A j comes before the node A i in the ordering.This scheme restricts the values of c i,j(i≥j)to0and narrows the search space to the extent that the GA willﬁnd only a suboptimal solution,if theﬁxed ordering of the nodes is wrong.3.2Dual Genetic Algorithm for BN Structure Learning The conventional method has the limitation that the ordering between the nodes is predetermined and the nodal connec-tions are upper triangular.The conventional genetic encod-ing cannot represent all the possible BN structures and the search space was not fully explored to determine theﬁttest structure of BNs.If there is no prior knowledge about the ordering between variables,which is usually the case,the resulting structure will not be satisfactory.This paper describes a proposed new genetic method that can be applied to the structure learning of the BNs.In the proposed method,the connectivity matrix is assumed to be upper triangular,but it is not exactly the same as that of the conventional method.The ordering of the nodes is notﬁxed and it is also learned by the GA.Thus,the entire solution space is searched for theﬁttest structure of the BN.3.2.1EncodingIn order to encode all of the information related to the struc-ture learning of the BN into a chromosome and search the entire solution space for theﬁttest structure,a dual chromo-some is proposed,which is composed of an ordering chro-mosome and a connectivity chromosome:The ordering chro-mosome is integer-coded and denotes the ordering among the BN nodes.The connectivity chromosome is binary-coded and denotes the upper triangular connectivity matrix, which represents the connection among the nodes with re-spect to the ordering chromosome.The ordering chromo-some X o and the connectivity chromosome X c are encoded as follows:X o=x1x2···x nX c=c1,2···c1,n c2,3···c2,n···c n−2,n−1c n−2,n c n−1,n(7) wherex i is an integer and x i∈{1,···,n},x i x j,iff i jC=⎛⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎝0c1,2c1,3···c1,n−1c1,n00c2,3···c2,n−1c2,n..................000···0c n−1,n000 (00)⎞⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎠c i,j=1if x i is a parent of x j0otherwise(8)The ordering chromosome consists of the indices of the vari-ables.If there are n root nodes(nodes without parents)and they have m children nodes,theﬁrst n genes of this chro-mosome are the indices of the root nodes.The next m genes are the indices of nodes which can be the children of the root nodes.This structure is repeated until all of the vari-ables are visited.The connectivity chromosome denotes the connectivity matrix,which deﬁnes the dependency relation among the variables.For the evolution of the connectivity chromosome,the plain GA operators are applied.For the evolution of the ordering chromosome,however,the plain GA operators do not work and some genetic operators used in traveling salesman problem(TSP)are applied toﬁnd the best ordering of the variables[17].In[18],several GA oper-ators used in TSP were applied under the K2algorithm and it was shown that their performances are almost the same.In the proposed method,the GA operators similar to those of [18]are used.The following examples show the basic idea of the suggested dual genetic encoding.The GA operators for the dual genetic encoding will be explained in detail in the subsequent section.Example1(Encoding of the dual chromosome): Consider two BN structures as shown in Fig.2.Each BN is represented by a dual chromosome(X io,X ic),in which i=1,2and the subscripts o and c denote an ordering chromosome and a connectivity chromosome,respectively. These chromosomes are explicitly shown in(9).X1o=126354X1c=110000100010010X2o=543126Fig.2Two BNs(Example1).LEE et al.:STRUCTURE LEARNING OF BAYESIAN NETWORKS USING DUAL GENETIC ALGORITHM35X2c=110001100010011(9)C i and¯C i denote the connectivity matrices,as shown in(10),created by the proposed dual chromosome(X io,X ic)and bythe conventional method[7],respectively.C1=⎛⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎝011000000100000010000001000000000000⎞⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎠,¯C1=⎛⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎝010001001000000100000000000000000010⎞⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎠C2=⎛⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎝011000001100000010000001000001000000⎞⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎠,¯C2=⎛⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎝000001000001010000101000001100000000⎞⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎠(10)The proposed method can explore a much wider solu-tion space than the existing GA-based method because the proposed dual chromosome encoding can represent all the possible structures of the BNs.The subsequent theorems show that there is no BN structure that cannot be encoded by the proposed dual genetic encoding and the proposed en-coding explores the entire solution space of the BN struc-tures.First,we deﬁne two terminologies that will be used in the theorems.The root indicates a node that has no parent nodes and a leaf indicates a node that has no child nodes. Theorem1:Any DAG has at least one root and one leaf.There is no DAG which does not have a root or a leaf.Proof.Consider a DAG with n nodes.If there is no leaf in the DAG,then all nodes in the DAG have at least one child node.So if we select any node in the DAG and tra-verse from the node to one of its child nodes n+1times, then we would encounter the same node at least one time. That means that there is at least one loop in the DAG and this is a contradiction.Therefore,any DAG has at least one leaf.Similarly,if there is no root in the DAG,then all nodes have at least one parent node.If any node in the DAG is selected and movement is in the reverse direction from the node to one of its parent nodes n+1times,then the same node will be encountered at least one time.That means that there is at least one loop in the DAG and this is a contradic-tion.Therefore,any DAG has at least one root. Theorem2:Consider a DAG with n+1nodes.The DAG can be decom-posed as a connection of a root(or a leaf)and a small DAG with n nodes.Proof.Consider the DAG G with n+1nodes.Then,by theorem1,G has at least one root and one leaf.If we remove the root R and the connected arcs from G,then the resulting graph G will have n nodes.Assume that the resulting graph G is not the DAG.Then,there is at least one loop in G . Even if the deleted node R is appended to G and the dis-connected arcs are restored,the resulting graph still has a loop.Since the resulting graph is the original graph G and it has a loop,it is a contradiction.Therefore,G is also the DAG and we can conclude that a DAG with n+1nodes can be decomposed as a connection of a root and a small DAG with n nodes.In the same way,it can be shown that if a leaf L and the connected arcs are removed from G,the resulting graph G becomes the DAG and it can be concluded that a DAG with n+1nodes can be decomposed as a combination of a leaf L and a small DAG with n nodes.Hence,a discussion follows that reveals that there is no BN structure which cannot be encoded by the proposed dual genetic encoding.Theorem3:Any DAG with n nodes can be represented by a certain or-dering among n nodes and an upper triangular connectivity matrix with respect to the given ordering.Proof.Here,mathematical induction is utilized.When the number of nodes is two,the theorem trivially holds.As-sume that x1is a root and x2is a leaf.If the ordering is “12”,the connectivity matrix C=0100for the DAG is upper triangular.Next,assume that this theorem holds when the number of nodes is n and consider a DAG G with n+1 nodes.By theorem2,DAG G with n+1nodes can be de-composed as a connection of a root(or a leaf)and a small DAG with nodes.If G is decomposed as a connection of a root and a small DAG G ,the root and the connected arcs can be removed.Then,by the assumption,we canﬁnd a proper ordering O among n variables and upper triangular connectivity matrix C with respect to the ordering O.O=a1a2···a nC=⎛⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎝0c1,2c1,3···c1,n−1c1,n00c2,3···c2,n−1c2,n..................000···0c n−1,n000 (00)⎞⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎠(11)wherea x is an integer and a x∈{1,···,n+1}f or x=1,···,n+1a j a k iff j kc i,j=1if a i is a parent of a j0otherwise(12)which fully represents G .If the deleted root is denoted as a n+1and the ordering among the n+1variables are selected asO =a n+1a1a2···a n(13) then the original DAG with n+1nodes can be represented by an upper triangular connectivity matrix,36IEICE TRANS.INF.&SYST.,VOL.E91–D,NO.1JANUARY 2008C =⎛⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎝0c n +1,1c n +1,2c n +1,3···c n +1,n −1c n +1,n 00c 1,2c 1,3···c 1,n −1c 1,n 000c 2,3···c 2,n −1c 2,n .....................0000···0c n −1,n 000 00⎞⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎠=0C120C(14)with respect to the ordering O =a n +1a 1a 2···a n wherec i ,j =1if a i is a parent of a j0otherwiseand C is n ×n upper triangular matrixand C12is 1×n matrix (15)Similarly,if G is decomposed as a connection of a leaf and a small DAG G ,the leaf and the connected arcs can be removed.Then,by the assumption,a proper ordering O among n variables and upper triangular connectivity matrix C of (11)can be found,which fully represents the small DAG G .If the deleted leaf is denoted as a n +1and the or-dering among the n +1variables are selected asO=a 1a 2···a n a n +1(16)then the original DAG with n +1nodes can be represented by an upper triangular connectivity matrix,C =⎛⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎝0c 1,2c 1,3c 1,4...c 1,n c 1,n +100c 2,3c 2,4...c 2,n c 2,n +1000c 3,4...c 3,n c 3,n +1.....................0000...0c n ,n +10000 (00)⎞⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎠=C C1200 (17)wherec i ,j =1if a i is a parent of a j0otherwiseand C is n ×n upper triangular matrixand C12is n ×1matrix(18)This means that if the property is true for n ,the property isalso true for n +1and the proof is completed. 3.2.2CrossoverConsider the genetic operations (crossover and mutation)for the dual chromosome.First,let us consider the crossover.In the case of connectivity matrix,any upper triangular ma-trix is valid as a BN structure.Thus,the plain crossover is enough and is closed in the domain of the connectivity chromosomes as in [7].However,in the case of the ordering chromosome,the crossover is not straightforward.In orderto explain the genetic crossover for the ordering chromo-somes,let X o and Y o be two n dimensional ordering chro-mosomes represented byX o =x 1x 2···x n Y o =y 1y 2···y n(19)The proposed crossover generates a random number r from a uniform distribution from 1to n and creates two new chro-mosomes X o and Yo according to following equations.X o =x 1x 2 (x)n Y o =y 1y 2···y n(20)x i = x i if i <ry αi −r otherwise y i =y i if i <r x βi −r otherwise(21)whereα0,α1,···,αn −r ∈{1,2,···,n }α0<α1<···<αn −ry αj x 1,x 2,···,x r −1for j =0,1,2,···,n −r β0,β1,···,βn −r ∈{1,2,···,n }β0<β1<···<βn −rx βj y 1,y 2,···,y r −1for j =0,1,2,···,n −r(22)Example 2(Crossover for ordering chromosome):Consider the two BNs in Example 1.Assume that the crossover operation is applied to the ordering chromosomes at the point between the second and the third genes,which means r =3and n =6in this example.The o ﬀspring start withX 1o =12xxxx X 2o =54xxxx(23)Since X1o contains “1”and “2”,the two digits in X 2o are deleted.Then the remaining sub-chromosome of X 2o is “5436.”The concatenation of the two parts yields an o ﬀ-spring ordering chromosome X1o =125436.In the same way,“54”and “1263”are concatenated and the another o ﬀ-spring ordering chromosome becomes X2o =541263.X1o =125436X 1c =110000100010010X 2o =541263X 2c =110001100010011(24)C 1=⎛⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎝011000000100000010000001000000000000⎞⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎠,C 2=⎛⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎝01100000110000001000000100000100000⎞⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎠(25)If the connectivity chromosomes are the same as the parents,then the o ﬀspring BNs are depicted as in Fig.3.LEE et al.:STRUCTURE LEARNING OF BAYESIAN NETWORKS USING DUAL GENETIC ALGORITHM37Fig.3Oﬀspring BNs after crossover(Example2).The following shows the pseudo code of crossover forthe ordering chromosome:procedure OrderCrossover(Population)Size=crossover_rate*Population_Size;While(Size>0)Doselect p1and p2from Population;select the crossover point value randomlyfrom1to chromosome length;generate two children chromosomes c1,c2;i=0;j=0;While(i<crossover point)Doput ith gene of p1into that of c1;put ith gene of p2into that of c2;i=i+1;endWhile(i<chromosome length)DoWhile(j<chromosome length)DoIf jth gene of p2is not in c1Thenput jth gene of p2into ith gene ofc1;i=i+1;Elsej=j+1;endendi=(crossover point);j=0;While(i<chromosome length)DoWhile(j<chromosome length)DoIf jth gene of p1is not in c2Thenput jth gene of p1into ith gene ofc2;i=i+1;Elsej=j+1;endendSize=Size-2;chromosome[p1]=chromosome[c1];chromosome[p2]=chromosome[c2];endend(a)(b)Fig.4Two BNs before and after mutation(Example3).3.2.3MutationFor the connectivity chromosome,the plain mutation pro-duces only the upper triangular matrix as in case of thecrossover operation.Thus,the plain mutation is enough andis closed in the domain of the connectivity chromosomes asin[7].The ordering chromosome is not the case.The fol-lowing discussion explains the genetic mutation for the or-dering chromosome.Let X o be the n dimensional orderingchromosome,X o=x1x2···x n(26)The proposed mutation operator generates a random numberr1and r2from a uniform distribution from1to n and createsthe new chromosomes X o according to following equations:X o=x 1x 2···x n(27)x i=⎧⎪⎪⎪⎨⎪⎪⎪⎩x r2if i=r1x r1else if i=r2x i otherwise(28)Example3(Mutation for ordering chromosome):Consider a BN structure with three variables as shown inFig.4(a).Using the proposed dual genetic encoding,the orderingand the connectivity chromosomes are represented as:X o=123X c=110(29)respectively,and the connectivity matrix is as follows.C=⎛⎜⎜⎜⎜⎜⎜⎜⎝011000000⎞⎟⎟⎟⎟⎟⎟⎟⎠(30)Suppose that theﬁrst and the second genes of the orderingchromosome are exchanged,which means r1=1,r2=2,and n=3in this example,and the connectivity chromosomedoes not change.The resulting dual chromosome and theconnectivity matrix become:X o=213X c=110(31)C =⎛⎜⎜⎜⎜⎜⎜⎜⎝011000000⎞⎟⎟⎟⎟⎟⎟⎟⎠(32)Fig.4(b)depicts the mutated BN.38IEICE TRANS.INF.&SYST.,VOL.E91–D,NO.1JANUARY2008The following shows the pseudo code of mutation op-eration for the ordering chromosome:procedure OrderMutation(Population)Size=mutation_rate*Population_Size;While(Size>0)Doselect a chromosome from Populationrandomly;select two mutation point values i,jrandomly from1to chromosome length;exchange ith and jth gene of thechromosome;Size=Size-1;endend4.SimulationIn this section,the proposed method is applied to three real-world problems and the validity of this method is demon-strated through computer simulation.In all the simulations, we restrict the maximum number of parents of each node toﬁve.The restriction is not necessary but we place it for simple implementation.Without the restrictions,the num-ber of possible conﬁgurations would increase exponentially with the number of parents[21].It is a trade oﬀbetween the performance and the computational cost.4.1Home Network SystemIn this section,the proposed method is applied to the home network system.The home network system is a typical test bed of the ubiquitous computing and sensor network,while it is expected to upgrade the quality of living over approx-imately the next decade.The implementation of context-aware computing is the key issue in the home network and has received attention from engineers and scientists. Context-aware computing is jargon coined by computer sci-entists and it is aimed at1.gathering information about the users from various sen-sors distributed in a smart home,2.recognizing the intention of the users,and3.providing them with human friendly services.In context-aware computing,it is assumed that1.the home appliances and devices are equipped withwired/wireless sensors,2.they gather information about the circumstances underwhich they operate,3.they presume the intention or action of the users,and4.they react according to the intention of the users. Literature provides that the contexts of user activities can be presumed from the state of the environment[19].How-ever,context-awareness is not fully understood and the tools and techniques for developing context-awareapplicationsFig.5An example of the BN structure for a Home network system. are still in their infancy.BNs are one of the possible tools for the context-aware computing.In this example,the proposed method is applied and a BN is developed that presumes the intention or action of a single user,who lives in the home network system.Figure5shows the example of BN struc-ture of the context-aware system for the home network.A web-based virtual action simulator was developed in FLASH and a database of672cases for a context-aware sys-tem was built,for the purpose of training the BN[13].Forty two random variables are used to implement the context-awareness of the BN.Twenty one variables represent the state of the home appliances such as the TV,lights in the living room,the refrigerator,etc.The other twenty one vari-ables represent the activities of a single user,for example whether he/she is studying,sleeping,or ing the proposed method,the Bayesian network is trained such that the action of the user is presumed from the measurements of the sensors distributed in the context-aware home.4.2Car Diagnosis ProblemsThe car diagnosis problem introduced by Norsys is a simple example of belief network.The reason why a car does not move is presumed,based on spark plugs,headlights,main fuse,etc[14].Eighteen nodes are used in this BN and all nodes of the network take discrete values.Some of them can take on three discrete states and the others can take on two states.A database of two thousand cases is utilized to train the BN.The database was generated from Netica tool[14]. Figure6shows the structure of the car diagnosis problem depicted by Netica from which the sample cases were col-lected.Note that,Fig.6depicts the desired BN structure and the goal of the structure learning for BN is to obtain the structures which are close to this desired one.4.3ALARM NetworkALARM(A Logical Alarm Reduction Mechanism)is a medical diagnostic system for patient monitoring.It is a complex belief network with eight diagnoses,sixteenﬁnd-ings,and thirteen intermediate variables[20].A database of two thousand cases is utilized to train the BN.As in the previous example,the database is generated from Net-ica tool[14].Figure7shows the structure of the ALARM network depicted by Netica from which the sample cases are collected.Note that,Fig.10depicts the desired BN structure。

华为MateBook X Pro14 使用指南说明书

Research on Hierarchical Interactive Teaching Model Based on Naive Bayesian ClassificationDongyan FanInformation faculty, Business College of Shanxi University, Taiyuan 030031, ChinaAbstract—The purpose of this research is improving the current inject classroom teaching mode that ignores individual differences and inefficiency of students. By studying classification algorithm in data mining and applying the classification method based on Naive Bayes algorithm, we designed and implemented scientific classification of students, and draw lessons from stratified and interactive teaching mode, so as to builded a new effective teaching mode. The results show that through scientific classification of students, real-time hierarchical interaction teaching effectively stimulate students' interest in learning, improve cooperation ability, and improve classroom teaching efficiency.Keywords—Naive Bayesian; student classification; hierarchical interactive; teaching modelI.I NTRODUCTIONUnder the background of big data era, the current teaching mode is not adapt to the cultivation of innovative talents, there are many problems, such as low efficiency of classroom, teachers' manipulation of teaching process, ignore the individual differences of students in knowledge transfer ability. Therefore, this study aimed at these problems, by studying classification algorithm in data mining and applying the classification method based on Naive Bayes algorithm, we design and implement scientific classification of students, and draw lessons from stratified and interactive teaching mode, so as to build a new effective teaching mode. The mode enable students to learn efficiently, so as to adapt to the trend of rapid development of new technology and cultivate innovative talents.II.R ESEARCH M ETHODThe research and practice of the hierarchical interactive teaching model based on the Naive Bayesian classification is based on the classification of students' differences. So there are two major tasks need to do: the approaches to the students' difference measurement and grouping and the design of hierarchical interactive teaching framework. Its method flow is shown in Figure I.FIGURE I. RESEARCH METHOD FLOWFirst of all, based on the samples, the naive Bayes algorithm according to the student's attribute value is used to test the students' differences. Then, according to the results to make a scientific difference classification to achieve effective grouping for students. At the same time, the design of the hierarchical interactive teaching framework is carried out by the two subjects (the student is the main body, the teacher is the leading part). Finally, the teaching effect is evaluated and analyzed.III.S TUDENT C LASSIFICATION D ESIGN B ASED ON N AIVEB AYESIANA.Naive Bayesian Theoretical PrincipleAt present, there are many kinds of algorithms in data mining, such as based on Bayes algorithm, decision tree algorithm, neural network algorithm, rough set algorithm, genetic algorithm, support vector machine algorithm and so on. In the practical application of many classification algorithms, the most widely used algorithm is Naive Bayesian algorithm model. Naive Bayes is a simple and effective classification model.From Bayes’ theorem recall that:()()()||P A B P BP B AP A= (1)Equation (1): P(A) and P(B) separate representation the probability of occurrenceof events A andevents B.()|P A B indicates the probability of occurrence of event A under the premise that event B occurs. ()|P A B is a priori probability, and its value is often easily obtained.()|P B A indicates the probability of occurrence of event B under the premise that event A occurs. ()|P B A is a posteriori probability, and its value is the result of the solution of the Bayesian formula.The classifier structure diagram based on the naive Bayes algorithm is shown in Figure II. It’s leaf node Am represents the m attribute, and the root node C represents the category. Suppose {},,D C A S=are training samples, it includes the studentcategory {}12,,iC C C C= and the student attribute {}12,,mA A A A= .Suppose {}12,,nS S S S= represents acollection of classified students, in whichnS represents nthstudent. Suppose {}12,,k mX a a a= is a student to be classified,International Conference on Computer Science, Electronics and Communication Engineering (CSECE 2018)in which each m a represents an attribute eigenvalue of the pending item k X .FIGURE II. THE CLASSIFIER STRUCTURE DIAGRAMB. Design the Individualized Attributes of StudentsThe student classification method based on the naive Bayes algorithm is used the information of the past students as the sample set , which is used to construct the naive Bayes classifier.Students are classified according to the information of the students' attributes. The students divided into the same category are not simply using the score as criterion of evaluation. Its are classified by comprehensive evaluation after combination of other attributes.The difference classification based on the naive Bayes algorithm is select the individual attributes of the students as shown in Figure III. The students which 8 attribute values similar in the two dimensions (character and learning style) are put into one category, while the 12 attributes values of the three dimensions of personal basic situation, learning interest and cognitive ability are different. The purpose of the classification is to carry out differential teaching to implicit dynamic stratification and heterogeneous cooperation for students'cognitive ability, learning interest and basic information.FIGURE III. INDIVIDUALIZED ATTRIBUTES OF STUDENTSC. Student Classification Design Based on Naive Bayesian The process based on the naive Bayes classification is shown in Figure IV.FIGURE IV. STUDENT CLASSIFICATION CYCLE FLOW CHARTBASED ON NAIVE BAYES ALGORITHM1)()i P C is set to indicate the frequency of the occurrence of the student category i C in the training sample concentration, that is the category probability. For sample data sets, there are different levels of students in each category, which avoids the discrimination of students.()()i i P C Count C n=　(2)The function ()i Count C represents the number of students belonging to category i which is in the entire student sample collection of S .n represents the total number of the entire student sample collection of S .2)()|j j i P A C a = is set to represent the conditional probability of each characteristic attribute value of the student in the category.()()()|i C j j j j i i P A C Count A a a Count C ===(3)j j A a =indicates that the value of the j attribute is j a .Thefunction ()i C j j Count A a =represents the number of students which the attribute name is j A and attribute value is j a in the i student category.3) ()|k i P X C is set to represent the conditional probability of the students k X to be classified in the student category i C , m represents the number of attributes that describe student differences.()()1||mk i j j i j P X C P A C a ===∏ (4)4) ()j j P A a = is set to represent the probability of the student's attribute j A when the value is j a . ()()j j j j P A Count A a a n===　(5)The function ()j j Count A a = indicates the number when the value of attribute j is j a .5) ()k P X is set to indicate the probability that the student k X should be classified in the training sample concentration. ()()1mk j j j P X P A a ===∏ (6)6) ()|i k P C X is set to represent the conditional probability that the student k X should be classified to category i . ()()()()||k i i i k k P X C P C P C X P X =(7)7) ()max |k P C X is set to represent the maximum category probability of the student k X which should be classified to the student category .()()()(){}max 12|max |,|,,|k k k i k P C X P C X P C X P C X = (8) max C indicates the maximum category of conditionalprobability which is obtained by (8).Finally, (8) is used to calculate the maximum category probability of the students to be classified in the students category. That is the category of the students to be classified. At this point, one classification ends.IV. T HE D ESIGN OF THE H IERARCHICAL I NTERACTIVET EACHING F RAMEWORK The hierarchical interactive teaching model is an independent, inquiring and cooperative teaching model based on the classification of the naive Bayes algorithm. This model breaks the original classroom structure, and takes the interaction of teachers and students as the carrier, and also group autonomy, and let the students as the subject of the class. This model is guided by the task of the problem, and it is based on the students' self-study, and it aims at the completion of the task of the group. This model creates an ecological chain class based on group mutual learning to solve problems. It pays attention to the state of learning and the quality of life for every student. The design of the hierarchical interactive teaching model framework is shown in Figure V.FIGURE V. THE HIERARCHICAL INTERACTIVE TEACHING MODELFRAMEWORKThe four layers of the hierarchical interactive teaching model are closely related to each other, and support each other dynamically with the spiral. The five segments drive each other to form a whole, interlace and connect with each other. This teaching mode makes the classroom an active area for teachers and students to resonate with their ideology and to show their personality together.V.A NALYSIS OF T EACHING E FFECTIn this paper, the teaching effect is analyzed from two aspects by using the method of questionnaire and comparative experiment. First, the experimental class's comparative analysis before and after the experiment is carried out. Then, a comparative analysis between the experimental class and the contrast class is carried out.The comparative data of the experimental class before and after the experiment are shown in Figure VI. From Figure VI, it can be seen that 85.72% of the students have An attitude of approval towards the application of the hierarchical interactive teaching model based on the naive Bayes algorithm in the teaching. There are 70.13% of the students satisfied with the improved teaching effect. At the same time, it can be seen that the students' interest in learning and the ability to communicate and cooperate have improved obviously.FIGURE VI. THE COMPARATIVE DATA OF THE EXPERIMENTALCLASS BEFORE AND AFTER THE EXPERIMENT The comparison between the experimental class and the contrast class is shown in Figure VII. From Figure VII, we can see that students' satisfaction degree, teaching effect satisfaction and group learning atmosphere based on Naive Bayes algorithm classification are higher than those of the contrast class. At the same time, it can be seen that the students' interest in learning and the ability to communicate and cooperate have also been improved.FIGURE VII. THE COMPARISON BETWEEN THE EXPERIMENTALCLASS AND THE CONTRAST CLASSVI.C ONCLUSIONThe comprehensive analysis shows that, in the implementation of the hierarchical interactive teaching model based on the naive Bayes algorithm, the new teaching mode was accepted by the students , it was welcomed by the students. The new teaching mode can improve the ability of learning interest and collaboration of students. It has a very good teaching effect. Experiments show that the classification algorithm based on Naive Bayes has better feasibility and effectiveness in solving student classification problem.However, due to the limited personal time and ability, there are still some shortcomings in the study. In order to better achieve hierarchical interaction teaching mode based on Naive Bayes algorithm and improve teaching effect, we still need to further improve the limitation of applying naive Bayes algorithm, that is, suppose the attributes of students are independent.A CKNOWLEDGMENTThis work was supported by “Research and construction of the practice teaching system of information specialty(J2016138, The major project of teaching reform research in Shanxi Education Department)” and “The optimization and the platform construction of the practice teaching system of information specialty (SYJ201509, The major project of the research on teaching reform Business College of Shanxi University)”. Our special thanks are due to Prof. Ma Shangcai, for his helpful discussion with preparing the manuscript.R EFERENCES[1]Jonathan Rauh. Problems in Identifying Public and Private Organizations:A Demonstration Using a Simple Naive Bayesian Classification[J]. PublicOrganization Review,2015,15(1).[2]SangitaB, P., Deshmukh, S.R.. Use of Support Vector Machine, decisiontree and Naive Bayesian techniques for wind speed classification[P].Power and Energy Systems (ICPS), 2011 International Conference on,2011.[3]Yan Dong. Hierarchical interactive teaching mode and its practice andexploration of mathematics teaching in Senior High School [D].Southwest University,2016.[4]Chen Zhiqiang. Hierarchical interactive teaching mode and its practiceand exploration of mathematics teaching in Senior High School [D].Henan University,2016.[5]S. Mukherjee and N. Sharma. Intrusion detection using naïve Bayesclassifier with feature reduction[J].Procedia Technology,vol. 4, pp. 119–128, 2012.[6]L. Jiang, Z. Cai, D. Wang, and H. Zhang. Improving tree augmented naiveBayes for class probability estimation[J]. Knowledge-Based Systems, vol.26, pp. 239–245, 2012.[7]Sharma RK, Sugumaran V, Kumar H, Amarnath M. A comparative studyof naïve Bayes classifier and Bayes net classifier for fault diagnosis of roller bearing using sound signal[J].International Journal of Decision Support Systems. 2015 Jan 1; 1(1):115-29.[8]Hamse Y Mussa, John BO Mitchell,Robert C Glen.Full “Laplacianised”posterior naïve Bayesian algorithm[J]. Journal of Cheminformatics. 2013 5:37.[9]K. Magesh Kumar, P. Valarmathie. Domain and Intelligence BasedMultimedia Question Answering System[J]. International Journal of Evaluation and Research in Education, Vol. 5, No. 3, September 2016 : 227 – 234.[10][11]Zhijun Wang1, Li Chen, Terry Anderson. A Framework forInteraction and Cognitive Engagement in Connectivist Learning Contexts[J]. International Review of Research in Open and DistanceLearning, Vol. 15,No.2, Apr 2014:121-141.。

基于进化MCMC的DBN学习算法

基于进化MCMC的DBN学习算法郭鹏;李乃祥;刘同海【期刊名称】《计算机工程》【年(卷),期】2011(037)010【摘要】Dynamic Bayesian Network(DBN) learning with evolutionary MCMC algorithm is presented.Parameter learning with absent data is done with EM algorithm.In structure learning, multiple Bayesian network chromosomes are generated as candidates and are processed with mutation and crossover.The structures are learned with MCMC function which is obtained with temperatures and Bayesian InformationCriterion(BIC) scores of corresponding Bayesian networks.In each generation, the Bayesian network with the maximal BIC score is selected as the result of the stracture learning.Experimental results proves the stability of the method's performance.%提出利用进化MCMC算法进行动态贝叶斯网络(DBN)学习的方法.在数据缺省情况下利用EM算法进行贝叶斯网络参数学习,结构学习部分生成多条备选的贝叶斯网络染色体,对染色体进行变异操作和交叉操作,在遗传操作中根据温度参数和贝叶斯网络及贝叶斯信息准则来构造MCMC函数,并利用MCMC函数进行贝叶斯网络学习.每一代进化后,将贝叶斯信息评分最大的贝叶斯网络作为结构学习的结果.实验结果验证了该方法性能的稳定性.【总页数】3页(P143-145)【作者】郭鹏;李乃祥;刘同海【作者单位】天津大学计算机科学与技术学院,天津,300072;天津农学院计算机科学与信息工程系,天津,300384;天津农学院计算机科学与信息工程系,天津,300384;天津农学院计算机科学与信息工程系,天津,300384【正文语种】中文【中图分类】TP309【相关文献】1.基于蚁群优化的DBN转移网络结构学习算法 [J], 胡仁兵;翼俊忠;张鸿勋;刘椿年2.一种基于EM和分类损失的半监督主动DBN学习算法 [J], 赵悦;穆志纯;李霞丽;潘秀琴3.基于深度学习DBN算法的高速公路危险变道判别模型 [J], 赵玮;徐良杰;冉斌;汪济洲4.基于改进遗传算法的DBN结构自适应学习算法 [J], 孙美婷;刘彬5.基于Kriging和MCMC的结构可靠性主动学习算法 [J], 张灏岩;毕秋实;李勃;郭广勇因版权原因，仅展示原文概要，查看原文内容请购买。

贝叶斯正则化Bayesian BP Regulation

APPLICATION OF BAYESIAN REGULARIZED BP NEURALNETWORK MODEL FOR TREND ANALYSIS,ACIDITY ANDCHEMICAL COMPOSITION OF PRECIPITATION IN NORTHCAROLINAMIN XU1,GUANGMING ZENG1,2,∗,XINYI XU1,GUOHE HUANG1,2,RU JIANG1and WEI SUN21College of Environmental Science and Engineering,Hunan University,Changsha410082,China;2Sino-Canadian Center of Energy and Environment Research,University of Regina,Regina,SK,S4S0A2,Canada(∗author for correspondence,e-mail:zgming@,ykxumin@,Tel.:86–731-882-2754,Fax:86-731-882-3701)(Received1August2005;accepted12December2005)Abstract.Bayesian regularized back-propagation neural network(BRBPNN)was developed for trend analysis,acidity and chemical composition of precipitation in North Carolina using precipitation chemistry data in NADP.This study included two BRBPNN application problems:(i)the relationship between precipitation acidity(pH)and other ions(NH+4,NO−3,SO2−4,Ca2+,Mg2+,K+,Cl−and Na+) was performed by BRBPNN and the achieved optimal network structure was8-15-1.Then the relative importance index,obtained through the sum of square weights between each input neuron and the hidden layer of BRBPNN(8-15-1),indicated that the ions’contribution to the acidity declined in the order of NH+4>SO2−4>NO−3;and(ii)investigations were also carried out using BRBPNN with respect to temporal variation of monthly mean NH+4,SO2−4and NO3−concentrations and their optimal architectures for the1990–2003data were4-6-1,4-6-1and4-4-1,respectively.All the estimated results of the optimal BRBPNNs showed that the relationship between the acidity and other ions or that between NH+4,SO2−4,NO−3concentrations with regard to precipitation amount and time variable was obviously nonlinear,since in contrast to multiple linear regression(MLR),BRBPNN was clearly better with less error in prediction and of higher correlation coefﬁcients.Meanwhile,results also exhibited that BRBPNN was of automated regularization parameter selection capability and may ensure the excellentﬁtting and robustness.Thus,this study laid the foundation for the application of BRBPNN in the analysis of acid precipitation.Keywords:Bayesian regularized back-propagation neural network(BRBPNN),precipitation,chem-ical composition,temporal trend,the sum of square weights1.IntroductionCharacterization of the chemical nature of precipitation is currently under con-siderable investigations due to the increasing concern about man’s atmospheric inputs of substances and their effects on land,surface waters,vegetation and mate-rials.Particularly,temporal trend and chemical composition has been the subject of extensive research in North America,Canada and Japan in the past30years(Zeng Water,Air,and Soil Pollution(2006)172:167–184DOI:10.1007/s11270-005-9068-8C Springer2006168MIN XU ET AL.and Flopke,1989;Khawaja and Husain,1990;Lim et al.,1991;Sinya et al.,2002; Grimm and Lynch,2005).Linear regression(LR)methods such as multiple linear regression(MLR)have been widely used to develop the model of temporal trend and chemical composition analysis in precipitation(Sinya et al.,2002;George,2003;Aherne and Farrell,2002; Christopher et al.,2005;Migliavacca et al.,2004;Yasushi et al.,2001).However, LR is an“ill-posed”problem in statistics and sometimes results in the instability of the models when trained with noisy data,besides the requirement of subjective decisions to be made on the part of the investigator as to the likely functional (e.g.nonlinear)relationships among variables(Burden and Winkler,1999;2000). On the other hand,recently,there has been increasing interest in estimating the uncertainties and nonlinearities associated with impact prediction of atmospheric deposition(Page et al.,2004).Besides precipitation amount,human activities,such as local and regional land cover and emission sources,the actual role each plays in determining the concentration at a given location is unknown and uncertain(Grimm and Lynch,2005).Therefore,it is of much signiﬁcance that the model of temporal variation and precipitation chemistry is efﬁcient,gives unambiguous models and doesn’t depend upon any subjective decisions about the relationships among ionic concentrations.In this study,we propose a Bayesian regularized back-propagation neural net-work(BRBPNN)to overcome MLR’s deﬁciencies and investigate nonlinearity and uncertainty in acid precipitation.The network is trained through Bayesian reg-ularized methods,a mathematical process which converts the regression into a well-behaved,“well-posed”problem.In contrast to MLR and traditional neural networks(NNs),BRBPNN has more performance when the relationship between variables is nonlinear(Sovan et al.,1996;Archontoula et al.,2003)and more ex-cellent generalizations because BRBPNN is of automated regularization parameter selection capability to obtain the optimal network architecture of posterior distri-bution and avoid over-ﬁtting problem(Burden and Winkler,1999;2000).Thus,the main purpose of our paper is to apply BRBPNN method to modeling the nonlinear relationship between the acidity and chemical compositions of precipitation and improve the accuracy of monthly ionic concentration model used to provide pre-cipitation estimates.And both of them are helpful to predict precipitation variables and interpret mechanisms of acid precipitation.2.Theories and Methods2.1.T HEORY OF BAYESIAN REGULARIZED BP NEURAL NETWORK Traditional NN modeling was based on back-propagation that was created by gen-eralizing the Widrow-Hoff learning rule to multiple-layer networks and nonlinear differentiable transfer monly,a BPNN comprises three types ofAPPLICATION OF BAYESIAN REGULARIZED BP NEURAL NETWORK MODEL 169Hidden L ayerInput a 1=tansig(IW 1,1p +b 1 ) Output L ayer a 2=pu relin(LW 2,1a 1+b 2)Figure 1.Structure of the neural network used.R =number of elements in input vector;S =number of hidden neurons;p is a vector of R input elements.The network input to the transfer function tansig is n 1and the sum of the bias b 1.The network output to the transfer function purelin is n 2and the sum of the bias b 2.IW 1,1is input weight matrix and LW 2,1is layer weight matrix.a 1is the output of the hidden layer by tansig transfer function and y (a 2)is the network output.neuron layers:an input layer,one or several hidden layers and an output layer comprising one or several neurons.In most cases only one hidden layer is used (Figure 1)to limit the calculation time.Although BPNNs with biases,a sigmoid layer and a linear output layer are capable of approximating any function with a ﬁnite number of discontinuities (The MathWorks,),we se-lect tansig and pureline transfer functions of MATLAB to improve the efﬁciency (Burden and Winkler,1999;2000).Bayesian methods are the optimal methods for solving learning problems of neural network,which can automatically select the regularization parameters and integrates the properties of high convergent rate of traditional BPNN and prior information of Bayesian statistics (Burden and Winkler,1999;2000;Jouko and Aki,2001;Sun et al.,2005).To improve generalization ability of the network,the regularized training objective function F is denoted as:F =αE w +βE D (1)where E W is the sum of squared network weights,E D is the sum of squared net-work errors,αand βare objective function parameters (regularization parameters).Setting the correct values for the objective parameters is the main problem with im-plementing regularization and their relative size dictates the emphasis for training.Specially,in this study,the mean square errors (MSE)are chosen as a measure of the network training approximation.Set a desired neural network with a training data set D ={(p 1,t 1),(p 2,t 2),···,(p i ,t i ),···,(p n ,t n )},where p i is an input to the network,and t i is the corresponding target output.As each input is applied to the network,the network output is compared to the target.And the error is calculated as the difference between the target output and the network output.Then170MIN XU ET AL.we want to minimize the average of the sum of these errors(namely,MSE)through the iterative network training.MSE=1nni=1e(i)2=1nni=1(t(i)−a(i))2(2)where n is the number of sample set,e(i)is the error and a(i)is the network output.In the Bayesian framework the weights of the network are considered random variables and the posterior distribution of the weights can be updated according to Bayes’rule:P(w|D,α,β,M)=P(D|w,β,M)P(w|α,M)P(D|α,β,M)(3)where M is the particular neural network model used and w is the vector of net-work weights.P(w|α,M)is the prior density,which represents our knowledge of the weights before any data are collected.P(D|w,β,M)is the likelihood func-tion,which is the probability of the data occurring,given that the weights w. P(D|α,β,M)is a normalization factor,which guarantees that the total probability is1.Thus,we havePosterior=Likelihood×PriorEvidence(4)Likelyhood:A network with a speciﬁed architecture M and w can be viewed as making predictions about the target output as a function of input data in accordance with the probability distribution:P(D|w,β,M)=exp(−βE D)Z D(β)(5)where Z D(β)is the normalization factor:Z D(β)=(π/β)n/2(6) Prior:A prior probability is assigned to alternative network connection strengths w,written in the form:P(w|α,M)=exp(−αE w)Z w(α)(7)where Z w(α)is the normalization factor:Z w(α)=(π/α)K/2(8)APPLICATION OF BAYESIAN REGULARIZED BP NEURAL NETWORK MODEL171 Finally,the posterior probability of the network connections w is:P(w|D,α,β,M)=exp(−(αE w+βE D))Z F(α,β)=exp(−F(w))Z F(α,β)(9)Setting regularization parametersαandβ.The regularization parameters αandβdetermine the complexity of the model M.Now we apply Bayes’rule to optimize the objective function parametersαandβ.Here,we haveP(α,β|D,M)=P(D|α,β,M)P(α,β|M)P(D|M)(10)If we assume a uniform prior density P(α,β|M)for the regularization parame-tersαandβ,then maximizing the posterior is achieved by maximizing the likelihood function P(D|α,β,M).We also notice that the likelihood function P(D|α,β,M) on the right side of Equation(10)is the normalization factor for Equation(3). According to Foresee and Hagan(1997),we have:P(D|α,β,M)=P(D|w,β,M)P(w|α,M)P(w|D,α,β,M)=Z F(α,β)Z w(α)Z D(β)(11)In Equation(11),the only unknown part is Z F(α,β).Since the objective function has the shape of a quadratic in a small area surrounding the minimum point,we can expand F(w)around the minimum point of the posterior density w MP,where the gradient is zero.Solving for the normalizing constant yields:Z F(α,β)=(2π)K/2det−1/2(H)exp(−F(w MP))(12) where H is the Hessian matrix of the objective function.H=β∇2E D+α∇2E w(13) Substituting Equation(12)into Equation(11),we canﬁnd the optimal values for αandβ,at the minimum point by taking the derivative with respect to each of the log of Equation(11)and set them equal to zero,we have:αMP=γ2E w(w MP)andβMP=n−γ2E D(w MP)(14)whereγ=K−αMP trace−1(H MP)is the number of effective parameters;n is the number of sample set and K is the total number of parameters in the network. The number of effective parameters is a measure of how many parameters in the network are effectively used in reducing the error function.It can range from zero to K.After training,we need to do the following checks:(i)Ifγis very close to172MIN XU ET AL.K,the network may be not large enough to properly represent the true function.In this case,we simply add more hidden neurons and retrain the network to make a larger network.If the larger network has the sameﬁnalγ,then the smaller network was large enough;and(ii)if the network is sufﬁciently large,then a second larger network will achieve comparable values forγ.The Bayesian optimization of the regularization parameters requires the com-putation of the Hessian matrix of the objective function F(w)at the minimum point w MP.To overcome this problem,the Gauss-Newton approximation to Hessian ma-trix has been proposed by Foresee and Hagan(1997).Here are the steps required for Bayesian optimization of the regularization parameters:(i)Initializeα,βand the weights.After theﬁrst training step,the objective function parameters will recover from the initial setting;(ii)Take one step of the Levenberg-Marquardt algorithm to minimize the objective function F(w);(iii)Computeγusing the Gauss-Newton approximation to Hessian matrix in the Levenberg-Marquardt training algorithm; (iv)Compute new estimates for the objective function parametersαandβ;And(v) now iterate steps ii through iv until convergence.2.2.W EIGHT CALCULATION OF THE NETWORKGenerally,one of the difﬁcult research topics of BRBPNN model is how to obtain effective information from a neural network.To a certain extent,the network weight and bias can reﬂect the complex nonlinear relationships between input variables and output variable.When the output layer only involves one neuron,the inﬂuences of input variables on output variable are directly presented in the inﬂuences of input parameters upon the network.Simultaneously,in case of the connection along the paths from the input layer to the hidden layer and along the paths from the hidden layer to the output layer,it is attempted to study how input variables react to the hidden layer,which can be considered as the impacts of input variables on output variable.According to Joseph et al.(2003),the relative importance of individual input variable upon output variable can be expressed as:I=Sj=1ABS(w ji)Numi=1Sj=1ABS(w ji)(15)where w ji is the connection weight from i input neuron to j hidden neuron,ABS is an absolute function,Num,S are the number of input variables and hidden neurons, respectively.2.3.M ULTIPLE LINEAR REGRESSIONThis study attempts to ascertain whether BRBPNN are preferred to MLR models widely used in the past for temporal variation of acid precipitation(Buishand et al.,APPLICATION OF BAYESIAN REGULARIZED BP NEURAL NETWORK MODEL173 1988;Dana and Easter,1987;MAP3S/RAINE,1982).MLR employs the following regression model:Y i=a0+a cos(2πi/12−φ)+bi+cP i+e i i=1,2,...12N(16) where N represents the number of years in the time series.In this case,Y i is the natural logarithm of the monthly mean concentration(mg/L)in precipitation for the i th month.The term a0represents the intercept.P i represents the natural logarithm of the precipitation amount(ml)for the i th month.The term bi,where i(month) goes from1to12N,represents the monotonic trend in concentration in precipitation over time.To facilitate the estimation of the coefﬁcients a0,a,b,c andφfollowing Buishand et al.(1988)and John et al.(2000),the reparameterized MLR model was established and theﬁnal form of Equation(16)becomes:Y i=a0+αcos(2πi/12)+βsin(2πi/12)+bi+cP i+e i i=1,2,...12N(17)whereα=a cosϕandβ=a sinϕ.a0,α,β,b and c of the regression coefﬁcients in Equation(17)are estimated using ordinary least squares method.2.4.D ATA SET SELECTIONPrecipitation chemistry data used are derived from NADP(the National At-mospheric Deposition Program),a nationwide precipitation collection network founded in1978.Monthly precipitation information of nine species(pH,NH+4, NO−3,SO2−4,Ca2+,Mg2+,K+,Cl−and Na+)and precipitation amount in1990–2003are collected in Clinton Crops Research Station(NC35),North Carolina, rmation on the data validation can be found at the NADP website: .The BRBPNN advantages are that they are able to produce models that are robust and well matched to the data.At the end of training,a Bayesian regularized neural network has the optimal generalization qualities and thus there is no need for a test set(MacKay,1992;1995).Husmeier et al.(1999)has also shown theoretically and by example that in a Bayesian regularized neural network,the training and test set performance do not differ signiﬁcantly.Thus,this study needn’t select the test set and only the training set problem remains.i.Training set of BRBPNN between precipitation acidity and other ions With regard to the relationship between precipitation acidity and other ions,the input neurons are taken from monthly concentrations of NH+4,NO−3,SO2−4,Ca2+, Mg2+,K+,Cl−and Na+.And precipitation acidity(pH)is regarded as the output of the network.174MIN XU ET AL.ii.Training set of BRBPNN for temporal trend analysisBased on the weight calculations of BRBPNN between precipitation acidity and other ions,this study will simulate temporal trend of three main ions using BRBPNN and MLR,respectively.In Equation(17)of MLR,we allow a0,α,β,b and c for the estimated coefﬁcients and i,P i,cos(2πi/12),and sin(2πi/12)for the independent variables.To try to achieve satisfactoryﬁtting results of BRBPNN model,we similarly employ four unknown items(i,P i,cos(2πi/12),and sin(2πi/12))as the input neurons of BRBPNN,the availability of which will be proved in the following. 2.5.S OFTWARE AND METHODMLR is carried out through SPSS11.0software.BRBPNN is debugged in neural network toolbox of MATLAB6.5for the algorithm described in Section2.1.Concretely,the BRBPNN algorithm is implemented through“trainbr”network training function in MATLAB toolbox,which updates the weight and bias according to Levenberg-Marquardt optimization.The function minimizes both squared errors and weights,provides the number of network parameters being effectively used by the network,and then determines the correct combination so as to produce a network that generalizes well.The training is stopped if the maximum number of epochs is reached,the performance has been minimized to a suitable small goal, or the performance gradient falls below a suitable target.Each of these targets and goals is set at the default values by MATLAB implementation if we don’t want to set them artiﬁcially.To eliminate the guesswork required in determining the optimum network size,the training should be carried out many times to ensure convergence.3.Results and Discussions3.1.C ORRELATION COEFﬁCIENTS OF PRECIPITATION IONSFrom Table I it shows the correlation coefﬁcients for the ion components and precipitation amount in NC35,which illustrates that the acidity of precipitation results from the integrative interactions of anions and cations and mainly depends upon four species,i.e.SO2−4,NO−3,Ca2+and NH+4.Especially,pH is strongly correlated with SO2−4and NO−3and their correlation coefﬁcients are−0.708and −0.629,respectively.In addition,it can be found that all the ionic species have a negative correlation with precipitation amount,which accords with the theory thatthe higher the precipitation amount,the lower the ionic concentration(Li,1999).3.2.R ELATIONSHIP BETWEEN PH AND CHEMICAL COMPOSITIONS3.2.1.BRBPNN Structure and RobustnessFor the BRBPNN of the relationship between pH and chemical compositions,the number of input neurons is determined based on that of the selected input variables,APPLICATION OF BAYESIAN REGULARIZED BP NEURAL NETWORK MODEL175TABLE ICorrelation coefﬁcients of precipitation ionsPrecipitation Ions Ca2+Mg2+K+Na+NH+4NO−3Cl−SO2−4pH amountCa2+ 1.0000.4620.5480.3490.4490.6270.3490.654−0.342−0.369Mg2+ 1.0000.3810.9800.0510.1320.9800.1230.006−0.303K+ 1.0000.3200.2480.2260.3270.316−0.024−0.237Na+ 1.000−0.0310.0210.9920.0210.074−0.272NH+4 1.0000.7330.0110.610−0.106−0.140NO−3 1.0000.0500.912−0.629−0.258Cl− 1.0000.0490.075−0.265SO2−4 1.000−0.708−0.245pH 1.0000.132 Precipitation 1.000 amountcomprising eight ions of NH+4,NO−3,SO2−4,Ca2+,Mg2+,K+,Cl−and Na+,and the output neuron only includes pH.Generally,the number of hidden neurons for traditional BPNN is roughly estimated through investigating the effects of the repeatedly trained network.But,BRBPNN can automatically search the optimal network parameters in posterior distribution(MacKay,1992;Foresee and Hagan, 1997).Based on the algorithm of Section2.1and Section2.5,the“trainbr”network training function is used to implement BRBPNNs with a tansig hidden layer and a pureline output layer.To acquire the optimal architecture,the BRBPNNs are trained independently20times to eliminate spurious effects caused by the random set of initial weights and the network training is stopped when the maximum number of repetitions reaches3000epochs.Add the number of hidden neurons(S)from1to 20and retrain BRBPNNs until the network performance(the number of effective parameters,MSE,E w and E D,etc.)remains approximately the same.In order to determine the optimal BRBPNN structure,Figure2summarizes the results for training many different networks of the8-S-1architecture for the relationship between pH and chemical constituents of precipitation.It describes MSE and the number of effective parameters changes along with the number of hidden neurons(S).When S is less than15,the number of effective parameters becomes bigger and MSE becomes smaller with the increase of S.But it is noted that when S is larger than15,MSE and the number of effective parameters is roughly constant with any network.This is the minimum number of hidden neurons required to properly represent the true function.From Figure2,the number of hidden neurons (S)can increase until20but MSE and the number of effective parameters are still roughly equal to those in the case of the network with15hidden neurons,which suggests that BRBPNN is robust.Therefore,using BPBRNN technique,we can determine the optimal size8-15-1of neural network.176MIN XU ET AL.Figure2.Changes of optimal BRBPNNs along with the number of hidden neurons.parison of calculations between BRBPNN(8-15-1)and MLR.3.2.2.Prediction Results ComparisonFigure3illustrates the output response of the BRBPNN(8-15-1)with a quite goodﬁt.Obviously,the calculations of BRBPNN(8-15-1)have much higher correlationcoefﬁcient(R2=0.968)and more concentrated near the isoline than those of MLR. In contrast to the previous relationships between the acidity and other ions by MLR,most of average regression R2achieves less than0.769(Yu et al.,1998;Baez et al.,1997;Li,1999).Additionally,Figures2and3show that any BRBPNN of8-S-1architecture hasbetter approximating qualities.Even if S is equal to1,MSE of BRBPNN(8-1-1)ismuch smaller and superior than that of MLR.Thus,we can judge that there havebeen strong nonlinear relationships between the acidity and other ion concentration,which can’t be explained by MLR,and that it may be quite reasonable to apply aAPPLICATION OF BAYESIAN REGULARIZED BP NEURAL NETWORK MODEL177TABLE IISum of square weights(SSW)and the relative importance(I)from input neurons to hidden layer Ca2+Mg2+K+Na+NH+4NO−3Cl−SO2−4 SSW 2.9589 2.7575 1.74170.880510.4063 4.0828 1.3771 5.2050 I(%)10.069.38 5.92 2.9935.3813.88 4.6817.70neural network methodology to interpret nonlinear mechanisms between the acidity and other input variables.3.2.3.Weight Interpretation for the Acidity of PrecipitationTo interpret the weight of the optimal BRBPNN(8-15-1),Equation(15)is used to evaluate the signiﬁcance of individual input variable and the calculations are illustrated in Table II.In the eight inputs of BRBPNN(8-15-1),comparatively, NH+4,SO2−4,NO−3,Ca2+and Mg2+have greater impacts upon the network and also indicates theseﬁve factors are of more signiﬁcance for the acidity.From Table II it shows that NH+4contributes by far the most(35.38%)to the acidity prediction, while SO2−4and NO−3contribute with17.70%and13.88%,respectively.On the other hand,Ca2+and Mg2+contribute10.06%and9.38%,respectively.3.3.T EMPORAL TREND ANALYSIS3.3.1.Determination of BRBPNN StructureUniversally,there have always been lowﬁtting results in the analysis of temporal trend estimation in precipitation.For example,the regression R2of NH+4and NO−3 for Vhesapeake Bay Watershed in Grimma and Lynch(2005)are0.3148and0.4940; and the R2of SO2−4,NH+4and NO−3for Japan in Sinya et al.(2002)are0.4205, 0.4323and0.4519,respectively.This study also applies BRBPNN to estimate temporal trend of precipitation chemistry.According to the weight results,we select NH+4,SO2−4and NO−3to predict temporal trends using BRBPNN.Four unknown items(i,P i,cos(2πi/12),and sin(2πi/12))in Equation(17)are assumed as input neurons of BRBPNNs.Spe-cially,two periods(i.e.1990–1996and1990–2003)of input variables for NH+4 temporal trend using BRBPNN are selected to compare with the past MLR results of NH+4trend analysis in1990–1996(John et al.,2000).Similar to Figure2with training20times and3000epochs of the maximum number of repetitions,Figure4summarizes the results for training many different networks of the4-S-1architecture to approximate temporal variation for three ions and shows the process of MSE and the number of effective parameters along with the number of hidden neurons(S).It has been found that MSE and the number of effective parameters converge and stabilize when S of any network gradually increases.For the1990–2003data,when the number of hidden neurons(S)can178MIN XU ET AL.Figure4.Changes of optimal BRBPNNs along with the number of hidden neurons for different ions.∗a:the period of1990–2003;b:the period of1990–1996.increase until10,we canﬁnd the minimum number of hidden neurons required to properly represent the accurate function and achieve satisfactory results are at least 6,6and4for trend analysis of NH+4,SO2−4and NO−3,respectively.Thus,the best BRBPNN structures of NH+4,SO2−4and NO−3are4-6-1,4-6-1,4-4-1,respectively. Additionally for NH+4data in1990–1996,the optimal one is BRBPNN(4-10-1), which differs from BRBPNN(4-6-1)of the1990–2003data and also indicates that the optimal BRBPNN architecture would change when different data are inputted.parison between BRBPNN and MLRFigure5–8summarize the comparison results of the trend analysis for different ions using BRBPNN and MLR,respectively.In particular,for Figure5,John et al. (2000)examines the R2of NH+4through MLR Equation(17)is just0.530for the 1990–1996data in NC35.But if BRBPNN method is utilized to train the same1990–1996data,R2can reach0.760.This explains that it is indispensable to consider the characteristics of nonlinearity in the NH+4trend analysis,which can make up the insufﬁciencies of MLR to some extent.Figure6–8demonstrate the pervasive feasibility and applicability of BRBPNN model in the temporal trend analysis of NH+4,SO2−4and NO−3,which reﬂects nonlinear properties and is much more precise than MLR.3.3.3.Temporal Trend PredictionUsing the above optimal BRBPNNs of ion components,we can obtain the optimal prediction results of ionic temporal trend.Figure9–12illustrate the typical seasonal cycle of monthly NH+4,SO2−4and NO−3concentrations in NC35,in agreement with the trend of John et al.(2000).APPLICATION OF BAYESIAN REGULARIZED BP NEURAL NETWORK MODEL179parison of NH+4calculations between BRBPNN(4-10-1)and MLR in1990–1996.parison of NH+4calculations between BRBPNN(4-6-1)and MLR in1990–2003.parison of SO2−4calculations between BRBPNN(4-6-1)and MLR in1990–2003.Based on Figure9,the estimated increase of NH+4concentration in precipita-tion for the1990–1996data corresponds to the annual increase of approximately 11.12%,which is slightly higher than9.5%obtained by MLR of John et al.(2000). Here,we can conﬁrm that the results of BRBPNN are more reasonable and im-personal because BRBPNN considers nonlinear characteristics.In contrast with180MIN XU ET AL.parison of NO−3calculations between BRBPNN(4-4-1)and MLR in1990–2003Figure9.Temporal trend in the natural log(logNH+4)of NH+4concentration in1990–1996.∗Dots (o)represent monitoring values.The solid and dashed lines respectively represent predicted values and estimated trend given by BRBPNN method.Figure10.Temporal trend in the natural log(logNH+4)of NH+4concentration in1990–2003.∗Dots (o)represent monitoring values.The solid and dashed lines respectively represent predicted values and estimated trend given by BRBPNN method.。

贝叶斯优化算法全面解析-图文

Bayesian Optimization CSC2541 - Topics in Machine LearningScalable and Flexible Models of UncertaintyUniversity of Toronto - Fall 2017Overview1.Bayesian Optimization of Machine Learning Algorithms2.Gaussian Process Optimization in the Bandit Setting3.Exploiting Structure for Bayesian OptimizationBayesian Optimization of Machine Learning Algorithms J. Snoek, A. Krause, H. Larochelle, and R.P. Adams (2012)Practical Bayesian Optimization of Machine Learning AlgorithmsJ. Snoek et al. (2015)Scalable Bayesian Optimization Using Deep Neural NetsPresentation by: Franco Lin, Tahmid Mehdi, Jason LiMotivationPerformance of Machine Learning algorithms are usually dependent on the choice of hyperparametersPicking the optimal hyperparameter values are hard-Ex. grid search, random search, etc.-Instead could we use a model to select which hyperparameters will be good next?Bayes Opt. of Machine Learning Algorithms-Bayesian Optimization uses all of the information from previous evaluations and performs some computation to determine the next point to try-If our model takes days to train, it would be beneficial to have a well structured way of selecting the next combination of hyperparameters to try-Bayesian Optimization is much better than a person finding a good combination of hyperparametersBayesian OptimizationIntuition:We want to find the peak of our true function (eg. accuracy as a function of hyperparameters)To find this peak, we will fit a Gaussian Process to our observed points and pick our next best point where we believe the maximum will be.This next point is determined by an acquisition function - that trades of exploration and exploitationBayesian Optimization TutorialBayesian Optimization Tutorialthat maximizes acquisition function Find the next best point xnBayesian Optimization TutorialEvaluate ƒ at the new observation xand update posteriornUpdate acquisition function from new posterior and find the next best pointAcquisition Function Intuition-We will use the acquisition functionProbability of Improvement (PI) asan example.-We want to find the point with thelargest area above our best value-This corresponds to the maximumof our acquisition functionAcquisition Functions-Guides the optimization by determining which point to observe next and is easier to optimize to find the next sample pointProbability of Improvement (PI)Expected Improvement (EI)GP-Upper/Lower Confidence Bound (GP-UCB/LCB)The Prior-Power of Gaussian Process depends on covariance function-For optimization, we don’t want kernels that produce unrealistically smooth sample functions-Automatic Relevance Determination (ARD) Matern 5/2 kernel is a good choiceKernel HyperparametersMarginalize over hyperparameters and compute integrated acquisition functionApproximate integral with Monte Carlo methodsConsiderations for Bayes Opt-Evaluating f may be time-consuming-Modern optimization methods should take advantage of multi-core/parallel programmingExpected Improvement per Second-Evaluating f will take longer in some regions of the parameter space-We want to pick points that are likely to be good and evaluated quickly -Let c(x) be the duration time to evaluate f(x)-Use GP to model ln[c(x)]-we can compute predicted expected inverse duration which allows us to obtain the EI per Second as a function of xParallelizing Bayes Opt-Can we determine which x to evaluate next, while other points are being evaluated?-Idea: Utilize tractable properties of GP to get Monte Carlo estimates of acquisition function under different results from pending function evaluationsConsider the case where N evaluations have completed, with data {xn ,yn}n=1N, and Jevaluations are pending {xj }j=1JParallelization Example-We’ve evaluated 3 observations and 2are pending {x 1,x 2}-Fit a model for each possible realizationof {f(x 1), f(x 2)}-Calculate acquisition for each model -Integrate all acquisitions over xResults●Branin-Hoo●Logistic Regression MNIST ●Online LDA●M3E●CNN CIFAR-10Logistic Regression - MNISTCIFAR-10●3-layer conv-net●Optimized over○Number of epochs○Learning rate○L2-norm constants ●Achieved state of the art○9.5% test errorGP Bayesian Optimization - Pros and Cons●Advantages○Computes the mean and variance●Disadvantages○Function evaluation is cubic on the number of inputsScalable Bayesian Optimization Using Deep Neural Networks●Replace a Gaussian Process with a Bayesian Neural Network●Use a deterministic neural network with Bayesian linear regression onthe last hidden layer●More accurately, use Bayesian linear regression with basis functions○DNN: R k -> R d○Bayesian linear regression: R d -> R○k is the dimensionality of the input, and d is the number of hidden units in the last layerBayesian Linear Regression●Still requires an inversion●Linear in the number of observations●Cubic in the basis function dimension or number of hidden units, DResultsGaussian Process Optimization in the Bandit SettingN. Srinivas, A. Krause, S. Kakade, and M. Seeger (2010)Gaussian process optimization in the bandit setting: No regret and experimental design Presentation by: Shadi Zabad, Wei Zhen Teoh, Shuja KhalidThe Bandits are Back!-We just learned about some exciting newtechniques for optimizing black box functions.Can we apply them to the classic multi-armedbandit problem?-In this case, we’d like to optimize the unknownreward function.Credit: D. Tolpin at ECAI 2012Cost-bounded Optimization-In the bandit setting, the optimization procedure is cost-sensitive: There’s a cost incurred each time we evaluate the function.-The cost is proportional to how far the point is from the point of maximum reward.-Therefore, we have to optimize the reward function while minimizing the cost incurred along the way.An Infinite Number of Arms-The multi-armed bandit algorithms and analyses we’ve seen so farassumed a discrete decision space (e.g. a decision space wherewe have K slot machines).-However, in Gaussian Process optimization, we’d like to considercontinuous decision spaces.-And in this domain, some of the theoretical analyses that wederived for discrete decision spaces can’t be extended in astraightforward manner.Credit: @Astrid, CrossValidatedMulti-armed Bandit Problem: Recap -The basic setting : We have a decision space that’sassociated with anunknown reward function .-Discrete examples: Slot machines at a casino, drug trials.-Continuous examples : Digging for oil or minerals, robotmotion planning.-In this setting, a “policy ” is a procedure for exploringthe decision space. An optimal policy is defined as aprocedure which minimizes a cost measure. The mostcommon cost measure is the “regret ”.Credit: Intelligent Motion Lab (Duke U)Credit: Gatis GribustsA Measure of Regret-In general terms, regret is defined as “the loss in reward due to not knowing” the maximum pointsbeforehand.-We can formalize this notion with 2 concepts:-Instantaneous regret (r t): the loss in reward at step t: r t = f(D max) - f(D t)-Cumulative regret (R T): the total loss in reward after T steps:R T = ∑r tMinimizing Regret: A Tradeoff-As we have seen before, we can define policies thatbalance exploration and exploitation. Some of thepolicies we’ve looked at are:-Epsilon-greedy-Thompson sampling-Upper Confidence Bound (UCB)-Some of these policies perform better than othersin minimizing the average regret over time.Average Regret = R T / TCredit: Russo et al., 2017Asymptotic Regret-We can also look at the cumulative or average regret measure as the number of iterations goes toinfinity.-An algorithm is said to be no-regret if its asymptoticcumulative regret rate is sublinear with respect to T (i.e. the number of iterations)sqrt(T) and log(T) are examples of sublinear regret rates w.r.t. T.Why is Asymptotic Regret Important?-In real world applications, we know neitherinstantaneous nor average regret. So, whyare we concerned with characterizing theirasymptotic behavior?-Answer: Bounds on the average regret tellus about the convergence rate (i.e. how fastwe approach the maximum point) of theoptimization algorithm.Credit: N. de Freitas et al., 2012Regret Bounds in Discrete Decision Spaces-In the previous lecture, we discussed asymptotic regret in discrete decision spaces where we have K slot machines or drug trials.-We also looked at theorems by Auer et al. that derive an upper bound on the regret rate for the UCB algorithm in discrete settings.Dani et al. 2008“In the traditional K-arm bandit literature, the regret is often characterized for a particular problem in terms of T, K, and problem dependent constants . In the K-arm bandit results of Auer et al. [2002], this problem dependent constant is the ‘gap’ between the loss of the best arm and the second best arm.”Regret Bounds in Continuous Decision Spaces-Dani et al.** extended Auer et al.’s theoretical results to continuous decision spaces and proved upper and lower regretbounds for the UCB algorithm.-However, their method places restrictions on the types of reward functions considered, primarily: The functions are defined overfinite-dimensional linear spaces.** Dani, V., Hayes, T. P., and Kakade, S. M. Stochastic linear optimization under bandit feedback. In COLT, 2008.Infinite-dimensional Functions-Srinivas et al. propose to relax some of the restrictionsof Dani et al.’s analysis and extend the results torandom, infinite-dimensional functions.-Earlier in the semester, we learned about a method forgenerating such classes of functions: GaussianProcesses.-Idea: Assuming the target reward function is sampledfrom a Gaussian Process, try to optimize it usingGP-UCB.-How to derive regret bounds for those classes ofCredit: Duvenaud, The Kernel Cookbook functions?Using Information Gain To Derive Regret BoundsInformation GainRecall Mackay (1992) paper: Information gain can be quantified as change in entropy In this context: Information gain =entropy in prior - entropy in posterior after y A sampled = H(f) - H( f | y A )= I(f; y A ), mutual information between f and observed y A=I(y A ; f) = H(y A ) - H( y A |f) = (log| 2I + K A |)/2 - (log| 2I |)/2 = (log|I + -2 K A |)/2Note:information gain depends on kernel of GP prior and input spaceCredit: Srinivas et al. 2010If our goal is just exploration ...Greedy Experimental Design Algorithm:Sequentially, findHowever the worse point weselect, the more penalty we get Credit: Srinivas et al. 2010GP - UCB to the rescueExplore ExploitCredit: Srinivas et al. 2010Maximum information GainDefinition:Maximum information gain after T data points sampled,This term will be used to quantify the regret bound for the algorithmRegret Bounds - Finite Domain Theorem 1:Assumptions:-Finite D- f sample of a GP with mean 0,-k(x, x’) of GP s.t. k(x,x) (variance) not greater than 1Then, by running GP-UCB for f withWe obtain: TAssuming some strictly sublinear T ...(we will verify later that this is achievable by choice of kernels),We can find some sublinear function f(T) bounding above P(R T curve lies below) is at least 1-f(T)Regret Bounds II - General Compact+Convex SpaceTheorem 2:Assumptions:- D compact and convex in [0,r]d,- f sample of a GP with mean 0,-k(x, x’) of GP s.t. k(x,x) (variance) not greater than 1-k(x,x’) s.t. f fulfills smoothness condition -- discussed nextThen, by running GP-UCB for f withWe obtain:Regret Bounds II ContinuedTheorem 2 requires f to fulfill:This holds for stationary kernels k(x,x’) = k(x-x’) which are 4-times differentiable: Squared Exponential Kernel Matern Kernels with v>2Credit: Srinivas et al. 2010Bounding Information Gain-- F is submodular function⇒T⇒ T SubmodularityThis holds if A constructed byGreedy Experiment Design Rule Credit: Krause, https://las.inf.ethz.ch/sfo/Bounding Information Gain ContinuedWe can bound the term by considering the worst allocation of the T samples under some relaxed greedy procedure (see appendix section C).In finite space D, this eventually gives us a bound in terms of the eigenvalues of the covariance matrix for all |D| points:The faster the spectrum decays, the slower the growth of the boundBounding Information Gain ContinuedCredit: Srinivas et al. 2010Bounding Information Gain ContinuedTheorem 5: Assume general compact and convex set D in R d , kernel k(x,x’)≤1:1.d- dimensional bayesian linear regression:2.Squared exponential kernel:3.Matern kernel (v>1) :Now recall the bound obtained for GP-UCB in theorem 2: Combining the two theorems we obtain the following (1-δ) upper confidence bound for the total regret, R T (up to polylog factors):With T = + Credit: Srinivas et al. 2010Results and DiscussionExperimental Setup●Synthetic and real sensor network data (traffic and temperature)used to illustrate the differences●Gaussian Processes - Upper Confidence Bound (GP-UCB) iscompared with various heuristics:○Expected Improvement (EI)○Most Probable Improvement (MPI)○Naive Methods (only mean or only variance)。

下载提示

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

PAPER Structure Learning of Bayesian Networks Using Dual Genetic Algorithm

合集下载

华为MateBook X Pro14 使用指南说明书

基于进化MCMC的DBN学习算法

贝叶斯正则化Bayesian BP Regulation

贝叶斯优化算法全面解析-图文

文档推荐

最新文档