docstr: Uses the KL-LUCB algorithm (Kaufmann and Kalyanakrishnan, 2013) together with additional sampling to search
  feature sets (anchors) that guarantee the prediction made by a classifier model. The search is greedy if
  ``beam_size=1``. Otherwise, at each of the `max_anchor_size` steps, `beam_size` solutions are explored.
  By construction, solutions found have high precision (defined as the expected of number of times the classifier
  makes the same prediction when queried with the feature subset combined with arbitrary samples drawn from a
  noise distribution). The algorithm maximises the coverage of the solution found - the frequency of occurrence
  of records containing the feature subset in set of samples.
  
  Parameters
  ----------
  delta
      Used to compute `beta`.
  epsilon
      Precision bound tolerance for convergence.
  desired_confidence
      Desired level of precision (`tau` in `paper <https://homes.cs.washington.edu/~marcotcr/aaai18.pdf>`_).
  beam_size
      Beam width.
  epsilon_stop
      Confidence bound margin around desired precision.
  min_samples_start
      Min number of initial samples.
  max_anchor_size
      Max number of features in result.
  stop_on_first
      Stop on first valid result found.
  coverage_samples
      Number of samples from which to build a coverage set.
  batch_size
      Number of samples used for an arm evaluation.
  verbose
      Whether to print intermediate LUCB & anchor selection output.
  verbose_every
      Print intermediate output every verbose_every steps.
  
  Returns
  -------
  Explanation dictionary containing anchors with metadata like coverage and precision and examples.
docstr_tok: ["Uses","the","KL-LUCB","algorithm","(","Kaufmann","and","Kalyanakrishnan",",","2013",")","together","with","additional","sampling","to","search","feature","sets","(","anchors",")","that","guarantee","the","prediction","made","by","a","classifier","model",".","The","search","is","greedy","if","``","beam_size=1","``",".","Otherwise",",","at","each","of","the","`","max_anchor_size","`","steps",",","`","beam_size","`","solutions","are","explored",".","By","construction",",","solutions","found","have","high","precision","(","defined","as","the","expected","of","number","of","times","the","classifier","makes","the","same","prediction","when","queried","with","the","feature","subset","combined","with","arbitrary","samples","drawn","from","a","noise","distribution",")",".","The","algorithm","maximises","the","coverage","of","the","solution","found","-","the","frequency","of","occurrence","of","records","containing","the","feature","subset","in","set","of","samples",".","Parameters","--","--","--","--","--","delta","Used","to","compute","`","beta","`",".","epsilon","Precision","bound","tolerance","for","convergence",".","desired_confidence","Desired","level","of","precision","(","`","tau","`","in","`","paper","<","https",":","\/\/homes.cs.washington.edu\/~marcotcr\/aaai18.pdf",">","`","_",")",".","beam_size","Beam","width",".","epsilon_stop","Confidence","bound","margin","around","desired","precision",".","min_samples_start","Min","number","of","initial","samples",".","max_anchor_size","Max","number","of","features","in","result",".","stop_on_first","Stop","on","first","valid","result","found",".","coverage_samples","Number","of","samples","from","which","to","build","a","coverage","set",".","batch_size","Number","of","samples","used","for","an","arm","evaluation",".","verbose","Whether","to","print","intermediate","LUCB","&","anchor","selection","output",".","verbose_every","Print","intermediate","output","every","verbose_every","steps",".","Returns","--","--","--","-","Explanation","dictionary","containing","anchors","with","metadata","like","coverage","and","precision","and","examples","."]
code: def anchor_beam(
      self,
      delta: float = 0.05,
      epsilon: float = 0.1,
      desired_confidence: float = 1.0,
      beam_size: int = 1,
      epsilon_stop: float = 0.05,
      min_samples_start: int = 100,
      max_anchor_size: Optional[int] = None,
      stop_on_first: bool = False,
      batch_size: int = 100,
      coverage_samples: int = 10000,
      verbose: bool = False,
      verbose_every: int = 1,
      **kwargs,
  ) -> dict:
      """
      Uses the KL-LUCB algorithm (Kaufmann and Kalyanakrishnan, 2013) together with additional sampling to search
      feature sets (anchors) that guarantee the prediction made by a classifier model. The search is greedy if
      ``beam_size=1``. Otherwise, at each of the `max_anchor_size` steps, `beam_size` solutions are explored.
      By construction, solutions found have high precision (defined as the expected of number of times the classifier
      makes the same prediction when queried with the feature subset combined with arbitrary samples drawn from a
      noise distribution). The algorithm maximises the coverage of the solution found - the frequency of occurrence
      of records containing the feature subset in set of samples.
  
      Parameters
      ----------
      delta
          Used to compute `beta`.
      epsilon
          Precision bound tolerance for convergence.
      desired_confidence
          Desired level of precision (`tau` in `paper <https://homes.cs.washington.edu/~marcotcr/aaai18.pdf>`_).
      beam_size
          Beam width.
      epsilon_stop
          Confidence bound margin around desired precision.
      min_samples_start
          Min number of initial samples.
      max_anchor_size
          Max number of features in result.
      stop_on_first
          Stop on first valid result found.
      coverage_samples
          Number of samples from which to build a coverage set.
      batch_size
          Number of samples used for an arm evaluation.
      verbose
          Whether to print intermediate LUCB & anchor selection output.
      verbose_every
          Print intermediate output every verbose_every steps.
  
      Returns
      -------
      Explanation dictionary containing anchors with metadata like coverage and precision and examples.
      """
  
      # Select coverage set and initialise object state
      coverage_data = self._get_coverage_samples(
          coverage_samples,
          samplers=self.samplers,
      )
      self._init_state(batch_size, coverage_data)
  
      # sample by default 1 or min_samples_start more random value(s)
      (pos,), (total,) = self.draw_samples([()], min_samples_start)
  
      # mean = fraction of labels sampled data that equals the label of the instance to be explained, ...
      # ... equivalent to prec(A) in paper (eq.2)
      mean = np.array([pos / total])
      beta = np.log(1.0 / delta)
      # lower bound on mean precision
      lb = self.dlow_bernoulli(mean, np.array([beta / total]))
  
      # if lower precision bound below tau with margin eps, keep sampling data until lb is high enough ...
      # or mean falls below precision threshold
      while (
          mean > desired_confidence
          and lb < desired_confidence - epsilon
      ):
          (n_pos,), (n_total,) = self.draw_samples([()], batch_size)
          pos += n_pos
          total += n_total
          mean = np.array([pos / total])
          lb = self.dlow_bernoulli(mean, np.array([beta / total]))
  
      # if prec_lb(A) > tau for A=() then the empty result satisfies the constraints ...
      if lb > desired_confidence:
          return {
              "feature": [],
              "mean": [],
              "num_preds": total,
              "precision": [],
              "coverage": [],
              "examples": [],
              "all_precision": mean,
              "success": True,
          }
  
      current_size, best_coverage = 1, -1
      best_of_size: Dict[int, list] = {0: []}
      best_anchor = ()
  
      if max_anchor_size is None:
          max_anchor_size = self.state["n_features"]
  
      # find best result using beam search
      while current_size <= max_anchor_size:
          # create new candidate anchors by adding features to current best anchors
          anchors = self.propose_anchors(best_of_size[current_size - 1])
          # goal is to max coverage given precision constraint P(prec(A) > tau) > 1 - delta (eq.4)
          # so keep tuples with higher coverage than current best coverage
          anchors = [
              anchor
              for anchor in anchors
              if self.state["t_coverage"][anchor] > best_coverage
          ]
  
          # if no better coverage found with added features -> break
          if len(anchors) == 0:
              break
  
          # for each result, get initial nb of samples used and prec(A)
          stats = self.get_init_stats(anchors)
  
          # apply KL-LUCB and return result options (nb of options = beam width) in the form of indices
          candidate_anchors = self.kllucb(
              anchors,
              stats,
              epsilon,
              delta,
              batch_size,
              min(beam_size, len(anchors)),
              verbose=verbose,
              verbose_every=verbose_every,
          )
          # store best anchors for the given result size (nb of features in the result)
          best_of_size[current_size] = [
              anchors[index] for index in candidate_anchors
          ]
          # for each candidate result:
          #   update precision, lower and upper bounds until precision constraints are met
          #   update best result if coverage is larger than current best coverage
          stats = self.get_init_stats(
              best_of_size[current_size], coverages=True
          )
          positives, n_samples = stats["positives"], stats["n_samples"]
          beta = np.log(
              1.0
              / (
                  delta
                  / (1 + (beam_size - 1) * self.state["n_features"])
              )
          )
          kl_constraints = beta / n_samples
          means = stats["positives"] / stats["n_samples"]
          lbs = self.dlow_bernoulli(means, kl_constraints)
          ubs = self.dup_bernoulli(means, kl_constraints)
  
          if verbose:
              print("Best of size ", current_size, ":")
              for i, mean, lb, ub in zip(
                  candidate_anchors, means, lbs, ubs
              ):
                  print(i, mean, lb, ub)
  
          # draw samples to ensure result meets precision criteria
          continue_sampling = self.to_sample(
              means, ubs, lbs, desired_confidence, epsilon_stop
          )
          while continue_sampling.any():
              selected_anchors = [
                  anchors[idx]
                  for idx in candidate_anchors[continue_sampling]
              ]
              pos, total = self.draw_samples(
                  selected_anchors, batch_size
              )
              positives[continue_sampling] += pos
              n_samples[continue_sampling] += total
              means[continue_sampling] = (
                  positives[continue_sampling]
                  / n_samples[continue_sampling]
              )
              kl_constraints[continue_sampling] = (
                  beta / n_samples[continue_sampling]
              )
              lbs[continue_sampling] = self.dlow_bernoulli(
                  means[continue_sampling],
                  kl_constraints[continue_sampling],
              )
              ubs[continue_sampling] = self.dup_bernoulli(
                  means[continue_sampling],
                  kl_constraints[continue_sampling],
              )
              continue_sampling = self.to_sample(
                  means, ubs, lbs, desired_confidence, epsilon_stop
              )
  
          # anchors who meet the precision setting and have better coverage than the best anchors so far
          coverages = stats["coverages"]
          valid_anchors = (means >= desired_confidence) & (
              lbs > desired_confidence - epsilon_stop
          )
          better_anchors = (
              valid_anchors & (coverages > best_coverage)
          ).nonzero()[0]
  
          if verbose:
              for i, valid, mean, lb, ub, coverage in zip(
                  candidate_anchors,
                  valid_anchors,
                  means,
                  lbs,
                  ubs,
                  coverages,
              ):
                  t = anchors[i]
                  print(
                      "%s mean = %.2f lb = %.2f ub = %.2f coverage: %.2f n: %d"
                      % (
                          t,
                          mean,
                          lb,
                          ub,
                          coverage,
                          self.state["t_nsamples"][t],
                      )
                  )
                  if valid:
                      print(
                          "Found eligible result ",
                          t,
                          "Coverage:",
                          coverage,
                          "Is best?",
                          coverage > best_coverage,
                      )
  
          if better_anchors.size > 0:
              best_anchor_idx = better_anchors[
                  np.argmax(coverages[better_anchors])
              ]
              best_coverage = coverages[best_anchor_idx]
              best_anchor = anchors[candidate_anchors[best_anchor_idx]]
              if best_coverage == 1.0 or stop_on_first:
                  break
  
          current_size += 1
  
      # if no result is found, choose highest precision of best result candidate from every round
      if not best_anchor:
          success = (
              False  # indicates the method has not found an anchor
          )
          logger.warning(
              f"Could not find an anchor satisfying the {desired_confidence} precision constraint. "
              f"Now returning the best non-eligible result. The desired precision threshold might not be "
              f"achieved due to the quantile-based discretisation of the numerical features. The "
              f"resolution of the bins may be too large to find an anchor of required precision. "
              f"Consider increasing the number of bins in `disc_perc`, but note that for some "
              f"numerical distribution (e.g. skewed distribution) it may not help."
          )
          anchors = []
          for i in range(0, current_size):
              anchors.extend(best_of_size[i])
          stats = self.get_init_stats(anchors)
          candidate_anchors = self.kllucb(
              anchors,
              stats,
              epsilon,
              delta,
              batch_size,
              1,  # beam size
              verbose=verbose,
          )
          best_anchor = anchors[candidate_anchors[0]]
      else:
          success = True
  
      return self.get_anchor_metadata(
          best_anchor, success, batch_size=batch_size
      )
  
imports: import copy
  import logging
  from collections import defaultdict, namedtuple
  from typing import Callable, Dict, List, Optional, Set, Tuple
  import numpy
  from alibi.utils.distributions import kl_bernoulli
label_desc: Use image node_id 16 for calling the AnchorBaseBeam obj's underlying member method code with example usage: obj.anchor_beam(delta, epsilon, desired_confidence, beam_size, epsilon_stop, min_samples_start, max_anchor_size, stop_on_first, batch_size, coverage_samples, verbose, verbose_every) and returns: self, dict