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

Issue:
FR: Implement `Falcun`
### Describe the workflow you want to enable

`Falcun` (Fast active learning by contrastive uncertainty) [1] is a hybrid pool-based strategy that jointly selects uncertain samples via margin sampling while considering diversity within the probability space.

[[1] Gilhuber, S., Beer, A., Ma, Y., Seidl, T. (2024). FALCUN: A Simple and Efficient Deep Active Learning Strategy. In: ECML-PKDD 2024](https://link.springer.com/chapter/10.1007/978-3-031-70352-2_25)

### Describe your proposed solution

The authors detail their algorithm in the paper [1] and provide a Pytorch implementation at [GitHub](https://github.com/sobermeier/falcun).

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

_No response_

### Additional context

_No response_


Discussion / hints:

Fix patch:
diff --git a/docs/examples/pool/_falcun.json b/docs/examples/pool/_falcun.json
new file mode 100644
index 00000000..e8bbe366
--- /dev/null
+++ b/docs/examples/pool/_falcun.json
@@ -0,0 +1,17 @@
+[
+  {
+    "class" : "Falcun",
+    "package" : "pool",
+    "method" : "Fast Active Learning by Contrastive UNcertainty (FALCUN)",
+    "category" : "Uncertainty Sampling",
+    "template" : "examples/template_pool_batch.py",
+    "tags" : ["pool",  "classification", "single-annotator"],
+    "title" : "Fast Active Learning by Contrastive UNcertainty (FALCUN)",
+    "refs" : ["gilhuber2024falcun"],
+    "sequence" : ["title", "text_0", "plot", "refs"],
+    "text_0" : "",
+    "import_misc" : "from skactiveml.pool import Falcun",
+    "init_qs" : "Falcun(random_state=42)",
+    "query_params" : "X=X, y=y, clf=clf"
+  }
+]
diff --git a/docs/examples/template_pool.py b/docs/examples/template_pool.py
index 16c8077a..75611d54 100644
--- a/docs/examples/template_pool.py
+++ b/docs/examples/template_pool.py
@@ -16,7 +16,7 @@
 "$install_dependencies|# !pip install scikit-activeml"
 
 # %%
-#.. raw:: html
+# .. raw:: html
 #
 #   <hr style="border-style: solid; border-top: 1px solid; border-right: 0; border-bottom: 0; border-left: 0;">
 #
@@ -35,9 +35,13 @@
 random_state = np.random.RandomState(0)
 
 # Build a dataset.
-X, y_true = make_blobs(n_samples="$n_samples|200", n_features=2,
-                       centers=[[0, 1], [-3, .5], [-1, -1], [2, 1], [1, -.5]],
-                       cluster_std=.7, random_state=random_state)
+X, y_true = make_blobs(
+    n_samples="$n_samples|200",
+    n_features=2,
+    centers=[[0, 1], [-3, 0.5], [-1, -1], [2, 1], [1, -0.5]],
+    cluster_std=0.7,
+    random_state=random_state,
+)
 y_true = y_true % 2
 y = np.full(shape=y_true.shape, fill_value=MISSING_LABEL)
 
@@ -67,17 +71,32 @@
     # Plot the labeled data.
     coll_old = list(ax.collections)
     title = ax.text(
-        0.5, 1.05, f"Decision boundary after acquring {c} labels",
-        size=plt.rcParams["axes.titlesize"], ha="center",
-        transform=ax.transAxes
+        0.5,
+        1.05,
+        f"Decision boundary after acquring {c} labels",
+        size=plt.rcParams["axes.titlesize"],
+        ha="center",
+        transform=ax.transAxes,
+    )
+    ax = plot_utilities(
+        qs,
+        "$query_params",
+        "$plot_utility_params|candidates=None",
+        res="$res|25",
+        feature_bound=feature_bound,
+        ax=ax,
+    )
+    ax.scatter(
+        X[:, 0], X[:, 1], c=y_true, cmap="coolwarm", marker=".", zorder=2
+    )
+    ax.scatter(
+        X_labeled[:, 0],
+        X_labeled[:, 1],
+        c="grey",
+        alpha=0.8,
+        marker=".",
+        s=300,
     )
-    ax = plot_utilities(qs, "$query_params",
-                        "$plot_utility_params|candidates=None", res="$res|25",
-                        feature_bound=feature_bound, ax=ax)
-    ax.scatter(X[:, 0], X[:, 1], c=y_true, cmap="coolwarm", marker=".",
-               zorder=2)
-    ax.scatter(X_labeled[:, 0], X_labeled[:, 1], c="grey", alpha=.8,
-               marker=".", s=300)
     ax = plot_decision_boundary(clf, feature_bound, ax=ax)
 
     coll_new = list(ax.collections)
diff --git a/docs/examples/template_pool_batch.py b/docs/examples/template_pool_batch.py
index 026afa49..b1740578 100644
--- a/docs/examples/template_pool_batch.py
+++ b/docs/examples/template_pool_batch.py
@@ -16,7 +16,7 @@
 "$install_dependencies|# !pip install scikit-activeml"
 
 # %%
-#.. raw:: html
+# .. raw:: html
 #
 #   <hr style="border-style: solid; border-top: 1px solid; border-right: 0; border-bottom: 0; border-left: 0;">
 #
@@ -27,8 +27,11 @@
 from sklearn.datasets import make_blobs
 
 from skactiveml.utils import MISSING_LABEL, labeled_indices, unlabeled_indices
-from skactiveml.visualization import plot_utilities, plot_decision_boundary, \
-    plot_contour_for_samples
+from skactiveml.visualization import (
+    plot_utilities,
+    plot_decision_boundary,
+    plot_contour_for_samples,
+)
 
 "$import_clf|from skactiveml.classifier import ParzenWindowClassifier"
 "$import_misc"
@@ -36,9 +39,13 @@
 random_state = np.random.RandomState(0)
 
 # Build a dataset.
-X, y_true = make_blobs(n_samples="$n_samples|200", n_features=2,
-                       centers=[[0, 1], [-3, .5], [-1, -1], [2, 1], [1, -.5]],
-                       cluster_std=.7, random_state=random_state)
+X, y_true = make_blobs(
+    n_samples="$n_samples|200",
+    n_features=2,
+    centers=[[0, 1], [-3, 0.5], [-1, -1], [2, 1], [1, -0.5]],
+    cluster_std=0.7,
+    random_state=random_state,
+)
 y_true = y_true % 2
 y = np.full(shape=y_true.shape, fill_value=MISSING_LABEL)
 
@@ -63,17 +70,32 @@
     X_labeled = X[labeled_indices(y)]
 
     # Query the next instance/s.
-    query_idx, utilities = qs.query("$query_params", batch_size=4, return_utilities=True)
+    query_idx, utilities = qs.query(
+        "$query_params", batch_size=4, return_utilities=True
+    )
 
     # Plot the labeled data.
     for i, ax in enumerate(axs.flatten()):
         coll_old = list(ax.collections)
-        plot_contour_for_samples(X, utilities[i], res="$res|25",
-                                 feature_bound=feature_bound, replace_nan=None, ax=ax)
-        ax.scatter(X[:, 0], X[:, 1], c=y_true, cmap="coolwarm", marker=".",
-                   zorder=2)
-        ax.scatter(X_labeled[:, 0], X_labeled[:, 1], c="grey", alpha=.8,
-                   marker=".", s=300)
+        plot_contour_for_samples(
+            X,
+            utilities[i],
+            res="$res|25",
+            feature_bound=feature_bound,
+            replace_nan=None,
+            ax=ax,
+        )
+        ax.scatter(
+            X[:, 0], X[:, 1], c=y_true, cmap="coolwarm", marker=".", zorder=2
+        )
+        ax.scatter(
+            X_labeled[:, 0],
+            X_labeled[:, 1],
+            c="grey",
+            alpha=0.8,
+            marker=".",
+            s=300,
+        )
         ax = plot_decision_boundary(clf, feature_bound, ax=ax)
         ax.set_title(f"Batch {c+1}, Utilities[{i}]")
 
diff --git a/docs/examples/template_pool_regression.py b/docs/examples/template_pool_regression.py
index 7448677f..f6ca1bf7 100644
--- a/docs/examples/template_pool_regression.py
+++ b/docs/examples/template_pool_regression.py
@@ -16,7 +16,7 @@
 "$install_dependencies|# !pip install scikit-activeml"
 
 # %%
-#.. raw:: html
+# .. raw:: html
 #
 #   <hr style="border-style: solid; border-top: 1px solid; border-right: 0; border-bottom: 0; border-left: 0;">
 #
@@ -37,14 +37,18 @@
 def true_function(X_):
     return (X_**3 + 2 * X_**2 + X_ - 1).flatten()
 
+
 n_samples = "$n_samples|100"
 X = np.concatenate(
-        [uniform.rvs(0, 1.5, 9 * n_samples // 10, random_state=random_state),
-         uniform.rvs(1.5, 0.5, n_samples // 10, random_state=random_state)]
-    ).reshape(-1, 1)
-
-noise = np.vectorize(lambda x : random_state.rand() * 1.5 if x < 1
-                                else random_state.rand() * 0.5)
+    [
+        uniform.rvs(0, 1.5, 9 * n_samples // 10, random_state=random_state),
+        uniform.rvs(1.5, 0.5, n_samples // 10, random_state=random_state),
+    ]
+).reshape(-1, 1)
+
+noise = np.vectorize(
+    lambda x: random_state.rand() * 1.5 if x < 1 else random_state.rand() * 0.5
+)
 
 # Build a dataset.
 y_true = true_function(X) + noise(X).flatten()
diff --git a/docs/examples/template_pool_regression_batch.py b/docs/examples/template_pool_regression_batch.py
index 7b7aa80d..b771647d 100644
--- a/docs/examples/template_pool_regression_batch.py
+++ b/docs/examples/template_pool_regression_batch.py
@@ -16,7 +16,7 @@
 "$install_dependencies|# !pip install scikit-activeml"
 
 # %%
-#.. raw:: html
+# .. raw:: html
 #
 #   <hr style="border-style: solid; border-top: 1px solid; border-right: 0; border-bottom: 0; border-left: 0;">
 #
@@ -37,14 +37,18 @@
 def true_function(X_):
     return (X_**3 + 2 * X_**2 + X_ - 1).flatten()
 
+
 n_samples = "$n_samples|100"
 X = np.concatenate(
-        [uniform.rvs(0, 1.5, 9 * n_samples // 10, random_state=random_state),
-         uniform.rvs(1.5, 0.5, n_samples // 10, random_state=random_state)]
-    ).reshape(-1, 1)
+    [
+        uniform.rvs(0, 1.5, 9 * n_samples // 10, random_state=random_state),
+        uniform.rvs(1.5, 0.5, n_samples // 10, random_state=random_state),
+    ]
+).reshape(-1, 1)
 
-noise = np.vectorize(lambda x : random_state.rand() * 1.5 if x < 1
-                                else random_state.rand() * 0.5)
+noise = np.vectorize(
+    lambda x: random_state.rand() * 1.5 if x < 1 else random_state.rand() * 0.5
+)
 
 # Build a dataset.
 y_true = true_function(X) + noise(X).flatten()
@@ -87,7 +91,7 @@ def true_function(X_):
 
     sort_mask = np.argsort(X.flatten())
     X_plot = X.flatten()[sort_mask]
-    utilities_plot = utilities[0][sort_mask]/batch_size
+    utilities_plot = utilities[0][sort_mask] / batch_size
 
     is_lbld = is_labeled(y)
 
diff --git a/docs/examples/template_stream.py b/docs/examples/template_stream.py
index 89c0eeac..14b88c71 100644
--- a/docs/examples/template_stream.py
+++ b/docs/examples/template_stream.py
@@ -16,7 +16,7 @@
 "$install_dependencies|# !pip install scikit-activeml"
 
 # %%
-#.. raw:: html
+# .. raw:: html
 #
 #   <hr style="border-style: solid; border-top: 1px solid; border-right: 0; border-bottom: 0; border-left: 0;">
 #
diff --git a/docs/refs.bib b/docs/refs.bib
index 62f036ab..2fc43c18 100644
--- a/docs/refs.bib
+++ b/docs/refs.bib
@@ -331,4 +331,11 @@ @inproceedings{prabhu2021active
   booktitle={ICCV},
   pages={8505--8514},
   year={2021}
+}
+@inproceedings{gilhuber2024falcun,
+  title={{FALCUN: A Simple and Efficient Deep Active Learning Strategy}},
+  author={Gilhuber, Sandra and Beer, Anna and Ma, Yunpu and Seidl, Thomas},
+  booktitle={Joint European Conference on Machine Learning and Knowledge Discovery in Databases},
+  pages={421--439},
+  year={2024},
 }
\ No newline at end of file
diff --git a/skactiveml/pool/__init__.py b/skactiveml/pool/__init__.py
index d745ab03..893a35c7 100644
--- a/skactiveml/pool/__init__.py
+++ b/skactiveml/pool/__init__.py
@@ -40,6 +40,7 @@
 from ._contrastive_al import ContrastiveAL
 from ._clue import Clue
 from ._wrapper import SubSamplingWrapper, ParallelUtilityEstimationWrapper
+from ._falcun import Falcun
 
 __all__ = [
     "multiannotator",
@@ -80,4 +81,5 @@
     "RegressionTreeBasedAL",
     "SubSamplingWrapper",
     "ParallelUtilityEstimationWrapper",
+    "Falcun",
 ]
diff --git a/skactiveml/pool/_falcun.py b/skactiveml/pool/_falcun.py
new file mode 100644
index 00000000..ba09f601
--- /dev/null
+++ b/skactiveml/pool/_falcun.py
@@ -0,0 +1,188 @@
+"""
+Module implementing `Falcun`, which is a deep active learning strategy jointly
+selecting uncertain and diverse samples.
+"""
+
+import numpy as np
+
+from sklearn.base import clone
+
+from ..base import SingleAnnotatorPoolQueryStrategy, SkactivemlClassifier
+from ..utils import (
+    MISSING_LABEL,
+    check_scalar,
+    check_type,
+    check_equal_missing_label,
+)
+from ._uncertainty_sampling import uncertainty_scores
+
+
+class Falcun(SingleAnnotatorPoolQueryStrategy):
+    """Fast Active Learning by Contrastive UNcertainty (FALCUN)
+
+    This class implements the "Fast Active Learning by Contrastive UNcertainty"
+    (FALCUN) query strategy [1]_, which is a hybrid pool-based strategy that
+    jointly selects uncertain samples via margin sampling while considering
+    batch diversity within the class probability space.
+
+    Parameters
+    ----------
+    gamma : float > 0, default=1
+        Controls the randomness in the selection. A value of 0 corresponds to
+        random sampling, while a value going to infinity corresponds to
+        selecting the sample with the highest utility (relevance).
+    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] Gilhuber, S., Beer, A., Ma, Y., Seidl, T. (2024). FALCUN: A Simple
+       and Efficient Deep Active Learning Strategy. In: ECML-PKDD 2024.
+    """
+
+    def __init__(
+        self,
+        gamma=1,
+        missing_label=MISSING_LABEL,
+        random_state=None,
+    ):
+        super().__init__(
+            missing_label=missing_label, random_state=random_state
+        )
+        self.gamma = gamma
+
+    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
+
+        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
+            Classifier implementing the methods `fit` and `predict_proba`.
+        fit_clf : bool, default=True
+            Defines whether the classifier `clf` 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, ) of type \
+                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 the indices of the
+              samples in `(X,y)`.
+            - If `candidates` is of shape `(n_candidates, *)`, `candidates` is
+              considered as the candidate 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.
+
+        Returns
+        -------
+        query_indices : numpy.ndarray of shape (batch_size)
+            The query_indices indicate for which candidate sample a label is
+            to queried, e.g., `query_indices[0]` indicates the first selected
+            sample. The indexing refers to the samples in `X`.
+        utilities : numpy.ndarray of shape (batch_size, n_samples)
+            The utilities of samples after each selected sample of the batch,
+            e.g., `utilities[0]` indicates the utilities used for selecting
+            the first sample (with index `query_indices[0]`) of the batch.
+            Utilities for labeled samples will be set to np.nan.
+
+            - If `candidates` is `None`, the indexing refers to the samples
+              in `X`.
+            - If `candidates` is of shape `(n_candidates,)` and of type
+              `int`, `utilities` refers to the samples in `X`.
+            - If `candidates` is of shape `(n_candidates, *)`, `utilities`
+              refers to the indexing in `candidates`.
+        """
+        # 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)
+        check_scalar(
+            self.gamma,
+            "gamma",
+            min_val=0,
+            target_type=(float, int),
+            min_inclusive=True,
+        )
+        check_type(clf, "clf", SkactivemlClassifier)
+        check_equal_missing_label(clf.missing_label, self.missing_label_)
+        check_scalar(fit_clf, "fit_clf", bool)
+
+        # Fit classifier, if requested.
+        if fit_clf:
+            if sample_weight is None:
+                clf = clone(clf).fit(X, y)
+            else:
+                clf = clone(clf).fit(X, y, sample_weight)
+
+        # Compute uncertainties via margin sampling (cf. Eq. (1) in [1]).
+        probas_cand = clf.predict_proba(X_cand)
+        unc_cand = uncertainty_scores(probas_cand, method="margin_sampling")
+
+        # Initialize distances in probability space (cf. Eq. (3) in [1]).
+        dist_cand = unc_cand.copy()
+
+        query_indices = []
+        utilities_cand = np.full((batch_size, len(X_cand)), np.nan)
+        cand_indices = np.arange(len(X_cand))
+        for b in range(batch_size):
+            if b > 0:
+                # Update distances (diversity) values in the class probability
+                # space (cf. Eqs. (2) and (4) in [1]).
+                probas_q = probas_cand[[query_indices[int(b - 1)]]]
+                dist_new = np.abs(probas_cand - probas_q).sum(axis=1)
+                dist_cand = np.minimum(dist_new, dist_cand)
+                dist_min = dist_cand.min()
+                dist_range = dist_cand.max() - dist_min
+                dist_cand -= dist_min
+                if dist_range > 0:
+                    dist_cand /= dist_range
+
+            # Compute relevance scores for candidates (cf. Eq. (5) and (6) in [1]).
+            rel_cand = (unc_cand + dist_cand) ** self.gamma
+            rel_cand[query_indices] = 0
+            rel_cand_sum = np.sum(rel_cand)
+            if rel_cand_sum == 0:
+                rel_cand = np.ones_like(rel_cand)
+                rel_cand[query_indices] = 0
+            rel_cand = rel_cand / np.sum(rel_cand)
+
+            # Sample instance to be labeled (cf. Eq. (6) in [1]).
+            query_idx = self.random_state_.choice(
+                cand_indices, p=rel_cand, size=1
+            )
+            rel_cand[query_indices] = np.nan
+            utilities_cand[b] = rel_cand
+            query_indices.append(query_idx[0])
+
+        if mapping is not None:
+            query_indices = mapping[query_indices]
+            utilities = np.full((batch_size, len(X)), np.nan)
+            utilities[:, mapping] = utilities_cand
+        else:
+            utilities = utilities_cand
+
+        if return_utilities:
+            return query_indices, utilities
+        else:
+            return query_indices


Test patch:
diff --git a/skactiveml/pool/tests/test_falcun.py b/skactiveml/pool/tests/test_falcun.py
new file mode 100644
index 00000000..3f221f2a
--- /dev/null
+++ b/skactiveml/pool/tests/test_falcun.py
@@ -0,0 +1,129 @@
+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 Falcun
+from skactiveml.classifier import ParzenWindowClassifier, SklearnClassifier
+from skactiveml.utils import MISSING_LABEL
+from skactiveml.tests.template_query_strategy import (
+    TemplateSingleAnnotatorPoolQueryStrategy,
+)
+
+
+class TestFalcun(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": ParzenWindowClassifier(
+                classes=self.classes,
+            ),
+        }
+        super().setUp(
+            qs_class=Falcun,
+            init_default_params={"gamma": 1},
+            query_default_params_clf=self.query_default_params_clf,
+        )
+
+    def test_init_param_gamma(self):
+        test_cases = [
+            (0, None),
+            (1e-3, None),
+            (0.1, None),
+            ("1", TypeError),
+            (-1, ValueError),
+            (-0.5, ValueError),
+        ]
+        self._test_param("init", "gamma", 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 = ParzenWindowClassifier(classes=np.unique(y_true))
+        cand_iter = zip([None, np.arange(10, 30), X[10:30]], [len(X), 20, 20])
+        for candidates, n_candidates in cand_iter:
+            qs_1 = Falcun(random_state=42)
+            qs_5 = Falcun(random_state=42, gamma=5)
+
+            # Without labeled samples, the initial selection is the same,
+            # even for different `gamma` values.
+            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.ones_like(utilities_1)
+            expected_utilities /= n_candidates
+            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())
+                np.testing.assert_allclose(
+                    np.nansum(utilities, axis=1), [1, 1]
+                )
+                if prev_utilities is not None:
+                    self.assertTrue((utilities_copy != prev_utilities).sum())
+                    # Check that different `gamma` values lead to the same
+                    # selection regarding the batch's first sample.
+                    max_idx = utilities_copy[0].argmax()
+                    prev_max_idx = prev_utilities[0].argmax()
+                    self.assertTrue(max_idx, prev_max_idx)
+                    # Check that different `gamma` values lead to different
+                    # utilities.
+                    self.assertGreater(
+                        np.abs(utilities_copy[0] - prev_utilities[0]).sum(),
+                        0.1,
+                    )
+                else:
+                    prev_utilities = utilities_copy