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

• arxiv url: http://arxiv.org/abs/2209.13636v3
• Date: Wed, 16 Apr 2025 08:23:43 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-26 11:04:35.587489
• Title: Local Grammar-Based Coding Revisited
• Title（参考訳）: 局所文法に基づく符号化の再検討
• Authors: Łukasz Dębowski,
• Abstract要約: 最小限の局所文法ベースの符号化では、入力文字列は最小出力長が定義された文法として表現される。 我々は、ジップフの法則を思い出させるような、ランク付けされた確率の単純な調和的境界を導出する。 我々は語彙サイズに関する既知の境界を洗練し、相互情報と冗長性による部分的なパワー・ロー同値を示す。 有限語彙が経験的ランクリストである文法ベースのコードを分析し、そのようなコードも普遍的であることを証明した。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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の法則と大規模言語モデルのニューラルスケーリング法則を結びつけることに関係している。 第三に、固定無限語彙を持つ普遍符号のためのフレームワークを開発し、経験的データとは無関係なランク付けパターンとして普遍符号を再放送する。 最後に、有限語彙が経験的ランクリストである文法ベースのコードを分析し、そのようなコードも普遍的であることを証明した。 これらの結果により、普遍文法に基づくコーディングの基礎が拡張され、人間の言語や言語モデルに対する電力法則への接続が再確認される。

関連論文リスト

• CodeI/O: Condensing Reasoning Patterns via Code Input-Output Prediction [47.17755403213469]
  我々は,文脈的に構築されたコードに埋め込まれた多様な推論パターンを凝縮する新しい手法であるCodeI/Oを提案する。 与えられたコードとテストケースを完全に自然言語で予測するためにモデルをトレーニングすることで、それらを普遍的な推論プリミティブに公開します。 実験の結果、CodeI/Oは記号、科学、論理学、数学と数値、常識推論タスクに一貫した改善をもたらすことが示された。
  論文  参考訳（メタデータ） (2025-02-11T07:26:50Z)
• Training Neural Networks as Recognizers of Formal Languages [87.06906286950438]
  ニューラルネットワークを文字列のバイナリ分類器として直接訓練し評価する。 3つのニューラルアーキテクチャに対して、チョムスキー階層の様々な言語について結果を提供する。 我々の貢献は、将来の研究において、言語認識の主張を理論的に健全に検証するのに役立つだろう。
  論文  参考訳（メタデータ） (2024-11-11T16:33:25Z)
• 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)
• Sparse Logistic Regression with High-order Features for Automatic Grammar Rule Extraction from Treebanks [6.390468088226495]
  本研究では,木バンクから重要な粒度の文法パターンを抽出し,探索する手法を提案する。 我々は,異なる言語にまたがる記述や規則を抽出し,合意と語順の2つの言語現象について考察する。 我々の手法は、スペイン語、フランス語、ウーロフにおける有名な文法規則とあまり知られていない重要な文法規則の両方を捉えている。
  論文  参考訳（メタデータ） (2024-03-26T09:39:53Z)
• Rewriting the Code: A Simple Method for Large Language Model Augmented Code Search [7.822427053078387]
  Generation-Augmented Retrieval (GAR)フレームワークは、クエリを拡張するための例のコードスニペットを生成する。 本稿では、forスタイルの正規化内でコード(ReCo)を書き換える、シンプルで効果的な方法を提案する。 コードスタイル類似度(Code Style similarity)は、コード内のスタイリスティック類似度を定量化するための最初のメートル法である。
  論文  参考訳（メタデータ） (2024-01-09T12:12:50Z)
• 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)
• Incorporating Constituent Syntax for Coreference Resolution [50.71868417008133]
  本稿では,構成構文構造をグラフベースで組み込む手法を提案する。 また、高次近傍情報を利用して構成木に富んだ構造をエンコードすることも検討する。 on the English and Chinese parts of OntoNotes 5.0 benchmark shows that our proposed model beats a strong baseline or a new-of-the-art performance。
  論文  参考訳（メタデータ） (2022-02-22T07:40:42Z)
• Grammar-Based Grounded Lexicon Learning [68.59500589319023]
  G2L2は、構成的および基礎的な言語表現を学ぶための語彙主義的なアプローチである。 G2L2の中核には語彙エントリの集まりがあり、各単語を構文型とニューロシンボリックセマンティックプログラムにマッピングする。 G2L2は、少量のデータから新しい単語合成へと一般化することができる。
  論文  参考訳（メタデータ） (2022-02-17T18:19:53Z)
• Learning grammar with a divide-and-concur neural network [4.111899441919164]
  本研究では,文脈自由文法推論に対する分割・コンカレント反復予測手法を実装した。 本手法は比較的少数の離散パラメータを必要とするため,推測文法を直接解釈可能である。
  論文  参考訳（メタデータ） (2022-01-18T22:42:43Z)
• Rule Augmented Unsupervised Constituency Parsing [11.775897250472116]
  本稿では,構文規則の形で存在する言語について,非常に汎用的な言語知識を活用するアプローチを提案する。 MNLIとWSJという2つのベンチマークデータセットで、最先端の新たな結果を得る。
  論文  参考訳（メタデータ） (2021-05-21T08:06:11Z)
• How (Non-)Optimal is the Lexicon? [35.91590073820011]
  我々は,レキシコンの符号化理論的な見方を取り入れ,新しい生成統計モデルを用いる。 7つの類型的多様言語からコーパスを抽出し、これらの上限を用いてレキシコンの最適性を定量化する。 我々は、(構成的)形態学とグラフ戦術が自然符号の複雑さのほとんどを十分に説明できることを発見した。
  論文  参考訳（メタデータ） (2021-04-29T11:55:47Z)
• Autoregressive Belief Propagation for Decoding Block Codes [113.38181979662288]
  誤り訂正符号の復号化にグラフニューラルネットワークを用いた最近の手法を再検討する。 本手法は,他手法がゼロワードでのみ学習できる対称性条件に反する。 1つの単語でトレーニングする余地がなく、関連するサンプル空間のごく一部でトレーニングできないにもかかわらず、効果的なトレーニングを実演する。
  論文  参考訳（メタデータ） (2021-01-23T17:14:55Z)
• CodeBLEU: a Method for Automatic Evaluation of Code Synthesis [57.87741831987889]
  コード合成の分野では、一般的に使用される評価基準はBLEUまたは完全精度である。 我々はCodeBLEUと呼ばれる新しい自動評価指標を導入する。 n-gramマッチングにおけるBLEUの強度を吸収し、抽象構文木(AST)やデータフローによるコードセマンティクスを通じてコード構文を注入する。
  論文  参考訳（メタデータ） (2020-09-22T03:10:49Z)

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

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