論文の概要: Combinatorial and computational investigations of Neighbor-Joining bias

• arxiv url: http://arxiv.org/abs/2007.09345v3
• Date: Wed, 16 Sep 2020 20:54:55 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-09 05:34:07.336188
• Title: Combinatorial and computational investigations of Neighbor-Joining bias
• Title（参考訳）: 隣り合うバイアスの組合せおよび計算的研究
• Authors: Ruth Davidson and Abraham Martin del Campo
• Abstract要約: Neighbor-Joiningアルゴリズムは、生物学的データから生じる相同性マップから木の計量を計算する。 これらの地域についての完全な記述はまだ見つかっていない。 隣り合う集合の異なる配列は、同じ木を生成することができ、したがって複数の幾何学的領域を同じ出力に関連付ける。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Neighbor-Joining algorithm is a popular distance-based phylogenetic method that computes a tree metric from a dissimilarity map arising from biological data. Realizing dissimilarity maps as points in Euclidean space, the algorithm partitions the input space into polyhedral regions indexed by the combinatorial type of the trees returned. A full combinatorial description of these regions has not been found yet; different sequences of Neighbor-Joining agglomeration events can produce the same combinatorial tree, therefore associating multiple geometric regions to the same algorithmic output. We resolve this confusion by defining agglomeration orders on trees, leading to a bijection between distinct regions of the output space and weighted Motzkin paths. As a result, we give a formula for the number of polyhedral regions depending only on the number of taxa. We conclude with a computational comparison between these polyhedral regions, to unveil biases introduced in any implementation of the algorithm.
• Abstract（参考訳）: 隣り合うアルゴリズムは、生物データから生じる相似性マップからツリーメトリックを計算する一般的な距離に基づく系統解析手法である。 ユークリッド空間の点としての異性写像を実現するアルゴリズムは、入力空間を木の組み合わせ型によってインデックスされた多面体領域に分割する。 これらの領域の完全な組合せ記述はまだ見つかっていないが、近傍に結合する凝集イベントの異なる配列が同じ組合せ木を生成できるため、複数の幾何領域を同じアルゴリズム出力に関連付けることができる。 木上の凝集順序を定義することでこの混乱を解消し、出力空間の異なる領域と重み付きモツキン経路の間の単射をもたらす。 その結果,分類数にのみ依存する多面体領域数の式が得られた。 我々は,これらの多面体領域間の計算比較を行い,アルゴリズムの実装に現れるバイアスを明らかにする。

関連論文リスト

• LiteSearch: Efficacious Tree Search for LLM [70.29796112457662]
  本研究では,動的ノード選択とノードレベルの探索予算を備えた新しいガイド付き木探索アルゴリズムを提案する。 GSM8KおよびTabMWPデータセットを用いて行った実験により,本手法はベースライン法に比べて計算コストが大幅に低いことを示した。
  論文  参考訳（メタデータ） (2024-06-29T05:14:04Z)
• Boundary Detection Algorithm Inspired by Locally Linear Embedding [8.259071011958254]
  本稿では,広く使用されている局所的線形埋め込みアルゴリズムにインスパイアされた境界点検出手法を提案する。 本手法は,2つの近傍探索スキーム($epsilon$-radius ball scheme)と$K$-nearest neighbor scheme($K$-nearest neighbor scheme)を用いて実装する。
  論文  参考訳（メタデータ） (2024-06-26T16:05:57Z)
• Hierarchical Clustering via Local Search [0.0]
  階層クラスタリングのための局所探索アルゴリズムを提案する。 任意の局所最適木は少なくとも$fracn-23sum_i jw(i,j)$の収益を保証し、そこでは$n$はオブジェクトの数で、$w: [n] times [n] mathbbR+$は関連する類似関数である。
  論文  参考訳（メタデータ） (2024-05-24T23:46:24Z)
• Optimal estimation of Gaussian (poly)trees [25.02920605955238]
  分布学習(KL距離)と構造学習(正確な回復)の両問題を考察する。 最初のアプローチはChow-Liuアルゴリズムに基づいており、最適な木構造分布を効率的に学習する。 第2のアプローチは、制約に基づく構造学習のための条件付き独立試験器として部分相関を用いたポリツリーに対するPCアルゴリズムの修正である。
  論文  参考訳（メタデータ） (2024-02-09T12:58:36Z)
• An Optimal Algorithm for the Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [65.268245109828]
  多武装バンディット(R-CPE-MAB)の真価純探査問題について検討する。 既存のR-CPE-MABの手法は、いわゆるトランスダクティブ線形帯域の特殊な場合と見なすことができる。 本稿では,差分探索アルゴリズム (CombGapE) を提案する。
  論文  参考訳（メタデータ） (2023-06-15T15:37:31Z)
• Linearized Wasserstein dimensionality reduction with approximation guarantees [65.16758672591365]
  LOT Wassmap は、ワーッサーシュタイン空間の低次元構造を明らかにするための計算可能なアルゴリズムである。 我々は,LOT Wassmapが正しい埋め込みを実現し,サンプルサイズの増加とともに品質が向上することを示す。 また、LOT Wassmapがペア距離計算に依存するアルゴリズムと比較して計算コストを大幅に削減することを示す。
  論文  参考訳（メタデータ） (2023-02-14T22:12:16Z)
• Algorithmic Determination of the Combinatorial Structure of the Linear Regions of ReLU Neural Networks [0.0]
  正準多面体のすべての次元の領域と面を決定する。 この全標準構造を計算するアルゴリズムを提案する。 得られたアルゴリズムは、中間ニューロンの数に時間とともに数値的に安定し、すべての次元にわたって正確な情報を得る。
  論文  参考訳（メタデータ） (2022-07-15T18:36:12Z)
• Exact and Approximate Hierarchical Clustering Using A* [51.187990314731344]
  クラスタリングのA*探索に基づく新しいアプローチを紹介します。 A*と新しいエンフォレリスデータ構造を組み合わせることで、禁止的に大きな検索空間を克服します。 実験により,本手法は粒子物理利用事例や他のクラスタリングベンチマークにおいて,ベースラインよりもかなり高品質な結果が得られることを示した。
  論文  参考訳（メタデータ） (2021-04-14T18:15:27Z)
• Partition-based formulations for mixed-integer optimization of trained ReLU neural networks [66.88252321870085]
  本稿では,訓練されたReLUニューラルネットワークのための混合整数式について紹介する。 1つの極端な場合、入力毎に1つのパーティションがノードの凸殻、すなわち各ノードの最も厳密な可能な定式化を回復する。
  論文  参考訳（メタデータ） (2021-02-08T17:27:34Z)
• Convex Polytope Trees [57.56078843831244]
  コンベックスポリトープ木(CPT)は、決定境界の解釈可能な一般化によって決定木の系統を拡張するために提案される。 木構造が与えられたとき,木パラメータに対するCPTおよび拡張性のあるエンドツーエンドトレーニングアルゴリズムを効率的に構築する。
  論文  参考訳（メタデータ） (2020-10-21T19:38:57Z)
• Data Structures & Algorithms for Exact Inference in Hierarchical Clustering [41.24805506595378]
  本稿では,新しいトレリスデータ構造に基づく階層クラスタリングにおける表現型推論のための動的プログラミングアルゴリズムを提案する。 我々のアルゴリズムは時間と空間に比例してN$要素のパワーセットをスケールし、これは(2N-3)! 可能な階層のそれぞれを明示的に考慮するよりも指数関数的に効率的である。
  論文  参考訳（メタデータ） (2020-02-26T17:43:53Z)

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

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