  Uncertainty sampling is a prevalent active learning algorithm that queries
sequentially the annotations of data samples which the current prediction model
is uncertain about. However, the usage of uncertainty sampling has been largely
heuristic: (i) There is no consensus on the proper definition of "uncertainty"
for a specific task under a specific loss; (ii) There is no theoretical
guarantee that prescribes a standard protocol to implement the algorithm, for
example, how to handle the sequentially arrived annotated data under the
framework of optimization algorithms such as stochastic gradient descent. In
this work, we systematically examine uncertainty sampling algorithms under both
stream-based and pool-based active learning. We propose a notion of equivalent
loss which depends on the used uncertainty measure and the original loss
function and establish that an uncertainty sampling algorithm essentially
optimizes against such an equivalent loss. The perspective verifies the
properness of existing uncertainty measures from two aspects: surrogate
property and loss convexity. Furthermore, we propose a new notion for designing
uncertainty measures called \textit{loss as uncertainty}. The idea is to use
the conditional expected loss given the features as the uncertainty measure.
Such an uncertainty measure has nice analytical properties and generality to
cover both classification and regression problems, which enable us to provide
the first generalization bound for uncertainty sampling algorithms under both
stream-based and pool-based settings, in the full generality of the underlying
model and problem. Lastly, we establish connections between certain variants of
the uncertainty sampling algorithms with risk-sensitive objectives and
distributional robustness, which can partly explain the advantage of
uncertainty sampling algorithms when the sample size is small.
