PaperlayerView exact revision on arXiv

Source-linked AI summary

Horseshoes in multidimensional scaling and local kernel methods

Persi Diaconis, Sharad Goel, Susan Holmes

arXiv:0811.1477v1stat.AP

TL;DR

The paper asks how horseshoe patterns arise in dimensionality-reduction projections, especially when only local distances are known. It analyzes House voting data through an interval-based model and derives a theoretical explanation connecting eigenvectors to horseshoe shapes. The authors suggest this result may help explain the ubiquity of horseshoes.

  • Problem

    The paper examines how horseshoe patterns arise in dimensionality-reduction methods when the data have a latent ordering and only local distances are accurately known.

    Source: §1 · p. 1

  • Method

    The authors model legislators as points on an interval and analyze voting-derived distances and their MDS and kernel projections.

    Source: §2 · pp. 7, 9, §3.1 · p. 10

  • Results

    The proximity matrix is totally positive, so its first eigenvector can be increasing and its second unimodal; plotting them against each other always yields a horseshoe.

    Source: Summary · p. 20

  • Takeaways & Limitations

    The authors suggest that total positivity may help explain the ubiquity of horseshoe patterns.

    Source: Summary · p. 20

    The analysis assumes legislators can be mapped isometrically to an interval and that distances are accurately estimated only for nearby points.

    Source: §2 · pp. 8–9

Abstract

from arXiv · show

Classical multidimensional scaling (MDS) is a method for visualizing high-dimensional point clouds by mapping to low-dimensional Euclidean space. This mapping is defined in terms of eigenfunctions of a matrix of interpoint dissimilarities. In this paper we analyze in detail multidimensional scaling applied to a specific dataset: the 2005 United States House of Representatives roll call votes. Certain MDS and kernel projections output ``horseshoes'' that are characteristic of dimensionality reduction techniques. We show that, in general, a latent ordering of the data gives rise to these patterns when one only has local information. That is, when only the interpoint distances for nearby points are known accurately. Our results provide a rigorous set of results and insight into manifold learning in the special case where the manifold is a curve.

1. Introduction.

The paper analyzes horseshoe patterns in dimensionality-reduction projections, arguing that a latent ordering can produce them when only nearby-point distances are accurately known. It applies this perspective to 2005 House voting data and reviews the MDS procedure used to produce the projections.

1. Introduction.

  • A latent ordering can generate horseshoes when only local interpoint distances are known accurately, a pattern also reported across other statistical applications.The paper develops a rigorous analysis of this phenomenon.Source: §1 · pp. 1–2

1.1. The voting data.

  • The analysis uses 401 Representatives who voted on at least 90% of the 669 roll calls, with an empirical distance based roughly on vote disagreement.The data were restricted from the House membership to those meeting the voting threshold.Source: §1.1 · pp. 2–3
  • The 2005 House voting data produce twin horseshoes, with the model relating legislators' positions along a curve to political ideology.The paper notes that legislators at the political extremes lie slightly toward the center rather than at the projected curve tips.Source: §1.1 · p. 4

1.2. Multidimensional scaling.

  • MDS double-centers squared distances to recover inner products, then uses their leading eigenfunctions to form a lower-dimensional embedding.For the voting-data proximities, the centered and uncentered matrices have approximately the same eigenfunctions because row sums are nearly constant and eigenfunctions are approximately mean-zero.Source: §1.2 · pp. 4, 5, 7
  • The paper also connects MDS to kernel methods, focusing on an isotropic exponential kernel for its analysis of horseshoes.The specified kernel is k(x_i,x_j) = exp(-θ(x_i - x_j)'(x_i - x_j)).Source: §1.2 · p. 6

2. A model for the data.

The model places legislators on an interval and treats observed distances as locally accurate estimates of their latent separations. A cut-point voting model supplies a framework for relating voting records to those distances and comparing the assumptions with the data.

2. A model for the data.

  • In the cut-point model, each bill has a cut-point separating legislators who vote yea from those who vote nay.The model represents a bill with a cut-point and a bill parameter; its parameters are not identifiable without further restrictions.Source: §2 · p. 8
  • The model assumes legislators can be mapped isometrically to an interval and that empirical distances are accurate for nearby legislators.Equal spacing is used as a mathematically simple assumption matching the observed distances.Source: §2 · pp. 8–9
  • Comparisons between the model and voting data show rough but good accord.The paper points to comparisons involving Figures 3, 6, 7, and 9 and their accompanying commentary.Source: §2 · p. 9
  • Uniformly distributed cut-points and the model's assumptions support identifying distances between legislators from their voting records.The paper states that the uniformity assumption implies distance identifiability.Source: §2 · pp. 8–9

3. Analysis of the model.

Under local-distance information, the model yields explicit approximate eigenfunctions that produce horseshoe projections; a two-population construction yields twin horseshoes.

3.1. Eigenfunctions and horseshoes.

  • Because global distances may be unavailable, the analysis uses local dissimilarities, continuizes the scaled matrix, solves an integral equation, and applies perturbation theory.The resulting closed-form approximations describe the matrix's eigenvectors and eigenvalues.Source: §3.1 · p. 10
  • For uniformly spaced points, the first two approximate eigenfunctions are trigonometric functions defined by roots of specified equations.The paper gives cosine- and sine-based forms for these eigenfunctions.Source: §3.1 · p. 11
  • Using direct interval distances instead of exponential dissimilarities preserves much of the analysis, with explicitly diagonalizable operators and similar eigenfunctions.The paper relates this case to the crystal configuration of a one-dimensional Anderson model.Source: §3.1 · p. 11

3.1.1. Horseshoes and twin horseshoes.

  • The first two approximate eigenfunctions produce a horseshoe encoding relative interval order, but not absolute direction.The relationship between the eigenfunctions is a curve, not a quadratic function of the first eigenvector.Source: §3.1.1 · p. 12
  • In the two-population model, three approximate eigenfunctions yield twin horseshoes in the centered three-dimensional mapping.The first function spans both populations with opposite signs, while the second and third are supported on separate populations.Source: §3.1.1 · pp. 12–14, Figure 5 · p. 15

4. Connecting the model to the data.

The voting-data eigenfunctions and their re-indexed forms broadly agree with the model’s predictions, supporting its assumptions. MDS ranks also reflect local voting-distance patterns, which are related to but not identical with political-ideology rankings.

4. Connecting the model to the data.

  • 0.13192, 0.00764, and 0.00634 are the first three voting-data eigenvalues; the second and third are about equal and much smaller than the first.The paper notes that this pattern is what its two-population model suggests.Source: §4 · p. 15
  • After re-indexing legislators by f1 sign and sorting the two groups by f2 and f3, the 2004 MDS ordered eigenfunctions appear to agree with theoretically derived functions, validating modeling assumptions.Source: §4 · p. 16, Figure 8 · p. 17
  • Under the model’s isometric-interval assumption, MDS rank should follow legislators’ interval order; selected empirical distance profiles and within-group distances are roughly consistent with that assumption.The distance profiles of the first and last ranked legislators are, respectively, increasing and decreasing.Source: §4 · p. 16, Figure 9 · p. 18
  • MDS and ADA rankings are mostly consistent, but MDS separates two groups of relatively liberal Republicans whose voting positions differ despite equal ADA ratings.Mary Bono and Gil Gutknecht each received 15% from ADA, yet their votes on the 20 ADA bills never aligned when they supported the liberal position.Source: §4 · pp. 18–19, Figure 10 · p. 19
  • National Journal rankings show a similar divergence for relatively liberal Republicans, while the paper reports no comparable phenomenon for Democrats under either ranking system.The National Journal’s 2005 rating uses 107 selected votes.Source: §4 · p. 19

Summary.

The paper develops a limiting closed-form explanation for double-horseshoe patterns and connects the voting data to the model form that produces them. It also relates the pattern to eigenvector structure in a totally positive matrix.

Summary.

  • The analysis begins from the clean double-horseshoe pattern found by applying MDS to U.S. House voting data.The main results give a limiting closed-form explanation for data matrices that are double-centered versions of a specified form.Source: Summary · p. 19
  • Voting data from the cut-point model give rise to the model form analyzed in the paper.Source: Summary · p. 19
  • Figure 11 compares representatives’ eigendecomposition-derived rank with their National Journal liberal score.Source: Figure 11 · p. 20
  • For the matrix discussed, total positivity allows the first eigenvector to be increasing and the second unimodal; plotting them against each other always produces a horseshoe.Source: Summary · p. 20

APPENDIX: THEOREMS AND PROOFS FOR SECTION 3

The appendix supports the paper’s results with a perturbation theorem, an analysis of the continuous kernel’s trigonometric eigenfunctions, and approximations for discrete matrices. It also states a separation condition for the eigenfunction bound and extends the approximations to uncentered matrices.

APPENDIX: THEOREMS AND PROOFS FOR SECTION 3

  • If a unit vector has residual at most ε, the matrix has an eigenvalue within ε; with eigenvalue separation s, an eigenfunction can be chosen within ε/(s−ε).The bound permits nonsimple eigenvalues, but eigenvalues corresponding to distinct eigenspaces must be well separated.Source: APPENDIX: THEOREMS AND PROOFS FOR… · pp. 21–22
  • The appendix derives trigonometric solutions for the continuous kernel and shows that these give all its eigenfunctions with positive eigenvalues.Source: APPENDIX: THEOREMS AND PROOFS FOR… · pp. 23, 24, 26
  • The continuous-kernel eigenfunctions and eigenvalues yield approximate eigenfunctions and eigenvalues for the discrete case.The proof bounds the discretization error using the right-hand rule.Source: APPENDIX: THEOREMS AND PROOFS FOR… · pp. 28–29
  • For uncentered matrices, cosine and sine functions defined by positive solutions to the stated equations are approximate eigenfunctions of the corresponding matrices.Source: APPENDIX: THEOREMS AND PROOFS FOR… · p. 29

SUPPLEMENTARY MATERIAL

The supplementary directory provides code, original voting data, and transformed data used in the analysis.

SUPPLEMENTARY MATERIAL

Related papers

Loading 0811.1477v1…