論文の概要: Approximating 1-Wasserstein Distance with Trees

• arxiv url: http://arxiv.org/abs/2206.12116v1
• Date: Fri, 24 Jun 2022 07:19:50 GMT
• ステータス: 処理完了
• システム内更新日: 2022-06-27 12:47:26.361728
• Title: Approximating 1-Wasserstein Distance with Trees
• Title（参考訳）: 木で1-wasserstein距離を近似する
• Authors: Makoto Yamada, Yuki Takezawa, Ryoma Sato, Han Bao, Zornitsa Kozareva, Sujith Ravi
• Abstract要約: Wasserstein distanceは、自然言語処理(NLP)とコンピュータビジョン(CV)の様々な用途で有効である。 ワッサースタイン距離を推定する際の課題の1つは、計算コストが高く、多くの分布比較タスクではうまくスケールしないことである。 樹木の縁の重みを学習するための,単純かつ効率的なL1正規化手法を提案する。
• 参考スコア（独自算出の注目度）: 41.77145868123863
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Wasserstein distance, which measures the discrepancy between distributions, shows efficacy in various types of natural language processing (NLP) and computer vision (CV) applications. One of the challenges in estimating Wasserstein distance is that it is computationally expensive and does not scale well for many distribution comparison tasks. In this paper, we aim to approximate the 1-Wasserstein distance by the tree-Wasserstein distance (TWD), where TWD is a 1-Wasserstein distance with tree-based embedding and can be computed in linear time with respect to the number of nodes on a tree. More specifically, we propose a simple yet efficient L1-regularized approach to learning the weights of the edges in a tree. To this end, we first show that the 1-Wasserstein approximation problem can be formulated as a distance approximation problem using the shortest path distance on a tree. We then show that the shortest path distance can be represented by a linear model and can be formulated as a Lasso-based regression problem. Owing to the convex formulation, we can obtain a globally optimal solution efficiently. Moreover, we propose a tree-sliced variant of these methods. Through experiments, we demonstrated that the weighted TWD can accurately approximate the original 1-Wasserstein distance.
• Abstract（参考訳）: 分布間の差を測定するワッサースタイン距離は、自然言語処理(NLP)とコンピュータビジョン(CV)の様々な用途において有効であることを示す。 wasserstein距離の推定における課題の1つは、計算コストが高く、多くの分散比較タスクでうまくスケールしないことである。 本稿では,木面上のノード数に関して,TWDが木面上に埋め込まれた1-ワッサースタイン距離を線形時間で計算できる木面ワッサースタイン距離(TWD)を用いて1-ワッサースタイン距離を近似することを目的とする。 より具体的には、木の端の重みを学習するための単純で効率的なL1正規化手法を提案する。 この結果から,木上の最短経路距離を用いて1-ワッサーシュタイン近似問題を距離近似問題として定式化できることを示す。 次に,最短経路距離を線形モデルで表現し,ラッソに基づく回帰問題として定式化できることを示す。 凸定式化により、グローバル最適解を効率的に得ることができる。 さらに,これらの手法のツリースライクな変種を提案する。 実験により、重み付きtwdは元の1-wasserstein距離を正確に近似できることを示した。

関連論文リスト

• Fast unsupervised ground metric learning with tree-Wasserstein distance [14.235762519615175]
  教師なしの地上距離学習アプローチが導入されました 木にサンプルや特徴を埋め込むことでWSV法を強化し,木-ワッサーシュタイン距離(TWD)を計算することを提案する。 我々は、このアルゴリズムが最もよく知られた方法よりも完全なWSVアプローチの近似に収束し、$mathcalO(n3)$複雑さを持つことを理論的かつ経験的に実証する。
  論文  参考訳（メタデータ） (2024-11-11T23:21:01Z)
• Relative-Translation Invariant Wasserstein Distance [82.6068808353647]
  距離の新しい族、相対翻訳不変ワッサーシュタイン距離(RW_p$)を導入する。 我々は、$RW_p 距離もまた、分布変換に不変な商集合 $mathcalP_p(mathbbRn)/sim$ 上で定義される実距離測度であることを示す。
  論文  参考訳（メタデータ） (2024-09-04T03:41:44Z)
• Sharper Bounds for Chebyshev Moment Matching with Applications to Differential Privacy and Beyond [26.339024618084476]
  我々は、ワッサーシュタイン距離の正確な回復が、以前よりも多くのノイズで可能であることを証明した。 主な応用として、微分プライベートな合成データ分布を構築するための単純な「線形クエリ」アルゴリズムが得られた。 数値線形代数における新たなモーメントベースリカバリの第二の応用について説明する。
  論文  参考訳（メタデータ） (2024-08-22T13:26:41Z)
• A New Robust Partial $p$-Wasserstein-Based Metric for Comparing Distributions [8.176521989807748]
  我々は,部分的な2ドルワッサーシュタイン距離の計算に基づく$k$-RPWと呼ばれる,$k ge 0$でパラメータ化された新しい距離の族を導入する。 我々の距離関数は、1ドルのWasserstein、2ドルのWasserstein、およびノイズの多い実世界のデータセット上の画像検索タスクのTV距離と比較して精度が高い。
  論文  参考訳（メタデータ） (2024-05-06T17:41:13Z)
• Linearized Wasserstein dimensionality reduction with approximation guarantees [65.16758672591365]
  LOT Wassmap は、ワーッサーシュタイン空間の低次元構造を明らかにするための計算可能なアルゴリズムである。 我々は,LOT Wassmapが正しい埋め込みを実現し,サンプルサイズの増加とともに品質が向上することを示す。 また、LOT Wassmapがペア距離計算に依存するアルゴリズムと比較して計算コストを大幅に削減することを示す。
  論文  参考訳（メタデータ） (2023-02-14T22:12:16Z)
• Robust Multi-Object Tracking by Marginal Inference [92.48078680697311]
  ビデオにおける多目的追跡は、隣接するフレーム内のオブジェクト間の1対1の割り当てに関する根本的な問題を解決する必要がある。 本稿では,各オブジェクトの限界確率をリアルタイムに計算する効率的な手法を提案する。 MOT17とMOT20ベンチマークで競合する結果を得る。
  論文  参考訳（メタデータ） (2022-08-07T14:04:45Z)
• Fixed Support Tree-Sliced Wasserstein Barycenter [40.087553363884396]
  本研究では, 固定支持木-ワッセルシュタインバリセンタ (FS-TWB) と呼ばれる木-ワッセルシュタイン距離下のバリセンタと, 固定支持木-スライスされたワッセルシュタインバリセンタ (FS-TSWB) と呼ばれる拡張部を提案する。 FS-TWB と FS-TSWB は,元の Wasserstein バリセンタよりも2桁早く解けることを示す。
  論文  参考訳（メタデータ） (2021-09-08T04:50:33Z)
• Learning High Dimensional Wasserstein Geodesics [55.086626708837635]
  高次元の2つの確率分布の間のワッサーシュタイン測地線を計算するための新しい定式化と学習戦略を提案する。 ラグランジュ乗算器の手法を最適輸送(OT)問題の動的定式化に適用することにより、サドル点がワッサーシュタイン測地線であるミニマックス問題を導出する。 次に、深層ニューラルネットワークによる関数のパラメータ化を行い、トレーニングのためのサンプルベースの双方向学習アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2021-02-05T04:25:28Z)
• Supervised Tree-Wasserstein Distance [21.9998734051455]
  そこで本研究では,木メータに基づく高速かつ教師付きメトリック学習手法であるSupervised Tree-Wasserstein (STW) 距離を提案する。 我々はSTW距離を高速に計算できることを示し、文書分類タスクの精度を向上させる。
  論文  参考訳（メタデータ） (2021-01-27T16:24:51Z)
• On Projection Robust Optimal Transport: Sample Complexity and Model Misspecification [101.0377583883137]
  射影ロバスト(PR)OTは、2つの測度の間のOTコストを最大化するために、射影可能な$k$次元部分空間を選択する。 私たちの最初の貢献は、PRワッサーシュタイン距離のいくつかの基本的な統計的性質を確立することである。 次に、部分空間を最適化するのではなく平均化することにより、PRW距離の代替として積分PRワッサーシュタイン距離(IPRW)を提案する。
  論文  参考訳（メタデータ） (2020-06-22T14:35:33Z)

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

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