論文の概要: The Central Spanning Tree Problem

• arxiv url: http://arxiv.org/abs/2404.06447v1
• Date: Tue, 9 Apr 2024 16:49:42 GMT
• ステータス: 処理完了
• システム内更新日: 2024-04-10 13:51:47.799419
• Title: The Central Spanning Tree Problem
• Title（参考訳）: 中央スパンニングツリー問題
• Authors: Enrique Fita Sanmartín, Christoph Schnörr, Fred A. Hamprecht,
• Abstract要約: スパンニングツリーは多くのデータ分析タスクにおいて重要なプリミティブであり、データセットをその「骨格」という観点で要約する必要がある。 我々は,(枝分かれした)中央のスパンニングツリーが,データのノイズに対してより頑丈であることを示し,そのスケルトンの観点からデータセットを要約するのに適していることを示す。
• 参考スコア（独自算出の注目度）: 20.14154858576556
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Spanning trees are an important primitive in many data analysis tasks, when a data set needs to be summarized in terms of its "skeleton", or when a tree-shaped graph over all observations is required for downstream processing. Popular definitions of spanning trees include the minimum spanning tree and the optimum distance spanning tree, a.k.a. the minimum routing cost tree. When searching for the shortest spanning tree but admitting additional branching points, even shorter spanning trees can be realized: Steiner trees. Unfortunately, both minimum spanning and Steiner trees are not robust with respect to noise in the observations; that is, small perturbations of the original data set often lead to drastic changes in the associated spanning trees. In response, we make two contributions when the data lies in a Euclidean space: on the theoretical side, we introduce a new optimization problem, the "(branched) central spanning tree", which subsumes all previously mentioned definitions as special cases. On the practical side, we show empirically that the (branched) central spanning tree is more robust to noise in the data, and as such is better suited to summarize a data set in terms of its skeleton. We also propose a heuristic to address the NP-hard optimization problem, and illustrate its use on single cell RNA expression data from biology and 3D point clouds of plants.
• Abstract（参考訳）: スパンニングツリーは多くのデータ解析タスクにおいて重要なプリミティブであり、データセットをその「骨格」という観点で要約する必要がある場合や、下流処理にはすべての観測値に木型のグラフが必要である場合である。 スパンニングツリーの一般的な定義は、最小のスパンニングツリーと最適距離スパンニングツリー、すなわち最小のルーティングコストツリーである。 最も短い枝木を探索するが、分岐点が加わった場合、さらに短い枝木も実現できる。 残念なことに、最小スパンニング木とスタイナー木は観測のノイズに対して頑丈ではない;すなわち、元のデータセットの小さな摂動は、しばしば関連するスパンニング木に劇的な変化をもたらす。 これに対し、ユークリッド空間にデータが存在する場合、2つのコントリビューションを行う: 理論的には、「(分岐した)中央スパンニングツリー」という新しい最適化問題を導入し、前述のすべての定義を特別な場合として仮定する。 実用面では、(枝分かれした)中央スパンニングツリーは、データのノイズに対してより頑丈であり、スケルトンの観点からデータセットを要約するのに適していることを示す。 また,NP-hard 最適化問題に対処するためのヒューリスティックな手法を提案し,生物学および植物の3次元点群からの単一細胞RNA発現データにその使用法を解説した。

関連論文リスト

• Learning a Decision Tree Algorithm with Transformers [75.96920867382859]
  メタ学習によってトレーニングされたトランスフォーマーベースのモデルであるMetaTreeを導入し、強力な決定木を直接生成する。 我々は、多くのデータセットに欲求決定木とグローバルに最適化された決定木の両方を適合させ、MetaTreeを訓練して、強力な一般化性能を実現する木のみを生成する。
  論文  参考訳（メタデータ） (2024-02-06T07:40:53Z)
• Prediction Algorithms Achieving Bayesian Decision Theoretical Optimality Based on Decision Trees as Data Observation Processes [1.2774526936067927]
  本稿では,データの背後にあるデータ観測過程を表現するために木を用いる。 我々は、過度な適合に対して頑健な統計的に最適な予測を導出する。 これをマルコフ連鎖モンテカルロ法により解き、ステップサイズは木の後方分布に応じて適応的に調整される。
  論文  参考訳（メタデータ） (2023-06-12T12:14:57Z)
• 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)
• Spectral Top-Down Recovery of Latent Tree Models [13.681975313065477]
  スペクトルトップダウン・リカバリ (STDR) は、大きな潜在木モデルを推定するための分割・コンカレントアプローチである。 STDRの分割ステップは非ランダムです。 代わりに、観測されたノードに関連する適切なラプラシア行列のFiedlerベクトルに基づいている。 私達はSTDRが統計的に一貫性があることを証明し、高い確率で木を正確に回復するために必要なサンプルの数を縛ります。
  論文  参考訳（メタデータ） (2021-02-26T02:47:42Z)
• Visualizing hierarchies in scRNA-seq data using a density tree-biased autoencoder [50.591267188664666]
  本研究では,高次元scRNA-seqデータから意味のある木構造を同定する手法を提案する。 次に、低次元空間におけるデータのツリー構造を強調する木バイアスオートエンコーダDTAEを紹介する。
  論文  参考訳（メタデータ） (2021-02-11T08:48:48Z)
• 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)
• Growing Deep Forests Efficiently with Soft Routing and Learned Connectivity [79.83903179393164]
  この論文は、いくつかの重要な側面で深い森林のアイデアをさらに拡張します。 我々は、ノードがハードバイナリ決定ではなく、確率的ルーティング決定、すなわちソフトルーティングを行う確率的ツリーを採用する。 MNISTデータセットの実験は、私たちの力のある深部森林が[1]、[3]よりも優れたまたは匹敵するパフォーマンスを達成できることを示しています。
  論文  参考訳（メタデータ） (2020-12-29T18:05:05Z)
• Forest R-CNN: Large-Vocabulary Long-Tailed Object Detection and Instance Segmentation [75.93960390191262]
  我々は、オブジェクトカテゴリ間の関係に関する事前知識を利用して、きめ細かいクラスを粗い親クラスにクラスタリングする。 そこで本研究では,NMS再サンプリング法を提案する。 提案手法はフォレストR-CNNと呼ばれ,ほとんどのオブジェクト認識モデルに適用可能なプラグイン・アンド・プレイモジュールとして機能する。
  論文  参考訳（メタデータ） (2020-08-13T03:52:37Z)
• MurTree: Optimal Classification Trees via Dynamic Programming and Search [61.817059565926336]
  動的プログラミングと探索に基づいて最適な分類木を学習するための新しいアルゴリズムを提案する。 当社のアプローチでは,最先端技術が必要とする時間のごく一部しか使用せず,数万のインスタンスでデータセットを処理することが可能です。
  論文  参考訳（メタデータ） (2020-07-24T17:06:55Z)
• Bounds of the sum of edge lengths in linear arrangements of trees [0.90238471756546]
  特に,固定サイズの木の縁長の和に関する諸問題について検討する。 一次元空間ネットワークにおける最適性スコアの研究のための基盤を確立した。
  論文  参考訳（メタデータ） (2020-06-24T21:53:39Z)

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

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