Uncertainty Sampling for Action Recognition via Maximizing Expected Average Precision

1 Introduction

Recognizing human actions in video clips has been an important topic itself, and also as a component in more complex tasks such as event detection. Most action recognition datasets are collected from various sources, including Youtube and Google videos, Hollywood movies, and so on. With sufficient labeled data, action recognition algorithms are able to achieve good performance. However, while collecting the videos takes effort, labeling them is a more complex task in terms of time and money. Active learning is one way to alleviate the pain of annotation by allowing the classifier to choose the most informative data samples for labeling. It has many applications in computer vision such as segmentation [Dutt Jain and Grauman, 2016], pose estimation [Liu and Ferrari, 2017], and event detection [Yang et al., 2015].

∗Corresponding author

When it comes to applying active learning in classification tasks, uncertainty sampling is arguably the "first choice" owing to its simplicity and effectiveness. However, there is no guarantee that the traditional task-agnostic uncertainty measure matches the evaluation metric of the task at hand. In addition, recent advance [Ramirez-Loaiza et al., 2017] in active learning suggests that conventional uncertainty sampling algorithms may not work when the underlying evaluation metric is not accuracy. Therefore, we argue that the uncertainties of data samples change along with the underlying evaluation metric. In action recognition, Average Precision (AP) is a widely-used evaluation metric that calculates the area under the precision-recall curve, which is somehow overlooked in the active learning community. This paper aims at resolving the issues with the conventional uncertainty sampling algorithms by understanding their intrinsic properties, and developing new active learning algorithms for action recognition.

We propose to evaluate the uncertainty of one video by the expected AP on all other unlabeled videos. Similar to Expected Error Reduction [Roy and McCallum, 2001], videos with maximal expected AP are selected for labeling. Unlike accuracy which can be re-interpreted as the average of individual scores over all samples, AP is more related to complex rank-based metrics (such as AUC). It cannot be viewed as the average of instance-level scores and thus cannot be directly calculated using previous techniques such as [Roy and McCallum, 2001]. In order to obtain expected AP, we face two inevitable obstacles. The first one is "how to calculate AP when the true labels of video clips are unknown," while the second one is "under what distribution is the expected APbased calculated."

Although the true label of each unlabeled video clip is unknown, the probability that the video belongs to the positive (negative) class is provided by the underlying one-vs-rest classifiers. We treat each unknown true label as a independent biased coin that flips head (one) with probability to the positive class, and tail (zero) with probability to the negative class. In other words, the true label associated with each unlabeled video clip is defined as an independent Bernoulli random variable, and the probability of success is defined as the probability that the video belongs to the positive class. After that, we explicitly calculate the expected AP on the joint distribution of all true labels. Since most action recognition datasets have more than two classes, the expected AP is calculated in a one-vs-rest manner. To the best of our knowledge, this is the first work that optimizes AP in active learning for classification. It is also suitable for action recognition tasks, since AP is widely used in such applications.

Our contributions are as follows. First, we introduce a novel technique that treats the true labels of unlabeled videos as independent Bernoulli random variables, thus making it possible to directly calculate the expected evaluation metric. Second, this technique successfully reveals the intrinsic properties of existing uncertainty sampling algorithms. Third, we calculate the expected AP using dynamic programming in polynomial time, and empirically evaluate our algorithm on three real-world action recognition datasets, and show that our uncertainty sampling approach outperforms other uncertain-based methods with (mean) AP being the evaluation metric.

2 RelatedWork

There is an extensive body of literature about action recognition; here we only name a few related to the feature extractor used in this paper. Trajectory-based methods such as Dense Trajectories (DT) [Wang et al., 2011] and Improved Dense Trajectories (IDT) [Wang and Schmid, 2013] are among the most effective feature extractors in action recognition. There are many works in literature that tries to improve on IDT, such as multi-skip feature stacking [Lan et al., 2015] and Fisher Vector encoding [Perronnin et al., 2010]. Since AP is an important evaluation metric in many tasks including action recognition, researchers propose different models that optimize AP during training. For example, [Triantafillou et al., 2017] optimizes AP for information retrieval models. [Yue et al., 2007] proposes a variant of the SVMs that optimizes AP. [Behl et al., 2014] further develops this method in weakly supervised learning by minimizing an upper-bound for AP .

Pool-based active learning is an intensively-studied problem in the machine learning community (See [Settles, 2010] for an overview). In the past two decades, many active learning algorithms are developed, such as selecting uncertain samples [Lewis and Gale, 1994], selecting samples about which a committee of classifier disagree [Seung et al., 1992], querying samplings that minimizes the expected error of the model [Roy and McCallum, 2001], selecting representative samples [Yu et al., 2006], and many more. One of the most widely-used groups of active learning algorithms is uncertainty sampling [Lewis and Gale, 1994; Sharma and Bilgic, 2017], which selects the instances about which the classifier is most uncertain for labeling. Uncertainty sampling is widely used in computer vision tasks such as medical image classification [Zhou et al., 2017], human pose estimation [Liu and Ferrari, 2017], facial expression recognition [Chakraborty et al., 2015], action recognition/event detection [Yang et al., 2015], and so on. In most active learning literature, accuracy is chosen as the evaluation metric, but researchers also develop active learning algorithms for other metrics. For example, [Culver et al., 2006] proposes a method that maximizes AUC of the hypothesis, using a semi-supervised ranking approach. [Long et al., 2010] maximizes discounted cumulative gain (DCG) to select the most informative instances. To the best of our knowledge, there is currently no uncertainty sampling algorithm that directly optimizes AP in literature.

3 The ProposedMethod

In this section, we first review two most widely-used uncertainty measures, namely maximum conditional and entropy, and then we propose to treat unknown true labels as Bernoulli random variables and show that maximum conditional implicitly optimizes expected accuracy. After that, we propose to optimize expected AP and obtain our Uncertainty Sampling via maximizing expected Average Precision (USAP).

3.1 Uncertainty Sampling

Typical uncertainty sampling strategies select top-k instances from the unlabeled pool U based on their individual uncertainty φ(·), formally we have

where S∗ is the set of the most uncertain samples. Two common uncertainty measures are maximum conditional and Shanon entropy. For binary classification, we have

where P1 indicates the probability sample x belong to the positive class. Note that Eq. (1) and Eq. (2) selects the exact same samples in binary classification. There are also multiclass versions of the two algorithms

where P(y|x, w) indicates the probability that instance x belongs to class y given the classifier with weight w.

3.2 Uncertainty Sampling under Accuracy

For binary classification, accuracy is defined as the proportion of samples that are correctly classified over all tested samples, i.e., accuracy = (tp + tn)/(tp + fp + tn + fn). For n unlabeled samples {xi}ni=1 , let the labels be selected from {0, 1} and let pi be the posterior probability that xi belongs to the positive class, i.e., pi = P(y = 1|xi,w). Let {yi}ni=1 be a set of independent Bernoulli random variables such that yi takes one with probability pi and zero otherwise. In other words, we have

Intuitively, for each unlabeled instance xi, we flip a biased coin and let the outcome yi be the true labels of xi. Given the true labels, the accuracy can be easily calculated as follows

where I(·) is the indicator function and ˆ yi is the predicted label of xi. For binary classification, we usually assume ˆ yi takes one if pi > 1 - pi and zero otherwise, i.e.,

By flipping n coins once, we obtain one sample of the accuracy. If the coins are flipped multiple times, the accuracies obtained each time will center around its mean. To avoid actually generating yi for each xi, we can calculate the expectation of accuracy over the joint distribution of all yi, i.e.,

After substituting Eq. (6) and Eq. (7) into Eq. (8), we have

Recall that uncertainty of one instance is defined as the expected evaluation metric on all other instances, i.e., for instance xj , we have its uncertainty φ(xj) under accuracy as

After dropping constants, we have the uncertainty measure that matches the maximum conditional in Eq. (1) as follows

By introducing Bernoulli random variables as true labels, we prove that the maximum conditional strategy implicitly maximizes the expected accuracy, which is usually the underlying evaluation metric. However, recent study [Ramirez-Loaiza et al., 2017] shows that when the underlying evaluation metric is not accuracy, the maximum conditional strategy may fail. Since AP is widely used in action recognition as a evaluation metric, it is desirable to select instances that directly optimizes AP. In the following, we develop an uncertainty sampling algorithm under AP using the same technique.

3.3 Uncertainty Sampling under AP

AP is a more complex evaluation metric than accuracy. It can be described as the area under the precision-recall curve. It is originally used as an evaluation metric for information retrieval tasks, and is now widely-used in classification applications such as action recognition.

For video samples {xi}ni=1 with true labels {yi}ni=1 ∈ {0, 1}n , let {pi}ni=1 be the probability output of the classifier satisfying pi = P(y = 1|xi,w). Without loss of generality, we assume that {pi}ni=1 are sorted in descending order, i.e, p1 ≥ p2 ≥ ... ≥ pn. For convenience, we also define the positive label set U + = {i|yi = 1} and let |U +| be the cardinality of U +. For each i ∈ U +, by carefully setting the classification threshold so that only the first i instances are predicted positive, we have recall that equals i/|U +|. The corresponding precision equals ∑ij=1 yj/i. In other words, each i ∈ U + corresponds to a single precision-recall point on the precision-recall curve. Therefore the area under the curve can be approximated by

Using the fact that |U +| = ∑ni=1 yi, and let {yi}ni=1 be the Bernoulli random variables satisfying yi ∼ Ber(pi), the expected AP can be formulated as

At first glance, the above expectation is difficult to calculate because the denominator ∑nj=1 yj is not a constant. Here we expand the expectation by its definition as

We introduce a auxiliary variable t = ∑nj=1 yj, and the expected AP becomes 1

where

and

Therefore, instead of directly calculating expected AP, we can calculate function h(·) and f(·, ·) instead. For n >= 1 and t >= 1, we can calculate h(·) (and further f(·, ·)) using dynamic programming by splitting Eq. (15) into two terms which separately indicate the case that yn = 0 and yn = 1. Formally, we have

and thus f(n, t) can be reformulated as

where

Similar to Eq. (16), we obtain formula for function g(·, ·) by splitting on yn. Formally, we have

Considering the corner cases, g(n, t) (t >= 0, n >= 0) has the following formulation:

Similarly, f(n, t) (t >= 0, n >= 0) can be reformulated as

Most of the existing action recognition datasets have more than two classes, therefore we use one-vs-rest classifiers and sum the expected AP over all classes. Algorithm 1 demonstrates our Uncertainty Sampling via maximizing Average Precision (USAP) method. When the number of unlabeled samples becomes large, it would be time-consuming to calculate the exact expected AP. To alleviate this issue, we use a fast screening rule to obtain fast approximations for the expected AP, and use it to filter out uninformative samples. Algorithm 1 runs in O(cn3 ) for c-class classification with n unlabeled samples.

Algorithm 1 USAP

Input: number of selected videos k, number of classes c, number of unlabeled videos n, probability estimate p ∈ [0, 1]n×c , unlabeled video set U

Output: selected video set S

• 1: φ← 0
• 2: for i=1 to c do
• 3: for j=1 to n do
• 4: p′ ← p∗i\{pji}% the i-th column of p without pji
• 5: Sort p′ in descending order
• 6: Calculate g(·, ·) using Eq. (17) and p′
• 7: Calculate f(·, ·) using Eq. (18) and p′
• 8: Calculate AP∧using Eq. (14)
• 9: φj ← φj + AP∧
• 10: end for
• 11: end for
• 12: Select S ⊂ U corresponding to the k largest φ value
• 13: Return: S

3.4 Fast Screening Rule

As the previous section shows, calculating the expected AP can be slow in practice. Therefore, we use the precision@n for n video samples as an approximation to filter out uninformative samples.

Precision is the fraction of positive instances among the positively predicted instances, i.e. PREC = tp/(tp + fn). Given probability estimate {pi}ni=1 of n samples in descending order. Precision@n corresponds to recall of 1 because the classification threshold is set so small that all samples are predicted positive. Same as the previous section, we assign Bernoulli random variables {yi}ni=1 as true labels of video samples. Under such circumstances, we have

and the expected precision becomes

Therefore, the approximation of video xj can be viewed as

Given the above approximation, we calculate φPREC(·) for each unlabeled videos and each one-vs-all classifier output, and sum φPREC(·) over all classes. The videos with small sums are discarded for efficiency purposes. The screening rule runs in O(cn) for c-class classification with n unlabeled samples.

4 Experimental Results

Experiment Setting For each video clip, a level-three MIFS [Lan et al., 2015] feature extractor is used to extract fixedlength feature, and Logistic Regression with parameter C = 100 is used as the underlying linear classifier to conduct onevs-rest classification. Note that the purpose of this paper is not to obtain state-of-the-art action recognition results, but to demonstrate the necessity to consider underlying evaluation metric when building active learning algorithms for action recognition. For each dataset, we use the official training set as unlabeled set and official testing set as the unseen testing set. All active learning methods select data from the unlabeled dataset, and one-vs-rest classifiers are trained on all labeled data and tested on testing set. We use Mean Average Precision (MAP) as the evaluation metric. For a c-class video classification, we randomly select 10 videos of each class as initial labeled dataset. As a result, there are 10c labeled videos in the beginning. We iteratively select c videos until the labeling budget is reached. All experiments are repeated with different initial labeled data, and the averaged MAP is reported.

Compared methods We compare our USAP method with the following multi-class baselines:

• Rand: the method that selects unlabeled videos uni-

formly at random

• Pmax: the method that chooses uncertain samples based-on the maximum posterior probability in Eq. (3) [Lewis and Gale, 1994]
• Entro: the uncertainty sampling method based on Shannon entropy in Eq. (4)
• Usdm: the method that maximizes entropy along with diversity [Yang et al., 2015]
• Rank: the method that combines entropy with Mutual Information as diversity [Chakraborty et al., 2015]

Datasets Three representative datasets are used:

The HMDB51 dataset [Kuehne et al., 2011] has 51 action classes and 6766 video clips extracted from digitized movies and YouTube. [Kuehne et al., 2011] provides both original videos and stabilized ones. Only original videos are used in this paper. There are three official train-test splits for this dataset. For each split, we run all active learning methods with two different initial labeled set.

The Hollywood2 dataset [Marszalek et al., 2009] contains 12 action classes and 1707 video clips that are collected from 69 different Hollywood movies. It has 1707 videos in total with a pre-defined split of 823 training videos and 884 test videos. We run each active learning method with five different initial labeled set on this dataset.

The UCF50 dataset [Reddy and Shah, 2013] has 50 action classes spanning over 6618 YouTube videos clips that can be split into 25 groups. The video clips in the same group are generally very similar in background. We use one group as testing data and the other 24 groups as unlabeled data, so there are 25 different splits for this dataset. We use the first

5 of them to test all active learning algorithms, each with one initial labeled set.

To speed up our algorithm, on large datasets UCF50 and Hmdb51, we use the fast screen rule in Section 3.4 to filter out uninformative video samples so that the size of the unlabeled pool does not exceed 2000. Algorithm 1 is then used to select uncertain samples accordingly on the remaining videos.

Results We illustrate the performance of the active learning algorithms for action recognition application in Table 1 and 2. In the two tables, each row corresponds to the number of selected videos, and each column corresponds to an active learning algorithm.

As shown in the two Tables, we have three observations. First, on dataset HMDB51 and UCF50, all active learning algorithms generally outperform random sampling, while on hollywood2, all other active learning algorithms (except ours) fail to outperform random sampling. This is because movie videos of this dataset sometimes have more than one labels, which misleads the conventional uncertainties. Second, our algorithm outperforms the other active learning algorithms when the number labeled samples becomes large. This shows that optimizing AP for active learning is effective. Note that Usdm and Rank sometimes have higher MAP than our algorithm in the initial stage of active learning, which is the effect of the diversity used. Third, our algorithm selects fewer video samples than other active learning algorithms to achieve the same MAP when the labeled set becomes large. For example in hollywood2, our algorithm requires 24c labeled videos to achieve 58% MAP while Pmax and Entro need 28c and 30c respectively.

Combine USAP with diversity In order to integrate our APbased uncertainty with diversity, we replace entropy-based uncertainty with our AP-based uncertainty (φ in Algorithm 1) for algorithm Rank and Usdm. The two new algorithms, denoted as RankAP and UsdmAP, are tested on dataset Hollywood2 with 15c, 20c, and 25c labeled videos.

In Figure 1, UsdmAP and RankAP outperforms Rand in three different number of labeled videos, namely 15c, 20c and 25c, while Table 2 shows that, without our uncertainty measure, Usdm and Rank sometimes has slightly lower MAP than Rand. This result demonstrates that under MAP, our USAP uncertainty measure is able to find more informative videos than the conventional Shanon entropy, combined with existing diversity measures in Usdm and Rank.

5 Conclusion and FutureWork

In this paper, we propose a novel active learning algorithm for action recognition by maximizing expected AP, and treating the unknown true labels of unlabeled videos as independent Bernoulli random variables. The expected AP can be formalized and calculated on the joint distribution of all random variables. Then the uncertainty of each unlabeled video is defined as the expected AP of all other unlabeled videos. The proposed uncertainty sampling algorithm is tested on three real-word action recognition datasets. Experiments show that our algorithm outperforms other uncertainty-based algorithms. As future work, we plan to explore new active learning methods under other metrics such as mean accuracy, Fmeasure and AUC.

Acknowledgments

This work is supported in part by China National 973 program 2014CB340301. We also acknowledge the Data to Decisions and the Cooperative Research Centers program (D2D CRC) for funding Yi Yang's research.