Patent Publication Number: US-7720774-B2

Title: Learning method and apparatus utilizing genetic algorithms

Description:
CROSS REFERENCE TO RELATED APPLICATION 
   The present invention contains subject matter related to Japanese Patent Applications JP2005-317031 and JP2006-116038 filed in the Japanese Patent Office on Oct. 31, 2005 and Apr. 19, 2006, respectively, the entire contents of which being incorporated herein by reference. 
   BACKGROUND OF THE INVENTION 
   1. Field of the Invention 
   The present invention relates to a learning apparatus for building a network structure of a Bayesian network based on data obtained by learning (hereinafter may be referred to as “learning data”) and to a method of building the network structure. 
   2. Description of the Related Art 
   In recent years, the scope of application of the information processing technology has been extended, and an information-processing mechanism capable of operating according to various circumstances and a variety of users has become important. That is, treated objects having uncertainty (i.e., objects which may not be assumed in advance or may not be fully observed) have become increasingly important. Therefore, a mechanism of processing intelligent information to understand circumstances as precisely as possible even if only uncertain information is available and of performing appropriate processing may be required. 
   Because of these demands, a probability model which describes an object of interest using a network structure and probabilistically forecasts from observed events the object to be known has attracted attention. A Bayesian network which indicates a cause and effect relationship (connection) between nodes representing variables by means of a directed graph is known as a typical probability model. 
   [Non-patent reference 1] Cooper, G., and Herskovits, E., “A Bayesian method for the induction of probabilistic networks from Data”, Machine Learning, Vol. 9, pp. 309-347, 1992 
   [Non-patent reference 2] Hongjun Zhou, Shigeyuki Sakane, “Sensor Planning for Mobile Robot Localization Using Structure Learning and Inference of Bayesian Network,” Journal of the Japan Robotics Society, Vol. 22, No. 2, pp. 245-255, 2004 
   SUMMARY OF THE INVENTION 
   In order to apply the Bayesian network to an actual object to be handled, it is important to build an appropriate model. 
   In many of existing examples of practical applications, a model is built by making use of knowledge and experience of an expert who is versed in the region to be tackled. There is a demand for a method of building a network structure of a Bayesian network based on learning data. However, building a network structure based on learning data is an NP-hard problem. Furthermore, it may be necessary that directed acyclicity of the network structure be assured. Therefore, it is not easy to build an optimum network structure. 
   Accordingly, in order to build a network structure in a realistic time, a K2 algorithm using heuristics has been proposed (see non-patent reference 1). The K2 algorithm includes the steps: 1) restricted candidates that can be parent nodes for each node are selected; 2) one child node is selected, candidate parent nodes are added one by one, and a network structure is built; 3) the node is adopted as a parent node if and only if the evaluated value goes high; and 4) the process goes to other child node if there is not any other node that can be added as a parent node or if the evaluated value is not increased by addition of a node. The above-described steps 1)-4) are carried out for every child node. Thus, a quasi-optimum network structure can be built. In the step 1) above, candidates that can become parent nodes for each node are restricted for the following reasons. Where the orders between nodes are previously designed, the range in which a search for a network structure is made is restricted, thus reducing the amount of computation. Furthermore, the acyclicity of the network structure is assured. 
   Although this K2 algorithm can build a network structure in a realistic time, there is the restriction that the orders between nodes might be previously designed based on designer&#39;s prior knowledge. 
   On the other hand, a method of determining the connection between nodes using a K2 algorithm after determining the orders between the nodes using a genetic algorithm has also been proposed (see non-patent reference 2). 
   However, with these related art algorithms, a network structure is built by determining the connection between nodes in a bottom-up manner according to orders designed by a designer or according to orders determined using a genetic algorithm. Therefore, these algorithms are unsuited for added learning of network structures. In addition, many people have some knowledge about connection besides experts versed in the region to be handled. With related art algorithms, it has been difficult to reflect prior knowledge about connection in a network structure. 
   In view of such actual circumstances in the related art techniques, it is desirable to provide learning apparatus and method which can build a network structure (i.e., orders and connections) of a Bayesian network based on learning data when there is an NP-hard problem, can reflect all or some of knowledge about orders and connections in the network structure, and permit added learning of the network structure. 
   A learning apparatus according to one embodiment of the present invention builds a network structure of a Bayesian network based on learning data, the Bayesian network representing a cause and effect relationship between plural nodes in terms of a directed graph. The learning apparatus has (a) storage means in which the learning data is stored and (b) learning means for building the network structure based on the learning data. The learning means prepares an initial population of individuals constituted by individuals each having a genotype in which orders between the nodes and cause and effect relationship have been stipulated, repeatedly carries out crossovers and/or mutations on the initial population of individuals based on a genetic algorithm, calculates an evaluated value for each individual based on the learning data, searches for an optimum individual, and takes the phenotype of the optimum individual as the aforementioned network structure. 
   In the learning apparatus according to the embodiment described above, the genotype can take the plural nodes arranged in a first direction according to a stipulated order as parent nodes, take the plural nodes arranged in a second direction perpendicular to the first direction according to the stipulated order as child nodes, and stipulate the presence or absence of a cause and effect relationship between corresponding nodes by alleles at each of gene loci at which the parent nodes and child nodes correspond to each other. 
   Another embodiment of the present invention is a learning method of building a network structure of a Bayesian network where a cause and effect relationship between plural nodes is represented by a directed graph. This method starts with preparing an initial population of individuals constituted by individuals each having a genotype in which orders and a cause and effect relationship between the nodes are stipulated. Crossovers and/or mutations of the initial population of individuals are repeatedly performed based on a genetic algorithm. An evaluated value for each individual is calculated based on the learning data, and an optimum individual is searched for. The phenotype of the optimum individual is taken as the aforementioned network structure. 
   According to the learning apparatus and method according to embodiments of the present invention, a quasi-optimum network structure can be efficiently built when there is an NP-hard problem. Furthermore, all or some of designer&#39;s knowledge about the network structure (orders and connections) can be reflected in the initial population of individuals. Moreover, added learning of the network structure is enabled. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
       FIG. 1  is a schematic diagram of a learning apparatus according to an embodiment of the present invention. 
       FIG. 2  is a table showing an example of a set of items of learning data used when a model of a Bayesian network is built. 
       FIGS. 3A and 3B  are diagrams showing an example of a two-dimensional genotype and its genotype. 
       FIG. 4  is a flowchart illustrating a procedure for searching for an optimum individual using a genetic algorithm. 
       FIGS. 5A and 5B  are diagrams illustrating a calculational formula for BD metric. 
       FIGS. 6A and 6B  are diagrams showing an example of a lethal gene produced during order crossovers and order mutations in a classical genetic algorithm. 
       FIGS. 7A and 7B  are diagrams showing examples of connection crossovers in a case where the orders of parent individuals are the same. 
       FIGS. 8A and 8B  are diagrams showing examples of order crossovers in a case where the orders of parent individuals are different. 
       FIGS. 9A and 9B  are diagrams showing examples of processing for connection mutations. 
       FIGS. 10A and 10B  are diagrams showing examples of processing for order mutations. 
       FIGS. 11A ,  11 B, and  11 C are diagrams showing examples in which processing for connection mutations is performed after processing for order mutations. 
       FIGS. 12A and 12B  are diagrams showing examples in which the number of parent nodes having a cause and effect relationship with some child node exceeds an upper limit as a result of processing for order crossovers. 
       FIGS. 13A and 13B  are diagrams showing examples in which genes are adjusted to prevent the number of parent nodes having a cause and effect relationship from exceeding the upper limit. 
       FIG. 14  is a diagram showing four directed acyclic graphs and an evaluated value calculated under the condition N′ ijk =1. 
       FIGS. 15A and 15B  are diagrams illustrating a procedure for creating learning data used when the evaluated value of  FIG. 14  was calculated. 
       FIG. 16  is a diagram showing four directed acyclic graphs and an evaluated value calculated by the procedure of an embodiment. 
       FIG. 17  is a diagram illustrating a procedure for obtaining specific learning data. 
       FIG. 18  is a diagram illustrating a procedure for obtaining specific learning data. 
       FIG. 19  is a diagram illustrating a procedure for obtaining specific learning data. 
       FIG. 20  is a diagram illustrating a procedure for obtaining specific learning data. 
       FIG. 21  is a diagram showing a network structure obtained by a K2 algorithm based on learning data. 
       FIG. 22  is a diagram showing a network structure of the twentieth generation when added learning was done using the network structure of  FIG. 21  as an initial structure. 
       FIG. 23  is a diagram showing a network structure of the fortieth generation when added learning was done using the network structure of  FIG. 21  as an initial structure. 
       FIG. 24  is a diagram showing a network structure of the sixtieth generation when added learning was done using the network structure of  FIG. 21  as an initial structure. 
       FIG. 25  is a diagram showing a network structure of the eightieth generation when added learning was done using the network structure of  FIG. 21  as an initial structure. 
   

   DESCRIPTION OF THE PREFERRED EMBODIMENTS 
   Specific embodiments of the present invention are hereinafter described in detail with reference to the drawings. In one of the embodiments, the invention is applied to a learning apparatus which constructs a network structure of a Bayesian network based on data about learning (learning data). 
   First, the structure of the learning apparatus according to the present embodiment is schematically shown in  FIG. 1 . As shown in  FIG. 1 , the learning apparatus  1  according to the present embodiment includes a learning data storage portion  10 , a learning portion  11 , and a model storage portion  12 . 
   Learning data used when a model of a Bayesian network is built is stored in the learning data storage portion  10 . One example of full set of discrete data in a case where there are five nodes, from X 0  to X 4 , is shown in  FIG. 2 . In  FIG. 2 , each item of the learning data is represented in the form X i   jk , where i indicates a node ID, j indicates a case ID (i.e., what is the data item number as counted from the first obtained item of the learning data), and k indicates a state ID (i.e., the state at each node). That is, X i   jk  means that the state of learning data item obtained at the node X i  as the jth data item is indicated by state ID=k. 
   The learning portion  11  builds a model of a Bayesian network based on the learning data stored in the learning data storage portion  10 . Especially, the learning portion  11  determines both the orders between nodes constituting the network structure of the Bayesian network and connections at the same time by the use of a genetic algorithm. The use of the genetic algorithm makes it possible to build a quasi-optimum network structure efficiently when there is an NP-hard problem. The model built by the learning portion  11  is stored in the model storage portion  12 . 
   Processing for building the network structure by the learning portion  11  is next described in detail. In the following, it is assumed, for the sake of simplicity, that there are five nodes, from X 0  to X 4 . 
   The learning portion  11  according to the present embodiment represents individuals used in the network structure of the Bayesian network, i.e., genetic algorithm, in terms of a two-dimensional genotype as shown in  FIG. 3A . In  FIG. 3A , x 0 , x 1 , x 2 , x 3 , and x 4  in the rows and columns indicate the orders between nodes. The orders in the rows and columns are identical at all times. Gene loci in the triangular region located over the diagonal components have alleles “0” and “1”, which indicate connections from parent nodes to child nodes. “0” indicates that there is no cause and effect relationship between parent and child nodes. “1” indicates that there is a cause and effect relationship between parent and child nodes. Each diagonal component corresponds to a self-loop. Gene loci in the triangular region located under the diagonal components have alleles “0” and “1”, which indicate connections from child nodes to parent nodes. To assure acyclicity of the network structure, it is assumed that genes located under the diagonal components show no manifestation of traits. Therefore, individuals having the two-dimensional genotype as shown in  FIG. 3A  have a phenotype as shown in  FIG. 3B . 
   The learning portion  11  takes numerous individuals having such a two-dimensional genotype as an initial population of individuals. The initial population of individuals is searched for an optimum individual using a genetic algorithm. The phenotype of the individual is taken as a quasi-optimum network structure. 
   A procedure for searching for the optimum individual using the genetic algorithm is illustrated in the flowchart of  FIG. 4 . 
   First, in step S 1 , the learning portion  11  creates the initial population of individuals. At this time, the learning portion  11  may create the initial population of individuals at random. Where the designer has knowledge about the network structure (orders and connections), the initial population of individuals may be created by converting the phenotypes into two-dimensional genotypes and performing processing for mutations. The latter method permits the designer&#39;s knowledge about the network structure to be totally or partially reflected in the initial population of individuals. Furthermore, the learning portion  11  may create the initial population of individuals from individuals indicated by the results of learning. In this case, added learning of the network structure is enabled. 
   Then, in step S 2 , the learning portion  11  calculates the evaluated value of each individual (fitness in the genetic algorithm) based on the learning data stored in the learning data storage portion  10 . In particular, the BD metric (P(D|B s )) is calculated according to the following Eq. (1), and a logarithm of the calculated value is taken as the evaluated value. 
   
     
       
         
           
             
               
                 
                   P 
                   ⁡ 
                   
                     ( 
                     
                       D 
                       | 
                       
                         B 
                         s 
                       
                     
                     ) 
                   
                 
                 = 
                 
                   
                     ∏ 
                     
                       i 
                       = 
                       0 
                     
                     
                       n 
                       - 
                       1 
                     
                   
                   ⁢ 
                   
                       
                   
                   ⁢ 
                   
                     
                       ∏ 
                       
                         j 
                         = 
                         0 
                       
                       
                         
                           q 
                           i 
                         
                         - 
                         1 
                       
                     
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       
                         
                           Γ 
                           ⁡ 
                           
                             ( 
                             
                               N 
                               ij 
                               ′ 
                             
                             ) 
                           
                         
                         
                           Γ 
                           ⁡ 
                           
                             ( 
                             
                               
                                 N 
                                 ij 
                                 ′ 
                               
                               + 
                               
                                 N 
                                 ij 
                               
                             
                             ) 
                           
                         
                       
                       ⁢ 
                       
                         
                           ∏ 
                           
                             k 
                             = 
                             0 
                           
                           
                             
                               r 
                               i 
                             
                             - 
                             1 
                           
                         
                         ⁢ 
                         
                           
                             
                                 
                             
                             ⁢ 
                             
                               Γ 
                               ⁢ 
                               
                                 ( 
                                 
                                   
                                     N 
                                     ijk 
                                     ′ 
                                   
                                   + 
                                   
                                     N 
                                     ijk 
                                   
                                 
                                 ) 
                               
                             
                           
                           
                             Γ 
                             ⁡ 
                             
                               ( 
                               
                                 N 
                                 ijk 
                                 ′ 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                 
               
             
             
               
                 ( 
                 1 
                 ) 
               
             
           
         
       
     
   
   In this Eq. (1), D is learning data stored in the learning data storage portion  10 , B s  indicates individuals used in the network structure of the Bayesian network, i.e., genetic algorithm, P(D|B s ) is the probability of D under condition B s , and Γ is a gamma function and given by Γ(n)=(n−1)!. From (n−1)!=n!/n, it is considered that 0!=1!/1=1. Therefore, for the sake of convenience, the relationship 0!=1 is introduced. Furthermore, as shown in  FIG. 5A , let n be the number of nodes. Let X i  be the ith node. Let V ik  be the kth value that the X i  can assume. Let r i  be the number of values (number of states) that the X i  can assume. As shown in  FIG. 5B , let Π i  be the parent node pattern of the X i . Let w ij  be the jth pattern (value that can be assumed) of the Π i . q i  is the number of patterns of the Π i . N ijk  is the number of data items within the learning data D which make X i  have values v ik  and Π i  have values w ij . N ij  is calculated according to the following Eq. (2). N′ ijk  and N′ ij  are associated with designer&#39;s prior knowledge and can be treated similarly to N ijk  and N ij . Their details will be described later. 
   
     
       
         
           
             
               
                 
                   N 
                   ij 
                 
                 = 
                 
                   
                     ∑ 
                     
                       k 
                       = 
                       0 
                     
                     
                       
                         r 
                         i 
                       
                       - 
                       1 
                     
                   
                   ⁢ 
                   
                     
                       N 
                       ijk 
                     
                     . 
                   
                 
               
             
             
               
                 ( 
                 2 
                 ) 
               
             
           
         
       
     
   
   In practice, the learning data stored in the learning data storage portion  10  may have missing data items or may be continuous quantity instead of discrete data. A method of coping with missing data items or continuous quantity is described, for example, by Richard E. Neapolitan in “LEARNING BAYESIAN NETWORKS”, ISBN 0-13-012534-2. 
   Subsequently, in step S 3 , the learning portion  11  makes a decision as to whether an ending condition is satisfied or not. In particular, one example of the ending condition is that the number of generations has exceeded a threshold value. Another example is that the rate of variation of the evaluated value has decreased below a threshold value. If the ending condition is not satisfied, control goes to step S 4 . If the ending condition is satisfied, an individual producing the highest evaluated value is selected, and the processing is ended. 
   Subsequently, instep S 4 , the learning portion  11  selects a next population of individuals from the present population of individuals based on the evaluated value. That is, the learning portion selects a desired number of individuals from the present population of individuals based on the evaluated value while permitting overlap. Methods generally used in genetic algorithms such as roulette wheel selection, tournament selection, and elite reservation can be used as methods of selection. However, the logarithm of the BD metric that is an evaluated value is a negative value and so it is difficult to directly utilize a method of performing a selection with a probability proportional to the evaluated value as in roulette wheel selection. Accordingly, the evaluated value may be previously converted into a positive value using a Boltzmann distribution. 
   Subsequently, in steps S 5  and S 6 , the learning portion  11  performs processing for crossovers on individuals contained in the present population of individuals according to a desired crossover probability. Furthermore, the learning portion performs processing for mutations according to a desired mutation rate. In this processing for crossovers, two child individuals are created from two parent individuals. In the processing for mutations, one child individual is created from one parent individual. At this time, parent individuals may be replaced by created child individuals. Child individuals and parent individuals may be made to coexist. 
   Especially, in the processing for order crossovers and processing for order mutations, in a case where a classical procedure of genetic algorithm is used, lethal genes are easily produced as shown in  FIGS. 6A and 6B . For example, as shown in  FIG. 6A , where individuals having orders X 0 , X 1 , X 2 , X 3 , and X 4  and individuals having orders X 3 , X 1 , X 0 , X 4 , and X 2  are crossed using the point between the third and fourth nodes as a crossover point, it follows that nodes having the same node ID are present within the same individual, resulting in a lethal gene. Furthermore, as shown in  FIG. 6B , where processing for producing mutations at the position X 2  of individuals having orders X 0 , X 1 , X 2 , X 3 , and X 4  is performed to produce X 4 , it follows that nodes having the same node ID are present within the same individual. This gives rise to a lethal gene. Where lethal genes are produced easily in this way, the efficiency of learning is low. Therefore, a framework preventing generation of lethal genes would be necessary. 
   When a network structure of a Bayesian network is built using a genetic algorithm, order crossover or order mutation is essentially equivalent to a traveling salesman problem, and various procedures have been proposed (see, literature written by P. Larranaga, C. Kuijpers, R. Murga, and Y. Yurramendi, “Learning Bayesian network structures by searching for the best ordering with genetic algorithms”, IEEE Transactions on Systems, Man and Cybernetics, 26(4), pp. 487-493, 1996) In the following, processing for crossovers in step S 5  is first described while taking specific examples. 
   An example of the processing for crossovers in a case where parent individuals have the same orders is shown in  FIGS. 7A and 7B . In this crossover processing, only connections are treated. As shown in  FIG. 7A , with respect to two parent individuals having orders X 0 , X 1 , X 2 , X 3 , and X 4 , the point between the third and fourth nodes is taken as a crossover point. The following genes are exchanged. As a result, child individuals as shown in  FIG. 7B  are obtained. As can be seen from  FIG. 7B , the connection of the parent individuals has been genetically transmitted to child individuals. 
   An example of processing for order crossovers in a case where parent individuals have different orders is shown in  FIGS. 8A and 8B . For the processing for order crossovers, PMX (partially-mapped crossover) can be used, for example. In this PMX, 1) two crossover points are selected at random, 2) nodes between the crossover points are interchanged, 3) if each node is not used (3-1) within the individual, then it is used intact, if the node has been already used (3-2), then it is exchanged with a node from which an unexchanged node will be mapped, and if the node has also been already used (3-3), the node is exchanged with the node from which the unexchanged node will be mapped. At this time, the exchanged node inherits the connection with the parent node or child node of the present node itself. As shown in  FIG. 8A , with respect to a parent individual having orders X 0 , X 1 , X 2 , X 3 , and X 4  and another parent individual having orders X 2 , X 0 , X 4 , X 3 , and X 1 , if nodes between crossover points which are between the second and third nodes and between the fourth and fifth nodes, respectively, are interchanged according to a PMX procedure, child individuals as shown in  FIG. 8B  are obtained. As can be seen from FIG.  8 B, orders and connections of the parent individuals have been genetically transmitted to the child individuals. 
   Where the parent individuals have the same orders as shown in  FIG. 7A , if order crossover is performed according to a PMX procedure, the same child individuals as in  FIG. 7B  are obtained. That is, the processing for connection crossovers shown in  FIGS. 7A and 7B  is a special case of the processing for order crossovers (i.e., parent individuals have the same orders). Only if the processing for order crossovers is performed, the processing for connection crossovers is also carried out. 
   Subsequently, the processing for mutations in step S 6  is described while taking its specific examples. 
   An example of the processing for connection mutations is shown in  FIGS. 9A and 9B . This processing for connection mutations is realized by inverting a gene at an arbitrary gene locus onto an allele. As shown in  FIG. 9A , with respect to a parent individual having orders X 0 , X 1 , X 2 , X 3 , and X 4 , if gene “0” at a gene locus where the parent node is X 3  and the child node is X 1  is inverted onto an allele “1”, and if gene “1” at a gene locus where the parent node is X 4  and the child node is X 0  is inverted onto an allele “0”, child individuals as shown in  FIG. 9B  are obtained. 
   An example of processing for order mutations is shown in  FIGS. 10A and 10B . For example, inversion mutation (IVM) can be used for the processing for order mutations. This inversion mutation (IVM) involves 1) selecting plural successive nodes at random and removing them and 2) inverting the orders of the removed nodes and then inserting the orders into random locations. As shown in  FIG. 10A , with respect to a parent individual having orders X 0 , X 1 , X 2 , X 3 , and X 4 , two successive nodes X 2  and X 3  are selected and removed. Their orders are inverted. If the orders are then inserted behind X 4 , child individuals as shown in  FIG. 10B  are obtained. 
   Since the processing for connection mutations shown in  FIGS. 9A and 9B  and the processing for order mutations shown in  FIGS. 10A and 10B  are independent of each other, both of these two kinds of processing can be performed. However, obtained child individuals differ according to which one of the kinds of processing is performed first. An example in which processing for connection mutations is performed after performing processing for order mutations is shown in  FIGS. 11A-11C . As shown in  FIG. 11A , with respect to a parent individual having orders X 0 , X 1 , X 2 , X 3 , and X 4 , two successive nodes X 2  and X 3  are selected and removed. Their orders are inverted and then inserted behind X 4 . That is, processing for order mutations is performed. As a result, an individual as shown in  FIG. 11B  is obtained. Furthermore, with respect to this individual, gene “0” at a gene locus where the parent node is X 3  and the child node is X 1  is inverted onto an allele “1”. A gene “1” at a gene locus where the parent node is X 4  and the child node is X 0  is inverted onto an allele “0”. That is, processing for connection mutations is performed. As a result, an individual as shown in  FIG. 11C  is obtained. 
   Referring back to  FIG. 4 , the number of parent nodes is limited in step S 7 , and then process goes back to step S 2 . That is, an upper limit (MaxFanIn) is previously set for the number of parent nodes (FanIn) having a cause and effect relationship with itself for each of child nodes of each individual. If the number of parent nodes having a cause and effect relationship with an arbitrary child node exceeds the upper limit as a result of the processing for crossovers and processing for mutations in steps S 5  and S 6 , genes are so adjusted that the relation FanIn≦MaxFanIn holds. Examples in which the number of parent nodes is restricted in this way are shown in  FIGS. 12A ,  12 B,  13 A, and  13 B. As shown in  FIG. 12A , with respect to a parent individual having orders X 0 , X 1 , X 2 , X 3 , and X 4  and another parent individual having orders X 2 , X 0 , X 4 , X 3 , and X 1 , if nodes between crossover points between the second and third nodes and between the fourth and fifth nodes, respectively, are interchanged according to a PMX procedure, child individuals as shown in  FIG. 12B  are obtained. In this figure, with respect to the child individuals on the left side, the number of parent nodes (FanIn) having a cause and effect relationship with child node X 0  is 4, which exceeds the upper limit (MaxFanIn) of 3. Accordingly, the relationship FanIn≦MaxFanIn is achieved by selecting gene “1” at a gene locus where the parent node is X 3  and the child node is X 0 , for example, out of individuals shown in  FIG. 13A  and inverting the selected gene “1” onto allele “0” to produce individuals as shown in  FIG. 13B . 
   When genes are inverted onto their alleles such that the relationship FanIn≦MaxFanIn is achieved, the inverted genes may be selected at random. The selection may be so made that the evaluated value of the individuals becomes highest. In the latter case, it maybe necessary to calculate the evaluated value regarding individuals having child nodes for which the number of parent nodes has exceeded the upper limit. With respect to this individual, it may not be necessary to calculate the evaluated value in step S 2 . The evaluated value computed in step S 7  can be exploited. 
   In this way, according to the learning apparatus  1  of the present embodiment, a quasi-optimum network structure can be built efficiently for an NP-hard problem by expressing the network structure of a Bayesian network (orders and connections) (i.e., individuals used in a genetic algorithm) in terms of a two-dimensional genotype, taking numerous individuals having the two-dimensional genotype as an initial population of individuals, searching the initial population of individuals for an optimum individual using a genetic algorithm, and taking the phenotype of the individual as the network structure of the Bayesian network. 
   Furthermore, the learning apparatus  1  makes it possible to totally or partially reflect designer&#39;s knowledge about the network structure in the initial population of individuals by converting the phenotype into a two-dimensional genotype and performing processing for mutations in a case where the designer has knowledge about the network structure (orders and connections). Where it is desired to fix orders and connections at some nodes, individuals having two-dimensional genotypes different from the fixed orders and connections may be regarded as lethal genes and removed from the subject of selection in the above step S 4 . 
   In addition, the learning apparatus  1  enables added learning of the network structure by creating an initial population of individuals from individuals obtained as a result of learning. 
   In the description of the flowchart illustrated in  FIG. 4 , the learning apparatus  11  performs both processing for crossovers and processing for mutations. Only one of the two kinds of processing may also be performed. 
   As shown in Eq. (1), the BD metric is chiefly composed of (i) N ijk  determined by the network structure and learning data and (ii) N′ ijk  determined by the designer&#39;s prior knowledge. Generally, where the designer&#39;s prior knowledge can be defined for all i&#39;s and j&#39;s regarding some node X i  and its parent node such as p (v ik , w ij ) N′ ijk  are calculated according to the following Eq. (3). In this Eq. (3), N′ is referred to as the equivalent sample size, and is a parameter for assuming what number of samples are used to represent information obtained from the prior knowledge.
 
 N′   ijk   =p ( v   ik   , w   ij )× N′   (3)
 
   Where the designer has prior knowledge about the network structure, the designer&#39;s prior knowledge can be reflected by substituting the N′ ijk  calculated in this way into the above Eq. (1). 
   Meanwhile, where the designer does not have such prior knowledge, it is customary to calculate the BD metric under the condition N′ ijk =1. The BD metric calculated under the condition N′ ijk =1 is especially referred to as a K2 metric. 
   However, where the assumption N′ ijk =1 is made in this way, the values of calculated BD metric of directed acyclic graphs (DAGS) might be different if the graphs belong to the same Morkov equivalent class that results in the same inferential result. 
   As an example, a network structure made up of four nodes of Cloudy, Sprinkler, Rain, and WetGrass as shown in  FIG. 14  is now considered. 
   Of the directed acyclic graphs (DAGS) shown in  FIG. 14 , G 1  to G 3  have the same links and have the same uncoupled head-to-head meetings (Sprinkler→WetGrass←Rain) and, therefore, these three graphs can be represented in the same DAG pattern gp. However, G 4  has the same link as G 1  to G 3  but has other uncoupled head-to-head meetings (Sprinkler→Cloudy←Rain) and so cannot be represented in the DAG pattern gp. An evaluated value (logarithm of the BD metric) calculated under the condition N′ ijk =1 when some learning data is given to the four DAGs is also shown in  FIG. 14 . 
   The learning data was created in the following manner using a DAG having a conditional probability table (CPT) as shown in  FIG. 15A . That is, at Cloudy that is the node of the highest degree of parentage, it is first probabilistically determined whether the node is true or false based on the conditional probability table. It is now assumed that Cloudy=true. At each of Sprinkler and Rain that are child nodes of the Cloudy, a decision is then made probabilistically as to whether the node is true or false based on the conditional probability table under the parental condition. It is here assumed that Sprinkler=false and Rain=true. Then, at WetGrass that is the child node of the Sprinkler and Rain, the node is probabilistically determined whether the node is true or false based on the conditional probability table under the parental condition. In this way, learning data about one case is created. Learning data about 1,000 cases are created similarly as shown in  FIG. 15B . 
   As shown in  FIG. 14 , where the assumption N′ ijk =1 is made, the evaluated value of G 1  and G 3  is different from the evaluated value of G 2 . Where the assumption N′ ijk =1 is made in this way, DAGs which should produce the same evaluated value and belong to the same Markov equivalent class, i.e., DAGs that can be represented in the same DAG pattern, may produce different calculated values of BD metric. 
   Accordingly, the assumption N′ ijk =1 is not suitable in a case where the logarithm of the BD metric is taken as an evaluated value as described above and a search is made for an optimum network structure based on the evaluated value. 
   Accordingly, in the present embodiment, the N′ ijk  is determined as follows such that DAGs belonging to the same Markov equivalent class produce the same calculated value of BD metric. 
   First, in a first method, the number of states at nodes X i  is set to r i . Their respective joint probability distributions p (X 0 , X 1 , . . . , X n-1 ) are all calculated according to the following Eq. (4). 
   
     
       
         
           
             
               
                 
                   p 
                   ⁡ 
                   
                     ( 
                     
                       
                         X 
                         0 
                       
                       , 
                       
                         X 
                         1 
                       
                       , 
                       
                         … 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         
                           X 
                           
                             n 
                             - 
                             1 
                           
                         
                       
                     
                     ) 
                   
                 
                 = 
                 
                   1 
                   / 
                   
                     
                       ∏ 
                       
                         i 
                         = 
                         0 
                       
                       
                         n 
                         - 
                         1 
                       
                     
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       r 
                       i 
                     
                   
                 
               
             
             
               
                 ( 
                 4 
                 ) 
               
             
           
         
       
     
   
   Simultaneous occurrence frequencies c (X 0 , X 1 , . . . , X n-1 ) are all set to 1 such that the effect of prior knowledge is minimized. Under this state, N′ ijk  is determined as given by the following Eq. (5). 
   
     
       
         
           
             
               
                 
                   N 
                   ijk 
                   ′ 
                 
                 = 
                 
                   
                     
                       ( 
                       
                         
                           ∏ 
                           
                             i 
                             = 
                             0 
                           
                           
                             n 
                             - 
                             1 
                           
                         
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         
                           r 
                           i 
                         
                       
                       ) 
                     
                     / 
                     
                       r 
                       i 
                     
                   
                   ⁢ 
                   
                     q 
                     i 
                   
                 
               
             
             
               
                 ( 
                 5 
                 ) 
               
             
           
         
       
     
   
   In this first method, the value of the N′ ijk  is increased with increasing the number of nodes n and the number of states r i . Therefore, there is the possibility that the effect N ijk  of the learning data becomes smaller than the effect N′ ijk  of prior knowledge. Accordingly, in a second method, the relationship N′ ijk =0 is introduced to eliminate the effect of the prior knowledge. 
   With respect to the four DAGs shown in  FIG. 14 , evaluated values calculated using N′ ijk  determined by the first and second methods are shown in  FIG. 16 . As shown in  FIG. 16 , in a case where N′ ijk  is determined by the first and second methods, the evaluated values of G 1  to G 3  are all the same. 
   A specific embodiment is described below. In this embodiment, a model of a Bayesian network for inferring behavior of a user by observing the user with a camera mounted to a television receiver (hereinafter abbreviated as the TV receiver) is assumed. The network structure is constructed based on previously prepared learning data. 
   The learning data has been prepared in the manner described below. 
   First, pictures of the user who makes manipulations in front of the TV receiver are taken by the camera. From the input images, four kinds of parameters ((1) FaceDir: (FaceDirection) direction of the face; (2) FacePlace: the position of the face; (3) FaceSize: the size of the face; and (4) OptiFlow (OpticalFlowDirection):motion of the user) have been recognized as shown in  FIGS. 17-20 . With respect to the direction of the face (FaceDir), each input image is divided into 3 segments in the up-and-down direction and into 5 segments in the left-and-right direction as shown in  FIG. 17 . It is assumed that the user&#39;s face is in the center position. There are 16 states in total. That is, the face is directed at any one of the 15 regions. In the 16th state, the user&#39;s face does not exist within the input image. 
   With respect to the position of the face (FacePlace), information about the position of the face indicated by all the learning data is classified, for example, as shown in  FIG. 18  using a vector quantization procedure. Ten states are produced in total. That is, the user&#39;s face is judged to be present in any one of the 9 regions. In the tenth state, the user&#39;s face does not exist in the input image. 
   With respect to the size of the face (FaceSize), five states are produced in total. That is, the size of the user&#39;s face is judged to be closest to any one of 4 sizes shown in  FIG. 19 . In the fifth state, the user&#39;s face is judged not to be present within the input image. With respect to the motion of the user (OptiFlow), nine states are produced in total. That is, the direction of the motion of the user is judged to be closest to any one of the 8 directions shown in  FIG. 20 . In the ninth state, no motion is found in the input image. 
   The results of the recognitions have been labeled in the following four ways: 
   (1) Channel (Communication Channel): whether the user faces the TV receiver. 
   (2) ComSignal (Communication Signal): whether the user is manipulating the TV receiver. 
   (3) UserGoalTV: whether the user is conscious of the TV receiver. 
   (4) UserPresence: whether user is present ahead of the TV receiver. All the labeling results are indicated by binary form: Yes or No. 
   Furthermore, to treat dynamic events, the time sequence in which the aforementioned results of recognitions and labeling operations occur are discussed. A data item occurring at some instant of time is suffixed with “_t — 0”. A data item occurring one tick earlier is suffixed with “_t — 1”. A data item occurring 2 ticks earlier is suffixed with “_t — 2”. One example of expression is “FacePlace_t — 0”. 
   Where the four kinds of results of recognitions and four kinds of label are used each for 3 ticks, the number of nodes is 24. Assuming that the tick interval is 1 second, learning data about 165,000 cases have been prepared from a sequence of motion pictures (30 frames/second) for about 90 minutes. 
   A network structure built using a K2 algorithm based on the learning data is shown in  FIG. 21 . At this time, orders between nodes are set as follows: 
   FacePlace_t — 0, FaceSize_t — 0, FaceDir_t — 0, OptiFlow_t — 0, Channel_t — 0, ComSignal_t — 0, UserGoalTV_t — 0, UserPresence_t — 0, FacePlace_t — 1, FaceSize_t — 1, FaceDir_t — 1, OptiFlow_t — 1, Channel_t — 1, ComSignal_t — 1, UserGoalTV_t — 1, UserPresence_t — 1, FacePlace_t — 2, FaceSize_t — 2, FaceDir_t — 2, OptiFlow_t — 2, Channel_t — 2, ComSignal_t — 2, UserGoalTV_t — 2, UserPresence_t — 2 
   In the present embodiment, added learning of the network structure has been done using the network structure shown in  FIG. 21  as an initial structure and based on the same learning data as the aforementioned learning data. Transition of the network structure during the learning process is shown in  FIGS. 22-25 , which show network structures of the 20th generation, 40th generation, 60th generation, and 80th generation, respectively. As can be seen from  FIGS. 21-25 , the evaluated value (logarithm of BD metric) of elite individuals increased as the generation alteration was repeated. The evaluated value did not vary from the 80th generation to the 200th generation. Consequently, it can be said that a convergence was achieved at about 80th generation and that a quasi-optimum network structure was built. The final orders between the nodes are as follows: 
   FaceDir_t — 0, FaceSize_t — 0, FacePlace_t — 0, Channel_t — 0, OptiFlow_t — 0, UserPresence_t — 0, FaceDir_t — 1, UserGoalTV_t — 0, FaceSize_t — 1, FacePlace_t — 1, ComSignal_t — 1, Channel_t — 2, Channel_t — 1, ComSignal_t — 0, OptiFlow_t — 1, FaceSize_t — 2, FaceDir_t — 2, FacePlace_t — 2, ComSignal_t — 2, OptiFlow_t — 2, UserGoalTV_t — 1, UserGoalTV_t — 2, UserPresence_t — 1, UserPresence_t — 2 
   While the best mode for implementing the present invention has been described so far, the invention is not limited to the above-described embodiments. Of course, various modifications can be made thereto without departing from the scope of the present invention delineated by the accompanying claims.