論文の概要: Learning Ultrametric Trees for Optimal Transport Regression

• arxiv url: http://arxiv.org/abs/2210.12288v1
• Date: Fri, 21 Oct 2022 22:54:42 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-25 18:03:52.854552
• Title: Learning Ultrametric Trees for Optimal Transport Regression
• Title（参考訳）: 最適輸送回帰のためのUltrametric Treesの学習
• Authors: Samantha Chen, Puoya Tabaghi, Yusu Wang
• Abstract要約: 本稿では,与えられた離散距離空間に対して最適な木構造を求める。 私たちのキーとなるアイデアの1つは、問題を超測度空間に配置することである。 最適化中、パラメータを階層最小分散木アルゴリズムにより超測度空間に投影する。
• 参考スコア（独自算出の注目度）: 14.251232932408804
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Optimal transport provides a metric which quantifies the dissimilarity between probability measures. For measures supported in discrete metric spaces, finding optimal transport distance has cubic time complexity in the size of the space. However, measures supported on trees admit a closed-form optimal transport which can be computed in linear time. In this paper, we aim to find an optimal tree structure for a given discrete metric space, so that the tree-Wasserstein distance can best approximate the optimal transport distance in the original space. One of our key ideas is to cast the problem in ultrametric spaces. This helps define different tree structures and allows us to optimize the tree structure via projected gradient decent over space of ultrametric matrices. During optimization, we project the parameters to the ultrametric space via a hierarchical minimum spanning tree algorithm. Experimental results on real datasets show that our approach outperforms previous approaches in approximating optimal transport distances. Finally, experiments on synthetic data generated on ground truth trees show that our algorithm can accurately uncover the underlying tree metrics.
• Abstract（参考訳）: 最適輸送は、確率測度間の相似性を定量化する計量を提供する。 離散距離空間で支持される測度に対して、最適な移動距離を求めることは空間の大きさにおいて立方体の時間複雑性を持つ。 しかし、木に支えられた測度は、線形時間で計算できる閉形式の最適輸送を許容する。 本稿では,与えられた離散距離空間に対する最適木構造を求め,木-ワッセルシュタイン距離を元の空間における最適輸送距離に最も近いものにすることを目的とする。 私たちのキーとなるアイデアの1つは、問題を超測度空間に配置することである。 これは、異なる木構造を定義するのに役立ち、超計量行列の空間上に適度に投影された勾配を通して木構造を最適化できる。 最適化では,階層的最小スパンディングツリーアルゴリズムを用いてパラメータを超メトリック空間に投影する。 実データを用いた実験の結果, 提案手法は, 最適移動距離を近似する従来のアプローチよりも優れていることがわかった。 最後に、地上の真理木から生成された合成データ実験により、我々のアルゴリズムが根底にある木の指標を正確に発見できることが示されている。

関連論文リスト

• Fast unsupervised ground metric learning with tree-Wasserstein distance [14.235762519615175]
  教師なしの地上距離学習アプローチが導入されました 木にサンプルや特徴を埋め込むことでWSV法を強化し,木-ワッサーシュタイン距離(TWD)を計算することを提案する。 我々は、このアルゴリズムが最もよく知られた方法よりも完全なWSVアプローチの近似に収束し、$mathcalO(n3)$複雑さを持つことを理論的かつ経験的に実証する。
  論文  参考訳（メタデータ） (2024-11-11T23:21:01Z)
• Linearized Wasserstein dimensionality reduction with approximation guarantees [65.16758672591365]
  LOT Wassmap は、ワーッサーシュタイン空間の低次元構造を明らかにするための計算可能なアルゴリズムである。 我々は,LOT Wassmapが正しい埋め込みを実現し,サンプルサイズの増加とともに品質が向上することを示す。 また、LOT Wassmapがペア距離計算に依存するアルゴリズムと比較して計算コストを大幅に削減することを示す。
  論文  参考訳（メタデータ） (2023-02-14T22:12:16Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。 本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
  論文  参考訳（メタデータ） (2023-01-30T15:46:39Z)
• Geodesic Sinkhorn for Fast and Accurate Optimal Transport on Manifolds [53.110934987571355]
  多様体グラフ上の熱核に基づく測地学的シンクホーンを提案する。 化学療法中の患者試料からの高次元単細胞データの複数分布のバリセンタの計算に本法を適用した。
  論文  参考訳（メタデータ） (2022-11-02T00:51:35Z)
• Efficient Non-Parametric Optimizer Search for Diverse Tasks [93.64739408827604]
  興味のあるタスクを直接検索できる,スケーラブルで汎用的なフレームワークを初めて提示する。 基礎となる数学表現の自然木構造に着想を得て、空間を超木に再配置する。 我々は,モンテカルロ法を木探索に適用し,レジェクションサンプリングと等価形状検出を備える。
  論文  参考訳（メタデータ） (2022-09-27T17:51:31Z)
• Tree ensemble kernels for Bayesian optimization with known constraints over mixed-feature spaces [54.58348769621782]
  木アンサンブルはアルゴリズムチューニングやニューラルアーキテクチャ検索といったブラックボックス最適化タスクに適している。 ブラックボックス最適化にツリーアンサンブルを使うことの2つのよく知られた課題は、探索のためのモデル不確実性を効果的に定量化し、また、 (ii) ピースワイドな定値取得関数を最適化することである。 我々のフレームワークは、連続/離散的機能に対する非拘束ブラックボックス最適化のための最先端の手法と同様に、混合変数の特徴空間と既知の入力制約を組み合わせた問題の競合する手法よりも優れている。
  論文  参考訳（メタデータ） (2022-07-02T16:59:37Z)
• Near-optimal estimation of smooth transport maps with kernel sums-of-squares [81.02564078640275]
  滑らかな条件下では、2つの分布の間の正方形ワッサーシュタイン距離は、魅力的な統計的誤差上界で効率的に計算できる。 生成的モデリングのような応用への関心の対象は、基礎となる最適輸送写像である。 そこで本研究では,地図上の統計的誤差であるL2$が,既存のミニマックス下限値とほぼ一致し,スムーズな地図推定が可能となる最初のトラクタブルアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-12-03T13:45:36Z)
• Entropic estimation of optimal transport maps [15.685006881635209]
  厳密な有限サンプル保証付き$mathbbRd$上の2つの分布間の最適写像を推定する手法を開発する。 我々は,Sinkhornのアルゴリズムを用いて,推定器の計算が容易であることを示す。
  論文  参考訳（メタデータ） (2021-09-24T14:57:26Z)
• Optimal Decision Trees for Nonlinear Metrics [42.18286681448184]
  本稿では,非線形メトリクスに対して最適な木を生成するための新しいアルゴリズムを提案する。 我々の知る限りでは、これは非線形メトリクスに対して証明可能な最適決定木を計算するための最初の方法である。 当社のアプローチは、線形メトリクスの最適化と比較した場合、トレードオフにつながります。
  論文  参考訳（メタデータ） (2020-09-15T08:30:56Z)
• Fast Unbalanced Optimal Transport on a Tree [40.60905158071766]
  本研究では、アルゴリズムの観点から、不均衡な最適輸送問題の時間的複雑さを初めて考察する。 ユークリッド計量におけるカントロヴィチ・ルビンシテイン距離と最適部分輸送が強い四進時間では計算できないことを証明した。 そこで本研究では,木メータ上での準線形時間において,より一般的な不均衡な最適輸送問題を正確に解くアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-04T08:43:59Z)
• A Practical Index Structure Supporting Fr\'echet Proximity Queries Among Trajectories [1.9335262420787858]
  我々は、計算コストの高いメトリクスの下で、レンジと近隣クエリに$k$のスケーラブルなアプローチを提案する。 計量指標のクラスタリングに基づいて,軌跡数に線形な木構造を求める。 本研究では,多種多様な合成および実世界のデータセットに関する広範な実験により,本手法の有効性と有効性について分析する。
  論文  参考訳（メタデータ） (2020-05-28T04:12:43Z)

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

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