論文の概要: Multidimensional Scaling: Approximation and Complexity

• arxiv url: http://arxiv.org/abs/2109.11505v1
• Date: Thu, 23 Sep 2021 17:14:25 GMT
• ステータス: 処理完了
• システム内更新日: 2021-09-24 15:34:32.192190
• Title: Multidimensional Scaling: Approximation and Complexity
• Title（参考訳）: 多次元スケーリング:近似と複雑性
• Authors: Erik Demaine, Adam Hesterberg, Frederic Koehler, Jayson Lynch, John Urschel
• Abstract要約: 距離多次元スケーリング(MDS)は、高次元データの意味のある(非線形でない)低次元埋め込みを生成するための古典的な方法である。 釜田カワイ型グラフ描画法がMDSと等価であることを証明し,その有効性を検証可能な近似アルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 13.238259763199162
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Metric Multidimensional scaling (MDS) is a classical method for generating meaningful (non-linear) low-dimensional embeddings of high-dimensional data. MDS has a long history in the statistics, machine learning, and graph drawing communities. In particular, the Kamada-Kawai force-directed graph drawing method is equivalent to MDS and is one of the most popular ways in practice to embed graphs into low dimensions. Despite its ubiquity, our theoretical understanding of MDS remains limited as its objective function is highly non-convex. In this paper, we prove that minimizing the Kamada-Kawai objective is NP-hard and give a provable approximation algorithm for optimizing it, which in particular is a PTAS on low-diameter graphs. We supplement this result with experiments suggesting possible connections between our greedy approximation algorithm and gradient-based methods.
• Abstract（参考訳）: 計量多次元スケーリング(mds)は、高次元データの有意義な(非線形)低次元埋め込みを生成する古典的な手法である。 MDSは統計学、機械学習、グラフ描画コミュニティで長い歴史を持っている。 特に、釜田-河井強制グラフ描画法はMDSと等価であり、グラフを低次元に埋め込むのに最も一般的な方法の1つである。 汎用性にもかかわらず、MDSの理論的理解は、目的関数が極めて非凸であるため制限され続けている。 本稿では, カマダカワイ目標の最小化がnpハードであること, 最適化のための証明可能な近似アルゴリズム, 特に低径グラフ上のptasについて述べる。 我々はこの結果を, グリーディ近似アルゴリズムと勾配に基づく手法との接続の可能性を示す実験で補う。

関連論文リスト

• Orthogonal polynomial approximation and Extended Dynamic Mode Decomposition in chaos [0.0]
  拡張動的モード分解(EDMD)は、ダイナミックスの予測とモデル縮小のためのデータ駆動型ツールである。 特に、EDMDがカオスシステムが作用する微分可能な関数のクラスをどのように扱うかは明らかになっていない。 我々は、カオス写像の最も単純な例に基づいて、EDMDの汎用的で厳密な理論を初めて開発する。
  論文  参考訳（メタデータ） (2023-05-14T05:14:51Z)
• Efficient Graph Field Integrators Meet Point Clouds [59.27295475120132]
  点雲を符号化するグラフ上での効率的な場積分のためのアルゴリズムを2種類提案する。 第1のクラスであるSeparatorFactorization(SF)は、ポイントメッシュグラフの有界属を利用するが、第2のクラスであるRFDiffusion(RFD)は、ポイントクラウドの一般的なepsilon-nearest-neighborグラフ表現を使用する。
  論文  参考訳（メタデータ） (2023-02-02T08:33:36Z)
• Bayesian Hyperbolic Multidimensional Scaling [2.5944208050492183]
  低次元多様体が双曲型であるとき、多次元スケーリングに対するベイズ的アプローチを提案する。 ケース制御可能性近似は、より大きなデータ設定における後部分布からの効率的なサンプリングを可能にする。 提案手法は,シミュレーション,標準基準データセット,インディアン村のネットワークデータ,およびヒトの遺伝子発現データを用いて,最先端の代替手法に対して評価する。
  論文  参考訳（メタデータ） (2022-10-26T23:34:30Z)
• Deep Manifold Learning with Graph Mining [80.84145791017968]
  グラフマイニングのための非段階的決定層を持つ新しいグラフ深層モデルを提案する。 提案モデルでは,現行モデルと比較して最先端性能を実現している。
  論文  参考訳（メタデータ） (2022-07-18T04:34:08Z)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  最適グラフ構造を学習するための二段階最適化手法を提案する。 また、時間的複雑さをさらに軽減するために、低ランク近似モデルについても検討する。
  論文  参考訳（メタデータ） (2022-05-06T03:37:00Z)
• From graphs to DAGs: a low-complexity model and a scalable algorithm [0.0]
  本稿では,低ランク行列因数分解とDAGの連続的な最適化のためのスペース化機構を組み合わせたLoRAM for Low-Rank Additive Modelを提案する。 提案手法は,NoTearsと同じDAG特性関数を扱いながら,立方的複雑性から二次的複雑性への還元を実現する。
  論文  参考訳（メタデータ） (2022-04-10T10:22:56Z)
• Scaling Structured Inference with Randomization [64.18063627155128]
  本稿では、構造化されたモデルを数万の潜在状態に拡張するためにランダム化された動的プログラミング(RDP)のファミリを提案する。 我々の手法は古典的DPベースの推論に広く適用できる。 また、自動微分とも互換性があり、ニューラルネットワークとシームレスに統合できる。
  論文  参考訳（メタデータ） (2021-12-07T11:26:41Z)
• Learning Based Proximity Matrix Factorization for Node Embedding [33.18041180501025]
  ノード埋め込みの最近の進歩は、近接行列因数分解法は、数百万のノードを持つ大規模グラフに対して、非常に高い性能とスケールが得られることを示している。 トレーニング可能な近接測度を持つフレームワークである Em Lemane を提案する。 提案手法は,ほぼすべてのデータセットにおいて,リンク予測とノード分類タスクの両方において,既存のソリューションよりも優れている。
  論文  参考訳（メタデータ） (2021-06-10T03:29:15Z)
• Scalable Adversarial Attack on Graph Neural Networks with Alternating Direction Method of Multipliers [17.09807200410981]
  乗算器の交互方向法(ADMM)を用いた最初のスケーラブルな対向攻撃法であるSAGを提案する。 SAGは最先端の手法と比較して計算量やメモリオーバーヘッドを大幅に削減できることを示す。
  論文  参考訳（メタデータ） (2020-09-22T00:33:36Z)
• Mix Dimension in Poincar\'{e} Geometry for 3D Skeleton-based Action Recognition [57.98278794950759]
  グラフ畳み込みネットワーク(GCN)はすでに、不規則なデータをモデル化する強力な能力を実証している。 本稿では,ポアンカー幾何学を用いて定義した空間時空間GCNアーキテクチャを提案する。 提案手法を,現在最大規模の2つの3次元データセット上で評価する。
  論文  参考訳（メタデータ） (2020-07-30T18:23:18Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  我々は高密度サブグラフ発見のための新しい学習問題を導入する。 まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。 そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-06-24T11:37:33Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。