CN1983308A - Learning apparatus and method - Google Patents

Abstract

A learning device for establishing a network structure of a Bayesian network based on learning data. In Bayesian networks, the relationship between cause and effect among multiple nodes is represented by a directed graph. The learning device includes a storage part that stores learning data and a learning part that builds a network structure based on the learning data. The learning section prepares an initial individual group formed by individuals each having a genotype in which an order among nodes and a relationship between a cause and an effect are specified, repeatedly performs crossover processing and/or mutation processing in the initial individual group based on a genetic algorithm, Calculate the estimated value of each individual based on the learning data, find the best one among the individuals, and use the phenotype of the best individual as the network structure.

Description

Learning equipment and methods

technical field

The present invention relates to a learning device that builds a network structure of a Bayesian network based on data obtained through learning (hereinafter referred to as "learning data") and a method of building the network structure.

Background technique

In recent years, the range of application of information processing technology has expanded, and an information processing mechanism capable of operating according to various environments and various users has become important. That is, dealing with objects with uncertainty (eg, objects that may not have been assumed in advance, or objects that may not have been fully observed) has become increasingly important. Therefore, mechanisms that process intelligent information to understand the environment as precisely as possible and perform appropriate processing may be required even when only uncertain information is available.

Because of these needs, probabilistic models that describe objects of interest using network structures and probabilistically predict objects to be learned from observed events have attracted attention. A Bayesian network in which a relationship (connection) between a cause and an effect is indicated between nodes representing variables by means of a directed graph is a known typical probability model.

[Non-Patent Document 1] Cooper, G, and Herskovits, E., "A Bayesian method for the induction of probabilistic networks from Data (a Bayesian method for induction of probabilistic networks from data)", Machine Learning, Vol.9, pp.309-347, 1992.

[Non-Patent Document 2] Hongjun Zhou, Shigeyuki Sakane, "Sensor Planning for Mobile Robot Localization Using Structure Learning and Inference of BayesianNetwork (Sensor Design for Mobile Robot Localization Using Structure Learning and Inference of Bayesian Network)", Journal of the Japan Robotics Society (Journal of Robotics Society of Japan), Vol.22, No.2, pp.245-255, 2004.

Contents of the invention

In order to apply Bayesian networks to real objects, it is important to build appropriate models.

In many existing embodiments of practical applications, the models are built by utilizing the knowledge and experience of experts versed in the field to be dealt with. What is needed is a method for building the network structure of a Bayesian network based on learning data. However, building a network structure based on learning data is an NP-hard (nondeterministic polynomial-hard, nondeterministic polynomial-hard) problem. Also, it may be necessary to ensure directed acyclicity of the network structure. Therefore, it is not easy to establish an optimal network structure.

Therefore, in order to actually build a network structure, a K2 algorithm using a heuristic has been proposed (see Non-Patent Document 1). The K2 algorithm includes steps: 1) Selecting restricted candidates that can be parent nodes for each node; 2) Selecting a child node, adding candidate parent nodes one by one, and building a network structure; 3) If and only estimating When the value becomes large, adopt this node as a parent node; and 4) If there is no other node that can be added as a parent node, or if the estimated value cannot be increased by the addition of a node, processing goes to other child nodes. Execute the above steps 1) to 4) for each child node. Therefore, a quasi-optimal network structure can be established. In the above step 1), candidates that can become parent nodes of each node are restricted for the following reason. In the case of pre-designing the order among the nodes, the scope of finding the network structure is limited, thus reducing the amount of computation. Moreover, the acyclicity of the network structure is ensured.

Although this K2 algorithm is able to build a network structure in practice, there is also a limitation that the order between nodes may be pre-designed based on the designer's existing knowledge.

On the other hand, a method of determining connections between nodes using a K2 algorithm after determining the order between nodes using a genetic algorithm has also been proposed (see Non-Patent Document 2).

However, with these related art algorithms, a network structure is established by determining connections between nodes in a bottom-up manner according to an order designed by a designer, or according to an order determined using a genetic algorithm. Therefore, these algorithms are not suitable for additive learning of network structures. In addition, many people have some knowledge about connections in addition to being well-versed experts in the field to be dealt with. With related art algorithms, it has been difficult to reflect existing knowledge about connections in the network structure.

In view of such actual conditions in related technologies, when there is an NP-hard problem, it is desirable to provide a learning device and method capable of establishing a network structure (that is, order and connection) of a Bayesian network based on learning data, which The learning device and method can reflect all or some knowledge about the order and connections in the network structure and allow additional learning of the network structure.

According to an embodiment of the present invention, the learning device establishes the network structure of the Bayesian network based on the learning data, and in the Bayesian network, the relationship between the cause and the result among multiple nodes is represented in the form of a directed graph. The learning device includes (a) storage means for storing learning data and (b) learning means for building a network structure based on the learning data. The learning device prepares an initial individual group consisting of individuals each having a genotype in which the order between nodes and the relationship between cause and effect are specified, and is repeatedly executed on the initial individual group based on a genetic algorithm Crossover and/or mutation, calculate an estimated value for each individual based on the learning data, find the best individual, and use the phenotype of the best individual as the aforementioned network structure.

In the learning device according to the above-mentioned embodiment, the genotype can have a plurality of nodes arranged in the first direction according to the prescribed order as parent nodes, and a plurality of nodes arranged in the second direction perpendicular to the first direction according to the prescribed order can be used as parent nodes. Multiple nodes act as child nodes, and the presence or absence of causal and consequential relationships between corresponding nodes is specified by alleles at each gene loci where parent and child nodes interact with each other. correspond.

Another embodiment of the present invention is a learning method for establishing a network structure of a Bayesian network, wherein the Bayesian network represents the relationship between causes and results among multiple nodes in the form of a directed graph. The method begins by preparing an initial population of individuals each having a genotype in which the order between nodes and the relationship between cause and effect are specified. Crossover and/or mutation of the initial population of individuals is repeatedly performed based on a genetic algorithm. Estimates are calculated for each individual based on the learning data and the best individual is found. The phenotype of the best individual is used as the aforementioned network structure.

According to the learning device and method of the embodiments of the present invention, a quasi-optimal network structure can be effectively established when there is an NP-hard problem. Moreover, all or some of the designer's knowledge about the network structure (order and connection) can be reflected in the initial individual group. Furthermore, additional learning of the network structure is enabled.

Description of drawings

FIG. 1 is a schematic diagram of a learning device according to an embodiment of the present invention.

FIG. 2 is a table showing an example of a set of learning data items used when building a Bayesian network model.

3A and 3B are diagrams showing a two-dimensional genotype and an example of its genotype.

Fig. 4 is a flow chart illustrating the process of finding the best individual using the genetic algorithm.

5A and 5B are diagrams illustrating calculation formulas for a BD metric.

6A and 6B are schematic diagrams showing examples of lethal genes generated during sequential crossover and sequential mutation in a classical genetic algorithm.

7A and 7B are schematic diagrams showing an example of connecting crossovers when the order of parents is the same.

8A and 8B are diagrams showing an example of order crossing when the orders of parent individuals are different.

9A and 9B are schematic diagrams showing examples of processing for linking to be mutated.

10A and 10B are schematic diagrams showing an example of processing for sequential mutation.

11A , 11B and 11C are schematic diagrams showing an example in which processing for connection mutation is performed after sequential mutation processing.

12A and 12B are diagrams showing an example in which the number of parent nodes having a cause-and-effect relationship with some child nodes exceeds an upper limit as a result of order crossover processing.

13A and 13B are diagrams showing an example of adjusting genes to prevent the number of parent nodes having a cause-and-effect relationship from exceeding an upper limit.

Fig. 14 shows a schematic diagram of four directed acyclic graphs and estimated values calculated under the condition of N' _ijk =1.

15A and 15B are diagrams illustrating a process of creating learning data used when calculating the estimated value of FIG. 14 .

Figure 16 is a schematic diagram showing four directed acyclic graphs and estimates computed by the process of one embodiment.

Fig. 17 is a schematic diagram illustrating a procedure for obtaining specific learning data.

Fig. 18 is a schematic diagram illustrating a procedure for obtaining specific learning data.

Fig. 19 is a schematic diagram illustrating a procedure for obtaining specific learning data.

Fig. 20 is a schematic diagram illustrating a procedure for obtaining specific learning data.

FIG. 21 is a schematic diagram showing a network structure obtained by the K2 algorithm based on learning data.

FIG. 22 shows a schematic diagram of the network structure of the twentieth generation when additional learning is performed using the network structure of FIG. 21 as the initial structure.

FIG. 23 shows a schematic diagram of the fortieth generation network structure when additional learning is performed using the network structure in FIG. 21 as the initial structure.

FIG. 24 shows a schematic diagram of the network structure of the 60th generation when additional learning is performed using the network structure of FIG. 21 as the initial structure.

FIG. 25 shows a schematic diagram of the eightieth generation network structure when additional learning is performed using the network structure in FIG. 21 as the initial structure.

Detailed ways

Specific embodiments of the present invention will be described in detail below with reference to the accompanying drawings. In one embodiment, the present invention is applied to a learning device that constructs a network structure of a Bayesian network based on data on learning (learning data).

First, the structure of a learning device according to an embodiment of the present invention is schematically shown in FIG. 1 . As shown in FIG. 1 , the learning device 1 according to the present embodiment includes a learning data storage section 10 , a learning section 11 and a model storage section 12 .

Learning data used in building the Bayesian network model is stored in the learning data storage section 10 . One embodiment of a corpus of discrete data is shown in Figure 2, with five nodes from _X0 to _X4 . In Fig. 2, each entry of learning data is represented in the form _Xijk , where i denotes the node ID, j denotes the event ID (i.e., the data entry number counted from the first obtained learning ^data entry), and k denotes the state ID (i.e., in the state of each node). That is, X _i ^jk represents the state of the learning data item obtained at node _Xi , and the j-th data item is represented by state ID=k.

Based on the learning data stored in the learning data storage section 10, the learning section 11 constructs a Bayesian network model. Specifically, the learning section 11 simultaneously determines the order among the nodes constituting the network structure of the Bayesian network and connects both by using a genetic algorithm. When there are NP-hard problems, the use of genetic algorithms makes it possible to efficiently construct quasi-optimal network structures. The model established by the learning section 11 is stored in the model storage section 12 .

The processing by the learning section 11 for constructing the network structure will be specifically described below. Next, for simplicity, assume that there are 5 nodes, from X ₀ to X ₄ .

According to the present invention, the learning section 11 represents individuals used in the network structure of the Bayesian network, that is, the genetic algorithm, based on the two-dimensional genotype as shown in FIG. 3A. In FIG. 3A, X ₀ , X ₁ , X ₂ , X ₃ and X ₄ in rows and columns indicate the order among nodes. The order in rows and columns is always the same. Gene positions located in the triangular region above the diagonal part have alleles '0' and '1', which represent 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 a cause and effect relationship exists between a parent node and a child node. Each diagonal section corresponds to a self-loop. Gene positions located in the triangular region below the diagonal part have alleles "0" and "1", which represent connections from child nodes to parent nodes. In order to ensure the acyclicity of the network structure, it is assumed that the genes located below the diagonal part have no trait expression. Thus, an individual with a two-dimensional genotype as shown in Figure 3A has a phenotype as shown in Figure 3B.

The learning section 11 regards many individuals having such two-dimensional genotypes as an initial individual group. Use genetic algorithm to find the best individual in the initial individual group. Individual phenotypes were taken as quasi-optimal network structures.

The process of finding the best individual using the genetic algorithm will be described in the flowchart of FIG. 4 .

First, at step S1, the learning section 11 creates an initial group of individuals. At this time, the learning section 11 may randomly create an initial individual group. In the case of a designer with knowledge about the network structure (order and connection), an initial population of individuals is created by converting phenotypes into two-dimensional genotypes and performing mutation processing. The latter approach allows the designer's knowledge about the network structure to be fully or partially reflected in the initial population of individuals. Also, the learning section 11 may create an initial individual group from the individuals represented by the learning results. In this case, additional learning of the network structure is enabled.

Then, at step S2 , the learning section 11 calculates an estimated value for each individual based on the learning data stored in the learning data storage section 10 (fitting in the genetic algorithm). Specifically, the BD measure (P(D|B _s )) was calculated according to the following formula (1), and the logarithm of the calculated value was taken as an estimated value.

$\mathrm{<span\; class="notranslate">\; P</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; D.</span>}<span\; class="notranslate">\; |</span>{\mathrm{<span\; class="notranslate">\; B</span>}}_{\mathrm{<span\; class="notranslate">\; the\; s</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 0</span>}}{\overset{\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; \&Pi;</span>}}}\underset{\mathrm{<span\; class="notranslate">\; j</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 0</span>}}{\overset{{\mathrm{<span\; class="notranslate">\; q</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; \&Pi;</span>}}}\frac{\mathrm{<span\; class="notranslate">\; \&Gamma;</span>}<span\; class="notranslate">\; (</span>{{\mathrm{<span\; class="notranslate">\; N</span>}}^{<span\; class="notranslate">\; \&prime;</span>}}_{\mathrm{<span\; class="notranslate">\; ij</span>}}<span\; class="notranslate">\; )</span>}{\mathrm{<span\; class="notranslate">\; \&Gamma;</span>}<span\; class="notranslate">\; (</span>{{\mathrm{<span\; class="notranslate">\; N</span>}}^{<span\; class="notranslate">\; \&prime;</span>}}_{\mathrm{<span\; class="notranslate">\; ij</span>}}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; N</span>}}_{\mathrm{<span\; class="notranslate">\; ij</span>}}<span\; class="notranslate">\; )</span>}\underset{\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 0</span>}}{\overset{{\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; \&Pi;</span>}}}\frac{\mathrm{<span\; class="notranslate">\; \&Gamma;</span>}<span\; class="notranslate">\; (</span>{{\mathrm{<span\; class="notranslate">\; N</span>}}^{<span\; class="notranslate">\; \&prime;</span>}}_{\mathrm{<span\; class="notranslate">\; ijk</span>}}<span\; class="notranslate">\; +</span>{\mathrm{<span\; class="notranslate">\; N</span>}}_{\mathrm{<span\; class="notranslate">\; ijk</span>}}<span\; class="notranslate">\; )</span>}{\mathrm{<span\; class="notranslate">\; \&Gamma;</span>}<span\; class="notranslate">\; (</span>{{\mathrm{<span\; class="notranslate">\; N</span>}}^{<span\; class="notranslate">\; \&prime;</span>}}_{\mathrm{<span\; class="notranslate">\; ijk</span>}}<span\; class="notranslate">\; )</span>}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>$

In this formula (1), D is the learning data stored in the learning data storage part 10, B _s represents the individual used in the network structure of the Bayesian network, that is, the genetic algorithm, and P(D|B _s ) is the The probability of D under the condition of B _s , Γ is a gamma (gamma) function and by Γ(n)=(n-1)! give. From (n-1)! =n! /n, think 0! = 1! /1=1. Therefore, for convenience, the relation 0! =1. Also, as shown in FIG. 5A, let n be the number of nodes. Let _Xi be the ith node. Let v _ik be the kth value that _Xi can assume. Let _ri be the number of values (number of states) that _Xi can assume. As shown in FIG. 5B, let Π _i be the parent pattern of X _i . Let W _ij be the jth pattern (value that can be assumed) of Π _i . q _i is the number of patterns of Π _i . N _ijk is the number of data _entries in the learning data D such that Xi has the value vi _ik and Π _i has the value w _ij . N _ij is calculated according to the following formula (2). N' _ijk and N' _ij are related to the prior knowledge of the designer and can be handled in a similar manner to N _ijk and N _ij . Their specific contents will be described below.

${\mathrm{<span\; class="notranslate">\; N</span>}}_{\mathrm{<span\; class="notranslate">\; ij</span>}}<span\; class="notranslate">\; =</span>\underset{\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 0</span>}}{\overset{{\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}{\mathrm{<span\; class="notranslate">\; N</span>}}_{\mathrm{<span\; class="notranslate">\; ijk</span>}}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 2</span>}<span\; class="notranslate">\; )</span>$

Actually, the learning data stored in the learning data storage section 10 may have missing data entries or may be continuous quantities instead of discrete data. For example, in Richard E. Neapolitan, "LEARNING BAYESIAN NETWORKS", ISBN 0-13-012534-2, describes a method for dealing with missing data entries or consecutive quantities.

Next, at step S3, the learning section 11 makes a decision as to whether or not the end condition is satisfied.

In fact, an example of an end condition is that the number of generations has exceeded a threshold. Another example is when the rate of change of the estimated value decreases below a threshold. If the end condition is not satisfied, control goes to S4. If the end condition is satisfied, the individual producing the highest estimate is selected and the process ends.

Next, at step S4, the learning section 11 selects the next group of individuals from the current group of individuals based on the estimated value. That is, when the permits overlap, the learning section selects the desired number of individuals from the current individual population based on the estimated value. Methods generally used in genetic algorithms such as roulette wheel selection, tournament selection, and elite reservation can be used as the selection method. However, the logarithm of the BD metric as an estimated value is negative, and thus it is difficult to directly utilize a method of performing a selection with a probability ratio on an estimated value such as a rotary wheel selection. Therefore, the estimated values are pre-converted to positive values using a Boltzmann distribution.

Next, in steps S5 and S6, the learning section 11 executes a process of intersecting individuals contained in the current individual group in accordance with a desired intersecting probability. Also, the learning section performs mutation processing according to a desired mutation rate. In this intersection process, two child individuals are created from two parent individuals. In mutation processing, a child individual is created from a parent individual. At the same time, the created child individual can replace the parent individual. It is possible to make child individuals and parent individuals coexist.

In particular, in the processing of sequential crossover and processing of sequential mutation, in the case of the classical process using the genetic algorithm, as shown in FIGS. 6A and 6B , it is easy to generate a lethal gene. For example, as shown in FIG. 6A , when individuals with the order X ₀ , X ₁ , X ₂ , X ₃ , and X ₄ and individuals with the order X ₃ , X ₁ , X ₀ , X ₄ , and X ₂ are used in the third In the case where a point between the node and the fourth node is intersected as an intersection point, a node having the same node ID exists in the same individual, resulting in the generation of a lethal gene. Moreover, as shown in FIG. 6B , in the case of performing a process of generating a mutation at position X ₂ of an individual having the order X ₀ , X ₁ , X ₂ , X ₃ and X ₄ to generate X ₄ , in the same individual A node with the same node ID appeared. This causes the lethal gene. In the case where lethal genes are easily produced in this way, the learning efficiency is low. Therefore, a framework to prevent the production of lethal genes is necessary.

When using genetic algorithms to build the network structure of Bayesian networks, order crossover or order mutation is essentially equivalent to the traveling salesman problem, and various methods have been proposed (see, by P.Larranaga, C.Kuijpers , R.Murga and Y.Yurramendi, "Learning Bayesian Network Structure Using Genetic Algorithms to Find the Best Order", IEEE Transactions on Systems, Man and Cybemetics (IEEE Systems, People, and Cybernetics Transactions), 26(4 ), pp.487-493, 1996).

Next, first, the intersection processing at step S5 when a specific example occurs will be described.

An example of crossover processing where the parent individuals have the same order is shown in Figures 7A and 7B. In this cross processing, only joins are processed. As shown in FIG. 7A , with respect to two parent individuals having the order X ₀ , X ₁ , X ₂ , X3 and X ₄ , the point between the third and fourth nodes serves as the intersection point. Subsequent genes are exchanged. As a result, child individuals as shown in Fig. 7B are obtained. As can be seen from Figure 7B, the connection of the parent individuals is inherited genetically to the daughter individuals.

An example of sequence crossover processing where parent individuals have different orders is shown in FIGS. 8A and 8B . For processing of order intersection, for example, PMX (Partial Mapping Intersection) can be used. In this PMX, 1) two intersections are randomly selected, 2) nodes are swapped between two intersections, 3) if each node is not used within an individual (3-1), then the node is used intact, if the node is already used (3-2), then it is swapped with the node from which the unswapped node is to be mapped, if the node is also already used (3-3 ), then the node is swapped with the node from which the unswapped node is to be mapped. At this point, the switched node inherits the connection to the parent node or to the child nodes of the parent node itself. As shown in Figure 8A, regarding a parent individual with the order X ₀ , X ₁ , X ₂ , X ₃ and X ₄ and another parent individual with the order X ₂ , X ₀ , X ₄ , X ₃ and X ₁ , if Nodes respectively between the second and third nodes and between the intersection points between the fourth and fifth nodes are exchanged according to the PMX method, and then a sub-individual as shown in FIG. 8B is obtained. As can be seen from Figure 8B, the order and linkage of the parent individuals has been inherited genetically to the daughter individuals.

In the case of parent individuals having the same order as shown in FIG. 7A, if order crossing is performed according to the PMX process, then the same child individuals as in FIG. 7B are obtained. That is, the processing of connection intersections shown in FIGS. 7A and 7B is a specific case in the processing of order intersections (ie, parents have the same order). Only when processing for sequence crossing is performed, processing for connection crossing is also performed.

Next, the mutation processing in step S6 is described using a specific example.

An example of processing for linking mutations is shown in Figures 9A and 9B. This processing for junctional mutations is achieved by inverting genes at arbitrary gene positions to alleles. As shown in Figure 9A, with respect to parent individuals with the order X ₀ , X ₁ , X ₂ , X ₃ and X ₄ , if the gene at the gene position in the case where the parent node is X ₃ and the child node is X ₁ "0" is inverted to allele "1", and if the gene "1" at the gene position in the case where the parent node is X ₄ and the child node is X ₀ is inverted to allele "0", then A child individual as shown in Figure 9B is obtained.

An example for sequential mutation processing is shown in Figures 10A and 10B. For example, inversion mutagenesis (IVM) can be used for the treatment of sequential mutations. This inversion mutation (IVM) involves 1) randomly selecting a number of consecutive consecutive nodes and removing them, and 2) reversing the order of the removed nodes and inserting the order at random positions. As shown in FIG. 10A , with respect to parent individuals having the order X ₀ , X ₁ , X ₂ , X ₃ and X ₄ , two consecutive nodes X ₂ and X ₃ are selected and removed. Their order is reversed. If the sequence is then inserted after _X4 , a child individual as shown in Figure 10B is obtained.

Since the processing for link mutation shown in FIGS. 9A and 9B and the processing for sequential mutation shown in FIGS. 10A and 10B are independent of each other, both types of processing can be performed. However, the obtained sub-individuals differ depending on which type of processing is performed first. An example of the process of performing link mutation after the process of performing sequential mutation is shown in FIGS. 11A-11C . As shown in FIG. 11A , with respect to parent individuals with the order X ₀ , X ₁ , X ₂ , X ₃ and X ₄ , two consecutive nodes X ₂ and X ₃ are selected and removed. Their order is reversed and then inserted after _X4 . That is, processing for sequential mutation is performed. As a result, individuals as shown in Fig. 11B were obtained. Also, with respect to this individual, the gene "0" at the gene position in the case where the parent node is _X3 and the child node is _X1 is reversed to the allele "1". Gene "1" at a gene position where parent node is _X4 and child node is _X0 is inverted to allele "0". That is, processing for connection mutation is performed. As a result, individuals as shown in Fig. 11C were obtained.

Referring back to FIG. 4, the number of parent nodes is limited in step S7, and then the process jumps back to step S2. That is, for each child node of each individual, an upper limit (MaxFanIn) is set in advance with respect to the number of parent nodes (FanIn) having a cause-and-effect relationship with itself. If, as a result of the processing for crossover and processing for mutation at steps S5 and S6, the number of parent nodes having causal and consequential relationships with any child node exceeds the upper limit, the gene is thus adjusted to maintain the relationship FanIn≤MaxFanIn . Examples are shown in Figures 12A, 12B, 13A and 13B, where the number of parent nodes is limited in this way. As shown in Figure 12A, regarding a parent individual with the order X ₀ , X ₁ , X ₂ , X ₃ and X ₄ and another parent individual with the order X ₂ , X ₀ , X ₄ , X ₃ and X ₁ , if Nodes respectively located between the intersections between the second and third nodes and between the fourth and fifth nodes are exchanged according to the PMX process, and then sub-individuals as shown in FIG. 12B are obtained. In this figure, regarding the child individual on the left, the number of parent nodes (FanIn) having a cause-and-effect relationship with the child node X ₀ is 4, which exceeds the upper limit (MaxFanIn)3. Therefore, by selecting the gene "1" at the gene position where the parent node is X ₃ and the child node is X ₀ in the individual shown in Figure 13A, and inverting the selected gene "1" to the allele "0", to generate individuals as shown in Fig. 13B, so as to realize the relationship of FanIn≤MaxFanIn.

When genes are inverted to their alleles, the FanIn≤MaxFanIn relationship is achieved, and the inverted genes can be randomly selected. Selection can also be made to maximize individual estimates. In the latter case, it may be necessary to compute estimates about individuals with child nodes whose number of parents exceeds an upper limit. With respect to this individual, it may not be necessary to calculate the estimated value at step S2. The estimated value calculated in step S7 can be utilized.

Thus, according to the learning device 1 of the present embodiment, a certain number of individuals with two-dimensional The genotype individuals are used as the initial individual group, and the genetic algorithm is used to find the best individual in the initial individual group, and the individual phenotype is used as the network structure of the Bayesian network, and a quasi-optimal network that is effective for NP-hard problems can be established structure.

Furthermore, by converting the phenotype into a two-dimensional genotype and performing mutation processing in the case that the designer has knowledge about the network structure (order and connection), the learning device 1 makes it possible to fully or partially reflect the designer's knowledge about the individual at the initial stage. Knowledge of the network structure in the group. In the case where it is desired to fix the order and connection at some nodes, individuals with two-dimensional genotypes different from the fixed order and connection are regarded as lethal genes and removed from the selection objects in the above step S4.

Furthermore, the learning device 1 can perform additional learning of the network structure by creating an initial individual group from individuals obtained as a result of learning.

In the description of the flowchart explanatory diagram in FIG. 4 , the learning device 11 executes crossover processing and mutation processing. It is also possible to perform only one of the two types of processing.

As shown in Equation (1), the BD metric mainly consists of (i) N _ijk determined by the network structure and learning data and (ii) N′ _ijk determined by the designer's prior knowledge. In general, where the designer's prior knowledge can be defined for all i's and j's about some node _Xi and their parent nodes such as p(vi _ik , w _ij ), then according to the following Formula (3) calculates N' _ijk . In formula (3), N' is an equivalent sample size, and is a parameter assuming how many samples are used to represent information obtained from existing knowledge.

N' _ijk = p( _vik , w _ij )×N' (3)

In the case where the designer has prior knowledge about the network structure, the designer's prior knowledge can be reflected by substituting N' _ijk calculated in this way into the above formula (1).

Meanwhile, in the case where the designer does not have such prior knowledge, the BD metric is generally calculated under the condition of N' _ijk =1. The BD metric calculated under the condition of N' _ijk =1 is especially called K2 metric.

However, assuming N′ _ijk = 1 in this way, if the directed acyclic graph (DAG) belongs to the same Markovian (Morkov) equivalent class leading to the same inference result, then the calculation of the directed acyclic graph The resulting BD metric may also be different.

As an example, now consider the network structure composed of four nodes of cloudy sky, sprinkler, rain and wet grass as shown in Fig.14.

In the directed acyclic graph (DAG) shown in Figure 14, G1 to G3 have the same link and have the same uncoupled head-to-head meeting (sprinkler → wet grass ← rain), and thus, these three graphs can be represented by the same DAG schema gp. However, G4 has the same linkage as G1 to G3, but has an additional uncoupled head-to-head encounter (sprinkler → cloudy → rainy) and thus cannot be represented in the DAG schema gp. Also shown in FIG. 14 are estimated values (logarithms of the BD metric) calculated under the condition of N' _ijk =1 when some learning data are given to the four DAGs.

As shown in FIG. 15A , the learning data is created in such a way that a DAG with a conditional probability table (CPT) is used below. That is, on the cloudy sky which is the highest-level node of the parent-child relationship, based on the conditional probability table, it is first probabilistically determined whether the node is true or false. Now assume Cloudy=True. In each of sprinklers and rain as child nodes of cloudy, a conclusion is then made probabilistically as to whether that node is true or false based on the conditional probability table in the parent condition. Here it is assumed that Sprinklers=False and Raining=True. Then at Wet Grass, which is a child node of Sprinkler and Rain, probabilistically determine whether the node is true or false based on the conditional probability table under the parent condition. In this way, learning data on an event is created. As shown in Fig. 15B, learning data on 1000 events was similarly created.

As shown in Fig. 14, where the assumption of N' _ijk = 1 is made, the estimated values of G1 and G3 are different from the estimated value of G2. Assuming N' _ijk =1 in this way, DAGs that should produce the same estimated value and belong to the same class of Markov equations, ie DAGs that can be represented in the same DAG mode, can produce different calculated values of the BD metric.

Therefore, when taking the logarithm of the BD metric as an estimated value and finding an optimal network structure based on the estimated value as described above, it is inappropriate to assume N' _ijk =1.

Therefore, in this embodiment, N' _ijk is determined such that DAGs belonging to the same Markov equation class produce the same calculated value of the BD metric.

First, in the first method, the number of states at node _Xi is set to r _i . All their respective connection probability distributions p(X ₀ , X ₁ , . . . , X _n-1 ) are calculated according to the following formula (4).

$\mathrm{<span\; class="notranslate">\; p</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; 0</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; x</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; \&Lambda;x</span>}}_{\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; /</span>\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 0</span>}}{\overset{\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; \&Pi;</span>}}}{\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 4</span>}<span\; class="notranslate">\; )</span>$

The simultaneous occurrence frequencies c(X ₀ , X ₁ , . . . , X _n-1 ) are all set to 1 to minimize the influence of existing knowledge. In this state, N' _ijk is determined by the formula (5) given below.

${\mathrm{<span\; class="notranslate">\; N</span>}}_{\mathrm{<span\; class="notranslate">\; ijk</span>}}^{<span\; class="notranslate">\; \text{'}</span>}<span\; class="notranslate">\; =</span><span\; class="notranslate">\; (</span>\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 0</span>}}{\overset{\mathrm{<span\; class="notranslate">\; no</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; \&Pi;</span>}}}{\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; /</span>{\mathrm{<span\; class="notranslate">\; r</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}{\mathrm{<span\; class="notranslate">\; q</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; -</span><span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; 5</span>}<span\; class="notranslate">\; )</span>$

In this first method, the value of N' _ijk increases as the number of nodes n increases and the number of states r _i increases. Therefore, there is a possibility that the influence N _ijk of the learning data becomes smaller than the influence N′ _ijk of the existing knowledge. Therefore, in the second method, the relation of N' _ijk =0 is introduced to eliminate the influence of existing knowledge.

Regarding the four DAGs as shown in FIG. 14 , FIG. 16 shows N′ _ijk determined by the first and second methods to calculate estimated values. As shown in FIG. 16, in the case where N' _ijk is determined by the first and second methods, the estimated values of G1 to G3 are all the same.

A specific embodiment is described below. In this embodiment, a Bayesian network model in which user behavior is inferred by observing the user through a camera mounted to a television receiver (hereinafter abbreviated as TV receiver) is assumed. Build the network structure based on the previously prepared learning data.

The learning data has been prepared in the manner described below.

First, a photo of a user operating in front of a TV receiver is captured by a video camera. From the input image, four types of parameters have been recognized as shown in Figures 17-20 ((1) FaceDir: (FaceDirection) the direction of the face; (2) FacePlace: the position of the face; (3) FaceSize: the size of the face; and (4) OptiFlow (OpticalFlowDirection): user's motion). Regarding the direction of the face (FaceDir), as shown in FIG. 17 , each input image is divided into 3 segments in the up-down direction and into 5 segments in the left-right direction. Assume the user's face is at the center. There are 16 states in total. That is, the face is oriented in any one of 15 regions. In state 16, the user's face does not exist in the input image.

Regarding the position of the face (FacePlace), the information on the face position indicated by all the learning data is classified, for example, employing a vector quantization process as shown in FIG. 18 . A total of 10 states are generated. That is, it is determined that the user's face exists in any one of the nine areas. In state 10, the user's face does not exist in the input image.

Regarding the size of the face (FaceSize), a total of 5 states are generated. That is, it is determined that the size of the user's face is closest to any one of the 4 sizes shown in FIG. 19 . In the fifth state, it is determined that the user's face does not exist in the input image. With respect to the user's motion (OptiFlow), a total of 9 states are generated. That is, it is determined that the user's motion direction is closest to any one of the eight directions as shown in FIG. 20 . In state 9, no motion is found in the input image.

The results of cognition are marked in the following four ways:

(1) Channel (communication channel): whether the user is facing the TV receiver.

(2) ComSignal (communication signal): Whether the user is operating the TV receiver.

(3) UserGoalTV: Whether the user is aware of the TV receiver.

(4) UserPresence: whether the user appears before the TV receiver. All flagged outcomes are represented as binary yes or no.

Furthermore, in order to deal with dynamic events, the aforementioned cognitive results are discussed as well as the timing at which marking operations occur. Data entries that occur at a certain time are suffixed with "_t_0". Data entries that occurred one time unit (tick) ago are suffixed with "_t_1". Data entries that occurred two time units ago are suffixed with "_t_2". An example of a representation is "FacePlace_t_0".

The number of nodes is 24 in the case of four cognitive outcomes and four markers each for 3 time units. Assuming that the time unit interval is 1 second, learning data on 165,000 events has been prepared from about 90 minutes of moving picture sequences (30 frames/second).

Based on the learning data as shown in FIG. 21, the network structure is established using the K2 algorithm. At this time, the order among the nodes is 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_1FaceSize_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 this embodiment, additional learning of the network structure is performed using the network structure shown in FIG. 21 as the initial structure and based on the same learning data as the aforementioned learning data. The network structure changes during the learning process are shown in Figs. 22-25, showing the network structures of the 20th generation, 40th generation, 60th generation and 80th generation, respectively. From Figures 21-25, it can be seen that the estimated value (logarithm of the BD metric) of elite individuals increases as the iteration changes. Estimates do not change from generation 80 to generation 200. Therefore, it can be said that convergence is reached at about the 80th generation and a quasi-optimal network structure is established. The final order among the nodes is 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。

Although the best mode for carrying out the invention has been described so far, the invention is not limited to the above-described embodiments. Various modifications can, of course, be made without departing from the scope of the invention as outlined in the claims.

Cross References to Related Applications

The present application contains subject matter related to Japanese Patent Applications JP2005-317031 and JP2006-116038 filed in the Japan Patent Office on Oct. 31, 2005 and April 19, 2006, respectively, the entire contents of which are hereby incorporated by reference.

Claims (10)

1. facility for study is used for setting up based on learning data the network structure of Bayesian network, represents cause between a plurality of nodes and the relation between the result by digraph in Bayesian network, and described facility for study comprises:

Memory storage, the storage learning data; And

Learning device is used for setting up network structure based on learning data;

Wherein, described learning device prepares all have the initial stage groups of individuals that genotypic individuality is formed by each, order between the node and the relation between cause and the result in this genotype, have been stipulated, repeatedly carry out intersection and/or sudden change processing on the groups of individuals in the early stage based on genetic algorithm, calculate each individual estimated value based on learning data, seek best body one by one, and with the phenotype of this optimized individual as network structure.

2. facility for study as claimed in claim 1, wherein, described genotype order according to the rules will be arranged in a plurality of nodes on the first direction as close node, with according to the rules sequencing perpendicular to a plurality of nodes on the second direction of first direction as child node, and the existence by coming cause between the regulation respective nodes and result relation at the allele on each gene location or do not exist, each close node and each child node are corresponding mutually on this gene location.

3. facility for study as claimed in claim 2, wherein, child node have for or the gene at gene location place that is higher than the order of close node order show the performance do not have feature.

4. facility for study as claimed in claim 2, wherein, have under the situation that outnumbers given number of close node of cause and result relation with the anyon node, gene at least one gene location that described learning device will be associated with this child node is reversed to its allele, makes the number that has a close node of cause and result relation with child node become littler than given number.

5. facility for study as claimed in claim 1, wherein, whole or some existing knowledge of described initial stage groups of individuals reflection deviser.

6. facility for study as claimed in claim 1, wherein, described initial stage groups of individuals is based on the individuality that obtains as learning outcome.

7. facility for study as claimed in claim 1, wherein, described estimated value is the logarithm of BD tolerance, and wherein, i node in n node is as child node X _iThe time, child node X _iCan be from v _I0To v _Iri-1Suppose r _iThe value, and with child node X _iModel number with the value that can suppose of all close nodes of cause and result relation is q _iIf, child node X _iValue be v _IkAnd the generation data are wherein with child node X _iThe value of all close nodes with cause and result relation is supposed the j pattern, then according to following formula calculate the times N of before obtaining learning data, expecting ' _Ijk:

${N\text{'}}_{\mathrm{ijk}}=\left(\underset{i=0}{\overset{n-1}{\mathrm{\&Pi;}}}{r}_i\right)/r_i{q}_i.$

8. facility for study as claimed in claim 1, wherein, described estimated value is the logarithm of BD tolerance, and wherein, the i node in n node is as child node X _iThe time, child node X _iCan be from v _I0To v _Iri-1Suppose r _iThe value, and with child node X _iThe number of pattern with the value that can suppose of all close nodes of cause and result relation is q _iIf, child node X _iValue be v _IkAnd the generation data, wherein with child node X _iThe value of all close nodes with cause and result relation is assumed to the j pattern, then before learning data obtains the times N of expection ' _IjkBe set to equal zero (N ' _Ijk=0).

9. set up the learning method of the network structure of Bayesian network based on learning data for one kind, in described Bayesian network, be illustrated between cause between a plurality of nodes and the result by digraph and concern that this learning method comprises step:

Preparation all has the initial stage groups of individuals that genotypic individuality is formed by each, has stipulated the relation between the order between a plurality of nodes and cause and result in described genotype;

Repeat the processing that intersects and/or suddenly change on the groups of individuals in the early stage based on genetic algorithm;

Calculate each individual estimated value based on learning data;

One of the best in the searching individuality; And

With the phenotype of this optimized individual as network structure.

10. facility for study is used for setting up based on learning data the network structure of Bayesian network, in described Bayesian network, is illustrated in cause between a plurality of nodes and the relation between the result by digraph, and described facility for study comprises:

Storage area, the storage learning data; And

The study part is operable as based on learning data and sets up network structure;

Wherein, described study part prepares all have the initial stage groups of individuals that genotypic individuality is formed by each, order between the node and the relation between cause and the result in described genotype, have been stipulated, repeat intersection and/or sudden change processing on the groups of individuals in the early stage based on genetic algorithm, calculate each individual estimated value based on learning data, seek one of the best in the individuality, and with the phenotype of optimized individual as network structure.

Images