IEEE Geoscience and Remote Sensing Magazine - September 2022 - 260

not span near a decision frontier. When using breaking tie,
we iteratively select the b points that maximize
REPRESENTATIVENESS-BASED METHODS
a ,BT which
might induce redundancy within a batch. Nevertheless,
breaking tie offers major advantages, such as its scalability
to large data sets and its small number of hyperparameters.
BATCH-BALD
A Bayesian model makes predictions (| ,)py xw where the
model parameters w are conditioned on the training data
set Lt
at step :( |). Batch-BALD is an epistemic unt
wp wLt
+
certainty function that estimates the mutual information
between the classes of multiple data points ,,
" 1
the model parameters w:
ax ;) (; |, ).Ly wx L
BB 1 11
(
:bt ::= I bb t
1
f
yyb, and
f
(3)
We can think of Batch-BALD as answering the question,
" xxb
" How would labeling the subset of points ,, , inform
us on the right probability distribution over the model parameters
w? " Another way to consider Batch-BALD is to rewrite
it as
ax Ly wx L
yx Ly xw L
BB(; ) =bt ::
11
1:
11
::
=- (4)
HE H
I
(; |, )
(| ,)
t
bb t
bb tpwL bb t
11
(| ): :(| ,, ).
The first term on the right-hand side of (4) is high when
the model is overall uncertain about its predictions and the
second term is low when the model is certain for each draw
of model parameters from the posterior (| ).pw Lt
Thus aBB
is high when different draws of the model parameters lead
to confident but disagreeing predictions.
To compute those terms, expectations over the model
parameters have to be approximated using MC samples
wp (| ).wL
far as yi
t +
jt The second term can be easily computed as
conditioned on w are independant. The first term is
more difficult to compute as the joint probability of y :b1
not factorize, resulting in a sum over all possible cb
of y ,:b1 which is not tractable in practice. Thus, ()yH :b1
is approximated by sampling m configurations of y .:b1 Moredoes
values
y
:b1
t
over, to overcome combinatorial complexity of the optimization
problem, there are
sible batches of points ,, ,xx ,Ubt1 " f 1
the number of points in ,Ut
a ^^ ^
||
Ut
= ||!! || !Ub Ub
where ||Ut
/
b k hhh postt
-
denotes
a greedy algorithm is proposed.
The main disadvantage of Batch-BALD is that it requires
heavy computational resources on large data sets. If the use
of tensor multiplication on GPU can speed up the computation
of the joint entropy, it is at the expense of heavy memory
requirements as a ||
we recall that ||Ut
t
Um c## matrix is stored, where
is the number of unlabeled points at step
t, m is the number of samples we draw to estimate the joint
entropy (),yH :b1
and c is the number of classes. Moreover,
the larger the batches (of size b), the tougher the estimation
of the mutual information.
BALD is the special case where the size of the batch is
equal to one. Therefore, it only considers samples individually
(like Breaking Tie) and is more prone to query-redundant
samples but is much easier to estimate.
260
HIERARCHICAL
The idea behind [41] is to query points so that there are
enough training samples in each data cluster to make the
classifier confident on the class of every cluster. A hierarchical
segmentation T is computed, starting from a segmentation
where each pixel is a region, to a segmentation where
all pixels are included in one region by iteratively merging
regions based on a similarity criterion. This hierarchical segmentation
can be described as a tree, where the root is the region
containing all pixels and the leaves are each single pixel.
Then, the hierarchical segmentation T is pruned (branches
are kept or cut), starting from the root, whether the test error
prediction is reduced and nodes are said to be admissible. For
a given cluster v classified as its majority label l, the test error
v
e is formulated as the portion of misclassified samples. It is
estimated by querying and labeling points from the clusters
e =pt
()],pt where
LB
vl,
UB
vl,
v 1 maxp ,vl
l
,
(6)
where p ,vl is the portion of the class l in the cluster v. The
confidence interval associated with class probabilities at
step t is [( ),
IEEE GEOSCIENCE AND REMOTE SENSING MAGAZINE SEPTEMBER 2022
CORE SET
Core Set aims to solve a k-center problem, i.e., selecting a
subset s of Ut
ax LU (; ,)
1:
coreset bt t =-maxmin T xx
xU xx L
it jb t
!
! 1: ,
(, ),
ij
of size b such that the largest distance between
an unlabeled data point and its nearest labeled point
is minimized:
(5)
where T is a distance in the classifier output space. The idea is
that every unlabeled point should be included in the smallest
possible balls centered on the labeled points. If the kcenter
problem is NP-hard [44], a greedy algorithm provides
a solution :
x b1
)
= maxmin xi j
!! ,
)
such thatdd# #
,
with dgreedy UL:ij b1xx xxD (, )
greedy 2 opt where optd is the optimal solution.
The result of the greedy algorithm is used as an initialization
to perform the search for a better solution. For
a given radius d [12] formulates a mixed-integer program
that verifies whether the Core Set problem is feasible. This
is much easier to perform than solving the k-center problem
itself. Starting from the upper bound given by the
greedy solution, smaller and smaller bounds are iteratively
queried. Meanwhile, the weakness of the k-center algorithm
(selecting undesired outliers) is tackled by allowing
the algorithm to ignore, at most, a given budget of outliers.
The Core Set approach is motivated by the fact that small
changes in the feature space should induce small changes in
the classifier decision. Therefore, having a training data set
that spans the whole data set should allow the classifier to
have good knowledge of the data. When dealing with large
data sets, computing the distances between every candidate
point and every training point is too time consuming to be
useful in practice. Selecting a subset of the unlabeled data
set, however, can circumvent the problem.
IEEE Geoscience and Remote Sensing Magazine - September 2022

Table of Contents for the Digital Edition of IEEE Geoscience and Remote Sensing Magazine - September 2022
