TECHNICAL FIELD

The present invention relates to a relationship extraction device, a method of extracting relationship, and a program.

BACKGROUND ART

For data having multiple elements, investigation of correlations between elements has been conducted in various technical fields (e.g., in the fields of the statistics, machine learning, molecular dynamics, etc.).

For example, in the field of statistics and machine learning, techniques have been proposed in which vectors having multiple elements of data arranged are mapped to a space called vv-RKHS (vector-valued reproducing kernel Hilbert space), to approximate a function that represents a relationship between the elements on the vv-RKHS (Non-patent document 1). As the vv-RKHS is a space of vector-valued functions, it has an advantage of being capable of approximating the relationship among multiple elements at once. Note that techniques have been also proposed that extract information on cyclic components from time series data that represents change in time of the relationship by using the vv-RKHS for time series data (Non-patent document 2).

Also, for example, in the field of physics and molecular dynamics, techniques have been proposed that extract information on collective oscillations by a method called phase reduction (Non-patent document 3). Also, for example, in the field of machine learning, methods have been proposed that extract variables in a causality relationship by a method called Granger causality (Non-patent document 4).

The vv-RKHS described above is a generalization of the RKHS (reproducing kernel Hilbert space) used for analyzing data having a single element. By using the RKHS, data exhibiting complex behavior can be converted into data exhibiting simple behavior. Using this property, techniques have been studied that approximate complex time series data with a simple function on the RKHS (Non-patent document 5).

Here, as another generalization of the RKHS, a space called RKHM (reproducing kernel Hilbert C*-module) has been proposed, and theoretical analysis has been conducted in the field of physics (Non-patent document 6). The RKHM is a space of functions having values in a space called C*-algebra, and hence, can be used for approximating a C*-algebra-valued function. Note that C*-algebra is a generalization of a set of all complex numbers and a set of all matrices, and is a space having the concepts of conjugation and norm.

RELATED ART DOCUMENTS
Non-Patent Document

[Non-patent document 1] Mauricio A. Alvarez, Lorenzo Rosasco, and Neil D. Lawrence, ‘Kernels for vector-valued functions: a review,’ Computer Science and Artificial Intelligence Laboratory Technical Report, MIT-CSAIL-TR-2011-033 CBCL-301, 2011.

[Non-patent document 2] Keisuke Fujii, Yoshinobu Kawahara, ‘Dynamic mode decomposition in vector-valued reproducing kernel Hilbert spaces for extracting dynamical structure among observables,’ Neural Networks 117, pp. 94-103, 2019.

[Non-patent document 3] Hiroya Nakao, Sho Yasui, Masashi Ota, Kensuke Arai and Yoji Kawamura, ‘Phase reduction and synchronization of a network of coupled dynamical elements exhibiting collective oscillations,’ Chaos 28, 045103, 2018.

[Non-patent document 4] Songting Li, Yanyang Xiao, Douglas Zhou and David Cai, ‘Causal inference in nonlinear systems: Granger causality versus time-delayed mutual information,’ Phys. Rev. E 97, 052216, 2018.

[Non-patent document 5] Yuka Hashimoto, Isao Ishikawa, Masahiro Ikeda, Yoichi Matsuo and Yoshinobu Kawahara, ‘Krylov Subspace Method for Nonlinear Dynamical Systems with Random Noise,’ arXiv: 1909.03634, 2019.

[Non-patent document 6] Jaeseong Heo, ‘Reproducing kernel Hilbert C*-modules and kernels associated with cocycles,’ J. Math. Phys. 49, 103507, 2008.

SUMMARY OF THE INVENTION
Problem to be Solved by the Invention

Meanwhile, the RKHS is only capable of handling data having a single element, and hence, cannot describe a relationship among multiple elements. Also, the phase reduction aims at approximating collective behavior of data, and hence, cannot represent a relationship among elements. On the other hand, although the vv-RKHS takes a relationship among multiple elements into consideration, the proximity between vector-valued functions included in the vv-RKHS is measured in complex values. Therefore, for example, in the case where the purpose is to completely extract information on the relationship of any two elements from among the multiple elements, the number of relationships between the two data items each having n elements becomes n², and hence, it becomes necessary to represent the proximity of functions corresponding to these data items n²complex numbers.

In contrast, if using the RKHM, the proximity of functions can be measured by a C*-algebra value of a matrix or the like. However, there is no framework of using the RKHM that aims at extracting relationships between elements of data having multiple elements.

One embodiment of the present invention was devised in view of the above points, and has an object to extract relationships between elements held in data using the RKHM.

Means for Solving Problem

As described above, in order to achieve the object, a relationship extraction device according to one embodiment includes a first obtaining means configured to obtain a set of data {x₀, . . . , x_T−1}⊆X each having multiple elements and a set of data {y₀=f(x₀), . . . , y_T−1=f(x_T−1)}⊆Y each having multiple elements, where f is any mapping; a generation means configured to generate an approximate operator that approximates a Perron-Frobenius operator K satisfying Kφ₁(x_t)=φ₂(y_t) for t=0, . . . , T−1, wherein φ₁is a feature mapping with respect to a positive definite kernel function k₁on X×X that takes C*-algebra values, and φ₂is a feature mapping with respect to a positive definite kernel function k₂on Y×Y that takes C*-algebra values; a second obtaining means configured to obtain data x_tand x_sas targets of relationship extraction; and an extraction means configured to extract a relationship between each element of x_tand each element of x_sby using the approximate operator.

Advantageous Effects of the Invention

Relationships between elements held in data can be extracted using the RKHM.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 is a diagram illustrating an example of a functional configuration of a relationship extraction device according to a present embodiment;

FIG. 2 is a flow chart illustrating an example of an approximate operator generation process according to the present embodiment;

FIG. 3 is a flow chart illustrating an example of a relationship extraction process according to the present embodiment;

FIG. 4A is a diagram (part 1) illustrating an example of an evaluation result;

FIG. 4B is a diagram (part 1) illustrating an example of an evaluation result;

FIG. 5A is a diagram (part 2) illustrating an example of an evaluation result;

FIG. 5B is a diagram (part 2) illustrating an example of an evaluation result;

FIG. 5C is a diagram (part 2) illustrating an example of an evaluation result;

FIG. 5D is a diagram (part 2) illustrating an example of an evaluation result;

FIG. 6A is a diagram (part 3) illustrating an example of an evaluation result;

FIG. 6B is a diagram (part 3) illustrating an example of an evaluation result;

FIG. 7A is a diagram (part 4) illustrating an example of an evaluation result;

FIG. 7B is a diagram (part 4) illustrating an example of an evaluation result; and

FIG. 8 is a diagram illustrating an example of a hardware configuration of a relationship extraction device according to the present embodiment.

EMBODIMENTS FOR CARRYING OUT THE INVENTION

In the following, one embodiment of the present invention will be described. In the present embodiment, a relationship extraction device 10 will be described, that can extract a relationship (i.e., interrelation) between any two elements held in data when the data including one or more items each having multiple elements is given, by using an RKHM.

First, a theoretical construction of the present embodiment will be described.

<<Settings>>

Let X be a space to which data having multiple elements belongs, and let {x₀, x₁, . . . }⊆X be a set of given data. Let A be a C*-algebra, to consider an A-valued positive definite kernel k:X×X→A. Here, when stating that a mapping k:X×X→A is an A-valued positive definite kernel, the mapping satisfies the following Condition 1 and Condition 2.

(Condition 1) For any x,y∈X, k(x,y)=k(x,y)* where * denotes conjugate.

(Condition 2) Let m be any natural number, for any x₀, x₁, . . . , x_m-1∈X and any c₀, c₁, . . . c_m-1∈A, the following double summation is positive.

[

Math
.

1

]



∑

t
=
0

m
-
1

∑

s
=
0

m
-
1

c
t
*

⁢

k
⁡
(

x
t

,

x
s

)

⁢

c
s

Here, “positive” means being positive constant in a C*-algebra, which is a generalization of a Hermitian matrix whose all eigenvalues are greater than or equal to 0 (i.e., Hermitian positive definite).

Given an A-valued positive definite kernel k, a mapping φ from X to an A-valued function is defined by φ(x)=k(⋅,x). This mapping (p is also referred to as a feature map.

For a natural number m, x₀, x₁, . . . , x_m-1∈X, and c₀, c₁, . . . , c_m-1∈A, let M_k,0be a space configured from the entirety of the following linear combination.

[

Math
.

2

]



∑

t
=
0

m
-
1

ϕ
⁡
(

x
t

)

⁢

c
t

Also, let m and m′ be natural numbers, x₀, x₁, . . . , x_m-1, y₀, y₁, . . . , y_m′-1∈X, and c₀, c₁, . . . , c_m-1, d₀, d₁, . . . , d_m′-1∈A, an operation <⋅, ⋅>_kwith respect to M_k,0is defined as follow:

[

Math
.

3

]



〈

∑

t
=
0

m
-
1

ϕ
⁡
(

x
t

)

⁢

c
t

,

∑

t
=
0

m
′

-
1

ϕ
⁡
(

y
t

)

⁢

d
t

〉

k

=

∑

t
=
0

m
-
1

∑

s
=
0

m
′

-
1

c

t

*

⁢

k
⁡
(

x
t

,

y
s

)

⁢

d
s

The operation <⋅,⋅>_kdefined in this way has the properties of the A-valued inner product. In other words, the operation has the following four properties with respect to u,v,w∈M_k,0and c,d∈A:

- <u,v>_k=<v,u>_k*
- <u,u>_kis positive
- <u,u>_k=0 is equivalent to u=0
- <u,vc+wd>_k=<u,v>_kc+<u,w>_kd

By using this inner product <⋅,⋅>_k, a complex-valued norm can be defined as follows:

[

Math
.

4

]




v


k

=



〈

v
,
v

〉

k



1
2

A space in which M_k,0is completed with respect to this norm is denoted as M_k, and is referred to as a reproducing kernel Hilbert C*-module (RKHM) with respect to k. M_kcan be configured uniquely. Also, in M_k, the magnitude of an A value |⋅|_kcan also be defined as follows:

[

Math
.

5

]



❘
"[LeftBracketingBar]"

v

❘
"[RightBracketingBar]"

k

=

〈

v
,
v

〉

k

1
2

Assuming that each of x_t(t=0, 1, . . . ) being an element of X has n elements, x_tis denoted as x_t=[x_t,0, . . . , x_t,n-1]. In the case where a C*-algebra A is the entirety of n×n matrices, an A-valued positive definite kernel k can be configured by using the following complex-valued positive definite kernel:

{tilde over (k)} [Math. 6]

k

Note that in the text of the present description, for the sake of convenience, a symbol having “˜” added to the top of x is written as “˜x”.

In fact, if each (i,j) component of an n×n matrix k(x_t,x_s) is defined by ˜k(x_t,i,x_s,j) with respect to the elements x_tand x_sof X, it can be shown that k is an n×n matrix-valued positive definite kernel. ˜k(x_t,i,x_s,j) represents the proximity of x_t,iand x_s,j; therefore, each (i,j) component of k(x_t,x_s) (i.e., the inner product of φ(x_t) and φ(x_s)) represents the proximity of the i-th component x_t,iof x_tand the j-th component x_s,iof x_s.

<<Relationship of Data in RKHM>>

Let X and Y be spaces to which data belongs, and assume that the following Formula (1) holds for x₀, x₁, . . . , x_T−1∈X and y₀, y₁. . . , y_T−1∈Y.

y_t=f(x_t) (1)

where f is a mapping from X to Y that is nonlinear in general.

Let k₁be a positive definite kernel on X, let k₂be a positive definite kernel on Y, let φ₁be a feature map with respect to k₁, and let φ₂be a feature map with respect to k₂. In order to express Formula (1) described above as a formula in the following spaces,

M_k₁,M_k₂ [Math. 7]

Assume that the following mapping,

K:M_k₁→M_k₂ [Math. 8]

satisfies the following Formula (2),

Kφ₁(x_t)=φ₂(y_t) (2)

Such K is referred to as a Perron-Frobenius operator. In the case where x₀, x₁, . . . , x_T−1∈X constitute time series data, if setting X=Y, y_t=x_t+1, and k₁=k₂, then, f is a mapping representing time evolution, and thereby, K is also a mapping representing time evolution.

<<Approximation of Perron-Frobenius Operator by Orthonormal Projection>>

In the following, it is assumed that an element x_t(t=0, 1, . . . ) of X has n elements, and is expressed as x_t=[x_t,0, . . . , x_t,n-1]. Also, assume that a C*-algebra A is the entirety of n×n matrices, and as described above, an A-valued positive definite kernel k is configured using a complex-valued positive definite kernel ˜k.

At this time, consider approximating K that satisfies Formula (2) describe above, to analyze f by using the approximated K, predict y_tfrom a given x_t, and compare matrix-valued inner products of elements of X obtained by such analysis and prediction (i.e., measure the proximity). The value of an inner product (proximity) takes a matrix value, and its component represents the proximity of elements, and thereby, relationships between the elements can be extracted. In the following, (i) a case of applying a Perron-Frobenius operator K when X=Y, y_t=x_t+1, and k₁=k₂=k; and (ii) a case of applying the Perron-Frobenius operator K when X*Y, will be described.

(i) The case of X=Y, y_t=x_t+1, and k₁=k₂=k

In this case, by solving a minimization problem in Formula (3) shown later,

{circumflex over (K)} [Math. 9]

is solved to approximate K. Note that in the text of the present description, for the sake of convenience, a symbol having “{circumflex over ( )}” added to the top of x is written as “{circumflex over ( )}x”.

[

Math
.

10

]



min

ϕ
⁡
(

x

t
+
1

)

=

K

^

⁢

ϕ
⁡
(

x
t

)

⁢

(

t
=
0

,
…

,

T
-
2

)

,

K
^

∈

L
⁡
(

V
T

)

❘
"[LeftBracketingBar]"

ϕ
⁡
(

x
T

)

-

K
^

⁢

ϕ
⁡
(

X

T
-
1

)

❘
"[RightBracketingBar]"

k

(
3
)

where V_Tis a set of all linear combinations expressed as in the following formula:

[

Math
.

11

]



∑

t
=
0

T
-
1

ϕ
⁡
(

x
t

)

⁢

c
t

(

c
t

∈
A

)

Also, L(V_T) is a set of all A-linear operators from V_Tto V_T(i.e., L that satisfies L(vc)=(Lv)c for any c∈A and any v∈M_k).

In order to solve the minimization problem shown in Formula (3) described above, an orthonormal projection from M_kto V_Tis calculated. Here, an orthonormal projection P from M_kto V_Tis an A-linear operator from M_kto V_Tthat satisfies P²=P and P=P*. P can be calculated by configuring an orthonormal system {q₀, q₁, . . . , q_T−1} of V_T. The orthonormal system {q₀, q₁, . . . , q_T−1} of V_Tis a Hermitian matrix c where <q_t,q_s>_k=0 and <q_t,q_t>_kis not 0 for q_t∈V_Tand s≠t, and c²=c is satisfied (in this case, q_tis called normal).

Given time series data x₀, x₁, . . . , x_T−1∈X, an orthonormal system {q₀, q₁, . . . , q_T−1} of V_Tcan be configured by sequentially executing the following Step 1 and Step 2 for t=0, 1, . . . ,T−1.

Step 1: If t=0, set ˜q₀=φ(x₀). On the other hand if t≠0, for s=0, . . . , t−1, set r_s,t=<φ(x_t), q_s>_k, and set ˜q_tas follows:

[

Math
.

12

]



q
~

t

=

ϕ
⁡
(

x
t

)

-

∑

s
=
0

t
-
1

r

s
,
t

⁢

q
s

Step 2: Next, let ε be a real number greater than or equal to 0, and if ∥˜q_t∥_k≥ε, set q_t=0; otherwise, the following is executed. Let eigenvalues of <˜q_t, ˜q_t>_kbe λ_t,0≥ . . . ≥λ_t,n-1, and let m_tbe the maximum index that satisfies λ_i>ε². Also, let U_tD_tU_t* be the eigendecomposition of <˜q_t,˜q_s>_k. Here, D_tis a matrix having diagonal components of λ_t,0, . . . , λ_t,n-1and non-diagonal components of all zero. U_tis a matrix in which eigenvectors corresponding to the respective eigenvalues λ_t,n-1are arranged in this order. At this time, <˜q_t, ˜q_t>_kis a Hermitian positive definite matrix, and hence, if ∥˜q_t∥_k>ε, has at least one positive eigenvalue greater than ε, and m_t>0.

Therefore, let {circumflex over ( )}D_tbe a matrix having the following diagonal components,

[

Math
.

13

]



1

λ

t
,
0

,
…

,

1

λ

t
,

m
t

,
0
,
…

,
0

and having non-diagonal components of all zero, and set b_t=U_t{circumflex over ( )}D_tU_t. Further, set q_t=˜q_tb_t. q_tis normal, and hence, is an orthonormal vector.

Let Φ_Tbe an A-linear mapping to map a vector [c₀, . . . , c_T−1] of arrayed T elements of the C*-algebra A to the following linear combination:

[

Math
.

14

]



∑

t
=
0

T
-
1

q
t

⁢

c
t

Also, let B_Tbe a matrix having diagonal components of b₀, . . . , b_T−1and non-diagonal components of all zero, and let R_Tbe a T×T matrix having r_s,tas the (s,t) component. Note that each component of R_Tis an element of A. By executing Step1 and Step2 described above, it can be shown that Q_T=Φ_TB_T−Q_TR_T; therefore, Q_T=Φ_TB_T(I+R_T)⁻¹where I is an identity matrix.

For Q_Tconfigured as described above, Q_TQ_T* is an orthonormal projection from M_kto ˜V_T(i.e., if setting P=Q_TQ_T*, P is an orthonormal projection) where ˜V_Tis a set of all linear combinations expressed as in the following formula:

[

Math
.

15

]



∑

t
=
0

T
-
1

q
t

⁢

c
t

(

c

t

∈
A

)

The orthonormal projection minimizes the difference, i.e., for any element v of M_kand any element w of ˜V_T, |v−w|_k−|v−Pv|_kis positive. Also, in the case of setting c=0 at Step 2 described above, any element v of V_Tcan be expressed as follows:

[

Math
.

16

]



v
=

∑

t
=
0

T
-
1

q
t

⁢

c
t

Therefore, it can be shown V_T=˜V_T. Here, c_tis an n×n matrix.

Therefore, it can be understood that {circumflex over ( )}K fulfilling Formula (3) described above satisfies {circumflex over ( )}Kφ(x_T−1)=Q_TQ_T*φ(x_T), and satisfies {circumflex over ( )}Kφ(x_t)=Q_TQ_T*φ(x_t+1) (t=0, . . . , T−1). Meanwhile, for an element v of M_k, an element of V_Tthat minimizes the difference is Q_TQ_T*v. Therefore, Kv is approximated with {circumflex over ( )}KQ_TQ_T*v. Here, {circumflex over ( )}KQ_TQ_T*v can be expressed as follows:

{circumflex over (K)}Q_TQ_T*v={circumflex over (K)}Φ_TB_T(I+R_T)⁻¹Q*_Tv=Q_TQ*_TΦ_T+1B_T(I+R_T)⁻¹Q*_Tv=Q_T(I+R_T)⁻*B*_TΦ*_TΦ_T+1B_T(I+R_T)⁻¹Q*_Tv [Math. 17]

where, −* denotes the Hermitian transposition of an inverse matrix.

By Q_T, a vector of arrayed T elements of A and an element of V_Tcan be considered as identical, and hence, Q_Tcan be regarded as an operator representing a coordinate transformation. Therefore, K is approximated with a T×T matrix in which components expressed as in the following formula,

(I+R_T)⁻*B*_TΦ*_TΦ_T+1B_T(I+R_T)⁻¹ [Math. 18]

are elements of A. Φ_T*Φ_T+1 is a T×T matrix whose (s, t) component is k (x_s, x_t+1)∈A, and hence, the formula,

(I+R_T)⁻*B*_TΦ*_TΦ_T+1B_T(I+R_T)⁻¹ Math. 19]

can be calculated in practice. Therefore, ˜K_Tis set as follows:

{tilde over (K)}_T=(I+R_T)⁻*B*_TΦ*_TΦ_T+1B_T(I+R_T)⁻¹ [Math. 20]

and this ˜K_Tis referred to as an “approximate Perron-Frobenius operator”.

Thus, by using this approximate Perron-Frobenius operator ˜K_T, Kv can be approximated as Q_T˜K_TQ_T*v for any v∈M_k.

(ii) The Case of X≠Y

In this case, let V_Tbe a set of all linear combinations expressed as in the following formula,

[

Math
.

21

]



∑

t
=
0

T
-
1

ϕ
1

(

x
t

)

⁢

c
t

(

c
t

∈
A

)

and let W_Tbe a set of all linear combinations expressed as in the following formula:

[

Math
.

22

]



∑

t
=
0

T
-
1

ϕ
2

(

y
t

)

⁢

c
t

(

c
t

∈
A

)

Further, in substantially the same way as in (i) described above, an orthonormal system {q₀, q₁, . . . , q_T−1} of VT is configured, and by using this orthonormal system {q₀, q₁, . . . , q_T−1}, Q_Tis configured. Further, let {circumflex over ( )}K be a linear mapping from V_Tto W_Tthat satisfies {circumflex over ( )}Kφ₁(x_t)=φ₂(y_t), to approximate Kv with {circumflex over ( )}KQ_TQ_T*v. Therefore, also for W_T, an orthonormal system is configured in substantially the same way as in (i) described above, and by using this orthonormal system, P_Tis configured by a method substantially the same as the method of configuring Q_Tdescribed above.

Also, in substantially the same way as in (i) described above, Q_Tis decomposed as Q_T=Φ_TB_T(I+R_T)−1 where Φ_Tis an A-linear mapping that maps a vector [c₀, . . . , c_T−1] of arrayed T elements of A to the following linear combination:

[

Math
.

23

]



∑

t
=
0

T
-
1

ϕ
1

(

x
t

)

⁢

c
t

 

In substantially the same way, P_Tis decomposed as P_T=Ψ_TC_T(I+S_T)⁻¹where Ψ_Tis an A-linear mapping that maps a vector [c₀, . . . , c_T−1] of arrayed T elements of A to the following linear combination:

[

Math
.

24

]



∑

t
=
0

T
-
1

ϕ
2

(

y
t

)

⁢

c
t

 

Also, C_Tis a T×T matrix with respect to W_T, configured by a method substantially the same as the method of configuring B_Tdescribed above. Similarly, S_Tis a T×T matrix with respect to W_T, configured by a method substantially the same as the method of configuring R_Tdescribed above.

At this time, as {circumflex over ( )}Kφ₁(x_t)=φ₂(y_t) is satisfied, {circumflex over ( )}KΦ_T=ωT is derived; therefore, K is approximated with a T×T matrix that has components of elements of A, and is expressed as follows:

P*_T{circumflex over (K)}Q_T=(I+S_T)−*C*_TΨ*_TΨ_TB_T(I+R_T)⁻¹ [Math. 25]

In other words, the approximate Perron-Frobenius operator is set as follows:

{tilde over (K)}_T=(I+S_T)⁻*C*_TΨ*_TΨ_TB_T(I+R_T)⁻¹ [Math. 26]

<<Decomposition of Approximate Perron-Frobenius Operator>>

As described above, an A-valued positive definite kernel k is configured with a complex-valued positive definite kernel ˜k, and is an n×n matrix in which each component takes a complex value. Therefore, letting C be the complex number field, the approximate Perron-Frobenius operator ˜K_Tcan be regarded as ˜K_T∈C^nT×nT.

Here, assume that there exist eigenvalues ˜λ₀, . . . , ˜λ_nT-1and corresponding eigenvectors ˜v₀, . . . , ˜v_nT-1for the approximate Perron-Frobenius operator ˜K_T. By setting v_m=[˜v_m, 0, . . . , 0] and λ_m=diag{˜λ_m, 0, . . . , 0}, ˜K_Tv_m=v_mλ_mis satisfied. Also, if [˜v₁, . . . , ˜v_nT-1] is invertible, the following formula holds:

[

Math
.

27

]



Q
T
*

⁢

ϕ
⁡
(

x
0

)

=

∑

m
=
0

nT
-
1

v
m

⁢

c
m

(

c
m

∈
A

)

 

Here, by the definition of K, φ(x_t)=K^tφ(x₀) holds. Therefore, by using an approximate Perron-Frobenius operator, φ(x_t) is approximated with Q_T˜K_TtQ_T*φ(x₀). Similarly, by using an approximate Perron-Frobenius operator, φ(x_s) is approximated with Q_T˜K_T^sQ_T*φ(x₀).

Then, k (x_t, x_s)=<φ(x_t), φ(x_s)>_kcan be approximated as in the following Formula (4):

[

Math
.

28

]



〈

ϕ
⁡
(

x
t

)

,

ϕ
⁡
(

x
s

)

〉

k

≈

〈

Q
T

⁢

K
~

T
t

⁢

∑

m
=
0

nT
-
1

v
m

⁢

c
m

,

Q
T

⁢

K
~

T
s

⁢

∑

m
=
0

nT
-
1

v
m

⁢

c
m

〉

k

(
4
)

=

〈

K
~

T
t

⁢

∑

m
=
0

nT
-
1

v
m

⁢

c
m

,

K
~

T
s

⁢

∑

m
=
0

nT
-
1

v
m

⁢

c
m

〉

=

〈

∑

m
=
0

nT
-
1

v
m

⁢

λ
m
t

⁢

c
m

,

∑

m
=
0

nT
-
1

v
m

⁢

λ
m
s

⁢

c
m

〉

=

∑

m
,

m
′

=
0

nT
-
1

c
m
*

(

λ
m
*

)

t

⁢

〈

v
m

,

v

m
′

〉

⁢

λ

m
′

s

⁢

c

m
′

=

∑

m
,

m
′

=
0

nT
-
1

λ
~

~

m
t

⁢

λ
~

m
′

s

(

v
~

m
*

⁢

v
~

m
′

)

⁢

c
m
*

⁢

c

m
′

where for u_mand v_m, <u_m, v_m≥u_m*v_m.

By approximation and decomposition executed in this way, for example, it becomes possible to analyze the behavior when having s,t→∞; the cycle of change in k(x_t,x_s) (i.e., a matrix in which each (i,j) component represents the proximity between the i-th component of x_tand the j-th component of x_s); and the like.

Next, a functional configuration of the relationship extraction device 10 according to the present embodiment will be described with reference to FIG. 1. FIG. 1 is a diagram illustrating an example of a functional configuration of the relationship extraction device 10 according to the present embodiment.

As illustrated in FIG. 1, the relationship extraction device 10 according to the present embodiment includes an approximate operator generation processing unit 100, a relationship extraction processing unit 200, and a storage unit 300.

The storage unit 300 stores a set of data {x₀, x₁, . . . ,x_T−1} each having multiple elements. Also, in the storage unit 300, an approximate Perron-Frobenius operator ˜K_Tgenerated by the approximate operator generation processing unit 100, and relationships extracted by the relationship extraction processing unit 200 are stored (i.e., an n×n matrix as an approximation result shown in Formula (4) described above).

The approximate operator generation processing unit 100 takes as input a set of data {x₀, x₁, . . . , x_T−1} each having multiple elements, and executes an approximate operator generation process of generating an approximate Perron-Frobenius operator ˜K_T. Here, the approximate operator generation processing unit 100 includes an obtaining unit 101 and an approximate operator generation unit 102. The obtaining unit 101 obtains the set of data {x₀, x₁, . . . , x_T−1} each having multiple elements from the storage unit 300. The approximate operator generation unit 102 generates an approximate Perron-Frobenius operator ˜K_Tfrom {x₀, x₁, . . . , x_T−1} obtained by the obtaining unit 101.

The relationship extraction processing unit 200 takes as input data x_sand x_tas targets of relationship extraction, and executes a relationship extraction process to extract relationships between the data. Here, the relationship extraction processing unit 200 includes an obtaining unit 201 and a relationship extraction unit 202.

The obtaining unit 201 obtains the data x_sand x_tas targets of relationship extraction from the storage unit 300. The relationship extraction unit 202 extracts relationships between the obtained x_sand x_tby the obtaining unit 201.

Note that the configuration of the relationship extraction device 10 illustrated in FIG. 1 is an example, and another configuration may be adopted. For example, the approximate operator generation processing unit 100 and the relationship extraction processing unit 200 may be included in different devices or equipment.

Next, an approximate operator generation process according to the present embodiment will be described with reference to FIG. 2. FIG. 2 is a flow chart illustrating an example of an approximate operator generation process according to the present embodiment.

The obtaining unit 101 of the approximate operator generation processing unit 100 obtains data each having multiple elements from the storage unit 300 (also obtains y₀, y₁, . . . , y_T−1in the case of (ii) described above) (Step S101).

Next, the approximate operator generation unit 102 of the approximate operator generation processing unit 100 sets t←0 where t is an index indicating the data obtained at Step S101 described above (Step S102).

Next, the approximate operator generation unit 102 of the approximate operator generation processing unit 100 generates an orthonormal vector q_tby using φ(x₀), . . . , φ(x_t) as described in the above (i) and (ii) (φ₁(x₀), . . . , φ₁(x_t) in the case of (ii) described above) (Step S103). Note that an orthonormal vector of W_Tis also generated in the case of (ii) described above.

Next, the approximate operator generation unit 102 of the approximate operator generation processing unit 100 sets t←t+1 (Step S104). Further, the approximate operator generation unit 102 of the approximate operator generation processing unit 100 determines whether t<T (Step S105).

If t<T is determined at Step S105 described above, the approximate operator generation unit 102 of the approximate operator generation processing unit 100 returns to Step S103. Thus, for t=0, . . . , T−1, Step S103 described above is executed, and the orthonormal system {q₀, q₁, . . . , q_T−1} is obtained. Note that in the case of (ii) described above, the orthonormal system of W_Tis also obtained.

If t<T is not determined at Step S105 described above, the approximate operator generation unit 102 of the approximate operator generation processing unit 100 generates an approximate Perron-Frobenius operator ˜K_Tby using the orthonormal system {q₀, q₁, . . . , q_T−1} as described in the above (i) and (ii) (also using the orthonormal system of W_Tin the case of (ii)) (Step S106).

Next, a relationship extraction process according to the present embodiment will be described with reference to FIG. 3. FIG. 3 is a flow chart illustrating an example of a relationship extraction process according to the present embodiment.

The obtaining unit 201 of the relationship extraction processing unit 200 obtains the data x_sand x_tas targets of relationship extraction from the storage unit 300 (Step S201).

Next, the relationship extraction unit 202 of the relationship extraction processing unit 200 extracts relationships between the obtained x_sand x_tobtained at Step S101 described above (Step S102). In other words, the relationship extraction unit 202 approximates k(x_t,x_s)=<φ(x_t), φ(x_s)>_kby Formula (4) described above (Step S202). Accordingly, an n×n matrix is obtained in which each (i,j) component represents the proximity between the i-th component of x_tand the j-th component of x_s(i.e., the relationship between x_t,iand x_s,j), and the relationships between x_sand x_tare extracted.

Application Examples

In the following, several application examples using the approximate Perron-Frobenius operator will be described.

<<Anomaly Detection>>

Suppose that each of x₀, x₁, . . . , x_T−1∈X has n items of time series data. In other words, suppose that x_tincludes x_t,0, . . . , x_t,n-1as n items of time series data, denoted as x_t=[x_t,0, . . . , x_t,n-1]. In the case where φ(x_t) has been obtained, φ(x_t+1) can be predicted by using an approximate Perron-Frobenius operator ˜K_Tobtained by the method described in (i) described above. This prediction can be obtained by Q_T˜K_TQ_T*φ(x_t) as described above.

At this time, assuming that the following equation holds,

[

Math
.

29

]



K
~

T

⁢

Q
T
*

⁢

ϕ
⁡
(

x
t

)

=

∑

s
=
0

T
-
1

ϕ
⁡
(

x
s

)

⁢

c
s

 

Each (j,j) component of the following formula,

[

Math
.

30

]



❘
"[LeftBracketingBar]"

∑

s
=
0

T
-
1

ϕ
⁡
(

x
s

)

⁢

c
s

-

ϕ
⁡
(

x
t

)

❘
"[RightBracketingBar]"

k
2

 

is equivalent to the following:

[

Math
.

31

]





∑

s
=
0

T
-
1

∑

i
=
0

n
-
1

(

c
s

)

i
,
j

⁢

ϕ
~

(

x

s
,
i

)

-

ϕ
~

(

x

t
,
i

)



k
~

 

where ˜φ is a feature map with respect to ˜k, and (c_s)_i,jis the (i,j) component of c_sbeing an n×n matrix.

Therefore, in the case where the (j,j) component of the following formula is large,

[

Math
.

32

]



❘
"[LeftBracketingBar]"

∑

s
=
0

T
-
1

ϕ
⁡
(

x
s

)

⁢

c
s

-

ϕ
⁡
(

x
t

)

❘
"[RightBracketingBar]"

k
2

 

it can be understood that an anomaly occurs in the j-th data item in the n items of time series data.

<<Causal Estimation (Part 1)>>

For n items of time series data, x₀, x₁, . . . , x_T−1∈X are defined such that x_s,i+m″nis data at time s+m″ of the i-th item of the time series data. At this time, consider the case of t=s in Formula (4) described above. For ˜λ_mhaving a magnitude close to 1,

{tilde over (λ)}_m^s{tilde over (λ)}_m^s({tilde over (v)}*_m{tilde over (v)}_m)c*_mc_m [Math. 33]

is unchanged by the change in s; therefore, for ˜λ_mhaving the magnitude close to 1, in the sum of Formula (4) described above, by calculating only the following,

{tilde over (λ)}_m^s{tilde over (λ)}_m^s({tilde over (v)}*_m{tilde over (v)}_m(c*_mc_m [Math. 34]

An unchanged part regardless of the change in s in the approximation of k(x_s,x_s) (the proximity between x_sand x_s) can be extracted. Therefore, if the value of the (i,j+m″n) component of the sum is large, then, x_s,iand x_s,j+m″nare close regardless of s; conversely, if the value of the component (i,j+m″n) is small, then x_s,iand x_s,j+m″nare distant regardless of s. In other words, it can be understood that the change in the i-th data from among the n items of time series data is a cause of the change in the j-th data.

<<Causal Estimation (Part 2)>>

Suppose that each of x₀, x₁, . . . , x_T−1∈X has n items of time series data. In the case where the change in j-th data from among the n items of time series data is a cause of the change in i-th data, consider data ˜x₀, ˜x₁, . . . , ˜x_T−1each obtained by removing the j-th component in x_t(t=0, . . . , T−1). In other words, it is set as ˜x_t=[x_t,0, . . . , x_t,j-1, x_t,j+1, . . . , x_t,n−1]

At this time, in the case of considering that ˜K_Tis generated with ˜x₀, ˜x₁, . . . , ˜x_T−1to predict ˜x_sfor S≥T, this prediction is calculated by Q_T˜K_TQ_T*φ(˜x_s-1); however, among the components of ˜x_s, it is expected that the component corresponding to the i-th data is not approximated well. Therefore, by comparing the components of the following formula,

|Q_T{tilde over (K)}_TQ*_Tϕ({tilde over (x)}_S-1)−ϕ({tilde over (x)}_S)|_k² [Math. 35]

data that changes due to the change in the j-th data as the cause can be identified. In other words, in the case where the (i,i) component of the following formula is large,

|Q_T{tilde over (K)}_TQ*_Tϕ({tilde over (x)}_S-1)−ϕ({tilde over (x)}_S)|_k² [Math. 36]

it can be understood that the change in the j-th data is the cause of the change in the i-th data. In the Granger causality, a linear relationship is assumed between items of data in time series data, whereas the method according to the present embodiment can estimate with good precision even for a nonlinear relationship.

<<Behavior of Proximity Between Elements when t→∞>>

In Formula (4) described above, the term corresponding to ˜λ_m=1 becomes a constant value when t→∞, and a term corresponding to |˜λ_m|<1 becomes zero when t→∞. Therefore, in Formula (4) described above, by setting ˜λ_mnot being 1 to 0, the behavior of the proximity between elements when t→∞ can be understood.

Kernel PCA will be described as one of modified examples of the present embodiment. Let x₀, x₁, . . . , x_T−1∈X be data each having n elements. By using the same notations as used in Step 2 described above, ˜b_tis defined as ˜b_t=U_tD_tU_twhere D_tis a matrix having diagonal components of

√{square root over (λ_t,0)}, . . . ,√{square root over (λ_t,m_t)},0, . . . ,0 [Math. 37]

and having non-diagonal components of all zero. Let ˜B_mbe a matrix having diagonal components of ˜b₀, . . . , ˜b_m-1and non-diagonal components of all zero. In the case of setting ε=0, Φ_m=Q_m(˜B_m+R_m) holds. Also, it can be shown that Cm that satisfies Q_m*Q_m=C_mC_m* exists. Therefore, by calculating the singular value decomposition as C_m*R_m=U_mΣ_mV_m*, and setting w₁=Q_mC_mu₁, it can be shown that under a condition of v_tbeing normal, w₁is a vector that maximizes the following formula:

[

Math
.

38

]



∑

t
=
0

m
-
1



w
⁢

〈

w
,

v
t

〉

k



k
2

 

where u_trepresents a t-th column of U_m. Also, v_tis expressed as follows:

[

Math
.

39

]



v
t

=

ϕ
⁡
(

x
t

)

-

∑

s
=
0

m
-
1

ϕ
⁡
(

x
s

)

 

Therefore, it can be stated that w₁is a vector that best approximates the residual on the RKHM, and this w₁will be referred to as the first principal vector. Similarly, w_t=Q_mC_mU_twill be referred to as a t-th principal vector. Denoting non-zero eigenvalues of Φ_m*Φ_m(a T×T matrix whose (s, t) component is k(x_s, x_t+1)∈A) as λ₀≥ . . . ≥λ₁>0, and the corresponding eigenvectors as v₀, . . . ,v₁, it can be shown w_t=λ_t^−1/2Φ_mv_t; therefore, calculation is carried out in practice in this way. The proximity between data φ(x_s) and the t-th principal vector can be expressed as <w_t,φ(x_s)>_k, and hence, <w_t,φ(x_s)>_kcan be regarded as the t-th principal component of φ(x_s). However, <w_t,φ(x_s)>_ktakes a matrix value, and hence, instead of <w_t,φ(x_s)>_k, for example, by using ∥<w_t,φ(x_s)≥_k∥, a distribution of the data can be visualized. For example, visualization in the two-dimensional plane can be achieved by taking ∥<w₁,φ(x_s)>_k∥ in the horizontal axis and ∥<w_t,φ(x_s)>_k∥ in the vertical axis, and plotting the data. Also, by replacing φ(x_s) with the following formula,

[

Math
.

40

]



ϕ
⁡
(

x
s

)

-

∑

t
=
0

m
-
1

ϕ
⁡
(

x
t

)

 

a centralized kernel PCA can be executed as in the case of general kernel PCA using the RKHS.

Next, evaluation of the method according to the present embodiment will be described.

<<Goodness of Prediction>>

A Kuramoto model on [0,2Π) shown in the following Formula (5) was considered.

[

Math
.

41

]



d
⁢

θ
i

dt

=

ω
i

+

κ
n

⁢

∑

j
=
0

n
-
1

sin
⁡
(

θ
j

-

θ
i

)

(
5
)

where θ_i(0) was assumed to be a random number following a uniform distribution on [0, 2Π), and ω_iwas also assumed to be a random number following the uniform distribution on [0, 2Π).

A dynamical system shown in the following Formula (6) obtained by discretizing Formula (5) described above was considered.

[

Math
.

42

]



x

t
,
i

=

x

t
-
1

,
i

+

Δ
⁢
t
⁢

ω
i

+

Δ
⁢
t
⁢

κ
n

⁢

∑

j
=
0

n
-
1

sin
⁡
(

x

t
-
1

,
j

-

x

t
-
1

,
i

)

(
6
)

Here, on [0, 2Π), the following function was considered,

{tilde over (k)}(x,y)=e^−|e^ix^−e^iy^| [Math. 43]

where the (i,j) component of k(x_t,x_s) was set to ˜k(x_t,i,x_s,j), and Δt=0.01. Also, parameters were also set as n=200, T=10, and m_t=j_tupon normalization. At this time, for S=100, the magnitude |Q_T˜K_TQ_T*φ(x_s-1)|_kof a predicted value was calculated in the cases of a parameter κ representing the strength of interrelation set to κ=1, 10.

A result of plotting values of the respective components of |Q_T˜K_TQ_T*φ(x_s-1)|_K, in the case of κ=1 is illustrated in FIG. 4A. Also, a result of plotting values of the respective components of |Q_T˜K_TQ_T*φ(x_s-1)|_kin the case of κ=10 is illustrated in FIG. 4B. Q_T-K_TQ_T*φ(x_s-1) is an approximation of φ(x_s); therefore, the (i,j) component of |Q_T˜K_TQ_T*φ(x_S-1)|_kis considered to be the (i,j) component of k(x_s,x_s), i.e., an approximation of ˜k(x_s,i,x_s,j). Therefore, if x_s,iand x_s,jare closer to each other, the (i,j) components of |Q_T˜K_TQ_T*φ(x_s-1)|_kshould become greater, or if x_s,iand x_s,jare apart further, the (i,j) components of |Q_T˜K_TQ_T*φ(x_s-1)|_kshould become smaller.

In FIG. 4B, (i,j) components are uniformly greater compared to those in FIG. 4A (i.e., a greater value of K resulted in uniformly greater (i,j) components). Therefore, the value of each component of the predicted value at time S is aligned. In the Kuramoto model, as a certain length of time elapses, the greater K resulted in better aligned values of the elements; therefore, it can be understood that the approximation was obtained precisely.

In fact, in the case of κ=1, 10, results of calculating k (x₁₀, x₁₀) and k (x₁₀₀, x₁₀₀) for x₁₀and x₁₀₀, respectively, obtained directly from Formula (6) described above are illustrated in FIGS. 5A to 5D. Comparing FIG. 4A with FIG. 5C, and FIG. 4B with FIG. 5D, respectively, it can be understood that close values are obtained. Also, comparing FIG. 4B with FIG. 5B and FIG. 5D, although at t=10, these are not yet completely synchronized, by using ˜K_Tapproximated by using data up to t=10, it can be understood the state of t=100 being sufficiently synchronized is predicted.

<<Behavior of Proximity Between Elements when t→∞>>

A Kuramoto model on [0,2Π) shown in the following Formula (7) was considered.

[

Math
.

44

]



d
⁢

θ
i

dt

=

ω
i

+

1
n

⁢

∑

j
=
0

n
-
1

κ

i
,
j

⁢

sin
⁡
(

θ
j

-

θ
i

)

(
7
)

where θ_i(0) was assumed to be a random number following a uniform distribution on [0, 2Π), and ω_iwas also assumed to be a random number following the uniform distribution on [0, 2Π).

A dynamical system shown in the following Formula (8) obtained by discretizing Formula (7) described above was considered.

[

Math
.

45

]



x

t
,
i

=

x

t
-
1

,
i

+

Δ
⁢
t
⁢

ω
i

+

Δ
⁢
t
⁢

1
n

⁢

∑

j
=
0

n
-
1

κ

i
,
j

⁢

sin
⁡
(

x

t
-
1

,
j

-

x

t
-
1

,
i

)

(
8
)

Here, on [0, 2Π), the following function was considered,

{tilde over (k)}(x,y)=e^−|e^ix^−e^iy^| [Math. 46]

where the (i,j) component of k(x_t,x_s) was set to ˜k(x_t,i,x_s,j), and Δt=0.01. Also, ˜K_Twas calculated with n=50, T=10, and m_t=j_tupon normalization. Further, under each of the following Setting 1 and Setting 2, Formula (4) described above was calculated. Here, when calculating Formula (4) described above, zero was assumed except for ˜λ_mclose to 1.

Setting 1: In the case of i>25 and j>25, κ_i,j=100; otherwise κ_i,j=0

Setting 2: In the case of (i<25 or i>35) and (j<25 or j>35), κ_i,j=100; otherwise κ_i,j=0

A result of calculating Formula (4) described above and plotting values of the respective components of the calculated result under Setting 1 described above is illustrated in FIG. 6A. Also, a result of calculating Formula (4) described above and plotting values of the respective components of the calculated result under Setting 2 described above is illustrated in FIG. 6B. Also, taking i in the vertical axis and j in the horizontal axis, a result of plotting the magnitudes of κ_i,junder Setting 1 described above is illustrated in FIG. 7A. Similarly, a result of plotting the magnitudes of κ_i,junder Setting 2 described above is illustrated in FIG. 7B. In the Kuramoto model, elements interacting each other take closer values as time has elapsed sufficiently longer (i.e., elements having large values of κ_i,j). Therefore, it can be understood that the behavior of the proximity when t→∞ can be approximated.

Finally, a hardware configuration of the relationship extraction device 10 according to the present embodiment will be described with reference to FIG. 8. FIG. 8 is a diagram illustrating an example of a hardware configuration of the relationship extraction device 10 according to the present embodiment.

As illustrated in FIG. 8, the relationship extraction device 10 according to the present embodiment is implemented by a generic computer or computer system, and includes an input device 401, a display device 402, an external I/F 403, a communication I/F 404, a processor 405, and a memory device 406. These hardware components are connected via a bus 407 so as to be capable of communicating with each other.

The input device 401 is, for example, a keyboard, a mouse, a touch panel, and the like. The display device 402 is, for example, a display or the like. Note that the relationship extraction device 10 may or may not have at least one of the input device 401 and the display device 402.

The external the I/F 403 is an interface with an external device. The external I/F 403 is an interface with an external device. The external device includes a recording medium 403a or the like. The relationship extraction device 10 can execute read and write with the recording medium 403a via the external I/F 403. The recording medium 403a may store, for example, one or more programs that implement the approximate operator generation processing unit 100 and the relationship extraction processing unit 200.

Note that the recording medium 403a includes, for example, CD(Compact Disc), DVD(Digital Versatile Disk), SD memory card (Secure Digital memory card), USB(Universal Serial Bus) memory card, and the like.

The communication I/F 404 is an interface for connecting the relationship extraction device 10 to a communication network. Note that one or more programs that implements the approximate operator generation processing unit 100 and relationship extraction processing unit 200 may be obtained (downloaded) from a predetermined server device or the like via the communications I/F 404.

The processor 405 is any of various types of arithmetic/logic devices, for example, a CPU(Central Processing Unit), a GPU(Graphics Processing Unit), and the like. The approximate operator generation processing unit 100 and the relationship extraction processing unit 200 are implemented by, for example, a process in which one or more programs stored in the memory device 406 causes the processor 405 to execute.

The memory device 406 is any of various types of storage devices such as, for example, an HDD (Hard Disk Drive), SSD (Solid State Drive), RAM (Random Access Memory), ROM (Read-Only Memory), flash memory, and the like. The storage unit 300 is implemented by, for example, the memory device 406. However, the storage unit 300 may be implemented by, for example, a storage device connected to the relationship extraction device 10 through a communication network.

By having the hardware configuration illustrated in FIG. 8, the relationship extraction device 10 according to the present embodiment can implement the approximate operator generation process and the relationship extraction process described above. Note that the hardware configuration illustrated in FIG. 8 is an example, and the relationship extraction device 10 may have another hardware configuration. For example, the relationship extraction device 10 may have more than one processors 405 or more than one memory devices 406.

The present invention is not limited to the embodiments described above that have been specifically disclosed, and various modifications, changes, combinations with known techniques, and the like can be made within a range not deviating from the description of the claims.

The present application is based on a base application No. 2020-035051 filed in Japan on Mar. 2, 2020, the entire contents of which are hereby

INCORPORATED BY REFERENCE
List of Reference Numerals

10 relationship extraction device

100 approximate operator generation processing unit

101 obtaining unit

102 approximate operator generation unit

200 relationship extraction processing unit

201 obtaining unit

202 relationship extraction unit

300 storage unit

401 input device

402 display device

403 external I/F

403a recording media

404 communication I/F

405 processor

406 memory device

407 bus