論文の概要: 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距離を正確に近似できることを示した。
関連論文リスト
- 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) - A Riemannian Block Coordinate Descent Method for Computing the
Projection Robust Wasserstein Distance [36.97843660480747]
wasserstein距離は、機械学習とディープラーニングにおいてますます重要になっている。
最近提案された次元の呪いを和らげるためのアプローチは、サンプルデータを低次元の部分空間に投影し、それから投影されたデータ間のワッサーシュタイン距離を計算することである。
しかし、このアプローチは、実際には非常に難しいStiefel多様体上の最大分問題を解決する必要があります。
本研究では,Stiefel多様体上の正規化最大ミン問題の新たな再構成に基づく,この問題を解くための新しいブロック座標降下法(RBCD)を提案する。
論文 参考訳(メタデータ) (2020-12-09T17:47:56Z) - Two-sample Test using Projected Wasserstein Distance: Breaking the Curse
of Dimensionality [15.194516549163245]
統計学と機械学習の基本的な問題である2サンプルテストのための予測されたワッサースタイン距離を開発する。
重要な貢献は、投影された確率分布の間のワッサーシュタイン距離を最大化する低次元線型写像を見つけるために最適射影を結合することである。
論文 参考訳(メタデータ) (2020-10-22T18:08:58Z) - The Unbalanced Gromov Wasserstein Distance: Conic Formulation and
Relaxation [0.0]
距離測度空間(すなわち確率分布を持つ距離空間)を比較することは、多くの機械学習問題の中心である。
そのような距離空間の間の最も一般的な距離は計量測度Gro-Wasserstein (GW) 距離であり、その距離は二次である。
GW の定式化は、任意の正測度を持つ距離空間の比較を等距離まで緩和する。
論文 参考訳(メタデータ) (2020-09-09T12:38:14Z) - 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) - Fast and Robust Comparison of Probability Measures in Heterogeneous
Spaces [62.35667646858558]
本稿では, アンカー・エナジー (AE) とアンカー・ワッサースタイン (AW) 距離を紹介する。
我々の主な貢献は、素案実装が立方体となる対数四重項時間でAEを正確に計算するスイープラインアルゴリズムを提案することである。
AE と AW は,一般的な GW 近似の計算コストのごく一部において,様々な実験環境において良好に動作することを示す。
論文 参考訳(メタデータ) (2020-02-05T03:09:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。