LORE: Jointly Learning the Intrinsic Dimensionality and Relative Similarity Structure From Ordinal Data

AI summary

Overview

• Research area: Machine learning, specifically ordinal embedding (OE), with applications in psychophysics, neuroscience, and comparison-based representation learning.
• Technical level: Intermediate. The core idea (recovering a low-dimensional map from "is A more similar to B than C?" judgments) is intuitive, but the method relies on nonconvex optimization tools such as the Schatten-p quasi-norm and an iteratively reweighted algorithm.
• Scope: The paper proposes LORE (Low Rank Ordinal Embedding), an algorithm that simultaneously learns an ordinal embedding and its intrinsic dimensionality, and evaluates it on synthetic data, an LLM-based simulated perceptual space, and three crowdsourced human similarity datasets.

What This Paper Is About

Ordinal embedding methods learn a multidimensional representation of items purely from relative similarity judgments (triplets), but every existing method requires the user to pick the embedding dimension in advance, with little guidance about the true complexity of the underlying perceptual space. LORE addresses this by jointly learning the embedding and its intrinsic rank, regularizing the solution so that the model does not over- or under-parameterize the latent perceptual geometry. The paper's stated goal is to enable parsimonious, interpretable, and data-efficient modeling of subjective percepts such as taste, smell, or aesthetic preference.

Key Contributions

1. A new ordinal embedding algorithm. LORE jointly infers the embedding and its dimensionality by regularizing with the nonconvex Schatten-p quasi-norm, balancing triplet accuracy against representation compactness so the result is neither underfit nor overparameterized.
2. An efficient optimization scheme with convergence guarantees. The Schatten-p quasi-norm objective is optimized with an iteratively reweighted algorithm, and the paper proves convergence of the embedding sequence to a stationary point (Theorem 1, with proof sketched and full proof in Appendix A).
3. Extensive validation where the true rank is known. The authors test LORE across varying dimensionality, noise levels, and numbers of queries, and show it estimates intrinsic dimensionality far better than existing methods while matching near-optimal triplet accuracy.
4. Real-world validation with interpretable axes. On three crowdsourced human similarity datasets, LORE achieves comparable triplet accuracy to state-of-the-art methods at substantially lower rank, and its learned axes are semantically interpretable.

Main Findings

• Baselines cannot recover rank; LORE can. Across all tested query fractions, LORE uniquely recovers the true intrinsic rank of the embedding, while baseline methods consistently default to the maximum allowed dimension. LORE matches the test triplet accuracy of the best baseline across all conditions.
• Stable regularization regime. Across a broad range of the regularization parameter (λ ≈ 0.01), LORE achieves nearly perfect test triplet accuracy and accurate intrinsic rank recovery, even as the fraction of queried triplets varies. Results in Appendix C extend this to varying noise, number of percepts, and intrinsic rank.
• Tracking increasing complexity. As the true intrinsic rank increases, only LORE tracks the change; all other methods ignore the underlying complexity. Some loss in rank recovery is observed at higher true ranks, which the authors attribute to a fixed number of triplets and the curse of dimensionality.
• Simulated LLM perceptual space. Using SBERT embeddings of 50 randomly chosen foods with intrinsic dimensionality controlled by truncated SVD (ranks 1–10) and only 5% of triplets sampled (30 runs, noise = 0.1), LORE closely tracks the intrinsic rank while all baseline OE algorithms default to the embedding dimension. Dim-CV (the hypothesis-testing method of Künstle et al., 2022) is farther from the intrinsic rank and takes considerably longer, shown on a log-scaled axis. LORE also significantly outperforms baselines in test triplet accuracy in this highly undersampled setting.
• Crowdsourced datasets. On Food-100, LORE achieves 82.45 ± 0.27 test accuracy with rank 3.3 ± 0.47 versus rank 15 ± 0.00 for SOE, FORTE, t-STE, and CKL; Dim-CV reaches 77.67 ± 0.02 accuracy with rank 1.47 ± 0.51. On Materials, LORE gets both the highest reported triplet accuracy (84.08 ± 0.19) and a low rank of 2.23 ± 0.43. On Cars, accuracy is low for all methods, yet LORE stays compact (rank 3 ± 0.45) and does not degenerate to random chance like Dim-CV (50.43 ± 1.07 accuracy, rank 1.0 ± 0.0).
• Speed. LORE is described as the second fastest method after FORTE consistently, with e.g. 6.64 ± 3.90 s on Food-100 versus 1721.9 ± 26.71 s for Dim-CV.
• Semantic interpretability. Without semantic supervision, LORE's first three axes on Food-100 align with interpretable properties: sweet to savory (Axis 1), dense to light (Axis 2), and carb-rich to protein/vegetable (Axis 3). The last axis is slightly less coherent, which the authors say is expected for axes linked to smaller singular values. Across methods, LORE's axes are consistently more aligned with meaningful semantic concepts than every method except CKL, which is comparable.
• Positioning against prior methods. Table 1 characterizes GNMDS, CKL, FORTE, t-STE, SOE, and OENN as none recovering intrinsic rank; LORE is listed as the only method that recovers intrinsic rank, is scalable, has high triplet accuracy, and produces semantically interpretable embeddings.

Methodology in Plain English

LORE starts from the observation that a perceptual space lives in some unknown low dimension d, much smaller than the number of percepts N, but the embedding we learn is placed in a user-chosen dimension d′. Rather than optimizing a Gram matrix (which requires non-scalable positive-semidefinite constraints and O(N²) work), LORE directly optimizes the embedding matrix Z, which makes each update scale with the smaller O(N d′).

The trick is to penalize the rank of Z. Because rank constraints are NP-hard and non-convex, the common substitute is the nuclear norm, but that shrinks all singular values uniformly. The paper instead uses the nonconvex Schatten-p quasi-norm (p = 0.5), which penalizes large singular values less severely and is reported to aid intrinsic rank recovery. This is, to the authors' knowledge, the first integration of the Schatten quasi-norm into a scalable ordinal embedding framework.

To make optimization tractable, the hinge triplet loss is smoothed with the softplus function, giving the objective log(1 + exp(...)) terms plus λ times the sum of singular values raised to the power p. The result is differentiable except where the embedding collapses, which the authors say can be avoided with wide initializations. Optimization proceeds via an iteratively reweighted algorithm: at each step the algorithm takes a singular value decomposition, adjusts the singular values in a weighted manner, discards non-positive ones, and reconstructs the embedding, repeating until convergence checks are satisfied. Each iteration costs O(d′(T + Nd′)) operations.

Default settings used throughout: p = 0.5, μ = 0.1 (chosen larger than the empirical Lipschitz constant so it needs no tuning), λ around 0.01, and random Gaussian initialization with variance of at least 5. Synthetic experiments default to query_fraction = 0.1, p = 0.5, d = 5, N = 50, noise = 0.1, d′ = 15, and 30 independent seeds. Evaluation uses test triplet accuracy (proportion of held-out triplets correctly satisfied) and measured rank (effective rank of the learned embedding).

Why This Matters

Impact on research. Most ordinal embedding work reports high triplet accuracy while silently overparameterizing the latent space, which can fragment a single real perceptual dimension into several axes. LORE removes the need to hand-tune the embedding dimension and, per the authors, is the only evaluated OE method that can jointly learn high-quality embeddings and the intrinsic rank. The paper argues this matters for scientific parsimony and for psychophysics, where recovering the latent internal representation is the central goal. The authors also note that metric learning and contrastive learning cannot be directly transferred to this setting because they rely on additional explicit representations or supervision that ordinal embedding does not have.

Real-world applications (as discussed in the paper):

• Flavor and food science, where a compact, interpretable embedding of taste percepts (illustrated with the Food-100 sweet-to-savory, dense-to-light, and carb-to-protein axes) supports product design.
• Materials perception, where the learned low-rank structure was verified against UMAP visualizations from prior work on the Materials dataset.
• Psychophysics and vision research, including prior OE applications the paper cites such as mapping tactile-visual dimensions of wood textures (roughness and gloss), mapping philosophical concepts onto conceptual axes, and mapping perceived distortions from spectacles.
• Crowdsourced perceptual studies generally, where query efficiency matters and active learning approaches can further reduce data collection cost.

Industry relevance. The method is implemented in cblearn as cblearn.embedding.LORE, with standalone reproduction code publicly available, which lowers the barrier for practitioners building comparison-based recommendation, search-ranking, or preference-modeling systems from relative judgments rather than absolute ratings. Its scalability claim (linear-in-d′ per-iteration cost and second-fastest runtimes after FORTE in the reported benchmarks) matters for large-scale deployment, and its lower-rank outputs reduce downstream storage and analysis cost.

Future Directions

• Theoretical guarantees. The paper states plainly that it lacks theoretical guarantees for exact rank recovery or optimal embeddings; LORE's optimization is only guaranteed to reach stationary points, not global minima.
• Active learning for data collection. The authors list active learning methods to collect perceptual data more efficiently as a future direction, which connects to the cited finding that OE learning demands at least O(N d log N) actively sampled triplets.
• Application across domains. The paper hopes the work inspires applied and theoretical advances using LORE to uncover perceptual space structure in domains beyond those tested.
• Extending to new percepts and datasets. The discussion frames LORE as a tool for mapping subtle subjective phenomena to interpretable low-dimensional spaces across psychology, neuroscience, and social science, and the reproducibility statement provides a demo for applying LORE to new datasets.

Target Audience

Researchers and practitioners in psychophysics, perceptual science, neuroscience, and social science who need to model subjective percepts from relative judgments; machine learning researchers working on ordinal embedding, low-rank recovery, and nonconvex optimization; and applied data scientists building comparison-based preference or similarity systems who want an embedding method that does not require specifying the dimension in advance. Readers seeking a method with complete theoretical guarantees for rank recovery will find that limitation explicitly acknowledged.

Authors’ abstract

Learning the intrinsic dimensionality of subjective perceptual spaces such as taste, smell, or aesthetics from ordinal data is a challenging problem. We introduce LORE (Low Rank Ordinal Embedding), a scalable framework that jointly learns both the intrinsic dimensionality and an ordinal embedding from noisy triplet comparisons of the form, "Is A more similar to B than C?". Unlike existing methods that require the embedding dimension to be set apriori, LORE regularizes the solution using the nonconvex Schatten-$p$ quasi norm, enabling automatic joint recovery of both the ordinal embedding and its dimensionality. We optimize this joint objective via an iteratively reweighted algorithm and establish convergence guarantees. Extensive experiments on synthetic datasets, simulated perceptual spaces, and real world crowdsourced ordinal judgements show that LORE learns compact, interpretable and highly accurate low dimensional embeddings that recover the latent geometry of subjective percepts. By simultaneously inferring both the intrinsic dimensionality and ordinal embeddings, LORE enables more interpretable and data efficient perceptual modeling in psychophysics and opens new directions for scalable discovery of low dimensional structure from ordinal data in machine learning.