PaperlayerView exact revision on arXiv

Source-linked AI summary

Dissimilarity-based Sparse Subset Selection

Ehsan Elhamifar, Guillermo Sapiro, S. Shankar Sastry

arXiv:1407.6810v2cs.LGstat.ML

TL;DR

Finding a compact set of representatives that captures a larger collection matters across data and model applications, but many methods rely on a single set or constrained dissimilarities. DS3 uses a row-sparsity-regularized optimization over source-to-target dissimilarities, with a convex relaxation. The paper reports grouping guarantees, outlier handling, and improved state-of-the-art results across representative-image and representative-model tasks.

  • Problem

    The paper addresses how to select representatives from a source set to encode a target set using pairwise dissimilarities.

    Source: §1.2 · p. 2

  • Method

    DS3 formulates representative selection as row-sparsity-regularized trace minimization and uses a convex relaxation of its generally NP-hard formulation.

    Source: §1.2 · p. 2, §2.3.1 · p. 4

  • Results

    The paper reports that DS3 has guarantees for finding representatives across jointly grouped sets and revealing their clustering.

    Source: §6 · p. 13

  • Takeaways & Limitations

    The authors report that their ADMM implementation is highly parallelizable, further reducing computational time.

    Source: §6 · p. 13

    DS3 does not explicitly use known training labels to minimize classification error when selecting samples; extending it to a supervised setting is left to future research.

    Source: §5.1.2 · p. 10

Abstract

from arXiv · show

Finding an informative subset of a large collection of data points or models is at the center of many problems in computer vision, recommender systems, bio/health informatics as well as image and natural language processing. Given pairwise dissimilarities between the elements of a `source set' and a `target set,' we consider the problem of finding a subset of the source set, called representatives or exemplars, that can efficiently describe the target set. We formulate the problem as a row-sparsity regularized trace minimization problem. Since the proposed formulation is, in general, NP-hard, we consider a convex relaxation. The solution of our optimization finds representatives and the assignment of each element of the target set to each representative, hence, obtaining a clustering. We analyze the solution of our proposed optimization as a function of the regularization parameter. We show that when the two sets jointly partition into multiple groups, our algorithm finds representatives from all groups and reveals clustering of the sets. In addition, we show that the proposed framework can effectively deal with outliers. Our algorithm works with arbitrary dissimilarities, which can be asymmetric or violate the triangle inequality. To efficiently implement our algorithm, we consider an Alternating Direction Method of Multipliers (ADMM) framework, which results in quadratic complexity in the problem size. We show that the ADMM implementation allows to parallelize the algorithm, hence further reducing the computational time. Finally, by experiments on real-world datasets, we show that our proposed algorithm improves the state of the art on the two problems of scene categorization using representative images and time-series modeling and segmentation using representative~models.

1 INTRODUCTION

Selecting representative data points or models can summarize large collections and support applications ranging from dataset interpretation to more efficient learning. DS3 uses pairwise dissimilarities across source and target sets to select representatives, with contributions including grouping guarantees, outlier handling, and a parallelizable optimization method.

1 INTRODUCTION

  • Representatives preserve characteristics of larger data or model collections and can aid dataset interpretation, efficient learning and inference, recommendation, clustering, and data generation.The introduction also describes their use in model compression and selecting samples for classifiers.Source: §1 · p. 1

1.1 Prior Work on Subset Selection

  • Prior methods either target low-dimensional subspaces or use pairwise relationships, but existing approaches can depend on initialization, approximate the original problem, restrict dissimilarities, or scale poorly.The cited review contrasts these approaches and their limitations.Source: §1.1 · pp. 1–2

1.2 Paper Contributions

  • DS3 selects representatives from a source set to encode a target set, including settings where the sets differ or only some pairwise dissimilarities are available.Unlike cited single-set methods, its setting includes selecting models to represent data points.Source: §1.2 · p. 2
  • DS3 works with arbitrary dissimilarities, including asymmetric ones and those that violate the triangle inequality.This contrasts with cited methods that require metric dissimilarities.Source: §1.2 · p. 2
  • When points form groups defined by dissimilarities, the method selects representatives from all groups and reveals the sets’ clustering.The paper also gives a regularization-parameter range in which the solution changes from one representative to the maximum number.Source: §1.2 · pp. 2–3
  • The framework is reported to handle outliers, use a parallelizable ADMM implementation, and improve state-of-the-art results on representative-image categorization and representative-model time-series tasks.The implementation is described as having quadratic complexity in problem size.Source: §1.2 · p. 3

2 DISSIMILARITY-BASED SPARSE SUBSET SELECTION (DS3)

DS3 seeks a small subset of a source set whose members can represent a target set using supplied pairwise dissimilarities. The framework allows the sets to differ and does not require dissimilarities to be metrics or vector-space-derived.

2.1 Problem Statement

  • Given pairwise dissimilarities, DS3 seeks a small subset of source elements that well represents the target collection.A smaller dissimilarity value means a source element represents a target element better.Source: §2.1 · p. 3, §2 · p. 3
  • The source and target sets may contain different types of elements, such as models and data points, or may be identical.Examples include model-to-data encoding errors and distances between dynamical systems or data points.Source: §2.1 · p. 3

2.2 Dissimilarities

  • Dissimilarities may be computed from vector representations or supplied without them, and DS3 can also use similarities by negating them.Examples include graph edges, subjective image comparisons, and sentence similarities from string kernels.Source: §2.2 · p. 3
  • When source and target sets are identical, dissimilarities need not be symmetric or satisfy the triangle inequality.The paper gives image-feature and sentence-representation examples where one-way representation is possible.Source: §2.2 · p. 3
  • Using separate source and target sets can reduce the cost of computing and storing dissimilarities by selecting a small source subset of a larger dataset.The target may be the remainder of the dataset or the entire dataset.Source: §2.2 · p. 3

2.3 DS3 Algorithm

DS3 represents target elements with source-set exemplars by optimizing a row-sparse assignment matrix. Its convex relaxation trades representative count against encoding cost, while the regularization parameter controls how many representatives are selected.

2.3 DS3 Algorithm

  • In the noisy nonlinear-manifold example, decreasing λ selects more representative affine models that approximate the manifold more accurately.The models are learned from noisy data using the optimization with p = ∞.Source: §2.3 · p. 4, §2.3.2 · p. 5

2.3.1 Simultaneous Sparse Recovery-Based Optimization

  • The original formulation minimizes representative count and target encoding cost, but its binary assignments and row-count penalty make it non-convex and generally NP-hard.The convex relaxation replaces row counting with sums of row norms and relaxes assignments to the interval [0, 1].Source: §2.3.1 · pp. 4–5
  • The assignment matrix identifies representatives through its nonzero rows, and its entries encode target-to-representative assignments.For p = 2 assignments are typically soft, whereas for p = ∞ they are typically hard.Source: §2.3.1 · p. 5
  • When only some dissimilarities are observed, representatives can be found by restricting the objective to observed entries and setting assignments at missing entries to zero.Source: §2.3.1 · p. 5

2.3.2 Regularization Parameter Effect

  • For small λ, DS3 favors lower encoding cost and selects more representatives; for sufficiently large λ, it selects only one.As λ approaches zero, each target selects its closest source element.Source: §2.3.2 · p. 5

2.4 Dealing with Outliers

The framework handles outliers in both sets: it rejects source elements that cannot represent the target and can leave target outliers unencoded. A penalized outlier variable balances target encoding against outlier selection.

2.4 Dealing with Outliers

  • Source elements that cannot effectively represent the target are not selected, so representative selection also rejects source outliers.The framework addresses different source and target sets, while also applying when the sets are identical.Source: §2.4 · p. 5
  • Target elements can be marked as outliers rather than forced to use representatives, avoiding unwanted representatives for poorly encoded targets.Each target element’s inlier and outlier probabilities sum to one; the outlier weight penalizes selecting it as an outlier.Source: §2.4 · p. 5
  • A lower outlier weight makes a target element more likely to be classified as an outlier, while zero weights yield the trivial all-outlier solution.The framework also describes weights that increase when a source element can represent a target well and decrease otherwise.Source: §2.4 · pp. 5–6
  • The optimization treats the outlier vector as an added representative with cost w⊤e, while row sparsity penalizes representatives only for target inliers.This separates the cost of representing inliers from the cost of assigning targets to the outlier option.Source: §2.4 · p. 5
  • In the example, the target cluster centered at (7, −1) is detected as an outlier because no source points efficiently encode it.Representatives are selected from the shared clusters centered at (0, 0) and (5, 5).Source: Figure 5 · p. 6

2.5 Clustering via Representatives

The solution identifies representatives and encodes target-to-representative membership, yielding soft assignments or a hard partition of the target set. Under joint group partitioning, targets select representatives from their own group.

2.5 Clustering via Representatives

  • Each solution column gives the probabilities that a target element is represented by each source element, providing a soft assignment to representatives.The assignment entries lie in [0, 1].Source: §2.5 · p. 6
  • Choosing the representative with minimum dissimilarity gives each target element a hard assignment and partitions the target set into representative-based groups.The number of groups equals the number of representatives selected by the rule in (9).Source: §2.5 · p. 6
  • When the source and target sets jointly partition into groups by dissimilarity, targets in each group select representatives from the source group with the same membership.Source: §2.5 · p. 6
  • Co-clustering the bipartite graph of representative-to-target similarities can produce fewer clusters than the number of representatives.The desired smaller cluster count can be set through the co-clustering method.Source: §2.5 · p. 6

2.6 Alternative Formulation and Relationships to Integer Programming-Based Formulations

The alternative convex formulation minimizes encoding cost under a representative budget. The formulations connect to facility location by relaxing binary assignments and row-norm choices.

2.6 Alternative Formulation and Relationships to Integer Programming-Based Formulations

  • The alternative formulation minimizes encoding cost subject to a representative budget τ, which for p = ∞ corresponds to the desired number of representatives.The formulation is related to (5) through a Lagrange multiplier.Source: §2.6 · p. 6
  • Formulations (5) and (10) generalize and relax uncapacitated and capacitated facility location, respectively, by relaxing binary assignments and using arbitrary row ℓp norms.The facility-location formulations use binary assignments and the ℓ∞-norm on rows of Z.Source: §2.6 · p. 6
  • The convex formulations permit efficient optimization methods instead of integer or linear programming, and the paper reports guaranteed clustering in non-trivial situations.The paper identifies this as the first demonstration of integrality of a convex program for clustering, alongside its earlier work.Source: §2.6 · p. 6

3 DS3 IMPLEMENTATION

The ADMM implementation solves DS3 through alternating updates and has substantially lower reported runtime than CVX on the tested datasets. Its updates admit parallelization, with stated complexity bounds for serial and parallel execution.

3 DS3 IMPLEMENTATION

  • ADMM is significantly faster than CVX for both p = 2 and p = ∞; at N = 100, CVX runs out of memory and time while ADMM runs efficiently.The comparison averages runtime over 100 randomly generated datasets on the stated X86–64 server.Source: Table 1 · p. 7, §3 · p. 7
  • ADMM alternates updates of Z, constrained C, and the Lagrange multiplier Λ; the auxiliary-variable formulation is equivalent to (5) for the optimal Z.The C update enforces simplex constraints, and the multiplier is then updated with the other variables fixed.Source: §3 · pp. 6–7
  • The Z minimization separates across M rows, while the C minimization separates across N columns, enabling parallel subproblems.The Z step takes O(MN); with P resources, its stated runtime becomes O(⌈M/P⌉N).Source: §3 · p. 7
  • The multiplier update costs O(MN) and can be parallelized across rows or columns; the stated implementation uses memory and time proportional to the number of entries in D.The algorithm stops when both errors meet ε or the iteration limit is reached.Source: §3 · p. 7
  • The proposed ADMM implementation has O(M log(M)N) runtime, reducible to O(⌈MN/P⌉log(M)) with P parallel resources.The paper contrasts this with standard convex solvers, which typically have cubic or higher complexity.Source: §3 · p. 7

4 THEORETICAL ANALYSIS

The theoretical analysis characterizes how regularization affects representative selection and establishes clustering guarantees when source and target sets partition jointly by dissimilarity. It also gives results for the special case where the sets are identical.

4.1 Regularization Parameter Effect

  • For p ∈ {2, ∞}, λ ≥ λmax,p selects xℓ*, the source element with the smallest sum of dissimilarities to Y; the thresholds may differ by p.The regularization parameter trades off representative count against encoding cost; larger λ emphasizes fewer representatives.Source: §4.1 · p. 8
  • As λ approaches zero, each target element selects its closest source element as representative, minimizing encoding cost.This is the limiting case of placing more emphasis on encoding cost than on the number of representatives.Source: §4.1 · p. 8

4.2 Clustering Guarantees

  • When X and Y jointly partition into L groups, λ < λg makes each target group choose representatives from its corresponding source group, revealing the clustering.Under an appropriate interval of λ values, each target group can be represented by one source-group representative, yielding L representatives.Source: §4.2 · p. 9
  • The one-representative-per-group regime applies when λ is at least the group’s single-representative threshold but remains below λg, if that interval is nonempty.The selected representative corresponds to the group’s medoid.Source: §4.2 · p. 9

4.3 Identical Source and Target Sets

  • For X = Y, the clustering guarantee also covers groups where points across groups can be closer than points within a group, a regime where dissimilarity thresholding fails.The analysis assumes each point has lower self-dissimilarity than dissimilarity to any other point.Source: §4.3 · p. 9
  • For two Euclidean clusters, the joint-partition condition holds when each point is closer to its own cluster medoid and λ < r12 − max{r1, r2}.Here, r1 and r2 are cluster radii and r12 is the distance between clusters.Source: §4.3 · p. 9
  • For X = Y, λ ≤ λmin makes the optimal solution the identity matrix, so every point represents itself.The threshold is defined from the smallest gap between off-diagonal and self-dissimilarities.Source: §4.3 · p. 9

5 EXPERIMENTS

The experiments evaluate DS3 on representative-based scene classification and dynamical-model segmentation, including detection of outlying activities. Across these tasks, the reported results show strong performance with reduced training samples and effective segmentation and outlier detection.

5 EXPERIMENTS

  • The experiments compare DS3 on two real-world tasks: nearest-neighbor classification with representative samples and dynamic-data modeling and segmentation with representative models.The implementation scales dissimilarities to [0, 1] and typically sets λ = αλmax,p with α ∈ [0.01, 0.5].Source: §5 · p. 9

5.1 Classification using Representatives

  • Representatives can reduce nearest-neighbor classification’s testing-time computational cost and memory requirements while maintaining or improving performance.The experiments select representatives from training data and use them as the reduced training set.Source: §5.1 · p. 9, §5.1.1 · p. 10

5.1.1 Scene Categorization

  • With 35% of training samples per class, DS3’s classification performance is only 2.9% worse than using all training samples, and generally exceeds the compared methods.Using χ2 rather than Euclidean dissimilarities improves all algorithms’ classification performance by about 16%.Source: §5.1.1 · p. 10, Table 2 · p. 10

5.1.2 Initializing Supervised Algorithms via DS3

  • DS3-initialized SNC achieves 2.53% higher classification accuracy than nearest-neighbor classification using all training samples.The comparison is on the 15 Scene Categories dataset as the selected fraction of training samples varies.Source: §5.1.2 · pp. 10–11, Table 3 · p. 11

5.2 Modeling and Segmentation of Dynamic Data

  • DS3 learns representatives for time-series modeling and segmentation, a setting with applications including human-activity segmentation and nonlinear dynamic modeling.The experiments use motion-capture data to model and segment human activities.Source: §5.2 · p. 11, §5.2.2 · p. 11

5.2.1 Learning Switching Dynamical Models

  • The method estimates local models from trajectory snippets, compares each snippet with candidate models by representation error, then selects representatives and assigns snippets to them.The framework permits different model classes and arbitrary loss functions when local models can be estimated.Source: §5.2.1 · p. 11

5.2.2 Segmentation of human activities

  • DS3 obtains small segmentation errors, including when within-class dissimilarities exceed between-class dissimilarities, a regime where graph partitioning can fail.Kmedoids and AP generally have large errors; SC and SBiC improve on them but also have large errors in general.Source: §5.2.2 · p. 12, Table 4 · p. 12

5.3 Dealing with outliers

  • At τ = 0.1, DS3 detects the excluded ‘Jump’ activity with 90.6% TPR at 1.5% FPR, supporting outlier detection in time-series data.The experiment excludes one activity while estimating models and evaluates detection across values of β.Source: §5.3 · p. 13, Figure 12 · p. 13

6 CONCLUSION

The paper proposes DS3 for selecting source-set representatives that encode a target set, with theoretical guarantees, an efficient parallelizable ADMM implementation, and improvements over the state of the art on two real-data problems.

6 CONCLUSION

  • When the two sets jointly partition into groups, DS3 finds representatives from all groups and reveals their clustering.The paper also investigates how the regularization parameter affects the solution.Source: §6 · p. 13
  • The proposed ADMM implementation is highly parallelizable, reducing computational time.The paper also identifies scaling DS3 to very large datasets as ongoing work.Source: §6 · p. 13
  • Experiments on real datasets show state-of-the-art improvements in scene categorization with representative images and time-series modeling and segmentation with representative models.Source: §6 · p. 13
  • Ongoing work includes scaling DS3, studying high-dimensional statistical guarantees, and further analyzing its properties with outliers.Source: §6 · p. 13

APPENDIX PROOFS OF THEORETICAL RESULTS

The appendix proves conditions under which the optimization selects a single representative and establishes a group-structured recovery result by ruling out a lower-objective alternative assignment.

Proofs of Theoretical Results

  • The appendix establishes that the two sets used in the proof to characterize subgradients are equal.Source: APPENDIX PROOFS OF THEORETICAL RESULTS · p. 14
  • The single nonzero row corresponds to the source element with the minimum total dissimilarity, and the proof derives a regularization threshold for obtaining one nonzero row.The threshold is considered separately for p = 2 and p = ∞.Source: APPENDIX PROOFS OF THEORETICAL RESULTS · pp. 15–16
  • For the group-structured result, assigning elements from later target groups to representatives in the first source group would permit a feasible solution with a smaller objective, contradicting optimality.The proof uses a triangle-inequality bound and a condition involving λg to establish the contradiction.Source: APPENDIX PROOFS OF THEORETICAL RESULTS · pp. 16–17

RESULTS FOR p = 2

The results for p = 2 and p = ∞ are generally similar, but the choice of norm changes the assignment probabilities encouraged by the method.

RESULTS FOR p = 2

  • The p = 2 and p = ∞ results are quite similar overall, while p = 2 promotes probabilities in [0, 1] and p = ∞ promotes probabilities in {0, 1}.Source: RESULTS FOR p = 2 · p. 17

CLASSIFICATION USING REPRESENTATIVES

On the 15 Scene Categories task, DS3 generally performs better than the compared methods, including AP, and using only 35% of training samples per class yields accuracy close to using all samples. Results also depend on the dissimilarity measure.

CLASSIFICATION USING REPRESENTATIVES

  • DS3 generally performs better than the other methods, including AP, while Rand performs worst and Kmedoids follows it.The text attributes Kmedoids’ weaker performance to dependence on a good initialization.Source: CLASSIFICATION USING REPRESENTATIVES · p. 17
  • Using 35% of training samples per class, DS3 is 2.90% lower than using all samples with χ2 distances and 3.24% lower with Euclidean distances.Source: CLASSIFICATION USING REPRESENTATIVES · p. 17
  • Using χ2 dissimilarity improves classification performance for all algorithms by about 16% relative to Euclidean dissimilarity.Source: CLASSIFICATION USING REPRESENTATIVES · p. 17
  • The figures illustrate that decreasing λ increases the number of representatives for manifold approximation, while increasing λ decreases it for the three-Gaussian example.In the latter example, nonzero rows of Z identify representatives and its entries indicate association probabilities.Source: Figure 13 · p. 18, Figure 14 · p. 18
Loading 1407.6810v2…