Method, system, and computer program product for determining causality
Implementations of the present disclosure relate to a method, system and program product for determining a causality between a plurality of variables. Specifically, a method is provided for determining a causality between a plurality of vectors, which comprises: in response to a data set of a plurality of samples associated with the plurality of variables being collected, obtaining a matrix describing the causality between the plurality of variables, each sample among the plurality of samples comprising data that corresponds to the plurality of variables; determining fitness associated with the causality and sparsity associated with the causality based on the data set and the matrix, wherein the sparsity comprises a constraint on each vector among a plurality of vectors in the matrix, the constraint corresponding to a variable among the plurality of variables; building a first problem formula describing the causality according to the determined fitness and sparsity; and solving the built first problem formula so as to obtain a candidate result of the matrix. Further, there is provided a corresponding system and computer program product.
1. A method for determining a causality between a plurality of variables, comprising:
in response to a data set of a plurality of samples associated with the plurality of variables being collected, obtaining a matrix describing the causality between the plurality of variables, each sample among the plurality of samples comprising data that corresponds to the plurality of variables;
determining fitness associated with the causality and sparsity associated with the causality based on the data set and the matrix, wherein the sparsity comprises a constraint on each vector among a plurality of vectors in the matrix, the constraint corresponding to a variable among the plurality of variables;
building a first problem formula describing the causality according to the determined fitness and sparsity; and
solving the built first problem formula so as to obtain a candidate result of the matrix.
2. The method of claim 1 , wherein determining the fitness and the sparsity comprises: with respect to a current vector among a plurality of vectors in the matrix, determining fitness and sparsity for the current vector; and
wherein the constraint comprises a constraint on the current vector, and determining the sparsity for the current vector comprises:
determining a weight vector in the constraint on the current vector; and
determining the sparsity for the current vector based on the determined weight vector and the current vector.
3. The method of claim 2 , wherein determining the weight vector comprises:
determining sparsity for the current vector based on an initial value of the weight vector;
building a second problem formula associated with the current vector according to the fitness for the current vector and the sparsity for the current vector;
solving the second problem formula so as to obtain the current vector; and
determining the weight vector based on the obtained current vector.
4. The method of claim 3 , further comprising: determining the initial value of the weight vector, comprising determining the initial value based on a least square operation associated with the current vector.
5. The method of claim 4 , wherein determining the initial value based on the least square operation associated with the current vector comprises:
determining the d th element w id i n i in the initial value based on the following formula:
w
j
,
d
ini
=
β
j
,
d
(
ols
)
β
j
(
ols
)
1
,
β
j
(
ols
)
=
(
x
-
j
T
x
-
j
)
-
1
x
-
j
T
x
j
,
wherein β j represents the current vector, β j,d represents the d th element in the current vector β j , β j,d (ols) represents a least square operation, ∥ represents an absolute value operation, ∥ ∥ 1 represents a 1-norm operation, x j represents a portion associated with the current vector β j among the plurality of samples, x −j represents a portion associated with vectors other than the current vector β j among the plurality of samples, T represents a transpose operation, j=1, p, and p represents a number of the plurality of variables.
6. The method of claim 5 , wherein determining the weight vector based on the current vector comprises:
determining a corresponding element in the weight vector based on an element in the obtained current vector.
7. The method of claim 6 , wherein determining the corresponding element in the weight vector based on the element in the obtained current vector comprises:
determining the d th element w j,d in the weight vector w j based on the following formula:
w
j
,
d
=
β
j
,
d
1
1
+
γ
abs
(
β
j
)
1
1
+
γ
1
,
wherein β j,d represents the d th element in the current vector β j , γ represents a predetermined parameter, and abs ( ) represents an absolute value operation.
8. The method of claim 7 , wherein determining the sparsity for the current vector comprises: determining the sparsity Sparsity j for the current vector β j based on:
Sparsity j =∥w j ⊙β j ∥ 1 , wherein ⊙ represents a dot-product operation.
9. The method of claim 7 , wherein determining the sparsity for the current vector comprises: determining the sparsity Sparsity j for the current vector β j based on:
Sparsity j =∥w j −γ ⊙β j ∥ 1 , wherein ⊙ represents a dot-product operation.
10. The method of claim 7 , wherein determining the sparsity for the current vector further comprises:
determining a weight coefficient λ j in the constraint on the current vector; and
determining the sparsity for the current vector comprises determining the sparsity Sparsity j for the current vector β j based on:
Sparsity j =∥w j −γ ⊙β j ∥ 1 , wherein ⊙ represents a dot-product operation.
11. The method of claim 2 , wherein building the first problem formula comprises: building the first problem formula based on:
min
β
1
,
…
,
β
p
∑
j
=
1
p
x
j
-
x
-
j
β
j
2
2
+
Sparsity
j
wherein p represents a number of the plurality of variables, x j represents a portion associated with the current vector β j among the plurality of samples, x −j represents a portion associated with vectors other than the current vector β j among the plurality of samples, ∥x j −x −j β j ∥ 2 2 represents fitness for the current vector β j , ∥ ∥ 2 2 represents a 2-norm operation, and Sparsity j represents sparsity for the current vector β j .
12. The method of claim 1 , wherein building the first problem formula describing the causality further comprises: building a causal sequence based on at least one variable among the plurality of variables; and
solving the first problem formula so as to obtain a candidate result of the matrix comprises: solving the first problem formula based on the causal sequence as a constraint condition, so that a directed graph represented by the candidate result is a directed acyclic graph.
13. The method of claim 12 , wherein building the causal sequence based on at least one variable among the plurality of variables comprises:
with respect to a first variable in the causal sequence, selecting a second variable that has a causality with the first variable from the candidate result of the matrix; and
adding the selected second variable to the causal sequence as a successor of the first variable.
14. A computer program product, tangibly stored on a non-transitory computer-readable medium and comprising machine-executable instructions, which, when executed, cause a machine to implement the steps of a method according to claim 1 .
15. A device for determining a causality between a plurality of variables, comprising one or more processors configured to;
in response to a data set of a plurality of samples associated with the plurality of variables being collected, obtain a matrix describing the causality between the plurality of variables, each sample among the plurality of samples comprising data that corresponds to the plurality of variables;
determine fitness associated with the causality and sparsity associated with the causality based on the data set and the matrix, wherein the sparsity comprises a constraint on each vector among a plurality of vectors in the matrix, the constraint corresponding to a variable among the plurality of variables;
build a first problem formula describing the causality according to the determined fitness and sparsity; and
solve the built first problem formula so as to obtain a candidate result of the matrix.