Method, device and system for estimating causality among observed variables

Patent metadata

Field	Value
Publication number	US-11651234-B2
Application number	US-201816140880-A
Country	US
Kind code	B2
Filing date	Sep 25, 2018
Priority date	Sep 30, 2017
Publication date	May 16, 2023
Grant date	May 16, 2023

Abstract

A method, device and system for estimating causality among observed variables are provided. In response to receiving observation data of a plurality of observed variables, a causality objective function is determined, based on fitting inconsistencies when fitting is performed using the observed variables and a sparse constraint for a causal network structure. The fitting inconsistencies are adjusted based on weighting factors of the observed variables, wherein a weighting factor of an observed variable indicates a minimum underestimate value of cost required for fitting a target variable using all other observed variables than the above observed variable. Then, the causality among the plurality of observed variables is estimated by using the observations data to optimally solve the causality objective function through sparse causal reasoning under a directed acyclic graph constraint.

First claim

What is claimed is:

1. A method for estimating causality among observed variables, comprising:
in response to receiving observation data of a plurality of observed variables, determining a causality objective function for the plurality of observed variables, based on fitting inconsistencies when fitting is performed using an L2 norm of the observed variables, an L0 norm of a sparse constraint of a causal network structure of the observed variables, and a directed acyclic graph (DAG) constraint, wherein the L2 norm and the L0 norm taken together form a first cost for a first graph under the DAG constraint, wherein the fitting inconsistencies are adjusted based on weighting factors of the observed variables, and wherein a weighting factor of an observed variable indicates a minimum underestimate value of a second cost for a second graph based on the L2 norm and the L0 norm taken together, wherein the second cost is required for fitting a target variable using all other observed variables than the observed variable, and the minimum underestimate value of the second cost is based on no DAG constraint; and
estimating the causality among the plurality of observed variables by using the observations data to optimally solve the causality objective function for the plurality of observed variables through sparse causal reasoning under the DAG constraint.

2. The method of claim 1 , wherein the sparse causal reasoning of the causality objective function for the plurality of observed variables is converted into an optimal causal sequence recursive solving problem, and wherein a cost consumed from a starting node to a current node in a sorted causal sequence and a predicted cost from the current node to a target node are determined based on the fitting inconsistencies adjusted with the weighting factors of the observed variables and the sparse constraint for the causal network structure of the observed variables.

3. The method of claim 2 , further comprising: in a procedure of the optimal causal sequence recursive solving:
for a new generated candidate causal sequence, determining whether it is conflicted with a predetermined variable group sequence relationship; and
discarding the generated new candidate causal sequence if it is determined that there is a conflict.

4. The method of claim 3 , wherein the predetermined variable group sequence relationship is given by an expert in the art.

5. The method of claim 3 , wherein the predetermined variable group sequence relationship is automatically determined based on the observation data.

6. The method of claim 5 , wherein the predetermined variable group sequence relationship is automatically determined by:
for each of the observed variables, obtaining a potential optimal parent node set thereof;
generating a parent relationship graph based on the acquired optimal parent node set;
extracting strongly connected components from the parent relationship graph;
converting the parent relationship graph into a new directed acyclic graph, by converting each of the strongly connected components into a new node and adding a respective edge between respective new nodes when two strongly connected components have a connectivity in the parent relationship graph; and
extracting a sequence relationship between the strongly connected components in the directed acyclic graph as the predetermined variable group sequence relationship.

7. A system for estimating causality among observed variables, comprising:
a processor; and
a memory having a computer program code stored therein which, when executed by the processor, causes the processor to perform the method of claim 1 .

8. A device for estimating causality among observed variables, comprising:
a processor; and
a memory storing executable instructions that, when executed by the processor, causes the processor to perform as:
an objective function determining module configured for, in response to receiving observation data of a plurality of observed variables, determining a causality objective function for the plurality of observed variables, based on fitting inconsistencies when fitting is performed using an L2 norm of the observed variables, an L0 norm of a sparse constraint of a causal network structure of the observed variables, and a directed acyclic graph (DAG) constraint, wherein the L2 norm and the L0 norm taken together form a first cost for a first graph under the DAG constraint, wherein the fitting inconsistencies are adjusted based on weighting factors of the observed variables, and wherein a weighting factor of an observed variable indicates a minimum underestimate value of a second cost for a second graph based on the L2 norm and the L0 norm taken together, wherein the second cost is required for fitting a target variable using all other observed variables than the observed variable, and the minimum underestimate value of the second cost is based on no DAG constraint; and
a causal reasoning module configured for, estimating the causality among the plurality of observed variables by using the observations data to optimally solve the causality objective function for the plurality of observed variables through sparse causal reasoning under the DAG constraint.

9. The device of claim 8 , wherein the causal reasoning module is configured for converting the sparse causal reasoning of the causality objective function for the plurality of observed variables into an optimal causal sequence recursive solving problem, and wherein the causal reasoning module is configured for determining a cost consumed from a starting node to a current node in a sorted causal sequence and a predicted cost from the current node to a target node, based on the fitting inconsistencies adjusted with the weighting factors of the observed variables and the sparse constraint for the causal network structure of the observed variables.

10. The device of claim 9 , wherein the processor further performs as a search space cutting module configured for, in a procedure of the optimal causal sequence recursive solving:
for a generated new candidate causal sequence, determining whether it is conflicted with a predetermined variable group sequence relationship; and
discarding the generated new candidate causal sequence if it is determined that there is a conflict.

11. The device of claim 10 , wherein the predetermined variable group sequence relationship is given by an expert in the art.

12. The device of claim 11 , wherein the predetermined variable group sequence relationship is automatically determined based on the observation data.

13. The device of claim 12 , wherein the processor further performs as a sequence relationship determining module configured for automatically determining the predetermined variable group sequence relationship by:
for each of the observed variables, obtaining a potential optimal parent node set there of;
generating a parent relationship graph based on the acquired optimal parent node set;
extracting strongly connected components from the parent relationship graph;
converting the parent relationship graph into a new directed acyclic graph, by converting each of the strongly connected components into a new node and adding a respective edge between respective new nodes when two strongly connected components have a connectivity in the parent relationship graph; and
extracting a sequence relationship between the strongly connected components in the directed acyclic graph as the predetermined variable group sequence relationship.

Assignees

• Nec Corp

Inventors

• Liu Chunchen
• Feng Lu
• Wei Wenjuan

Classifications

• G06F2216/03

  Data mining · CPC title

• G06N5/02 Primary

  Knowledge representation; Symbolic representation · CPC title

• G06F16/9024

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title

• G06N5/022 Primary

  Knowledge engineering; Knowledge acquisition · CPC title

• G06N7/01

  Probabilistic graphical models, e.g. probabilistic networks · CPC title