論文の概要: A Characterization of List Language Identification in the Limit

• arxiv url: http://arxiv.org/abs/2511.04103v1
• Date: Thu, 06 Nov 2025 06:39:20 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-07 20:17:53.329177
• Title: A Characterization of List Language Identification in the Limit
• Title（参考訳）: 限界におけるリスト言語識別の一特徴
• Authors: Moses Charikar, Chirag Pabbaraju, Ambuj Tewari,
• Abstract要約: 本研究では,対象言語からのサンプルの列を与えられた限界における言語識別の問題について検討する。 学習者の目標は、ある有限時間を超える推測が正しいように、対象言語に対する推測列を出力することである。 制限で特定できる$k$-listの言語コレクションの正確な特徴付けを与えます。
• 参考スコア（独自算出の注目度）: 31.38302438096483
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the problem of language identification in the limit, where given a sequence of examples from a target language, the goal of the learner is to output a sequence of guesses for the target language such that all the guesses beyond some finite time are correct. Classical results of Gold showed that language identification in the limit is impossible for essentially any interesting collection of languages. Later, Angluin gave a precise characterization of language collections for which this task is possible. Motivated by recent positive results for the related problem of language generation, we revisit the classic language identification problem in the setting where the learner is given the additional power of producing a list of $k$ guesses at each time step. The goal is to ensure that beyond some finite time, one of the guesses is correct at each time step. We give an exact characterization of collections of languages that can be $k$-list identified in the limit, based on a recursive version of Angluin's characterization (for language identification with a list of size $1$). This further leads to a conceptually appealing characterization: A language collection can be $k$-list identified in the limit if and only if the collection can be decomposed into $k$ collections of languages, each of which can be identified in the limit (with a list of size $1$). We also use our characterization to establish rates for list identification in the statistical setting where the input is drawn as an i.i.d. stream from a distribution supported on some language in the collection. Our results show that if a collection is $k$-list identifiable in the limit, then the collection can be $k$-list identified at an exponential rate, and this is best possible. On the other hand, if a collection is not $k$-list identifiable in the limit, then it cannot be $k$-list identified at any rate that goes to zero.
• Abstract（参考訳）: 対象言語からの例の列を与えられた場合、学習者の目標は、対象言語に対する推測列を出力し、ある有限時間を超える推測が正しいようにすることである。 Goldの古典的な結果は、その限界における言語識別は、本質的には興味深い言語のコレクションでは不可能であることを示した。 その後、Angluin氏は、このタスクが可能である言語コレクションの正確なキャラクタリゼーションを提供した。 近年の言語生成問題に対する肯定的な結果に触発され、学習者が各ステップで$k$の推測リストを作成できる追加の権限を与えられた場合に、古典的な言語識別問題を再考する。 目的は、ある有限時間を超えて、予想の1つが各時点のステップで正しいことを保証することである。 我々は、Angluinのキャラクタリゼーションの再帰バージョン(サイズが1ドルである言語識別のために)に基づいて、制限で識別できる$k$-listの言語のコレクションの正確なキャラクタリゼーションを与える。 言語コレクションが制限で$k$-listを識別できるのは、そのコレクションが$k$の言語コレクションに分解できる場合に限る。 また,この特徴量を用いて,コレクション内のある言語でサポートされている分布から,入力がi.d.ストリームとして描画される統計的状況において,リストの識別率を確立する。 我々の結果は、コレクションが制限で識別可能な$k$-listであれば、指数率で$k$-listを識別でき、これが最善であることを示している。 一方、コレクションが制限で識別可能な$k$-listでなければ、0になる任意のレートで$k$-listを識別することはできない。

関連論文リスト

• Density Measures for Language Generation [2.2872032473279065]
  言語生成アルゴリズムの妥当性と広さのトレードオフについて検討する。 限界における言語生成のための既存のアルゴリズムは、真の言語でゼロ密度を持つ出力セットを生成する。 しかしながら、出力が厳密に正の密度を持つ極限における言語生成のアルゴリズムが$K$であることを示す。
  論文  参考訳（メタデータ） (2025-04-19T18:08:18Z)
• Exploring Facets of Language Generation in the Limit [10.18252143035175]
  任意の可算言語コレクションは、その極限において非一様生成の強い特性を持つ生成子を持つことを示す。 我々は,[KM24]の生成アルゴリズムにおける妥当性と幅の緊張関係を,徹底的な生成の定義を導入して定式化する。 また,包括的生成が可能な言語コレクションの正確な特徴付けも提供する。
  論文  参考訳（メタデータ） (2024-11-22T22:13:40Z)
• On the Limits of Language Generation: Trade-Offs Between Hallucination and Mode Collapse [26.73254784599135]
  未知の言語からのサンプルを考えると、言語モデルはトレーニングで見えない有効な文字列を生成するべきである。 そうでなければ、無効な文字列を出力することは「幻覚」を構成し、全範囲のキャプチャーに失敗すると「モード崩壊」につながる。 我々は,ゴールドとアングルインをベースとした統計的言語生成システムにおいて,これを検証した。
  論文  参考訳（メタデータ） (2024-11-14T18:06:55Z)
• Language Generation in the Limit [0.7787343335258782]
  候補言語の可算リストに限って生成できるエージェントが存在することを示す。 これは、言語学習のよく研究されたモデルにおいて、ゴールドとアングルインによる否定的な結果と劇的に対照的である。
  論文  参考訳（メタデータ） (2024-04-10T05:53:25Z)
• AdaCCD: Adaptive Semantic Contrasts Discovery Based Cross Lingual Adaptation for Code Clone Detection [69.79627042058048]
  AdaCCDは、その言語でアノテーションを使わずに、新しい言語のクローンコードを検出する新しい言語間適応手法である。 5つのプログラミング言語からなる多言語コードクローン検出ベンチマークを構築し,AdaCCDの言語間適応性を評価する。
  論文  参考訳（メタデータ） (2023-11-13T12:20:48Z)
• Inducing Language-Agnostic Multilingual Representations [61.97381112847459]
  言語間の表現は、世界中のほとんどの言語でNLP技術が利用可能になる可能性がある。 i) 対象言語のベクトル空間をピボットソース言語に再配置すること、(ii) 言語固有の手段と分散を取り除くこと、(ii) 副産物としての埋め込みの識別性を向上すること、(iii) 形態的制約や文の並べ替えを除去することによって言語間の入力類似性を高めること、の3つのアプローチを検討する。
  論文  参考訳（メタデータ） (2020-08-20T17:58:56Z)
• XCOPA: A Multilingual Dataset for Causal Commonsense Reasoning [68.57658225995966]
  XCOPA (Cross-lingual Choice of Plausible Alternatives) は11言語における因果コモンセンス推論のための多言語データセットである。 提案手法は,翻訳に基づく転送と比較して,現在の手法の性能が低下していることを明らかにする。
  論文  参考訳（メタデータ） (2020-05-01T12:22:33Z)
• On the Importance of Word Order Information in Cross-lingual Sequence Labeling [80.65425412067464]
  ソース言語の単語順に適合する言語間モデルでは、ターゲット言語を処理できない可能性がある。 本研究では,ソース言語の単語順序に敏感なモデルを作成することで,対象言語の適応性能が向上するかどうかを検討する。
  論文  参考訳（メタデータ） (2020-01-30T03:35:44Z)

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

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