Learning a directed acyclic graph using a machine learning model loss

Abstract

A computing device learns a directed acyclic graph (DAG). (A) A target variable is defined from variables based on a topological order vector and a first index. (B) Input variables are defined from the variables based on the topological order vector and a second index. (C) A machine learning model is trained with observation vectors using the target variable and the input variables. (D) The machine learning model is executed to compute a loss value. (E) The second index is incremented. (F) (B) through (E) are repeated a first plurality of times. (G) The first index is incremented. (H) (A) through (G) are repeated a second plurality of times. A parent set is determined for each variable based on a comparison between the loss value computed each repetition of (D). The parent set is output for each variable to describe the DAG that defines a hierarchical relationship between the variables.

What is claimed is: 
     
         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:
 (A) define a topological order vector, wherein the topological order vector includes an indicator for each variable of a plurality of variables in an order defined such that each variable's parent set is a subset of variables listed in the topological order vector whose order is lower, wherein the plurality of variables have a non-linear relationship;   (B) define a target variable and zero or more input variables from the plurality of variables based on the defined topological order vector;   (C) train a machine learning model with a plurality of observation vectors using the defined target variable and the zero or more input variables, wherein each observation vector of the plurality of observation vectors includes a variable value for each variable of the plurality of variables;   (D) execute the trained machine learning model with a second plurality of observation vectors using the defined target variable and the zero or more input variables to compute a loss value, wherein each observation vector of the second plurality of observation vectors includes the variable value for each variable of the plurality of variables;   (E) repeat (B) through (D) a first plurality of times determined based on a number of the plurality of variables to compute the loss value of the topological order defined in (A);   (F) repeat (A) through (E) a second plurality of times determined based on the number of the plurality of variables, wherein each topological order vector defined in (A) is unique in comparison to other topological order vectors defined in (A);   (G) repeat (A) through (F) a third plurality of times until a best topological order vector is determined based on a comparison between the loss values computed for each topological order vector in (E);   (H) output the determined best topological order vector to describe a hierarchical relationship between the plurality of variables; and   (I) learn a Directed Acyclic Graph (DAG) based on the best topological order vector.   
     
     
         2 . The non-transitory computer-readable medium of  claim 1 , wherein the loss value is a mean squared error value. 
     
     
         3 . The non-transitory computer-readable medium of  claim 1 , wherein the indicator for each variable of the plurality of variables is a unique index assigned to each variable of the plurality of variables. 
     
     
         4 . The non-transitory computer-readable medium of  claim 1 , wherein the second plurality of observation vectors is identical to the plurality of observation vectors. 
     
     
         5 . The non-transitory computer-readable medium of  claim 1 , wherein a different plurality of observation vectors is used in (C) during each iteration of in (E), wherein the loss value is a sum of the loss values computed from each iteration of (D) in (E). 
     
     
         6 . The non-transitory computer-readable medium of  claim 1 , wherein the best topological order vector is determined in (G) as the topological order vector defined in (A) that resulted in a minimum value of the loss value computed for each topological order vector in (E). 
     
     
         7 . The non-transitory computer-readable medium of  claim 1 , wherein the topological order vector is defined in (A) based on a topological order determination method. 
     
     
         8 . The non-transitory computer-readable medium of  claim 1 , wherein the topological order vector is defined in (A) as a unique permutation of the indicator for each variable of the plurality of variables. 
     
     
         9 . The non-transitory computer-readable medium of  claim 1 , wherein the first plurality of times is equal to N v , where N v  indicates a number of the plurality of variables, wherein the loss value computed in (D) during each iteration of (E) is added to the loss value computed in (D) during a previous iteration of (E), wherein the loss value is initialized to zero after (A) and before (E). 
     
     
         10 . The non-transitory computer-readable medium of  claim 1 , wherein, before (B), the computer-readable instructions further cause the computing device to initialize a target variable index, wherein defining the target variable and the zero or more input variables from the plurality of variables based on the defined topological order vector comprises:
 (AB) defining the target variable as the variable indicated by a k th  entry of the topological order vector, wherein k indicates the target variable index; and   (AC) defining the zero or more input variables as preceding entries of the topological order vector in the order defined from l=1, . . . , k−1,   wherein after (AB) and (AC) and before a next repetition of (B) through (E), the computer-readable instructions further cause the computing device to increment the target variable index.   
     
     
         11 . The non-transitory computer-readable medium of  claim 10 , wherein, before (A), the computer-readable instructions further cause the computing device to initialize a first index value i and a second index value j=i+1, wherein defining the topological order vector in (A) comprises:
 (BA) defining a next topological order vector t as a current topological order vector t c , wherein the current topological order vector t c  was defined in a previous iteration of (A) or as an initial topological order vector;   (BB) defining t(n)=t c (n+1) for n=i, . . . , j−1; and   (BC) defining t(j)=t c (i).   
     
     
         12 . The non-transitory computer-readable medium of  claim 11 , wherein, after a current repetition of (E), the computer-readable instructions further cause the computing device to:
 (BD) increment the second index value j;   (BE) when j≤N v , repeat (A) through (D) as part of performing (E);   (BF) when j>N v , increment the first index value i;   (BG) initialize the second index value j=i+1; and   (BH) when i≤N v −1, repeat (A) through (D) as part of performing (E).   
     
     
         13 . The non-transitory computer-readable medium of  claim 11 , wherein the initial 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 indicator associated with the randomly selected variable to the topological order vector until all of the indicators are added to the topological order vector. 
     
     
         14 . The non-transitory computer-readable medium of  claim 10 , wherein, before (A), the computer-readable instructions further cause the computing device to initialize a first index value i and a second index value j=i+1, wherein defining the topological order vector in (A) comprises:
 (BA) defining a next topological order vector t as a current topological order vector t c , wherein the current topological order vector t c  was defined in a previous iteration of (A) or as an initial topological order vector;   (BB) defining t(k+1)=t c (k) for n=i, . . . ,j−1; and   (BC) defining t(i)=t c (j).   
     
     
         15 . The non-transitory computer-readable medium of  claim 10 , wherein, before (A), the computer-readable instructions further cause the computing device to initialize a first index value i and a second index value j=i+1, wherein defining the topological order vector in (A) comprises:
 (BA) defining a next topological order vector t as a current topological order vector t c , wherein the current topological order vector t c  was defined in a previous iteration of (A) or as an initial topological order vector;   (BB) defining t(i)=t c (j); and   (BC) defining t(j)=t c (i).   
     
     
         16 . The non-transitory computer-readable medium of  claim 1 , wherein, before (B), the computer-readable instructions further cause the computing device to:
 (AA) initialize the loss value;   (AB) initialize a target variable index;   (AC) determine whether an equation loss value has been computed based on the defined topological order vector and the target variable index;   (AD) when the equation loss value has been computed, retrieve the computed equation loss value based on an index associated with the defined topological order vector and the target variable index;   (AE) when the equation loss value has not been computed, perform (B), (C), and (D), wherein the loss value computed in (D) is the computed equation loss value;   (AF) add the equation loss value to the loss value; and   (AG) store the computed equation loss value in association with an identifier determined from the defined topological order vector and the target variable index.   
     
     
         17 . The non-transitory computer-readable medium of  claim 16 , wherein the computed equation loss value is stored in an array having a logical dimension of N v *2 N     v     −1 , where N v  indicates a number of the plurality of variables, wherein the computed equation loss value is stored in the array using the identifier as an index into the array. 
     
     
         18 . The non-transitory computer-readable medium of  claim 16 , wherein retrieving the stored, computed equation loss value based on the index comprises:
 sorting the zero or more input variables of the defined topological order vector in ascending order to define a sorted topological order vector;   mapping the sorted topological order vector to the identifier using the target variable index; and   retrieving the equation loss value from the array.   
     
     
         19 . The non-transitory computer-readable medium of  claim 1 , wherein the first plurality of times is based on a predefined neighbor determination method. 
     
     
         20 . The non-transitory computer-readable medium of  claim 1 , wherein the topological order vector is defined in (A) based on a predefined neighbor determination method, where i, j topological order vectors are determined, where i=1, . . . , N v −1, j=i+1, . . . , N v , and N v  indicates a number of the plurality of variables, wherein the plurality of times equals N v *(N v −1)/2. 
     
     
         21 . The non-transitory computer-readable medium of  claim 1 , wherein the determined best topological order vector is used to determine each variable's parent set to define a directed acyclic graph. 
     
     
         22 . The non-transitory computer-readable medium of  claim 1 , wherein, to learn the DAG in (I), the computer-readable instructions further cause the computing device to:
 (J) define a second target variable and a second, zero or more input variables based on a first index and a second index;   (K) train a second machine learning model with the plurality of observation vectors using the defined second target variable and the defined second, zero or more input variables;   (L) execute the trained second machine learning model using the second plurality of observation vectors with the defined second target variable and the defined second, zero or more input variables to compute a residual vector;   (M) repeat (K) through (L) a fourth plurality of times after incrementing the second index;   (N) repeat (J) through (M) a fifth plurality of times after incrementing the first index;   (O) determine a parent set for each variable of the plurality of variables based on a comparison between the residual vector computed in (L); and   (P) output the determined parent set for each variable of the plurality of variables to describe a directed acyclic graph that further defines the hierarchical relationship between the plurality of variables.   
     
     
         23 . The non-transitory computer-readable medium of  claim 22 , wherein, after (H) and before (I), the computer-readable instructions further cause the computing device to:
 (AA) define an initial second target variable and an initial second, zero or more input variables based on the first index;   (AB) train the second machine learning model with the plurality of observation vectors using the defined initial second target variable and the defined initial second, zero or more input variables; and   (AC) execute the second machine learning model trained in (AB) using the second plurality of observation vectors with the defined initial second target variable and the defined initial second, zero or more input variables to compute an initial residual vector.   
     
     
         24 . The non-transitory computer-readable medium of  claim 23 , wherein, after (M) and before (N), the computer-readable instructions further cause the computing device to:
 determine if the residual vector computed in (L) is dependent on the initial residual vector computed in (AC) using an independence test method;   when the residual vector computed in (L) is dependent on the initial residual vector computed in (AC), store an indicator that the variable indicated by an i th  variable is a parent variable of a j th  variable, where i indicates the first index and j indicates the second index.   
     
     
         25 . The non-transitory computer-readable medium of  claim 22 , wherein the fourth plurality of times is equal to a number of the plurality of variables, and the fifth plurality of times is equal to the number of the plurality of variables minus one. 
     
     
         26 . The non-transitory computer-readable medium of  claim 1 , wherein, to learn the DAG in (I), the computer-readable instructions further cause the computing device to:
 (J) define a second target variable based on a first index;   (K) define a second, zero or more input variables based on a second index;   (L) train a second machine learning model with the plurality of observation vectors using the defined second target variable and the defined second, zero or more input variables;   (M) execute the trained second machine learning model using the second plurality of observation vectors with the defined second target variable and the defined second, zero or more input variables to compute a second loss value;   (N) repeat (K) through (M) a fourth plurality of times after incrementing the second index;   (O) identify a third loss value computed in (M) that results when all of the plurality of variables except the defined second target variable are selected as the defined second, zero or more input variables;   (P) identify a fourth loss value computed in (M) that is less than the identified third loss value plus a predefined selection threshold value;   (Q) identify the defined second, zero or more input variables associated with the computation of the fourth loss value in (M);   (R) select the identified second, zero or more input variables as parent variables for the defined second target variable;   (S) repeat (J) through (R) a fifth plurality of times after incrementing the first index; and   (T) output the determined parent variables for each variable of the plurality of variables to describe a directed acyclic graph that further defines the hierarchical relationship between the plurality of variables.   
     
     
         27 . The non-transitory computer-readable medium of  claim 26 , wherein the fourth plurality of times is equal to 2 (i−1) , where i indicates the first index, wherein the fifth plurality of times is equal to N v −1, where N v  indicates a number of the plurality of variables. 
     
     
         28 . The non-transitory computer-readable medium of  claim 26 , wherein, in (P), a plurality of fourth loss values is identified, wherein the fourth loss value is one of the plurality of fourth loss values, wherein, in (Q), the defined second, zero or more input variables associated with each fourth loss value of the plurality of fourth loss values is identified, and after (Q) and before (R), the computer-readable instructions further cause the computing device to:
 determine a number of the defined second, zero or more input variables associated with the computation of each fourth loss value of the plurality of fourth loss values; and   select a minimum number of variables value from the determined number of the defined second, zero or more input variables associated with the computation of each fourth loss value of the plurality of fourth loss values,   wherein, in (R), the identified second, zero or more input variables selected as parent variables for the defined second target variable is the defined second, zero or more input variables associated with the selected minimum number of variables value.   
     
     
         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
 (A) define a topological order vector, wherein the topological order vector includes an indicator for each variable of a plurality of variables in an order defined such that each variable's parent set is a subset of variables listed in the topological order vector whose order is lower, and wherein the plurality of variables have a non-linear relationship; 
 (B) define a target variable and zero or more input variables from the plurality of variables based on the defined topological order vector; 
 (C) train a machine learning model with a plurality of observation vectors using the defined target variable and the zero or more input variables, wherein each observation vector of the plurality of observation vectors includes a variable value for each variable of the plurality of variables; 
 (D) execute the trained machine learning model with a second plurality of observation vectors using the defined target variable and the zero or more input variables to compute a loss value, wherein each observation vector of the second plurality of observation vectors includes the variable value for each variable of the plurality of variables; 
 (E) repeat (B) through (D) a first plurality of times determined based on a number of the plurality of variables to compute the loss value of the topological order defined in (A); 
 (F) repeat (A) through (E) a second plurality of times determined based on the number of the plurality of variables, wherein each topological order vector defined in (A) is unique in comparison to other topological order vectors defined in (A); 
 (G) repeat (A) through (F) a third plurality of times until a best topological order vector is determined based on a comparison between the loss values computed for each topological order vector in (E); 
 (H) output the determined best topological order vector to describe a hierarchical relationship between the plurality of variables; and 
 (I) learn a Directed Acyclic Graph (DAG) based on the best topological order vector. 
   
     
     
         30 . A method of learning a topological order of a plurality of variables, the method comprising:
 (A) defining, by a computing device, a topological order vector, wherein the topological order vector includes an indicator for each variable of a plurality of variables in an order defined such that each variable's parent set is a subset of variables listed in the topological order vector whose order is lower, and wherein the plurality of variables have a non-linear relationship;   (B) defining, by the computing device, a target variable and zero or more input variables from the plurality of variables based on the defined topological order vector;   (C) training, by the computing device, a machine learning model with a plurality of observation vectors using the defined target variable and the zero or more input variables, wherein each observation vector of the plurality of observation vectors includes a variable value for each variable of the plurality of variables;   (D) executing, by the computing device, the trained machine learning model with a second plurality of observation vectors using the defined target variable and the zero or more input variables to compute a loss value, wherein each observation vector of the second plurality of observation vectors includes the variable value for each variable of the plurality of variables;   (E) repeating, by the computing device, (B) through (D) a first plurality of times determined based on a number of the plurality of variables to compute the loss value of the topological order defined in (A);   (F) repeating, by the computing device, (A) through (E) a second plurality of times determined based on the number of the plurality of variables, wherein each topological order vector defined in (A) is unique in comparison to other topological order vectors defined in (A);   (G) repeating, by the computing device, (A) through (F) a third plurality of times until a best topological order vector is determined based on a comparison between the loss values computed for each topological order vector in (E);   (H) outputting, by the computing device, the determined best topological order vector to describe a hierarchical relationship between the plurality of variables, and   (I) learning, by the computing device, a Directed Acyclic Graph (DAG) based on the best topological order vector.