Source code for cleanlab.outlier

# Copyright (C) 2017-2023  Cleanlab Inc.
# This file is part of cleanlab.
#
# cleanlab is free software: you can redistribute it and/or modify
# it under the terms of the GNU Affero General Public License as published
# by the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
#
# cleanlab is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU Affero General Public License for more details.
#
# You should have received a copy of the GNU Affero General Public License
# along with cleanlab.  If not, see <https://www.gnu.org/licenses/>.

"""
Methods for finding out-of-distribution examples in a dataset via scores that quantify how atypical each example is compared to the others.

The underlying algorithms are described in `this paper <https://arxiv.org/abs/2207.03061>`_.
"""

import warnings
from typing import Dict, Optional, Tuple, Union

import numpy as np
from sklearn.exceptions import NotFittedError
from sklearn.neighbors import NearestNeighbors

from cleanlab.count import get_confident_thresholds
from cleanlab.internal.label_quality_utils import (
    _subtract_confident_thresholds,
    get_normalized_entropy,
)
from cleanlab.internal.neighbor.knn_graph import correct_knn_distances_and_indices, features_to_knn
from cleanlab.internal.numerics import softmax
from cleanlab.internal.outlier import correct_precision_errors, transform_distances_to_scores
from cleanlab.internal.validation import assert_valid_inputs, labels_to_array
from cleanlab.typing import LabelLike


[docs]class OutOfDistribution: """ Provides scores to detect Out Of Distribution (OOD) examples that are outliers in a dataset. Each example's OOD score lies in [0,1] with smaller values indicating examples that are less typical under the data distribution. OOD scores may be estimated from either: numeric feature embeddings or predicted probabilities from a trained classifier. To get indices of examples that are the most severe outliers, call `~cleanlab.rank.find_top_issues` function on the returned OOD scores. Parameters ---------- params : dict, default = {} Optional keyword arguments to control how this estimator is fit. Effect of arguments passed in depends on if `OutOfDistribution` estimator will rely on `features` or `pred_probs`. These are stored as an instance attribute `self.params`. If `features` is passed in during ``fit()``, `params` could contain following keys: * knn: sklearn.neighbors.NearestNeighbors, default = None Instantiated ``NearestNeighbors`` object that's been fitted on a dataset in the same feature space. Note that the distance metric and `n_neighbors` is specified when instantiating this class. You can also pass in a subclass of ``sklearn.neighbors.NearestNeighbors`` which allows you to use faster approximate neighbor libraries as long as you wrap them behind the same sklearn API. If you specify ``knn`` here, there is no need to later call ``fit()`` before calling ``score()``. If ``knn is None``, then by default: The knn object is instantiated as ``sklearn.neighbors.NearestNeighbors(n_neighbors=k, metric=dist_metric).fit(features)``. - If ``dim(features) > 3``, the distance metric is set to "cosine". - If ``dim(features) <= 3``, the distance metric is set to "euclidean". The implementation of the euclidean distance metric depends on the number of examples in the features array: - For more than 100 rows, it uses scikit-learn's "euclidean" metric. This is for efficiency reasons reasons. - For 100 or fewer rows, it uses scipy's ``scipy.spatial.distance.euclidean`` metric. This is for numerical stability reasons. See: https://scikit-learn.org/stable/modules/neighbors.html See: https://scikit-learn.org/stable/modules/generated/sklearn.metrics.pairwise.euclidean_distances.html See: https://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.distance.euclidean.html * k : int, default=None Optional number of neighbors to use when calculating outlier score (average distance to neighbors). If `k` is not provided, then by default ``k = knn.n_neighbors`` or ``k = 10`` if ``knn is None``. If an existing ``knn`` object is provided, you can still specify that outlier scores should use a different value of `k` than originally used in the ``knn``, as long as your specified value of `k` is smaller than the value originally used in ``knn``. * t : int, default=1 Optional hyperparameter only for advanced users. Controls transformation of distances between examples into similarity scores that lie in [0,1]. The transformation applied to distances `x` is ``exp(-x*t)``. If you find your scores are all too close to 1, consider increasing `t`, although the relative scores of examples will still have the same ranking across the dataset. If `pred_probs` is passed in during ``fit()``, `params` could contain following keys: * confident_thresholds: np.ndarray, default = None An array of shape ``(K, )`` where K is the number of classes. Confident threshold for a class j is the expected (average) "self-confidence" for that class. If you specify `confident_thresholds` here, there is no need to later call ``fit()`` before calling ``score()``. * adjust_pred_probs : bool, True If True, account for class imbalance by adjusting predicted probabilities via subtraction of class confident thresholds and renormalization. If False, you do not have to pass in `labels` later to fit this OOD estimator. See `Northcutt et al., 2021 <https://jair.org/index.php/jair/article/view/12125>`_. * method : {"entropy", "least_confidence"}, default="entropy" Method to use when computing outlier scores based on `pred_probs`. Letting length-K vector ``P = pred_probs[i]`` denote the given predicted class-probabilities for the i-th example in dataset, its outlier score can either be: - ``'entropy'``: ``1 - sum_{j} P[j] * log(P[j]) / log(K)`` - ``'least_confidence'``: ``max(P)`` (equivalent to Maximum Softmax Probability method from the OOD detection literature) - ``gen``: Generalized ENtropy score from the paper of Liu, Lochman, and Zach (https://openaccess.thecvf.com/content/CVPR2023/papers/Liu_GEN_Pushing_the_Limits_of_Softmax-Based_Out-of-Distribution_Detection_CVPR_2023_paper.pdf) """ OUTLIER_PARAMS = {"k", "t", "knn"} OOD_PARAMS = {"confident_thresholds", "adjust_pred_probs", "method", "M", "gamma"} DEFAULT_PARAM_DICT: Dict[str, Union[str, int, float, None, np.ndarray]] = { "k": None, # param for feature based outlier detection (number of neighbors) "t": 1, # param for feature based outlier detection (controls transformation of outlier scores to 0-1 range) "knn": None, # param for features based outlier detection (precomputed nearest neighbors graph to use) "method": "entropy", # param specifying which pred_probs-based outlier detection method to use "adjust_pred_probs": True, # param for pred_probs based outlier detection (whether to adjust the probabilities by class thresholds or not) "confident_thresholds": None, # param for pred_probs based outlier detection (precomputed confident thresholds to use for adjustment) "M": 100, # param for GEN method for pred_probs based outlier detection "gamma": 0.1, # param for GEN method for pred_probs based outlier detection } def __init__(self, params: Optional[dict] = None) -> None: self._assert_valid_params(params, self.DEFAULT_PARAM_DICT) self.params = self.DEFAULT_PARAM_DICT.copy() if params is not None: self.params.update(params) if self.params["adjust_pred_probs"] and self.params["method"] == "gen": print( "CAUTION: GEN method is not recommended for use with adjusted pred_probs. " "To use GEN, we recommend setting: params['adjust_pred_probs'] = False" ) # scaling_factor internally used to rescale distances based on mean distances to k nearest neighbors self.params["scaling_factor"] = None
[docs] def fit_score( self, *, features: Optional[np.ndarray] = None, pred_probs: Optional[np.ndarray] = None, labels: Optional[np.ndarray] = None, verbose: bool = True, ) -> np.ndarray: """ Fits this estimator to a given dataset and returns out-of-distribution scores for the same dataset. Scores lie in [0,1] with smaller values indicating examples that are less typical under the dataset distribution (values near 0 indicate outliers). Exactly one of `features` or `pred_probs` needs to be passed in to calculate scores. If `features` are passed in a ``NearestNeighbors`` object is fit. If `pred_probs` and 'labels' are passed in a `confident_thresholds` ``np.ndarray`` is fit. For details see `~cleanlab.outlier.OutOfDistribution.fit`. Parameters ---------- features : np.ndarray, optional Feature array of shape ``(N, M)``, where N is the number of examples and M is the number of features used to represent each example. For details, `features` in the same format expected by the `~cleanlab.outlier.OutOfDistribution.fit` function. pred_probs : np.ndarray, optional An array of shape ``(N, K)`` of predicted class probabilities output by a trained classifier. For details, `pred_probs` in the same format expected by the `~cleanlab.outlier.OutOfDistribution.fit` function. labels : array_like, optional A discrete array of given class labels for the data of shape ``(N,)``. For details, `labels` in the same format expected by the `~cleanlab.outlier.OutOfDistribution.fit` function. verbose : bool, default = True Set to ``False`` to suppress all print statements. Returns ------- scores : np.ndarray If `features` are passed in, `ood_features_scores` are returned. If `pred_probs` are passed in, `ood_predictions_scores` are returned. For details see return of `~cleanlab.outlier.OutOfDistribution.scores` function. """ scores = self._shared_fit( features=features, pred_probs=pred_probs, labels=labels, verbose=verbose, ) if scores is None: # Fit was called on already fitted object so we just score vals instead scores = self.score(features=features, pred_probs=pred_probs) return scores
[docs] def fit( self, *, features: Optional[np.ndarray] = None, pred_probs: Optional[np.ndarray] = None, labels: Optional[LabelLike] = None, verbose: bool = True, ): """ Fits this estimator to a given dataset. One of `features` or `pred_probs` must be specified. If `features` are passed in, a ``NearestNeighbors`` object is fit. If `pred_probs` and 'labels' are passed in, a `confident_thresholds` ``np.ndarray`` is fit. For details see `~cleanlab.outlier.OutOfDistribution` documentation. Parameters ---------- features : np.ndarray, optional Feature array of shape ``(N, M)``, where N is the number of examples and M is the number of features used to represent each example. All features should be **numeric**. For less structured data (e.g. images, text, categorical values, ...), you should provide vector embeddings to represent each example (e.g. extracted from some pretrained neural network). pred_probs : np.ndarray, optional An array of shape ``(N, K)`` of model-predicted probabilities, ``P(label=k|x)``. Each row of this matrix corresponds to an example `x` and contains the model-predicted probabilities that `x` belongs to each possible class, for each of the K classes. The columns must be ordered such that these probabilities correspond to class 0, 1, ..., K-1. labels : array_like, optional A discrete vector of given labels for the data of shape ``(N,)``. Supported `array_like` types include: ``np.ndarray`` or ``list``. *Format requirements*: for dataset with K classes, labels must be in 0, 1, ..., K-1. All the classes (0, 1, ..., and K-1) MUST be present in ``labels``, such that: ``len(set(labels)) == pred_probs.shape[1]`` If ``params["adjust_confident_thresholds"]`` was previously set to ``False``, you do not have to pass in `labels`. Note: multi-label classification is not supported by this method, each example must belong to a single class, e.g. ``labels = np.ndarray([1,0,2,1,1,0...])``. verbose : bool, default = True Set to ``False`` to suppress all print statements. """ _ = self._shared_fit( features=features, pred_probs=pred_probs, labels=labels, verbose=verbose, )
[docs] def score( self, *, features: Optional[np.ndarray] = None, pred_probs: Optional[np.ndarray] = None ) -> np.ndarray: """ Use fitted estimator and passed in `features` or `pred_probs` to calculate out-of-distribution scores for a dataset. Score for each example corresponds to the likelihood this example stems from the same distribution as the dataset previously specified in ``fit()`` (i.e. is not an outlier). If `features` are passed, returns OOD score for each example based on its feature values. If `pred_probs` are passed, returns OOD score for each example based on classifier's probabilistic predictions. You may have to previously call ``fit()`` or call ``fit_score()`` instead. Parameters ---------- features : np.ndarray, optional Feature array of shape ``(N, M)``, where N is the number of examples and M is the number of features used to represent each example. For details, see `features` in `~cleanlab.outlier.OutOfDistribution.fit` function. pred_probs : np.ndarray, optional An array of shape ``(N, K)`` of predicted class probabilities output by a trained classifier. For details, see `pred_probs` in `~cleanlab.outlier.OutOfDistribution.fit` function. Returns ------- scores : np.ndarray Scores lie in [0,1] with smaller values indicating examples that are less typical under the dataset distribution (values near 0 indicate outliers). If `features` are passed, `ood_features_scores` are returned. The score is based on the average distance between the example and its K nearest neighbors in the dataset (in feature space). If `pred_probs` are passed, `ood_predictions_scores` are returned. The score is based on the uncertainty in the classifier's predicted probabilities. """ self._assert_valid_inputs(features, pred_probs) if features is not None: if self.params["knn"] is None: raise ValueError( "OOD estimator needs to be fit on features first. Call `fit()` or `fit_scores()` before this function." ) scores, _ = self._get_ood_features_scores( features, **self._get_params(self.OUTLIER_PARAMS) ) if pred_probs is not None: if self.params["confident_thresholds"] is None and self.params["adjust_pred_probs"]: raise ValueError( "OOD estimator needs to be fit on pred_probs first since params['adjust_pred_probs']=True. Call `fit()` or `fit_scores()` before this function." ) scores, _ = _get_ood_predictions_scores(pred_probs, **self._get_params(self.OOD_PARAMS)) return scores
def _get_params(self, param_keys) -> dict: """Get function specific dictionary of parameters (i.e. only those in param_keys).""" return {k: v for k, v in self.params.items() if k in param_keys} @staticmethod def _assert_valid_params(params, param_keys): """Validate passed in params and get list of parameters in param that are not in param_keys.""" if params is not None: wrong_params = list(set(params.keys()).difference(set(param_keys))) if len(wrong_params) > 0: raise ValueError( f"Passed in params dict can only contain {param_keys}. Remove {wrong_params} from params dict." ) @staticmethod def _assert_valid_inputs(features, pred_probs): """Check whether features and pred_prob inputs are valid, throw error if not.""" if features is None and pred_probs is None: raise ValueError( "Not enough information to compute scores. Pass in either features or pred_probs." ) if features is not None and pred_probs is not None: raise ValueError( "Cannot fit to OOD Estimator to both features and pred_probs. Pass in either one or the other." ) if features is not None and len(features.shape) != 2: raise ValueError( "Feature array needs to be of shape (N, M), where N is the number of examples and M is the " "number of features used to represent each example. " ) def _shared_fit( self, *, features: Optional[np.ndarray] = None, pred_probs: Optional[np.ndarray] = None, labels: Optional[LabelLike] = None, verbose: bool = True, ) -> Optional[np.ndarray]: """ Shared fit functionality between ``fit()`` and ``fit_score()``. For details, refer to `~cleanlab.outlier.OutOfDistribution.fit` or `~cleanlab.outlier.OutOfDistribution.fit_score`. """ self._assert_valid_inputs(features, pred_probs) scores = None # If none scores are returned, fit was skipped if features is not None: if self.params["knn"] is not None: # No fitting twice if knn object already fit warnings.warn( "A KNN estimator has previously already been fit, call score() to apply it to data, or create a new OutOfDistribution object to fit a different estimator.", UserWarning, ) else: # Get ood features scores if verbose: print("Fitting OOD estimator based on provided features ...") scores, knn = self._get_ood_features_scores( features, **self._get_params(self.OUTLIER_PARAMS) ) self.params["knn"] = knn if pred_probs is not None: if self.params["confident_thresholds"] is not None: # No fitting twice if confident_thresholds object already fit warnings.warn( "Confident thresholds have previously already been fit, call score() to apply them to data, or create a new OutOfDistribution object to fit a different estimator.", UserWarning, ) else: # Get ood predictions scores if verbose: print("Fitting OOD estimator based on provided pred_probs ...") scores, confident_thresholds = _get_ood_predictions_scores( pred_probs, labels=labels, **self._get_params(self.OOD_PARAMS), ) if confident_thresholds is None: warnings.warn( "No estimates need to be be fit under the provided params, so you could directly call " "score() as an alternative.", UserWarning, ) else: self.params["confident_thresholds"] = confident_thresholds return scores def _get_ood_features_scores( self, features: Optional[np.ndarray] = None, knn: Optional[NearestNeighbors] = None, k: Optional[int] = None, t: int = 1, ) -> Tuple[np.ndarray, Optional[NearestNeighbors]]: """ Return outlier score based on feature values using `k` nearest neighbors. The outlier score for each example is computed inversely proportional to the average distance between this example and its K nearest neighbors (in feature space). Parameters ---------- features : np.ndarray Feature array of shape ``(N, M)``, where N is the number of examples and M is the number of features used to represent each example. For details, `features` in the same format expected by the `~cleanlab.outlier.OutOfDistribution.fit` function. knn : sklearn.neighbors.NearestNeighbors, default = None For details, see key `knn` in the params dict arg of `~cleanlab.outlier.OutOfDistribution`. k : int, default=None Optional number of neighbors to use when calculating outlier score (average distance to neighbors). For details, see key `k` in the params dict arg of `~cleanlab.outlier.OutOfDistribution`. t : int, default=1 Controls transformation of distances between examples into similarity scores that lie in [0,1]. For details, see key `t` in the params dict arg of `~cleanlab.outlier.OutOfDistribution`. Returns ------- ood_features_scores : Tuple[np.ndarray, Optional[NearestNeighbors]] Return a tuple whose first element is array of `ood_features_scores` and second is a `knn` Estimator object. """ DEFAULT_K = 10 # fit skip over (if knn is not None) then skipping fit and suggest score else fit. distance_metric = None correct_knn = False if knn is None: # setup default KNN estimator # Make sure both knn and features are not None knn = features_to_knn(features, n_neighbors=k) correct_knn = True features = None # features should be None in knn.kneighbors(features) to avoid counting duplicate data points # Log knn metric as string to ensure compatibility for score correction distance_metric = ( metric if isinstance((metric := knn.metric), str) else str(metric.__name__) ) k = knn.n_neighbors elif k is None: k = knn.n_neighbors max_k = knn.n_neighbors # number of neighbors previously used in NearestNeighbors object if k > max_k: # if k provided is too high, use max possible number of nearest neighbors warnings.warn( f"Chosen k={k} cannot be greater than n_neighbors={max_k} which was used when fitting " f"NearestNeighbors object! Value of k changed to k={max_k}.", UserWarning, ) k = max_k # Fit knn estimator on the features if a non-fitted estimator is passed in try: knn.kneighbors(features) except NotFittedError: knn.fit(features) # Get distances to k-nearest neighbors Note that the knn object contains the specification of distance metric # and n_neighbors (k value) If our query set of features matches the training set used to fit knn, the nearest # neighbor of each point is the point itself, at a distance of zero. distances, indices = knn.kneighbors(features) if ( correct_knn ): # This should only happen if knn is None at the start of this function. Will NEVER happen for approximate KNN provided by user. _features_for_correction = ( knn._fit_X if features is None else features ) # Hacky way to get features (training or test). Storing np.unique results is a hassle. ONLY WORKS WITH sklearn NearestNeighbors object distances, _ = correct_knn_distances_and_indices( features=_features_for_correction, distances=distances, indices=indices, ) # Calculate average distance to k-nearest neighbors avg_knn_distances = distances[:, :k].mean(axis=1) if self.params["scaling_factor"] is None: self.params["scaling_factor"] = float( max(np.median(avg_knn_distances), 100 * np.finfo(np.float_).eps) ) scaling_factor = self.params["scaling_factor"] if not isinstance(scaling_factor, float): raise ValueError(f"Scaling factor must be a float. Got {type(scaling_factor)} instead.") ood_features_scores = transform_distances_to_scores( avg_knn_distances, t, scaling_factor=scaling_factor ) distance_metric = distance_metric or ( metric if isinstance((metric := knn.metric), str) else metric.__name__ ) p = None if distance_metric == "minkowski": p = knn.p ood_features_scores = correct_precision_errors( ood_features_scores, avg_knn_distances, distance_metric, p=p ) return (ood_features_scores, knn)
def _get_ood_predictions_scores( pred_probs: np.ndarray, *, labels: Optional[LabelLike] = None, confident_thresholds: Optional[np.ndarray] = None, adjust_pred_probs: bool = True, method: str = "entropy", M: int = 100, gamma: float = 0.1, ) -> Tuple[np.ndarray, Optional[np.ndarray]]: """Return an OOD (out of distribution) score for each example based on it pred_prob values. Parameters ---------- pred_probs : np.ndarray An array of shape ``(N, K)`` of model-predicted probabilities, `pred_probs` in the same format expected by the `~cleanlab.outlier.OutOfDistribution.fit` function. confident_thresholds : np.ndarray, default = None For details, see key `confident_thresholds` in the params dict arg of `~cleanlab.outlier.OutOfDistribution`. labels : array_like, optional `labels` in the same format expected by the `~cleanlab.outlier.OutOfDistribution.fit` function. adjust_pred_probs : bool, True Account for class imbalance in the label-quality scoring. For details, see key `adjust_pred_probs` in the params dict arg of `~cleanlab.outlier.OutOfDistribution`. method : {"entropy", "least_confidence", "gen"}, default="entropy" Which method to use for computing outlier scores based on pred_probs. For details see key `method` in the params dict arg of `~cleanlab.outlier.OutOfDistribution`. M : int, default=100 For GEN method only. Hyperparameter that controls the number of top classes to consider when calculating OOD scores. gamma : float, default=0.1 For GEN method only. Hyperparameter that controls the weight of the second term in the GEN score. Returns ------- ood_predictions_scores : Tuple[np.ndarray, Optional[np.ndarray]] Returns a tuple. First element is array of `ood_predictions_scores` and second is an np.ndarray of `confident_thresholds` or None is 'confident_thresholds' is not calculated. """ valid_methods = ( "entropy", "least_confidence", "gen", ) if (confident_thresholds is not None or labels is not None) and not adjust_pred_probs: warnings.warn( "OOD scores are not adjusted with confident thresholds. If scores need to be adjusted set " "params['adjusted_pred_probs'] = True. Otherwise passing in confident_thresholds and/or labels does not change " "score calculation.", UserWarning, ) if adjust_pred_probs: if confident_thresholds is None: if labels is None: raise ValueError( "Cannot calculate adjust_pred_probs without labels. Either pass in labels parameter or set " "params['adjusted_pred_probs'] = False. " ) labels = labels_to_array(labels) assert_valid_inputs(X=None, y=labels, pred_probs=pred_probs, multi_label=False) confident_thresholds = get_confident_thresholds(labels, pred_probs, multi_label=False) pred_probs = _subtract_confident_thresholds( None, pred_probs, multi_label=False, confident_thresholds=confident_thresholds ) # Scores are flipped so ood scores are closer to 0. Scores reflect confidence example is in-distribution. if method == "entropy": ood_predictions_scores = 1.0 - get_normalized_entropy(pred_probs) elif method == "least_confidence": ood_predictions_scores = pred_probs.max(axis=1) elif method == "gen": if pred_probs.shape[1] < M: # pragma: no cover warnings.warn( f"GEN with the default hyperparameter settings is intended for datasets with at least {M} classes. You can adjust params['M'] according to the number of classes in your dataset.", UserWarning, ) probs = softmax(pred_probs, axis=1) probs_sorted = np.sort(probs, axis=1)[:, -M:] ood_predictions_scores = ( 1 - np.sum(probs_sorted**gamma * (1 - probs_sorted) ** (gamma), axis=1) / M ) # Use 1 + original gen score/M to make the scores lie in 0-1 else: raise ValueError( f""" {method} is not a valid OOD scoring method! Please choose a valid scoring_method: {valid_methods} """ ) return ( ood_predictions_scores, confident_thresholds, )