Fast, approximate conditional distribution sampling

A computer-executed method for an importance-based machine learning (ML) explainer for an ML model, comprising:

• generating a KD-Tree that comprises the data instances of a particular dataset to be sampled;
• wherein the KD-Tree comprises a plurality of buckets;
• wherein each bucket, of the plurality of buckets, includes a unique set of similar data instances from the particular dataset;
• generating a random sample dataset from the particular dataset by, for each bucket of the plurality of buckets, including, in the random sample dataset, a randomly-selected subset of the unique set of similar data instances in said each bucket, wherein:
• each data instance in the particular data set has a set of features,
• the set of features comprises a subset of features that are to be kept and a subset of features that are to be replaced, and
• the subset of features that are to be replaced includes a particular feature to be tested;
• identifying a set of nearest neighbor data instances, from the random sample dataset, based on one or more similarities between a target data instance in the particular dataset and the nearest neighbor data instances, wherein each data instance, of the set of nearest neighbor data instances, is one of the particular number of data instances nearest to the target data instance among the data instances of the random sample dataset in a subspace of the subset of features that are to be kept;
• generating a set of perturbed data instances, based on the target instance, by generating, for each nearest neighbor data instance of the set of nearest neighbor data instances, a corresponding perturbed data instance comprising:
• a feature value of said each nearest neighbor data instance for the subset of features that are to be replaced of the corresponding generated data instance, and feature values of the target data instance for the subset of features that are to be kept;
• and
• generating an importance score for at least the particular tested feature for the ML model based on a difference between output of the ML model using the target data instance and output of the ML model using the set of perturbed data instances,
• wherein the method is performed by one or more computing devices.

One or more non-transitory computer-readable media storing one or more sequences of instructions that, when executed by one or more processors, cause:

• randomly sampling a particular dataset to generate, in memory, a random sample dataset of the particular dataset, wherein:
• each data instance in the particular data set has a set of features,
• the set of features comprises a subset of features that are to be kept and a subset of features that are to be replaced, and
• the subset of features that are to be replaced includes a particular feature to be tested;
• after randomly sampling the particular dataset to identify the random sample dataset:
• identifying a set of nearest neighbor data instances, from the random sample dataset, based on one or more similarities between the subset of features that are to be kept in a target data instance in the particular dataset and the subset of features that are to be kept in the nearest neighbor data instances of the set of nearest neighbor data instances;
• wherein the set of nearest neighbor data instances has a particular number of data instances;
• wherein each data instance, of the set of nearest neighbor data instances, is one of the particular number of data instances nearest to the target data instance among the data instances of the random sample dataset in a subspace of the subset of features that are to be kept;
• generating a set of perturbed data instances, based on the target instance, by generating, for each nearest neighbor data instance of the set of nearest neighbor data instances, a corresponding perturbed data instance comprising:
• a feature value of said each nearest neighbor data instance for the subset of features that are to be replaced of the corresponding generated data instance, and feature values of the target data instance for the subset of features that are to be kept;
• and
• generating an importance score for at least the particular tested feature for an ML model based on a difference between output of the ML model using the target data instance and output of the ML model using the set of perturbed data instances.

One or more non-transitory computer-readable media storing one or more sequences of instructions that, when executed by one or more processors, cause:

• generating a KD-Tree that comprises the data instances of a particular dataset to be sampled;
• wherein the KD-Tree comprises a plurality of buckets;
• wherein each bucket, of the plurality of buckets, includes a unique set of similar data instances from the particular dataset;
• generating a random sample dataset from the particular dataset by, for each bucket of the plurality of buckets, including, in the random sample dataset, a randomly-selected subset of the unique set of similar data instances in said each bucket, wherein:
• each data instance in the particular data set has a set of features,
• the set of features comprises a subset of features that are to be kept and a subset of features that are to be replaced, and
• the subset of features that are to be replaced includes a particular feature to be tested;
• identifying a set of nearest neighbor data instances, from the random sample dataset, based on one or more similarities between a target data instance in the particular dataset and the nearest neighbor data instances, wherein each data instance, of the set of nearest neighbor data instances, is one of the particular number of data instances nearest to the target data instance among the data instances of the random sample dataset in a subspace of the subset of features that are to be kept;
• generating a set of perturbed data instances, based on the target instance, by generating, for each nearest neighbor data instance of the set of nearest neighbor data instances, a corresponding perturbed data instance comprising:
• a feature value of said each nearest neighbor data instance for the subset of features that are to be replaced of the corresponding generated data instance, and feature values of the target data instance for the subset of features that are to be kept;
• and
• generating an importance score for at least the particular tested feature for an ML model based on a difference between output of the ML model using the target data instance and output of the ML model using the set of perturbed data instances.