Stopping

Stopping criteria for value computations.

This module provides a basic set of stopping criteria, like MaxUpdates, MaxTime, or HistoryDeviation among others. These can behave in different ways depending on the context. For example, MaxUpdates limits the number of updates to values, which depending on the algorithm may mean a different number of utility evaluations or imply other computations like solving a linear or quadratic program.

Creating stopping criteria

The easiest way is to declare a function implementing the interface StoppingCriterionCallable and wrap it with make_criterion(). This creates a StoppingCriterion object that can be composed with other stopping criteria.

Alternatively, and in particular if reporting of completion is required, one can inherit from this class and implement the abstract methods [_check][pydvl.value.stopping.StoppingCriterion._check] and completion.

Composing stopping criteria

Objects of type StoppingCriterion can be composed with the binary operators & (and), and | (or), following the truth tables of Status. The unary operator ~ (not) is also supported. See StoppingCriterion for details on how these operations affect the behavior of the stopping criteria.

References

---

1. Ghorbani, A., Zou, J., 2019. Data Shapley: Equitable Valuation of Data for Machine Learning. In: Proceedings of the 36th International Conference on Machine Learning, PMLR, pp. 2242–2251. ↩

StoppingCriterionCallable

Bases: Protocol

Signature for a stopping criterion

StoppingCriterion(modify_result=True)

Bases: ABC

A composable callable object to determine whether a computation must stop.

A StoppingCriterion is a callable taking a ValuationResult and returning a Status. It also keeps track of individual convergence of values with converged, and reports the overall completion of the computation with completion.

Instances of StoppingCriterion can be composed with the binary operators & (and), and | (or), following the truth tables of Status. The unary operator ~ (not) is also supported. These boolean operations act according to the following rules:

• The results of [_check][pydvl.value.stopping.StoppingCriterion._check] are combined with the operator. See Status for the truth tables.
• The results of converged are combined with the operator (returning another boolean array).
• The completion method returns the min, max, or the complement to 1 of the completions of the operands, for AND, OR and NOT respectively. This is required for cases where one of the criteria does not keep track of the convergence of single values, e.g. MaxUpdates, because completion by default returns the mean of the boolean convergence array.

Subclassing

Subclassing this class requires implementing a [_check][pydvl.value.stopping.StoppingCriterion._check] method that returns a Status object based on a given ValuationResult. This method should update the attribute [_converged][pydvl.value.stopping.StoppingCriterion._converged], which is a boolean array indicating whether the value for each index has converged. When this does not make sense for a particular stopping criterion, completion should be overridden to provide an overall completion value, since its default implementation attempts to compute the mean of [_converged][pydvl.value.stopping.StoppingCriterion._converged].

PARAMETER	DESCRIPTION
modify_result	If True the status of the input ValuationResult is modified in place after the call. TYPE: bool DEFAULT: True

Source code in src/pydvl/value/stopping.py

def __init__(self, modify_result: bool = True):
    self.modify_result = modify_result
    self._converged = np.full(0, False)

converged: NDArray[np.bool_] property

Returns a boolean array indicating whether the values have converged for each data point.

Inheriting classes must set the _converged attribute in their [_check][pydvl.value.stopping.StoppingCriterion._check].

RETURNS	DESCRIPTION
NDArray[numpy.bool_]	A boolean array indicating whether the values have converged for
NDArray[numpy.bool_]	each data point.

completion()

Returns a value between 0 and 1 indicating the completion of the computation.

Source code in src/pydvl/value/stopping.py

def completion(self) -> float:
    """Returns a value between 0 and 1 indicating the completion of the
    computation.
    """
    if self.converged.size == 0:
        return 0.0
    return float(np.mean(self.converged).item())

__call__(result)

Calls [_check][pydvl.value.stopping.StoppingCriterion._check], maybe updating the result.

Source code in src/pydvl/value/stopping.py

def __call__(self, result: ValuationResult) -> Status:
    """Calls [_check][pydvl.value.stopping.StoppingCriterion._check], maybe updating the result."""
    if len(result) == 0:
        logger.warning(
            "At least one iteration finished but no results where generated. "
            "Please check that your scorer and utility return valid numbers."
        )
    status = self._check(result)
    if self.modify_result:  # FIXME: this is not nice
        result._status = status
    return status

AbsoluteStandardError(threshold, fraction=1.0, burn_in=4, modify_result=True)

Bases: StoppingCriterion

Determine convergence based on the standard error of the values.

If \(s_i\) is the standard error for datum \(i\) and \(v_i\) its value, then this criterion returns Converged if \(s_i < \epsilon\) for all \(i\) and a threshold value \(\epsilon \gt 0\).

PARAMETER	DESCRIPTION
threshold	A value is considered to have converged if the standard error is below this value. A way of choosing it is to pick some percentage of the range of the values. For Shapley values this is the difference between the maximum and minimum of the utility function (to see this substitute the maximum and minimum values of the utility into the marginal contribution formula). TYPE: float
fraction	The fraction of values that must have converged for the criterion to return Converged. TYPE: float DEFAULT: 1.0
burn_in	The number of iterations to ignore before checking for convergence. This is required because computations typically start with zero variance, as a result of using empty(). The default is set to an arbitrary minimum which is usually enough but may need to be increased. TYPE: int DEFAULT: 4

Source code in src/pydvl/value/stopping.py

def __init__(
    self,
    threshold: float,
    fraction: float = 1.0,
    burn_in: int = 4,
    modify_result: bool = True,
):
    super().__init__(modify_result=modify_result)
    self.threshold = threshold
    self.fraction = fraction
    self.burn_in = burn_in

MaxChecks(n_checks, modify_result=True)

Bases: StoppingCriterion

Terminate as soon as the number of checks exceeds the threshold.

A "check" is one call to the criterion.

PARAMETER	DESCRIPTION
n_checks	Threshold: if None, no _check is performed, effectively creating a (never) stopping criterion that always returns Pending. TYPE: Optional[int]

Source code in src/pydvl/value/stopping.py

def __init__(self, n_checks: Optional[int], modify_result: bool = True):
    super().__init__(modify_result=modify_result)
    if n_checks is not None and n_checks < 1:
        raise ValueError("n_iterations must be at least 1 or None")
    self.n_checks = n_checks
    self._count = 0

MaxUpdates(n_updates, modify_result=True)

Bases: StoppingCriterion

Terminate if any number of value updates exceeds or equals the given threshold.

Note

If you want to ensure that all values have been updated, you probably want MinUpdates instead.

This checks the counts field of a ValuationResult, i.e. the number of times that each index has been updated. For powerset samplers, the maximum of this number coincides with the maximum number of subsets sampled. For permutation samplers, it coincides with the number of permutations sampled.

PARAMETER	DESCRIPTION
n_updates	Threshold: if None, no _check is performed, effectively creating a (never) stopping criterion that always returns Pending. TYPE: Optional[int]

Source code in src/pydvl/value/stopping.py

def __init__(self, n_updates: Optional[int], modify_result: bool = True):
    super().__init__(modify_result=modify_result)
    if n_updates is not None and n_updates < 1:
        raise ValueError("n_updates must be at least 1 or None")
    self.n_updates = n_updates
    self.last_max = 0

MinUpdates(n_updates, modify_result=True)

Bases: StoppingCriterion

Terminate as soon as all value updates exceed or equal the given threshold.

This checks the counts field of a ValuationResult, i.e. the number of times that each index has been updated. For powerset samplers, the minimum of this number is a lower bound for the number of subsets sampled. For permutation samplers, it lower-bounds the amount of permutations sampled.

PARAMETER	DESCRIPTION
n_updates	Threshold: if None, no _check is performed, effectively creating a (never) stopping criterion that always returns Pending. TYPE: Optional[int]

Source code in src/pydvl/value/stopping.py

def __init__(self, n_updates: Optional[int], modify_result: bool = True):
    super().__init__(modify_result=modify_result)
    self.n_updates = n_updates
    self.last_min = 0

MaxTime(seconds, modify_result=True)

Bases: StoppingCriterion

Terminate if the computation time exceeds the given number of seconds.

Checks the elapsed time since construction

PARAMETER	DESCRIPTION
seconds	Threshold: The computation is terminated if the elapsed time between object construction and a _check exceeds this value. If None, no _check is performed, effectively creating a (never) stopping criterion that always returns Pending. TYPE: Optional[float]

Source code in src/pydvl/value/stopping.py

def __init__(self, seconds: Optional[float], modify_result: bool = True):
    super().__init__(modify_result=modify_result)
    self.max_seconds = seconds or np.inf
    if self.max_seconds <= 0:
        raise ValueError("Number of seconds for MaxTime must be positive or None")
    self.start = time()

HistoryDeviation(n_steps, rtol, pin_converged=True, modify_result=True)

Bases: StoppingCriterion

A simple check for relative distance to a previous step in the computation.

The method used by (Ghorbani and Zou, 2019)¹ computes the relative distances between the current values \(v_i^t\) and the values at the previous checkpoint \(v_i^{t-\tau}\). If the sum is below a given threshold, the computation is terminated.

\[\sum_{i=1}^n \frac{\left| v_i^t - v_i^{t-\tau} \right|}{v_i^t} < \epsilon.\]

When the denominator is zero, the summand is set to the value of \(v_i^{ t-\tau}\).

This implementation is slightly generalised to allow for different number of updates to individual indices, as happens with powerset samplers instead of permutations. Every subset of indices that is found to converge can be pinned to that state. Once all indices have converged the method has converged.

Warning

This criterion is meant for the reproduction of the results in the paper, but we do not recommend using it in practice.

PARAMETER	DESCRIPTION
n_steps	Checkpoint values every so many updates and use these saved values to compare. TYPE: int
rtol	Relative tolerance for convergence (\(\epsilon\) in the formula). TYPE: float
pin_converged	If True, once an index has converged, it is pinned TYPE: bool DEFAULT: True

Source code in src/pydvl/value/stopping.py

def __init__(
    self,
    n_steps: int,
    rtol: float,
    pin_converged: bool = True,
    modify_result: bool = True,
):
    super().__init__(modify_result=modify_result)
    if n_steps < 1:
        raise ValueError("n_steps must be at least 1")
    if rtol <= 0 or rtol >= 1:
        raise ValueError("rtol must be in (0, 1)")

    self.n_steps = n_steps
    self.rtol = rtol
    self.update_op = np.logical_or if pin_converged else np.logical_and
    self._memory = None  # type: ignore

make_criterion(fun, converged=None, completion=None, name=None)

Create a new StoppingCriterion from a function. Use this to enable simpler functions to be composed with bitwise operators

PARAMETER	DESCRIPTION
fun	The callable to wrap. TYPE: StoppingCriterionCallable
converged	A callable that returns a boolean array indicating what values have converged. TYPE: Callable[[], NDArray[numpy.bool_]] | None DEFAULT: None
completion	A callable that returns a value between 0 and 1 indicating the rate of completion of the computation. If not provided, the fraction of converged values is used. TYPE: Callable[[], float] | None DEFAULT: None
name	The name of the new criterion. If None, the __name__ of the function is used. TYPE: str | None DEFAULT: None

RETURNS	DESCRIPTION
Type[StoppingCriterion]	A new subclass of StoppingCriterion.

Source code in src/pydvl/value/stopping.py

def make_criterion(
    fun: StoppingCriterionCallable,
    converged: Callable[[], NDArray[np.bool_]] | None = None,
    completion: Callable[[], float] | None = None,
    name: str | None = None,
) -> Type[StoppingCriterion]:
    """Create a new [StoppingCriterion][pydvl.value.stopping.StoppingCriterion] from a function.
    Use this to enable simpler functions to be composed with bitwise operators

    Args:
        fun: The callable to wrap.
        converged: A callable that returns a boolean array indicating what
            values have converged.
        completion: A callable that returns a value between 0 and 1 indicating
            the rate of completion of the computation. If not provided, the fraction
            of converged values is used.
        name: The name of the new criterion. If `None`, the `__name__` of
            the function is used.

    Returns:
        A new subclass of [StoppingCriterion][pydvl.value.stopping.StoppingCriterion].
    """

    class WrappedCriterion(StoppingCriterion):
        def __init__(self, modify_result: bool = True):
            super().__init__(modify_result=modify_result)
            self._name = name or getattr(fun, "__name__", "WrappedCriterion")

        def _check(self, result: ValuationResult) -> Status:
            return fun(result)

        @property
        def converged(self) -> NDArray[np.bool_]:
            if converged is None:
                return super().converged
            return converged()

        @property
        def name(self):
            return self._name

        def completion(self) -> float:
            if completion is None:
                return super().completion()
            return completion()

    return WrappedCriterion

---

Last update: 2023-09-02
Created: 2023-09-02