Incomplete Multi-View Weak-Label Learning

1 Introduction

In many real-world applications, a sample may have several heterogenous representations, each one giving a different view of the data, and may also have multiple labels. For example, a web image can be tagged with multiple topics given as labels, such as cattle, grass, and tree. At the same time, the image can also be described using heterogenous features, such as texture descriptors, shape descriptors, color descriptors, surrounding texts, and so on. Multi-view multi-label learning, as a natural formulation for this type of data, has attracted a lot of attention in machine learning and in many application domains [Liu et al., 2015; Luo et al., 2015]. Although many multi-view multi-label learning methods have been proposed in recent years, a main challenge remains for this problem: the lack of fully labeled training samples. In practice, it is rather difficult to collect all the relevant labels of a sample, and only a subset may be available. One such example is image annotation. An annotator may only afford to annotate an image with some labels, especially when the number of relevant labels is large. Learning from partially labeled samples is termed as the weaklabel learning problem [Sun et al., 2010; Bucak et al., 2011; Kong et al., 2014]. Several weak-label learning methods have been proposed in single-view [Yu et al., 2014; Cabral et al., 2015] and multi-view scenarios [Zhang et al., 2013].

∗Guoxian Yu is the corresponding author.

However, almost all aforementioned methods do not account for another important challenge: incomplete data. Namely, some samples may be missing their representation in one view. This can happen, in practice, for a variety of reasons, e.g., a temporary failure of sensors, or a man-made error. It has been observed that incomplete data are likely to lead to degradation in multi-view learning performance [Xu et al., 2015a].

The more challenging case is when both missing labels and incomplete data co-exist in a multi-view multi-label learning problem. To the best of our knowledge, few studies exist that handle incomplete data [Xu et al., 2015a] or missing labels [Zhang et al., 2013] in multi-view learning, but no previous work simultaneously takes into account both issues. To bridge this gap, we propose a novel unified model, called incomplete Multi-ViewWeak-Label Learning (iMVWL), to jointly handle incomplete views and missing labels. The basic strategy of iMVWL is to seek a shared subspace across heterogenous incomplete views, and a robust weak-label classifier in this subspace in a unified learning framework, where label correlations and discriminative information can be learned. In summary, our main contributions are as follows:

• The proposed iMVWL can jointly address incomplete views and missing labels. It learns a shared subspace from incomplete views with weak labels, label correlations, and a predictor in this subspace simultaneously.
• We develop a solution to iteratively optimize our model, avoiding suboptimal problems.
• Experiments on five widely used datasets and comparisons with a number of competitive methods [Yuan et al., 2012; Zhang et al., 2013; Xu et al., 2015a; Liu et al., 2015] demonstrate the superiority of the proposed work.

2 RelatedWork

This work is related to two branches of studies, weak-label learning and multi-view learning. Weak-label learning was pioneered by [Sun et al., 2010]. Many weak-label learning algorithms have subsequently been proposed. To name a few, weak-label learning algorithms under a supervised setting [Bucak et al., 2011; Kong et al., 2014], under a semi-supervised setting [Zhao and Guo, 2015; Wu et al., 2015], and under a multi-instance multi-label framework [Yang et al., 2013].

Multi-view learning deals with data represented in different views and has attracted increasing interest in recent years. Previous approaches have considered multi-views in conjunction with semi-supervised learning [Xu et al., 2015a; Nie et al., 2017], with multi-label learning [Zhang et al., 2013; Liu et al., 2015] or with active learning [Wang and Zhou, 2010]. Others tried to estimate a latent subspace by assuming that samples (in different views) corresponding to the same object are close to each other when mapped into the latent subspace [Zhang et al., 2013; Liu et al., 2015; Xu et al., 2017].

Almost all previous weak-label learning studies focus on a single-view setting. Likewise, almost all existing multi-view learning studies typically assume completeness of each view (i.e., each sample appears in all views). The only exceptions are LabelMe [Zhang et al., 2013] and MVL-IV [Xu et al., 2015a]. LabelMe is a multi-view weak-label learning method, but it assumes complete views of each training sample. As discussed above, this assumption is often violated in practice. MVL-IV is a recently proposed multi-view learning solution that considers incomplete views. It integrates multiple incomplete views by assuming that the views are generated from a common subspace, so that the learned subspace may capture cross-view relationships. Nevertheless, MVL-IV is an unsupervised subspace learning approach, which may be lacking discriminative ability due to missing label information [Xu et al., 2017]. On the other hand, MVL-IV assumes the available labels of training samples are complete, ignoring the widely witnessed weak-label scenarios. Moreover, MVL-IV decouples the subspace learning from the follow-up classification learning tasks, which may result in suboptimal models due to the lack of mutual adaptation of the two steps.

To address these challenges, this paper proposes a novel unified framework (iMVWL) to jointly handle incomplete views and weak labels. iMVWL simultaneously learns the shared subspace from incomplete views, a predictor in this subspace, and local label structure. iMVWL not only achieves a discriminative shared subspace from incomplete views, but also a robust weak-label classifier that can dynamically capture local label correlations. To the best of our knowledge, no previous work has been developed to jointly handle challenges from both incomplete views and weak labels.

3 Proposed Approach

Suppose X = {Xv}nv v=1 represents a dataset with n samples and nv views, where Xv = [x1v , x2v , ..., xnv ] ∈ Rn×dv indicates the full feature space in view v. Y = [y1, y2, ..., yn]T ∈ {-1, 1}n×c is the corresponding weak-label matrix, where yi ∈ {-1, 1}c is the label vector of xi and c is the number of distinct labels. yic′ = 1 (c′ = 1, ..., c) means the c′ -th label is relevant, while yic′ = -1 does not provide any information. In the multi-incomplete view setting, a sample may appear in some views, but not all. That is, the data matrix Xmay have a number of missing rows. An easy fix to this problem is to remove any sample missing in at least one view. However, this approach will significantly reduce the number of samples that can be used for training. Our goal is to predict the labels of unlabeled samples based on multiple incomplete feature spaces X and the weak-label space spanned by Y.

3.1 ProblemFormulation

With multi-view multi-label data, how to generate a shared discriminative subspace across views and how to train an efficient and robust multi-label classifier in that subspace for label prediction are two challenging problems. Some subspace learning algorithms have been proposed to seek the shared subspace across views [Zhao et al., 2017], such as multi-view subspace learning methods based on a low rank constraint [Liu et al., 2015], matrix factorization [ ˇZitnik and Zupan, 2015], and nonnegative matrix factorization (NMF) [Wang and Zhang, 2013]. Among them, NMF has been successfully applied in text mining, image annotations, bioinformatics, recommender systems and other domains [Wang and Zhang, 2013], since most data matrices are naturally nonnegative, or can be easily transformed into nonnegative ones. The major difference between NMF and other matrix factorization methods, such as SVD (singular value decomposition), is the nonnegative constraints, which help to obtain a part-based representation as well as to enhance interpretability of the learned subspace. In this paper, we also focus on nonnegative data matrix mining tasks, and adapt NMF to learn a discriminative low-rank representation from incomplete views by using weak-label information. Given a multi-view datasets X , the standard NMF can be adapted to find a shared subspace V as follows:

where Uv ∈ Rdv×k , V ∈ Rn×k , and k is the desired low-rank size, ||.||F represents the Frobenius norm, Uv ≥ 0 and V ≥ 0 are the nonnegative constraints for the matrices. The learned subspace V in Eq. (1) can capture the cross-view relationships since it enables the integration of complementary information across multiple views [Xu et al., 2015a]. In many applications, however, Eq. (1) may be unreliable due to the presence of incomplete views. A remedy for Eq. (1) to deal with this problem is to fill the missing samples with average feature values; nonetheless, this approach may introduce errors, especially when the number of missing samples is large, hence not suitable for incomplete view setting. Besides, the above unsupervised subspace learning process is lacking discriminative ability because it ignores label information. To address these drawbacks, we formulate subspace learning from incomplete views as a supervised approach, which considers label information and complementary information across incomplete views as follows:

where ⊙ is the Hadamard product (element-wise product). Ov ∈ Rn×dv is an indicator matrix that denotes the missing entries, where Ovi,j = 1 if (i, j) is an observed entry in Xv; Ovi,j = 0, otherwise. Y ∈ Rn×c denotes the available label matrix of n samples. W ∈ Rk×c is the coefficient matrix, which maps the shared feature subspace into a semantic label space. In Eq. (2), we can achieve two goals. On one hand, the learned subspace can capture the cross-view relationships as discussed before. On the other hand, we can utilize the label information Y to induce the shared subspace towards a semantic label space via the second term, which not only helps to obtain a discriminative subspace but also may alleviate the widely spread semantic gap [Datta et al., 2008] between the input heterogeneous feature spaces and the semantic label space, since V can be viewed as a bridge between them.

Eq. (2), however, ignores another important issue in multiviewweak-label learning, i.e., the presence of missing labels. Namely, often in practice, Y is incomplete and contains many missing entries. As such, we need to avoid the influence of missing labels in Y and improve the robustness of Eq. (2). Considering that label correlation is very important in weaklabel setting and usually can further improve the performance [Dong et al., 2018], we leverage label correlation among weak labels to estimate the predicted likelihood scores and extend Eq. (2) as follows:

where M ∈ Rn×c is an indicator matrix for missing labels: Mi,j = 1 if (i, j) is an observed entry in Y; Mi,j = 0, otherwise. S ∈ Rc×c denotes the label correlation matrix, α > 0 is the trade-off parameter. By incorporating the label correlation matrix S, Eq. (3) not only can estimate the predicted likelihood scores, but also can enhance the discriminative ability of the learned subspace by using label correlations among weak labels. However, since the observed relevant label sets of samples are incomplete, we cannot directly compute the label correlation matrix S from prior knowledge Y; we need to learn it. In addition, we also need to account for the fact that label correlations are naturally local [Huang and Zhou, 2012], and can manifest as direct or indirect dependencies [Wu et al., 2015]. As such, it is reasonable to assume that label correlations are locally structured, that is, there exists a subset of labels, which are closely related to each other through complex correlations, and are independent from the rest. This local structure typically implies a low-rank structure of S, which is common in real-world applications [Xu et al., 2015b; Xu et al., 2016]. To capture local label correlations, we add a low-rank constraint on S, and make Eq. (3) more suitable for weak-label problems as follows:

where β is the trade-off parameter, which balances the relative importance of the low-rank constraint on S. By adding the rank term, our model can capture local label correlations among weak labels which is more suitable for real-world applications. It's worth noticing that the work in [Xu et al., 2015b] also makes a low-rank assumption among labels, but its usage is different. In particular, the authors in [Xu et al., 2015b] multiply the low rank correlation matrix with Y to replenish missing labels. In contrast, we use the low rank correlation matrix with the predicted likelihood label vectors. As such, since the estimated label correlation values may not be very reliable in practice, our method is less impacted by them. Furthermore, since V is the low-rank feature representation learned across incomplete views, Eq. (4) is robust to outliers and background noise that may affect the feature space. The rank minimization problem is NP-hard. Here we can relax the rank problem using the nuclear norm || · ||∗ [Cand` es and Recht, 2009], and reformulate Eq. (4) as follows:

Eq. (5) considers cross-view relationships and local (low rank) label structure. In addition, it absorbs label information to induce the shared subspace and enhance its discriminative power. Another advantage of our model is that it jointly learns a shared subspace from incomplete views with weak labels, the local label structure, and the predictor in this subspace. This unified model reinforces their reciprocal effects and thus further improves the performance.

4 Optimization

The minimization problem in Eq. (5) is defined with respect to {Uv}vv=1 , V, W and S. Since a close-form solution cannot be computed, we develop an alternative optimization method to optimize the objective function.

(I). Keep {Uv}, V and S fixed, update W

When {Uv}, V and S are fixed, we have the following e-

quation for W by taking the derivative of Eq. (5) w.r.t. W,

We can derive the following fixed-point updating rule for W,

(II). Keep {Uv}, V and W fixed, update S

When {Uv}, V and W are fixed, optimizing Eq. (5) with respect to S is equivalent to

Eq. (8) can be viewed as a matrix completion problem [Cand` es and Recht, 2009], and many algorithms have been proposed to solve this problem in recent decades. Here we adopt an efficient speedup algorithm, Maxide [Xu et al., 2013], to solve it. Maxide only needs to estimate a c × c matrix.

(III). Keep {Uv}, W and S fixed, update V

When keeping {Uv}, W and S fixed, we obtain the following equation for V by taking the derivative of Eq. (5) w.r.t. V:

Using the Karush-Kuhn-Tucker (KKT) condition [Boyd and Vandenberghe, 2004], we can derive the following updating rule,

(IV). Keep {V}, W and S fixed, update Uv

With {V}, W and S fixed, the computation of Uv is independent fromUv′ , v′ ̸= v. Thus, for each view v, we obtain the following equation for Uv by taking the derivative of Eq. (5) w.r.t. Uv:

Using the KKT condition, we can derive the following updating rule:

4.1 Complexity Analysis

The time complexity of iMVWL is dominated by matrix multiplication. In each iteration, the time complexities of solving W and S in Eq. (7) and Eq. (8) are O(nck) and O(rc lnc lnn) respectively, where r is the rank of S; the time complexity of updating V in Eq. (10) and Uv in Eq. (12) is less than O(nv(nkdmax + 2nk2 + nck)) and O(nv(nkdmax+dmaxk2 )), respectively. dmax represents the largest dimensionality of the views. Since n ≫ k and n ≫ c, the overall time complexity of iMVWL is O(tnvnkdmax), where t is the number of iterations to reach convergence. In practice, t does not exceed 60. In our study, some of the views have sparse feature matrices; as such, the actual time cost of the above operations can be further reduced.

5 Experiments

5.1 Experimental Setup

The five multi-view datasets used in the experiments (Core15k, Pascal07, ESPGame, IAPRTC-12, and Mirflicker) are summarized in Table 1. These datasets 1 are obtained from [Guillaumin et al., 2010], and each is represented by six feature views: HUE, SIFT, GIST, HSV, RGB, and LAB. For each dataset, we randomly sample 70% of the data for training, and use the remaining 30% data for testing (unlabeled data). Moreover, to create weak-label scenarios, we follow the protocol given in [Xu et al., 2013]: for each label c′ we remove the assignment of c′ for ω% randomly sampled positive and negative training samples (c′ becomes a missing label); to create incompleteview data scenarios, we randomly remove ε% samples from each view, while ensuring each sample appears in at least one view. For each dataset, dmin represents the minimum dimensionality of the different views.

Methods: We compare iMVWL against four state-of-theart methods: LabelMe [Zhang et al., 2013], MVL-IV [Xu et al., 2015a], lrMMC [Liu et al., 2015], and iMSF [Yuan et al., 2012]. The first two methods have been introduced in the Related work Section. lrMMC is a matrix completion based multi-view learning method, but it assumes complete views of each training sample and does not explicitly consider missing labels and label correlations. iMSF was initially proposed for single label classification with multiple incomplete sources; we extend it for multi-label classification by training multiple classifiers (one for each label). These comparing methods cannot directly handle incomplete multi-view weak-label settings. For experimental comparisons, we adapt LabelMe and lrMMC by filling missing features with average values, and set the missing labels of MVL-IV and iMSF as negative labels. In addition, we introduce iMVWL-Sp, iMVWL-X, and iMVWLNc to investigate the contribution of learning a discriminative shared subspace, separately handling multiple feature views, and capturing local label correlations, respectively. iMVWLSp excludes label information during the subspace learning process. iMVWL-X concatenates multi-view features into a single vector. iMVWL-Nc excludes label correlations. Fivefold cross validation on the training set is used to select the optimal parameter values for each competitive method. Optimal parameters for the competitive methods are selected as suggested in the corresponding papers. For our method, we selected the parameters α and β from {10i |i = -5, · · · , 0}. Experimental results show that iMVWL yields relatively stable performance with α around 10-2 and β around 10-2 , and therefore we use these values. All the experiments are repeated ten times, and both the average and standard deviation are reported. The source code of iMVWL is publicly available at http://mlda.swu.edu.cn/codes.php?name=iMVWL.

1 Available at http://lear.inrialpes.fr/people/guillaumin/data.php

Evaluation: Four widely used multi-label evaluation metrics are adopted for performance comparisons, i.e., Ranking Loss (RL), Average Precision (AP), Hamming Loss (HL), and adapted AUC. A formal definition of the first three metrics can be found in [Zhang and Zhou, 2014]. The adapted AUC is suggested in [Bucak et al., 2011]. To maintain consistency with other evaluation metrics, in our experiments, we report 1-RL instead of RL. Thus, as for other metrics, the higher the value of 1-RL, the better the performance is.

5.2 Results On All Datasets

Table 2 and 3 give the results of all methods on five datasets across four evaluation metrics. In the table, ·/◦ indicates whether iMVWL is statistically (using a pairwise t-test at 95% significance level) superior/inferior to the corresponding method.

It can be seen that iMVWL outperforms the other methods in most cases. MVL-IV, iMSF, and iMVWL are all designed for incomplete multi-view data, but iMVWL almost always outperforms the other two across the four evaluation metrics. The main reason is that MVL-IV and iMSF assume that the available labels are complete and ignore the widely witnessed weak-label scenarios. Both lrMMC and LabelMe are multiview learning methods based on subspace learning, and they can handle weak-labels. But LabelMe is outperformed by lrMVL across five datasets. A possible reason is that lrMMC considers the multi-view weak-label learning task as a matrix completion problem, which is more robust to missing values. However, lrMMC is outperformed by iMVWL in many cases. This is mainly because lrMMC assumes the completeness of multiple views. As discussed in the Introduction section, this assumption is often violated in practice.

Table 3: Results of variants of iMVWL on all datasets with ω% = 50%, ε% = 50%, and k = 0.5dmin.

In Table 3, iMVWL-Sp is a degenerate case of iMVWL, which is obtained by excluding label information during subspace learning, thereby isolating the subspace learning process from the subsequent classification task. iMVWL almost always performs better than iMVWL-Sp on these datasets. This is mainly because in iMVWL-Sp the learned subspace may lack the ability to discriminate between different labels. In addition, when the objectives are treated separately, an optimal subspace can be achieved, but it may not be optimal for the subsequent prediction. These results corroborate our motivation to jointly optimize the two objectives. iMVWLNc is obtained from iMVWL by excluding label correlations, and is almost always outperformed by iMVWL. This fact demonstrates the effectiveness of the proposed method in capturing local label correlations. iMVWL-X is another variant of iMVWL; it concatenates all feature view vectors into a single vector, and follows the same process of iMVWL for prediction. It's outperformed by iMVWL in almost every case. These results justify the rationale of handling multiple feature views separately.

An interesting observation is that iMVWL-Sp performs better than (or comparable to) other methods in most cases. This is mainly because iMVWL-Sp addresses both incomplete multi-view and weak-label problems, while the other methods only address one of the two. The performance margin achieved by iMVWL and iMVWL-Sp further justifies our motivation to jointly handle incomplete multi-view data and weak-labels.

5.3 HandlingWeak-Labels

We conducted additional experiments on Core15k to investigate the performance of iMVWL and other methods when handling missing labels. We set the dimensionality of the shared subspaces equal to 20%, 50%, and 80% of dmin, with ω% that varies from 0% to 50% with a step-size of 10%. Since iMSF is not a subspace learning method, its performance is the same for all dimensionality. Since the results on all evaluation metrics are similar, for space limitation, we report only the results of AUC in Figure 1.

We can see that the performance of all the methods decreases when ω% increases, and iMVWL outperforms the competitive methods in all the settings. Also, regardless of the dimensionality of the learned subspaces, iMVWL performs consistently better than the other methods under different ratios of missing labels.

5.4 Handling Incomplete Multi-ViewData

We also performed experiments to investigate the impact of different percentages (ε%) of incomplete views on the performance of various methods. Similarly to previous experimental protocols, we set the dimensionality of the learned subspace equal to 20%, 50%, and 80% of dmin, and then increase the percentage of incomplete views ε% from 0% to 50% with a step-size of 10%. Due to space limitation, we report only the results for ε% equal to 0%, 30%, and 50% in Figure 2. The performance trend for ε% equal 10%, 20%, and 40% is similar to those reported in Figure 2.

It can be seen that the performance of all the methods decreases with the increasing of ε%, and iMVWL gives the best performance in all the cases. In addition, as the dimensionality (k) of the shared subspace increases, the performance of all the methods shows an increasing trend, but iMVWL still performs consistently better than the competitors, under the different percentages of incomplete views.

5.5 Parameter Analysis

In this section, we test the sensitivity of iMVWL w.r.t. α and β. The tested range for α and β is {10i |i = -5, · · · , 0}. For brevity, we only report the 1-RL and AUC results on Core15k in Figure 3; similar results were obtained for the other datasets as well.

From the Figure, we can see that iMVWL achieves relatively stable and good performance when α ≈ 10-2 and β ≈ 10-2 . We also observe that when α = 10-5 or β = 10-5 , iMVWL has reduced 1-RL or AUC. This result confirms the contribution of weak-label information and local label correlation in improving the performance of iMVWL. When α or β are close to one, the AUC and 1-RL sharply decrease. This is because large values of α (or β) overweight the effect of weak-label information in subspace learning (or local label correlations), while underweighting the shared subspace V, which encodes cross-view relationships.

5.6 Runtime And Convergence Analysis

We also study the runtime cost of the competing methods on the five datasets, and report the costs in Table 4. The experiments are conducted on CentOS 6.9 with Inter(R) Xeon E5-2678, 64GB RAM and MATLAB 2013a. We can see that iMVWL runs much faster than other comparing methods in most cases. The only exception is lrMMV on ESPGame and IAPRTC-12 datasets. This is mainly because lrMMC needs to estimate a target matrix of size n×k just once, while iMVWL has to estimate the label correlation matrix of size c × c in each iteration. As a result, when c is large, iMVWL costs more. These results corroborate the efficiency of the proposed method. The convergence trends on the other datasets are similar.

Figure 4 shows the convergence curve of iMVWL on Core15k and Pascal07 datasets. As we can see, on both datasets, iMVWL tends to converge after 60 iterations. The convergence trends on the other datasets are similar.

6 Conclusion

In this paper, we propose a novel model called iMVWL to learn from data with incomplete views and missing labels. iMVWL learns a discriminative shared subspace from incomplete views with weak labels. At the same time, it learns a robust weak-label classifier in the subspace and the local label structure. An alternative optimization solution is developed to optimize this model, which not only can avoid suboptimal problems, but also reinforces the reciprocal effects of the shared subspace and of the classifier, and further improves the performance. The experimental results show that iMVWL outperforms other competitive methods. How to further improve the efficiency of iMVWL is an interesting future pursue.

Acknowledgments

This work is supported by NSFC (61741217, 61402378 and 61732019), Open Research Project of Hubei Key Laboratory of Intelligent Geo-Information Processing (KLIGIP2017A05).