論文の概要: Learning Erasing Equal-Length Relational Pattern Languages in the Limit from Positive Data over Binary Alphabets

• arxiv url: http://arxiv.org/abs/2610.39156v1
• Date: Thu, 29 Oct 2026 01:41:18 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-31 05:25:12.443348
• Title: Learning Erasing Equal-Length Relational Pattern Languages in the Limit from Positive Data over Binary Alphabets
• Title（参考訳）: 2元Alphabet上の正値データから等長関係パターン言語を学習する
• Abstract要約: アングルインのパターン言語は、与えられた関係に立つ変数の繰り返し発生のために置換された文字列を要求することで一般化される。 非学習性はすでに、変数の最大値が3つあるパターンによって生成される言語の制限されたサブクラスを保っていることを示す。
• 参考スコア（独自算出の注目度）: 2.1576477867114585
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Relational pattern languages generalize Angluin's pattern languages by requiring the strings substituted for repeated occurrences of a variable to stand in a given relation, rather than to be identical. We study erasing pattern languages under the equal-length relation, where all occurrences of a variable must be replaced by strings of the same length. Over alphabets with at least three letters, this class is known to be learnable in the limit from positive data. We show that over a binary alphabet it is not, which resolves an open question from earlier work. Our proof reveals that non-learnability already holds for the restricted subclass of languages generated by patterns that have exactly three maximal substrings of variables. We then show that patterns with at most two maximal substrings of variables are learnable in the limit from positive data for every alphabet of size at least two. If the target pattern is known to have at most one maximal substring of variables, this can even be achieved by an iterative learner, which updates its hypothesis using only the current example and its previous hypothesis.
• Abstract（参考訳）: リレーショナル・パターン言語は、アングルインのパターン言語を一般化するために、変数の繰り返し発生のために置換された文字列が同一であるのではなく、与えられた関係に立つように要求する。 変数のすべての発生を同じ長さの文字列で置き換えなければならない、等長関係の下でパターン言語を消去することについて検討する。 少なくとも3文字のアルファベットでは、このクラスは正のデータから極限で学習できることが知られている。 2進アルファベットではそうではないことが示され、これは初期の研究から解き放たれた疑問を解消する。 我々の証明は、変数の最大3つの部分列を持つパターンによって生成される言語の制限されたサブクラスを、非学習性が既に保持していることを明らかにする。 次に、変数の最大2つの部分列を持つパターンは、少なくとも2つのサイズのアルファベットごとに正のデータから学習可能であることを示す。 対象のパターンが少なくとも1つの最大部分列を持つことが知られている場合、これは反復学習者によって達成され、現在の例とそれ以前の仮説のみを用いて仮説を更新する。

関連論文リスト

• LangMAP: A Language-Adaptive Approach to Tokenization [30.443524396044428]
  LangMAPは、UnigramLMアルゴリズムを多言語設定に拡張するトークン化スキームである。 マルチ言語モデルをスクラッチからトレーニングしたり、事前訓練されたモデルのトークン化ツールを個別の言語に適応する際にも使用することができる。 言語ラベルはトレーニング時に必要とされているが、アルゴリズムの重要な特徴は、入力言語の知識なしに推論時に言語固有のトークン化を実行することである。
  論文  参考訳（メタデータ） (2026-06-22T16:32:00Z)
• The Inclusion Depth of Pattern Languages: An Open Problem in Algorithmic Learning Theory [7.317669651319179]
  この注記は、パターン言語の包含深さを計算する問題の定式化である。 中心的な開問題は、包含深さ ID_Sigma(p) が任意の有限アルファベット Sigma 上のすべてのパターン p に対して計算可能であるかどうかである。 単純な予想式 ID_Sigma(p) = 2|p| - #var(p) - 1 は線形時間アルゴリズムを意味する。
  論文  参考訳（メタデータ） (2026-05-28T11:19:25Z)
• Random Text, Zipf's Law, Critical Length,and Implications for Large Language Models [0.0]
  我々は、故意に単純で完全に非言語的なテキストモデルについて研究する。 単語は、非空間シンボルの最大ブロックとして定義される。
  論文  参考訳（メタデータ） (2025-11-14T23:05:59Z)
• Training Neural Networks as Recognizers of Formal Languages [87.06906286950438]
  ニューラルネットワークを文字列のバイナリ分類器として直接訓練し評価する。 3つのニューラルアーキテクチャに対して、チョムスキー階層の様々な言語について結果を提供する。 我々の貢献は、将来の研究において、言語認識の主張を理論的に健全に検証するのに役立つだろう。
  論文  参考訳（メタデータ） (2024-11-11T16:33:25Z)
• Lexinvariant Language Models [84.2829117441298]
  離散語彙記号から連続ベクトルへの写像であるトークン埋め込みは、任意の言語モデル(LM)の中心にある 我々は、語彙記号に不変であり、したがって実際に固定トークン埋め込みを必要としないテクスチトレキシン変種モデルについて研究する。 十分長い文脈を条件として,レキシン変項LMは標準言語モデルに匹敵する難易度が得られることを示す。
  論文  参考訳（メタデータ） (2023-05-24T19:10:46Z)
• Linear-Time Modeling of Linguistic Structure: An Order-Theoretic Perspective [97.57162770792182]
  文字列内のトークンのペア間の関係をモデル化するタスクは、自然言語を理解する上で不可欠な部分である。 これらの徹底的な比較は避けられ、さらに、トークン間の関係を文字列上の部分順序としてキャストすることで、複雑さを線形に減らすことができる。 提案手法は,文字列中の各トークンの実際の数を並列に予測し,それに従ってトークンをソートすることで,文字列内のトークンの総順序を決定する。
  論文  参考訳（メタデータ） (2023-05-24T11:47:35Z)
• Learning Languages with Decidable Hypotheses [1.2728819383164875]
  極限における言語学習において、最も一般的な仮説は、ある言語の列挙子を与えることである。 いわゆる$W$-indexは任意の計算可能可算言語を命名することができる。 我々は、任意の決定可能な言語、すなわち特徴関数のプログラムを命名できる別のシステム($C$-indices)を使用している。
  論文  参考訳（メタデータ） (2020-10-15T09:27:47Z)
• Phonological Features for 0-shot Multilingual Speech Synthesis [50.591267188664666]
  単言語モデルにおいても,トレーニング中に見つからない言語に対して,コードスイッチングが可能であることを示す。 テスト時には、訓練で見たことのない音の近似を含む、新しい言語で、理解不能で、コードスイッチトされた音声を生成する。
  論文  参考訳（メタデータ） (2020-08-06T18:25:18Z)

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

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