Multi-View Matrix Completion for Multi-Label Image Classification

I Introduction

Multi-label image classification, where multiple labels are assigned to a given image, is useful in many web-based image analytic-based applications. For example, keywords can be automatically assigned to an uploaded web image so that annotated images may be searched directly using text-based image retrieval systems.

Dozens of multi-label algorithms have been proposed in the past decade . However, none of these methods are able to handle missing features, or cases where parts of the training data labels are unknown. Many of the algorithms lack robustness to outliers and background noise. In order to overcome these limitations, matrix completion (MC) has recently been introduced as an alternative methodology for transductive (semi-supervised) multi-label classification . In particular, the MC-based multi-label classification concatenates the feature and label matrices, and then completes the unknown entries (either features or labels) in the concatenated matrix by the use of the rank minimization criterion. In this way, the MC-based methods can be used not only to infer labels of the unlabeled data, but also to estimate values of the missing features, and denoise the observed features and labels.

Although MC-based algorithms are robust for general transductive multi-label classification tasks, they cannot directly handle those image classification problems that include images represented by multi-view features. A popular solution has been to concatenate all the features into a long vector, but this strategy not only ignores the physical interpretations of different features, but also encounters an over-fitting problem given frequently limited labeled training samples and high dimensional image features. Besides, the feature concatenation often leads to a very large matrix to be completed. Thus the time cost is very high and sometimes intolerable .

To avoid these drawbacks, we propose to weightedly combine the MC based classification outputs of different views, and develop a new framework, namely, multi-view matrix completion (MVMC) for handling multi-view features in semi-supervised multi-label image classification. To learn the view combination coefficients, we firstly perform a two-fold cross validation procedure on the labeled set for each view. That is, we divide the labeled training samples into two (usually equal) sets. Labels in one set are assumed to be unknown and are completed using the label information in the other set. In fact the labeled training samples have been annotated, and thus we propose to linearly combine the predicted labels of all the views to approximate the ground-truth labels. In this way, we learn the combination coefficients of different views. In the learning of the coefficients, we propose to directly optimize average precision (AP), which is a critical criterion in evaluating a multi-label classification algorithm. We also present a formulation that adopts the least squares (LS) loss, which is quite efficient although not so proper as the AP loss for multi-label classification. Finally, for each view, the labels of the unlabeled and test data are predicted using matrix completion, and the obtained predictions of all the views are combined using the learned coefficients. The proposed algorithms tend to assign higher weight to the view carrying more discriminative information, and thus explore the complementary nature of different views.

In order to evaluate our MVMC algorithms (MVMC-LS and MVMC-AP), we have used two challenging datasets, PASCAL VOC’ 07 and MIR Flickr . To the best of our knowledge, there are no other algorithms which employ multi-view matrix completion. Therefore, in order to assess performance, we first compared our algorithms with the best single view (BMC), concatenation of all the views (CMC), and average the outputs of different views (AMC) in terms of mean average precision (mAP), mean area under the ROC curve (mAUC) and hamming loss (HL). To further verify the effectiveness of MVMC, we compared MVMC-AP with some popular and competitive feature-level and classifier-level multi-view approaches, as well as some competitive multi-label classification methods . The experimental results show that our novel approach outperforms the current state-of-the-art.

The main contributions of this paper are: 1) the cross validation strategy that learns the view combination coefficients in the proposed multi-view matrix completion framework for multi-label image classification; 2) the developed solutions for the constrained optimization problems with the AP loss, as well as the LS loss. The former is particular suitable for multi-label classification, and the latter is for the sake of efficiency; 3) the robustness analysis of the AP loss compared with the LS and hinge loss in MVMC.

The rest of the paper is organized as follows. We firstly review some related work on matrix completion and multi-view learning in Section II. Section III summarizes the recent work on utilizing matrix completion for transduction and multi-label classification. In Section IV, we present the proposed MVMC framework, as well as the MVMC-LS and MVMC-AP algorithms by choosing different loss functions. Moreover, the robustness of the different algorithms is analyzed. The experimental results are presented in Section V. Finally, we conclude this paper in Section VI and prove the main theorem of this paper in Section VII.

II Related Work

To recovery a low-rank matrix corrupted with arbitrary large errors, a combination of the nuclear norm and the $l_{1}$-norm should be minimized. Lin et al. extended the classical augmented Lagrange multipliers (ALM) for solving this minimization problem efficiently. In particular, the exact ALM (EALM) method proposed in was proved to have a pleasing convergence speed. The improved version, inexact ALM (IALM), was shown to be more precise and much faster than the state-of-the-art solvers, such as the accelerated proximal gradient (APG) algorithm . Recently, matrix completion was introduced for transductive (semi-supervised) multi-label learning and we will depict it in section III.

II-B Multi-view learning

Multi-view learning is an active research topic in recent years. The multiple views can be the different viewpoints of an object in the camera, or the various descriptions of a given sample. We focus on the latter in this paper, and the goal is to learn to fuse the different descriptions. Lots of methods have been proposed in the recent decades for multi-view classification , retrieval , clustering , etc. In this section, we mainly review the classification methods , although most of them are also amenable for other applications. According to the level of the fusion being carried out, the multi-view classification methods can be grouped into two major categories: feature-level fusion and classifier-level fusion. We further divide them into four sub-categories: similarity fusion and unified subspace learning for the feature level, output/decision fusion and interactive fusion for the classifier level.

A direct strategy for feature-level fusion is to concatenate the different kinds of features into a long vector. This often leads to the curse of dimensionality problem and thus it is not practical. To this end, many sophisticated techniques are developed, which include those similarity space fusion (mostly kernel fusion by now) and multi-view subspace learning approaches.

Similarity space fusion: As far as we know, most of the current works on similarity space fusion are implemented in the form of kernel fusion. Multiple kernel learning (MKL) is one of the most representative framework for kernel fusion. For example, in , a combination of different kernels built on different features sets were utilized for protein prediction. MKL was also used for dimensionality reduction of the multi-view data based on graph embedding . McFee and Lanckriet presented a method to combine multiple kernels in a proposed partial order embedding algorithm. The method learns a set of kernel mappings to induce a unified multi-modal similarity space, where the human perceptual information expressed by relative comparisons is incorporated. Kloft et al. extended the traditional $l_{1}$-norm MKL to arbitrary norms, and showed that the non-sparse MKL was superior to the state-of-the-art in combining different feature sets for biometrics recognition.

Unified subspace learning: In the feature-level fusion, another set of algorithms is on multi-view subspace learning. Canonical correlation analysis (CCA) is one of the most popular methods for two-view learning, and seeks a subspace where the given two views are maximally correlated. SVM-2K combines Kernel CCA (KCCA) and support vector machine (SVM) in a single optimization problem. Recently, White et al. proposed a convex formulation for learning a shared subspace of multiple sources. In the learned subspace, conditional independence constraints are enforced.

II-B2 Classifier-level fusion

Schemes in this category either learn classifiers of different views independently or interactively.

Output or decision fusion: Individual classifiers are created for different views and then the outputs or decisions are fused. In , the SVM outputs are firstly converted to probabilistic scores, and then concatenated as the input of an SVM for final classification. This method was shown to outperform the simple feature concatenation, followed by an SVM. Such an approach was called hierarchical SVM in , and is compared with several other popular classifier fusion strategies, such as weighted sum of outputs and majority voting. Fumera and Roli gave a theoretical analysis of the linear combination of multiple classifiers, and the effectiveness of their analytical model was confirmed by the experimental results. A thorough study on the weighted voting methods for classifier fusion was presented in , where the neural network was adopted to estimate the combination weights.

Interactive fusion: Methods in this sub-category communicate information with other views when learning classifier of the current view. Lots of these methods are semi-supervised and naturally two-view, such as co-training , co-regularization , etc. In the co-training framework, unlabeled samples classified by one view with high confidence were put in the labeled pool of the other view. Such a process was repeated until the classification performance on the validation dataset decreased. Although succeed empirically, co-training is based on the compatibility and class conditional independence assumptions, which are usually too restrictive to be satisfied . The co-EM algorithm bootstrapped samples in a similar way like co-training, but the unlabeled samples were labeled probabilistically in a batch mode using expectation-maximization (EM). By formulating the linear classifier in a probabilistic framework, SVM was introduced as the base classifier in co-EM . In , classifiers of different views are enforced to be agreed on unlabeled data by the use of a regularization term, in a graph-based semi-supervised framework. This is called co-regularization and a similar idea was utilized in , under the theme of manifold regularization .

It was shown in that classifier-level fusion outperforms simple feature concatenation, while sophisticated feature-level fusion can usually be better than classifier-level fusion since the raw information is preserved . The proposed MVMC method belongs to the classifier-level fusion, and is particular suitable for transductive (semi-supervised) multi-label classification. It was demonstrated empirically in this paper that MVMC can outperform some competitive classifier-level and feature-level multi-view learning approaches when limited labeled data are available. Experiments also show that MVMC is superior to competitive multi-label and the recently proposed semi-supervised multi-label classification method .

III Transduction with matrix completion

where $\|Z\|_{*}$ is the nuclear norm (sum of singular values) of $Z$, $c_{x}$ and $c_{y}$ are the loss function for the features and labels respectively. Both $\mu$ and $\lambda$ are the trade-off parameters. In , $c_{x}$ is chosen to be the least squares loss and $c_{y}$ is the log loss.

The problem (2) can be solved by a modified fixed point continuation (FPC) algorithm, which is to alternate between the gradient descent, $A^{k}=Z^{k}-\tau g(Z^{k})$, and the shrinkage $Z^{k+1}=S_{\tau\mu}(A^{k})$. The step size $\tau$ can be easily computed according to . Here, $k$ is the iteration step and $g(Z^{k})$ is the matrix gradient given by

IV Multi-view matrix completion

In this section, we first present our multi-view matrix completion (MVMC) framework, and then develop an algorithm that directly optimizes average precision for transductive (semi-supervised) multi-label image classification. The MVMC framework is depicted in Fig. 1. For all the labeled, unlabeled and test images, we extract different kinds of features, such as SIFT and GIST . Then we construct the stacked matrix $Z^{(v)}$ for the $v$’th view. To combine the multiple views for matrix completion, a natural idea is to weightedly sum the different feature matrices $X^{(v)},v=1,\ldots,V$, where $V$ is the number of views. However, the dimensionality of different views varies. Although we can utilize some dimensionality reduction algorithm, such as kernel PCA (KPCA), to preprocess the features, the summation of different matrices lacks physical interpretation. Therefore, we propose to combine the output label matrices of different views. KPCA is still employed to preprocess the features to significantly reduce the time complexity of the MC algorithm. The MC-1 algorithm is adopted to complete the matrix for each view since the processed features can be either positive or negative. We use the least squares loss for $c_{x}$ and the generalized log loss (a smooth approximation of the hinge loss) for $c_{y}$. Subsequently, we proposed a two-step algorithm to learn the output combination coefficients of the different views: $\bullet$ Generate training data for each view. The training data we referred here is not the features to complete the matrix $Z^{(v)}$, but the output labels to learn the combination $\theta$. We generate the data by assuming parts (e.g. half) of the labeled data as unlabeled, and predict their labels using the other parts. Such a process is then conducted conversely. In this way, we obtain the predicted labels $Y_{l}^{(v)},v=1,\ldots,V$ of the labeled data, whose labels $Y_{l}^{0}$ are actually known. $\bullet$ Learn the combination coefficients. In our formulation, the final output is a linear combination of the multiple outputs obtained from different views. Thus, we use the weighted summation $Y_{l}=\sum_{v=1}^{V}\theta_{v}Y_{l}^{(v)}$ to approximate the ground-truth $Y_{l}^{0}$. By minimizing the approximation error, we can learn the weight $\theta$.

Finally, for each view, we predict the labels of the unlabeled and test data by utilizing all the labeled data. The multiple predictions are combined with the learned $\theta$.

where $N=|\Omega_{Y_{l}}|$ is the number of entries in $\Omega_{Y_{l}}$, which is equal to $n_{l}\times m$. Here, $n_{l}$ is the number of labeled samples. The regularization term $\|\theta\|_{2}^{2}$ is used to control the model complexity, and $\eta$ is the trade-off parameter. Here, $L$ is some pre-defined convex loss. It is easy to verify that the problem (4) is convex, and thus we can obtain the global solution. In this paper, we first choose $L$ to be the least squares (LS) loss, which will lead to a quite efficient solution.

IV-B A least squares formulation of MVMC (MVMC-LS)

If we choose $L$ to be the least squares loss, i.e. $L(f(x),y)=(f(x)-y)^{2}$, then the optimization problem becomes

where $\varepsilon_{ij}=(H_{ii}-H_{ij}-H_{ji}+H_{jj})\theta_{i}-\sum_{k}(H_{ik}-H_{jk})\theta_{k}$. By further taking the constraint $\theta_{v}\geq 0$ into consideration, we have

In spite of the efficiency of the LS formulation, the LS loss is designed to optimize the accuracy performance, which is not appropriate for multi-label classification . Thus the obtained solution may be unsatisfactory. The hinge loss used in support vector machine (SVM) is not adopted for the same reason. Besides, the least squares and hinge loss are not robust loss functions . Therefore, we propose to directly optimize the average precision (AP), which is a critical criterion for evaluating the multi-label classification performance, and we can prove that the algorithm that utilizes the AP loss is more robust than that adopts the least squares or hinge loss. To this end, better view combination coefficients $\{\theta_{v}\}$ can be found hopefully. In the following, we first present the AP formulation of MVMC, and then give some theoretical analysis of the proposed algorithm, i.e., the robustness of the algorithm that adopts the AP loss compared with the least squares and hinge loss.

IV-C Optimizing average precision in MVMC (MVMC-AP)

Different from the least squares formulation, where the loss is point-wise and calculated on two scalar elements, the average precision (AP) loss is computed over two vectors for each label (category) and thus list-wise. Before presenting the AP loss, we first introduce the AP score. Suppose the input space is $\mathcal{C}$ and the output space is $\mathcal{O}$ (rankingsIt should be noted that the ranking we refer to here is an ordered sequence and the rank value is a number in the sequence, not the notation “rank” of a matrix we used in Section III. over a corpus $\mathcal{S}=\{d_{1},\ldots,d_{|\mathcal{S}|}\}$, each $d_{i}$ is a sample). In this paper (transductive multi-label classification), $\mathcal{C}$ consists of the different labels (categories), which correspond to the possible queries in information retrieval . For a certain label, if $\hat{o}$ is a prediction vector for the samples in $\mathcal{S}$ and $o$ is the corresponding ground-truth, then the AP score can be defined as

where $r(\cdot)$ is a vector of rank values. The ground-truth ranking $r(o)$ has only two rank values, i.e., $1$ for the positive samples and otherwise. The prediction ranking $r(\hat{o})$ is the sorting result of the predictions in $\hat{o}$, a larger prediction value corresponding to a higher rank value. Here, $N_{pos}=|\{i:r_{i}(o)=1\}|$ is the total number of positive samples, and $Prec@k$ is the percentage of positive samples in the top $k$ samples, where the samples in the corpus are assumed to have been sorted according to the prediction $\hat{o}$.

Usually, the mean of the AP scores of all labels, i.e., mAP is adopted for evaluation. Therefore, the loss calculation will be preformed over all labels. In the following, we show how to incorporate the AP loss into an optimization problem for learning $\theta$.

The central idea of optimizing AP in MVMC is to transform the multi-label classification into a retrieval problem, and regard each label as a query. Given a certain label $t$, the aim is to find a ranking $o$ that maximizes the discriminant function:

which is assumed to be linear (parameterized by $\theta$) in some combined feature representation given by:

where $d_{i}$ and $d_{j}$ are the samples, $\mathcal{S}^{t}$ and $\bar{\mathcal{S}}^{t}$ denote the set of positive and negative samples of $S$ for label $t$. Here, the pairwise orderings is utilized, i.e., $\mathcal{O}\subset\{-1,0,+1\}^{|\mathcal{S}|\times|\mathcal{S}|}$. For each $o\in\mathcal{O}$, $o_{ij}=+1$ if $d_{i}$ is ranked ahead of $d_{j}$, $o_{ij}=0$ if $d_{i}$ and $d_{j}$ have equal rank, and $o_{ij}=-1$ otherwise. We assume that the rankings is complete, i.e., $o_{ij}$ is either $+1$ or $-1$ (never ).

We can predict a ranking (of the samples) for label $t$ with a learned $\theta$. However, this is not the point of this paper and we only concentrate on learning the weight vector $\theta$. Here, we define the feature mapping function $\phi$ as $\phi(t,d)=p$. Each element of $p$ corresponds to the prediction of a certain view, and thus $\theta^{T}\phi(t,d)$ is a combined prediction of different views. For different labels, the feature mappings are the same, only the ground-truth orderings change. In this way, we can learn $\theta$ to combine different views by the use of the average precision (AP) loss.

Following , we use the structural SVM formulation to learn $\theta$, where an additional simplex constraint is added:

where $o_{t}$ is the ground-truth ranking for the label $t$. $C=\frac{1}{2N\eta}$, and we have defined $\delta\Psi_{t}(o)=\Psi(t,o_{t})-\Psi(t,o)$. We propose to solve the problem (12) using an alternating algorithm in the dual formulation. Note that for $\theta_{v}\geq 0,v=1,\ldots,V$, the constraint $\sum_{v=1}^{V}\theta_{v}=1$ can be satisfied by a simple normalization, so we left this sum-to-one constraint to be considered later. By introducing the Lagrangian, we obtain

Taking the partial derivatives of $L$ w.r.t. $\theta$, $\xi_{t}$ and setting them to be zero,

where $\zeta=[\zeta_{1},\ldots,\zeta_{V}]^{T}$ and the second identity is equivalent to $0\leq\alpha_{to}\leq C$ since the Lagrange multiplier $\beta_{t}\geq 0$. By substituting $\theta$ back into (12), we obtain the dual

We propose to solve this problem using the alternating optimization strategy. For fixed $\zeta$, the problem (15) becomes

which is a structural SVM formulation with the linear part $(\Delta^{T}-\zeta^{T}\delta\Psi)\alpha$. A cutting-plane algorithm is introduced to solve this problem and the most violated constraint can be found using the algorithm presented in . For fixed $\alpha$, the problem (15) can be reformulated as

This is a quadratic programming (QP) problem and can be solved quite efficiently using a standard SVM solver. It can be easily verified that the Hessian matrix of (15) H_{e}(\alpha,\zeta)=-\left[\begin{array}[]{cc}K&\delta\Psi^{T}\\ \delta\Psi&I_{V}\end{array}\right] is negative semi-definite, where $I_{V}$ is the $V\times V$ identity matrix, and thus the problem (15) is jointly concave w.r.t. $\alpha$ and $\zeta$. Besides, the sub-problems (16) and (17) are concave w.r.t. $\alpha$ and $\zeta$ respectively. Therefore, by alternatively solving (16) and (17), the algorithm will converge to the global solution of (15).

IV-D Complexity analysis

The complexity of MVMC has two parts: the first is determined by the MC-based classification of each view, and the second is determined by the learning of the view combination coefficients. In this paper, the MC-based classification is carried out by optimizing the MC-1 problem (2). We can reduce the complexity of the MC-based classification algorithm MC-1 to $(st(m+\bar{d}+n))$ by exploiting the approximate SVD based fixed point continuation (FPCA) algorithm, where $m$ and $n$ are the number of class labels and all samples respectively, $\bar{d}$ is the average feature dimension, $t$ is the iteration numbers, and $s$ is the number of elements in the $\mu$ sequence of the continuation step. In common, $s<50$ and $t<100$. Thus, the adopted MC-1 can solve large matrix rank minimization problems efficiently.

With regard to the learning of the combination coefficients ${\theta_{v}}_{v=1}^{V}$, we use the weighted summation $Y_{l}=\sum_{v=1}^{V}\theta_{v}Y_{l}^{(v)}$ to approximate the groundtruth $Y_{l}^{0}$. Weights $\{\theta_{v}\}_{v=1}^{V}$ are obtained by minimizing the approximation error. The size of each $Y_{l}^{(v)}$ is $n_{l}\times m$, where $n_{l}$ is the number of labeled data. This means that the complexity of the proposed view combination procedure is not dependent on the amount of all samples, but only on the labeled sample size, which is usually small in transductive (semi-supervised) classification. For MVMC-LS, the time complexity is $(V^{2}(n_{l}\times m))$, where $V$ is the number of views and is usually smaller than $10$. For MVMC-AP, structure SVM is exploited for optimization. According to , the time complexity of the cutting-plane method used in structural SVMs is linear in the number of training samples. Thus the computational time cost of learning the view combination coefficients is $(T(n_{l}\times m))$, where $T$ is the number of iterations and is independent on the number of samples . To this end, the view combination procedure is also very efficient, and according to our experience, it is more efficient than the MC-based classification.

Therefore, the time complexity of MVMC-LS and MVMC-AP are $(Vst(m+\bar{d}+n)+V^{2}(n_{l}\times m))$ and $(Vst(m+\bar{d}+n)+T(n_{l}\times m))$, respectively. The former is often more efficient since $V$ is usually small.

IV-E Robustness analysis

In this section, we aim to prove that AP loss is more robust than the least squares and hinge loss when learning $\theta$ for MVMC. That is, AP is more tolerate of noise. We present the definition of the robustness here for completeness.

where $h_{\mathbf{s}}$ represents the hypothesis learned using $\mathcal{A}$ on the training set $\mathbf{s}$. The sets $\{\mathcal{C}_{i}\}_{i=1}^{K}$ can be regarded as sets with elements having some similarity to each other, such as the distance.

The following two lemmas are useful for proving Theorem 1.

() Fix $\gamma>0$ and metric $\rho$ of $\mathcal{Z}$, If algorithm $\mathcal{A}$ satisfies

and $N(\gamma/2,\mathcal{Z},\rho)\leq\infty$, then $\mathcal{A}$ is $(N(\gamma/2,\mathcal{Z},\rho),\epsilon(\mathcal{Z}^{n}))$ robust.

() Let $B$ be a ball of radius $r$ in an $N$-dimensional Banach space and $\epsilon>0$. There exists a subset $B_{\epsilon}\subset B$ such that $|B_{\epsilon}|\leq(4r/\epsilon)^{N}$ and $\forall z\in B$, $\exists z^{\prime}\in B_{\epsilon}$ with $\rho(z,z^{\prime})\leq\epsilon$, where $\rho$ is the metric of the Banach space.

We defer the detailed proof of Theorem 1 in the last section.

V Experiments

In the experimental evaluation, we firstly compare the proposed MVMC-LS and MVMC-AP algorithms with the following MC-based strategies: 1) BMC, which is to use a single view that performs the best in MC; 2) CMC, which is to simply concatenate features of the multiple views in MC; 3) AMC, which is to average the MC outputs of the multiple views. Then we show the view combination coefficients learned by our MVMC-AP method. Finally, we compare MVMC-AP with some popular and competitive feature-level fusion , and classifier-level fusion algorithms, as well as some competitive multi-label and recently proposed semi-supervised multi-label classification approaches . Before all of these evaluations, we present the datasets and features we used, as well as our experimental settings.

Our experiments are conducted on two popular datasets, PASCAL VOC’ 07 (VOC for short) and MIR Flickr (MIR for short) . There are around $10,000$ natural images ($5,011$ training, $4,952$ test) from $20$ categories in the VOC dataset. The MIR dataset consists of $25,000$ images (half training, half test) and $38$ categories.

In natural image classification and web image annotation, the taxonomy of the images is very large and the category defined for a certain image may vary in different fields. Therefore, it is impossible to manually label abundant training images for every category, and it is common that limited labeled samples are given in natural image classification or annotation , especially for the new defined or uncommon categories. One of the advantages of the proposed transductive algorithms is the ability to handle small labeled sample size, since it can effectively utilize the information contained in the images from different views. To empirically demonstrate the effectiveness of MVMC, for both datasets, we only randomly select $n_{l}=\{20,30,50\}$ samples for each category in the training set as labeled, and all the others unlabeled. The labels of the unlabeled and test data are then inferred by our algorithms. Five random choices of the labeled data are used in our experiments. We also present the results of using all the labeled training samples to compare the performance of the algorithms in the fully supervised scenario. Besides, twenty percent of the test data are used for validation, which means that the parameters corresponding to the best performance on the validation set are used for unlabeled and test inference.

The features we used here are from , where 15 different image representations and tags are provided. Actually, the 15 representations are constructed from six kinds of visual features, which include two kinds of local features (Hue , SIFT ), a global representation (GIST ), and three global color histograms (Hsv, Lab, Rgb). In this paper, we regard each kind of visual feature as a single view. Then we have seven different views in all, with a tag view included. The dimensionality of the SIFT features we used is $1,000$, and the color features (Hsv, Lab, Rgb) is around $4,000$. The existing MC algorithms either fail to recover such a large size matrix $(25000\times 4000)$ or the time cost is intolerable. Thus we preprocess the features by KPCA to reduce the time complexity in the MC based image classification. For all the compared methods in this paper, the result dimension after KPCA is fixed to be $50$, since we found the different algorithms perform well under this setting.

In the VOC and MIR datasets, the positive and negative samples are quite unbalanced. Thus the traditional accuracy criterion is not proper any more, and we introduce three popular criteria in multi-label classification for evaluation. They are average precision (AP) , area under ROC curve (AUC) and hamming loss (HL) . In this paper, AP and AUC are the ranking performance computed under each label. Usually, the mean value over all labels, i.e., mAP and mAUC are reported. HL is utilized to evaluate the label set prediction for each instance. It is not a ranking based criterion but widely used in multi-label classification . A smaller value in HL indicates a better performance.

V-B A comparison with the MC-based strategies

There are several direct strategies to make use of the different views in MC: BMC, CMC and AMC. In this section, we demonstrate that learning the output combination coefficients is superior to all of these approaches. In particular, the algorithms compared are: $\bullet$ BMC : using the best single view, i.e., one that achieves the best MC-based classification performance. The MC-based transductive multi-label classification is performed by optimizing (2), where $c_{x}$ is chosen to be the least squares loss for the KPCA processed features, $c_{y}$ is tuned with $\gamma$ in $\{1,3,30\}$. The candidate set for choosing $\lambda$ is $\{10^{i}\mid i=-4,\ldots,2\}$. The parameter $\mu$ is initialized as $\mu_{0}=0.25\sigma_{1}$ ($\sigma_{1}$: the largest singular value of $Z^{0}$), and decreases with a factor $0.25$ in the continuation steps until $\mu=10^{-12}$. $\bullet$ CMC: feature-level fusion. Concatenating the normalized features of all the views into a very long vector, and then performing MC-based classification. $\bullet$ AMC: classifier-level fusion. Learning separate MC-based classifiers for different views, and then combining the outputs of all the classifiers uniformly. Before the combination, the outputs of each view are converted to the probability scores by the use of a sigmoid function $S(x)=1/((1+e^{-x}))$. $\bullet$ MVMC-LS: the proposed multi-view MC algorithm, in which the least squares loss is utilized. Outputs are also converted to probability scores. The trade-off parameter $\eta$ is tuned on the set $\{10^{i}\mid i=-2,\ldots,5\}$. $\bullet$ MVMC-AP: the proposed multi-view MC algorithm with the average precision (AP) loss.

The results for all the compared methods are presented in Fig. 2. A self-test with different number of labeled samples is carried out to see the performance variation with respect to the labeled training size. We can see that the performance of all the presented methods improve when the number of labeled samples increase. By fusing all the views, either in the feature-level or classifier-level, can always be superior to the use of only the best single view. The concatenation (CMC) and average outputs (AMC) methods are comparable with each other. Although the proposed MVMC-LS algorithm is superior to CMC and AMC in most cases, the improvement is not significant, except for the mAP performance on the MIR dataset, while MVMC-AP consistently outperforms them in terms of all the evaluated criteria on the VOC dataset, and usually has small deviations. This demonstrates the effectiveness of the learned coefficients using the AP loss. Similar results can be seen on the MIR dataset, only the mAUC performance of the compared combination methods is comparable. In the fully supervised case (the “all” column), we find that CMC is superior to AMC and comparable to MVMC sometimes. This is because when large amounts of labeled data are available, the curse-of-dimension problem caused by simple concatenation is alleviated.

V-C Analysis of the view combination coefficients

In Fig. 3, we show the combination coefficients $\theta$ learned by MVMC-AP, together with the mAP by using MC for each view. From the results, we find that the tendency of the weights is consistent with the corresponding mAP in general, i.e., the views with a higher classification performance tend to be assigned larger weights, taking the DenseSIFT (the 2nd view) and the tags (the last view) for example. The three color histogram views (Hsv, Lab, Rgb) have similar discriminative power on the VOC dataset, and thus the weights for them are almost equivalent.

V-D Compared with other multi-view and multi-label algorithms

Our last set of experiments compare MVMC with some popular and competitive multi-view algorithms, where we learn a binary classifier for each label. Besides, extensive comparisons with the competitive and recently proposed multi-label classification algorithms are also performed. Specifically we compare MVMC-AP with the following methods: $\bullet$ HierSVM : learning separate SVM classifiers for each view, and then fusing the results by using an additional SVM classifier. This is called hierarchical SVM, and the trade-off parameter $C$ for each SVM classifier is optimized over $\{10^{i}\mid i=-1,\ldots,6\}$. $\bullet$ SimpleMKL : a very popular and competitive SVM-based multiple kernel learning algorithm. Constructing a kernel for each view, and then learning a linear combination of the different kernels, as well as a classifier based on the combined kernel. The penalty factor $C$ is tuned on the set $\{10^{i}\mid i=-1,\ldots,6\}$. $\bullet$ LpMKL : a recent proposed MKL algorithm, which extend MKL to $l_{p}$-norm with $p\geq 1$. The penalty factor $C$ is tuned on the set $\{10^{i}\mid i=-1,\ldots,6\}$ and we choose the norm $p$ from the set $\{1,8/7,4/3,2,4,8,16,\infty\}$. $\bullet$ KLS-CCA : a least-squares formulation of the kernelized CCA for multi-label classification. The ridge parameter is chosen from the candidate set $\{10^{i}|i=-3,\ldots,3\}$. The different views are fused by combining the kernels (similarity matrices) with uniform weights. $\bullet$ DLP : an improved label propagation algorithm that is proposed recently for transductive multi-label learning by considering the label correlation. The parameters $\alpha$ and $\lambda$ are optimized over the set $\{10^{i}|i=-5,\ldots,1\}$ and $\{10^{i}|i=-4,\ldots,2\}$ respectively. The parameter $K$ is chosen from $\{10,20,\ldots,100\}$. The different views are fused by combining the similarity matrices with uniform weights.

The performance of the compared methods on the VOC and MIR datasets are reported in Table II and III, respectively. Both the mean and standard deviation of the three criteria are presented. From the experimental results, we observe that: 1) the performance improves with an increase of the labeled samples; 2) the multi-label classification methods (KLS-CCA and DLP) are better than HierSVM, but is inferior to other multi-view learning algorithms overall; 3) DLP outperforms KLS-CCA in most cases since the unlabeled information is utilized in transduction. But when the number of labeled data is increased, the improvement deceases and sometimes KLS-CCA is better (e.g., the mAUC performance in the fully supervised case (the “all” column) on the MIR dataset), since the significance of the unlabeled information decreases; 4) On the VOC dataset, the mAP and HL scores of the SimpleMKL method are larger than HierSVM, while the mAUC performance of the latter is better. In general, LpMKL is superior to SimpleMKL and HierSVM. The proposed algorithm consistently outperforms the other three methods; 5) On the MIR dataset, the other methods are comparable with or superior to our algorithm in terms of mAUC, while their mAP and HL performance are poor. Under the HL criterion, SimpleMKL and HierSVM perform well on only one of the two datasets (VOC and MIR respectively), while the proposed MVMC-AP achieves the best performance consistently on both datasets. In particular, we obtain a significant $6.3\%$, $5.7\%$ and $4.9\%$ improvement in terms of mAP compared with LpMKL, when $20$, $30$ and $50$ labeled samples for each class are used, respectively; 6) In the fully supervised scenario (the “all” column), SimpleMKL and LpMKL are comparable to MVMC under the mAP and mAUC criteria, but the HL performance of our method is the best among all methods. Therefore, the proposed transductive classification approach is particular suitable for the small labeled sample size problem, and is comparable to the state-of-the-art methods when large amount of labeled data are available.

Besides, the average rank of the proposed alogrithm is smaller than all the other methods in terms of all the three criteria on the VOC dataset, as well as the mAP and HL criteria on the MIR dataset. According to the Friedman test , the statistics $F_{F}$ of mAP, mAUC and HL on the two datasets are $(16.09,11.57)$, $(31.49,11.79)$ and $(27.82,137.00)$ respectively. We can see that all of them are larger than the critical value $F(5,15)=2.27$, so we reject the null-hypothesis (the compared algorithm perform equally well).

VI Conclusion

Matrix completion (MC) has recently been used in transductive (semi-supervised) multi-label classification. It has the advantageous of being efficient, robust to noise, and being able to handle missing data. In existing algorithms, only features from a single view can be used, but there is not a single feature perfect for image classification. We therefore present a multi-view framework to fuse different kinds of features for MC-based multi-label classification. Our framework has the advantage of being able to explore the complementary properties of different views. We have designed two algorithms under the framework, MVMC-LS and MVMC-AP, which differ by the choice of different losses. The robustness of the two algorithms is analyzed.

From the experimental validation on the challenging PASCAL VOC’ 07 and MIR Flickr datasets, we mainly conclude that: 1) The classifier-level fusion is better than simple feature concatenation, which is in line with ; 2) The learning of the combination coefficients is critical in the classifier-level fusion. Although the least squares formulation is quite efficient for learning the coefficients, the performance is usually not satisfactory. Thus more sophisticated loss should be adopted, such as the average precision loss utilized in this paper. Future works may be to extend MVMC for optimizing other criteria, such as AUC , by changing the loss in MVMC.

VII Proofs of Main Results

Let $\{c_{1},\ldots,c_{\mathcal{N}(\gamma/2,p,\rho)}\}$ be a $\gamma/2$ cover of $p$, where $\rho$ is a $2$-norm metric. Suppose that every prediction returned by matrix completion has the range $[-b,b]$. Then, according to Lemma 2, we have

References