論文の概要: Frequency Estimation in Data Streams: Learning the Optimal Hashing Scheme

• arxiv url: http://arxiv.org/abs/2007.09261v2
• Date: Wed, 2 Jun 2021 04:38:39 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-09 14:59:05.444413
• Title: Frequency Estimation in Data Streams: Learning the Optimal Hashing Scheme
• Title（参考訳）: データストリームの周波数推定:最適なハッシュスキームの学習
• Authors: Dimitris Bertsimas and Vassilis Digalakis Jr
• Abstract要約: 本稿では,最適化と機械学習に基づくデータストリームの周波数推定問題に対する新しいアプローチを提案する。 提案手法は、観測されたストリームプレフィックスをほぼ最適にハッシュ要素に利用し、ターゲット周波数分布を圧縮する。 提案手法は, 推定誤差の平均(要素単位)と推定誤差の平均(要素単位)で1～2桁, 予測誤差で45～90%の精度で既存手法より優れていることを示す。
• 参考スコア（独自算出の注目度）: 3.7565501074323224
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present a novel approach for the problem of frequency estimation in data streams that is based on optimization and machine learning. Contrary to state-of-the-art streaming frequency estimation algorithms, which heavily rely on random hashing to maintain the frequency distribution of the data steam using limited storage, the proposed approach exploits an observed stream prefix to near-optimally hash elements and compress the target frequency distribution. We develop an exact mixed-integer linear optimization formulation, which enables us to compute optimal or near-optimal hashing schemes for elements seen in the observed stream prefix; then, we use machine learning to hash unseen elements. Further, we develop an efficient block coordinate descent algorithm, which, as we empirically show, produces high quality solutions, and, in a special case, we are able to solve the proposed formulation exactly in linear time using dynamic programming. We empirically evaluate the proposed approach both on synthetic datasets and on real-world search query data. We show that the proposed approach outperforms existing approaches by one to two orders of magnitude in terms of its average (per element) estimation error and by 45-90% in terms of its expected magnitude of estimation error.
• Abstract（参考訳）: 本稿では,最適化と機械学習に基づくデータストリームにおける周波数推定問題に対する新しいアプローチを提案する。 限られたストレージを用いてデータ蒸気の周波数分布を維持するためにランダムハッシュに強く依存する最先端のストリーミング周波数推定アルゴリズムとは対照的に,提案手法は観測されたストリームプレフィックスをほぼ最適にハッシュ要素に利用し,ターゲットの周波数分布を圧縮する。 我々は,観測されたストリームプレフィックスで見られる要素に対する最適あるいは準最適ハッシュスキームを計算し,機械学習を用いて未知の要素をハッシュする,正確な混合整数線形最適化法を開発した。 さらに,より効率的なブロック座標降下アルゴリズムを開発し,実例で示すように高品質な解を生成できるとともに,特に動的計画法を用いて,提案手法を線形時間に正確に解くことができる。 提案手法を合成データセットと実世界の検索クエリデータの両方で実証的に評価する。 提案手法は, 推定誤差の平均(要素単位)と推定誤差の平均(要素単位)で1～2桁, 予測誤差で45～90%の精度で既存手法より優れていることを示す。

関連論文リスト

• Building Conformal Prediction Intervals with Approximate Message Passing [14.951392270119461]
  等角予測は、分布のない方法で有効な予測間隔を構築するための強力なツールである。 本稿では,予測間隔の計算を高速化するために,AMP(Adroximate Message Passing)に基づく新しいアルゴリズムを提案する。 提案手法では,基準値に近い予測間隔が生成され,精度は桁違いに向上した。
  論文  参考訳（メタデータ） (2024-10-21T20:34:33Z)
• Distributed Markov Chain Monte Carlo Sampling based on the Alternating Direction Method of Multipliers [143.6249073384419]
  本論文では,乗算器の交互方向法に基づく分散サンプリング手法を提案する。 我々は,アルゴリズムの収束に関する理論的保証と,その最先端性に関する実験的証拠の両方を提供する。 シミュレーションでは,線形回帰タスクとロジスティック回帰タスクにアルゴリズムを配置し,その高速収束を既存の勾配法と比較した。
  論文  参考訳（メタデータ） (2024-01-29T02:08:40Z)
• Stochastic optimization with arbitrary recurrent data sampling [2.1485350418225244]
  最も一般的に使われているデータサンプリングアルゴリズムは、軽度な仮定の下にある。 特定のクラスの繰り返し最適化アルゴリズムに対して、他のプロパティは不要であることを示す。 我々は,データセットをカバーするサンプリングアルゴリズムを選択することで,収束を加速できることを示す。
  論文  参考訳（メタデータ） (2024-01-15T14:04:50Z)
• Learning Unnormalized Statistical Models via Compositional Optimization [73.30514599338407]
  実データと人工雑音のロジスティックな損失として目的を定式化することにより, ノイズコントラスト推定(NCE)を提案する。 本稿では,非正規化モデルの負の対数類似度を最適化するための直接的アプローチについて検討する。
  論文  参考訳（メタデータ） (2023-06-13T01:18:16Z)
• Low-rank extended Kalman filtering for online learning of neural networks from streaming data [71.97861600347959]
  非定常データストリームから非線形関数のパラメータを推定するための効率的なオンライン近似ベイズ推定アルゴリズムを提案する。 この方法は拡張カルマンフィルタ (EKF) に基づいているが、新しい低ランク+斜角行列分解法を用いている。 変分推論に基づく手法とは対照的に,本手法は完全に決定論的であり,ステップサイズチューニングを必要としない。
  論文  参考訳（メタデータ） (2023-05-31T03:48:49Z)
• Optimal Algorithms for the Inhomogeneous Spiked Wigner Model [89.1371983413931]
  不均一な問題に対する近似メッセージパッシングアルゴリズム(AMP)を導出する。 特に,情報理論の閾値よりも大きい信号と雑音の比を必要とする既知のアルゴリズムが,ランダムよりも優れた処理を行うための統計的・計算的ギャップの存在を同定する。
  論文  参考訳（メタデータ） (2023-02-13T19:57:17Z)
• Learning to Hash Robustly, with Guarantees [79.68057056103014]
  本稿では,理論的アルゴリズムと本質的に一致する最悪ケース保証を持つハミング空間のためのNSアルゴリズムを設計する。 理論的にも実用的にも、与えられたデータセットに対してアルゴリズムが最適化できる能力を評価する。 我々のアルゴリズムは、MNISTおよびImageNetデータセットに対する最悪のパフォーマンスのクエリを、1.8倍と2.1倍の精度でリコールする。
  論文  参考訳（メタデータ） (2021-08-11T20:21:30Z)
• Estimating leverage scores via rank revealing methods and randomization [50.591267188664666]
  任意のランクの正方形密度あるいはスパース行列の統計レバレッジスコアを推定するアルゴリズムについて検討した。 提案手法は,高密度およびスパースなランダム化次元性還元変換の合成と階調明細化法を組み合わせることに基づく。
  論文  参考訳（メタデータ） (2021-05-23T19:21:55Z)
• Matrix completion based on Gaussian belief propagation [5.685589351789462]
  行列ファクタリゼーションに基づく雑音マトリクス補完問題に対するメッセージパッシングアルゴリズムの開発を行う。 近似メッセージパッシングの文献によく用いられる摂動処理を適用することにより,提案アルゴリズムのメモリフレンドリーなバージョンを導出する。 合成データセットの実験により, 提案アルゴリズムは, 先行アルゴリズムが最適となる条件下では, ほぼ同じ性能を示すが, 非ガウス雑音により観測されたデータセットが破損した場合に有利であることがわかった。
  論文  参考訳（メタデータ） (2021-05-01T12:16:49Z)
• Sparse Algorithms for Markovian Gaussian Processes [18.999495374836584]
  スパースマルコフ過程は、誘導変数の使用と効率的なカルマンフィルタライク再帰を結合する。 我々は,局所ガウス項を用いて非ガウス的確率を近似する一般的なサイトベースアプローチであるsitesを導出する。 提案手法は,変動推論,期待伝播,古典非線形カルマンスムーサなど,機械学習と信号処理の両方から得られるアルゴリズムの新たなスパース拡張の一群を導出する。 派生した方法は、モデルが時間と空間の両方で別々の誘導点を持つ文学時間データに適しています。
  論文  参考訳（メタデータ） (2021-03-19T09:50:53Z)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。