How Unlabeled Web Videos Help Complex Event Detection?

1 Introduction

Multimedia event detection (MED) has become one of the most important visual content analysis tools as the rapid growth of web video-sharing services such as YouTube [Tamrakar et al., 2012; Natarajan et al., 2012; Habibian et al., 2014; Chang et al., 2015a]. This task aims to identify videos of a particular event of interest, e.g., making a cake or landing a fish, which is the higher level semantic abstraction of long video clips consisting of multiple concepts [Yan et al., 2015]. For example, an event like landing a fish can be described by multiple concepts, such as objects (e.g., human, fish), actions (e.g., standing, pulling) and scene (e.g., beside a river or lake).

Detecting multimedia events from web videos is a complicated and challenging task due to the lack of labeled exemplars, especially the positive ones [Chang et al., 2015b; 2017]. To enhance the performance of such complex event detection, traditional approaches rely on introducing some external sources that are relevant to the target events. Some researches assigned soft labels to related exemplars by assessing their "relatedness" with respect to the positive ones. With various concept selection strategies, Ye et al. and Ma et al. made use of high-level concept sources such as SIN dataset to facilitate the complex event detection [Ye et al., 2015]. In [Duan et al., 2012], event-related web videos were filtered out to help detect complex events. Generally, such external sources used by extant methods are artificially picked and labeled. However, building these external data usually requires professional human annotators, and the procedure is too timeconsuming and costly to scale. On the contrary, there are plenty of low-cost unlabeled videos on the web, which might have significant information for the complex event detection. As a result, it would be beneficial to exploit a more flexible approach which is able to utilize the easy-to-get unlabeled web videos together with the limited labeled data.

∗Corresponding author: Xiaojun Chang (cxj273@gmail.com)

Open source videos, i.e., unlabeled web videos without artificial picking and annotating in this paper, are usually unstructured and do not follow any particular distribution [Chang et al., 2015c]. Note that we call these videos unlabeled web videos because in this work they are used without any labels, even some weak labels such as the video's description. These characteristics make the unlabeled web videos easy to access. However, numerous videos from open source might have different impacts on the detection of a target event. To illustrate this point more clearly, we take the event landing a fish for an example (see Figure 1), where unlabeled web videos, e.g., playing with fishes and dolphin show, share several concepts such as fish and human with the target event. These videos might be beneficial for the target event detection. However, there are also some unlabeled web videos, such as motor racing and getting a vehicle unstuck, which are completely irrelevant to the target event. Involving these web videos in the training stage might degrade the classifier. As a result, it is challenging to involve the easy-to-get web videos to enhance the performance of MED.

In light of this, there are mainly two issues to be considered with respect to introducing the open source videos into MED. The first issue is how to leverage the beneficial semantic information of unlabeled web videos to enhance the performance of complex event detection. The second issue is how to alleviate the side effect of unlabeled web videos, which might cause large uncertainties and potential threats. To address the both issues, we propose a new robust dictionary learning framework for complex event detection, which is able to handle both labeled and easy-to-get unlabeled web videos by sharing the same dictionary between them. Our model shows strong robustness against the substantial noisy and outlier videos from open source, as a result of employing the ℓq-norm (0 < q < 2) based loss jointly with the structured sparsity based regularization. Figure 2 displays the overview of our framework for complex event detection with both labeled and unlabeled data. The objective is highly non-smooth and non-convex as using the ℓq-norm, therefore we present an effective alternating optimization algorithm to solve the proposed challenging problem.

We summarize our contributions as follows:

• Instead of picking and annotatingweb videos manually, we pioneer to employ the easy-to-get unlabeled web videos from open source to enhance the performance of complex event detection.
• To alleviate the side effect of varying unlabeled web videos, we propose a robust dictionary learning framework to handle labeled videos and unlabeled web videos simultaneously. This model shows strong robustness against the substantial noisy and outlier videos from open source.
• We conduct extensive experiments on the datasets of MED 13 and MED 14 for evaluation. The promising results demonstrate the effectiveness and superiority of the proposed method.

2 RelatedWork

2.1 MEDwith External Sources

External sources have been introduced to enhance the MED task, as the lack of labeled exemplars and the high cost of manual annotation. The intuitive way is to supplement the labeled samples directly. As high-level concept features are promising for event detection [Snoek et al., 2006; Hauptmann et al., 2007; Sadanand and Corso, 2012] and can be regarded as the bridge between training data and external sources, several methods [Yan et al., 2015] were presented to leverage external sources at concept level such as SIN dataset to facilitate event detection. These methods focused on transferring the knowledge from auxiliary data to the target events based on concept selection. However, there are still few researches on how to learn useful semantic information from open source rather than traditional dataset, which is labeled and well-structured but limited and difficult to extend, for the complex event detection. Several algorithms such as [Duan et al., 2012] have made efforts to utilize web videos, which are filtered out with various strategies to ensure these external sources are related to the target event. As a result, these algorithms reduced the utilization rate of web videos and were time consuming for the real-world applications.

2.2 MEDwith Dictionary Learning

Dictionary Learning has the ability to represent the data with a set of relevant basis vectors. It has shown the state-of-the-art performance on computer vision analysis due to the intrinsic sparse property of visual data. Most of the researches were dedicated to image processing problem [Raina et al., 2007; Mairal et al., 2009b; Jiang et al., 2015; Ramirez et al., 2010], and few works focused on MED from videos. For example, Yan et al. proposed a novel event oriented dictionary representation in [Yan et al., 2015] for each event to get more accurate and faster performance. While these works have made inspiring progress, the research on MED with dictionary learning is still in its infancy. Extant approaches are mainly based on traditional dictionary learning, which employs squared ℓ2norm as the reconstruction error. Therefore these methods are sensitive to noisy and outlier data. In the open source scenario, unlabeled web videos usually are unstructured and do not follow any particular distribution, hence noisy and outlier exemplars are inevitable by nature. As a result, robustness against noisy and outlier data needs to be taken into account in dictionary learning for complex event detection.

2.3 MEDwith Semi-Supervised Learning

Semi-supervised learning is a good way to handle the shortage of the labeled exemplars as its capability of utilizing both labeled and unlabeled data simultaneously. Recently, lots of researches [Chang et al., 2014; Misra et al., 2015; Liang et al., 2015; Luo et al., 2017] focused on the area of multimedia analysis such as feature selection and object detection with semi-supervised learning. For example, in [Chang et al., 2014], Chang et al. proposed a novel convex semi-supervised multi-label feature selection algorithm for large-scale datasets. Inspired by the baby learning process, Liang et al. integrated prior knowledge modeling, exemplar learning and learning with video contexts for supervised object detection in [Liang et al., 2015]. To avoid semantic drift when using semi-supervised learning [Misra et al., 2015], Misra et al. presented an approach to constrain this process by combining multiple weak cues in videos and exploiting decorrelated errors by modeling data in multiple feature spaces. Though aforementioned work has shown the potential of semi-supervised learning, research on more challenging and complicated tasks such as MED is desired.

3 The ProposedMethodology

Considering the complexity of MED and the limited number of labeled exemplars for a specific event, TRECVID Semantic Indexing Task (SIN) dataset 1 is usually leveraged to enhance the performance of complex event detection. In this paper, we follow the concept selection strategy used in [Yan et al., 2015]. For an event, first we calculate the similarity between concepts and this event by using both textual and visual methods, second we give equal weights to two different strategies to fuse the similarity and then select the Top 10 ranked concepts. As a result, we can automatically select videos which have semantic meaningful concepts for each MED event. Besides the SIN dataset which is labeled manually, a large number of videos are available without labels in practice. These videos might have significant information to enhance the accuracy of classification. However, few studies have been proposed to use these unlabeled videos for MED.

For a MED task, we suppose there are n1 positive training exemplars of the event collected into matrix X1 = [x(1) 1 , x(1) 2 , · · · , x(1) n1 ] ∈ Rd×n1 and n2 negative training exemplars of the event collected into matrix X2 = [x(2) 1 , x(2) 2 , · · · , x(2) n2 ] ∈ Rd×n2 . Let X3 = [x(3) 1 , x(3) 2 , · · · , x(3) n3 ] ∈ Rd×n3 be n3 semantic meaningful exemplars form SIN dataset, where the exemplars are collected from specified selected concepts for each event. X0 = [x(0) 1 , x(0) 2 , · · · , x(0) n0 ] ∈ Rd×n0 be the matrix whose columns are the unlabeled exemplars. The goal of MED in this paper is to learn a shared dictionary across the exemplar matrices X1, X2, X3, X0 and the corresponding sparse representation of each exemplar, such that unlabeled videos from open source are involved in this task and the dictionary is able to predict labels for the unseen exemplars.

Let the shared dictionary D = [d1, · · · , dr] ∈ Rd×r consisting of r basis vectors dj (j = 1, 2, · · · , r) and a(k) i = [a(k) 1i , a(k) 2i , · · · , a(k) ri ]⊤ ∈ Rr (k = 0, 1, 2, 3; i = 1, 2, · · · , nk) be the sparse representation of exemplar x(k) i ∈ Rd with respect to dictionary D. We collect all sparse representations of exemplar matrix Xk (k = 0, 1, 2, 3) into a coefficient matrix Ak = [a(k) 1 , · · · , a(k) nk ] ∈ Rr×nk . In this paper, the optimal dictionary D and the sparse representation Ak (k = 0, 1, 2, 3) are learned jointly by minimizing the following objective:

where the constraints on the ℓ2-norms of the basis vectors dj (j = 1, 2, · · · , r) are utilized to avoid degenerate solutions [Wang et al., 2013]. The ℓq-norm (0 < q < 2) is used to measure the reconstruction errors over all exemplars. This strategy significantly mitigates the influence of a large number of outlier and noisy data which is derived very far from the true data distribution [Wang et al., 2013].

1 http://www-nlpir.nist.gov/projects/tv2013/tv2013.html#sin

Typically, the smaller the value of q is, the less impact the outlier (noisy) exemplars have. The ℓ2,p-norm regularization term ‖Ak‖2,p = (∑ri=1 (∑nk j=1 |a(k) ij |2 ) p2 ) 1p penalizes all nk entries in each row of representation coefficient matrix Ak which corresponds to one single basis vector of dictionary D as a whole. As a result, when 0 < p < 2, structured sparsity is enforced on the coefficient matrix Ak (k = 0, 1, 2, 3) such that the basis vector of dictionary corresponding to the nonzero row of coefficient matrix Ak is selected for succeeding data representation. Specifically, for the training exemplars Xk ∈ Rd×nk , its dictionary is computed by

where ai(k) (i = 1, 2, · · · , r) is the i-th row of spare representation matrix Ak ∈ Rr×nk (k = 0, 1, 2, 3). For convenience, we construct the k-th dictionary for training exemplar matrix Xk as Dk ∈ Rd×|Dk| using all di ∈ Dk. Different from the method in [Wang et al., 2013], which using unlabeled and labeled data, our model is able to leverage the easy-toget unlabeled web videos, along with labeled MED data and event-related SIN dataset.

Given an unseen exemplar x and the learned dictionaries Dk(1 ≤ k ≤ 2), we can compute the sparse representation a(k) of x with regard to positive or negative class of the event, by solving the following LASSO problem:

Based on the sparse representation, the reconstruction error of x with respect to positive or negative class is calculated by

for k = 1, 2. Therefore, we can easily assign positive or negative label to this video x according to the result of sorting the reconstruction errors, i.e.,

In summary, by sharing the same dictionary, our model is able to handle both labeled and unlabeled data with a unified form. Moreover, the ℓq-norm based loss and the structured sparsity based regularization ensure the strong robustness of the proposed model against the substantial noisy and outlier videos from open source. Finally, our model detect events from testing videos with positive and negative adaptive dictionaries, which are generated by the structured sparsity based representation coefficients.

4 Optimization Algorithm

Considering the non-smoothness and non-convexity of the objective function (1), in this section, we exploit an alternating optimization algorithm to solve the proposed challenging problem effectively. For a better representation, we first introduce some notations and rewrite the optimization problem (1) as its simpler form equivalently.

We denote D = {D = [d1, . . . , dr] ∈ Rd×r : djd⊤j ≤ 1, ∀j = 1, . . . , r} as the feasible solution set of dictionary for optimization problem (1). Let X = [X0,X1,X2,X3] ∈ Rd×n be the collection of all the training exemplars and A = [A0,A1,A2,A3] ∈ Rr×n be the corresponding spare representation with respect to a specific dictionary D ∈ D, where n = ∑3k=0 nk. By denoting E = [e1, e2, . . . , en] = X - DA and Ak = [a1(k) , a2(k) , · · · , ar(k) ]⊤ (k = 0, 1, 2, 3), we define diagonal matrices Σ = diag(σ11, σ22, · · · , σnn) ∈ Rn×n and Λk = diag(λ(k) 11 , λ(k) 22 , · · · , λ(k) rr ) ∈ Rr×r (k = 0, 1, 2, 3), where 2

for i = 1, 2, · · · , n; j = 1, 2, · · · , r and k = 0, 1, 2, 3. In this sense, the optimization problem (1) is equivalent to the following problem:

When variable A is fixed, the optimization problem (7) with respect to variable D turns to a traditional dictionary learning problem, i.e.,

Considering the independence of the basis vectors, we update the dictionary D column by column through an efficient algorithm proposed in [Mairal et al., 2009a].

When the shared dictionary D is fixed, the optimization problem (7) can be decomposed into four independent problems with respect to each sparse representation matrix Ak (k = 0, 1, 2, 3), i.e.,

where Σk is the k-th part of diagonal matrix Σ corresponding to training exemplar matrix Xk. By setting the derivative of the objective function above with respect to Ak to zero, we have D⊤DAkΣk - D⊤XkΣk + γΛkAk = 0. As a result, for each training exemplar x(k) i in Xk (k = 0, 1, 2, 3; i = 1, 2, · · · , nk), we arrive at its spare representation given dictionary D by

In summary, we describe the alternating algorithm for optimization problem (1) in Algorithm 1. Note that the main computational complexity of this algorithm lies in calculating Algorithm 1 Alternating algorithm for problem (1)

2σii might be meaningless if 2q ‖ei‖2-q 2 is zero. Following the strategy used in [Nie et al., 2010], we regularize σii as 1 2 q ‖ei‖2-q 2 +ς since 1 2 q ‖ei‖2-q 2 +ς → 1 2 q ‖ei‖2-q 2 when ς → 0. Similar strategy can be used for λ(k) jj .

Input: Training data X = [X0, . . . ,XK] ∈ Rd×n , parameters γ, q and p.

Set t = 0, initialize D ∈ Rd×r and A ∈ Rr×n randomly, Σ ∈ Rn×n and Λk ∈ Rr×r (0 ≤ k ≤ K) as identity matrices.

1: repeat

• 2: Update the dictionary Dt+1 with algorithm proposed in [Mairal et al., 2009a];
• 3: for k = 0, . . . ,K do
• 4: Update each column of At+1 k with Eq. (10);
• 5: end for
• 6: Calculate the diagonal matrix Σt+1 with the i-th diagonal element as σt+1 ii = 1 2 q ‖xi-Dt+1 at+1 i ‖2-q 2 ;
• 7: Calculate the diagonal matrix Λt+1 k (0 ≤ k ≤ K) with the i-th diagonal element as (λ(k) ii )t+1 = 1 2p ‖(ai(k) )t+1 ‖2-p 2 ;
• 8: t = t +1

9: until Converge

Output: D and A.

the inverse of r ×r matrix during updating sparse representation for each exemplar with complexity O(nr3 ). To illustrate the effectiveness of the proposed algorithm theoretically, we first introduce a lemma in [Wang et al., 2015], i.e.,

Lemma 1. For any nonzero vectors vt+1 and vt , the following inequality holds for any t = 0, 1, 2, · · ·

where 0 < p < 2.

Based on Lemma 1, the convergence of the proposed alternating algorithm is illustrated by the following Theorem 1.

Theorem 1. The alternating updating rules in Algorithm 1 monotonically decrease the objective function value of optimization problem (1) in each iteration.

Proof. The detail proofs are skipped due to space limitation. It will be provided in the extended version of the paper.

5 Experiment

5.1 Datasets

We evaluate on two large scale real-world datasets: the TRECVID MEDTest 2013 3 and the TRECVID MEDTest 2014 4 , which are collected by the NIST for the TRECVID competition. Each dataset contains 20 complex events with 10 events in common. Specifically, the MEDTest 2013 dataset has events E006 to E015 and E021 to E030, while the MEDTest 2014 contains events E021 to E40. Please refer to the official website for the complete list of event names.

3 http://nist.gov/itl/iad/mig/med13.cfm

4 http://nist.gov/itl/iad/mig/med14.cfm

To enhance the performance of MED, SIN dataset is usually leveraged for its meaningful exemplars. It contains annotation for 346 semantic concepts from web videos. These concepts include objects, actions, scenes, attributes and nonvisual concepts which are all the basic elements for an event, e.g. kitchen, bus, boy. We use the Yahoo Flickr Creative Commons 100 Million Dataset (YFCC100M) [Thomee et al., 2016] as the unlabeled web videos in the experiments. YFCC100M is the largest public multimedia collection that has ever been released, comprising a total of 100 million media objects, of which approximately 99.2 million are photos and 0.8 million are videos. In this work, we only use these unlabeled videos (0.8m) to evaluate the proposed algorithm.

5.2 Experimental Setup

We extract state-of-the-art features from the videos. Specifically, Convolutional Neural Network (CNN) features are extracted. We extract the CNN features using the network architecture released by VGG. In our work, we extracted the features from the activation of the last pooling layer (pool5), as it has been demonstrated to be the best single feature in the literature. The VLAD encoding is applied after to form 65,536 dimensional representation. We cross-validated the regularization parameters in the range of {0.01, 0.1, 1, 10, 100}. We set p = 0.8 and q = 1.2 in our experiments to achieve the best performance. In order to keep our model (1) from being biased when the size of unlabeled data is greatly larger than labeled data, we follow the setting in [Amini and Gallinari, 2002], which showed that 20% of labeled data in the training set could improve the performance significantly. Average Precision (AP) and Mean AP (mAP) are used as the evaluation metrics. Higher value indicates better performance.

5.3 ComparisonMethods

The proposed algorithm is compared with these baselines:

• Support Vector Machine (SVM): SVM has been widely used by several research groups for MED competition and has shown its effectiveness. Hence, we use it as a baseline.
• Multiple Kernel Transfer Learning (MKTL) [Luo et al., 2011]: This algorithm aims to incorporate prior features into a multiple kernel learning framework.
• Dirty Model Multi-Task Learning (DMMTL) [Jalali et al., 2010]: This is a state-of-the-art multi-task learning algorithm imposing ℓ1/ℓp-norm regularizations.
• Multiple Kernel Learning Latent Variable Approach (MKLLVA) [Vahdat et al., 2013]: It is a multiple kernel learning latent variable approach for complex event detection.
• Event Oriented Dictionary Learning (EODL) [Yan et al., 2015]: EODL leverages training samples of selected concepts from the SIN dataset into a jointly supervised multitask dictionary learning framework.
• Class-Specific Sparse Multiple Kernel Learning (CSSMKL) [Liu et al., 2016]: This is a class-specific sparse multiple kernel learning algorithm for spectral-spatial hyperspectral image classification.

5.4 Experimental Results Analysis

To demonstrate the effectiveness of our proposed robust dictionary learning framework with unlabeled web videos, we evaluate all comparison methods with 10 and 100 positive exemplars from test datasets, respectively. Due to the space limitation, we only present in Figure 3 the performance of AP with respect to each event of TRECVID MED 13. We observe from the experimental results that: (1) Since both the proposed model and EODL are based on dictionary learning, they generally perform as the best competitive classifiers, while other algorithms have varying degree of success on different events. (2) Thanks to the unlabeled web videos introduced in complex event detection, our algorithm achieves the best or second-best performance for 19 out of 20 events, indicating the positive function of unlabeled web videos to some extent. Specifically, for almost all of the events, such as "E006: Birthday party" and "E010: Grooming an animal", there are plenty of related videos in YFCC100M which play an effective role in promoting the performance of complex event detection; Instead, only a few unlabeled videos from YFCC101M are relevant to the event "E008: Flash mob gathering". These substantial unlabeled web videos are served as noises and outliers for complex event detection. As a result, it is reasonable that our algorithms performs poorer than EODL in terms of "E008: Flash mob gathering."

For a fair comparison, we further report in Table 1 the values of mAP over 20 events of TRECVID MEDTest 2013 and 2014, respectively. The experimental results indicate that: (1) For all of the competitors, more positive exemplars, i.e., 100Ex vs. 10Ex, are beneficial to enhance the performance of complex event detection remarkably. This phenomenon gears to the fact that more labeled data is crucial for MED tasks; (2) Our model consistently outperforms other state-of-the-art methods with respect to both 100Ex and 10Ex. Specifically, our model achieves a 15.8% on average improvement in terms of mAP comparing with the SVM that is widely used in MED competition. This result indicates that the proposed robust dictionary learning framework has strong robustness against substantial noisy and outlier videos from open source.

6 Conclusion

In this paper, we have carried out the first exploration about utilizing the easy-to-get unlabeled web videos to enhance the performance of complex event detection. We proposed a new robust dictionary learning framework to handle both labeled and unlabeled data by addressing two main challenges caused by open source videos, i.e., how to leverage their beneficial semantic information and how to alleviate their side effect. Moreover, we present an effective alternating optimization algorithm to solve the proposed highly non-smooth and nonconvex problem. Finally, extensive experiment results on several large scale datasets demonstrate the effectiveness of the proposed method. In the future, we intend to focus on the dictionary learning over multi-view features for MED.

Acknowledgments

This work is was supported in part by "The Fundamental Theory and Applications of Big Data with Knowledge Engineering" under the National Key Research and Development Program of China with grant Nos 2016YFB1000903; Ministry of Education Innovation Research Team No. IRT13035; Project of China Knowledge Centre for Engineering Science and Technology; National Science Foundation of China under Grant Nos. 61502377.