論文の概要: Learning-based Sketches for Frequency Estimation in Data Streams without Ground Truth
- arxiv url: http://arxiv.org/abs/2412.03611v3
- Date: Fri, 15 Aug 2025 13:27:17 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-08-18 16:53:24.07133
- Title: Learning-based Sketches for Frequency Estimation in Data Streams without Ground Truth
- Title（参考訳）: 地中真実のないデータストリームにおける周波数推定のための学習ベーススケッチ
- Authors: Xinyu Yuan, Yan Qiao, Meng Li, Zhenchun Wei, Cuiying Feng, Zonghui Wang, Wenzhi Chen,
- Abstract要約: 伝統的なスケッチは、厳密なメモリ制約の下でのみ粗い見積もりを提供する。
キーごとの周波数推定のための実践的な学習パラダイムであるUCL-sketchを提案する。
設計では、2つの重要なイノベーションを紹介している: (i) 基礎的な真実(GT)を必要としない同等の学習に基づくオンライントレーニングメカニズムと、 (ii) 構造化推定バケットを活用して実世界のデータストリームにスケールする高度にスケーラブルなアーキテクチャ。
- 参考スコア（独自算出の注目度）: 9.924618812446315
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Estimating the frequency of items on the high-volume, fast data stream has been extensively studied in many areas, such as database and network measurement. Traditional sketches provide only coarse estimates under strict memory constraints. Although some learning-augmented methods have emerged recently, they typically rely on offline training with real frequencies or/and labels, which are often unavailable. Moreover, these methods suffer from slow update speeds, limiting their suitability for real-time processing despite offering only marginal accuracy improvements. To overcome these challenges, we propose UCL-sketch, a practical learning-based paradigm for per-key frequency estimation. Our design introduces two key innovations: (i) an online training mechanism based on equivalent learning that requires no ground truth (GT), and (ii) a highly scalable architecture leveraging logically structured estimation buckets to scale to real-world data stream. The UCL-sketch, which utilizes compressive sensing (CS), converges to an estimator that provably yields a error bound far lower than that of prior works, without sacrificing the speed of processing. Extensive experiments on both real-world and synthetic datasets demonstrate that our approach outperforms previously proposed approaches regarding per-key accuracy and distribution. Notably, under extremely tight memory budgets, its quality almost matches that of an (infeasible) omniscient oracle. Moreover, compared to the existing equation-based sketch, UCL-sketch achieves an average decoding speedup of nearly 500 times. To help further research and development, our code is publicly available at https://github.com/Y-debug-sys/UCL-sketch.
- Abstract（参考訳）: 高体積高速データストリーム上の項目の頻度を推定する手法は,データベースやネットワーク計測など,多くの分野で広く研究されている。
伝統的なスケッチは、厳密なメモリ制約の下でのみ粗い見積もりを提供する。
最近、いくつかの学習強化手法が登場したが、通常、実際の周波数やラベルによるオフライントレーニングに依存しており、しばしば利用できない。
さらに、これらの手法は更新速度の遅さに悩まされており、限界精度の改善しか提供していないにもかかわらず、リアルタイム処理に適している。
これらの課題を克服するために,鍵単位の周波数推定のための実践的な学習パラダイムであるUCL-sketchを提案する。
私たちのデザインには2つの重要な革新があります。
一 根拠真理(GT)を必要としない同等の学習に基づくオンライン学習機構
(ii)論理的に構造化された推定バケットを利用して実世界のデータストリームにスケールする高度にスケーラブルなアーキテクチャ。
圧縮センシング(CS)を利用するUCLスケッチは、処理速度を犠牲にすることなく、前処理よりもはるかに低い誤差を確実に得る推定器に収束する。
実世界のデータセットと合成データセットの両方に対する大規模な実験により、我々のアプローチはキーごとの精度と分布に関する提案されたアプローチよりも優れていることが示された。
特に、非常に厳格なメモリ予算の下では、その品質は(実現不可能な)万能のオラクルとほぼ一致します。
さらに、既存の方程式ベースのスケッチと比較して、UCL-sketchは平均デコード速度を500倍に向上させる。
さらなる研究と開発を支援するため、私たちのコードはhttps://github.com/Y-debug-sys/UCL-sketch.comで公開されています。
関連論文リスト
- PROL : Rehearsal Free Continual Learning in Streaming Data via Prompt Online Learning [17.230781041043823]
4つの主要コンポーネントを含むオンライン連続学習(OCL)のための新しいプロンプトベース手法を提案する。
提案手法は,CIFAR100, ImageNet-R, ImageNet-A, CUBデータセットにおける現在のSOTAよりも高い性能を実現する。
論文 参考訳（メタデータ） (2025-07-16T15:04:46Z) - SONNET: Enhancing Time Delay Estimation by Leveraging Simulated Audio [17.811771707446926]
学習に基づく手法は、合成データにもとづいても、新しい実世界のデータに基づいてGCC-PHATを著しく上回り得ることを示す。
トレーニングされたモデルであるSONNETは、リアルタイムに実行可能で、多くの実データアプリケーションのために、最初から新しいデータに取り組んでいます。
論文 参考訳（メタデータ） (2024-11-20T10:23:21Z) - Learning-Based Heavy Hitters and Flow Frequency Estimation in Streams [9.22255012731159]
そこで本研究では,まず,大ヒット数,トップk,フロー周波数推定を識別する,LSSと呼ばれる競合カウンタベースのアルゴリズムを提案する。
以上の結果から, LSSは重打点, トップk, 流速推定において, スペースセービングの精度と効率を高めることができることが示された。
論文 参考訳（メタデータ） (2024-06-24T02:31:00Z) - Stochastic Amortization: A Unified Approach to Accelerate Feature and Data Attribution [62.71425232332837]
雑音ラベル付きモデルを用いたトレーニングは安価で驚くほど効果的であることを示す。
このアプローチは、いくつかの特徴属性とデータ評価手法を著しく加速し、しばしば既存のアプローチよりも桁違いにスピードアップする。
論文 参考訳（メタデータ） (2024-01-29T03:42:37Z) - Benchmarking Neural Network Training Algorithms [52.890134877995195]
トレーニングアルゴリズムは、ディープラーニングパイプラインに不可欠な部分です。
コミュニティとして、トレーニングアルゴリズムの改善を確実に特定することはできない。
固定ハードウェア上で実行される複数のワークロードを使用した,新たな,競争力のある,時間と時間のベンチマークを導入する。
論文 参考訳（メタデータ） (2023-06-12T15:21:02Z) - Learnability with Time-Sharing Computational Resource Concerns [65.268245109828]
本稿では,学習理論における計算資源の影響を考慮した理論的枠組みを提案する。
このフレームワークは、入ってくるデータストリームが潜在的に無限であるようなストリーム学習に自然に適用できる。
これはまた、インテリジェントなスーパーコンピュータオペレーティングシステムの設計に対する理論的視点を提供するかもしれない。
論文 参考訳（メタデータ） (2023-05-03T15:54:23Z) - Real-Time Evaluation in Online Continual Learning: A New Hope [104.53052316526546]
計算コストに関して,現在の継続学習(CL)手法を評価した。
簡単なベースラインは、この評価の下で最先端のCL法より優れている。
これは、既存のCL文献の大部分は、実用的でない特定の種類のストリームに適合していることを驚くほど示唆している。
論文 参考訳（メタデータ） (2023-02-02T12:21:10Z) - Learning with Neighbor Consistency for Noisy Labels [69.83857578836769]
特徴空間におけるトレーニング例間の類似性を利用した雑音ラベルから学習する手法を提案する。
合成(CIFAR-10, CIFAR-100)とリアル(mini-WebVision, Clothing1M, mini-ImageNet-Red)の両方のノイズを評価するデータセットの評価を行った。
論文 参考訳（メタデータ） (2022-02-04T15:46:27Z) - Accelerating Deep Learning with Dynamic Data Pruning [0.0]
ディープラーニングは、最先端のネットワークをトレーニングするために強力なコンピューティングシステムへのアクセスを必要とするため、違法にコストがかかるようになった。
forget scoresやGraNd/EL2N scoresといった以前の作業では、完全なデータセット内の重要なサンプルを特定し、残りのサンプルを刈り取ることで、エポック毎のイテレーションを減らすことができる。
本稿では,強化学習手法に基づく2つのアルゴリズムを提案し,ランダムな動的手法よりも高い精度でサンプルを動的にプーンする。
論文 参考訳（メタデータ） (2021-11-24T16:47:34Z) - Convolutional Sparse Coding Fast Approximation with Application to
Seismic Reflectivity Estimation [9.005280130480308]
2～5回の反復で畳み込みスパース符号の良好な近似を生成する古典的反復しきい値アルゴリズムの高速化版を提案する。
提案手法の性能は, 合成シナリオと実データシナリオの両方において, 地震インバージョン問題によって実証される。
論文 参考訳（メタデータ） (2021-06-29T12:19:07Z) - Fast accuracy estimation of deep learning based multi-class musical
source separation [79.10962538141445]
本稿では,ニューラルネットワークのトレーニングやチューニングを行うことなく,任意のデータセットにおける楽器の分離性を評価する手法を提案する。
理想的な比マスクを持つオラクルの原理に基づいて、我々の手法は最先端のディープラーニング手法の分離性能を推定するための優れたプロキシである。
論文 参考訳（メタデータ） (2020-10-19T13:05:08Z) - Low-Rank Robust Online Distance/Similarity Learning based on the
Rescaled Hinge Loss [0.34376560669160383]
既存のオンライン手法では、トレーニング三つ子やペアの制約が事前に存在すると仮定することが多い。
オンライン距離相似学習問題を,ロバストな再スケールヒンジ損失関数を用いて定式化する。
提案モデルは比較的汎用的で,任意のPAベースのオンラインディスタンス・シミュラリティアルゴリズムに適用可能である。
論文 参考訳（メタデータ） (2020-10-07T08:38:34Z) - Temporal Calibrated Regularization for Robust Noisy Label Learning [60.90967240168525]
ディープニューラルネットワーク(DNN)は、大規模な注釈付きデータセットの助けを借りて、多くのタスクで大きな成功を収めている。
しかし、大規模なデータのラベル付けは非常にコストがかかりエラーが発生しやすいため、アノテーションの品質を保証することは困難である。
本稿では,従来のラベルと予測を併用したTCR(Temporal Calibrated Regularization)を提案する。
論文 参考訳（メタデータ） (2020-07-01T04:48:49Z) - On Coresets for Support Vector Machines [61.928187390362176]
coresetは、元のデータポイントの小さな、代表的なサブセットである。
我々は,本アルゴリズムを用いて,既製のSVMソルバをストリーミング,分散,動的データ設定に適用可能であることを示す。
論文 参考訳（メタデータ） (2020-02-15T23:25:12Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。