論文の概要: How can classical multidimensional scaling go wrong?
- arxiv url: http://arxiv.org/abs/2110.11430v1
- Date: Thu, 21 Oct 2021 18:56:33 GMT
- ステータス: 処理完了
- システム内更新日: 2021-10-25 15:24:26.606470
- Title: How can classical multidimensional scaling go wrong?
- Title（参考訳）: 古典的多次元スケーリングはどのようにうまくいかないのか?
- Authors: Rishi Sonthalia, Gregory Van Buskirk, Benjamin Raichel, Anna C.
Gilbert
- Abstract要約: 多次元スケーリング(cMDS)はユークリッド空間にデータポイントを埋め込む方法である。
埋め込みの質は次元を増すにつれて低下することを示す。
また、この劣化は単純(例えば1-アネレスト近傍)と複雑(例えば多層ニューラルネット)の両方の分類精度をもたらすことも示している。
我々の分析では、行列が$D_l$で、少なくとも元の距離に近い$D_t$を返す新しい効率よく計算可能なアルゴリズムが導かれる。
- 参考スコア（独自算出の注目度）: 8.977242179323989
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Given a matrix $D$ describing the pairwise dissimilarities of a data set, a
common task is to embed the data points into Euclidean space. The classical
multidimensional scaling (cMDS) algorithm is a widespread method to do this.
However, theoretical analysis of the robustness of the algorithm and an
in-depth analysis of its performance on non-Euclidean metrics is lacking.
In this paper, we derive a formula, based on the eigenvalues of a matrix
obtained from $D$, for the Frobenius norm of the difference between $D$ and the
metric $D_{\text{cmds}}$ returned by cMDS. This error analysis leads us to the
conclusion that when the derived matrix has a significant number of negative
eigenvalues, then $\|D-D_{\text{cmds}}\|_F$, after initially decreasing, will
eventually increase as we increase the dimension. Hence, counterintuitively,
the quality of the embedding degrades as we increase the dimension. We
empirically verify that the Frobenius norm increases as we increase the
dimension for a variety of non-Euclidean metrics. We also show on several
benchmark datasets that this degradation in the embedding results in the
classification accuracy of both simple (e.g., 1-nearest neighbor) and complex
(e.g., multi-layer neural nets) classifiers decreasing as we increase the
embedding dimension.
Finally, our analysis leads us to a new efficiently computable algorithm that
returns a matrix $D_l$ that is at least as close to the original distances as
$D_t$ (the Euclidean metric closest in $\ell_2$ distance). While $D_l$ is not
metric, when given as input to cMDS instead of $D$, it empirically results in
solutions whose distance to $D$ does not increase when we increase the
dimension and the classification accuracy degrades less than the cMDS solution.
- Abstract（参考訳）: データセットのペアワイズな類似性を記述する行列 $d$ が与えられると、共通のタスクは、データポイントをユークリッド空間に埋め込むことである。
古典的多次元スケーリング(cMDS)アルゴリズムは、これを実現するために広く使われている手法である。
しかし、アルゴリズムの堅牢性の理論的解析と、非ユークリッド計量におけるその性能の詳細な分析は欠如している。
本稿では、$D$から得られる行列の固有値に基づいて、$D$と計量$D_{\text{cmds}}$との差のフロベニウスノルムをcMDSで返却する公式を導出する。
この誤差解析により、導出行列がかなりの数の負の固有値を持つとき、最初に減少すると、次元が大きくなるにつれて、$\|d-d_{\text{cmds}}\|_f$ が増加するという結論が導かれる。
したがって, 埋め込みの質は, 寸法が大きくなるにつれて低下する。
我々は、フロベニウスノルムが様々な非ユークリッド計量の次元を増やすにつれて増加することを実証的に検証する。
また,複数のベンチマークデータセットにおいて,埋め込みの劣化により,単純(例えば,1-ネアレスト近傍)と複合(例えば,多層ニューラルネット)の分類精度が向上し,埋め込み次元が増大するにつれて減少することを示した。
最後に、我々の分析により、行列 $D_l$ が $D_t$ に近い(ユークリッド計量は $\ell_2$ 距離に最も近い)新しい効率的な計算可能アルゴリズムが導かれる。
d_l$ はメトリックではないが、$d$ の代わりに cmds への入力として与えられると、次元を増加させると $d$ までの距離が増加せず、分類精度が cmds の解よりも低下する。
関連論文リスト
- Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - Convergence of Gradient Descent with Small Initialization for
Unregularized Matrix Completion [21.846732043706318]
バニラ勾配降下は、明示的な正則化を必要とせず、必ず基底真理$rmXstar$に収束することを示す。
驚くべきことに、収束率も最終的な精度もオーバーパラメータ化された検索ランク$r'$に依存しておらず、それらは真のランク$r$によってのみ支配される。
論文 参考訳（メタデータ） (2024-02-09T19:39:23Z) - A quasi-polynomial time algorithm for Multi-Dimensional Scaling via LP hierarchies [34.7582575446942]
多次元スケーリング(MDS)は、低次元ユークリッド空間に$n$ポイントの計量を埋め込む方法のファミリーである。
準多項式依存のMDSに対する最初の近似アルゴリズムは$Delta$である。
論文 参考訳（メタデータ） (2023-11-29T17:42:05Z) - Effective Minkowski Dimension of Deep Nonparametric Regression: Function
Approximation and Statistical Theories [70.90012822736988]
ディープ非パラメトリック回帰に関する既存の理論は、入力データが低次元多様体上にある場合、ディープニューラルネットワークは本質的なデータ構造に適応できることを示した。
本稿では,$mathcalS$で表される$mathbbRd$のサブセットに入力データが集中するという緩和された仮定を導入する。
論文 参考訳（メタデータ） (2023-06-26T17:13:31Z) - Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。
我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
論文 参考訳（メタデータ） (2023-02-03T03:19:14Z) - Near-optimal fitting of ellipsoids to random points [68.12685213894112]
楕円体をランダムな点に合わせるという基本的な問題は、低ランク行列分解、独立成分分析、主成分分析に関係している。
我々はこの予想を、ある$n = Omega(, d2/mathrmpolylog(d))$ に対する適合楕円体を構成することで対数的因子まで解決する。
我々の証明は、ある非標準確率行列の便利な分解を用いて、サンダーソン等最小二乗構成の実現可能性を示す。
論文 参考訳（メタデータ） (2022-08-19T18:00:34Z) - Majorization-minimization for Sparse Nonnegative Matrix Factorization
with the $\beta$-divergence [2.3787352248749376]
他の因子(辞書行列)のノルムは不正な定式化を避けるために制御する必要があることはよく知られている。
標準のプラクティスは、辞書の列に単位ノルムを持つよう制約することであり、これは非自明な最適化問題につながる。
我々は,$ell_1$-regularization あるいはより "攻撃的" なログ規則化に対して,単純な乗法的更新をもたらすブロック・ディフレッシブ・プライマリゼーション・最小化アルゴリズムを導出する。
論文 参考訳（メタデータ） (2022-07-13T16:09:29Z) - FriendlyCore: Practical Differentially Private Aggregation [67.04951703461657]
我々は、制約のない(擬似)計量空間から点の集合を$cal D$として取り出す、単純で実用的なツールである$mathsfFriendlyCore$を提案する。
$cal D$ が有効直径 $r$ を持つとき、$mathsfFriendlyCore$ はすべての点を含む "stable" サブセット $cal D_Gsubseteq cal D$ を返す。
$mathsfFriendlyCore$は、プライベートに集約する前に入力を前処理するために使用することができる。
論文 参考訳（メタデータ） (2021-10-19T17:43:50Z) - Conditional Uncorrelation and Efficient Non-approximate Subset Selection
in Sparse Regression [72.84177488527398]
相関性の観点からスパース回帰を考察し,条件付き非相関式を提案する。
提案手法により、計算複雑性は、スパース回帰における各候補部分集合に対して$O(frac16k3+mk2+mkd)$から$O(frac16k3+frac12mk2)$に削減される。
論文 参考訳（メタデータ） (2020-09-08T20:32:26Z) - Truncated Linear Regression in High Dimensions [26.41623833920794]
truncated linear regression において、従属変数 $(A_i, y_i)_i$ は $y_i= A_irm T cdot x* + eta_i$ は固定された未知の興味ベクトルである。
目標は、$A_i$とノイズ分布に関するいくつかの好ましい条件の下で$x*$を回復することである。
我々は、$k$-sparse $n$-dimensional vectors $x*$ from $m$ truncated sample。
論文 参考訳（メタデータ） (2020-07-29T00:31:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。