論文の概要: Deterministic Iteratively Built KD-Tree with KNN Search for Exact
Applications
- arxiv url: http://arxiv.org/abs/2106.03799v1
- Date: Mon, 7 Jun 2021 17:09:22 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-08 21:26:04.536428
- Title: Deterministic Iteratively Built KD-Tree with KNN Search for Exact
Applications
- Title(参考訳): 厳密な応用のためのKNN探索を用いた決定論的反復構築KD-Tree
- Authors: Aryan Naim, Joseph Bowkett, Sisir Karumanchi, Peyman Tavallali, Brett
Kennedy
- Abstract要約: K-Nearest Neighbors (KNN)サーチは、ロボット工学や自動運転車に応用された人工知能ソフトウェアの基本アルゴリズムである。
二分木と同様に、kd-treesはオンラインアプリケーションに新しいデータが付加され、木が再構築されない限り、検索性能が急速に低下する可能性があるため、不均衡になる。
クエリ結果の正確さを損なうことなく、ツリー再構築の回数を減らす「インターバルkd-treesのフォレスト」を提示する。
- 参考スコア(独自算出の注目度): 2.7325238096808318
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: K-Nearest Neighbors (KNN) search is a fundamental algorithm in artificial
intelligence software with applications in robotics, and autonomous vehicles.
These wide-ranging applications utilize KNN either directly for simple
classification or combine KNN results as input to other algorithms such as
Locally Weighted Learning (LWL). Similar to binary trees, kd-trees become
unbalanced as new data is added in online applications which can lead to rapid
degradation in search performance unless the tree is rebuilt. Although
approximate methods are suitable for graphics applications, which prioritize
query speed over query accuracy, they are unsuitable for certain applications
in autonomous systems, aeronautics, and robotic manipulation where exact
solutions are desired. In this paper, we will attempt to assess the performance
of non-recursive deterministic kd-tree functions and KNN functions. We will
also present a "forest of interval kd-trees" which reduces the number of tree
rebuilds, without compromising the exactness of query results.
- Abstract(参考訳): K-Nearest Neighbors (KNN)サーチは、ロボット工学や自動運転車に応用された人工知能ソフトウェアの基本アルゴリズムである。
これらの広範囲のアプリケーションは、単純な分類のために直接KNNを利用するか、ローカル重み学習(LWL)のような他のアルゴリズムへの入力としてKNN結果を組み合わせる。
二分木と同様に、kd-treesはオンラインアプリケーションに新しいデータが付加され、木が再構築されない限り検索性能が急速に低下する可能性があるため、不均衡になる。
近似手法はクエリの精度よりもクエリの速度を優先するグラフィクスアプリケーションに適しているが、正確な解を求める自律システム、航空学、ロボット操作の特定の応用には適していない。
本稿では,非再帰的決定論的kd-tree関数とKNN関数の性能評価を試みる。
また、クエリ結果の正確性を損なうことなく、ツリー再構築の回数を減らす「間隔kd-treeの森」も提示する。
関連論文リスト
- LiteSearch: Efficacious Tree Search for LLM [70.29796112457662]
本研究では,動的ノード選択とノードレベルの探索予算を備えた新しいガイド付き木探索アルゴリズムを提案する。
GSM8KおよびTabMWPデータセットを用いて行った実験により,本手法はベースライン法に比べて計算コストが大幅に低いことを示した。
論文 参考訳(メタデータ) (2024-06-29T05:14:04Z) - Archtree: on-the-fly tree-structured exploration for latency-aware
pruning of deep neural networks [20.564198591600647]
Archtreeはディープニューラルネットワーク(DNN)の遅延駆動型構造化プルーニングの新しい手法
ターゲットハードウェア上でのオン・ザ・フライの遅延推定を伴い、特定の予算よりも近いレイテンシを考慮に入れます。
実験結果から,Archtreeは従来の最先端手法と比較して,遅延予算の適合性を向上しつつ,オリジナルのモデルの精度を向上することが示された。
論文 参考訳(メタデータ) (2023-11-17T14:24:12Z) - Autonomous Tree-search Ability of Large Language Models [58.68735916408101]
大規模言語モデルは、高度なプロンプト技術で顕著な推論能力に優れています。
近年の研究では、LLMがより困難な推論タスクを解くために受動的木探索を行えるように、検索ロジックを定義するために外部プログラムを活用することが提案されている。
我々は,LLMの自律木探索能力という新しい概念を提案し,正しい解を求める探索軌跡を含む応答を自動生成する。
論文 参考訳(メタデータ) (2023-10-14T14:14:38Z) - Flexible Channel Dimensions for Differentiable Architecture Search [50.33956216274694]
本稿では,効率的な動的チャネル割当アルゴリズムを用いた新しい微分可能なニューラルアーキテクチャ探索法を提案する。
提案するフレームワークは,タスク精度と推論遅延において,従来の手法と等価なDNNアーキテクチャを見つけることができることを示す。
論文 参考訳(メタデータ) (2023-06-13T15:21:38Z) - RELS-DQN: A Robust and Efficient Local Search Framework for
Combinatorial Optimization [11.269582666887324]
本稿では,DQNフレームワークのRELS-DQNを紹介する。
1つのアプリケーションでトレーニングされたRELS-DQNモデルを使用することで、ローカル検索アルゴリズムと既存のDQNモデルの両方に等しい解値を提供することで、様々なアプリケーションに一般化することができる。
論文 参考訳(メタデータ) (2023-04-11T18:01:49Z) - New Linear-time Algorithm for SubTree Kernel Computation based on
Root-Weighted Tree Automata [0.0]
本稿では,SubTreeカーネル計算のための重み付き木オートマトンの概念に基づく線形時間アルゴリズムを提案する。
提案アルゴリズムの主な考え方は、DAGの削減とノードのソートを置き換えることである。
我々のアプローチには3つの大きな利点がある:それは出力に敏感であり、木の種類(順序のない木と順序のない木)に敏感であり、インクリメンタルな木カーネルベースの学習手法によく適応している。
論文 参考訳(メタデータ) (2023-02-02T13:37:48Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-01-07T08:00:02Z) - ISTA-NAS: Efficient and Consistent Neural Architecture Search by Sparse
Coding [86.40042104698792]
スパース符号問題としてニューラルアーキテクチャ探索を定式化する。
実験では、CIFAR-10の2段階法では、検索にわずか0.05GPUしか必要としない。
本手法は,CIFAR-10とImageNetの両方において,評価時間のみのコストで最先端のパフォーマンスを実現する。
論文 参考訳(メタデータ) (2020-10-13T04:34:24Z) - MurTree: Optimal Classification Trees via Dynamic Programming and Search [61.817059565926336]
動的プログラミングと探索に基づいて最適な分類木を学習するための新しいアルゴリズムを提案する。
当社のアプローチでは,最先端技術が必要とする時間のごく一部しか使用せず,数万のインスタンスでデータセットを処理することが可能です。
論文 参考訳(メタデータ) (2020-07-24T17:06:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。