論文の概要: Robust Learning-Augmented Dictionaries
- arxiv url: http://arxiv.org/abs/2402.09687v1
- Date: Thu, 15 Feb 2024 03:45:44 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-16 17:02:24.272324
- Title: Robust Learning-Augmented Dictionaries
- Title（参考訳）: ロバスト学習型辞書
- Authors: Ali Zeynali, Shahin Kamali, Mohammad Hajiesmaili
- Abstract要約: 最適な一貫性とロバスト性を備えた辞書を実装するための,最初の学習拡張データ構造を提案する。
我々のデータ構造はRobostSLと呼ばれ、データシーケンス内の要素のアクセス頻度の予測によって拡張されたスキップリストである。
数値実験により、RobostSLは、合成データと実データの両方を用いて、代替データ構造よりも優れていることが示された。
- 参考スコア（独自算出の注目度）: 5.906278982316205
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We present the first learning-augmented data structure for implementing
dictionaries with optimal consistency and robustness. Our data structure, named
RobustSL, is a skip list augmented by predictions of access frequencies of
elements in a data sequence. With proper predictions, RobustSL has optimal
consistency (achieves static optimality). At the same time, it maintains a
logarithmic running time for each operation, ensuring optimal robustness, even
if predictions are generated adversarially. Therefore, RobustSL has all the
advantages of the recent learning-augmented data structures of Lin, Luo, and
Woodruff (ICML 2022) and Cao et al. (arXiv 2023), while providing robustness
guarantees that are absent in the previous work. Numerical experiments show
that RobustSL outperforms alternative data structures using both synthetic and
real datasets.
- Abstract（参考訳）: 最適な一貫性とロバスト性を備えた辞書を実装するための,最初の学習拡張データ構造を提案する。
robustslというデータ構造は、データシーケンス内の要素のアクセス頻度の予測によって拡張されたスキップリストです。
適切な予測により、RobostSL は最適整合性(静的最適性を得る)を持つ。
同時に、各操作の対数実行時間を維持し、たとえ予測が逆向きに生成されるとしても、最適な堅牢性を確保する。
それゆえ、RobostSLはLin, Luo, and Woodruff (ICML 2022) と Cao et al. (arXiv 2023) の最近の学習強化データ構造の利点を全て備えている。
数値実験により、RobostSLは合成データと実データの両方を用いて代替データ構造より優れていた。
関連論文リスト
- Compact Neural Graphics Primitives with Learned Hash Probing [100.07267906666293]
学習したプローブを持つハッシュテーブルにはデメリットはなく,その結果,サイズと速度の組合せが好適であることを示す。
推論は、トレーニングが1.2-2.6倍遅い間、同じ品質で未処理のハッシュテーブルよりも高速である。
論文 参考訳（メタデータ） (2023-12-28T18:58:45Z) - Faithful Low-Resource Data-to-Text Generation through Cycle Training [14.375070014155817]
近年,構造化データからテキストを生成する手法が大幅に進歩している。
サイクルトレーニングでは、互いに逆転する2つのモデルを使用する。
サイクルトレーニングが完全に教師付きアプローチとほぼ同等のパフォーマンスを達成することを示す。
論文 参考訳（メタデータ） (2023-05-24T06:44:42Z) - Online List Labeling with Predictions [13.126494821223755]
オンラインリストラベリングの基本的な問題において,予測が活用可能であることを示す。
問題では、n個のアイテムが時間とともに到着し、サイズ Theta(n) の配列でソートされた順序で格納されなければならない。
データ構造をラベル付けした新しいリストを設計し、その性能を2つのモデルでバインドする。
論文 参考訳（メタデータ） (2023-05-17T19:46:34Z) - Forgetful Forests: high performance learning data structures for
streaming data under concept drift [0.46193503399184266]
本稿では,インクリメンタルな計算と逐次的および確率的フィルタリングを組み合わせることで,木に基づく学習アルゴリズムを実現する。
アルゴリズムは最先端のインクリメンタルアルゴリズムの最大24倍高速である。
論文 参考訳（メタデータ） (2022-12-15T14:49:01Z) - On the Transferability of Pre-trained Language Models: A Study from
Artificial Datasets [74.11825654535895]
大規模未ラベルテキストデータ上での事前学習言語モデル(LM)により、ダウンストリームのパフォーマンスが極めて容易になる。
我々は,事前学習データに含まれる特定の特徴について,セマンティクス以外では,下流タスクのスクラッチからトレーニングしたデータよりも,事前学習したLMを優れているか検討した。
論文 参考訳（メタデータ） (2021-09-08T10:39:57Z) - Learning to Hash Robustly, with Guarantees [79.68057056103014]
本稿では,理論的アルゴリズムと本質的に一致する最悪ケース保証を持つハミング空間のためのNSアルゴリズムを設計する。
理論的にも実用的にも、与えられたデータセットに対してアルゴリズムが最適化できる能力を評価する。
我々のアルゴリズムは、MNISTおよびImageNetデータセットに対する最悪のパフォーマンスのクエリを、1.8倍と2.1倍の精度でリコールする。
論文 参考訳（メタデータ） (2021-08-11T20:21:30Z) - Convolutional Sparse Coding Fast Approximation with Application to
Seismic Reflectivity Estimation [9.005280130480308]
2～5回の反復で畳み込みスパース符号の良好な近似を生成する古典的反復しきい値アルゴリズムの高速化版を提案する。
提案手法の性能は, 合成シナリオと実データシナリオの両方において, 地震インバージョン問題によって実証される。
論文 参考訳（メタデータ） (2021-06-29T12:19:07Z) - New Oracle-Efficient Algorithms for Private Synthetic Data Release [52.33506193761153]
微分プライベートな合成データを構築するための3つの新しいアルゴリズムを提案する。
アルゴリズムは最悪の場合でも差分プライバシーを満たす。
現状の手法である高次元行列機構 citeMcKennaMHM18 と比較すると,我々のアルゴリズムは大規模作業負荷の精度が向上する。
論文 参考訳（メタデータ） (2020-07-10T15:46:05Z) - A Constraint-Based Algorithm for the Structural Learning of
Continuous-Time Bayesian Networks [70.88503833248159]
連続時間ベイズネットワークの構造を学習するための制約に基づく最初のアルゴリズムを提案する。
我々は,条件付き独立性を確立するために提案した,異なる統計的テストと基礎となる仮説について論じる。
論文 参考訳（メタデータ） (2020-07-07T07:34:09Z) - Post-Estimation Smoothing: A Simple Baseline for Learning with Side
Information [102.18616819054368]
本稿では,構造指標データを予測に組み込む高速かつ効率的な手法として,後推定平滑化演算子を提案する。
滑らかなステップは元の予測器とは分離されているため、機械学習タスクの幅広いクラスに適用できる。
大規模な空間的・時間的データセットに関する実験は,実測後のスムース化の速度と正確さを浮き彫りにした。
論文 参考訳（メタデータ） (2020-03-12T18:04:20Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。