論文の概要: Compressing Multisets with Large Alphabets

• arxiv url: http://arxiv.org/abs/2107.09202v1
• Date: Thu, 15 Jul 2021 16:54:38 GMT
• ステータス: 処理完了
• システム内更新日: 2021-07-25 11:58:06.074534
• Title: Compressing Multisets with Large Alphabets
• Title（参考訳）: 大型Alphabetによるマルチセット圧縮
• Authors: Daniel Severo, James Townsend, Ashish Khisti, Alireza Makhzani, Karen Ullrich
• Abstract要約: マルチセットを最適に圧縮する現在の方法は、その計算時間はアルファベットサイズと線形にスケールするため、高次元のシンボルには適さない。 そこで本研究では,シンボルがI.d.と仮定して,これらのビットを復号する手法を提案する。
• 参考スコア（独自算出の注目度）: 30.281628616298317
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Current methods that optimally compress multisets are not suitable for high-dimensional symbols, as their compute time scales linearly with alphabet size. Compressing a multiset as an ordered sequence with off-the-shelf codecs is computationally more efficient, but has a sub-optimal compression rate, as bits are wasted encoding the order between symbols. We present a method that can recover those bits, assuming symbols are i.i.d., at the cost of an additional $\mathcal{O}(|\mathcal{M}|\log M)$ in average time complexity, where $|\mathcal{M}|$ and $M$ are the total and unique number of symbols in the multiset. Our method is compatible with any prefix-free code. Experiments show that, when paired with efficient coders, our method can efficiently compress high-dimensional sources such as multisets of images and collections of JSON files.
• Abstract（参考訳）: マルチセットを最適に圧縮する現在の方法は、計算時間はアルファベットサイズと線形にスケールするため、高次元シンボルには適していない。 市販のコーデックで順序列としてマルチセットを圧縮するのは計算効率が良いが、シンボル間の順序を符号化するビットが無駄になるため、準最適圧縮速度を持つ。 シンボルを i.i.d. と仮定して、平均時間複雑性で $\mathcal{o}(|\mathcal{m}|\log m)$ のコストで、$|\mathcal{m}|$ と $m$ を多重集合内の記号の総数と一意な数とする。 本手法はプレフィックスフリーコードと互換性がある。 実験により,効率的なコーダと組み合わせることで,画像の多重セットやJSONファイルのコレクションなどの高次元ソースを効率よく圧縮できることがわかった。

関連論文リスト

• Superposed Decoding: Multiple Generations from a Single Autoregressive Inference Pass [72.07642648108849]
  Superposed Decodingは、1つの自己回帰推論パスのコストで$k$のドラフトを生成する新しい復号アルゴリズムである。 Superposed Decodingは、他のデコード戦略と組み合わせることで、推論時間計算のスケーリング時に普遍的なカバレッジが向上する。
  論文  参考訳（メタデータ） (2024-05-28T17:40:48Z)
• Some Notes on the Sample Complexity of Approximate Channel Simulation [2.4554686192257424]
  チャネルシミュレーションアルゴリズムは、所定のターゲット分布のランダムサンプルを$Q$で効率的にエンコードし、機械学習ベースの損失データ圧縮における応用を見つけることができる。 本稿では,固定ランタイムを用いた近似スキームについて考察する。 D_KL[Q Vert P] + o(1)) Big/epsilonbigのみのサンプル複雑さで、$mathrmTV[Q Vert P] leq epsilon$を確保し、最適な符号化性能を維持するために、グローバルバウンドの深度制限A*符号化を利用する。
  論文  参考訳（メタデータ） (2024-05-07T14:44:41Z)
• Linear-time Minimum Bayes Risk Decoding with Reference Aggregation [52.1701152610258]
  最小ベイズリスク(MBR、Minimum Bayes Risk)は、機械翻訳の品質向上を図ったテキスト生成技術である。 これは2次複雑性を持つ実用計量のペアワイズ計算を必要とする。 本稿では,集約された参照表現に対して計算したスコアを用いて,ペアワイズメトリックスコアを近似する。
  論文  参考訳（メタデータ） (2024-02-06T18:59:30Z)
• Matrix Compression via Randomized Low Rank and Low Precision Factorization [47.902465710511485]
  現代の行列は数十億の要素を巻き込み、そのストレージと処理は計算資源とメモリ使用量の観点から非常に要求される。 この構造を利用して任意の行列 $mathbfA$ as $mathbfLmathbfR$ の低階分解を求めるアルゴリズムを提案する。 LlaMa-7$bの層を圧縮し,画像圧縮におけるアルゴリズムの有効性を実証的に実証した。
  論文  参考訳（メタデータ） (2023-10-17T06:56:57Z)
• A Formal Perspective on Byte-Pair Encoding [100.75374173565548]
  Byte-Pairimation (BPE) は、当初圧縮法として考案されたものの、NLPでデータをトークン化するために使われる一般的なアルゴリズムである。 我々は、ランタイムの複雑さを$mathcalOleft(N log Mright)$から$mathcalOleft(N log Mright)$に改善するBPEのより高速な実装を提供しています。
  論文  参考訳（メタデータ） (2023-06-29T10:29:23Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。 異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。 我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
  論文  参考訳（メタデータ） (2022-06-07T18:00:01Z)
• Understanding and Compressing Music with Maximal Transformable Patterns [0.0]
  点集合の最大パターンを探索するアルゴリズム、$DinmathbbRk$を提案する。 また、これらの最大パターンのそれぞれに対して発生の集合を探索する第2のアルゴリズムを提案する。 民謡旋律を調律語族に分類する作業において,3種類の異なる複雑性のクラスで新しい圧縮アルゴリズムを評価する。
  論文  参考訳（メタデータ） (2022-01-26T17:47:26Z)
• Impossibility Results for Grammar-Compressed Linear Algebra [14.85374185122389]
  膨大な量のデータを扱うためには、ベクトルや行列を圧縮することが自然で一般的である。 本稿では, 圧縮されたデータに対して, 元のデータがそんなに小さいかのように, 効率的に計算を実行できるかどうかを問う。 内積、行列ベクトル乗法、行列乗法など、最も基本的な線形代数演算を考える。
  論文  参考訳（メタデータ） (2020-10-27T10:33:01Z)
• Faster Binary Embeddings for Preserving Euclidean Distances [9.340611077939828]
  本稿では, 高速で, 距離保存可能なバイナリ埋め込みアルゴリズムを提案し, データセット $mathcalTsubseteqmathbbRn$ を立方体 $pm 1m$ のバイナリシーケンスに変換する。 我々の手法は高速かつメモリ効率が良く、時間複雑性は$O(m)$、空間複雑性は$O(m)$である。
  論文  参考訳（メタデータ） (2020-10-01T22:41:41Z)

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

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