Fugu-MT 論文翻訳(概要): On the Power of Learning-Augmented Search Trees

論文の概要: On the Power of Learning-Augmented Search Trees

arxiv url: http://arxiv.org/abs/2211.09251v3
Date: Thu, 15 May 2025 04:46:39 GMT
ステータス: 翻訳完了
システム内更新日: 2025-05-16 22:29:05.921963
Title: On the Power of Learning-Augmented Search Trees
Title（参考訳）: 学習強化探索木の力について
Authors: Jingbang Chen, Xinyuan Cao, Alicia Stepin, Li Chen,
Abstract要約: 本稿では,Treapsを用いた学習強化二分探索木(BST)について,慎重に設計した優先順位で検討する。その結果、各項目の深さが予測重量$w_x$によって決定される単純な探索木となる。
参考スコア（独自算出の注目度）: 7.325724756104182
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We study learning-augmented binary search trees (BSTs) via Treaps with carefully designed priorities. The result is a simple search tree in which the depth of each item $x$ is determined by its predicted weight $w_x$. Specifically, each item $x$ is assigned a composite priority of $-\lfloor\log\log(1/w_x)\rfloor + U(0, 1)$ where $U(0, 1)$ is the uniform random variable. By choosing $w_x$ as the relative frequency of $x$, the resulting search trees achieve static optimality. This approach generalizes the recent learning-augmented BSTs [Lin-Luo-Woodruff ICML '22], which only work for Zipfian distributions, by extending them to arbitrary input distributions. Furthermore, we demonstrate that our method can be generalized to a B-Tree data structure using the B-Treap approach [Golovin ICALP '09]. Our search trees are also capable of leveraging localities in the access sequence through online self-reorganization, thereby achieving the working-set property. Additionally, they are robust to prediction errors and support dynamic operations, such as insertions, deletions, and prediction updates. We complement our analysis with an empirical study, demonstrating that our method outperforms prior work and classic data structures.
Abstract（参考訳）: 本稿では,Treapsを用いた学習強化二分探索木(BST)について,慎重に設計した優先順位で検討する。その結果、各項目の深さが予測重量$w_x$によって決定される単純な探索木となる。具体的には、$x$は$-\lfloor\log\log(1/w_x)\rfloor + U(0, 1)$である。 w_x$ を $x$ の相対周波数として選ぶことで、結果の探索木は静的な最適性を達成する。この手法は, Zipfian分布にのみ対応し, 任意の入力分布に拡張することで, 最近の学習強化BST(Lin-Luo-Woodruff ICML '22]を一般化する。さらに,B-Trreapアプローチ [Golovin ICALP '09] を用いてB-Treeデータ構造に一般化できることを実証した。検索ツリーは, アクセスシーケンスの局所性を, オンラインの自己組織化によって活用し, ワークセット特性を達成できる。さらに、エラーを予測し、挿入、削除、予測更新などの動的操作をサポートする。我々は,本手法が先行研究や古典的データ構造より優れていることを示す実証的研究で分析を補完する。

関連論文リスト

Don't Get Lost in the Trees: Streamlining LLM Reasoning by Overcoming Tree Search Exploration Pitfalls [83.89771461061903]
検証者による木探索アルゴリズムの最近の進歩は、大規模言語モデル(LLM)の推論能力を大幅に向上させた。検証者による木探索アルゴリズムの最近の進歩は、大規模言語モデル(LLM)の推論能力を大幅に向上させた。意味論的に等価なコンテンツを持つ冗長な状態による$textitover-Exploration$と、検証器のスコアリングにおける高いばらつきに起因する$textitunder-Exploration$である。各種木探索アルゴリズムに適合するフレキシブルなプラグアンドプレイシステムであるFETCHを提案する。
論文参考訳（メタデータ） (2025-02-16T16:12:01Z)
Statistical-Computational Trade-offs for Density Estimation [60.81548752871115]
幅広い種類のデータ構造に対して、それらの境界は著しく改善されないことを示す。これは密度推定のための新しい統計計算トレードオフである。
論文参考訳（メタデータ） (2024-10-30T15:03:33Z)
Learning Tree Pattern Transformations [5.767156832161818]
ツリー$t$が別のツリー$t*$と構造的に異なる理由と理由を説明することは、コンピュータサイエンス全体で遭遇する問題である。本稿では,サンプルデータから木組間の構造的差異を説明する方法について考察する。
論文参考訳（メタデータ） (2024-10-10T08:20:57Z)
LiteSearch: Efficacious Tree Search for LLM [70.29796112457662]
本研究では,動的ノード選択とノードレベルの探索予算を備えた新しいガイド付き木探索アルゴリズムを提案する。 GSM8KおよびTabMWPデータセットを用いて行った実験により,本手法はベースライン法に比べて計算コストが大幅に低いことを示した。
論文参考訳（メタデータ） (2024-06-29T05:14:04Z)
Turnstile $\ell_p$ leverage score sampling with applications [56.403488578703865]
我々は,行列$AinmathbbRntimes d$の行をサンプリングする新しいアルゴリズムを開発した。我々のアルゴリズムはサンプル行インデックスのセットを返すだけでなく、わずかに乱れた行を $tildea_i approx a_i$ で返却し、サンプリング確率を $varepsilon$ の相対誤差に近似する。ロジスティック回帰のために、我々のフレームワークは$を達成した最初のアルゴリズムを得る。
論文参考訳（メタデータ） (2024-06-01T07:33:41Z)
End-to-end Feature Selection Approach for Learning Skinny Trees [13.388576838688202]
木アンサンブルにおける特徴選択のための最適化に基づく新しい手法を提案する。 Skinny Treesは、ツリーアンサンブルの機能選択のためのエンドツーエンドツールキットである。
論文参考訳（メタデータ） (2023-10-28T00:15:10Z)
On Computing Optimal Tree Ensembles [7.424944196676223]
ランダム林や、より一般的には(決定ノブレイクダッシュ-)ツリーアンサンブルは、分類と回帰の方法として広く使われている。最近のアルゴリズムの進歩は、そのサイズや深さなどの様々な測定に最適な決定木を計算することができる。 2つの新しいアルゴリズムと対応する下位境界を提供する。
論文参考訳（メタデータ） (2023-06-07T13:30:43Z)
The Effect of Points Dispersion on the $k$-nn Search in Random Projection Forests [1.376408511310322]
パーティショニングツリーは、$k$-nearest 隣のサーチのための効率的なデータ構造である。 $k$d-treesはベクトル量子化(VQ)誤差を減らすためにより多くの木レベルを必要とするため、高次元では非効率である。木が多くなると、点の分散は$k$-nn 探索に非常に限定的な影響を及ぼす。
論文参考訳（メタデータ） (2023-02-25T20:57:06Z)
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)
List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
高次元におけるリストデコタブル平均推定の基本的な課題について検討する。我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
論文参考訳（メタデータ） (2020-11-19T17:21:37Z)
Decision trees as partitioning machines to characterize their generalization properties [2.370481325034443]
データの分割の観点から、実値の特徴について二分決定木を再検討する。内部ノードが$N$である二分木構造のVC次元が$N log(Nell)$であることを示す。我々は,これらの結果に基づいて,多数のデータセット上でのCARTアルゴリズムよりも優れたプルーニングアルゴリズムを詳述する。
論文参考訳（メタデータ） (2020-10-14T19:25:58Z)
On $\ell_p$-norm Robustness of Ensemble Stumps and Trees [83.81523991945018]
我々は,アンサンブルスタンプの音響検証のための効率的なプログラムベースアルゴリズムを開発した。我々は,アンサンブル・スタンプや木を訓練するための最初の認証された防御法を,$ell_p$ノルム摂動に関して実証した。
論文参考訳（メタデータ） (2020-08-20T03:42:40Z)

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

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