論文の概要: MCPrioQ: A lock-free algorithm for online sparse markov-chains
- arxiv url: http://arxiv.org/abs/2304.14801v1
- Date: Fri, 28 Apr 2023 12:19:26 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-01 14:19:01.944541
- Title: MCPrioQ: A lock-free algorithm for online sparse markov-chains
- Title(参考訳): MCPrioQ: オンラインスパースマルコフチェーンのためのロックフリーアルゴリズム
- Authors: Jesper Derehag, {\AA}ke Johansson
- Abstract要約: MCPrioQは、オンラインおよび継続的学習を可能にする、ロックフリーのスパースマーコブチェーンである。
特に、下降確率順で$n$-itemsのルックアップを推奨するシステムに適している。
- 参考スコア(独自算出の注目度): 0.0
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: In high performance systems it is sometimes hard to build very large graphs
that are efficient both with respect to memory and compute. This paper proposes
a data structure called Markov-chain-priority-queue (MCPrioQ), which is a
lock-free sparse markov-chain that enables online and continuous learning with
time-complexity of $O(1)$ for updates and $O(CDF^{-1}(t))$ inference. MCPrioQ
is especially suitable for recommender-systems for lookups of $n$-items in
descending probability order. The concurrent updates are achieved using
hash-tables and atomic instructions and the lookups are achieved through a
novel priority-queue which allows for approximately correct results even during
concurrent updates. The approximatly correct and lock-free property is
maintained by a read-copy-update scheme, but where the semantics have been
slightly updated to allow for swap of elements rather than the traditional
pop-insert scheme.
- Abstract(参考訳): 高性能システムでは、メモリと計算の両方において効率的である非常に大きなグラフを構築するのが難しいことがある。
本稿では,ロックフリーなスパースマルコフチェーンであるmarkov-chain-priority-queue(mcprioq)と呼ばれるデータ構造を提案する。
MCPrioQは、下降確率順で$n$-itemsのルックアップを推奨するシステムに特に適している。
同時更新はハッシュテーブルとアトミック命令を使用して達成され、同時更新時でもほぼ正しい結果が得られる新しい優先度キューによって行われる。
近似的正確かつロックフリーなプロパティは、読み取りコピー更新スキームによって維持されるが、セマンティクスがわずかに更新され、従来のポップ・インサート・スキームよりも要素のスワップが可能になった。
関連論文リスト
- POCKET: Pruning Random Convolution Kernels for Time Series Classification from a Feature Selection Perspective [8.359327841946852]
2つの時系列分類モデル、ROCKETとMINIROCKETは、特徴を捉えるために多数のランダムな1-D畳み込みカーネルを必要とする。
本稿では,効果的にモデルを作成するための2つの革新的アルゴリズムを提案する。
実験の結果、POCKETは精度を著しく低下させることなく最大60%のカーネルを出力し、そのカーネルよりも11倍高速に動作していることがわかった。
論文 参考訳(メタデータ) (2023-09-15T16:03:23Z) - H$_2$O: Heavy-Hitter Oracle for Efficient Generative Inference of Large
Language Models [110.06476624089679]
メモリフットプリントを大幅に削減する新しいKVキャッシュの実装手法を提案する。
我々のアプローチは、トークンのごく一部が、注意点の計算において、ほとんどの価値に寄与する、という観察に基づいている。
我々は,最近のトークンとH$のバランスを動的に保持するKVキャッシュ消去ポリシーであるヘビーヒッター(H$O)を提案する。
論文 参考訳(メタデータ) (2023-06-24T20:11:14Z) - Quick Adaptive Ternary Segmentation: An Efficient Decoding Procedure For
Hidden Markov Models [70.26374282390401]
ノイズの多い観測から元の信号(すなわち隠れ鎖)を復号することは、ほぼすべてのHMMに基づくデータ分析の主要な目標の1つである。
本稿では,多対数計算複雑性において隠れた列を復号化するための分法であるQuick Adaptive Ternary(QATS)を提案する。
論文 参考訳(メタデータ) (2023-05-29T19:37:48Z) - Queue Scheduling with Adversarial Bandit Learning [20.606599586119835]
K$キューからなるワンホップ単一サーバキューシステムについて検討する。
我々のスケジューリング手法は,逆帯域学習とリアプノフドリフト最小化の革新的な組み合わせに基づいている。
ランダム化ポリシーのいくつかの(おそらく未知の)シーケンスで安定化可能なシステムを安定化できる2つの新しいアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-03-03T07:17:09Z) - Rethinking skip connection model as a learnable Markov chain [12.135167279383815]
我々は、学習可能なマルコフ連鎖として定式化できるスキップ接続でモデルの振舞いを深く掘り下げる。
効率的なマルコフ連鎖は、入力データを常により良い方法でターゲットドメインにマップするので好まれる。
残差のようなモデルを学習可能なマルコフ連鎖にするために、簡単なペナル接続のルーチンを提案する。
論文 参考訳(メタデータ) (2022-09-30T07:31:49Z) - Single MCMC Chain Parallelisation on Decision Trees [0.9137554315375919]
本稿では,平均的なラップトップやパソコン上でMCMC決定ツリーチェーンを並列化する手法を提案する。
実験の結果,シリアルと並列実装が統計的に同一である場合,実行時間を18倍に向上できることがわかった。
論文 参考訳(メタデータ) (2022-07-26T07:07:51Z) - Asymmetric Scalable Cross-modal Hashing [51.309905690367835]
クロスモーダルハッシュは、大規模なマルチメディア検索問題を解決する方法として成功している。
これらの問題に対処する新しい非対称スケーラブルクロスモーダルハッシュ(ASCMH)を提案する。
我々のASCMHは、最先端のクロスモーダルハッシュ法よりも精度と効率の点で優れています。
論文 参考訳(メタデータ) (2022-07-26T04:38:47Z) - Autoregressive Search Engines: Generating Substrings as Document
Identifiers [53.0729058170278]
自動回帰言語モデルは、回答を生成するデファクト標準として現れています。
これまでの研究は、探索空間を階層構造に分割する方法を探究してきた。
本研究では,検索空間の任意の構造を強制しない代替として,経路内のすべてのngramを識別子として使用することを提案する。
論文 参考訳(メタデータ) (2022-04-22T10:45:01Z) - Complex Event Forecasting with Prediction Suffix Trees: Extended
Technical Report [70.7321040534471]
複合イベント認識(CER)システムは、イベントのリアルタイムストリーム上のパターンを"即時"検出する能力によって、過去20年間に人気が高まっている。
このような現象が実際にCERエンジンによって検出される前に、パターンがいつ発生するかを予測する方法が不足している。
複雑なイベント予測の問題に対処しようとする形式的なフレームワークを提案する。
論文 参考訳(メタデータ) (2021-09-01T09:52:31Z) - Coded Stochastic ADMM for Decentralized Consensus Optimization with Edge
Computing [113.52575069030192]
セキュリティ要件の高いアプリケーションを含むビッグデータは、モバイルデバイスやドローン、車両など、複数の異種デバイスに収集され、格納されることが多い。
通信コストとセキュリティ要件の制限のため、核融合センターにデータを集約するのではなく、分散的に情報を抽出することが最重要となる。
分散エッジノードを介してデータを局所的に処理するマルチエージェントシステムにおいて,モデルパラメータを学習する問題を考える。
分散学習モデルを開発するために,乗算器アルゴリズムの最小バッチ交互方向法(ADMM)のクラスについて検討した。
論文 参考訳(メタデータ) (2020-10-02T10:41:59Z) - Time-aware Large Kernel Convolutions [41.19006428608901]
Time-Aware Large Kernel (TaLK) Convolutionsは、カーネルの総和の大きさを予測するために学習する新しい適応的畳み込み演算である。
提案手法は, 大規模標準機械翻訳, 抽象要約, 言語モデリングデータセットにおいて評価される。
論文 参考訳(メタデータ) (2020-02-08T15:30:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。