Unsupervised Human Action Categorization with Consensus Information Bottleneck Method

1 Introduction

Recognizing human actions automatically has been an active research area due to its wide applications, such as sports analysis, activity monitoring, action/event retrieval, etc. However, because of the large amount of intra-class variations, cluttered background and occlusion, changes of view point and camera motions, discovering action categories automatically remains a difficult and challenging task in the domain of computer vision.

In the past several years, many existing feature representations have achieved impressive progress, such as histogram of oriented gradient (HOG), histogram of optical flow (HOF)

⇤This work supported by the National Natural Science Foundation of China under grant No. 61170223, No. 61502434 and No. 61502432. Corresponding author: Yangdong Ye.

and motion boundary histograms (MBH), but their performances are still limited by the biases rooted in their selfstructures. Therefore, it would be pertinent to mention feature fusion method, which has recently shown excellent performance for human action recognition. In feature fusion scheme, multiple features are integrated to produce a more discriminative new feature. For instance, [Elfiky et al., 2012] investigated the optimal fusion of multiple features in the context of compact pyramid model. P. Natarajan [Natarajan et al., 2012] analyzed and combined color, motion, audio and audio-visual features by late score fusion method. However, feature fusion conducts prior to the procedure of action or object recognition, which can hardly consider the relationships between classes and different features.

Recently, general frameworks to deal with multiple features have been explored. Two most common approaches are multi-view clustering and consensus clustering, and both of them assume that there is a single, true clustering of the data set. Multi-view clustering [Cao et al., 2015; Kumar and Daum´e, 2011; Kumar et al., 2011; Wang et al., 2014] uses multiple views of the data set, rather than just one view, to improve clustering performance. It directly takes multiple features as input views, and tries to fully leverage the correlative information across features. However, human actions in images and videos are usually represented by several high dimensional multi-view features, which results in the problem of the dimensionality curse. Moreover, the trade-off determination of multiple features is also a difficult problem. Consensus clustering [Iam-On et al., 2011; Li et al., 2007; Strehl and Ghosh, 2003; Wu et al., 2015; Zhou et al., 2015] aims to find a single partition of data from multiple existing basic clusterings, where each basic clustering can be generated by one type of features, such as HOG, HOF, MBH, etc. So the final clustering is a consensus from these basic clusterings. However, consensus clustering yields final clustering without access to the underlying features of the human action data, which always makes the final partition limited to the quality of existing basic clusterings.

Due to the aforementioned problems, we present a novel and effective Consensus Information Bottleneck (CIB) method. This algorithm learns action categories according to one feature variable, while taking multiple clusterings obtained from other features as auxiliary variables. The complementary information between feature variable and existing auxiliary clusterings is measured by Maximization of Mutual Information (MMI). To solve MMI optimization, a sequential solution is proposed to update data partition. Our experiments demonstrate the effectiveness of CIB on five realistic human action data sets. In this study, the contributions can be summarized as below:

• ÷ A novel and effective consensus information bottleneck method is proposed, which learns action categories according to one feature variable and multiple clusterings simultaneously. Thus, the proposed method can solve the overreliance of consensus clustering on existing partitions.
• ÷ An effective measurement based on MMI is designed to quantify the complementary information between feature variable and existing auxiliary clusterings.

2 RelatedWork

2.1 Consensus andMulti-viewClustering

In the past decades, many consensus clustering and multiview clustering methods have been proposed. [Strehl and Ghosh, 2003] formalized consensus clustering as a combinatorial optimization problem in terms of shared mutual information. [Li et al., 2007] applied non-negative matrix factorization (NMF) to clustering ensemble. [Wang et al., 2011] applied a Bayesian method to consensus clustering. [Iam-On et al., 2011] proposed a link-based approach to the cluster ensemble problem. [Zhou et al., 2015] learned a robust consensus matrix for consensus clustering via Kullback-Leibler divergence minimization. [Wu et al., 2015] provided a systematic study of K-means-based consensus clustering (KCC). Recently, several studies have shown consensus clustering can improve the performance of human action clustering. For instance, [Yang et al., 2013] discovered motion primitives by hierarchical clustering optical flow in spatial and motion space. [Jones and Shao, 2014] estimated the mutual information between two clusterings and used it to improve the results of both clusterings simultaneously in the task of clustering of human action in context.

Recent advances in multi-view clustering should also be considered. [Kumar and Daum´e, 2011] presented co-training and co-regularized multi-view spectral clustering. [Wang et al., 2014] proposed a formulation for multi-feature clustering using minimax optimization, which unifies different feature modalities by minimizing their pairwise disagreements. [Cao et al., 2015] utilized Hilbert Schmidt independence criterion as diversity term to explore the complementarity of multiple features. However, the problem of dimensionality curse and trade-off determination for multiple views needs to overcome.

2.2 Information Bottleneck

The Information Bottleneck (IB) method, introduced in [Tishby et al., 1999], is an information-theoretic framework. Given the joint distribution of a source variable X and another relevant variable Y , IB tries to extract a compressed representation T of X, while preserving information about Y . The notion of compression is quantified by I(X; T ), while the informativeness is quantified by I(Y ; T). The basic quantity utilized in the IB framework is Shannon's mutual information, which is formally defined as:

Formally, the IB function is suggested in [Tishby et al., 1999] as follows:

where the tradeoff parameter β is the positive Lagrange multiplier controlling compression and informativeness. The solutions of this optimization problem are characterized by the bottleneck equations,

IB has been extended to deal with multiple variables. [Slonim et al., 2006] proposed multivariate extensions of IB method. [Gao et al., 2007] concentrated on multi-view problem using traditional clustering ensemble, which merely generates final result frommultiple basic clusterings. [Lou et al., 2013] and [Yan et al., 2015] proposed multi-feature extension of IB, which directly takes multiple features as input. [Xu et al., 2014] utilized IB to learn a shared subspace represented by multi-view features. In this study, we estimate the complementary information between feature variable and clusterings and use it to improve the performance of final clustering.

where DKL(·♣♣·) is the Kullback-Leibler divergence, Z(x↪ β) is a normalization function. The object of IB method is to find a compressed p(t♣x) of X.

3 Consensus Information Bottleneck method

In this section, we first define the problem of consensus information bottleneck (CIB) and give one formulation of the objective function, then the optimization of CIB method is presented.

3.1 ProblemDefinition

Given a collection of unlabeled videos including various human actions, such as cycling, boxing, diving, etc. In realistic scenarios, the performances of single feature representation are still limited by the biases rooted in their self-structures. Two most common approaches dealing with multiple features are consensus clustering and multi-view clustering, but they still have their own flaws, for instance, the overreliance of consensus clustering method on existing partitions, the dimensionality curse and trade-off determination of multi-view clustering. So we are curious about whether we can draw the advantage from both consensus and multi-view clustering.

Suppose there is an unlabeled video collection X taking values from ¶x1↪ x2↪ ▷ ▷ ▷ ↪ xm♦, which contains various action categories, and m is the total number of videos in the data. We assume that there are k + 1 discrete random variables Y1↪ ▷ ▷ ▷ ↪ Yk+1 on behalf of k+1 types of features of the video data, such as HOG, HOF, MBH, STIP, 3DSIFT, etc. First, we stochastically choose one discrete random variable as feature variable Y = ¶y1↪ y2↪ ▷ ▷ ▷ ↪ yn♦, which characterizes the videos X from one cue. Then the remaining k variables are used to generate multiple valid clusterings C1↪ ▷ ▷ ▷ ↪ Ck of the videos. The task of CIB algorithm is to learn a compressed representation p(t♣x) from both feature variable and multiple clusterings.

3.2 Objective Function

In this section, a novel and effective method named CIB is proposed to discover action categories in videos by considering both feature variable and multiple clusterings. The model of CIB is given in Figure 1, which has two parts: data compression and information preservation. In data compression, original videos X including various actions are compressed into variable T. In information preservation part, the compressed variable T should preserve the information about feature variable Y and existing clusterings C1↪ ▷ ▷ ▷ ↪ Ck. The objective function of CIB can be formulated as follows according to the Equation 2:

where I(X; T) measures the compactness of source variable X into the compressed variable T. I(Y ; T) + I(C1; T)↪ ▷ ▷ ▷ ↪ I(Ck; T) measures what information the compressed variable T should preserve, of which the I(Y ; T) is on behalf of its relevant feature information, I(C1; T)↪ ▷ ▷ ▷ ↪ I(Ck; T) denotes its information with respect to the information of existing clusterings. β is the balance parameter controlling the trade-off between information compression and preservation. λ1↪ ▷ ▷ ▷ ↪ λk are trade-off parameters to balance the influence of different existing clusterings obtained frommultiple features. For the convenience of optimization, we consider the problem of maximizing

which is clearly equivalent to minimize the Equation 4 by dividing -β. In the task of unsupervised human action categorization, the number of action categories M is much less than the source video variable X, which implies a significant compression. Therefore, we concentrate on preserving the information of T with respect to feature variable and existing clusterings maximally. To achieve this goal, the value of β is fixed to 1, so the mutual information I(X; T) is eliminated. Now, the objective function of CIB can be rewritten as

the fraction I(Y ; T) indicates to maximally preserve relevant feature information they capture about Y , λ1I(C1; T)↪ ▷ ▷ ▷ ↪ λkI(Ck; T) denote the preserved information with respect to existing clusterings. This study focuses on the hard clustering, where the value of p(t♣x) is either 0 or 1. Now, the task of our unsupervised human action categorization is reduce to maximize the objective function 6.

3.3 Optimization

To find an optimal partition of source videos X, a sequential draw-and-merge optimization method is presented. The sequential draw-and-merge method starts with random partition of X into M clusters. At each step, a potential x 2 X is drawn from its current cluster told , and then represented as a new singleton cluster ¶x♦. Now, we have M + 1 clusters. To ensure the total number of clusters is M, we must merge the singleton cluster ¶x♦ into one of clusters tnew . So we should guarantee to increase the value of objective function 6 at each draw-and-merge procedure.

The key issue of CIB is to decide which cluster tnew the singleton cluster ¶x♦ should be merged into. Let Lbef and Laft denote the value of function 6 before and after x is drawn from its current cluster; let Lnew denote the value of function 6 after x is merged into some new cluster tnew . The measure of deciding merger procedure is called "merger cost" dL, which is on behalf of the value change after one draw and merge procedure, i.e. dL = Laft -Lnew . We should merge ¶x♦ into tnew such that tnew = argmindL. In the following, we will give the solution to this problem.

Now, we first calculate the difference of I(Y ; T) in function 6 between the values of Lnew and Laft , which denoted by ∆Ifeature . Let x be merged into cluster t and become a new cluster et, i.e. ¶¶x♦↪ t♦ ) et, then

Using Equation 7 and Equation 8, we can get the following results.

Next, we give the calculation of λ1I(C1; T) + · · · + λkI(Ck; T). Suppose Ci is the i'th clustering from one feature representation, so we can compute the confusion matrix R(p↪ q) of Ci and T, where p and q are clusters in Ci and T. The elements in R are co-occurrence number of source data x belongs to both p in Ci and q in T. So the mutual information between T and Ci can be calculated. Now, the difference of λ1I(C1; T) + · · · + λkI(Ck; T) in function 6 between the values of Laft and Lnew is calculated by ∆Iclustering = λ1[I(C1; T aft ) - I(C1; T new )] + · · · + λk[I(Ck; T aft ) - I(Ck; T new )]. So the total merger cost dL is calculated as follows:

where the JSQ is the Jensen-Shannon divergence, Q = ¶ p(x) p(x)+p(t) ↪ p(t) p(x)+p(t) ♦. Since JSQ ≥ 0, we obtain ∆Ifeature ≥ 0.

At each draw-and-merge step, x will be merged into tnew such that tnew = argmindL, where dL is on behalf of the information loss. Note that, once x is merged into one new cluster, there must be some information loss, so we can get ∆Iclustering ≥ 0 and dL ≥ 0. Assumed X has a true clustering C, we can obtain I(T;Ci)  I(C;Ci). And because T is a compressed representation of X, so I(T ; Y )  I(X; Y ). So the value of objective function 6 is upper bounded, which is guaranteed to converge to a stable solution. The details of CIB algorithm is shown in Algorithm 1.

3.4 Complexity Analysis

In this section, we give the computation costs of the CIB algorithm. The time complexity of the random initialization at step 2 and the procedure of drawing some x at step 5 is O(N). At step 6, the merger cost dL between x and each new cluster t should be calculated, which takes O(lM♣X♣♣Y ♣), where l is the number of repetitions that should be performed over X

Algorithm 1 The Consensus Information Bottleneck: CIB

• 1: Input: Joint distribution p(X↪ Y ); multiple clusterings C1↪ ▷ ▷ ▷ ↪Ck; trade-off parameters λ1↪ · · · ↪ λk, cluster number M).
• 2: Initialize: T Random partition of X intoM clusters;
• 3: repeat
• 4: for For every x 2 X do
• 5: Draw: Remove x from current cluster t(x);
• 6: Computing merger cost:

For data point x, calculate merger costs dL of all possible reassignments of x to different clusters based on Equation 6;

• 7: Merge: Merge x into cluster tnew such that tnew = argmint2T dL;
• 8: end for
• 9: until Convergence
• 10: Output: A partition T of X into M clusters.

until convergence is attained. From the experimental section, the CIB takes a few repetitions to converge. The M is the number of clusters, usually, it can be considered as constant. Note that the calculation of mutual information between tnew and multiple clusterings C1↪ ▷ ▷ ▷ ↪Ck takes O(1), so the time complexity of CIB is O(♣X♣♣Y ♣).

4 Experiments

4.1 Data Set Descriptions

In this section, to evaluate the effectiveness of the proposed CIB algorithm, extensive experiments are conducted on five benchmark video data sets. The Weizmann data set contains 10 action categories performed by 9 people, to provide a total of 90 videos. The KTH data set contains 6 types of human actions performed by 25 subjects in outdoor and indoor environment, total of 599 sequences. UCF Sports [Rodriguez et al., 2008] data set consists of 1100 videos of various sports action videos, taken from various broadcast sources. UCF50 [Reddy and Shah, 2013] is an action recognition data set with 50 action categories, consisting of 6000 realistic videos in YouTube. HMDB [Kuehne et al., 2011] data set is a recently released large video database, which has been collected from various sources, mostly movies, and contains 6849 clips divided into 51 action categories. Figure 2 shows example frames in HMDB data set.

4.2 Experimental Setup

To incorporate the consensus information of auxiliary clusterings, we adopt the following three descriptors: STIP, HOG, HOF, to extract motion representations of the actions. Then the bag-of-words (BoW) model is adopted to represent videos. The size of the vocabulary in BoW model is set to 1000, which results in a 1000 dimensional frequency histogram of motion features. We choose one feature from STIP, HOG, HOF randomly as our feature variable, the remaining two features are naturally treated as clustering variables to construct auxiliary clusterings. In this paper, the clustering accuracy (AC) [Cai et al., 2009] is employed to evaluate the performance of different methods. The number of categories M is set to be identical with number of real categories on each data set. As all algorithms are stochastic, all experiments are run 10 times, and we report the average clustering results.

4.3 Experimental Results and Analysis

To validate the performance of the CIB approach, we adopt five types of baselines: original IB method, traditional clustering methods, consensus clustering methods, multi-view clustering methods action clustering methods.

Original IB and CIB

The original IB method can only process one feature variable. As an extension of IB method, CIB can handle feature variable and auxiliary clusterings simultaneously in the clustering procedure. In this section, we conduct the experiments to compare the performance of CIB and original IB. As illustrated in Table 1, we can get the following observations:

• ÷ The performances of IB method on HOG, HOF, STIP are different. For instance, IB method obtains the best AC in terms of HOF feature (69.8%) on Weizmann data set, while it gets the best result in STIP feature (68.9%) on KTH data set. This is mainly because no feature can perform consistently well for different clustering tasks.
• ÷ The performances of original IB method on concatenated feature are less than satisfactory. For instance, there is a decline on Weizmann and UCF Sports (1.9% and 1.4%). So, concatenating features simply can not consistently attain improved results compared with individual feature.
• ÷ The benefits of CIB method are verified as shown in Table 1. The CIB algorithm obtains improvement on all data sets used in this study in terms of AC value (6.6%, 3.2%, 2.0%, 5.2%, 1.0% respectively) compared with the best results of original IB on three individual features. So we can get the conclusion that the CIB algorithm can consistently improve the clustering perfor-

mance compared with the best results of original IB on individual feature.

As for the comparison with pLSA, LDA, NCuts, the results of CIB method obtain great improvement (15.7%, 8.7%, 6.7%, 7.2% respectively). This phenomenon demonstrates that the proposed CIB method is effective by exploiting the complementary impact of feature and multiple clusterings.

Consensus Clustering Methods and CIB

CIB method gives a better performance increase over the baseline consensus clustering methods, such as CSPA [Strehl and Ghosh, 2003], MCLA [Strehl and Ghosh, 2003], BCE [Wang et al., 2011]. We run IB method 15 times with different initializations to obtain 15 base clusterings, all the consensus clustering methods are then applied on them. From Table 2, we note that the performance improvements of CIB over three consensus methods on five data sets are 2.4%, 2.0%, 4.9% in terms of AC, respectively. This is mainly because that CIB can solve the overreliance of consensus clustering on existing clusterings.

Multi-view Clustering Methods and CIB

In this section, the experiments are conducted to verify the effectiveness of CIB method compared with multi-view clustering methods: the Co-Training multi-view Spectral Clustering(CTSC) [Kumar et al., 2011], the Co-Regularized multiview Spectral Clustering (CRSC) [Kumar and Daum´e, 2011] and the Robust Multi-view Spectral Clustering (RMSC) [Xia et al., 2014]. We implement the methods following the original works. A glance at Table 2 shows that our method is always better than the other three multi-view clustering methods by a large margin. Note that, CIB method just adopts one type of feature as input, which will reduce multi-view data dimension significantly.

Action Clustering Methods and CIB

For the comparison with action clustering in videos, we adopt DAKM [Jones and Shao, 2014], MfIB [Lou et al., 2013] and MvIB [Yan et al., 2015] as baselines. DAKM estimates the mutual information between clusterings and used it to improve the results of each clustering simultaneously. MfIB and MvIB are extensions of original IB and multivariate IB respectively, both of them take multiple features as input directly and try to leverage the correlative information across features. Differently, (1) CIB learns action categories according to one feature variable and multiple clusterings other than multiple features; (2) CIB is a consensus extension of original IB, which can capture the essence of consensus clustering and multi-view clustering. From Table 2, the performances of CIB are better than the action clustering methods.

4.4 The Impact of Parameters

Since there are two auxiliary clusterings (C1, C2) in our experiments, we show the impacts of varying parameter λ1 and λ2 on the performance of CIB on different data sets in Figure 3. Set λ1 + λ2 = 1, where λ1 acts on C1, λ2 acts on C2. Then, vary the values of λ1 from 0 to 1, with 0▷1 as the gap between adjacent values. When λ1 = 0, the CIB method only acts on feature variable Y and clustering C2. As we can see from Figure 3, we get the following observations:

• ÷ The performance of CIB fluctuates to some extent according to the trade-off parameters. When λ1 varies from 0 to 1, the value of λ2 varies from 1 to 0 correspondingly. However, the AC values of CIB change in small range on all the five data sets in Figure 3. That is to say the proposed algorithm is not sensitive to the trade-off parameters.
• ÷ Except two values on Weizmann data set, the performance of CIB is always better than the best results of original IB on individual feature. This phenomenon demonstrates that the CIB method can cope with feature variable and auxiliary clusterings effectively and it is relatively easy to choose the trade-off parameters.

4.5 Convergence of CIB algorithm

Figure 4 shows the repetitions of CIB on UCF50 and HMDB data set. We observe that the values of objective function 6 increase monotonically with each repetition and 14 iterations are enough for convergence.

5 Conclusions

In this paper, a novel and effective Consensus Information Bottleneck (CIB) method has been introduced for learning action categories from feature variable and auxiliary clusterings simultaneously. CIB adopts maximization of mutual information to measure feature and clusterings, which can solve the overreliance of consensus clustering on existing base clusterings. Therefore, the compressed results can reflect the hidden patterns by multiple cues. The experiments on five benchmark human action data sets have confirmed the effectiveness of the proposed CIB algorithm. Our further work will focus on incorporating heterogeneous features into the CIB approach, and applying it to more difficult tasks, such as action and scene categorization on large-scale data.