論文の概要: Local Grammar-Based Coding Revisited
- arxiv url: http://arxiv.org/abs/2209.13636v1
- Date: Tue, 27 Sep 2022 19:05:22 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-29 17:57:40.123080
- Title: Local Grammar-Based Coding Revisited
- Title(参考訳): 局所文法に基づく符号化再訪
- Authors: {\L}ukasz D\k{e}bowski
- Abstract要約: 局所文法に基づく最小限の符号化の問題を再考する。
本稿では、最小ブロック符号の強い普遍性の新たな、より単純で、より一般的な証明を示す。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We revisit the problem of minimal local grammar-based coding. In this
setting, the local grammar encoder encodes grammars symbol by symbol, whereas
the minimal grammar transform minimizes the grammar length in a preset class of
grammars as given by the length of local grammar encoding. It is known that
such minimal codes are strongly universal for a strictly positive entropy rate,
whereas the number of rules in the minimal grammar constitutes an upper bound
for the mutual information of the source. Whereas the fully minimal code is
likely intractable, the constrained minimal block code can be efficiently
computed. In this note, we present a new, simpler, and more general proof of
strong universality of the minimal block code, regardless of the entropy rate.
The proof is based on a simple Zipfian bound for ranked probabilities. By the
way, we also show empirically that the number of rules in the minimal block
code cannot clearly discriminate between long-memory and memoryless sources,
such as a text in English and a random permutation of its characters. This
contradicts our previous expectations.
- Abstract(参考訳): 局所文法に基づくコーディングの最小化の問題を再検討する。
この設定では、局所文法エンコーダは文法記号をシンボルでエンコードするが、最小文法変換は、局所文法エンコードの長さによって与えられる、事前設定された文法クラスにおける文法長を最小化する。
そのような極小符号は厳密に正のエントロピー率に対して強く普遍的であることが知られているが、極小文法における規則の数はソースの相互情報に対する上限を構成する。
完全に最小限のコードは難易度が高いが、制約のある最小のブロックコードは効率的に計算できる。
本稿では、エントロピー率に関係なく、最小ブロック符号の強い普遍性の新たな、より単純で、より一般的な証明を示す。
この証明は、ランク付けされた確率に対する単純なZipfian境界に基づいている。
ちなみに、最小ブロック符号におけるルールの数は、英語のテキストや文字のランダムな置換など、長期記憶源と無記憶源とを明確に区別できないことも実証的に示している。
これは我々の以前の期待と矛盾する。
関連論文リスト
- Progressive-Proximity Bit-Flipping for Decoding Surface Codes [9.801253635315636]
トリックやサーフェスコードのようなトポロジカル量子コードは、ハードウェア実装の優れた候補である。
既存のデコーダは、計算複雑性の低いような要求を満たすのに不足することが多い。
トリックおよび表面符号に適した新しいビットフリップ(BF)デコーダを提案する。
論文 参考訳(メタデータ) (2024-02-24T22:38:05Z) - Low-Weight High-Distance Error Correcting Fermionic Encodings [0.0]
誤り訂正特性を持つ実効的なフェルミオン・ツー・キュービット符号化を探索する。
安定化器と論理演算子の重みを著しく改善する有望な高距離符号化を複数報告する。
論文 参考訳(メタデータ) (2024-02-23T15:32:57Z) - Addressing Stopping Failures for Small Set Flip Decoding of Hypergraph
Product Codes [1.04049929128816]
ハイパーグラフ製品コードは、定レート量子LDPC符号の有望なファミリーである。
Small-Set-Flip(texttSSF$)は線形時間復号アルゴリズムである。
我々は,障害停止後の$textttSSF$を補うために,Projection-Along-a-Line(texttPAL$)デコーダと呼ばれる新しいデコードアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-11-01T22:08:49Z) - ChatRule: Mining Logical Rules with Large Language Models for Knowledge
Graph Reasoning [107.61997887260056]
そこで我々は,知識グラフ上の論理ルールをマイニングするための大規模言語モデルの力を解き放つ新しいフレームワークChatRuleを提案する。
具体的には、このフレームワークは、KGのセマンティック情報と構造情報の両方を活用するLLMベースのルールジェネレータで開始される。
生成されたルールを洗練させるために、ルールランキングモジュールは、既存のKGから事実を取り入れてルール品質を推定する。
論文 参考訳(メタデータ) (2023-09-04T11:38:02Z) - Fast Deterministic Black-box Context-free Grammar Inference [7.637155559284357]
State-of-the-artアプローチは、平らなパースツリーから始まる文法規則を一般化する。
アルバダの一般化の多くは、共通の言語概念のネスト規則に違反している。
結果、TreeVadaは経験的な比較で高速で高品質な文法を得た。
論文 参考訳(メタデータ) (2023-08-11T14:45:26Z) - Fault-Tolerant Computing with Single Qudit Encoding [49.89725935672549]
単一マルチレベルキューディットに実装された安定化器量子エラー訂正符号について論じる。
これらのコードは、quditの特定の物理的エラーに合わせてカスタマイズすることができ、効果的にそれらを抑制することができる。
分子スピン四重項上のフォールトトレラントな実装を実証し、線形キューディットサイズのみの成長を伴うほぼ指数関数的な誤差抑制を示す。
論文 参考訳(メタデータ) (2023-07-20T10:51:23Z) - Efficient Semiring-Weighted Earley Parsing [71.77514972816347]
本稿では,様々なスピードアップを伴うEarey (1970) の文脈自由構文解析アルゴリズムの,推論システムという形での参照記述を提供する。
私たちのプレゼンテーションには、Earey氏の$O(N3|GR|)$から、既知の最悪のランタイム改善が含まれています。
半重み付き推論への一般化を扱い、Stolcke (1995)のような文法を前処理して推論サイクルを排除し、さらに文プレフィックスの重みを計算するStolckeの手法を一般化する。
論文 参考訳(メタデータ) (2023-07-06T13:33:59Z) - GRACE: Discriminator-Guided Chain-of-Thought Reasoning [75.35436025709049]
本稿では, 正しい推論手順を導出するために, GRACE (CorrectnEss Discriminator) を用いたチェーン・オブ・シークレット・リAsoningを提案する。
GRACEは、正しいステップと間違ったステップに対して対照的な損失で訓練された判別器を採用しており、復号時に次のステップ候補を採点するために使用される。
論文 参考訳(メタデータ) (2023-05-24T09:16:51Z) - Quantum computation on a 19-qubit wide 2d nearest neighbour qubit array [59.24209911146749]
本稿では,1次元に制約された量子ビット格子の幅と物理閾値の関係について検討する。
我々は、表面コードを用いた最小レベルのエンコーディングでエラーバイアスを設計する。
このバイアスを格子サージャリングサーフェスコードバスを用いて高レベルなエンコーディングで処理する。
論文 参考訳(メタデータ) (2022-12-03T06:16:07Z) - Learning grammar with a divide-and-concur neural network [4.111899441919164]
本研究では,文脈自由文法推論に対する分割・コンカレント反復予測手法を実装した。
本手法は比較的少数の離散パラメータを必要とするため,推測文法を直接解釈可能である。
論文 参考訳(メタデータ) (2022-01-18T22:42:43Z) - Autoregressive Belief Propagation for Decoding Block Codes [113.38181979662288]
誤り訂正符号の復号化にグラフニューラルネットワークを用いた最近の手法を再検討する。
本手法は,他手法がゼロワードでのみ学習できる対称性条件に反する。
1つの単語でトレーニングする余地がなく、関連するサンプル空間のごく一部でトレーニングできないにもかかわらず、効果的なトレーニングを実演する。
論文 参考訳(メタデータ) (2021-01-23T17:14:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。