低维嵌入会突然失效,关键维度必须接近真实维度。
Provable Accuracy Collapse in Embedding-Based Representations under Dimensionality Mismatch
- 用对比学习三元组构建嵌入,发现维度不足时准确率骤降。
- 当维度低于真实维数的常数倍时,一半三元组被违反。
- 即使算法不限维度,也难突破50%基准准确率。
基于欧几里得空间 $bR^d$ 的嵌入表示是现代机器学习的核心,其目标之一是使用最小维度忠实捕捉数据关系。本文证明了维度与准确率之间的严格权衡,并揭示了一个根本性的信息论限制:除非嵌入维度 $d$ 接近真实维度 $D$,否则准确率将发生突然崩溃。主要结果表明,该现象在标准对比学习设置中即存在,其中监督仅来自一组 $m$ 个锚点-正样本-负样本三元组 $(i,j,k)$,编码距离关系 $ ext{dist}(i,j) < ext{dist}(i,k)$。具体而言,给定可由未知真实嵌入(维度为 $D$)实现的三元组,我们证明存在常数 $c < 1$,使得任意维度不超过 $cD$ 的嵌入,将违反至少一半三元组,导致准确率低至忽略输入的一维解。我们还补充了强计算困难性结果:在唯一博弈猜想下,即使三元组几乎可在 $D=1$ 维实现,任何多项式时间算法——无论维度如何——都无法实现超过50%的准确率。
原文摘要 · Abstract (English)
Embedding-based representations in Euclidean space $\mathbb{R}^d$ are a cornerstone of modern machine learning, where a major goal is to use the \emph{smallest dimension} that faithfully captures data relations. In this work, we prove sharp dimension--accuracy tradeoffs and identify a fundamental information-theoretic limitation: unless the embedding dimension $d$ is chosen close to the ground-truth dimension $D$, accuracy undergoes a sudden collapse. Our main result shows that this phenomenon arises even in standard contrastive learning settings, where supervision is limited to a set of $m$ anchor--positive--negative triplets $(i,j,k)$ encoding distance comparisons $\mathrm{dist}(i,j) < \mathrm{dist}(i,k)$. Specifically, given triplets realizable by an unknown ground-truth embedding in $D$ dimensions, we prove that there exists constant $c < 1$, such that \emph{every embedding of dimension at most $cD$ violates half of the triplets}, yielding accuracy as low as a trivial one-dimensional solution that ignores the input. We complement our information-theoretic bounds with strong computational hardness results: under the Unique Games Conjecture, even if the given triplets are nearly realizable in $D=1$ dimension, no polynomial-time algorithm -- \textit{regardless of its dimension} -- can achieve accuracy above the trivial $50\%$ baseline.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。