論文の概要: The Effect of Points Dispersion on the $k$-nn Search in Random Projection Forests

• arxiv url: http://arxiv.org/abs/2302.13160v1
• Date: Sat, 25 Feb 2023 20:57:06 GMT
• ステータス: 処理完了
• システム内更新日: 2023-02-28 18:40:11.919171
• Title: The Effect of Points Dispersion on the $k$-nn Search in Random Projection Forests
• Title（参考訳）: ランダム投影林における点分散が$k$-nn探索に及ぼす影響
• Authors: Mashaan Alshammari, John Stavrakakis, Adel F. Ahmed, Masahiro Takatsuka
• Abstract要約: パーティショニングツリーは、$k$-nearest 隣のサーチのための効率的なデータ構造である。 $k$d-treesはベクトル量子化(VQ)誤差を減らすためにより多くの木レベルを必要とするため、高次元では非効率である。 木が多くなると、点の分散は$k$-nn 探索に非常に限定的な影響を及ぼす。
• 参考スコア（独自算出の注目度）: 1.376408511310322
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Partitioning trees are efficient data structures for $k$-nearest neighbor search. Machine learning libraries commonly use a special type of partitioning trees called $k$d-trees to perform $k$-nn search. Unfortunately, $k$d-trees can be ineffective in high dimensions because they need more tree levels to decrease the vector quantization (VQ) error. Random projection trees rpTrees solve this scalability problem by using random directions to split the data. A collection of rpTrees is called rpForest. $k$-nn search in an rpForest is influenced by two factors: 1) the dispersion of points along the random direction and 2) the number of rpTrees in the rpForest. In this study, we investigate how these two factors affect the $k$-nn search with varying $k$ values and different datasets. We found that with larger number of trees, the dispersion of points has a very limited effect on the $k$-nn search. One should use the original rpTree algorithm by picking a random direction regardless of the dispersion of points.
• Abstract（参考訳）: 分割木は、$k$-nearest neighbor searchのための効率的なデータ構造である。 機械学習ライブラリは通常、$k$d-treesと呼ばれる特別な種類のパーティショニングツリーを使用して、$k$-nn検索を実行する。 残念ながら、$k$d-treesはベクトル量子化(VQ)誤差を減らすためにより多くの木レベルを必要とするため、高次元では非効率である。 ランダム射影木rptreesは、ランダム方向を使ってデータを分割することでこのスケーラビリティ問題を解決する。 rpTreesのコレクションはrpForestと呼ばれる。 rpForestの$k$-nn検索には2つの要因がある。 1)無作為な方向に沿った点の分散 2)rpForestにおけるrpTreeの数。 本研究では,これらの2つの要因が,異なる$k$値と異なるデータセットを持つ$k$-nn探索に与える影響について検討した。 木の数が多ければ多いほど、点の分散が$k$-nnの検索に非常に限定的な効果を持つことがわかった。 点の分散に関係なくランダムな方向を選択することで、元のrpTreeアルゴリズムを使うべきである。

関連論文リスト

• LiteSearch: Efficacious Tree Search for LLM [70.29796112457662]
  本研究では,動的ノード選択とノードレベルの探索予算を備えた新しいガイド付き木探索アルゴリズムを提案する。 GSM8KおよびTabMWPデータセットを用いて行った実験により,本手法はベースライン法に比べて計算コストが大幅に低いことを示した。
  論文  参考訳（メタデータ） (2024-06-29T05:14:04Z)
• Learning a Decision Tree Algorithm with Transformers [75.96920867382859]
  メタ学習によってトレーニングされたトランスフォーマーベースのモデルであるMetaTreeを導入し、強力な決定木を直接生成する。 我々は、多くのデータセットに欲求決定木とグローバルに最適化された決定木の両方を適合させ、MetaTreeを訓練して、強力な一般化性能を実現する木のみを生成する。
  論文  参考訳（メタデータ） (2024-02-06T07:40:53Z)
• On Computing Optimal Tree Ensembles [7.424944196676223]
  ランダム林や、より一般的には(決定ノブレイクダッシュ-)ツリーアンサンブルは、分類と回帰の方法として広く使われている。 最近のアルゴリズムの進歩は、そのサイズや深さなどの様々な測定に最適な決定木を計算することができる。 2つの新しいアルゴリズムと対応する下位境界を提供する。
  論文  参考訳（メタデータ） (2023-06-07T13:30:43Z)
• Random projection tree similarity metric for SpectralNet [1.376408511310322]
  SpectralNetは、ニューラルネットワークを使用してデータを分離する埋め込みを見つけるグラフクラスタリング手法である。 我々はランダムプロジェクションツリー(rpTrees)に基づく新しいスペクトルネット類似度指標を提案した。 実験の結果, SpectralNet は rpTree 類似度を用いたクラスタリング精度が$k$-nn グラフと比較できることがわかった。
  論文  参考訳（メタデータ） (2023-02-25T21:32:16Z)
• Learning-Augmented B-Trees [11.542679443281411]
  本研究は,Treapsを用いたBST(Learning-augmented binary search tree)とB-Trees(B-Trees)を複合優先度で検討する。 その結果、各項目の深さが予測重量$w_x$で決定される単純な探索木となる。
  論文  参考訳（メタデータ） (2022-11-16T22:50:40Z)
• Unbiased and Efficient Sampling of Dependency Trees [0.0]
  ほとんどのツリーバンクは、すべての有効な依存ツリーがROOTノードから出てくる単一のエッジを持つ必要がある。 Zmigrodらは最近、単一ルート依存ツリーの分布から置き換えることなくサンプリングするアルゴリズムを提案している。 我々は、Wilson-RCを置換したサンプリングアルゴリズムが実際にバイアスを受けていることを示す。
  論文  参考訳（メタデータ） (2022-05-25T09:57:28Z)
• Shallow decision trees for explainable $k$-means clustering [1.2891210250935146]
  決定木内の葉の深さに関連する指標を考慮に入れた効率的なアルゴリズムを提案する。 16個のデータセットの実験において,本アルゴリズムは決定木クラスタリングアルゴリズムよりも優れた結果が得られる。
  論文  参考訳（メタデータ） (2021-12-29T18:22:28Z)
• 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)
• 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)
• An Efficient Adversarial Attack for Tree Ensembles [91.05779257472675]
  傾斜促進決定木(DT)や無作為林(RF)などの木に基づくアンサンブルに対する敵対的攻撃 提案手法は,従来のMILP (Mixed-integer linear programming) よりも数千倍高速であることを示す。 私たちのコードはhttps://chong-z/tree-ensemble- attackで利用可能です。
  論文  参考訳（メタデータ） (2020-10-22T10:59:49Z)

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

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