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

• arxiv url: http://arxiv.org/abs/2209.13636v2
• Date: Wed, 12 Jul 2023 16:15:57 GMT
• ステータス: 翻訳完了
• システム内更新日: 2023-07-13 20:24:51.398217
• 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 has been 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 article, 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境界に基づいている。 ちなみに、最小ブロック符号におけるルールの数は、英語のテキストや文字のランダムな置換など、長期記憶源と無記憶源とを明確に区別できないことも実証的に示している。 これは我々の以前の期待と矛盾する。

関連論文リスト

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

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

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