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

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

arxiv url: http://arxiv.org/abs/2211.09251v1
Date: Wed, 16 Nov 2022 22:50:40 GMT
ステータス: 処理完了
システム内更新日: 2022-11-18 17:22:17.596100
Title: On the Power of Learning-Augmented BSTs
Title（参考訳）: 学習支援BSTのパワーについて
Authors: Jingbang Chen, Li Chen
Abstract要約: 本稿では,静的最適性および作業セット境界を大まかに予測した最初の学習拡張バイナリ探索木(BST)を提案する。
参考スコア（独自算出の注目度）: 11.089583246768342
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We present the first Learning-Augmented Binary Search Tree(BST) that attains Static Optimality and Working-Set Bound given rough predictions. Following the recent studies in algorithms with predictions and learned index structures, Lin, Luo, and Woodruff (ICML 2022) introduced the concept of Learning-Augmented BSTs, which aim to improve BSTs with learned advice. Unfortunately, their construction gives only static optimality under strong assumptions on the input. In this paper, we present a simple BST maintenance scheme that benefits from learned advice. With proper predictions, the scheme achieves Static Optimality and Working-Set Bound, respectively, which are important performance measures for BSTs. Moreover, the scheme is robust to prediction errors and makes no assumption on the input.
Abstract（参考訳）: 本稿では,静的最適性および作業セット境界を大まかに予測した最初の学習拡張バイナリ探索木(BST)を提案する。予測と学習インデックス構造を用いたアルゴリズムの最近の研究に続いて、Lin, Luo, Woodruff (ICML 2022)は学習アドバイスによるBSTの改善を目的としたLearning-Augmented BSTの概念を導入した。残念ながら、それらの構成は入力に対する強い仮定の下でのみ静的最適性を与える。本稿では,学習アドバイスの恩恵を受けるシンプルなBSTメンテナンス手法を提案する。適切な予測により、BSTの重要なパフォーマンス指標である静的最適性と作業セット境界をそれぞれ達成する。さらに、このスキームは誤差の予測に頑健であり、入力を仮定しない。

関連論文リスト

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)

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