Fugu-MT 論文翻訳(概要): Fitting trees to $\ell

論文の概要: Fitting trees to $\ell_1$-hyperbolic distances

arxiv url: http://arxiv.org/abs/2409.01010v1
Date: Mon, 2 Sep 2024 07:38:32 GMT
ステータス: 処理完了
システム内更新日: 2024-09-06 07:59:10.376389
Title: Fitting trees to $\ell_1$-hyperbolic distances
Title（参考訳）: 木を$\ell_1$-双曲距離に適合させる
Authors: Joon-Hyeok Yim, Anna C. Gilbert,
Abstract要約: 植物遺伝学的解析において,樹冠形成は重要な要素である。本研究では, 木組込み問題について, 双曲性ベクトルと木組込み誤差の関係について検討する。
参考スコア（独自算出の注目度）: 4.220336689294244
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Building trees to represent or to fit distances is a critical component of phylogenetic analysis, metric embeddings, approximation algorithms, geometric graph neural nets, and the analysis of hierarchical data. Much of the previous algorithmic work, however, has focused on generic metric spaces (i.e., those with no a priori constraints). Leveraging several ideas from the mathematical analysis of hyperbolic geometry and geometric group theory, we study the tree fitting problem as finding the relation between the hyperbolicity (ultrametricity) vector and the error of tree (ultrametric) embedding. That is, we define a vector of hyperbolicity (ultrametric) values over all triples of points and compare the $\ell_p$ norms of this vector with the $\ell_q$ norm of the distortion of the best tree fit to the distances. This formulation allows us to define the average hyperbolicity (ultrametricity) in terms of a normalized $\ell_1$ norm of the hyperbolicity vector. Furthermore, we can interpret the classical tree fitting result of Gromov as a $p = q = \infty$ result. We present an algorithm HCCRootedTreeFit such that the $\ell_1$ error of the output embedding is analytically bounded in terms of the $\ell_1$ norm of the hyperbolicity vector (i.e., $p = q = 1$) and that this result is tight. Furthermore, this algorithm has significantly different theoretical and empirical performance as compared to Gromov's result and related algorithms. Finally, we show using HCCRootedTreeFit and related tree fitting algorithms, that supposedly standard data sets for hierarchical data analysis and geometric graph neural networks have radically different tree fits than those of synthetic, truly tree-like data sets, suggesting that a much more refined analysis of these standard data sets is called for.
Abstract（参考訳）: 植物遺伝学的解析、メートル法埋め込み、近似アルゴリズム、幾何グラフニューラルネット、階層データの解析において、木を構築することは重要な要素である。しかし、それまでのアルゴリズム的な研究の多くは、一般的な距離空間(すなわち、事前制約のないもの)に焦点を当てていた。双曲幾何学と幾何群理論の数学的解析からいくつかのアイデアを取り入れ、木嵌合問題を、双曲性(ウルトラメトリック性)ベクトルと木埋め込みの誤差の関係を見出すものとして研究する。すなわち、すべての点三重項上の双曲性(ultrametric)値のベクトルを定義し、このベクトルの$\ell_p$ノルムと、最良の木の歪みの$\ell_q$ノルムを比較する。この定式化により、双曲性ベクトルの正規化された$\ell_1$ノルムの言葉で平均双曲性 (ultrametricity) を定義することができる。さらに、グロモフの古典的ツリー適合結果は、$p = q = \infty$ resultと解釈できる。出力埋め込みの$\ell_1$エラーが双曲性ベクトルの$\ell_1$ノルム(すなわち$p = q = 1$)で解析的に有界であるようなアルゴリズム HCCRootedTreeFit を提案する。さらに、このアルゴリズムはグロモフの結果や関連するアルゴリズムと比較して、理論的および経験的性能が著しく異なる。最後に、HCCRootedTreeFitと関連する木適合アルゴリズムを用いて、階層型データ解析と幾何グラフニューラルネットワークの標準データセットは、合成された木のようなデータセットと根本的に異なる木適合性を持ち、これらの標準データセットのより洗練された分析が求められていることを示す。

関連論文リスト

Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文参考訳（メタデータ） (2023-08-18T17:52:12Z)
Tight and fast generalization error bound of graph embedding in metric space [54.279425319381374]
非ユークリッド計量空間へのグラフ埋め込みは、既存の有界よりもはるかに少ない訓練データを持つユークリッド空間におけるグラフ埋め込みよりも優れていることを示す。我々の新しい上限は、既存の上限よりもかなり強く速く、最大で$R$と$O(frac1S)$に指数関数できる。
論文参考訳（メタデータ） (2023-05-13T17:29:18Z)
Random graph matching at Otter's threshold via counting chandeliers [16.512416293014493]
そこで本研究では,各木に根付いた重み付き木を数えることで構築した類似度スコアに基づく,グラフマッチングの効率的なアルゴリズムを提案する。これは、明示的な一定の相関で成功し、スパースグラフと密度グラフの両方に適用する最初のグラフマッチングアルゴリズムである。
論文参考訳（メタデータ） (2022-09-25T20:00:28Z)
Near-optimal fitting of ellipsoids to random points [68.12685213894112]
楕円体をランダムな点に合わせるという基本的な問題は、低ランク行列分解、独立成分分析、主成分分析に関係している。我々はこの予想を、ある$n = Omega(, d2/mathrmpolylog(d))$ に対する適合楕円体を構成することで対数的因子まで解決する。我々の証明は、ある非標準確率行列の便利な分解を用いて、サンダーソン等最小二乗構成の実現可能性を示す。
論文参考訳（メタデータ） (2022-08-19T18:00:34Z)
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)
Active-LATHE: An Active Learning Algorithm for Boosting the Error Exponent for Learning Homogeneous Ising Trees [75.93186954061943]
我々は、$rho$が少なくとも0.8$である場合に、エラー指数を少なくとも40%向上させるアルゴリズムを設計し、分析する。我々の分析は、グラフの一部により多くのデータを割り当てるために、微小だが検出可能なサンプルの統計的変動を巧みに活用することに基づいている。
論文参考訳（メタデータ） (2021-10-27T10:45:21Z)
Decentralized Learning of Tree-Structured Gaussian Graphical Models from Noisy Data [1.52292571922932]
本稿では,木構造ガウス図形モデル(GGM)の雑音データからの分散学習について検討する。 GGMは遺伝子制御ネットワークやソーシャルネットワークのような複雑なネットワークをモデル化するために広く利用されている。提案した分散学習では,木構造GGMの推定にChow-Liuアルゴリズムを用いる。
論文参考訳（メタデータ） (2021-09-22T10:41:18Z)
Unfolding Projection-free SDP Relaxation of Binary Graph Classifier via GDPA Linearization [59.87663954467815]
アルゴリズムの展開は、モデルベースのアルゴリズムの各イテレーションをニューラルネットワーク層として実装することにより、解釈可能で類似のニューラルネットワークアーキテクチャを生成する。本稿では、Gershgorin disc perfect alignment (GDPA)と呼ばれる最近の線形代数定理を利用して、二進グラフの半定値プログラミング緩和(SDR)のためのプロジェクションフリーアルゴリズムをアンロールする。実験結果から,我々の未学習ネットワークは純粋モデルベースグラフ分類器よりも優れ,純粋データ駆動ネットワークに匹敵する性能を示したが,パラメータははるかに少なかった。
論文参考訳（メタデータ） (2021-09-10T07:01:15Z)
SGA: A Robust Algorithm for Partial Recovery of Tree-Structured Graphical Models with Noisy Samples [75.32013242448151]
ノードからの観測が独立しているが非識別的に分散ノイズによって破損した場合、Ising Treeモデルの学習を検討する。 Katiyarら。 (2020) は, 正確な木構造は復元できないが, 部分木構造を復元できることを示した。統計的に堅牢な部分木回復アルゴリズムであるSymmetrized Geometric Averaging(SGA)を提案する。
論文参考訳（メタデータ） (2021-01-22T01:57:35Z)
Tree! I am no Tree! I am a Low Dimensional Hyperbolic Embedding [7.381113319198104]
本稿では,メタボリック・ファースト・アプローチを用いて,双曲表現を学習する新しい手法について検討する。低次元の双曲的埋め込みを直接決定するのではなく、データ上の木構造を学習する。この木構造は、双曲多様体に埋め込まれた階層的な情報を抽出するために直接使用できる。
論文参考訳（メタデータ） (2020-05-08T04:30:21Z)
Explainable $k$-Means and $k$-Medians Clustering [25.513261099927163]
我々は、小さな決定木を使ってデータセットをクラスタに分割し、クラスタを直接的な方法で特徴付けることを検討する。一般的なトップダウン決定木アルゴリズムが任意のコストでクラスタリングに繋がる可能性があることを示す。我々は、$k$の葉を持つ木を用いて説明可能なクラスタを生成する効率的なアルゴリズムを設計する。
論文参考訳（メタデータ） (2020-02-28T04:21:53Z)

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

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