code: def _approximate_shapley_values_via_early_stopping(
      set_func: Callable[[np.ndarray], Union[float, np.ndarray]],
      num_players: int,
      max_num_permutations: int,
      min_percentage_change_threshold: float,
      n_jobs: int,
      num_permutations_per_run: int = 5,
      use_halton_sequence: bool = True,
      num_consecutive_converged_runs: int = 2,
  ) -> np.ndarray:
      """Combines the approximation method described in
  
      Strumbelj, E., Kononenko, I. (2014).
      Explaining prediction models and individual predictions with feature contributions.
      In Knowledge and information systems, 41(3):647–665
  
      with an early stopping criteria. This is, if the Shapley values change less than a certain threshold on average
      between two runs, then stop the estimation.
  
      When use_halton_sequence is true, a Halton sequence is used to fill the sample space more uniformly than randomly
      generating a permutation. This can improve convergence seeing that the sampling aims at maximizing the information
      gain.
      """
      (
          full_subset_result,
          empty_subset_result,
      ) = _estimate_full_and_emtpy_subset_results(set_func, num_players)
  
      shapley_values = None
      old_shap_proxy = np.zeros(num_players)
      evaluated_subsets = {}
      num_generated_permutations = 0
      run_counter = 0
      halton_generator = None
      convergence_tracker = None
  
      if use_halton_sequence:
          halton_generator = Halton(
              num_players,
              seed=int(np.random.randint(np.iinfo(np.int32).max)),
          )
  
      if config.show_progress_bars:
          pbar = tqdm(total=1)
  
      with Parallel(n_jobs=n_jobs) as parallel:
          # The method stops if either the change between some consecutive runs is below the given threshold or the
          # maximum number of runs is reached.
          while True:
              run_counter += 1
              subsets_to_evaluate = set()
  
              # In each run, we create one random permutation of players. For instance, given 4 players, a permutation
              # could be [3,1,4,2].
              if halton_generator is None:
                  permutations = [
                      np.random.choice(
                          num_players, num_players, replace=False
                      )
                      for _ in range(num_permutations_per_run)
                  ]
              else:
                  # Generate k random permutations by sorting the indices of the Halton sequence
                  permutations = np.argsort(
                      halton_generator.random(num_permutations_per_run),
                      axis=1,
                  )
  
              for permutation in permutations:
                  num_generated_permutations += 1
                  # Create all subsets belonging to the generated permutation. This is, if we have [3,1,4,2], then the
                  # subsets are [3], [3,1], [3,1,4] [3,1,4,2].
                  subsets_to_evaluate.update(
                      [
                          subset_tuple
                          for subset_tuple in _create_index_order_and_subset_tuples(
                              permutation
                          )
                          if subset_tuple not in evaluated_subsets
                      ]
                  )
  
              # The result for each subset is cached such that if a subset that has already been evaluated appears again,
              # we can take this result directly.
              evaluated_subsets.update(
                  _evaluate_set_function(
                      set_func, subsets_to_evaluate, parallel, False
                  )
              )
  
              for permutation in permutations:
                  # To improve the runtime, multiple permutations are evaluated in each run.
                  if shapley_values is None:
                      shapley_values = (
                          _estimate_shapley_values_of_permutation(
                              permutation,
                              evaluated_subsets,
                              full_subset_result,
                              empty_subset_result,
                          )
                      )
                  else:
                      shapley_values += (
                          _estimate_shapley_values_of_permutation(
                              permutation,
                              evaluated_subsets,
                              full_subset_result,
                              empty_subset_result,
                          )
                      )
  
              if run_counter > max_num_permutations:
                  break
  
              new_shap_proxy = np.array(shapley_values)
              # The current Shapley values are the average of the estimated values, i.e. we need to divide by the number
              # of generated permutations here.
              new_shap_proxy /= num_generated_permutations
  
              if convergence_tracker is None:
                  if new_shap_proxy.ndim == 2:
                      convergence_tracker = np.zeros(
                          new_shap_proxy.shape[0]
                      )
                  else:
                      convergence_tracker = np.array([0])
  
              if run_counter > 1:
                  mean_percentage_change = 0
  
                  # In case Shapley values are estimated for multiple samples, e.g., in feature relevance. So, we have a
                  # matrix of Shapley values instead of a vector.
                  if new_shap_proxy.ndim == 2:
                      for i in range(new_shap_proxy.shape[0]):
                          (
                              converging,
                              tmp_mean_percentage_change,
                          ) = _check_convergence(
                              new_shap_proxy[i],
                              old_shap_proxy[i],
                              min_percentage_change_threshold,
                          )
  
                          if np.all(converging):
                              convergence_tracker[i] += 1
                          elif (
                              convergence_tracker[i]
                              < num_consecutive_converged_runs
                          ):
                              convergence_tracker[i] = 0
  
                          mean_percentage_change += (
                              tmp_mean_percentage_change
                          )
  
                      mean_percentage_change /= new_shap_proxy.shape[0]
                  else:
                      (
                          converging,
                          tmp_mean_percentage_change,
                      ) = _check_convergence(
                          new_shap_proxy,
                          old_shap_proxy,
                          min_percentage_change_threshold,
                      )
  
                      if np.all(converging):
                          convergence_tracker[0] += 1
                      elif (
                          convergence_tracker[0]
                          < num_consecutive_converged_runs
                      ):
                          convergence_tracker[0] = 0
                      mean_percentage_change = (
                          tmp_mean_percentage_change
                      )
  
                  if config.show_progress_bars:
                      pbar.set_description(
                          f"Estimating Shapley Values. "
                          f"Average change of Shapley values in run {run_counter} "
                          f"({num_generated_permutations} evaluated permutations): "
                          f"{mean_percentage_change * 100}%"
                      )
  
                  if np.all(
                      convergence_tracker
                      >= num_consecutive_converged_runs
                  ):
                      # Here, the change between consecutive runs is below the minimum threshold, but to reduce the
                      # likelihood that this just happened by chance, we require that this happens at least for
                      # num_consecutive_converged_runs times in a row.
                      break
  
              old_shap_proxy = new_shap_proxy
  
      if config.show_progress_bars:
          pbar.update(1)
          pbar.close()
  
      return shapley_values / num_generated_permutations
  
imports: import itertools
  import math
  from enum import Enum
  from typing import Callable, Dict, List, Optional, Set, Tuple, Union
  import numpy
  import scipy
  from joblib import Parallel, delayed
  from scipy.special import comb
  from scipy.stats._qmc import Halton
  from sklearn.linear_model import LinearRegression
  from tqdm import tqdm
  import dowhy.gcm.config
  from dowhy.gcm.util.general import set_random_seed
label_desc: Use image node_id 5 for calling a global function with example usage: _approximate_shapley_values_via_early_stopping(set_func, num_players, max_num_permutations, min_percentage_change_threshold, n_jobs, num_permutations_per_run, use_halton_sequence, num_consecutive_converged_runs) and returns: unknown