Learning Multi-modal Similarity

Brian McFee; Gert Lanckriet

Source-linked AI summary

Learning Multi-modal Similarity

Brian McFee, Gert Lanckriet

arXiv:1008.5163v1Aug 30, 2010cs.AI

TL;DR

The paper tackles similarity learning when heterogeneous modalities provide no single obvious similarity measure and human judgments are subjective or inconsistent. It combines graph-filtered relative comparisons with multiple-kernel learning to produce a unified similarity space. Experiments show that the learned kernel combinations improve over unweighted combinations and often over the single best kernel, while the formulation remains limited by global per-kernel weighting assumptions.

Problem
Heterogeneous multi-modal data lacks an obvious unified similarity measure, while relative human judgments can be subjective and inconsistent.
Method
The method filters relative comparisons with graph algorithms, then learns an ensemble of kernel projections constrained by the resulting comparisons.
Results
The learned MKL combinations improve over unweighted base-kernel combinations and often outperform the single best kernel; a K1 metric achieves 0.711 (diagonal) and 0.764 (full), significantly worse than K4.
Takeaways & Limitations
Graph filtering produces a simpler, more robust training problem, while the multiple-kernel formulation integrates modalities into a unified similarity space.
Takeaways & Limitations
A single weight per kernel may be too restrictive when different kernels are informative in different subsets or regions of the data.

Abstract

from arXiv · show

In many applications involving multi-media data, the definition of similarity between items is integral to several key tasks, e.g., nearest-neighbor retrieval, classification, and recommendation. Data in such regimes typically exhibits multiple modalities, such as acoustic and visual content of video. Integrating such heterogeneous data to form a holistic similarity space is therefore a key challenge to be overcome in many real-world applications. We present a novel multiple kernel learning technique for integrating heterogeneous data into a single, unified similarity space. Our algorithm learns an optimal ensemble of kernel transfor- mations which conform to measurements of human perceptual similarity, as expressed by relative comparisons. To cope with the ubiquitous problems of subjectivity and inconsistency in multi- media similarity, we develop graph-based techniques to filter similarity measurements, resulting in a simplified and robust training procedure.

1. Introduction

The paper addresses similarity learning for heterogeneous, multi-modal data, where different feature spaces can produce competing notions of similarity. It proposes combining human relative comparisons, graph-based filtering, and multiple-kernel embedding to learn a robust unified space.

Multi-modal data may support several plausible similarity notions across acoustic, semantic, visual, or social feature spaces.
Human relative comparisons provide side-information while avoiding unreliable quantitative similarity judgments and hard binary labels.The authors note that rank-ordering can be more reliable for subjective similarity judgments.
The framework aims to integrate modalities optimally while remaining robust to subjectivity and inter-labeler disagreement.
Graph processing filters inconsistent and redundant comparisons before they constrain the embedding optimization.
The proposed multiple-kernel method learns an ensemble of feature-space projections that produces a unified similarity space and generalizes to unseen data.

2. A graphical view of similarity

The paper represents relative similarity comparisons as a directed graph so it can identify inconsistency and redundancy before embedding. Graph processing produces a cleaner partial order that makes the learning problem more robust and efficient.

The embedding seeks to preserve the ordering that one item pair is more similar than another, with a unit distance margin.
Relative comparisons can be represented as directed edges between vertices corresponding to item pairs.A comparison (i, j, k, ℓ) creates an edge from pair (i, j) to pair (k, ℓ).
Cycles in the comparison graph indicate inconsistency because no embedding can satisfy all cyclic constraints.The authors interpret such cycles as label noise and identify subsets that must be violated.
For acyclic comparisons, transitive reduction removes constraints implied by other comparisons without changing the represented ordering.
Approximate maximum-acyclic-subgraph processing retains a consistent subset, while transitive reduction removes redundancy and lowers optimization overhead.

3. Partial order embedding

The partial order embedding framework learns transformations that conform Euclidean distances to relative similarity constraints, extending through kernels to nonlinear embeddings. Its kernel formulation supports out-of-sample mapping, while the GNMDS connection exposes the limitation of directly learning training-point inner products.

The embedding learns a representation consistent with relative similarity measurements and applies the learned projection to unseen points.Out-of-sample data is embedded by applying the learned projection.
Slack variables and regularization soften potentially unsatisfiable constraints while controlling overfitting.The optimization minimizes hinge loss over violations together with a regularization term.
Replacing the projection matrix with a positive semidefinite matrix converts the non-convex formulation into a semidefinite program.
3.2 Non-linear projection via kernels: Kernelization maps data into an RKHS before linear projection, thereby enabling nonlinear embedding functions.
3.2 Non-linear projection via kernels: The representer-theorem formulation expresses each projection component in the span of the training data and optimizes a finite matrix representation.
3.3 Connection to GNMDS: When K = I, the formulation recovers GNMDS, but directly learning training-point inner products does not provide a meaningful out-of-sample extension.

4. Multiple kernel embedding

The section develops multiple-kernel embeddings that combine heterogeneous feature spaces through separately learned projections, rather than relying on a single weighted projection. The resulting formulation is convex and can be solved as an SDP, though scaling remains difficult for large datasets.

Motivation and setup: Separate feature spaces and kernel matrices are combined into a unified embedding for heterogeneous data.Each modality is represented independently before integration.
Unweighted and weighted combinations: Unweighted kernel summation treats all kernels equally, potentially degrading the embedding when feature quality differs.The approach cannot distinguish features that best fit the similarity constraints from less useful features.
Weighted combination: A weighted-combination formulation is non-convex because its distance constraints contain cubic or differences of positive quadratic terms.Using one weight per kernel may also be too restrictive when kernels are informative in different regions.
Concatenated projection: Concatenating independently projected feature maps lets the model learn an ensemble of domain-specific projections jointly optimized for the embedding.This is more flexible than applying essentially the same projection to every weighted feature space.
Optimization: Replacing projection operators with positive-semidefinite matrices makes the regularization and distance terms linear, yielding the SDP-based Algorithm 4.The formulation optimizes over m different n×n matrices, or an equivalent block-diagonal mn×mn PSD matrix.
Properties and comparison: K4 contains K3 as a special case while remaining convex, and the proposed K4 formulation outperforms the simple unweighted combination in practice.The section notes that K4 is more tractable than K3 and empirically better than the unweighted rule.

5. Experiments

Experiments evaluate the framework on toy taxonomy data and musical perceptual-similarity data. Learned embeddings and multiple-kernel weighting improve accuracy, reject noisy or weak kernels, and benefit from graph processing.

Experiments: The framework is tested on a toy taxonomy dataset and a real-world dataset of musical perceptual similarity measurements.The toy data uses ALOI images and synthesized relative comparisons; the musical dataset evaluates artist-level similarity.
5.1 Toy experiment: Taxonomy embedding: The toy experiment combines shape, color, intensity, and random-noise kernels, with relative comparisons generated from an artificial label taxonomy.The taxonomy spans subtrees through least common ancestors, while the kernels encode complementary image properties and distractor noise.
5.1 Toy experiment: Taxonomy embedding: 0.984 accuracy: MKPOE outperforms the learned linear-kernel baseline at 0.951 and assigns negligible weights to random-noise kernels.The unweighted combination performs worse, reaching 0.718 in native space and 0.861 in the optimized sum-kernel space.
5.2.3 EMBEDDING RESULTS: On the musical dataset, learned metrics significantly improve accuracy over native kernel spaces, while full-matrix embeddings outperform diagonal embeddings in all but one case.This comparison is reported for each base kernel in the aset400 embedding evaluation.
5.2.3 EMBEDDING RESULTS: MKPOE improves over unweighted kernel combinations, often beats the single best kernel, and remains robust with poorly performing distractor kernels.A K1 metric over all kernels achieves 0.711 diagonal and 0.764 full accuracy, significantly below the K4 results.
5.2.3 EMBEDDING RESULTS: Learned kernel weights are sparse and nonuniform: the MFCC kernel is eliminated, while most weight is assigned to the social-tag kernel.The MKPOE visualization also captures high-level genre structure in a low-dimensional embedding.
5.2.4 GRAPH PROCESSING RESULTS: Each level of graph processing yields a small accuracy improvement while substantially reducing computational overhead during optimization.The fully processed constraint set is reduced to a maximal consistent partial order with 4401 measurements.

6. Hardness of dimensionality reduction

The paper shows that finding minimum-dimensional embeddings satisfying partial-order distance constraints is computationally hard, including NP-hardness already in one dimension.

Dimensionality limits: Convex regularization of W approximates rank, so the presented algorithms do not generally find embeddings of exactly minimal dimensionality.The paper notes that rank constraints are non-convex, limiting efficient convex minimization of dimensionality.
One-dimensional realizability: Not every partial-order distance instance can be realized in R1; a square requires side distances below diagonal distances, which R1 cannot satisfy.The square provides a concrete infeasible one-dimensional configuration.
Computational hardness: 1-POE is NP-Hard, established by reducing Betweenness to distance constraints that force one point between two others.The reduction maps each ordered triple to two distance comparisons encoding the required betweenness relation.
Computational hardness: Dimensionality reduction subject to partial-order constraints is also NP-Hard because 1-POE reduces to the general minimum-dimensional embedding problem.Thus the hardness applies beyond the one-dimensional special case.

7. Conclusion

The conclusion presents graph-based filtering and multiple-kernel learning as complementary components for integrating heterogeneous data into a perceptual similarity space.

Graph-based filtering: Graph-theoretic processing isolates inconsistencies and removes redundant relative-similarity constraints before optimization.This filtering reduces computational overhead while addressing noisy training measurements.
Multiple-kernel learning: The multiple-kernel formulation integrates feature modalities into a unified similarity space through concatenated projections and a semidefinite program.Diagonal constraints reduce computational complexity and make each point-feature contribution interpretable.
Multiple-kernel learning: Diagonal constraints yield a flexible model that uses kernels where they are informative and an interpretable model whose diagonal weights represent point-feature contributions.The formulation supports both computational simplification and a geometric interpretation of modality contributions.

Appendix A. Embeddability of partial orders

The appendix establishes embeddability for partial orders and describes constructions that preserve distance order while producing lower-dimensional or constraint-respecting embeddings.

Embeddability: Any set with a partial order over distances can be embedded into R^n while satisfying all distance comparisons.This provides a general existence result for partial-order embedding.
Order construction: For a total ordering, the problem reduces to non-metric multidimensional scaling and admits a constraint-satisfying constant-shift embedding.For general partial orders, topological sorting produces a weak total order before embedding.
Order construction: Algorithm 5 constructs a dissimilarity matrix from the partial-order graph, after which classical multidimensional scaling can produce an embedding.The appendix describes this as the general construction for converting ordered constraints into an embedding problem.
Dimension reduction: A constant spectral shift changes every squared distance by the same amount, preserving the ordering and yielding an embedding in R^(n−1).The shift uses the minimum eigenvalue and preserves the total order, hence the partial-order constraints.

Appendix B. Solver

The solver optimizes kernel-based distance constraints with hinge loss and projected subgradient updates, projecting iterates back onto positive semidefinite matrices.

Multiple-kernel extension: The multiple-kernel solver extends the single-kernel derivation, while diagonal constraints use a nonnegative projection W_ii → max(0, W_ii).The derivation is presented first for the single-kernel semidefinite program and then generalized.
Constraint formulation: A relative distance constraint becomes a linear inequality in the kernel-derived matrix representation, with slack variables for violations.The margin formulation compares two distances and permits a violation through ξ_ijkℓ.
Constraint formulation: Slack variables are eliminated by rewriting the optimization objective with hinge loss over the margin constraints.This converts explicit violation variables into a loss-based objective.
Optimization: The gradient combines regularization with hinge-loss contributions from violated constraints, which can be collected into an efficient matrix calculation.Linearity allows the solver to aggregate constraint terms before multiplying by the kernel matrix.
Optimization: After each update, spectral thresholding projects W onto the positive semidefinite cone by replacing each eigenvalue λ_i with max(0, λ_i).This maintains the required PSD constraint during projected subgradient descent.

Appendix C. Relationship to AUC

The appendix connects relative-distance comparisons with AUC-style ranking, defining GAUC as the fraction of correctly ordered pairs. Because this loss is nonconvex, the algorithms optimize a convex hinge-loss upper bound using margin and slack variables.

Embedding points and ranking neighbors by increasing distance yields an AUC score based on relevant-versus-irrelevant pair ordering.The ranking is evaluated over truncation levels and averaged to obtain AUC.
An embedding satisfying every relative-distance constraint achieves an AUC score of 1.This requires every relevant point to be closer than every irrelevant point for each query point.
GAUC generalizes AUC by averaging correctly ordered pairs, or equivalently satisfied relative-distance constraints, under partial or non-binary relevance observations.Unlike the binary, complete-relevance setting, GAUC applies to a more general set of relative comparisons.
Since the GAUC loss is a nonconvex sum of indicators, Algorithms 2–4 replace the indicators with hinge losses and introduce unit margins and nonnegative slack variables.The hinge formulation provides a convex upper bound on the original loss.