Inverse model calculation apparatus and inverse model calculation method

• US 20050096880A1
• Filed: 09/01/2004
• Published: 05/05/2005
• Est. Priority Date: 09/02/2003
• Status: Abandoned Application

• Current Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Original Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Inventors: Hatano, Hisaaki, Morita, Chie, Nakase, Akihiko
• Application Number:
  US10/930,766
• Publication Number:
  US 20050096880A1
• Time in Patent Office: Days
• US Class Current: 702/189
• CPC Class Codes: G06N 5/04 Inference or reasoning models

Abstract

An inverse model calculation apparatus and method according to an embodiment of the present invention record an input value inputted sequentially to a target system and an output value outputted sequentially from the target system as time series data, generate a decision tree for inferring an output value at future time, using the time series data, detect a leaf node having an output value at future time as a value of an object variable from the decision tree, and acquire a condition of explaining variables included in a rule associated with a path from a root node of the decision tree to the detected leaf node, as a condition for obtaining the output value.

Claims

1. An inverse model calculation apparatus for finding a condition under which a target system outputs a certain output value, the target system outputting the certain output value on the basis of an input value to the target system, the inverse model calculation apparatus comprising:

a time series data recording section which records an input value inputted sequentially to the target system and an output value outputted sequentially from the target system as time series data;

a decision tree generation section which generates a decision tree for inferring an output value at future time, using the time series data; and

a condition acquisition section which detects a leaf node having an output value at future time as a value of an object variable from the decision tree, and acquires a condition of explaining variables included in a rule associated with a path from a root node of the decision tree to the detected leaf node, as a condition for obtaining the output value.

2. The inverse model calculation apparatus according to claim 1, wherein

the target system outputs the output values of a plurality of items in response to the inputted input value, and the time series data recording section records the sequentially inputted input value and the sequentially outputted output values of the plurality of items as the time series data,

the decision tree generation section generates the decision tree regarding the item as object variable for every item, using the time series data,

the inverse model calculation apparatus further comprises a decision tree combination section combining the decision trees generated for the items to generate a composite decision tree having a set of object variables of the decision trees as one object variable, and

the condition acquisition section detects a leaf node having output values of the plurality of items at future time as a value of an object variable from the composite decision tree, and acquires a condition of explaining variables included in a rule associated with a path from a root node of the composite decision tree to the detected leaf node, as a condition for obtaining the output values of the items.

3. The inverse model calculation apparatus according to claim 2, wherein the decision tree combination section comprises:

a first processing section which implements inputting values of explaining variables to the decision trees and obtaining a value of a object variable from the decision trees respectively, a plurality of times; and

a second processing section which regards a set of values of the object variables obtained from the decision trees each time, as a value of one item, and which generates a decision tree having the one item as an object variable by using the values of explaining variables inputted to the decision trees and the values of object variables obtained from the decision trees.

4. The inverse model calculation apparatus according to claim 2, wherein the decision tree combination section comprises:

a root node decision section which acquires paths from a root node to leaf nodes from each of the decision trees, which generates a plurality of path sets by combining paths acquired from the decision trees between different decision trees, and which determines a node other than leaf nodes, that is most included in the plurality of path sets, as a root node of the composite decision tree;

a root node value decision section which specifies values for the determined root node, on the basis of the path sets including the determined root node, and which adds branches having the specified values to the determined root node;

a path set detection section which selects the branch added to the root node, and which detects path sets having the root node and the selected branch from among the path sets including the determined root node;

a node detection section which detects a node other than leaf nodes, that is most included except the root node in the detected path sets and add the detected node to the selected branch; and

a node value decision section which specifies a value for the detected node, using the detected path sets including the node detected by the node detection section, and which adds a branch having the specified value to the detected node;

wherein

the path set detection section selects the branch added by the node value decision section, and detects the path set having nodes and branches included in a path from the root node to the selected branch,

in the case where the number of the detected path set is at least 2,

the node detection section detects a node other than leaf node, that is most included except nodes included in the path from the root node to the selected branch, from the detected path sets and adds the detected node to the selected branch,

the node value decision section specifies a value for the detected node, using the detected path sets including the detected node, and adds a branch having the specified value to the detected node,

the path set detection section selects the added branch, and detects the path set having nodes and branches included in a path from the root node to the selected branch,

in the case where the number of the detected path set is less than 2,

the node detection section adds a node having a set of values of leaf nodes included in the detected path set to the selected branch as a leaf node of the composite decision tree,

the path set detection section selects a branch having no leaf node from the composite decision tree in the middle of generation in the case where there is a branch having no leaf node, and detects the path set having nodes and branches included in a path from the root node to the selected branch.

5. The inverse model calculation apparatus according to claim 2, wherein the decision tree combination section comprises:

a root node generation section which generates a composite node that is a set of root nodes in the decision trees, as a root node of the composite decision tree;

a root node value generation section which detects values that the root nodes in the decision trees have respectively, which generates a node value sets by combining the detected values between different decision trees, and which adds branches having the node value sets to the generated root node;

a node generation section which selects the added branch, which generates a set of nodes other than leaf nodes, following branches of the decision trees corresponding to the selected branch, as a composite node, in the case whether nodes other than leaf nodes are included in nodes following branches of the decision trees corresponding to the selected branch, and which adds this composite node to the selected branch;

a node value generation section which detects values that nodes constituting the composite node have on the base of the decision trees, which generates a node value set by combining the detected values between different decision trees, and which adds a branch having the node value set to the composite node;

a leaf node generation section which selects the added branch, which specifies paths in the decision trees corresponding to a path from the root node generated by the root node generation section to the selected branch, in the case where nodes other than leaf nodes are not included in nodes following branches of the decision trees corresponding to the selected branch, and which adds a node including a set of values of leaf nodes in the specified paths, to the selected branch as a leaf node of the composite decision tree.

6. The inverse model calculation apparatus according to claim 2, wherein the decision tree combination section further comprises:

a calculation section which selects a path from a root node to a leaf node from the composite decision tree, which detects paths corresponding to the selected path from the decision trees, and which calculates a probability that rules associated with the detected paths hold;

an inference section which infers a probability that rule associated with the selected path hold, on the basis of holding probabilities of the rules; and

a deletion section which deletes the selected path from the composite decision tree in the case where the inferred probability does not satisfy a predetermined reference.

7. The inverse model calculation apparatus according to claim 1, further comprising:

an input value generation section which generates an input value inputted to the target system, in the case where the condition acquired by the condition acquisition section is an input condition at future time, on the base of the input condition.

8. An inverse model calculation apparatus for finding a condition under which a target system outputs a certain output value, the target system outputting the certain output value on the basis of an input value to the target system, the inverse model calculation apparatus comprising:

a time series data recording section which records an input value inputted sequentially to the target system and an output value outputted sequentially from the target system as time series data;

a decision tree generation section which generates a decision tree for inferring an output value at future time, using the time series data;

a condition acquisition section which an output value at future time is inputted into as a initial condition, which detects a leaf node having the inputted output value as a value of an object variable from the decision tree, and which acquires a condition of explaining variables included in a rule associated with a path from a root node of the decision tree to the detected leaf node, as a condition to obtain the output value; and

a condition decision section, which determines whether the acquired condition is a past condition or a future condition, which determines whether the acquired condition is true or false by using the time series data and the acquired condition in the case where the acquired condition is the past condition, which determines whether the acquired condition is an input condition or an output condition in the case where the acquired condition is the future condition, which outputs the acquired condition as a necessary condition for obtaining the output value in the case where the acquired condition is the input condition, and which outputs the acquired condition to the condition acquisition section as an output value at future time in the case where the acquired condition is the output condition.

9. The inverse model calculation apparatus according to claim 8, wherein the condition decision section increments the future time and outputs the output value at the incremented future time to the condition acquisition section, in the case where the acquired condition is false.

10. An inverse model calculation apparatus for finding a condition under which a target system outputs a certain output value, the target system outputting the certain output value on the basis of an input value to the target system, the inverse model calculation apparatus comprising:

a time series data recording section which records an input value inputted sequentially to the target system and an output value outputted sequentially from the target system as time series data;

a decision tree generation section which generates a decision tree for inferring an output value at future time, using the time series data, a path from a root node to a leaf node being associated in the decision tree with a rule including a condition of explaining variables and a value of an object variable;

a first rule detection section which detects a rule having an output value at future time as a value of an object variable, from the decision tree;

a first condition calculation section which determines whether a condition of explaining variables for a partial time zone in the detected rule matches the time series data, and which in the case of matching, calculates a condition for obtaining the output value at the future time, using the detected rule and the time series data;

a second rule detection section, to which a rule is inputted, and which detects a rule that a condition of explaining variables for a partial time zone in the inputted rule matches from the decision tree;

a first input section which inputs the rule detected by the first rule detection section to the second rule detection section, in the case where the rule detected by the first rule detection section does not match the time series data;

a second input section which determines whether a condition of explaining variables for a partial time zone in the rule detected by the second rule detection section matches the time series data, and which, in the case of not-matching, inputs the rule detected by the second rule detection section to the second rule detection section; and

a second condition calculation section which calculates a condition for obtaining the output value at the future time, using all rules detected by the first and second rule detection sections and the time series data, in the case where the rule detected by the second rule detection section matches the time series data.

11. The inverse model calculation apparatus according to claim 10, further comprising:

a probability calculation section which calculates a probability that an output condition at certain time included in the rule detected by at least one of the first and second rule detection sections holds in the case where other condition before the certain time and at the certain time has held;

a time determination section which determines the certain time such that the probability satisfies a predetermined threshold; and

a time zone determination section which determines a time zone, including a time zone before the determined time and the determined time, as the partial time zone of the rule.

12. The inverse model calculation apparatus according to claim 10, further comprising:

an average calculation section which calculates, with respect to each rule of rules included in the decision tree, a probability that an output condition at certain time holds in the case where other condition before the certain time and at the certain time has held, and which calculates an average of the calculated probability between the rules;

a time determination section which determines the certain time such that the average of the probability satisfies a predetermined threshold; and

a common time zone determination section which determines a time zone that includes a time zone before the determined time and the determined time, as the partial time zone to be commonly applied to the rules.

13. An inverse model calculation method for finding a condition under which a target system outputs a certain output value, the target system outputting the certain output value on the basis of an input value to the target system, the inverse model calculation method comprising:

recording an input value inputted sequentially to the target system and an output value outputted sequentially from the target system as time series data;

generating a decision tree for inferring an output value at future time, using the time series data; and

detecting a leaf node having an output value at future time as a value of an object variable from the decision tree; and

acquiring a condition of explaining variables included in a rule associated with a path from a root node of the decision tree to the detected leaf node, as a condition for obtaining the output value.

14. An inverse model calculation method for finding a condition under which a target system outputs a certain output value, the target system outputting the certain output value on the basis of an input value to the target system, the inverse model calculation apparatus comprising:

recording an input value inputted sequentially to the target system and an output value outputted sequentially from the target system as time series data;

generating a decision tree for inferring an output value at future time, using the time series data;

inputting an output value at future time as a initial condition;

detecting a leaf node having the inputted output value as a value of an object variable from the decision tree;

acquiring a condition of explaining variables included in a rule associated with a path from a root node of the decision tree to the detected leaf node, as a condition for obtaining the output value;

determining whether the acquired condition is a past condition or a future condition;

determining whether the acquired condition is true or false by using the time series data and the acquired condition in the case where the acquired condition is the past condition;

determining whether the acquired condition is an input condition or an output condition in the case where the acquired condition is the future condition;

outputting the acquired condition as a necessary condition for obtaining the output value in the case where the acquired condition is the input condition

regarding the acquired condition as an output value at future time in the case where the acquired condition is an output condition, and detecting a leaf node having the regarded output value at the future time as a value of an object variable from the decision tree,

acquiring a condition of explaining variables included in a rule associated with a path from the root node to the detected leaf node, as a condition for obtaining the regarded output value.

15. The inverse model calculation method according to claim 14, further comprising:

incrementing the future time in the case where the acquired condition is false;

inputting the output value at the incremented future time as a new initial condition.

16. An inverse model calculation method for finding a condition under which a target system outputs a certain output value, the target system outputting the certain output value on the basis of an input value to the target system, the inverse model calculation method comprising:

recording an input value inputted sequentially to the target system and an output value outputted sequentially from the target system as time series data;

generating a decision tree for inferring an output value at future time, using the time series data, a path from a root node to a leaf node being associated in the decision tree with a rule including a condition of explaining variables and a value of an object variable;

detecting a rule having an output value at future time as a value of an object variable, from the decision tree;

in the case where a condition of explaining variables for a partial time zone in the detected rule matches the time series data, calculating a condition for obtaining the output value at the future time, using the detected rule and the time series data;

in the case of non-matching, newly detecting a rule matching the condition of explaining variables for a partial time zone in the detected rule, from the decision tree;

in the case where a condition of explaining variables for a partial time zone in the newly detected rule does not match the time series data, further detecting a rule which the condition of explaining variables for a partial time zone in the newly detected rule matches, from the decision tree;

repeating detecting a rule which a condition of explaining variables for a partial time zone in a latest detected rule matches, from the decision tree, until a rule whose condition of explaining variables for a partial time zone matches the time series data is detected; and

calculating a condition required to obtain the output value at the future time by using all rules detected from the decision tree and the time series data, in the case where the rule whose condition of explaining variables for a partial time zone matches the time series data has been detected.