Repository: scikit-activeml/scikit-activeml (language: python)

Issue:
FR: Implement the pool-based query strategy `Cal`
### Describe the workflow you want to enable

`Cal` (Contrastive active learning) [1] is pool-based strategy that selects samples similar in the (classifier's learned) feature space and still the classifier outputs maximally different class-membership probabilities.

[1] [Margatina, Katerina, Giorgos Vernikos, Loïc Barrault, and Nikolaos Aletras. "Active Learning by Acquiring Contrastive Examples." In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pp. 650-663. 2021.](https://aclanthology.org/2021.emnlp-main.51.pdf)

### Describe your proposed solution

The authors detail their algorithm in the paper [1] and provide a Pytorch implementation at [GitHub](https://github.com/mourga/contrastive-active-learning/tree/main).

### Describe alternatives you've considered, if relevant

_No response_

### Additional context

_No response_


Discussion / hints:

Fix patch:
diff --git a/README.rst b/README.rst
index 35432e82..e550c7f1 100644
--- a/README.rst
+++ b/README.rst
@@ -1,6 +1,6 @@
 .. intro_start
 
-|Doc| |Codecov| |PythonVersion| |PyPi| |Paper| |Black|
+|Doc| |Codecov| |PythonVersion| |PyPi| |Paper| |Black| |Downloads|
 
 .. |Doc| image:: https://img.shields.io/badge/docs-latest-green
    :target: https://scikit-activeml.github.io/scikit-activeml-docs/
@@ -20,6 +20,9 @@
 .. |Black| image:: https://img.shields.io/badge/code%20style-black-000000.svg
    :target: https://github.com/psf/black
 
+.. |Downloads| image:: https://static.pepy.tech/badge/scikit-activeml
+   :target: https://static.pepy.tech/badge/scikit-activeml/
+
 |
 
 .. image:: https://raw.githubusercontent.com/scikit-activeml/scikit-activeml/master/docs/logos/scikit-activeml-logo.png
@@ -76,6 +79,7 @@ We provide a broad overview of different use-cases in our `tutorial section <htt
 - `Pool-based Active Learning for Regression - Getting Started <https://scikit-activeml.github.io/scikit-activeml-docs/generated/tutorials/02_pool_regression_getting_started.html>`_,
 - `Pool-based Active Learning - Sample Annotating <https://scikit-activeml.github.io/scikit-activeml-docs/generated/tutorials/03_pool_oracle_annotations.html>`_,
 - `Pool-based Active Learning - Simple Evaluation Study <https://scikit-activeml.github.io/scikit-activeml-docs/generated/tutorials/04_pool_simple_evaluation_study.html>`_,
+- `Active Image Classification via Self-supervised Learning <https://scikit-activeml.github.io/scikit-activeml-docs/generated/tutorials/05_pool_al_with_self_supervised_learning.html>`_,
 - `Multi-annotator Pool-based Active Learning - Getting Started <https://scikit-activeml.github.io/scikit-activeml-docs/generated/tutorials/10_multiple_annotators_getting_started.html>`_,
 - `Stream-based Active Learning - Getting Started <https://scikit-activeml.github.io/scikit-activeml-docs/generated/tutorials/20_stream_getting_started.html>`_,
 - `Batch Stream-based Active Learning with Pool Query Strategies <https://scikit-activeml.github.io/scikit-activeml-docs/generated/tutorials/21_stream_batch_with_pool_al.html>`_,
diff --git a/docs/examples/pool/_contrastive_al.json b/docs/examples/pool/_contrastive_al.json
new file mode 100644
index 00000000..e612842b
--- /dev/null
+++ b/docs/examples/pool/_contrastive_al.json
@@ -0,0 +1,18 @@
+[
+{
+    "class" : "ContrastiveAL",
+    "package" : "pool",
+    "method" : "Contrastive Active Learning (CAL)",
+    "category" : "Uncertainty Sampling",
+    "template" : "examples/template_pool.py",
+    "tags" : ["pool", "classification", "single-annotator"],
+    "title" : "Contrastive Active Learning (CAL)",
+    "refs" : ["margatina2021active"],
+    "sequence" : ["title", "text_0", "plot", "refs"],
+    "text_0" : "",
+    "import_misc" : "from skactiveml.pool import ContrastiveAL",
+    "init_qs" : "ContrastiveAL(random_state=0)",
+    "query_params" : "X=X, y=y, clf=clf"
+}
+]
+
diff --git a/docs/examples/pool/_prob_cover.json b/docs/examples/pool/_prob_cover.json
new file mode 100644
index 00000000..1f5a8aea
--- /dev/null
+++ b/docs/examples/pool/_prob_cover.json
@@ -0,0 +1,18 @@
+[
+{
+    "class" : "ProbCover",
+    "package" : "pool",
+    "method" : "Probability Coverage (ProbCover)",
+    "category" : "Others",
+    "template" : "examples/template_pool.py",
+    "tags" : ["pool", "classification", "single-annotator"],
+    "title" : "Probability Coverage (ProbCover)",
+    "refs" : ["yehuda2022active"],
+    "sequence" : ["title", "text_0", "plot", "refs"],
+    "text_0" : "",
+    "import_misc" : "from skactiveml.pool import ProbCover",
+    "init_qs" : "ProbCover(n_classes=2, random_state=0, cluster_algo_dict={\"random_state\": 0})",
+    "query_params" : "X=X, y=y"
+}
+]
+
diff --git a/docs/refs.bib b/docs/refs.bib
index bfb58e3b..beb6cdbf 100644
--- a/docs/refs.bib
+++ b/docs/refs.bib
@@ -298,4 +298,17 @@ @inproceedings{hacohen2022active
   author={Hacohen, Guy and Dekel, Avihu and Weinshall, Daphna},
   booktitle={International Conference on Machine Learning},
   year={2022},
+}
+@inproceedings{yehuda2022active,
+  title={{Active Learning Through a Covering Lens}},
+  author={Yehuda, Ofer and Dekel, Avihu and Hacohen, Guy and Weinshall, Daphna},
+  booktitle={Advances in Neural Information Processing Systems},
+  year={2022}
+}
+@inproceedings{margatina2021active,
+  title={{Active Learning by Acquiring Contrastive Examples}},
+  author={Margatina, Katerina and Vernikos, Giorgos and Barrault, Lo{\"\i}c and Aletras, Nikolaos},
+  booktitle={Conference on Empirical Methods in Natural Language Processing},
+  pages={650--663},
+  year={2021}
 }
\ No newline at end of file
diff --git a/skactiveml/pool/__init__.py b/skactiveml/pool/__init__.py
index 173472cd..76858925 100644
--- a/skactiveml/pool/__init__.py
+++ b/skactiveml/pool/__init__.py
@@ -35,6 +35,8 @@
 from ._core_set import CoreSet, k_greedy_center
 from ._typi_clust import TypiClust
 from ._badge import Badge
+from ._prob_cover import ProbCover
+from ._contrastive_al import ContrastiveAL
 from ._wrapper import SubSamplingWrapper, ParallelUtilityEstimationWrapper
 
 __all__ = [
@@ -68,6 +70,8 @@
     "k_greedy_center",
     "TypiClust",
     "Badge",
+    "ProbCover",
+    "ContrastiveAL",
     "GreedyBALD",
     "RegressionTreeBasedAL",
     "SubSamplingWrapper",
diff --git a/skactiveml/pool/_badge.py b/skactiveml/pool/_badge.py
index dcfb402e..cb75c474 100644
--- a/skactiveml/pool/_badge.py
+++ b/skactiveml/pool/_badge.py
@@ -34,13 +34,16 @@ class Badge(SingleAnnotatorPoolQueryStrategy):
     clf_embedding_flag_name : str or None, default=None
         Name of the flag, which is passed to the `predict_proba` method for
         getting the (learned) sample representations. If
-        `clf_embedding_flag_name=None`, the input samples `X` are used.
+        `clf_embedding_flag_name=None` and `predict_proba` returns only one
+        output, the input samples `X` are used. If `predict_proba` returns
+        two outputs or `clf_embedding_name` is not `None`,
+        `(proba, embeddings)` are expected as outputs.
 
     References
     ----------
-    [1] J. Ash, Jordan T., Chicheng Zhang, Akshay Krishnamurthy,
-    John Langford, and Alekh Agarwal, "Deep Batch Active Learning by Diverse,
-    Uncertain Gradient Lower Bounds." ICLR, 2019.
+    .. [1] J. Ash, Jordan T., Chicheng Zhang, Akshay Krishnamurthy,
+       John Langford, and Alekh Agarwal, "Deep Batch Active Learning by Diverse,
+       Uncertain Gradient Lower Bounds." ICLR, 2019.
     """
 
     def __init__(
diff --git a/skactiveml/pool/_contrastive_al.py b/skactiveml/pool/_contrastive_al.py
new file mode 100644
index 00000000..ba1ad9c1
--- /dev/null
+++ b/skactiveml/pool/_contrastive_al.py
@@ -0,0 +1,216 @@
+"""
+Module implementing `ContrastiveAL`, which is a deep active learning strategy selecting
+contrastive samples.
+"""
+
+import numpy as np
+
+from sklearn.neighbors import NearestNeighbors
+from sklearn.base import clone
+
+from ..base import SingleAnnotatorPoolQueryStrategy, SkactivemlClassifier
+from ..utils import (
+    MISSING_LABEL,
+    is_labeled,
+    simple_batch,
+    check_scalar,
+    check_type,
+    check_equal_missing_label,
+)
+
+
+class ContrastiveAL(SingleAnnotatorPoolQueryStrategy):
+    """Contrastive Active Learning (ContrastiveAL)
+
+    This class implements the Contrastive Active Learning (ContrastiveAL) query strategy
+    [1], which  selects samples similar in the (classifier's learned) feature
+    space, while the classifier predicts maximally different class-membership
+    probabilities.
+
+    Parameters
+    ----------
+    nearest_neighbors_dict : dict, default=None
+        The parameters passed to the nearest neighboring algorithm
+        `sklearn.neighbors.NearestNeighbors`.
+    clf_embedding_flag_name : str or None, default=None
+        Name of the flag, which is passed to the `predict_proba` method for
+        getting the (learned) sample representations. If
+        `clf_embedding_flag_name=None` and `predict_proba` returns only one
+        output, the input samples `X` are used. If `predict_proba` returns
+        two outputs or `clf_embedding_name` is not `None`,
+        `(proba, embeddings)` are expected as outputs.
+    eps : float  > 0, default=1e-7
+        Minimum probability threshold to compute log-probabilities.
+    missing_label : scalar or string or np.nan or None, default=np.nan
+        Value to represent a missing label.
+    random_state : None or int or np.random.RandomState, default=None
+        The random state to use.
+
+    References
+    ----------
+    .. [1] Margatina, Katerina, Giorgos Vernikos, Loïc Barrault, and Nikolaos
+       Aletras. "Active Learning by Acquiring Contrastive Examples." In EMNLP,
+       pp. 650-663. 2021.
+    """
+
+    def __init__(
+        self,
+        nearest_neighbors_dict=None,
+        clf_embedding_flag_name=None,
+        eps=1e-7,
+        missing_label=MISSING_LABEL,
+        random_state=None,
+    ):
+        super().__init__(
+            missing_label=missing_label, random_state=random_state
+        )
+        self.nearest_neighbors_dict = nearest_neighbors_dict
+        self.clf_embedding_flag_name = clf_embedding_flag_name
+        self.eps = eps
+
+    def query(
+        self,
+        X,
+        y,
+        clf,
+        fit_clf=True,
+        sample_weight=None,
+        candidates=None,
+        batch_size=1,
+        return_utilities=False,
+    ):
+        """Query the next samples to be labeled.
+
+        Parameters
+        ----------
+        X : array-like of shape (n_samples, n_features)
+            Training data set, usually complete, i.e. including the labeled and
+            unlabeled samples.
+        y : array-like of shape (n_samples,)
+            Labels of the training data set (possibly including unlabeled ones
+            indicated by self.missing_label).
+        clf : skactiveml.base.SkactivemlClassifier
+            Model implementing the methods `fit` and `predict_proba`.
+        fit_clf : bool, default=True
+            Defines whether the classifier should be fitted on `X`, `y`, and
+            `sample_weight`.
+        sample_weight: array-like of shape (n_samples,), default=None
+            Weights of training samples in `X`.
+        candidates : None or array-like of shape (n_candidates) with \
+                dtype=int or array-like of shape (n_candidates, n_features), \
+                default=None
+            If `candidates` is `None`, the unlabeled samples from `(X, y)`
+            are considered as candidates.
+            If `candidates` is of shape `(n_candidates)` and of type `int`,
+            `candidates` is considered as a list of the indices of the samples
+            in `(X, y)`.
+            If `candidates` is of shape `(n_candidates, n_features)`, the
+            candidate samples are directly given in `candidates` (not
+            necessarily contained in `X`).
+        batch_size : int, default=1
+            The number of samples to be selected in one AL cycle.
+        return_utilities : bool, default=False
+            If `True`, also return the utilities based on the query strategy.
+
+        Returns
+        ----------
+        query_indices : numpy.ndarray of shape (batch_size,)
+            The `query_indices` indicate for which candidate sample a label is
+            to be queried, e.g., `query_indices[0]` indicates the first
+            selected sample.
+            If `candidates` is `None` or of shape `(n_candidates,)`, the
+            indexing refers to samples in X.
+        utilities : numpy.ndarray of shape (batch_size, n_samples)
+            The utilities of samples for selecting each sample of the batch.
+            Here, utilities refers to the Kullback-Leibler divergence between
+            the sample's own and its labeled nearest neighbors' predicted
+            class-membership probabilities. If `candidates` is `None` or of
+            shape `(n_candidates,)`, the indexing refers to the samples in `X`.
+        """
+        # Check parameters.
+        X, y, candidates, batch_size, return_utilities = self._validate_data(
+            X, y, candidates, batch_size, return_utilities, reset=True
+        )
+        X_cand, mapping = self._transform_candidates(candidates, X, y)
+        X_labeled = X[is_labeled(y, self.missing_label_)]
+        if not (
+            isinstance(self.nearest_neighbors_dict, dict)
+            or self.nearest_neighbors_dict is None
+        ):
+            raise TypeError(
+                "Pass a dictionary with corresponding parameter names and "
+                "values according to the `init` function of "
+                "`sklearn.neighbors.NearestNeighbors`."
+            )
+        nearest_neighbors_dict = (
+            {}
+            if self.nearest_neighbors_dict is None
+            else self.nearest_neighbors_dict.copy()
+        )
+        check_scalar(
+            self.eps,
+            "eps",
+            min_val=0,
+            max_val=0.1,
+            target_type=(float, int),
+            min_inclusive=False,
+        )
+        check_type(clf, "clf", SkactivemlClassifier)
+        check_equal_missing_label(clf.missing_label, self.missing_label_)
+        check_scalar(fit_clf, "fit_clf", bool)
+
+        if fit_clf:
+            if sample_weight is None:
+                clf = clone(clf).fit(X, y)
+            else:
+                clf = clone(clf).fit(X, y, sample_weight)
+
+        if len(X_labeled) > 0:
+            # Obtain classifier predictions and optionally learned feature
+            # embeddings (cf. line 3 and 4 in [1]).
+            predict_proba_kwargs = {}
+            if self.clf_embedding_flag_name is not None:
+                predict_proba_kwargs = {self.clf_embedding_flag_name: True}
+            P_labeled = clf.predict_proba(X_labeled, **predict_proba_kwargs)
+            P_cand = clf.predict_proba(X_cand, **predict_proba_kwargs)
+            if isinstance(P_labeled, tuple):
+                P_labeled, X_labeled = P_labeled
+            if isinstance(P_cand, tuple):
+                P_cand, X_cand = P_cand
+
+            # Clip probabilities to avoid zeros.
+            np.clip(P_labeled, a_min=self.eps, a_max=1, out=P_labeled)
+            P_labeled /= P_labeled.sum(axis=1, keepdims=True)
+            np.clip(P_cand, a_min=self.eps, a_max=1, out=P_cand)
+            P_cand /= P_cand.sum(axis=1, keepdims=True)
+
+            # Find nearest labeled samples of candidate samples
+            # (cf. line 2 in [1]).
+            nn = NearestNeighbors(**nearest_neighbors_dict).fit(X_labeled)
+            max_n_neighbors = min(nn.n_neighbors, len(X_labeled))
+            nn_indices = nn.kneighbors(
+                X_cand, n_neighbors=max_n_neighbors, return_distance=False
+            )
+
+            # Compute KL divergences between class-membership probabilities of
+            # candidates and their respective neighbors
+            # (cf. line 5 and 6 in [1]).
+            P_labeled = P_labeled[nn_indices]
+            utilities_cand = P_labeled * np.log(P_labeled / P_cand[:, None, :])
+            utilities_cand = utilities_cand.sum(axis=-1).mean(axis=-1)
+        else:
+            # Fallback to random sampling, if there are no labeled samples.
+            utilities_cand = np.zeros(len(X_cand))
+
+        if mapping is None:
+            utilities = utilities_cand
+        else:
+            utilities = np.full(len(X), np.nan)
+            utilities[mapping] = utilities_cand
+
+        return simple_batch(
+            utilities,
+            self.random_state_,
+            batch_size=batch_size,
+            return_utilities=return_utilities,
+        )
diff --git a/skactiveml/pool/_prob_cover.py b/skactiveml/pool/_prob_cover.py
new file mode 100644
index 00000000..bf1ee5c0
--- /dev/null
+++ b/skactiveml/pool/_prob_cover.py
@@ -0,0 +1,236 @@
+"""
+Module implementing `ProbCover`, which is a deep active learning strategy
+suited for low budgets.
+"""
+
+import numpy as np
+import warnings
+
+from sklearn.metrics import pairwise_distances
+from sklearn.cluster import KMeans
+from sklearn.utils.validation import column_or_1d
+
+from ..base import SingleAnnotatorPoolQueryStrategy
+from ..utils import (
+    MISSING_LABEL,
+    rand_argmax,
+    check_scalar,
+)
+
+
+class ProbCover(SingleAnnotatorPoolQueryStrategy):
+    """Probability Coverage
+
+    This class implements the Probability Coverage (ProbCover) query strategy
+    [1], which aims at maximizing the probability coverage in a meaningful
+    sample embedding space.
+
+    Parameters
+    ----------
+    n_classes : None or int, default=None
+        This parameter is used to determine the delta value. If
+        `n_classes=None`, the number of classes is extracted from the
+        given labels. If this extracted number of classes is below 2,
+        `n_classes=2` is used as a fallback.
+    deltas : None or array-like of shape (n_deltas,), default=None
+        List of deltas (ball radii) to be tested for finding the maximum
+        value satisfying a sample coverage >= `alpha`. If no value in
+        `deltas` satisfies this constraint, a warning is raised where
+        the minimum `delta` value is used. If `deltas=None`, the values
+        `np.arange(0.1, 2.1, 0.1)` are used.
+    alpha : float in (0, 1), alpha=0.95
+        Minimum coverage as a constraint for the `delta` selection.
+    cluster_algo : ClusterMixin.__class__, default=sklearn.cluster.KMeans
+        The cluster algorithm to be used for determining the best delta value.
+    cluster_algo_dict : dict, default=None
+        The parameters passed to the clustering algorithm `cluster_algo`,
+        excluding the parameter for the number of clusters.
+    n_cluster_param_name : string, default="n_clusters"
+        The name of the parameter for the number of clusters.
+    distance_func : callable, default=sklearn.metrics.pairwise_distances
+        Takes as input `X` to compute the distances between each pair of
+        samples. This function can also only return the precomputed distances
+        of each pair in `X` for speedup.
+    missing_label : scalar or string or np.nan or None, default=np.nan
+        Value to represent a missing label.
+    random_state : None or int or np.random.RandomState, default=None
+        The random state to use.
+
+    References
+    ----------
+    .. [1] Yehuda, Ofer, Avihu Dekel, Guy Hacohen, and Daphna Weinshall.
+       "Active Learning Through a Covering Lens." NeurIPS, 2022.
+    """
+
+    def __init__(
+        self,
+        n_classes=None,
+        deltas=None,
+        alpha=0.95,
+        cluster_algo=KMeans,
+        cluster_algo_dict=None,
+        n_cluster_param_name="n_clusters",
+        distance_func=pairwise_distances,
+        missing_label=MISSING_LABEL,
+        random_state=None,
+    ):
+        super().__init__(
+            missing_label=missing_label, random_state=random_state
+        )
+        self.deltas = deltas
+        self.alpha = alpha
+        self.n_classes = n_classes
+        self.cluster_algo = cluster_algo
+        self.cluster_algo_dict = cluster_algo_dict
+        self.n_cluster_param_name = n_cluster_param_name
+        self.distance_func = distance_func
+
+    def query(
+        self,
+        X,
+        y,
+        candidates=None,
+        batch_size=1,
+        return_utilities=False,
+        update=False,
+    ):
+        """Query the next samples to be labeled
+
+        Parameters
+        ----------
+        X : array-like of shape (n_samples, n_features)
+            Training data set, usually complete, i.e. including the labeled and
+            unlabeled samples.
+        y : array-like of shape (n_samples,)
+            Labels of the training data set (possibly including unlabeled ones
+            indicated by self.missing_label).
+        candidates : None or array-like of shape (n_candidates) with \
+                dtype=int, default=None
+            If `candidates` is None, the unlabeled samples from `(X, y)`
+            are considered as candidates.
+            If `candidates` is of shape `(n_candidates,)` and of type int,
+            `candidates` is considered as a list of the indices of the samples
+            in `(X, y)`.
+        batch_size : int, default=1
+            The number of samples to be selected in one AL cycle.
+        return_utilities : bool, default=False
+            If True, also return the utilities based on the query strategy.
+        update : bool, default=False
+            This boolean flag determines whether the computed `delta_max_`
+            and the `distances_` shall be updated in the `query`. For the first
+            call of `query`, this parameter has no impact because both
+            quantities are computed for the first time.
+
+        Returns
+        ----------
+        query_indices : numpy.ndarray of shape (batch_size,)
+            The `query_indices` indicate for which candidate sample a label is
+            to be queried, e.g., `query_indices[0]` indicates the first
+            selected sample.
+            If `candidates` in `None` or of shape `(n_candidates,)`, the
+            indexing refers to samples in `X`.
+        utilities : numpy.ndarray of shape (batch_size, n_samples)
+            The utilities of samples for selecting each sample of the batch.
+            Here, utilities mean the out-degree of the candidate samples.
+            If `candidates` is `None` or of shape `(n_candidates,)`, the
+            indexing refers to the samples in `X`.
+        """
+        # Check parameters.
+        X, y, candidates, batch_size, return_utilities = self._validate_data(
+            X, y, candidates, batch_size, return_utilities, reset=True
+        )
+        _, mapping = self._transform_candidates(
+            candidates, X, y, enforce_mapping=True
+        )
+        is_candidate = np.full(len(X), fill_value=False)
+        is_candidate[mapping] = True
+        n_classes = self.n_classes
+        if n_classes is None:
+            n_classes = max(len(np.unique(y[~is_candidate])), 2)
+        check_scalar(
+            n_classes,
+            "n_classes",
+            min_val=2,
+            min_inclusive=True,
+            target_type=int,
+        )
+        if self.deltas is None:
+            deltas = np.arange(0.2, 2.2, 0.2)
+        else:
+            deltas = column_or_1d(self.deltas, dtype=float)
+            deltas = np.sort(deltas)
+            if (deltas < 0).any():
+                raise ValueError("`deltas` must contain non-negative floats.")
+        check_scalar(
+            self.alpha,
+            "alpha",
+            min_val=0,
+            max_val=1,
+            min_inclusive=False,
+            max_inclusive=False,
+            target_type=float,
+        )
+        if not (
+            isinstance(self.cluster_algo_dict, dict)
+            or self.cluster_algo_dict is None
+        ):
+            raise TypeError(
+                "Pass a dictionary with corresponding parameter names and "
+                "values according to the `init` function of `cluster_algo`."
+            )
+        cluster_algo_dict = (
+            {}
+            if self.cluster_algo_dict is None
+            else self.cluster_algo_dict.copy()
+        )
+        check_scalar(update, name="update", target_type=bool)
+
+        if update or not hasattr(self, "delta_max_"):
+            # Compute distances between each pair of observed samples.
+            self.distances_ = self.distance_func(X)
+
+            # Compute the maximum `delta` value satisfying a purity >= `alpha`.
+            self.delta_max_ = deltas[0]
+            max_purity = -1
+            if len(deltas) > 1:
+                cluster_algo_dict[self.n_cluster_param_name] = n_classes
+                cluster_obj = self.cluster_algo(**cluster_algo_dict)
+                y_cluster = cluster_obj.fit_predict(X)
+                is_impure = y_cluster[:, None] != y_cluster
+                for delta in deltas:
+                    edges = self.distances_ <= delta
+                    purity = 1 - (edges * is_impure).any(axis=1).mean()
+                    max_purity = max(max_purity, purity)
+                    if purity < self.alpha:
+                        break
+                    self.delta_max_ = delta
+
+            # Check whether condition defined by `alpha` was satisfied.
+            if max_purity < self.alpha:
+                warnings.warn(
+                    f"The maximum purity was {max_purity} being smaller "
+                    f"than the required value `alpha={self.alpha}`. You must"
+                    f"provide smaller values in `deltas` to avoid "
+                    f"this warning."
+                )
+
+        # Compute edges of the graph with the samples as vertices.
+        edges = self.distances_ <= self.delta_max_
+
+        # Perform sample-wise selection of the batch.
+        query_indices = np.full(batch_size, fill_value=-1, dtype=int)
+        utilities = np.full((batch_size, len(X)), fill_value=np.nan)
+        for b in range(batch_size):
+            # Step (ii) in [1]: Remove incoming edges for covered samples.
+            is_covered = edges[~is_candidate].any(axis=0)
+            edges[:, is_covered] = False
+            # Step (i) in [1]: Query the sample with the highest out-degree.
+            utilities[b][is_candidate] = edges[is_candidate].sum(axis=1)
+            idx = rand_argmax(utilities[b], random_state=self.random_state_)[0]
+            is_candidate[idx] = False
+            query_indices[b] = idx
+
+        if return_utilities:
+            return query_indices, utilities
+        else:
+            return query_indices


Test patch:
diff --git a/skactiveml/pool/tests/test_badge.py b/skactiveml/pool/tests/test_badge.py
index 8fc18d9a..4562ebec 100644
--- a/skactiveml/pool/tests/test_badge.py
+++ b/skactiveml/pool/tests/test_badge.py
@@ -4,13 +4,17 @@
 from sklearn.linear_model import LogisticRegression
 from sklearn.svm import SVC
 
-from skactiveml.classifier import SklearnClassifier, ParzenWindowClassifier
+from skactiveml.classifier import SklearnClassifier
 from skactiveml.pool import Badge
 from skactiveml.utils import MISSING_LABEL
 from skactiveml.tests.template_query_strategy import (
     TemplateSingleAnnotatorPoolQueryStrategy,
 )
-from sklearn.exceptions import NotFittedError
+
+from skactiveml.tests.utils import (
+    ParzenWindowClassifierEmbedding,
+    ParzenWindowClassifierTuple,
+)
 
 
 class TestBadge(TemplateSingleAnnotatorPoolQueryStrategy, unittest.TestCase):
@@ -53,17 +57,6 @@ def test_query_param_clf(self):
         ]
         super().test_query_param_clf(test_cases=add_test_cases)
 
-    def test_query_param_fit_clf(self, test_cases=None):
-        test_cases = [] if test_cases is None else test_cases
-        test_cases += [
-            (1, TypeError),
-            ("string", TypeError),
-            (None, TypeError),
-            (False, NotFittedError),
-            (True, None),
-        ]
-        self._test_param("query", "fit_clf", test_cases=test_cases)
-
     def test_init_param_clf_embedding_flag_name(self, test_cases=None):
         test_cases = [] if test_cases is None else test_cases
         test_cases += [
@@ -178,17 +171,3 @@ def test_query(self):
             badge_1.query(X_1, y_1, clf_8),
             badge_1.query(X_1, y_1, clf_8),
         )
-
-
-class ParzenWindowClassifierEmbedding(ParzenWindowClassifier):
-    def predict_proba(self, X, return_embeddings=False):
-        probas = super().predict_proba(X)
-        if not return_embeddings:
-            return probas
-        return probas, X
-
-
-class ParzenWindowClassifierTuple(ParzenWindowClassifier):
-    def predict_proba(self, X, return_embeddings=False):
-        probas = super().predict_proba(X)
-        return (probas, X)
diff --git a/skactiveml/pool/tests/test_contrastive_al.py b/skactiveml/pool/tests/test_contrastive_al.py
new file mode 100644
index 00000000..a4a33d72
--- /dev/null
+++ b/skactiveml/pool/tests/test_contrastive_al.py
@@ -0,0 +1,168 @@
+import unittest
+
+import numpy as np
+from sklearn.linear_model import LogisticRegression
+from sklearn.svm import SVC
+from sklearn.datasets import make_blobs
+from skactiveml.pool import ContrastiveAL
+from skactiveml.classifier import ParzenWindowClassifier, SklearnClassifier
+from skactiveml.utils import MISSING_LABEL
+from skactiveml.tests.template_query_strategy import (
+    TemplateSingleAnnotatorPoolQueryStrategy,
+)
+from skactiveml.tests.utils import (
+    ParzenWindowClassifierEmbedding,
+    ParzenWindowClassifierTuple,
+)
+
+
+class TestContrastiveAL(
+    TemplateSingleAnnotatorPoolQueryStrategy, unittest.TestCase
+):
+    def setUp(self):
+        X = np.linspace(0, 1, 20).reshape(10, 2)
+        y = np.hstack([[0, 1], np.full(8, MISSING_LABEL)])
+        self.classes = [0, 1]
+        self.query_default_params_clf = {
+            "X": X,
+            "y": y,
+            "clf": ParzenWindowClassifier(
+                classes=self.classes, random_state=42
+            ),
+        }
+        self.query_default_params_clf_embedding = {
+            "X": X,
+            "y": y,
+            "clf": ParzenWindowClassifierEmbedding(
+                classes=self.classes,
+            ),
+        }
+        super().setUp(
+            qs_class=ContrastiveAL,
+            init_default_params={"nearest_neighbors_dict": {"n_neighbors": 2}},
+            query_default_params_clf=self.query_default_params_clf,
+        )
+
+    def test_init_param_nearest_neighbors_dict(self, test_cases=None):
+        test_cases = [] if test_cases is None else test_cases
+        test_cases += [
+            (1, TypeError),
+            ("string", TypeError),
+            (None, None),
+            ({}, None),
+            ({"n_neighbors": 2}, None),
+        ]
+        self._test_param("init", "nearest_neighbors_dict", test_cases)
+
+    def test_init_param_eps(self):
+        test_cases = [
+            (0, ValueError),
+            (1e-3, None),
+            (0.1, None),
+            ("1", TypeError),
+            (1, ValueError),
+        ]
+        self._test_param("init", "eps", test_cases)
+
+    def test_init_param_clf_embedding_flag_name(self, test_cases=None):
+        test_cases = [] if test_cases is None else test_cases
+        test_cases += [
+            (1, TypeError),
+            (None, None),
+            (False, TypeError),
+            (True, TypeError),
+            ("return_embeddings", None),
+        ]
+        self._test_param(
+            "init",
+            "clf_embedding_flag_name",
+            replace_query_params=self.query_default_params_clf_embedding,
+            test_cases=test_cases,
+        )
+
+    def test_query_param_clf(self, test_cases=None):
+        test_cases = [] if test_cases is None else test_cases
+        test_cases += [
+            (SVC(), TypeError),
+            (SklearnClassifier(SVC()), AttributeError),
+            (SklearnClassifier(SVC(probability=True)), None),
+            (
+                SklearnClassifier(LogisticRegression(), classes=self.classes),
+                None,
+            ),
+        ]
+        super().test_query_param_clf(test_cases=test_cases)
+
+    def test_query(self):
+        X, y_true = make_blobs(n_samples=100, centers=4, random_state=0)
+        y_true = y_true.astype(float)
+        clf_orig = ParzenWindowClassifier(classes=np.unique(y_true))
+        clf_emb = ParzenWindowClassifierEmbedding(classes=np.unique(y_true))
+        clf_tuple = ParzenWindowClassifierTuple(classes=np.unique(y_true))
+        for candidates in [None, np.arange(10, 30), X[10:30]]:
+            prev_clf_utilities = None
+            for clf in [clf_orig, clf_emb, clf_tuple]:
+                qs_1 = ContrastiveAL(
+                    nearest_neighbors_dict={"n_neighbors": 1},
+                    random_state=42,
+                )
+                qs_5 = ContrastiveAL(
+                    nearest_neighbors_dict={"n_neighbors": 5},
+                    random_state=42,
+                )
+
+                # Without labeled samples, the initial selection is the same,
+                # even for different nearest neighbor numbers.
+                y = np.full(len(y_true), MISSING_LABEL)
+                query_indices_1, utilities_1 = qs_1.query(
+                    X, y, clf=clf, candidates=candidates, return_utilities=True
+                )
+                query_indices_5, utilities_5 = qs_5.query(
+                    X, y, clf=clf, candidates=candidates, return_utilities=True
+                )
+                np.testing.assert_array_equal(query_indices_1, query_indices_5)
+                np.testing.assert_array_equal(utilities_1, utilities_5)
+                expected_utilities = np.zeros_like(utilities_1)
+                if candidates is not None and candidates.ndim == 1:
+                    expected_utilities[:, :10] = np.nan
+                    expected_utilities[:, 30:] = np.nan
+                np.testing.assert_array_equal(utilities_1, expected_utilities)
+
+                # All utilities are non-negative values or np.nan.
+                is_unlabeled = np.random.RandomState(0).choice(
+                    [False, True], size=(len(X),), replace=True
+                )
+                y = y_true.copy()
+                y[is_unlabeled] = np.nan
+                prev_utilities = None
+                for qs in [qs_1, qs_5]:
+                    query_indices, utilities = qs.query(
+                        X,
+                        y,
+                        clf=clf,
+                        candidates=candidates,
+                        batch_size=2,
+                        return_utilities=True,
+                    )
+                    utilities_copy = utilities.copy()
+                    is_nan = np.isnan(utilities)
+                    utilities_copy[is_nan] = 0.0
+                    is_non_negative = utilities_copy >= 0
+                    self.assertTrue(is_non_negative.all())
+                    if prev_utilities is not None:
+                        # Check that different numbers of nearest neighbors
+                        # lead to different utilities.
+                        self.assertTrue(
+                            np.nansum(utilities) != np.nansum(prev_utilities)
+                        )
+                    else:
+                        # Check that the utilties are consistent across
+                        # classifiers using different syntax to return
+                        # embeddings.
+                        if prev_clf_utilities is not None:
+                            np.testing.assert_array_equal(
+                                prev_clf_utilities, utilities
+                            )
+                        prev_clf_utilities = utilities
+
+                    prev_utilities = utilities
diff --git a/skactiveml/pool/tests/test_prob_cover.py b/skactiveml/pool/tests/test_prob_cover.py
new file mode 100644
index 00000000..5372e125
--- /dev/null
+++ b/skactiveml/pool/tests/test_prob_cover.py
@@ -0,0 +1,207 @@
+import unittest
+
+import numpy as np
+from sklearn.cluster import KMeans, SpectralClustering
+from sklearn.datasets import make_blobs
+from sklearn.metrics import pairwise_distances, euclidean_distances
+from skactiveml.pool import ProbCover
+from skactiveml.exceptions import MappingError
+from skactiveml.utils import MISSING_LABEL
+from skactiveml.tests.template_query_strategy import (
+    TemplateSingleAnnotatorPoolQueryStrategy,
+)
+
+
+class TestProbCover(
+    TemplateSingleAnnotatorPoolQueryStrategy, unittest.TestCase
+):
+    def setUp(self):
+        query_default_params_clf = {
+            "X": np.linspace(0, 1, 20).reshape(10, 2),
+            "y": np.hstack([[0, 1], np.full(8, MISSING_LABEL)]),
+        }
+        cluster_dict = {"random_state": 0, "n_init": 1}
+        super().setUp(
+            qs_class=ProbCover,
+            init_default_params={"cluster_algo_dict": cluster_dict},
+            query_default_params_clf=query_default_params_clf,
+        )
+
+    def test_init_param_n_classes(self, test_cases=None):
+        test_cases = [] if test_cases is None else test_cases
+        test_cases += [
+            (None, None),
+            (2, None),
+            (10, None),
+            ("string", TypeError),
+            (1.5, TypeError),
+            (0, ValueError),
+            (1, ValueError),
+        ]
+        self._test_param("init", "n_classes", test_cases)
+
+    def test_init_param_deltas(self, test_cases=None):
+        test_cases = [] if test_cases is None else test_cases
+        test_cases += [
+            ([0.5], None),
+            ([0.0, 1.0, 2.0], None),
+            ([500], None),
+            (np.array([0.0, 1.0, 2.0]), None),
+            ([-1], ValueError),
+            (0.5, ValueError),
+            (-1, ValueError),
+            ("string", ValueError),
+        ]
+        self._test_param("init", "deltas", test_cases)
+
+    def test_init_param_alpha(self, test_cases=None):
+        test_cases = [] if test_cases is None else test_cases
+        test_cases += [
+            (0.5, None),
+            (0.01, None),
+            (0.99, None),
+            (1.0, ValueError),
+            (0.0, ValueError),
+            ("string", TypeError),
+        ]
+        self._test_param("init", "alpha", test_cases)
+
+    def test_init_param_cluster_algo(self, test_cases=None):
+        test_cases = [] if test_cases is None else test_cases
+        test_cases += [
+            (1, TypeError),
+            ("string", TypeError),
+            (None, TypeError),
+            (ProbCover, TypeError),
+            (SpectralClustering, None),
+            (KMeans, None),
+        ]
+        self._test_param(
+            "init",
+            "cluster_algo",
+            test_cases,
+            replace_init_params={"random_state": 0},
+        )
+
+    def test_init_param_cluster_algo_dict(self, test_cases=None):
+        test_cases = [] if test_cases is None else test_cases
+        test_cases += [
+            (1, TypeError),
+            ("string", TypeError),
+            (None, None),
+            ({}, None),
+            ({"n_init": "auto", "random_state": 0}, None),
+        ]
+        self._test_param("init", "cluster_algo_dict", test_cases)
+
+    def test_init_param_n_cluster_param_name(self, test_cases=None):
+        test_cases = [] if test_cases is None else test_cases
+        test_cases += [
+            (1, TypeError),
+            ("string", TypeError),
+            (None, TypeError),
+            ("n_clusters", None),
+        ]
+        self._test_param("init", "n_cluster_param_name", test_cases)
+
+    def test_init_param_distance_func(self, test_cases=None):
+        test_cases = [] if test_cases is None else test_cases
+        test_cases += [
+            (pairwise_distances, None),
+            (euclidean_distances, None),
+            (1, TypeError),
+            ("string", TypeError),
+        ]
+        self._test_param("init", "distance_func", test_cases)
+
+    def test_query_param_update(self, test_cases=None):
+        test_cases = [] if test_cases is None else test_cases
+        test_cases += [
+            (False, None),
+            (True, None),
+            (1, TypeError),
+            ("string", TypeError),
+        ]
+        self._test_param("query", "update", test_cases)
+
+    def test_query(self):
+        X, y_true = make_blobs(n_samples=50, centers=4, random_state=0)
+        y_true = y_true.astype(float)
+        D = pairwise_distances(X)
+
+        def distance_func(X):
+            return D
+
+        for candidates in [None, np.arange(10, 30)]:
+            qs = ProbCover(
+                deltas=np.linspace(0.5, 2, 100),
+                cluster_algo_dict={"random_state": 0},
+                random_state=42,
+            )
+            qs_metric = ProbCover(
+                deltas=np.linspace(0.5, 2, 100),
+                cluster_algo_dict={"random_state": 0},
+                distance_func=distance_func,
+                random_state=42,
+            )
+            qs_cluster = ProbCover(
+                deltas=np.linspace(0.5, 2, 100),
+                random_state=42,
+                cluster_algo_dict={
+                    "init": "random",
+                    "max_iter": 1,
+                    "random_state": 0,
+                },
+            )
+
+            # With the same random state the initial selection is the same.
+            y = np.full(50, MISSING_LABEL)
+            self.assertEqual(
+                qs.query(X, y, candidates=candidates),
+                qs.query(X, y, candidates=candidates),
+            )
+
+            # Check non-negativity of `delta_max_`.
+            self.assertGreaterEqual(qs.delta_max_, 0.0)
+
+            # All utilities are non-negative integers or np.nan.
+            is_unlabeled = np.random.RandomState(0).choice(
+                [False, True], size=(len(X),), replace=True
+            )
+            y = y_true.copy()
+            y[is_unlabeled] = np.nan
+            query_indices, utilities = qs.query(
+                X,
+                y,
+                update=True,
+                candidates=candidates,
+                batch_size=2,
+                return_utilities=True,
+            )
+            utilities_copy = utilities.copy()
+            is_nan = np.isnan(utilities)
+            utilities_copy[is_nan] = 0.0
+            is_integer = np.mod(utilities_copy, 1) == 0
+            is_non_negative = utilities_copy >= 0
+            self.assertTrue(np.logical_and(is_integer, is_non_negative).all())
+
+            # Check functionality of `pairwise_distances_dict`.
+            query_indices_metric, utilities_metric = qs_metric.query(
+                X,
+                y,
+                batch_size=2,
+                candidates=candidates,
+                return_utilities=True,
+            )
+            np.testing.assert_array_equal(query_indices_metric, query_indices)
+            np.testing.assert_array_equal(utilities_metric, utilities)
+
+            # Check consistence of `delta_max_`.
+            self.assertEqual(qs.delta_max_, qs_metric.delta_max_)
+
+            # Check functionality of `cluster_algo_dict`.
+            _, _ = qs_cluster.query(X, y, candidates=candidates, batch_size=2)
+            self.assertTrue(qs_cluster.delta_max_ != qs.delta_max_)
+
+        # Check whether error is raised for `candidates` being not in `X`.
+        self.assertRaises(MappingError, qs.query, X, y, candidates=X)
diff --git a/skactiveml/tests/utils.py b/skactiveml/tests/utils.py
index 0a69c6e5..88ae322a 100644
--- a/skactiveml/tests/utils.py
+++ b/skactiveml/tests/utils.py
@@ -1,5 +1,7 @@
 import inspect
 
+from ..classifier import ParzenWindowClassifier
+
 
 def check_positional_args(func, func_name, param_dict, kwargs_name=None):
     func_params = inspect.signature(func).parameters
@@ -56,3 +58,17 @@ def check_test_param_test_availability(
                 hasattr(class_, f"test_{func_name}"),
                 msg=f"'test_{func_name}' missing in {class_.__class__}",
             )
+
+
+class ParzenWindowClassifierEmbedding(ParzenWindowClassifier):
+    def predict_proba(self, X, return_embeddings=False):
+        probas = super().predict_proba(X)
+        if not return_embeddings:
+            return probas
+        return probas, X
+
+
+class ParzenWindowClassifierTuple(ParzenWindowClassifier):
+    def predict_proba(self, X, return_embeddings=False):
+        probas = super().predict_proba(X)
+        return probas, X