PaperlayerView exact revision on arXiv

Source-linked AI summary

Multi-View Matrix Completion for Multi-Label Image Classification

Yong Luo, Tongliang Liu, Dacheng Tao, Chao Xu

arXiv:1904.03901v1stat.MLcs.CVcs.LG

TL;DR

Multi-view matrix completion addresses the limitations of single-view completion and feature concatenation in transductive multi-label image classification. It learns weights for combining view-specific outputs, using AP and LS loss formulations, and experiments report effective exploitation of complementary views on PASCAL VOC’ 07 and MIR Flickr.

  • Problem

    Single-view matrix completion cannot directly handle multi-view image features, while feature concatenation risks over-fitting and high computational cost.

  • Method

    MVMC uses cross validation on labeled data to learn weights for combining matrix-completion outputs from multiple views, with AP and LS loss formulations.

  • Results

    On PASCAL VOC’ 07 and MIR Flickr, MVMC is evaluated against single-view, concatenation, averaging, and other multi-view or multi-label methods.

  • Takeaways & Limitations

    The experiments show that MVMC exploits complementary views, with classifier-level fusion outperforming simple feature concatenation and AP-based learning generally preferable to LS.

Abstract

from arXiv · show

There is growing interest in multi-label image classification due to its critical role in web-based image analytics-based applications, such as large-scale image retrieval and browsing. Matrix completion has recently been introduced as a method for transductive (semi-supervised) multi-label classification, and has several distinct advantages, including robustness to missing data and background noise in both feature and label space. However, it is limited by only considering data represented by a single-view feature, which cannot precisely characterize images containing several semantic concepts. To utilize multiple features taken from different views, we have to concatenate the different features as a long vector. But this concatenation is prone to over-fitting and often leads to very high time complexity in MC based image classification. Therefore, we propose to weightedly combine the MC outputs of different views, and present the multi-view matrix completion (MVMC) framework for transductive multi-label image classification. To learn the view combination weights effectively, we apply a cross validation strategy on the labeled set. In the learning process, we adopt the average precision (AP) loss, which is particular suitable for multi-label image classification. A least squares loss formulation is also presented for the sake of efficiency, and the robustness of the algorithm based on the AP loss compared with the other losses is investigated. Experimental evaluation on two real world datasets (PASCAL VOC' 07 and MIR Flickr) demonstrate the effectiveness of MVMC for transductive (semi-supervised) multi-label image classification, and show that MVMC can exploit complementary properties of different features and output-consistent labels for improved multi-label image classification.

I. INTRODUCTION

Multi-label image classification supports web image analytics, but single-view matrix completion cannot adequately handle multi-view images. MVMC addresses this by learning weights to combine view-specific matrix-completion outputs, using AP and LS loss formulations.

  • Multi-label image classification assigns multiple labels per image for applications including web-image annotation and text-based retrieval.
  • Matrix completion supports transductive multi-label classification with robustness to missing data and noise, but existing methods use only a single feature view.
  • Concatenating multi-view features can ignore feature-specific interpretations, overfit limited labeled data, and create prohibitively large completion matrices.
  • MVMC combines matrix-completion outputs from different views and learns their coefficients through cross validation on labeled data.
  • The paper develops AP-loss and LS-loss solutions, with AP suited to multi-label classification and LS introduced for efficiency.
  • MVMC is evaluated on PASCAL VOC’ 07 and MIR Flickr against single-view, concatenation, and averaged-output strategies using mAP, mAUC, and HL.

1) Feature-level fusion:

Multi-view methods fuse features or classifier outputs, while matrix completion models missing labels and features through a low-rank stacked matrix. The paper positions MVMC as classifier-level fusion for semi-supervised multi-label classification.

  • 1) Feature-level fusion:: Feature concatenation can suffer from the curse of dimensionality, motivating similarity-fusion and shared-subspace approaches.
  • 2) Classifier-level fusion:: Classifier-level fusion creates separate view classifiers and combines their outputs or decisions.
  • 2) Classifier-level fusion:: MVMC belongs to classifier-level fusion and is reported to outperform simple feature concatenation and competitive methods when labeled data are limited.
  • A. Matrix completion: Matrix completion predicts unknown label entries by completing a low-rank stacked matrix containing features, labels, and a bias row.
  • A. Matrix completion: The matrix-completion objective minimizes nuclear norm and observed-entry losses, with trade-off parameters controlling the terms.

IV. MULTI-VIEW MATRIX COMPLETION

MVMC constructs a matrix-completion problem for each feature view and combines the resulting label predictions rather than summing heterogeneous feature matrices. Its coefficients are learned from held-out labeled examples.

  • MVMC extracts multiple feature types and constructs a stacked matrix separately for each view.
  • The framework combines output label matrices because directly summing heterogeneous feature matrices lacks physical interpretation.
  • KPCA reduces feature dimensionality, while MC-1 completes each view using feature and label losses.
  • Training data for coefficient learning are generated from outputs on portions of labeled data whose ground-truth labels remain known.
  • The combination coefficients are learned by minimizing the error between the weighted output sum and the ground-truth labels.
  • The learned coefficients combine predictions for unlabeled and test images after each view is completed using all labeled data.

A. The general formulation for learning θ

MVMC learns nonnegative view-combination weights from cross-validated labeled-data predictions, then combines matrix-completion outputs across views. It offers least-squares efficiency while motivating AP optimization for multi-label ranking quality and robustness.

  • A. The general formulation for learning θ: Cross-validation on labeled data generates per-view predictions used to learn the view-combination weights θ.Two folds treat one labeled subset as unknown and complete it using the other subset.
  • A. The general formulation for learning θ: The combined prediction is a weighted sum of all views, with an ℓ2 regularizer controlling model complexity and η governing the loss-regularization trade-off.The resulting convex optimization problem admits a global solution.
  • A. The general formulation for learning θ: Least-squares loss provides an efficient MVMC formulation for learning the view weights.The paper defines L(f(x), y) = (f(x) − y)^2 and rewrites the objective in compact matrix form.
  • B. A least squares formulation of MVMC (MVMC-LS): The compact least-squares objective uses H = 1/N PP^T and h, where each h_v summarizes agreement between view-v predictions and ground truth.P contains the predictions from the different views.
  • B. A least squares formulation of MVMC (MVMC-LS): Coordinate descent updates two weights at a time while enforcing the simplex constraint Σ_v θ_v = 1 and nonnegativity.The update is derived with the Lagrange method while holding θ_i + θ_j fixed.
  • B. A least squares formulation of MVMC (MVMC-LS): A view with larger h_i receives a larger combination weight θ_i under the least-squares solution.Here h_i measures the view’s prediction similarity to the ground truth.
  • B. A least squares formulation of MVMC (MVMC-LS): Least squares optimizes pointwise accuracy rather than the ranking-oriented AP criterion required for multi-label classification.The paper therefore presents AP loss as a more appropriate and robust alternative to least-squares or hinge loss.

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

MVMC-AP treats each label as a retrieval query and learns view weights from listwise ranking quality rather than pointwise accuracy. A structural-SVM formulation with alternating optimization provides the AP-based solution.

  • C. Optimizing average precision in MVMC (MVMC-AP): AP loss compares prediction and ground-truth rankings over vectors for each label, making it listwise rather than pointwise.Each label is treated as a query over the sample corpus.
  • C. Optimizing average precision in MVMC (MVMC-AP): AP distinguishes ranking quality when accuracy is identical: the toy predictions score 0.7 and 0.25 in AP despite both having accuracy 0.5.The example motivates AP for settings with many more negative than positive samples.
  • C. Optimizing average precision in MVMC (MVMC-AP): The combined prediction is parameterized as θ^Tφ(t, d), where φ contains the predictions from the different views.For each label, the feature mapping stays fixed while the ground-truth ordering changes.
  • C. Optimizing average precision in MVMC (MVMC-AP): MVMC-AP learns θ with a structural-SVM objective using ranking constraints, slack variables, and a nonnegative simplex-constrained weight vector.The sum-to-one constraint can be imposed by normalization after optimization.
  • C. Optimizing average precision in MVMC (MVMC-AP): Alternating optimization solves the AP formulation by switching between subproblems in the dual variables and view weights.The fixed-α subproblem is a quadratic program solvable with a standard SVM solver.
  • C. Optimizing average precision in MVMC (MVMC-AP): Because the objective is jointly concave in the alternating variables, the algorithm converges to the global solution.The subproblems are concave in α and ζ respectively.

D. Complexity analysis

MVMC complexity combines per-view matrix-completion cost with view-weight learning cost. The latter depends on labeled-sample size, and MVMC-LS is typically more efficient than MVMC-AP when the number of views is small.

  • D. Complexity analysis: MVMC complexity has separate terms for matrix completion in each view and learning the view-combination coefficients.The matrix-completion term uses the approximate-SVD FPCA implementation of MC-1.
  • D. Complexity analysis: The view-combination procedure depends on the labeled sample size rather than the total number of samples.This is useful in transductive classification, where the labeled set is usually small.
  • D. Complexity analysis: MVMC-LS has complexity O(V st(m+ d̄+n)+V^2(n_l×m)), while MVMC-AP has O(V st(m+ d̄+n)+T(n_l×m)).The paper states that MVMC-LS is often more efficient because V is usually small.

E. Robustness analysis

The analysis shows that AP-loss learning is more robust to noise than least-squares and hinge-loss learning under the paper’s partition-based robustness definition.

  • Robustness means partitioning the sample space into disjoint sets whose members satisfy a common loss-stability condition.The definition introduces K disjoint sets and compares objective behavior within those sets.
  • The comparison is motivated by the claim that AP loss is list-wise, while least-squares and hinge losses are point-wise.Ranking-based criteria are described as critical for multi-label classification.
  • AP-loss learning is (N, 0) robust, whereas least-squares and hinge-loss learning are only (N, a) and (N, b) robust with nonzero a and b.The AP algorithm tolerates noise that does not change the partition of the sample space.
  • The robustness claim concerns a particular fixed partition and does not assert equal losses for every training-set instance.This qualification narrows the interpretation of Theorem 1.
  • For AP loss, points sharing a ranking can be grouped into finitely many sets with equal objective losses, unlike the least-squares and hinge losses.The proof rationale relies on finitely many possible rankings versus infinitely many loss values for the other losses.

V. EXPERIMENTS

The experiments compare MVMC against single-view, feature-concatenation, and uniform-output-fusion matrix-completion strategies, then examine learned weights and broader competitors.

  • The evaluation compares MVMC-LS and MVMC-AP with BMC, CMC, and AMC matrix-completion strategies.BMC uses the best single view, CMC concatenates views, and AMC averages their outputs.
  • The study also analyzes the view-combination coefficients learned by MVMC-AP.This assesses how the proposed method weights different views.
  • MVMC-AP is further compared with competitive feature-level, classifier-level, and multi-label classification algorithms.The experiments extend beyond the directly related MC baselines.

A. Datasets, features and the evaluation criteria

Experiments use two multi-label image datasets and evaluate multiple-view matrix-completion strategies with ranking, ROC, and label-error criteria.

  • The experiments use PASCAL VOC’ 07 and MIR Flickr, containing approximately 10,000 and 25,000 images respectively.VOC has 20 categories; MIR Flickr has 38 categories.
  • The feature setup comprises seven views derived from local features, global representations, color histograms, and tags.The visual representations originate from six feature types, with a tag view included.
  • KPCA reduces each feature representation to dimension 50 before matrix-completion classification.The reduction addresses the high dimensionality and time cost of the feature matrices.
  • Performance is evaluated using mean average precision, mean area under the ROC curve, and hamming loss.mAP and mAUC measure ranking performance across labels, while HL measures label prediction error.
  • The compared strategies include the best single view, concatenated features, and uniformly averaged outputs.These correspond to BMC, CMC, and AMC, respectively.
  • As labeled-sample size increases, all methods improve; multi-view fusion generally exceeds the best single-view approach.CMC and AMC are described as comparable, while MVMC-LS is usually better than them and MVMC-AP performs consistently better on VOC.

C. Analysis of the view combination coefficients

The coefficient analysis links MVMC-AP’s learned view weights to individual-view mAP, while broader comparisons show strong VOC performance and mixed MIR results.

  • C. Analysis of the view combination coefficients: MVMC-AP generally assigns larger coefficients to views with higher individual-view mAP.DenseSIFT and tags are given as examples of views receiving larger weights.
  • C. Analysis of the view combination coefficients: The Hsv, Lab, and Rgb color-histogram views receive nearly equivalent weights on VOC because their discriminative power is similar.The relationship is reported specifically for the VOC dataset.
  • D. Compared with other multi-view and multi-label algorithms: On VOC, the proposed algorithm consistently outperforms the three compared multi-view and multi-label methods.The comparison reports results using mAP, mAUC, and hamming loss.
  • D. Compared with other multi-view and multi-label algorithms: On MIR, competing methods are comparable with or superior to the proposed algorithm in some evaluation settings.This indicates that the strongest comparative outcome is dataset-dependent.
  • D. Compared with other multi-view and multi-label algorithms: The proposed method has the smallest average rank on VOC for all three criteria and on MIR for mAP and hamming loss.The reported Friedman statistics exceed the critical value F(5, 15) = 2.27 for the tested criteria.

VI. CONCLUSION

MVMC extends matrix completion to fuse multiple feature views for semi-supervised multi-label image classification, with robustness analyzed for two loss formulations. Experiments on PASCAL VOC’ 07 and MIR Flickr support classifier-level fusion and the importance of learning combination coefficients.

  • MVMC fuses different feature views for transductive multi-label classification, addressing the limitation of single-view matrix completion.
  • MVMC-LS and MVMC-AP use different losses, and the robustness of both algorithms is analyzed.
  • Experiments on PASCAL VOC’ 07 and MIR Flickr find classifier-level fusion better than simple feature concatenation.
  • Learning the combination coefficients is critical for classifier-level fusion, while least squares is efficient but usually not satisfactory.
  • The paper identifies optimizing other criteria, such as AUC, as a direction for future MVMC work.

VII. PROOFS OF MAIN RESULTS

The proofs formalize AP-based view-combination robustness and contrast it with least-squares and hinge-loss behavior under prediction perturbations. They also characterize the prediction space through rankings, labels, and bounded prediction ranges.

  • The AP formulation chooses view-combination coefficients to maximize mean average precision over all labels.
  • The proof assumes every matrix-completion prediction lies in the range [−b, b].
  • The prediction space is partitioned using possible view rankings and binary label configurations.
  • The AP-based algorithm is stated to be (N, 0) robust, whereas least-squares and SVM-based algorithms have nonzero robustness bounds.
  • The proof concludes that AP loss tolerates small prediction perturbations when they do not change the partition, unlike least-squares and hinge loss.
Loading 1904.03901v1…