# US 11,443,198 B1 · Directed acyclic graph machine learning system

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 11,443,198 B1
- Document ID: US11443198B1
- Status: Granted
- Kind: B1
- Application number: 17/522,062
- Filed: 2021-11-09
- Granted: 2022-09-13
- Earliest claimed: 2021-07-18
- Assignees: SAS Institute Inc.
- Applicants: SAS Institute Inc.
- Inventors: Xilong Chen; Tao Huang; Jan Chvosta
- Web page: https://patentgrep.com/patent/US11443198B1

## CPC

- G06N 5/022: Knowledge engineering; Knowledge acquisition
- G06N 20/00: Machine learning
- G06F 17/16: Matrix or vector computation {, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization (matrix transposition G06F7/78)}
- G06F 17/10: Complex mathematical operations {(function generation by table look-up G06F1/03; evaluation of elementary functions by calculation G06F7/544)}
- G06N 5/02: Knowledge representation; Symbolic representation
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A computing device learns a directed acyclic graph (DAG). An SSCP matrix is computed from variable values defined for observation vectors. A topological order vector is initialized that defines a topological order for the variables. A loss value is computed using the topological order vector and the SSCP matrix. (A) A neighbor determination method is selected. (B) A next topological order vector is determined relative to the initialized topological order vector using the neighbor determination method. (C) A loss value is computed using the next topological order vector and the SSCP matrix. (D) (B) and (C) are repeated until each topological order vector is determined in (B) based on the neighbor determination method. A best topological vector is determined from each next topological order vector based on having a minimum value for the computed loss value. An adjacency matrix is computed using the best topological vector and the SSCP matrix.

## Claims

### Claim 1

A non-transitory computer-readable medium having stored thereon computer-readable instructions that when executed by a computing device cause the computing device to:
compute a sum of square and cross products (SSCP) matrix from variable values of a plurality of variables defined for a plurality of observation vectors, wherein the SSCP matrix has a dimension of Nv×Nv, where Nv is a number of the plurality of variables;
initialize a topological order vector that defines a topological order for the plurality of variables;
compute an initial loss value using the initialized topological order vector and the computed SSCP matrix;
learn a directed acyclic graph by
(A) selecting a neighbor determination method;
(B) determining a next topological order vector using the selected neighbor determination method;
(C) computing a loss value using the determined next topological order vector and the computed SSCP matrix;
(D) repeating (B) and (C) until each topological order vector is determined in (B) based on the selected neighbor determination method;
(E) determining a best topological order vector from each determined next topological order vector based on having a minimum value for the computed loss value; and
(F) computing an adjacency matrix using the determined best topological order vector and the computed SSCP matrix, wherein the adjacency matrix has the dimension of Nv×Nv, wherein values in the computed adjacency matrix indicate whether a variable is a parent of another variable; and
(G) output the computed adjacency matrix, wherein data in the computed adjacency matrix defines the directed acyclic graph based on the plurality of observation vectors wherein the directed acyclic graph describes relationships among the plurality of variables.

### Claim 2 (depends on 1)

The non-transitory computer-readable medium of claim 1, wherein the SSCP matrix is computed using SSCP=XτX, where SSCP indicates the computed SSCP matrix, X is an input matrix having dimension N×Nv, wherein X=xi,j, j=1, . . . , Nv; i=1, . . . , N, xi,j is a jth variable value of the plurality of variables of the ith observation vector of the plurality of observation vectors, τ indicates a transpose, and N is a number of the plurality of observation vectors.

### Claim 3 (depends on 1)

The non-transitory computer-readable medium of claim 1, wherein (B) and (C) are repeated for i*j topological order vectors, where i=1, . . . , Nv−1 and j=i, . . . , Nv.

### Claim 4 (depends on 1)

The non-transitory computer-readable medium of claim 1, wherein the topological order vector includes a unique index assigned to each variable of the plurality of variables.

### Claim 5 (depends on 4)

The non-transitory computer-readable medium of claim 4, wherein the topological order vector is initialized based on an order of the unique index assigned to each variable of the plurality of variables.

### Claim 6 (depends on 4)

The non-transitory computer-readable medium of claim 4, wherein the topological order vector is initialized by randomly selecting a variable of the plurality of variables that has not been added to the topological order vector and adding the unique index associated with the randomly selected variable to the topological order vector until all of the unique indices are added to the topological order vector.

### Claim 7 (depends on 4)

The non-transitory computer-readable medium of claim 4, wherein the topological order vector is initialized by computing a variance value for each variable from the variable values of each respective variable of the plurality of variables and by adding the unique index associated with each variable to the topological order vector in order based on the computed variance value.

### Claim 8 (depends on 7)

The non-transitory computer-readable medium of claim 7, wherein the unique index associated with each variable is added to the topological order vector in increasing order of the computed variance value.

### Claim 9 (depends on 4)

The non-transitory computer-readable medium of claim 4, wherein initializing the topological order vector comprises:
initializing the topological order vector to an empty vector;
(H) identifying a variable of the plurality of variables that has no parent based on values associated with the identified variable in a predefined, initial adjacency matrix;
(I) adding the unique index associated with the identified variable of the plurality of variables to the topological order vector;
(J) removing the identified variable as a parent of remaining variables of the plurality of variables that have not been added to the topological order vector; and
repeating (H) through (J) until each variable of the plurality of variables is identified in (H).

### Claim 10 (depends on 9)

The non-transitory computer-readable medium of claim 9, wherein before initializing the topological order vector, the computer-readable instructions further cause the computing device to compute the predefined, initial adjacency matrix using the plurality of observation vectors.

### Claim 11 (depends on 4)

The non-transitory computer-readable medium of claim 4, wherein the topological order vector is initialized using r0=rank({tilde over (p)}), where r0 is the topological order vector, and {tilde over (p)} is a predefined vector.

### Claim 12 (depends on 11)

The non-transitory computer-readable medium of claim 11, wherein before initializing the topological order vector, the computer-readable instructions further cause the computing device to compute the predefined vector using the plurality of observation vectors.

### Claim 13 (depends on 1)

The non-transitory computer-readable medium of claim 1, wherein after (F) and before (G), the computer-readable instructions further cause the computing device to:
compute an estimation error matrix We based on the determined best topological order vector, wherein the estimation error matrix has the dimension of Nv×Nv, wherein values in the computed estimation error matrix indicate an error value associated with each respective element of the computed adjacency matrix;
initializing a t-statistic matrix Wt with zeroes, wherein the t-statistic matrix Wt has the dimension of Nv×Nv;
initializing a matrix Wρ with ones, wherein the matrix Wρ has the dimension of Nv×Nv;
updating the t-statistic matrix Wt such that when We(i, j)>0, Wt(i, j)=W(i, j)/We(i, j), i=1, . . . , Nv, j=1, . . . , Nv, where W is the computed adjacency matrix;
updating the matrix Wρ such that when Wt(i, j)>0, Wρ(i, j)=2 (1−cdf(NORMAL, Wt(i, j))), and when Wt(i, j)<0, Wρ(i, j)=2 (cdf(NORMAL, Wt(i, j))), i=1, . . . , Nv, j=1, . . . , Nv, where cdf indicates a cumulative distribution function computation based on a normal distribution function NORMAL with the t-statistic matrix Wt(i, j) value as the random variable; and
setting W(i, j)=0, when Wρ(i, j)>T, and W(i, j)=1, when Wρ(i, j)≤T, i=1, . . . , Nv, j=1, . . . , Nv, where T is a predefined threshold value.

### Claim 14 (depends on 13)

The non-transitory computer-readable medium of claim 13, wherein computing the estimation error matrix comprises:
initializing an index value;
permuting the computed SSCP matrix using the determined best topological order vector;
(H) sweeping the permuted SSCP matrix based on the index value to define a swept SSCP matrix;
(I) computing We(j, i+1)=√{square root over (SSCPs(i+1,i+1)*SSCPs(j,j)/(N−i))}, j=1, . . . i, where i is the index value, SSCPs is the defined, swept SSCP matrix, and N is a number of the plurality of observation vectors;
(J) incrementing the index value;
repeating (H) through (J) until i>(Nv−1); and
permuting the computed estimation error matrix using the determined best topological order vector.

### Claim 15 (depends on 14)

The non-transitory computer-readable medium of claim 14, wherein the computed SSCP matrix is permuted using SSCPp=Pτ(rb)·SSCP·P(rb), where SSCP indicates the computed SSCP matrix, rb indicates the determined best topological order vector, P indicates a permutation matrix, and τ indicates a transpose, wherein the permutation matrix is defined using P(k, l)=1, when rb(k)=l,k=1, . . . , Nv, l=1, . . . , Nv; else P(k, l)=0.

### Claim 16 (depends on 14)

The non-transitory computer-readable medium of claim 14, wherein the computed estimation error matrix is permuted using We=P(rb)·We·Pτ(rb), where rb indicates the determined best topological order vector, P indicates a permutation matrix, and τ indicates a transpose, wherein the permutation matrix is defined using P(k, l)=1, when rb(k)=l, k=1, . . . , Nv, l=1, . . . , Nv; else P(k, l)=0.

### Claim 17 (depends on 1)

The non-transitory computer-readable medium of claim 1, wherein computing the adjacency matrix comprises:
initializing an index value to one;
permuting the computed SSCP matrix using the determined best topological order vector;
(H) sweeping the permuted SSCP matrix based on the index value to define a swept SSCP matrix;
(I) computing W(j, i+1)=SSCPs(j, i+1), j=1, . . . i, where W is the computed adjacency matrix, i is the index value, and SSCPs is the defined, swept SSCP matrix;
(J) incrementing the index value by one;
repeating (H) through (J) until i>(Nv−1); and
permuting the computed adjacency matrix using the determined best topological order vector.

### Claim 18 (depends on 17)

The non-transitory computer-readable medium of claim 17, wherein the computed SSCP matrix is permuted using SSCPp=Pτ(rb)·SSCP·P(rb), where SSCP indicates the computed SSCP matrix, rb indicates the determined best topological order vector, P indicates a permutation matrix, and τ indicates a transpose, wherein the permutation matrix is defined using P(k, l)=1, when rb (k)=l, k=1, . . . , Nv, l=1, . . . , Nv; else P(k, l)=0.

### Claim 19 (depends on 17)

The non-transitory computer-readable medium of claim 17, wherein the computed adjacency matrix is permuted using W=P(rb)·W·Pτ(rb), where rb indicates the determined best topological order vector, P indicates a permutation matrix, and τ indicates a transpose, wherein the permutation matrix is defined using P(k, l)=1, when rb(k)=l, k=1, . . . , Nv, l=1, . . . , Nv; else P(k, l)=0.

### Claim 20 (depends on 1)

The non-transitory computer-readable medium of claim 1, wherein computing the loss value in (C) comprises:
initializing an index value to one;
permuting the computed SSCP matrix using the determined next topological order vector;
(H) adding SSCPp(i, i) to the loss value, where SSCPp is the permuted SSCP matrix, and i is the index value;
(I) sweeping the permuted SSCP matrix based on the index value to redefine SSCPp;
(J) incrementing the index value by one;
repeating (H) through (J) until i>(Nv−1); and
adding SSCPp(Nv, Nv) to the loss value.

### Claim 21 (depends on 20)

The non-transitory computer-readable medium of claim 20, wherein the computed SSCP matrix is permuted using SSCPp=Pτ(r)·SSCP·P(r), where SSCP indicates the computed SSCP matrix, r indicates the determined next topological vector, P indicates a permutation matrix, and τ indicates a transpose, wherein the permutation matrix is defined using P(k, l)=1, when r(k)=l,k=1, . . . , Nv, l=1, . . . , Nv; else P (k, l)=0.

### Claim 22 (depends on 1)

The non-transitory computer-readable medium of claim 1, wherein the SSCP matrix is computed using SSCP=DτD, where SSCP indicates the computed SSCP matrix, D is a matrix having dimension N×(K+1)Nv, τ indicates a transpose, and N is a number of the plurality of observation vectors, wherein D is defined from the plurality of observation vectors, and a plurality of orthogonal vectors computed for each orthogonal basis function of a plurality of predefined orthogonal basis functions, where K is a number of the plurality of predefined orthogonal basis functions.

### Claim 23 (depends on 22)

The non-transitory computer-readable medium of claim 22, wherein the plurality of observation vectors is distributed across a plurality of computing devices, wherein the SSCP matrix is computed by each computing device of the plurality of computing devices on a subset of the plurality of observation vectors distributed to a respective computing device.

### Claim 24 (depends on 1)

The non-transitory computer-readable medium of claim 1, wherein computing the loss value in (C) comprises:
initializing a first index value to one;
permuting the computed SSCP matrix using the determined next topological order vector;
(H) adding SSCPp((i−1)*(K+1)+1, (i−1)*(K+1)+1) to the loss value, where SSCPp is the permuted SSCP matrix, i is the first index value, and K is a number of a plurality of predefined orthogonal basis functions;
(I) initializing a second index value to (i−1)*(K+1)+2;
(J) sweeping the permuted SSCP matrix based on the second index value to redefine SSCPp;
(K) incrementing the second index value by one;
(L) repeating (J) through (K) until j>(i−1)*(K+1)+(K+1), where j is the second index value;
(M) incrementing the first index value by one;
repeating (H) through (M) until i>(Nv−1); and
adding SSCPp((Nv−1)*(K+1)+1, (Nv−1)*(K+1)+1) to the loss value.

### Claim 25 (depends on 1)

The non-transitory computer-readable medium of claim 1, wherein determining the next topological order vector in (B) comprises:
initializing a first index value to one;
(H) when rc(k)<i or rc(k)>j, r(k)=rc(k), where r is the next topological order vector, rc is the initialized topological order vector or the next topological order vector determined for a most recent prior iteration of (B) when (B) has been performed at least once, k is the first index value, i is a predefined second index value, and j is a predefined third index value;
(I) when rc(k)=j, r(k)=i;
(J) when i≤rc(k)<j, r(k)=rc(k)+1;
(K) incrementing the first index value by one; and
repeating (H) through (K) until k>Nv, wherein (B) and (C) are repeated for i*j topological order vectors, where i=1, . . . , Nv−1 and j=i, . . . , Nv.

### Claim 26 (depends on 1)

The non-transitory computer-readable medium of claim 1, wherein determining the next topological order vector in (B) comprises:
initializing a first index value to one;
(H) when rc(k)≠i and rc(k)≠j, r(k)=rc(k), where r is the next topological order vector, rc is the initialized topological order vector or the next topological order vector determined for a most recent prior iteration of (B) when (B) has been performed at least once, k is the first index value, i is a predefined second index value, and j is a predefined third index value;
(I) when rc(k)=i, r(k)=j;
(J) when rc(k)=j, r(k)=i;
(K) incrementing the first index value by one;
repeating (H) through (K) until k>Nv, wherein (B) and (C) are repeated for i*j topological order vectors, where i=1, . . . , Nv−1 and j=i, . . . , Nv.

### Claim 27 (depends on 1)

The non-transitory computer-readable medium of claim 1, wherein determining the next topological order vector in (B) comprises:
initializing a first index value to one;
(H) when rc(k)<i or rc(k)>j, r(k)=rc(k), where r is the next topological order vector, rc is the initialized topological order vector or the next topological order vector determined for a most recent prior iteration of (B) when (B) has been performed at least once, k is the first index value, i is a predefined second index value, and j is a predefined third index value;
(I) when rc(k)=i, r(k)=j;
(J) when i<rc(k)≤j, r(k)=rc(k)−1; and
(K) incrementing the first index value by one; and
repeating (H) through (K) until k>Nv, wherein (B) and (C) are repeated for i*j topological order vectors, where i=1, . . . , Nv−1 and j=i, . . . , Nv.

### Claim 28 (depends on 1)

The non-transitory computer-readable medium of claim 1, wherein the neighbor determination method is selected from a plurality of neighbor determination methods, wherein (B), (C), and (D) are performed by each computing device of a plurality of computing devices using a different neighbor determination method of the plurality of neighbor determination methods.

### Claim 29

A computing device comprising:
a processor; and
a non-transitory computer-readable medium operably coupled to the processor, the computer-readable medium having computer-readable instructions stored thereon that, when executed by the processor, cause the computing device to
compute a sum of square and cross products (SSCP) matrix from variable values of a plurality of variables defined for a plurality of observation vectors, wherein the SSCP matrix has a dimension of Nv×Nv, where Nv is a number of the plurality of variables;
initialize a topological order vector that defines a topological order for the plurality of variables;
compute an initial loss value using the initialized topological order vector and the computed SSCP matrix;
learn a directed acyclic graph by
(A) selecting a neighbor determination method;
(B) determining a next topological order vector using the selected neighbor determination method;
(C) computing a loss value using the determined next topological order vector and the computed SSCP matrix;
(D) repeating (B) and (C) until each topological order vector is determined in (B) based on the selected neighbor determination method;
(E) determining a best topological order vector from each determined next topological order vector based on having a minimum value for the computed loss value; and
(F) computing an adjacency matrix using the determined best topological order vector and the computed SSCP matrix, wherein the adjacency matrix has the dimension of Nv×Nv, wherein values in the computed adjacency matrix indicate whether a variable is a parent of another variable; and
(G) output the computed adjacency matrix, wherein data in the computed adjacency matrix defines the directed acyclic graph based on the plurality of observation vectors, wherein the directed acyclic graph describes relationships among the plurality of variables.

### Claim 30

A method of learning a directed acyclic graph, the method comprising:
computing, by a computing device, a sum of square and cross products (SSCP) matrix from variable values of a plurality of variables defined for a plurality of observation vectors, wherein the SSCP matrix has a dimension of Nv×Nv, where Nv is a number of the plurality of variables;
initializing, by the computing device, a topological order vector that defines a topological order for the plurality of variables;
computing, by the computing device, an initial loss value using the initialized topological order vector and the computed SSCP matrix;
learning, by the computing device, a directed acyclic graph by
(A) selecting, by the computing device, a neighbor determination method;
(B) determining, by the computing device, a next topological order vector using the selected neighbor determination method;
(C) computing, by the computing device, a loss value using the determined next topological order vector and the computed SSCP matrix;
(D) repeating, by the computing device, (B) and (C) until each topological order vector is determined in (B) based on the selected neighbor determination method;
(E) determining, by the computing device, a best topological order vector from each determined next topological order vector based on having a minimum value for the computed loss value; and
(F) computing, by the computing device, an adjacency matrix using the determined best topological order vector and the computed SSCP matrix, wherein the adjacency matrix has the dimension of Nv×Nv, wherein values in the computed adjacency matrix indicate whether a variable is a parent of another variable; and
(G) outputting, by the computing device, the computed adjacency matrix, wherein data in the computed adjacency matrix defines the directed acyclic graph based on the plurality of observation vectors, wherein the directed acyclic graph describes relationships among the plurality of variables.