Incomplete Multi-Modal Visual Data Grouping

1 Introduction

In recent years, a large volume of techniques emerge in artificial intelligence field thanks to the easy accessibility of multimodal data captured from multiple sensors [Cai et al., 2013; Zhao and Fu, 2015; Zhang et al., 2015; Liu et al., 2016]. Working in an unsupervised manner, multi-modal grouping (or clustering) offers a general view of the heterogeneous data grouping structure, which has been drawing extensive attention [Bickel and Scheffer, 2004; Ding and Fu, 2014; Blaschko and Lampert, 2008; Chaudhuri et al., 2009; Fred and Jain, 2005; Singh and Gordon, 2008; Cao et al., 2015]. While beneath the prosperous studies of the multi-modal data grouping problem, there is an underlying problem, i.e., when the data from one modality/more modalities are inaccessible because of sensor failure or other reasons, most methods mentioned above would inevitably degenerate or even fail.

In this paper, we focus on this challenging, i.e., Incomplete multi-modality Grouping (IMG) problem.

To solve IMG problem, a natural thought is to reuse the existing techniques by remedying the incomplete data. In [Li et al., 2014], two strategies are applied to facilitate to fit IMG problem, i.e., remove samples suffering from missing information or preprocess the incomplete samples to fill in the missing information. Obviously, the first strategy changes the number of samples, which essentially disobeys the goal of the original problem. The second strategy has been experimentally tested to be not good enough [Shao et al., 2015].

Most recently, there are few attempts proposed to solve IMG problem. [Li et al., 2014] proposed a pioneer work to handle two-modal incomplete data case, by projecting the partial data into a common latent subspace via nonnegative matrix factorization (NMF) and `1 sparse regularizer. Following this line, a similar idea of weighted NMF and `2↪1 regularizer was proposed in [Shao et al., 2015]. However, both methods [Li et al., 2014; Shao et al., 2015] overlook the global structure over the entire data samples.

Inspired by this, we propose a novel method integrating the latent subspace generation and the compact global structure into a unified framework as shown in Figure 1. More specifically, a novel graph Laplacian term coupling the complete visual data samples is introduced in latent space, where the similar samples are more likely to be grouped together.

Compared with the existing approaches, the contributions of our method are three folds:

• We propose a novel method to deal with IMG problem for visual data with the consideration of the compact global structure in the low-dimensional latent space. The practice is achieved through a Laplacian graph on complete data instances, bridging the complete-modal samples and partial-modal samples.
• Nontrivially, we provide the optimization solution to our proposed objective, where three auxiliary variables are introduced to make the optimization of the proposed graph Laplacian term happen under the incomplete multi-modality setting.
• The superior results on six datasets, i.e., one synthetic and four visual datasets, validate the effectiveness of the proposed method. Specifically, when data suffer from large incompleteness, we raise the NMI performance bar by more than 30% and 10% for the synthetic and realworld visual data, respectively.

2 Method

We start with the introduction of some basic operator notations used in this paper. tr(·) is the operator to calculate the trace of matrix. hA↪Bi is the inner product of two matrixes calculated as tr(ATB). k · k2F denotes the Frobenius norm. Operator (A)+ works as max(0↪A) to make the matrix (or vector) non-negative. Other variable and parameter notations are introduced later in the manuscript.

2.1 Incomplete multi-modality Grouping

For the ease of discussion, we use two-modal case for illustration. Given a set of data samples X = [x1↪ ▷ ▷ ▷ ↪ xi↪ ▷ ▷ ▷ ↪ xN]↪ i = 1↪ ▷ ▷ ▷ ↪N, where N is the total number of samples. Each sample has two modalities, i.e., xi = [x(1) i ↪ x(2) i ]. For IMG problem, we follow the setting in [Li et al., 2014], the input data is separated as an incomplete modal sample set ˆX = ¶ ˆX(1↪2) ↪ ˆX(1) ↪ ˆX(2) ♦ instead of the complete multi-modal data X, where ˆX(1↪2) , ˆX(1) , and ˆX(2) denote the data samples presented in both modalities, modal-1 and modal-2, respectively. The feature dimensions of modal-1 and modal-2 data are d1 and d2, and the numbers of shared samples and unique samples in modal-1 and modal-2 are c, m and n, respectively. Accordingly, we have ˆX(1↪2) 2 Rc⇥(d1+d2) , ˆX(1) 2 Rm⇥d1 , ˆX(2) 2 Rn⇥d2 , N = c +m+ n . Same as traditional multi-view clustering, the goal of IMG is to group the samples into their corresponding clusters.

Previous methods, like MultiNMF [Liu et al., 2013] and PVC [Li et al., 2014], pursuit a common latent space via nonnegative matrix factorization (NMF) where samples from different views can be well grouped. In this work, we follow this line to find a latent common subspace for heterogenous multi-modal visual data. However differently, we get rid of the non-negative constraint to make the optimization much easier. Besides, the major contribution of this paper is to demonstrate the correctness and effectiveness of the proposed global constraint in IMG problem.

Given the latent dimension of projective subspace k, we denote P (1) c 2 Rc⇥k and P (2) c 2 Rc⇥k as the latent representations of ˆX(1↪2) = [X(1) c ;X(2) c ] from two different modalities. Note that X(1) c and X(2) c are the samples existing in both modalities, thus P (1) c and P (2) c are expected to be close, i.e., P (1) c ! Pc P (2) c . Consequently, we have the basic incomplete multi-modality grouping formulation as

where λ is a trade-off parameter, Pc is the shared latent representation from X(1) c and X(2) c , U (1) 2 Rk⇥d1 , U (2) 2 Rk⇥d2 are known as the bases in matrix decomposition, ˆ P (1) 2 Rm⇥k , ˆ P (2) 2 Rn⇥k are the latent low-dimensional coefficients for missing modal samples corresponding to ˆX(1) and ˆX(2) . Regularizers kU (1) k2F and kU (2) k2F are used to prevent the trivial solution.

2.2 Complete Graph Laplacian

By concatenating the projective coefficients in latent subspace P = [Pc; ˆ P (1) ; ˆ P (2) ] 2 RN⇥k , we can directly apply clustering method on P to get the cluttering result. However, it is deserved to know that the learned coefficients P is without global property which is crucial in subspace clustering. For the traditional multi-modality learning problem, global constraints are easy to be incorporated because of the complete modality setting, such as low-rank constraint in [Ding and Fu, 2014]. While in IMG problem, this cannot be easily achieved. To tackle this, we propose to learn a Laplacian graph incorporating all the samples in the latent space.

Integrating the idea of graph Laplacian and Eq. (1) into the unified objective function, we have our formulation with the complete graph Laplacian term G as

Here,

where LA 2 RN⇥N is the Laplacian matrix of similarity matrix A 2 RN⇥N , defined by LA = D - A, in which the degree matrix is the diagonal matrix with Dii = PNj=1 Aij . Several remarks are made here.

Remark 1: Thanks to the graph Laplacian term LA, we bridge the sample connection between complete modal samples and partial modal samples. In such a way, the global constraint on the complete set of data samples is integrated into the objective, which in turn influences the projected coefficients in low-dimensional space with the global structure. The practice of adding a graph term on the complete set of data gives the name of "complete graph Laplacian".

Remark 2: A is the affinity graph, with each element denoting the similarity between two data samples in latent subspace. We normalize each column as the summation equals to 1 as well as all the elements are nonnegative, making A have a probability interpretation. This naturally provides us with an opportunity to do spectral clustering on the optimized A, which none of the existing partial multi-view methods have. Remark 3: As shown in Eq. (4), the regularizers we add are all Frobenius norms for simplicity. According to [Lu et al., 2012], other regularizers such as `1-norm or trace (nuclear) norm are also good choices for preserving the global structure that benefits clustering performance.

2.3 Optimization

As seen in Eq.(2), in order to learn a meaningful affinity matrix in a unified framework, our proposed objective includes several matrix factorization terms, regularizers and constraints. It is obviously not jointly convex w.r.t. all the variables. Instead, we plan to update each variable at a time via augmented Lagrange Multiplier (ALM) with alternating direction minimizing strategy [Lin et al., 2011].

However, it is noted that Pc, ˆ P (1) and ˆ P (2) are difficult to be optimized because of the following reasons: (1) Laplacian graph LA is the graph measuring the affinities among all sample points, that is, we have to update them as a whole; (2) There is no way to directly combine Pc, ˆ P (1) and ˆ P (2) for optimization since ˆ P (1) and ˆ P (2) do not share the same basis, and even the size of input data in modal-1 is not the same as that in modal-2 ([X(1) c ; ˆX(1) ] 2 R(c+m)⇥d1 for modal1, [X(2) c ; ˆX(2) ] 2 R(c+n)⇥d2 for modal-2). This dilemma makes the variables Pc, ˆ P (1) and ˆ P (2) impossible to be optimized individually nor together as P . To solve this challenge, we propose to introduce three auxiliary variables Qc 2 Rc⇥k , ˆQ(1) 2 Rm⇥k and ˆQ(2) 2 Rn⇥k for Pc, ˆ P (1) and ˆ P (2) respectively. In this way, we separately update the affinity matrix A (Laplacian LA) and matrix factorization with the bridges of Pc = Qc, ˆ P (1) = ˆQ(1) and ˆ P (2) = ˆQ(2) .

Correspondingly, the augmented Lagrangian function of Eq. (2) with three auxiliary variables is written as

where Y = [Yc; ˆ Y (1) ; ˆ Y (2) ] is the lagrangian multiplier, and

θ > 0 is a penalty parameter. Specifically, variables P, Q, U (1) , U (2) , A in the ⌧ + 1 iteration are updated as follows:

Update U(1)&U(2) . Fixing P, Q and A, the Lagrangian function w.r.t. U (1) (⌧+1) is written as:

This is a standard least square problem with regularization, with its solution as

Here Ik is the identity matrix with k-dimension. Similarly, we have the following function to update U (2) (⌧+1) :

Update P. This part includes three subproblems, i.e., update Pc(⌧+1), ˆ P (1) (⌧+1) and ˆ P (2) (⌧+1) . For Pc(⌧+1), by fixing other variables, the corresponding Lagrangian function is

With the help of KKT condition that @(C(Pc))◁@(Pc) = 0, we have the following solver for Pc(⌧+1) =:

where R(⌧+1) = 2U (1) (⌧+1)U (1) (⌧+1)T + 2U (2) (⌧+1)U (2) (⌧+1)T + θIk . Similarly, we obtain the solutions for ˆ P (1) (⌧+1) as

and ˆ P (2) (⌧+1) as

Update Q. Recall that the motivation of introducing auxiliary Q = [Qc; ˆQ(1) ; ˆQ(2) ] is to bridge the gap of global representation of all the data samples in different modalities. Therefore, instead of individually updating Qc(⌧+1), ˆQ(1) (⌧+1) and ˆQ(2) (⌧+1) . We update Q(⌧+1) as a whole, with the Lagrangian function written as

Correspondingly, the solver of Q(⌧+1) via KKT condition is

where IN is the identity matrix with N-dimension.

Update A (LA). Fixing other variables, the graph Aproblem is in the following form

As discussed in Remark 2, A has the probability interpretation with each element considered as the similarity probability between two data samples. Therefore, we divide problem (15) into a set of subproblems Ai(⌧+1) according to sample index i as

where Si (⌧+1) is a column vector with its element j defined as Sij (⌧+1) = βkQi(⌧+1) -Qj(⌧+1) k2F 4γ . A detailed deduction can

be found in [Guo, 2015].

To sum up, for the complete algorithm, we initialize the variables and parameters (in the iteration #0, denoted as "⇤(0)") in ALM as follows: penalty parameter θ(0) = 10-3 , ⇢ = 1▷1, the max penalty parameter θmax = 106 , stopping threshold ✏ = 10-6 , P(0) = Q(0) = Y(0) = 0 2 RN⇥k , Pc(0) = Qc(0) = Yc(0) = 0 2 Rc⇥k , ˆ P (1) (0) = ˆQ(1) (0) = ˆ Y (1) (0) = 0 2 Rm⇥k , ˆ P (2) (0) = ˆQ(2) (0) = ˆ Y (2) (0) = 0 2 Rn⇥k , U (1) (0) = 0 2 Rk⇥d1 , U (2) (0) = 0 2 Rk⇥d2 , A(0) = LA(0) = 0 2 RN⇥N . Then we update each variable one by one as discussed above until convergence.

2.4 Complexity Analysis

Note that with different partial example ratios, the dimensions of ˆX(1↪2) , ˆX(1) and ˆX(2) are different, i.e., c↪ m↪ n vary. For simplicity, we consider the extreme case that no incomplete data exist, that is, complete (traditional) multi-view clustering case. The feature dimensions of different modalities are all d. In Algorithm 1, the most time-consuming parts are the matrix multiplication and inverse operations when updating U (1) ↪ U (2) ↪ P↪ Q↪ A. For each iteration, the inverse operations in Eqs. (7)(8)(10)(11)(12) cost O(k3 ) due to the k ⇥ k size matrix. While the inverse on graph in Eq. (14) takes time of O(N 3 ). Usually k ⌧ N, then the asymptotic upper-bound for inverse operation can be expressed as O(N 3 ). The multiplication operations take O(dkN) when updating U (1) ↪ U (2) ↪ P↪ Q. It costs O(N 3 ) when updating A. However, it is noted that the number of operations of O(N 3 ) in each iteration is only 2, the major computations are of order O(dkN). Suppose M is the number of operations consuming O(dkN), L is the iteration time. In sum, the time complexity of our algorithm is O(MLdkN + 2LN 3 ).

3 Experiment

• Synthetic data are comprised of two modalities. We first choose the cluster ci each sample belongs to, and then generate each of the modalities x(1) i and x(2) i from a two-component Gaussian mixture model. Two modalities are combined to form the sample (x(1) i ↪ x(2) i ↪ ci).

We sample 100 points from each modality. The cluster means in modal-1 are θ(1) 1 = (1 1), θ(1) 2 = (3 4), in modal-2 are θ(2) 1 = (1 2), θ(2) 2 = (2 2). The covariance for modal-1 are

• Real-world visual data: (a) MSR Action Pairs dataset [Oreifej and Liu, 2013] is a RGB-D action dataset containing 12 types of activities performed by 10 subjects. Each actor provides 360 videos for each modality. (b) MSR Daily Activity dataset [Wang et al., 2012] contains 16 types of activities performed by 10 subjects. Each actor repeats an action twice, providing 320 videos for each of the RGB and depth channels. For the above two RGBD video sequences, we temporally normalize each video clip to 10 frames with spatial resolution of 120⇥160. Histograms of gradient oriented feature is extracted from both depth and RGB videos with patch size 8⇥8. Thus, a total of 3000 patches are extracted from each video, with the feature dimensionality of 31. We will clarify this in our final version. (c) BUAA NirVis [Huang et al., 2012] contains two types of data, i.e., visual spectral (VIS) and near infrared (NIR) data. The first 10 subjects with 180 images are used. To fasten the computation, we resize the images to 10⇥10, and vectorize them. (d) UCI handwritten digit 1 consists of 0-9 handwritten digits data fromUCI repository. It includes 2000 examples, with one modality being the 76 Fourier coefficients and modal-2 being the 240 pixel averages in 2 ⇥ 3 windows.

For the compared methods, we consider the following algorithms as the baselines. (1) BSV (Best Single View): Due to the missing samples in each modality, we cannot directly perform k-means clustering on each modality data. Following [Shao et al., 2015], we firstly fill in all the missing data with the average features for each modality, and then perform clustering on each modality, and report the best result. (2) Concat: Feature concatenation is a straightforward way to deal with multi-modal data, which serves as our second baseline. Same as BSV, we firstly fill in all the missing data with the average features for each modality, and then concatenate all modal features into one. (3) MultiNMF: Multi-view NMF [Liu et al., 2013] seeks a common latent subspace based on joint NMF, which can be approximately regarded as the complete-view case of PVC. For the synthetic data, there are few data points containing negative values. In order to successfully run the code, we make the input data nonnegative as preprocessing. (4) PVC: Partial multi-view clustering [Li et al., 2014] is one of the most recent works in dealing with incomplete multi-modal data. This work can be considered as our proposed model without the complete graph Laplacian. One important parameter on regularizer λ is chosen from the parameter grid of ¶1e-4, 1e-3, 1e-2, 1e-1, 1e0, 1e1, 1e2♦, including the default 1e-2 used in the original paper.

1 http://archive.ics.uci.edu/ml/datasets.html

For the evaluation metric, we follow [Li et al., 2014], using Normalized Mutual Information (NMI). Besides, precision of clustering result is also reported to give a comprehensive view. Same as [Li et al., 2014], we test all the methods under different partial/incomplete example ratio (PER) varying from 0.1 to 0.9 with an interval of 0.2.

3.1 Experimental Result

For each dataset, we randomly select samples from each modality as the missing ones. Note that our method not only learns a better low-dimensional representation but also learns a similarity matrix among samples iteratively. This naturally gives us two opportunities to do clustering, i.e., k-means clustering on the latent representation P, and spectral clustering on the learned affinity graph A. To make the fair comparison, k-means results on P are reported. For each experiment, we repeats 10 times to get the average performance, the standard deviations are omitted here because it is observed that these values are usually small.

Table 1,2,3 and Figure 2 report the NMI values and precision on synthetic, video and image datasets with different PER ratio settings. From these tables and bar graphs, the following observations and discussions are made.

• The proposed method performs superiorly to the other baselines in almost all the settings; Especially for the challenging synthetic data, we raise the performance bar by around 31▷83% in NMI.
• With more missing modal samples (PER ratio increases), the performance of all the methods drops.
• With more missing modal samples, our method improves more compared with the state-of-the-art baseline. Specifically, our NMI improvement reaches 10▷34%

(PER=0.9) from 4▷58% (PER=0.1) for five real-world video/image datasets.

• For the real-world data, as PER ratio grows, the extent that performance drops is less than that of synthetic data.

Discussion: The first observation experimentally demonstrates that the proposed complete graph Laplacian term works in both synthetic and video/image multi-modal data, especially when some modal data are missing to a large extent. Note that for the matrix factorization part, we use the simplest way with only Frobenius norm regularization on basis matrix. However, we still outperform the competitors with the help of complete graph Laplacian term. With better matrix factorization techniques, e.g. NMF in [Li et al., 2014] or weighted NMF in [Shao et al., 2015], we believe that a better performance will be achieved.

With no doubt, the problem becomes more challenging when the number of shared samples is fewer. However, one may be curious why our method performs much better than others in synthetic data. The possible reason is that compared with modal-1 data, modal-2 data are difficult to separate. When points in modal-1 are missing, the existing methods cannot do a good job with only modal-2 data even in latent space. However, thanks to the affinity graph built on all data points, the data points from different clusters are iteratively pulled towards their corresponding cluster centers by the influence of global constraint. This enlightens us that in real-world multi-modal visual data, if one modal data perform poorly (e.g. people blend in the background visually) than the others, our proposed complete graph Laplacian term is capable to make it up from other discriminative modal data (e.g. discriminative depth information between people and background). One may be also interested in the reason why our method has a considerable improvement when data suffer from a large incompleteness. We believe, as PER ratio increases, the state-of-the-art method PVC degenerates dramatically because the common projection Pc becomes harder to be accurately estimated simply from the less shared multi-modal data. Nevertheless, our proposed complete graph Laplacian remedies the deviation by considering the global structure of incomplete multi-modal data in the latent space, which further leads to a robust grouping structure.

3.2 Convergence Study

To show the convergence property, we conduct an experiment on synthetic data with PER ratio set as 0.3 and parameters ¶λ↪ β↪ γ♦ set as ¶1e-2, 1e2, 1e2♦. The relative error of stop criterion kP⌧ - Q⌧k1 is computed in each iteration. The red curve in Figure 3(a) plots the convergence curve of our model. It is observed that after the first several iterations' bump, the relative error drops steadily, and then meets the convergence at around #40 iteration. The NMI value during each iteration is drawn in black. It can be seen that there are three stages before converging: the first stage (from #1 to #4), the NMI value grows dramatically; the second stage (from #5 to #40), the NMI bumps in a certain range but grows; the final stage (from #41 to the end), the NMI achieves the best at the convergence point.

3.3 Parameter Study

There are three major parameters in our approach, i.e., λ, β and γ. Same as convergence study, we conduct the parameter analytical experiments on synthetic data with PER ratio set as 0.3. Figure 3(b) shows the experiment of NMI result w.r.t. the parameter λ under two settings ¶[β=1e2, γ=1e0]; [β=1e2, γ=1e2]♦. We select the parameter ↵ in the grid of ¶1e-3, 1e2, 1e-1, 1e0, 1e1, 1e2, 1e3♦. It is observed that our method has a relatively good performance when λ is in the range of [1e-3, 1e-1], and drops when λ becomes larger.

The experiments shown in Figure 3(c,d) are designed to test the robustness of our model w.r.t. the trade-off parameters β and γ on the proposed graph Laplacian term. As we observe, the NMIs under different settings reach a relatively good performance when β = [1e-1, 1e0, 1e1] and γ = 1e2.

4 Conclusion

In this paper, we proposed a method dealing with incomplete multi-modal visual data grouping problem with the consideration of the compact global structure via a novel graph Laplacian term. This practice bridged the connection of missing samples data from different modalities. Superior experimental results on synthetic data and four real-world multi-modal visual datasets compared with several baselines validated the effectiveness of our method.

Acknowledgments

This research is supported in part by the NSF CNS award 1314484, ONR award N00014-12-1-1028, ONR Young Investigator Award N00014-14-1-0484, and U.S. Army Research Office Young Investigator Award W911NF-14-10218.