PaperlayerView exact revision on arXiv

Source-linked AI summary

Decomposition-Based Transfer Distance Metric Learning for Image Classification

Yong Luo, Tongliang Liu, Dacheng Tao, Chao Xu

arXiv:1904.03846v1cs.CV

TL;DR

Target metric learning often lacks the pairwise labels it needs, while source metrics may not transfer well across differing data distributions. DTDML builds a target metric from source-derived or random bases; experiments report advantages across handwritten and natural-image tasks.

  • Problem

    Target metric learning needs abundant pairwise side information that is costly to obtain, and source metrics may be biased when source and target distributions differ.

    Source: §I · p. 1

  • Method

    DTDML represents the target metric as a sparse combination of source-eigenvector or random base metrics, fitting its coefficients alongside source-metric integration weights.

    Source: §I · pp. 1–2, §III · p. 4

  • Results

    DTDML is significantly superior on almost all letter tasks and best on all NUS-WIDE splits, with average gains of 3.8% over TML on letters and 8.1% over TML on NUS-WIDE using four labeled samples.

    Source: 2) A comparison with the other… · p. 8, B. Web image annotation · p. 9

  • Takeaways & Limitations

    DTDML learns fewer variables than direct target-metric estimation, which the authors report supports more reliable solutions with limited target side information and faster optimization.

    Source: §I · p. 2

Abstract

from arXiv · show

Distance metric learning (DML) is a critical factor for image analysis and pattern recognition. To learn a robust distance metric for a target task, we need abundant side information (i.e., the similarity/dissimilarity pairwise constraints over the labeled data), which is usually unavailable in practice due to the high labeling cost. This paper considers the transfer learning setting by exploiting the large quantity of side information from certain related, but different source tasks to help with target metric learning (with only a little side information). The state-of-the-art metric learning algorithms usually fail in this setting because the data distributions of the source task and target task are often quite different. We address this problem by assuming that the target distance metric lies in the space spanned by the eigenvectors of the source metrics (or other randomly generated bases). The target metric is represented as a combination of the base metrics, which are computed using the decomposed components of the source metrics (or simply a set of random bases); we call the proposed method, decomposition-based transfer DML (DTDML). In particular, DTDML learns a sparse combination of the base metrics to construct the target metric by forcing the target metric to be close to an integration of the source metrics. The main advantage of the proposed method compared with existing transfer metric learning approaches is that we directly learn the base metric coefficients instead of the target metric. To this end, far fewer variables need to be learned. We therefore obtain more reliable solutions given the limited side information and the optimization tends to be faster. Experiments on the popular handwritten image (digit, letter) classification and challenge natural image annotation tasks demonstrate the effectiveness of the proposed method.

I. INTRODUCTION

The introduction motivates using related source tasks to learn target distance metrics when target labels are scarce and source and target distributions may differ. It presents DTDML’s base-metric approach and situates it within distance metric learning and transfer learning.

I. INTRODUCTION

  • Target metric learning needs abundant pairwise side information, but target labels are costly and directly applying a source metric may fail when task distributions differ.Related source tasks can provide more labeled samples and side information.Source: §I · p. 1
  • DTDML represents the target metric as a combination of base metrics from source eigenvectors or random bases, and learns sparse coefficients while matching an integration of source metrics.The approach targets fewer learned variables than direct target-metric estimation.Source: §I · pp. 1–2

A. Distance metric learning

  • Supervised distance metric learning includes methods based on constraints, chunklets, relative comparisons, nearest-neighbor objectives, and information-theoretic regularization.The introduction reviews representative methods including RCA, NCA, LMNN, and online regularized metric learning.Source: A. Distance metric learning · p. 2

B. Transfer learning

  • Homogeneous transfer assumes source and target share an instance space but differ in distribution; the paper focuses on this setting and reviews two prior homogeneous metric-transfer approaches.The cited approaches transfer prior knowledge from auxiliary data or encode task relationships in a covariance matrix.Source: B. Transfer learning · pp. 2–3

III. DECOMPOSITION BASED TRANSFER DISTANCE METRIC LEARNING

  • DTDML independently learns source metrics, integrates them, and represents the target metric using source eigenvectors or random bases; it jointly estimates integration weights and base coefficients by minimizing divergence.The target metric is formed from base metrics, with target labeled samples also used in learning the result metric.Source: §III · p. 4

A. Problem formulation

DTDML constructs the target metric from base metrics while encouraging it to remain close to an integration of source metrics. Its formulation uses sparse base-metric coefficients and alternating optimization.

A. Problem formulation

  • Sparse base-metric coefficients suppress redundant or noisy inputs when constructing the target metric.The formulation uses both ∥α∥2^2 and ∥θ∥1 to control model complexity.Source: A. Problem formulation · p. 4
  • The objective uses a hinge loss over pairwise constraints, with b set to zero.The supplied formulation also includes the difference between A and A_S as a term expected to be small.Source: A. Problem formulation · p. 4
  • The solution alternates between optimizing the source-metric integration weights α and the base-metric coefficients θ until convergence.Source: A. Problem formulation · p. 4

B. Optimization procedure

DTDML solves its two parameter subproblems with different procedures: it smooths the θ objective for Nesterov optimization and solves the α subproblem as a constrained quadratic program. The smoothing parameter trades approximation error against convergence speed.

B. Optimization procedure

  • For fixed α, the θ optimization smooths the nondifferentiable hinge loss before applying Nesterov’s method.Source: B. Optimization procedure · p. 4
  • The smoothing parameter σ balances approximation error against convergence speed: larger values increase approximation error, while smaller values slow convergence.The implementation empirically sets σ to 5.Source: B. Optimization procedure · p. 4
  • Nesterov’s method minimizes the smoothed θ objective at an optimal convergence rate of O(1/k^2).The method uses the smoothed-loss gradient and Lipschitz constant to set the descent direction and step size.Source: B. Optimization procedure · p. 5
  • The α subproblem is a constrained quadratic program that can be solved efficiently by coordinate descent.Each iteration updates two α elements while leaving the others fixed.Source: B. Optimization procedure · p. 5
  • Algorithm 1 describes the optimization procedure with automatic determination of γB and γC, and sets ρB and ρC empirically to one.The procedure stops when the objective-value change satisfies its stopping criterion.Source: B. Optimization procedure · pp. 5–6

C. Automatic determination of the regularization parameters γB and γC

The paper automatically selects γB and γC using an L-curve approach, but not γA because its regularization term couples α and θ. A tangency-based method identifies the L-curve corner, and the implementation stops based on objective-value change.

C. Automatic determination of the regularization parameters γB and γC

  • The automatic selection method covers γB and γC, but not γA because its regularization term ∥A−A_S∥2_F couples α and θ.Source: C. Automatic determination of the… · p. 6
  • The L-curve selects a regularization value at the corner that balances approximation error and solution size.A tangency-based method finds the corner; its tangent slopes ρB and ρC are empirically set to one.Source: C. Automatic determination of the… · p. 6
  • The implementation stops when the relative objective-value change between iterations falls below a predefined threshold.The stopping test uses |O_k−O_{k−1}|/|O_k−O_0|.Source: C. Automatic determination of the… · p. 6

D. Theoretical analysis

The theoretical analysis provides a generalization error bound for DTDML, derived using uniform stability.

D. Theoretical analysis

1) Uniform Stability:

The section defines uniform stability through single-example replacement and develops a Bregman-divergence route toward a stability result for the algorithm.

2) Generalization error bound:

  • Uniform stability bounds the loss change when one sample in the training set is replaced; s_i denotes that replaced-sample set.Source: 1) Uniform Stability · p. 6
  • For differentiable convex functions the section defines Bregman divergence, then extends it to nondifferentiable losses using subgradients.Source: 1) Uniform Stability · p. 6
  • The generalized Bregman divergence is nonnegative and additive, while the metric-loss difference is bounded by 4LR^2 times the Frobenius distance between metrics.Source: 1) Uniform Stability · p. 6
  • Theorem 2 states the algorithm's uniform-stability result under the assumption that every sample has norm at most R; L is the loss function's Lipschitz constant.The detailed proof is in the appendix.Source: 1) Uniform Stability · p. 7

2) Generalization error bound:

The section defines generalization error as the gap between expected and empirical pairwise risk, then derives a probabilistic bound using uniform stability and source-task information.

2) Generalization error bound:

  • Empirical risk averages pairwise losses over the sample, while expected risk is the expected pairwise loss; their difference is the generalization defect.Source: 2) Generalization error bound · p. 7
  • The bound is derived from the obtained uniform stability using McDiarmid's inequality for independent random variables with bounded single-sample effects.Source: 2) Generalization error bound · p. 7
  • Theorem 4 presents a high-probability generalization bound for the learned target metric, whose upper bound includes source-learned A_S and θ_S.The theorem states probability at least 1 − δ; g_AS is the largest loss under A_S.Source: 2) Generalization error bound · p. 7

IV. EXPERIMENTAL EVALUATION

The evaluation compares DTDML with target-only and transfer-learning baselines on handwritten image and natural-image tasks. Its handwritten-image study compares source-eigenvector bases with random bases and uses the results to choose a basis strategy for later experiments.

A. Handwritten image classification

  • The evaluation covers USPS digit tasks, handwritten-letter tasks, and a challenging natural-image annotation dataset.USPS has 7,291 samples; the letter dataset has 52,152 samples, with at most 1,000 positive and 1,000 negative samples selected per task.Source: §IV · p. 7, A. Handwritten image classification · pp. 7–8

IV. EXPERIMENTAL EVALUATION

  • The comparison includes target-only RDML, RDML trained on pooled source and target data, LDML, TML, and the proposed DTDML.Source metrics are trained with RDML; target metrics are evaluated by 1-nearest-neighbor accuracy on held-out data, averaging ten random labeled-sample choices and reporting standard deviations.Source: §IV · p. 7

A. Handwritten image classification

  • Each USPS task classifies a pair of digits, with one of nine tasks serving as the target and the others as sources; the letter study considers six binary tasks.USPS images are 16 × 16 raw pixels (d = 256); letter features have dimension 128.Source: A. Handwritten image classification · p. 8

1) A self-comparison of DTDML using source eigenvectors and random bases:

  • DTDML SE uses source-metric eigenvectors for a fixed m × d base count, whereas DTDML RB uses random-matrix eigenvectors and permits an arbitrary base count.The study randomly selects one task from each handwritten dataset for the comparison.Source: 1) A self-comparison of DTDML using… · p. 8
  • With 100 random bases, DTDML RB still obtains satisfactory accuracy, but it usually does not outperform DTDML SE; increasing the random-basis count tends to improve accuracy.The comparison covers handwritten digits and letters; DTDML SE is used in later experiments to avoid tuning the additional basis-count parameter.Source: 1) A self-comparison of DTDML using… · p. 8, Figure 2 · p. 8

2) A comparison with the other algorithms:

DTDML outperforms the compared methods on handwritten digit and letter classification and natural-image annotation. The discussion attributes its advantage to learning a target metric through base-metric coefficients, using fewer variables, and reports that source eigenvectors perform a little better than random bases.

2) A comparison with the other algorithms:

B. Web image annotation

  • On NUS-WIDE, six animal concepts form the source task and the remaining concepts form the target task, with 100 randomly selected samples per concept.The dataset contains 269,648 images, and the experiments use 500-D bag-of-visual-words features based on SIFT descriptors.Source: B. Web image annotation · p. 9

V. CONCLUSION AND DISCUSSION

  • DTDML learns base-metric combination coefficients rather than the high-dimensional target-metric entries, reducing the number of variables; Nesterov’s method is used for efficient optimization.The paper states that fewer variables can yield more reliable solutions with limited target side information and that optimization tends to be faster.Source: §V · pp. 9–10
  • Source eigenvectors and random bases can both construct the target metric, although source eigenvectors perform a little better.The paper also concludes that base-metric induction is more effective than directly learning target-metric variables, even with random bases.Source: §V · p. 10

APPENDIX A PROOF OF THEOREM 1

The appendix proofs derive a gradient and Lipschitz bound for Theorem 1, then use convexity and comparison of neighboring-sample minimizers in Theorem 2.

APPENDIX A PROOF OF THEOREM 1

  • Theorem 1’s proof derives the gradient for a sample and calculates a Lipschitz constant before concluding the proof.The supplied passages provide proof steps but do not state the theorem’s claim.Source: Appendix A · pp. 10–11

APPENDIX B PROOF OF THEOREM 2

  • Theorem 2’s proof writes the objective as a sum of convex terms, including an L1 penalty on the coefficient vector.The proof denotes the objective by F_N(θ)=P_N(θ)+Q(θ).Source: Appendix B · p. 11
  • The proof compares minimizers for datasets differing by one example and applies a lemma’s loss bound to complete the argument.It uses nonnegative generalized Bregman divergence and the stated bound on the change in loss.Source: Appendix B · p. 11

APPENDIX C PROOF OF LEMMA 2

The appendix bounds the learned metric’s distance from the source-metric integration, then uses stability and concentration arguments in the proof of Theorem 4.

APPENDIX C PROOF OF LEMMA 2

  • The proof of Lemma 2 bounds the Frobenius distance between the learned metric and the integrated source metric.The displayed bound depends on the loss at the integrated source metric and the difference in coefficient-vector L1 norms.Source: Appendix C · p. 11

APPENDIX D PROOF OF THEOREM 4

  • Theorem 4’s proof defines the generalization gap as the difference between population and empirical risk and invokes a stability bound.It states Φ(A_N)≤2β and uses an expectation bound for Φ(A_N).Source: Appendix D · p. 12
  • For δ>0, the proof applies McDiarmid’s inequality to obtain a probability statement for the gap.The supplied passage gives the probability setup but not the resulting bound’s full expression.Source: Appendix D · p. 12
Loading 1904.03846v1…