論文の概要: Local Grammar-Based Coding Revisited

• arxiv url: http://arxiv.org/abs/2209.13636v3
• Date: Wed, 16 Apr 2025 08:23:43 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-17 18:06:22.513208
• Title: Local Grammar-Based Coding Revisited
• Title（参考訳）: 局所文法に基づく符号化の再検討
• Authors: Łukasz Dębowski,
• Abstract要約: 最小限の局所文法ベースの符号化では、入力文字列は最小出力長が定義された文法として表現される。 我々は、ジップフの法則を思い出させるような、ランク付けされた確率の単純な調和的境界を導出する。 我々は語彙サイズに関する既知の境界を洗練し、相互情報と冗長性による部分的なパワー・ロー同値を示す。 有限語彙が経験的ランクリストである文法ベースのコードを分析し、そのようなコードも普遍的であることを証明した。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: In the setting of minimal local grammar-based coding, the input string is represented as a grammar with the minimal output length defined via simple symbol-by-symbol encoding. This paper discusses four contributions to this field. First, we invoke a simple harmonic bound on ranked probabilities, which reminds Zipf's law and simplifies universality proofs for minimal local grammar-based codes. Second, we refine known bounds on the vocabulary size, showing its partial power-law equivalence with mutual information and redundancy. These bounds are relevant for linking Zipf's law with the neural scaling law for large language models. Third, we develop a framework for universal codes with fixed infinite vocabularies, recasting universal coding as matching ranked patterns that are independent of empirical data. Finally, we analyze grammar-based codes with finite vocabularies being empirical rank lists, proving that that such codes are also universal. These results extend foundations of universal grammar-based coding and reaffirm previously stated connections to power laws for human language and language models.
• Abstract（参考訳）: 最小限の局所文法ベースの符号化では、入力文字列は単純なシンボルバイシンボル符号化によって定義された最小出力長の文法として表現される。 本稿では,この分野への4つの貢献について論じる。 これはZipfの法則を思い出させ、最小限の局所文法ベースの符号に対する普遍性証明を単純化する。 第二に、語彙サイズに関する既知の境界を精査し、相互情報と冗長性による部分的なパワー・ロー同値を示す。 これらの境界は、Zipfの法則と大規模言語モデルのニューラルスケーリング法則を結びつけることに関係している。 第三に、固定無限語彙を持つ普遍符号のためのフレームワークを開発し、経験的データとは無関係なランク付けパターンとして普遍符号を再放送する。 最後に、有限語彙が経験的ランクリストである文法ベースのコードを分析し、そのようなコードも普遍的であることを証明した。 これらの結果により、普遍文法に基づくコーディングの基礎が拡張され、人間の言語や言語モデルに対する電力法則への接続が再確認される。

関連論文リスト

• 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)

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

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