論文の概要: 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木データ構造も提供する。
データ構造は予測エラーに堅牢であり、挿入、削除、予測更新を処理する。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。