class_docstr: Uses the Kernel SHAP method to explain the output of any function.
  
  Kernel SHAP is a method that uses a special weighted linear regression
  to compute the importance of each feature. The computed importance values
  are Shapley values from game theory and also coefficients from a local linear
  regression.
  
  Parameters
  ----------
  model : function or iml.Model
      User supplied function that takes a matrix of samples (# samples x # features) and
      computes the output of the model for those samples. The output can be a vector
      (# samples) or a matrix (# samples x # model outputs).
  
  data : numpy.array or pandas.DataFrame or shap.common.DenseData or any scipy.sparse matrix
      The background dataset to use for integrating out features. To determine the impact
      of a feature, that feature is set to "missing" and the change in the model output
      is observed. Since most models aren't designed to handle arbitrary missing data at test
      time, we simulate "missing" by replacing the feature with the values it takes in the
      background dataset. So if the background dataset is a simple sample of all zeros, then
      we would approximate a feature being missing by setting it to zero. For small problems,
      this background dataset can be the whole training set, but for larger problems consider
      using a single reference value or using the ``kmeans`` function to summarize the dataset.
      Note: for the sparse case, we accept any sparse matrix but convert to lil format for
      performance.
  
  feature_names : list
      The names of the features in the background dataset. If the background dataset is
      supplied as a pandas.DataFrame, then ``feature_names`` can be set to ``None`` (default),
      and the feature names will be taken as the column names of the dataframe.
  
  link : "identity" or "logit"
      A generalized linear model link to connect the feature importance values to the model
      output. Since the feature importance values, phi, sum up to the model output, it often makes
      sense to connect them to the output with a link function where link(output) = sum(phi).
      Default is "identity" (a no-op).
      If the model output is a probability, then "logit" can be used to transform the SHAP values
      into log-odds units.
  
  Examples
  --------
  See :ref:`Kernel Explainer Examples <kernel_explainer_examples>`.
class_docstr_tok: ["Uses","the","Kernel","SHAP","method","to","explain","the","output","of","any","function",".","Kernel","SHAP","is","a","method","that","uses","a","special","weighted","linear","regression","to","compute","the","importance","of","each","feature",".","The","computed","importance","values","are","Shapley","values","from","game","theory","and","also","coefficients","from","a","local","linear","regression",".","Parameters","--","--","--","--","--","model",":","function","or","iml.Model","User","supplied","function","that","takes","a","matrix","of","samples","(","#","samples","x","#","features",")","and","computes","the","output","of","the","model","for","those","samples",".","The","output","can","be","a","vector","(","#","samples",")","or","a","matrix","(","#","samples","x","#","model","outputs",")",".","data",":","numpy.array","or","pandas.DataFrame","or","shap.common.DenseData","or","any","scipy.sparse","matrix","The","background","dataset","to","use","for","integrating","out","features",".","To","determine","the","impact","of","a","feature",",","that","feature","is","set","to","``","missing","''","and","the","change","in","the","model","output","is","observed",".","Since","most","models","are","n't","designed","to","handle","arbitrary","missing","data","at","test","time",",","we","simulate","``","missing","''","by","replacing","the","feature","with","the","values","it","takes","in","the","background","dataset",".","So","if","the","background","dataset","is","a","simple","sample","of","all","zeros",",","then","we","would","approximate","a","feature","being","missing","by","setting","it","to","zero",".","For","small","problems",",","this","background","dataset","can","be","the","whole","training","set",",","but","for","larger","problems","consider","using","a","single","reference","value","or","using","the","``","kmeans","``","function","to","summarize","the","dataset",".","Note",":","for","the","sparse","case",",","we","accept","any","sparse","matrix","but","convert","to","lil","format","for","performance",".","feature_names",":","list","The","names","of","the","features","in","the","background","dataset",".","If","the","background","dataset","is","supplied","as","a","pandas.DataFrame",",","then","``","feature_names","``","can","be","set","to","``","None","``","(","default",")",",","and","the","feature","names","will","be","taken","as","the","column","names","of","the","dataframe",".","link",":","``","identity","''","or","``","logit","''","A","generalized","linear","model","link","to","connect","the","feature","importance","values","to","the","model","output",".","Since","the","feature","importance","values",",","phi",",","sum","up","to","the","model","output",",","it","often","makes","sense","to","connect","them","to","the","output","with","a","link","function","where","link","(","output",")","=","sum","(","phi",")",".","Default","is","``","identity","''","(","a","no-op",")",".","If","the","model","output","is","a","probability",",","then","``","logit","''","can","be","used","to","transform","the","SHAP","values","into","log-odds","units",".","Examples","--","--","--","--","See",":","ref",":","`","Kernel","Explainer","Examples","<","kernel_explainer_examples",">","`","."]
code: def explain(self, incoming_instance, **kwargs):
      # convert incoming input to a standardized iml object
      instance = convert_to_instance(incoming_instance)
      match_instance_to_data(instance, self.data)
  
      # find the feature groups we will test. If a feature does not change from its
      # current value then we know it doesn't impact the model
      self.varyingInds = self.varying_groups(instance.x)
      if self.data.groups is None:
          self.varyingFeatureGroups = np.array(
              [i for i in self.varyingInds]
          )
          self.M = self.varyingFeatureGroups.shape[0]
      else:
          self.varyingFeatureGroups = [
              self.data.groups[i] for i in self.varyingInds
          ]
          self.M = len(self.varyingFeatureGroups)
          groups = self.data.groups
          # convert to numpy array as it is much faster if not jagged array (all groups of same length)
          if self.varyingFeatureGroups and all(
              len(groups[i]) == len(groups[0]) for i in self.varyingInds
          ):
              self.varyingFeatureGroups = np.array(
                  self.varyingFeatureGroups
              )
              # further performance optimization in case each group has a single value
              if self.varyingFeatureGroups.shape[1] == 1:
                  self.varyingFeatureGroups = (
                      self.varyingFeatureGroups.flatten()
                  )
  
      # find f(x)
      if self.keep_index:
          model_out = self.model.f(instance.convert_to_df())
      else:
          model_out = self.model.f(instance.x)
      if isinstance(model_out, (pd.DataFrame, pd.Series)):
          model_out = model_out.values
      self.fx = model_out[0]
  
      if not self.vector_out:
          self.fx = np.array([self.fx])
  
      # if no features vary then no feature has an effect
      if self.M == 0:
          phi = np.zeros((self.data.groups_size, self.D))
          phi_var = np.zeros((self.data.groups_size, self.D))
  
      # if only one feature varies then it has all the effect
      elif self.M == 1:
          phi = np.zeros((self.data.groups_size, self.D))
          phi_var = np.zeros((self.data.groups_size, self.D))
          diff = self.link.f(self.fx) - self.link.f(self.fnull)
          for d in range(self.D):
              phi[self.varyingInds[0], d] = diff[d]
  
      # if more than one feature varies then we have to do real work
      else:
          self.l1_reg = kwargs.get("l1_reg", "auto")
  
          # pick a reasonable number of samples if the user didn't specify how many they wanted
          self.nsamples = kwargs.get("nsamples", "auto")
          if self.nsamples == "auto":
              self.nsamples = 2 * self.M + 2**11
  
          # if we have enough samples to enumerate all subsets then ignore the unneeded samples
          self.max_samples = 2**30
          if self.M <= 30:
              self.max_samples = 2**self.M - 2
              if self.nsamples > self.max_samples:
                  self.nsamples = self.max_samples
  
          # reserve space for some of our computations
          self.allocate()
  
          # weight the different subset sizes
          num_subset_sizes = int(np.ceil((self.M - 1) / 2.0))
          num_paired_subset_sizes = int(np.floor((self.M - 1) / 2.0))
          weight_vector = np.array(
              [
                  (self.M - 1.0) / (i * (self.M - i))
                  for i in range(1, num_subset_sizes + 1)
              ]
          )
          weight_vector[:num_paired_subset_sizes] *= 2
          weight_vector /= np.sum(weight_vector)
          log.debug(f"{weight_vector = }")
          log.debug(f"{num_subset_sizes = }")
          log.debug(f"{num_paired_subset_sizes = }")
          log.debug(f"{self.M = }")
  
          # fill out all the subset sizes we can completely enumerate
          # given nsamples*remaining_weight_vector[subset_size]
          num_full_subsets = 0
          num_samples_left = self.nsamples
          group_inds = np.arange(self.M, dtype="int64")
          mask = np.zeros(self.M)
          remaining_weight_vector = copy.copy(weight_vector)
          for subset_size in range(1, num_subset_sizes + 1):
              # determine how many subsets (and their complements) are of the current size
              nsubsets = binom(self.M, subset_size)
              if subset_size <= num_paired_subset_sizes:
                  nsubsets *= 2
              log.debug(f"{subset_size = }")
              log.debug(f"{nsubsets = }")
              log.debug(
                  "self.nsamples*weight_vector[subset_size-1] = {}".format(
                      num_samples_left
                      * remaining_weight_vector[subset_size - 1]
                  )
              )
              log.debug(
                  "self.nsamples*weight_vector[subset_size-1]/nsubsets = {}".format(
                      num_samples_left
                      * remaining_weight_vector[subset_size - 1]
                      / nsubsets
                  )
              )
  
              # see if we have enough samples to enumerate all subsets of this size
              if (
                  num_samples_left
                  * remaining_weight_vector[subset_size - 1]
                  / nsubsets
                  >= 1.0 - 1e-8
              ):
                  num_full_subsets += 1
                  num_samples_left -= nsubsets
  
                  # rescale what's left of the remaining weight vector to sum to 1
                  if remaining_weight_vector[subset_size - 1] < 1.0:
                      remaining_weight_vector /= (
                          1 - remaining_weight_vector[subset_size - 1]
                      )
  
                  # add all the samples of the current subset size
                  w = weight_vector[subset_size - 1] / binom(
                      self.M, subset_size
                  )
                  if subset_size <= num_paired_subset_sizes:
                      w /= 2.0
                  for inds in itertools.combinations(
                      group_inds, subset_size
                  ):
                      mask[:] = 0.0
                      mask[np.array(inds, dtype="int64")] = 1.0
                      self.addsample(instance.x, mask, w)
                      if subset_size <= num_paired_subset_sizes:
                          mask[:] = np.abs(mask - 1)
                          self.addsample(instance.x, mask, w)
              else:
                  break
          log.info(f"{num_full_subsets = }")
  
          # add random samples from what is left of the subset space
          nfixed_samples = self.nsamplesAdded
          samples_left = self.nsamples - self.nsamplesAdded
          log.debug(f"{samples_left = }")
          if num_full_subsets != num_subset_sizes:
              remaining_weight_vector = copy.copy(weight_vector)
              remaining_weight_vector[
                  :num_paired_subset_sizes
              ] /= 2  # because we draw two samples each below
              remaining_weight_vector = remaining_weight_vector[
                  num_full_subsets:
              ]
              remaining_weight_vector /= np.sum(remaining_weight_vector)
              log.info(f"{remaining_weight_vector = }")
              log.info(f"{num_paired_subset_sizes = }")
              ind_set = np.random.choice(
                  len(remaining_weight_vector),
                  4 * samples_left,
                  p=remaining_weight_vector,
              )
              ind_set_pos = 0
              used_masks = {}
              while samples_left > 0 and ind_set_pos < len(ind_set):
                  mask.fill(0.0)
                  ind = ind_set[
                      ind_set_pos
                  ]  # we call np.random.choice once to save time and then just read it here
                  ind_set_pos += 1
                  subset_size = ind + num_full_subsets + 1
                  mask[
                      np.random.permutation(self.M)[:subset_size]
                  ] = 1.0
  
                  # only add the sample if we have not seen it before, otherwise just
                  # increment a previous sample's weight
                  mask_tuple = tuple(mask)
                  new_sample = False
                  if mask_tuple not in used_masks:
                      new_sample = True
                      used_masks[mask_tuple] = self.nsamplesAdded
                      samples_left -= 1
                      self.addsample(instance.x, mask, 1.0)
                  else:
                      self.kernelWeights[used_masks[mask_tuple]] += 1.0
  
                  # add the compliment sample
                  if (
                      samples_left > 0
                      and subset_size <= num_paired_subset_sizes
                  ):
                      mask[:] = np.abs(mask - 1)
  
                      # only add the sample if we have not seen it before, otherwise just
                      # increment a previous sample's weight
                      if new_sample:
                          samples_left -= 1
                          self.addsample(instance.x, mask, 1.0)
                      else:
                          # we know the compliment sample is the next one after the original sample, so + 1
                          self.kernelWeights[
                              used_masks[mask_tuple] + 1
                          ] += 1.0
  
              # normalize the kernel weights for the random samples to equal the weight left after
              # the fixed enumerated samples have been already counted
              weight_left = np.sum(weight_vector[num_full_subsets:])
              log.info(f"{weight_left = }")
              self.kernelWeights[nfixed_samples:] *= (
                  weight_left
                  / self.kernelWeights[nfixed_samples:].sum()
              )
  
          # execute the model on the synthetic samples we have created
          self.run()
  
          # solve then expand the feature importance (Shapley value) vector to contain the non-varying features
          phi = np.zeros((self.data.groups_size, self.D))
          phi_var = np.zeros((self.data.groups_size, self.D))
          for d in range(self.D):
              vphi, vphi_var = self.solve(
                  self.nsamples / self.max_samples, d
              )
              phi[self.varyingInds, d] = vphi
              phi_var[self.varyingInds, d] = vphi_var
  
      if not self.vector_out:
          phi = np.squeeze(phi, axis=1)
          phi_var = np.squeeze(phi_var, axis=1)
  
      return phi
  
imports: import copy
  import gc
  import itertools
  import logging
  import time
  import warnings
  import numpy
  import pandas
  import scipy.sparse
  import sklearn
  from packaging import version
  from scipy.special import binom
  from sklearn.linear_model import Lasso, LassoLarsIC, lars_path
  from sklearn.pipeline import make_pipeline
  from sklearn.preprocessing import StandardScaler
  from tqdm.auto import tqdm
  from .._explanation import Explanation
  from ..utils import safe_isinstance
  from ..utils._exceptions import DimensionError
  from ..utils._legacy import DenseData, SparseData, convert_to_data, convert_to_instance, convert_to_instance_with_index, convert_to_link, convert_to_model, match_instance_to_data, match_model_to_data
  from ._explainer import Explainer
label_desc: Use image node_id 4 for calling the KernelExplainer obj's underlying member method code with example usage: obj.explain(incoming_instance) and returns: phi