論文の概要: 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境界に基づいている。 ちなみに、最小ブロック符号におけるルールの数は、英語のテキストや文字のランダムな置換など、長期記憶源と無記憶源とを明確に区別できないことも実証的に示している。 これは我々の以前の期待と矛盾する。

関連論文リスト

• Incremental Context-free Grammar Inference in Black Box Settings [17.601446198181048]
  ブラックボックスの文脈自由文法推論は多くの実践的な設定において重要な課題である。 そこで本研究では,サンプル文字列をより小さな単位に分割し,文法を漸進的に推論する手法を提案する。 我々の手法であるKedavraは、より優れた文法品質(精度とリコールの強化)、より高速な実行、経験的比較による可読性の向上を実証した。
  論文  参考訳（メタデータ） (2024-08-29T17:00:38Z)
• Markov Constraint as Large Language Model Surrogate [49.86129209397701]
  NgramMarkovは制約プログラミング(CP)におけるテキスト生成に特化している これは文のn-グラムの確率の積を制限する。 5グラムではなく4グラムで現実の問題が初めて解決された。
  論文  参考訳（メタデータ） (2024-06-11T16:09:53Z)
• Grammar-Aligned Decoding [30.972850034752884]
  LLM(Large Language Models)は、プログラムコード、数学的公式、整形されたマークアップなどの高度に構造化された出力を確実に生成するのに苦労する。 制約付き復号法は、LLMが出力できるトークンを各ステップで厳格に制限し、出力が与えられた制約と一致することを保証することによってこの問題を軽減する。 本稿では,GCD技術がLLMの分布を歪め,文法的だがLLMに比例しない確率で現れる出力を導出することを示す。
  論文  参考訳（メタデータ） (2024-05-31T17:39:15Z)
• Language Generation with Strictly Proper Scoring Rules [70.340673452404]
  本稿では,非局所的なスコアリングルールを用いた言語モデリングが可能な,スコアリングルールを言語生成に適用するための戦略を提案する。 対数スコアの代替として、ブライアスコアと球面スコアの2つの古典的厳密なスコアルールを用いて言語生成モデルを訓練する。
  論文  参考訳（メタデータ） (2024-05-29T09:09:00Z)
• Decoding at the Speed of Thought: Harnessing Parallel Decoding of Lexical Units for LLMs [57.27982780697922]
  大規模言語モデルは、自然言語の理解と生成において例外的な能力を示した。 しかし、それらの生成速度は、その復号過程の本質的にシーケンシャルな性質によって制限される。 本稿では,データ駆動方式で実装された新しいデコーディング手法であるLexical Unit Decodingを紹介する。
  論文  参考訳（メタデータ） (2024-05-24T04:35:13Z)
• 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)
• Fast Deterministic Black-box Context-free Grammar Inference [7.637155559284357]
  State-of-the-artアプローチは、平らなパースツリーから始まる文法規則を一般化する。 アルバダの一般化の多くは、共通の言語概念のネスト規則に違反している。 結果、TreeVadaは経験的な比較で高速で高品質な文法を得た。
  論文  参考訳（メタデータ） (2023-08-11T14:45:26Z)
• Efficient Semiring-Weighted Earley Parsing [71.77514972816347]
  本稿では,様々なスピードアップを伴うEarey (1970) の文脈自由構文解析アルゴリズムの,推論システムという形での参照記述を提供する。 私たちのプレゼンテーションには、Earey氏の$O(N3|GR|)$から、既知の最悪のランタイム改善が含まれています。 半重み付き推論への一般化を扱い、Stolcke (1995)のような文法を前処理して推論サイクルを排除し、さらに文プレフィックスの重みを計算するStolckeの手法を一般化する。
  論文  参考訳（メタデータ） (2023-07-06T13:33:59Z)
• 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)

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

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