論文の概要: Bridging Arbitrary and Tree Metrics via Differentiable Gromov Hyperbolicity
- arxiv url: http://arxiv.org/abs/2505.21073v2
- Date: Wed, 28 May 2025 09:07:43 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-05-29 12:33:41.788978
- Title: Bridging Arbitrary and Tree Metrics via Differentiable Gromov Hyperbolicity
- Title（参考訳）: 識別可能なGromov双曲性による橋梁・樹木メートル法
- Authors: Pierre Houedry, Nicolas Courty, Florestan Martin-Baillon, Laetitia Chapel, Titouan Vayer,
- Abstract要約: 任意の計量空間が与えられると、ツリー計量からの偏差はグロモフの$delta$-hyperbolicityによって定量化できる。
本稿では,差分最適化フレームワーク DeltaZero を導入し,この問題を解決する。
我々の手法は一貫して最先端の歪みを実現する。
- 参考スコア（独自算出の注目度）: 13.751664797063208
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Trees and the associated shortest-path tree metrics provide a powerful framework for representing hierarchical and combinatorial structures in data. Given an arbitrary metric space, its deviation from a tree metric can be quantified by Gromov's $\delta$-hyperbolicity. Nonetheless, designing algorithms that bridge an arbitrary metric to its closest tree metric is still a vivid subject of interest, as most common approaches are either heuristical and lack guarantees, or perform moderately well. In this work, we introduce a novel differentiable optimization framework, coined DeltaZero, that solves this problem. Our method leverages a smooth surrogate for Gromov's $\delta$-hyperbolicity which enables a gradient-based optimization, with a tractable complexity. The corresponding optimization procedure is derived from a problem with better worst case guarantees than existing bounds, and is justified statistically. Experiments on synthetic and real-world datasets demonstrate that our method consistently achieves state-of-the-art distortion.
- Abstract（参考訳）: ツリーと関連する最短パス木メトリクスは、データの階層構造と組合せ構造を表現するための強力なフレームワークを提供する。
任意の計量空間が与えられると、ツリー計量からの偏差はグロモフの$\delta$-hyperbolicityによって定量化できる。
それでも、任意のメートル法を最も近い木のメートル法にブリッジするアルゴリズムの設計は、ほとんどの一般的なアプローチはヒューリスティックで保証が欠如しているか、あるいは適度にうまく機能しているため、依然として活発な関心の対象である。
本研究では,差分最適化フレームワーク DeltaZero を導入し,この問題を解決する。
提案手法はGromovの$\delta$-hyperbolicityのスムーズなサロゲートを利用する。
対応する最適化手順は、既存の境界よりも最悪の場合の保証が良い問題から導出され、統計的に正当化される。
合成および実世界のデータセットに関する実験は、我々の手法が常に最先端の歪みを達成することを示す。
関連論文リスト
- Fast unsupervised ground metric learning with tree-Wasserstein distance [14.235762519615175]
教師なしの地上距離学習アプローチが導入されました
一つの有望な選択肢はワッサーシュタイン特異ベクトル(WSV)であり、特徴量とサンプルの間の最適な輸送距離を同時に計算する際に現れる。
木にサンプルや特徴を埋め込むことでWSV法を強化し,木-ワッサーシュタイン距離(TWD)を計算することを提案する。
論文 参考訳（メタデータ） (2024-11-11T23:21:01Z) - Free Lunch in the Forest: Functionally-Identical Pruning of Boosted Tree Ensembles [45.962492329047215]
木アンサンブルを原モデルと「機能的に同一」な縮小版にプルークする方法を提案する。
我々は,アンサンブル上での機能的同一プルーニングの問題を形式化し,正確な最適化モデルを導入し,大規模なアンサンブルをプルーする高速かつ高効率な方法を提供する。
論文 参考訳（メタデータ） (2024-08-28T23:15:46Z) - Optimal Transport for Measures with Noisy Tree Metric [29.950797721275574]
木メートル空間上での確率測度に対する最適輸送問題について検討する。
一般に、1つの空間でサポートされている測度であっても、このアプローチは計算が難しい。
我々は、ロバスト OT が計量特性を満たすことを示し、負の定値であることを示す。
論文 参考訳（メタデータ） (2023-10-20T16:56:08Z) - Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
本稿では,2段階の適応性を持つオンライン凸最適化手法を提案する。
我々は$mathcalO(log V_T)$, $mathcalO(d log V_T)$, $hatmathcalO(sqrtV_T)$ regret bounds for strong convex, exp-concave and convex loss function。
論文 参考訳（メタデータ） (2023-07-17T09:55:35Z) - Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。
我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
論文 参考訳（メタデータ） (2023-02-03T03:19:14Z) - Asymmetric Scalable Cross-modal Hashing [51.309905690367835]
クロスモーダルハッシュは、大規模なマルチメディア検索問題を解決する方法として成功している。
これらの問題に対処する新しい非対称スケーラブルクロスモーダルハッシュ(ASCMH)を提案する。
我々のASCMHは、最先端のクロスモーダルハッシュ法よりも精度と効率の点で優れています。
論文 参考訳（メタデータ） (2022-07-26T04:38:47Z) - Tree ensemble kernels for Bayesian optimization with known constraints
over mixed-feature spaces [54.58348769621782]
木アンサンブルはアルゴリズムチューニングやニューラルアーキテクチャ検索といったブラックボックス最適化タスクに適している。
ブラックボックス最適化にツリーアンサンブルを使うことの2つのよく知られた課題は、探索のためのモデル不確実性を効果的に定量化し、また、 (ii) ピースワイドな定値取得関数を最適化することである。
我々のフレームワークは、連続/離散的機能に対する非拘束ブラックボックス最適化のための最先端の手法と同様に、混合変数の特徴空間と既知の入力制約を組み合わせた問題の競合する手法よりも優れている。
論文 参考訳（メタデータ） (2022-07-02T16:59:37Z) - HyperAid: Denoising in hyperbolic spaces for tree-fitting and
hierarchical clustering [36.738414547278154]
双曲空間におけるツリーメトリック・デノイング(HyperAid)に対する新しいアプローチを提案する。
Gromovの$delta$ hyperbolicity($delta$ hyperbolicity)の観点から評価すると、元のデータをツリーのようなデータに変換する。
我々はHyperAidを非負のエッジウェイトを強制するためのスキームに統合する。
論文 参考訳（メタデータ） (2022-05-19T17:33:16Z) - Rethinking Learnable Tree Filter for Generic Feature Transform [71.77463476808585]
Learnable Tree Filterはセマンティックセグメンテーションのためのモデル構造保存関係に対する顕著なアプローチを示す。
幾何学的制約を緩和するために,マルコフ確率場として再構成して解析を行い,学習可能な不定項を導入する。
セマンティックセグメンテーションでは、ベルとホイッスルなしでCityscapesベンチマークでトップパフォーマンス(82.1% mIoU)を達成しています。
論文 参考訳（メタデータ） (2020-12-07T07:16:47Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。