論文の概要: 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の重要なパフォーマンス指標である静的最適性と作業セット境界をそれぞれ達成する。
さらに、このスキームは誤差の予測に頑健であり、入力を仮定しない。
関連論文リスト
- Learning a Decision Tree Algorithm with Transformers [80.49817544396379]
本稿では,従来のアルゴリズムから出力されたフィルタを用いてトランスフォーマーモデルを用いて,分類のための強力な決定木を生成するメタトレーについて紹介する。
次にMetaTreeをトレーニングして、強力な一般化パフォーマンスを実現するツリーを生成します。
論文 参考訳(メタデータ) (2024-02-06T07:40:53Z) - End-to-end Feature Selection Approach for Learning Skinny Trees [15.047418632192754]
複合機能選択とツリーアンサンブル学習は難しい課題である。一般的な木アンサンブルツールキット(グラディエントツリーやランダムフォレストなど)は、誤解を招くことが知られている特徴量に基づいた特徴選択をサポートし、パフォーマンスを著しく損なう可能性がある。
本研究では,木組におけるアンサンブル選択のためのスキニーツリーツールキットを提案し,特徴選択とツリーアンサンブル学習を同時に行う。
論文 参考訳(メタデータ) (2023-10-28T00:15:10Z) - On Computing Optimal Tree Ensembles [8.941441654913644]
ランダム林や、より一般的には(決定ノブレイクダッシュ-)ツリーアンサンブルは、分類と回帰の方法として広く使われている。
最近のアルゴリズムの進歩は、そのサイズや深さなどの様々な測定に最適な決定木を計算することができる。
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) - Individualized and Global Feature Attributions for Gradient Boosted
Trees in the Presence of $\ell_2$ Regularization [0.0]
本稿では,プレデコン(PreDecomp)を提案する。プレデコン(PreDecomp,PreDecomp,PreDecomp)は,正規化を$ell$で訓練した場合に,増木に対する新規な個別化特徴属性である。
また、各ツリーのアウトサンプルデータに個々の特徴属性とラベルの内積で定義される、偏りのないグローバルな特徴属性のファミリーであるTreeInnerを提案する。
論文 参考訳(メタデータ) (2022-11-08T17:56:22Z) - 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) - Strongly Incremental Constituency Parsing with Graph Neural Networks [70.16880251349093]
文を構文木にパースすることは、NLPの下流アプリケーションに恩恵をもたらす。
トランジッションベースは、状態遷移システムでアクションを実行することでツリーを構築する。
既存のトランジションベースは主にシフト・リデュース・トランジション・システムに基づいている。
論文 参考訳(メタデータ) (2020-10-27T19:19:38Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。