import numpy as np
from scipy.special import factorial
from sklearn.utils.validation import check_array
from ..base import SkactivemlClassifier
from ..base import SingleAnnotatorPoolQueryStrategy
from ..classifier import ParzenWindowClassifier
from ..utils import (
MISSING_LABEL,
check_scalar,
simple_batch,
)
from ._target import _fit_and_resolve_estimator_target_spec
[docs]
class ProbabilisticAL(SingleAnnotatorPoolQueryStrategy):
"""Multi-class Probabilistic Active Learning (McPAL)
This class implements the query strategy Multi-class Probabilistic Active
Learning (McPAL) [1]_, which scores each unlabeled sample by the
density-weighted expected gain in a target performance metric
(e.g., accuracy), integrating a sample's impact, its class posterior,
and the posterior's reliability via a closed-form expectation over all
possible labelings. This yields a non-myopic selector for
multi-class problems. Its effectiveness hinges on calibrated posteriors and
sensible density estimates.
Parameters
----------
prior : float, default=1.0
Prior probabilities for the Dirichlet distribution of the samples.
m_max : int, default=1
Maximum number of hypothetically acquired labels.
missing_label : scalar or string or np.nan or None, default=np.nan
Value to represent a missing label.
metric : str or callable, default=None
The metric must be None or a valid kernel as defined by the function
`sklearn.metrics.pairwise.pairwise_kernels`. The kernel is used to
calculate the frequency of labels near the candidates and multiplied
with the probabilities returned by `clf` to get a kernel frequency
estimate for each class.
If metric is set to None, the `predict_freq` function of the `clf` will
be used instead. If this is not defined, a TypeError is raised.
metric_dict : dict, default=None
Further parameters passed directly to the kernel function. With
`metric_dict=None` and `metric="rbf"`, queries use `{"gamma": "mean"}`.
random_state : None or int or np.random.RandomState, default=None
The random state to use.
References
----------
.. [1] D. Kottke, G. Krempl, D. Lang, J. Teschner, and M. Spiliopoulou.
Multi-class Probabilistic Active Learning. In Eur. Conf. Artif. Intell.,
pages 586–594, 2016.
"""
def __init__(
self,
prior=1,
m_max=1,
missing_label=MISSING_LABEL,
metric=None,
metric_dict=None,
random_state=None,
):
super().__init__(
missing_label=missing_label,
random_state=random_state,
)
self.metric = metric
self.metric_dict = metric_dict
self.prior = prior
self.m_max = m_max
[docs]
def query(
self,
X,
y,
clf,
fit_clf=True,
sample_weight=None,
utility_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
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`.
utility_weight : array-like, default=None
Weight for each candidate (multiplied with utilities). Usually,
this is to be the density of a candidate in ProbabilisticAL. The
length of `utility_weight` is usually n_samples, except for the
case when candidates contains samples (ndim >= 2). Then the length
is `n_candidates`.
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
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 the samples in
`X`.
- If `candidates` is of shape `(n_candidates, n_features)`,
the indexing refers to the samples in `candidates`.
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`.
"""
clf, target_spec = _fit_and_resolve_estimator_target_spec(
self,
clf,
X,
y,
fit_estimator=fit_clf,
sample_weight=sample_weight,
estimator_name="clf",
fit_name="fit_clf",
estimator_types=(SkactivemlClassifier,),
)
# Validate input parameters.
X, y, candidates, batch_size, return_utilities = self._validate_data(
X,
y,
candidates,
batch_size,
return_utilities,
reset=True,
target_type=target_spec.target_type,
)
X_cand, mapping = self._transform_candidates(candidates, X, y)
# Check `utility_weight`.
if utility_weight is None:
if mapping is None:
utility_weight = np.ones(len(X_cand))
else:
utility_weight = np.ones(len(X))
utility_weight = check_array(utility_weight, ensure_2d=False)
if mapping is None and len(X_cand) != len(utility_weight):
raise ValueError(
f"'utility_weight' must have length 'n_candidates' but "
f"{len(X_cand)} != {len(utility_weight)}."
)
if mapping is not None and len(X) != len(utility_weight):
raise ValueError(
f"'utility_weight' must have length 'n_samples' but "
f"{len(X)} != {len(utility_weight)}."
)
if self.metric is None and not hasattr(clf, "predict_freq"):
raise TypeError(
"clf has no predict_freq and metric was set to None"
)
# Predict frequencies.
if self.metric is not None:
metric_dict = (
{"gamma": "mean"}
if self.metric_dict is None and self.metric == "rbf"
else self.metric_dict
)
pwc = ParzenWindowClassifier(
metric=self.metric,
metric_dict=metric_dict,
missing_label=clf.missing_label,
classes=target_spec.classes,
)
pwc.fit(X=X, y=y, sample_weight=sample_weight)
n = pwc.predict_freq(X_cand).sum(axis=1, keepdims=True)
pred_proba = clf.predict_proba(X_cand)
k_vec = n * pred_proba
else:
k_vec = clf.predict_freq(X_cand)
# Calculate utilities and return the output.
utilities_cand = cost_reduction(
k_vec, prior=self.prior, m_max=self.m_max
)
if mapping is None:
utilities = utilities_cand
else:
utilities = np.full(len(X), np.nan)
utilities[mapping] = utilities_cand
utilities *= utility_weight
return simple_batch(
utilities,
self.random_state_,
batch_size=batch_size,
return_utilities=return_utilities,
)
[docs]
def cost_reduction(k_vec_list, C=None, m_max=2, prior=1.0e-3):
"""Calculate the expected cost reduction.
Calculate the expected cost reduction for given maximum number of
hypothetically acquired labels, observed labels and cost matrix.
Parameters
----------
k_vec_list : array-like of shape (n_samples, n_classes)
Observed class labels.
C : array-like of shape (n_classes, n_classes), default=None
Cost matrix.
m_max : int
Maximal number of hypothetically acquired labels.
prior : float or array-like of shape (n_classes,)
Prior value for each class.
Returns
-------
expected_cost_reduction: array-like, shape (n_samples)
Expected cost reduction for given parameters.
"""
# Check if 'prior' is valid
check_scalar(prior, "prior", (float, int), min_inclusive=False, min_val=0)
# Check if 'm_max' is valid
check_scalar(m_max, "m_max", int, min_val=1)
n_classes = len(k_vec_list[0])
n_samples = len(k_vec_list)
# check cost matrix
if C is not None:
C = np.asarray(C)
# generate labelling vectors for all possible m values
l_vec_list = np.vstack(
[_gen_l_vec_list(m, n_classes) for m in range(m_max + 1)]
)
m_list = np.sum(l_vec_list, axis=1)
n_l_vecs = len(l_vec_list)
# Each count vector extends one with one fewer observation, so
# B(alpha + l) / B(alpha) follows from the beta recurrence without
# evaluating either (potentially underflowing) beta function.
l_indices = {tuple(l_vec): i for i, l_vec in enumerate(l_vec_list)}
added_classes = np.argmax(l_vec_list > 0, axis=1)
predecessors = np.zeros(n_l_vecs, dtype=int)
for i in range(1, n_l_vecs):
predecessor = l_vec_list[i].copy()
predecessor[added_classes[i]] -= 1
predecessors[i] = l_indices[tuple(predecessor)]
k_vec_list = np.asarray(k_vec_list, dtype=float)
multinomial = _multinomial(l_vec_list)
m_sums = np.empty((n_samples, m_max + 1))
# Bound the candidate/count/class tensors to about one million entries.
# Enumerating the count vectors remains combinatorial in m_max.
chunk_size = max(1, 2**20 // (n_l_vecs * n_classes))
for start in range(0, n_samples, chunk_size):
stop = min(start + chunk_size, n_samples)
k = k_vec_list[start:stop]
k_l = k[:, None, :] + l_vec_list
# The prior affects the expectation but not the predicted class.
y_hats = (
np.argmax(k_l, axis=2) if C is None else np.argmin(k_l @ C, axis=2)
)
alpha = k + prior
alpha_sum = np.sum(alpha, axis=1)
beta_ratio = np.ones((len(k), n_l_vecs))
for i in range(1, n_l_vecs):
c = added_classes[i]
beta_ratio[:, i] = beta_ratio[:, predecessors[i]] * (
(alpha[:, c] + (l_vec_list[i, c] - 1))
/ (alpha_sum + (m_list[i] - 1))
)
posterior = k_l + prior
if C is None:
# Sum the non-predicted classes directly to retain small costs
# even when the predicted class probability rounds to one.
np.put_along_axis(posterior, y_hats[:, :, None], 0, axis=2)
expected_cost = np.sum(posterior, axis=2)
else:
expected_cost = np.sum(
posterior * np.moveaxis(C[:, y_hats], 0, -1), axis=2
)
expected_cost /= alpha_sum[:, None] + m_list
weighted_cost = beta_ratio * multinomial * expected_cost
for m in range(m_max + 1):
m_sums[start:stop, m] = np.sum(
weighted_cost[:, m_list == m], axis=1
)
# compute classification cost reduction as difference
gains = np.zeros((n_samples, m_max)) + m_sums[:, 0].reshape(-1, 1)
gains -= m_sums[:, 1:]
# normalize cost reduction by number of hypothetical label acquisitions
gains /= np.arange(1, m_max + 1)
return np.max(gains, axis=1)
def _gen_l_vec_list(m_approx, n_classes):
"""Creates all possible class labeling vectors for given number of
hypothetically acquired labels and given number of classes.
Parameters
----------
m_approx : int
Number of hypothetically acquired labels.
n_classes : int
Number of classes.
Returns
-------
label_vec_list : array-like of shape (n_labels, n_classes)
All possible class label lists for given parameters.
"""
label_vec_list = [[]]
label_vec_res = np.arange(m_approx + 1)
for i in range(n_classes - 1):
new_label_vec_list = []
for labelVec in label_vec_list:
for newLabel in label_vec_res[
label_vec_res - (m_approx - sum(labelVec)) <= 1.0e-10
]:
new_label_vec_list.append(labelVec + [newLabel])
label_vec_list = new_label_vec_list
new_label_vec_list = []
for labelVec in label_vec_list:
new_label_vec_list.append(labelVec + [m_approx - sum(labelVec)])
return np.array(new_label_vec_list, int)
def _multinomial(a):
"""
Computes Multinomial coefficient:
Mult(a(i)) = (a(i,1)+...+a(i,n))!/(a(i,1)!...a(i,n)!)
Parameters
----------
a : array-like of shape (m, n)
Vectors to evaluated.
Returns
-------
result : array-like of shape (m)
Multinomial coefficients [Mult(a(0)), ..., Mult(a(m)].
"""
return factorial(np.sum(a, axis=1)) / np.prod(factorial(a), axis=1)