論文の概要: Hardness of Learning Regular Languages in the Next Symbol Prediction Setting

• arxiv url: http://arxiv.org/abs/2510.18634v1
• Date: Tue, 21 Oct 2025 13:37:34 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-25 03:08:13.630961
• Title: Hardness of Learning Regular Languages in the Next Symbol Prediction Setting
• Title（参考訳）: 記号予測設定における正規言語学習の難しさ
• Authors: Satwik Bhattamishra, Phil Blunsom, Varun Kanade,
• Abstract要約: 我々は,次のシンボル予測設定における言語の学習可能性について検討する。 我々は、PAC学習分析に適するように設定を定式化する。
• 参考スコア（独自算出の注目度）: 22.171557295567197
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the learnability of languages in the Next Symbol Prediction (NSP) setting, where a learner receives only positive examples from a language together with, for every prefix, (i) whether the prefix itself is in the language and (ii) which next symbols can lead to an accepting string. This setting has been used in prior works to empirically analyze neural sequence models, and additionally, we observe that efficient algorithms for the NSP setting can be used to learn the (truncated) support of language models. We formalize the setting so as to make it amenable to PAC-learning analysis. While the setting provides a much richer set of labels than the conventional classification setting, we show that learning concept classes such as DFAs and Boolean formulas remains computationally hard. The proof is via a construction that makes almost all additional labels uninformative, yielding a reduction from the conventional learning problem to learning with NSP labels. Under cryptographic assumptions, the reduction implies that the problem of learning DFAs is computationally hard in the NSP setting.
• Abstract（参考訳）: そこでは,各プレフィックスに対して,学習者が言語から肯定的な例のみを受信する,Next Symbol Prediction (NSP)設定における言語の学習可能性について検討する。 (i)接頭辞自体が言語に含まれるか否か (ii)次のシンボルが受け入れられる文字列に導くことができる。 この設定は、ニューラルシークエンスモデルを経験的に分析するための先行研究で使われており、さらに、NSP設定のための効率的なアルゴリズムが言語モデルの(取り外しされた)サポートを学ぶのに利用できることを観察している。 我々は、PAC学習分析に適するように設定を定式化する。 この設定は従来の分類設定よりもずっとリッチなラベルセットを提供するが、DFAやブール式のような学習概念クラスは計算的に難しいままであることを示す。 この証明は、ほとんど全ての追加ラベルを非形式的にし、従来の学習問題からNSPラベルでの学習に還元する構成である。 暗号的仮定では、この還元は、NSP設定においてDFAを学習する問題は計算的に困難であることを意味する。

関連論文リスト

• Benchmarking Prosody Encoding in Discrete Speech Tokens [13.60092490447892]
  本研究は, 韻律に対する感性に基づく韻律符号化に着目し, 離散トークンを設計するための実践的ガイドラインを提供することを目的とする。 特に、言語モデルでは、意味的内容だけでなく、韻律的特徴も反映する応答を理解し、生成することが期待されている。
  論文  参考訳（メタデータ） (2025-08-15T05:11:16Z)
• Signs as Tokens: A Retrieval-Enhanced Multilingual Sign Language Generator [55.94334001112357]
  テキスト入力から3Dサインアバターを自動回帰的に生成できる多言語手話モデルSigns as Tokens(SOKE)を導入する。 単語レベルの正確な記号を提供するために,外部記号辞書を組み込んだ検索強化SLG手法を提案する。
  論文  参考訳（メタデータ） (2024-11-26T18:28:09Z)
• Training Neural Networks as Recognizers of Formal Languages [87.06906286950438]
  ニューラルネットワークを文字列のバイナリ分類器として直接訓練し評価する。 3つのニューラルアーキテクチャに対して、チョムスキー階層の様々な言語について結果を提供する。 我々の貢献は、将来の研究において、言語認識の主張を理論的に健全に検証するのに役立つだろう。
  論文  参考訳（メタデータ） (2024-11-11T16:33:25Z)
• A Noise-tolerant Differentiable Learning Approach for Single Occurrence Regular Expression with Interleaving [19.660606583532598]
  本研究では,音のある文字列の集合からインターリービング(SOIRE)を用いて単一発生正規表現を学習する問題について検討する。 従来の研究のほとんどは制限されたSOIREしか学習せず、ノイズの多いデータでは堅牢ではない。 本稿では,SOIREのための耐雑音性差分学習手法SOIREDLを提案する。
  論文  参考訳（メタデータ） (2022-12-01T09:05:43Z)
• CCPrefix: Counterfactual Contrastive Prefix-Tuning for Many-Class Classification [57.62886091828512]
  多クラス分類のための新しいプレフィックスチューニング手法であるCCPrefixを提案する。 基本的に、ラベル空間における実数対から派生したインスタンス依存の軟式接頭辞は、多クラス分類における言語動詞化を補完するために利用される。
  論文  参考訳（メタデータ） (2022-11-11T03:45:59Z)
• Reordering Examples Helps during Priming-based Few-Shot Learning [6.579039107070663]
  PERO は 10 個の例から効率よく一般化できることを示す。 提案手法が感情分類,自然言語推論,事実検索のタスクに与える影響を実証する。
  論文  参考訳（メタデータ） (2021-06-03T11:02:36Z)
• NSL: Hybrid Interpretable Learning From Noisy Raw Data [66.15862011405882]
  本稿では,ラベル付き非構造データから解釈可能なルールを学習するニューラルシンボリック学習フレームワークNSLを提案する。 NSLは、機能抽出のためのトレーニング済みニューラルネットワークと、解集合セマンティクスに基づくルール学習のための最先端のILPシステムであるFastLASを組み合わせる。 NSLは、MNISTデータから堅牢なルールを学び、ニューラルネットワークやランダムフォレストベースラインと比較して、比較または優れた精度を達成できることを実証します。
  論文  参考訳（メタデータ） (2020-12-09T13:02:44Z)

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

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