Fugu-MT 論文翻訳(概要): Learning-Augmented B-Trees

論文の概要: Learning-Augmented B-Trees

arxiv url: http://arxiv.org/abs/2211.09251v2
Date: Mon, 24 Jul 2023 07:08:59 GMT
ステータス: 処理完了
システム内更新日: 2023-07-26 00:31:19.586031
Title: Learning-Augmented B-Trees
Title（参考訳）: 学習型b木
Authors: Xinyuan Cao, Jingbang Chen, Li Chen, Chris Lambert, Richard Peng, Daniel Sleator
Abstract要約: 本研究は,Treapsを用いたBST(Learning-augmented binary search tree)とB-Trees(B-Trees)を複合優先度で検討する。その結果、各項目の深さが予測重量$w_x$で決定される単純な探索木となる。
参考スコア（独自算出の注目度）: 11.542679443281411
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We study learning-augmented binary search trees (BSTs) and B-Trees via Treaps with composite priorities. The result is a simple search tree where the depth of each item is determined by its predicted weight $w_x$. To achieve the result, each item $x$ has its composite priority $-\lfloor\log\log(1/w_x)\rfloor + U(0, 1)$ where $U(0, 1)$ is the uniform random variable. This generalizes the recent learning-augmented BSTs [Lin-Luo-Woodruff ICML`22], which only work for Zipfian distributions, to arbitrary inputs and predictions. It also gives the first B-Tree data structure that can provably take advantage of localities in the access sequence via online self-reorganization. The data structure is robust to prediction errors and handles insertions, deletions, as well as prediction updates.
Abstract（参考訳）: 本研究は,Treapsを用いたBST(Learning-augmented binary search tree)とB-Treesを複合優先度で検討する。その結果、各項目の深さが予測重量$w_x$で決定される単純な探索木となる。この結果を達成するために、各$x$はその合成優先度 $-\lfloor\log(1/w_x)\rfloor + U(0, 1)$ ここで$U(0, 1)$は一様確率変数である。これは最近の学習強化BST(Lin-Luo-Woodruff ICML`22]を任意の入力と予測に一般化する。また、オンラインの自己再構成を通じてアクセスシーケンスの局所性を有効活用できる最初のb木データ構造も提供する。データ構造は予測エラーに堅牢であり、挿入、削除、予測更新を処理する。

関連論文リスト

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)

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