論文の概要: Identifiability and Order-Dimension Limits of In-Context Learning on Partial Orders

• arxiv url: http://arxiv.org/abs/2608.14004v1
• Date: Fri, 14 Aug 2026 06:47:40 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-17 20:14:29.297508
• Title: Identifiability and Order-Dimension Limits of In-Context Learning on Partial Orders
• Title（参考訳）: 部分順序の非文脈学習における識別可能性と順序-次元限界
• Abstract要約: 本研究では、論理的識別可能性、指導コスト、構造的複雑さ、および正規座標復号器クラスの正確な容量を分離する部分順序に基づく文脈内学習理論を開発する。 我々は、プロンプト依存の$s$-コーディネートデコーダを形式化し、古典的な座標次同値を用いて正確な表現境界を得る。
• 参考スコア（独自算出の注目度）: 18.267999630668665
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In-context learning is commonly formalized as inference from examples of a function. Partial orders instead combine transitivity, antisymmetry, and incomparability, so a finite prompt may not determine a queried comparison. We develop a theory of in-context learning on partial orders that separates logical identifiability, prompt teaching cost, structural complexity, and the exact capacity of a formal coordinate-decoder class. A version-space semantics makes background knowledge and open- versus closed-world assumptions explicit. For finite open-world prompts with positive and negative comparisons, we prove an exact completion trichotomy: after taking the reflexive transitive closure of the positive demonstrations, a query is forced true, forced false because every true completion creates a cycle or violates a negative demonstration, or remains genuinely ambiguous. For a known $n$-element universe, we characterize the open-world teaching number as the number of covers plus a blocker-set hitting number, prove that its maximum over all $n$-element posets is $n(n-1)$ and is uniquely attained by the antichain, and identify the blocker term as the exact cost of open-world rather than complete-Hasse semantics. We formalize prompt-dependent $s$-coordinate decoders and use the classical coordinate-order equivalence to obtain an exact representation boundary: dimension at most $s$ is necessary and sufficient, while width at most $s$ is a convenient sufficient condition.
• Abstract（参考訳）: インコンテキスト学習は、関数の例からの推論として一般的に形式化される。 部分順序は推移性、反対称性、非可換性を結合するので、有限プロンプトはクエリされた比較を決定することができない。 本研究では,論理的識別可能性,指導コスト,構造的複雑性,および正規座標復号器の正確な容量を分離する部分順序に基づく文脈内学習理論を開発する。 バージョン空間のセマンティクスは、背景知識とオープンワールドとクローズワールドの仮定を明確にする。 正および負の比較を持つ有限開世界プロンプトに対しては、正の演示の反射的推移的閉包(reflexive transitive closure)をとると、全ての真の完備化がサイクルを生成するか、負の演示に違反するか、真にあいまいなままであるから、クエリは真である、強制的偽である。 既知の$n$要素の宇宙では、オープンワールドの教え番号をカバー数とブロッカーセットのヒット数として特徴づけ、すべての$n$要素のポーズの最大値が$n(n-1)$であることを証明する。 我々は、プロンプト依存の$s$座標デコーダを定式化し、古典的な座標順序同値を用いて、正確な表現境界を得る: 次元は最大$s$で十分であり、幅は最大$s$で十分である。

関連論文リスト

• Strategic PAC Learnability via Geometric Definability [69.34283267701421]
  戦略分類は、個人が分類者の判断に影響を与えるために、コストで特徴を修正できる学習環境を研究する。 中心的な問題は、帰納的(戦略的な)仮説クラスのサンプルの複雑さが、基礎となる仮説クラスの複雑さと、実現可能な操作を管理するコスト構造にどのように依存するかである。 仮説クラスとコスト誘起近傍関係は、$mathbbR_mathtexp$上の一階式で定義することができる。 難易度は, 複雑度によって制御され, 学習性は維持されていることを証明した。
  論文  参考訳（メタデータ） (2026-05-13T12:21:56Z)
• Online Set Learning from Precision and Recall Feedback [60.00180898830079]
  オンライン設定でドメインの未知のサブセットである$N_texttarget$を学習する問題を考察する。 この単純なオンラインセット学習問題は、精度とリコール型のフィードバックで様々な学習シナリオを抽象化する。 この設定で仮説クラスが学習可能であることを示し、それが有限のヴァプニク・チェルヴォネンキス次元を持つ場合に限る。
  論文  参考訳（メタデータ） (2026-05-10T14:28:05Z)
• Diverse Dictionary Learning [47.381311762862985]
  観測データ$X = g(Z)$のみを与えられた場合、潜伏変数$Z$と生成プロセス$g$は未知であり、追加の仮定なしで$Z$を回収することは誤りである。 我々は、任意の観測に関連付けられた潜伏変数の交叉、補間、対称的な相違と、観測される潜伏変数の依存関係構造が、いまだ適切な不確定性まで同定可能であることを示す。
  論文  参考訳（メタデータ） (2026-04-19T18:18:34Z)
• Characterizing Online and Private Learnability under Distributional Constraints via Generalized Smoothness [63.833913892018536]
  本研究では、固定されたファミリー$U$からデータ生成分布を適応的に選択できる分布敵の下でのシーケンシャルな意思決定について検討する。 一般化滑らか性(Generalized smoothness)という概念の観点で学習可能性を認めるファミリー$U$のほぼ完全な特徴付けを提供する。 一般化された滑らかさは,分布制約下での個人学習性も特徴付けることを示す。
  論文  参考訳（メタデータ） (2026-02-24T06:15:59Z)
• Out-of-Context Reasoning in Large Language Models [21.57320110518431]
  本稿では,大規模言語モデル (LLM) が,単純な二項関係を通して記憶された知識についてどのように考えるかを検討する。 文脈内推論とは異なり、公理は訓練中にのみ見られ、タスクプロンプトには提供されない。 本稿では,新しいトークン埋め込みのみを公理上に学習し,未知のタスクで評価する,軽量な文脈表現学習手法を提案する。
  論文  参考訳（メタデータ） (2025-03-13T14:32:30Z)
• Complexity-Theoretic Implications of Multicalibration [8.315801422499863]
  多精度予測器はより強い条件を満たす:それらはコレクションの各セットで校正される。 この複雑性理論的正則性レンマは、異なる領域に影響を及ぼすことが知られている。 すべての函数(その硬さによらず)が不随伴なハードコア集合の小さな集合を持つことが示される。
  論文  参考訳（メタデータ） (2023-12-28T18:53:21Z)
• Superposition with Lambdas [59.87497175616048]
  匿名関数を含むがブール関数を除いた拡張多型高階論理のクラスフラグメントに対する重ね合わせ計算を設計する。 推論ルールは$betaeta$-equivalence class of $lambda$-termsで動作し、難解な完全性を達成するために高階統一に依存する。
  論文  参考訳（メタデータ） (2021-01-31T13:53:17Z)
• Superposition for Lambda-Free Higher-Order Logic [62.997667081978825]
  本稿では,意図的および拡張的クラス数$lambda$-free高階論理に対して,難解な完全重ね合わせ計算を導入する。 計算は完全単調でなくてもよい項順でパラメタ化され、$lambda$フリーの高次語彙パスとKnuth-Bendixの順序を使うことができる。
  論文  参考訳（メタデータ） (2020-05-05T12:10:21Z)

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

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