論文の概要: Learning Algorithms in the Limit

• arxiv url: http://arxiv.org/abs/2506.15543v1
• Date: Wed, 18 Jun 2025 15:17:03 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-19 19:35:51.708814
• Title: Learning Algorithms in the Limit
• Title（参考訳）: 限界における学習アルゴリズム
• Authors: Hristo Papazov, Nicolas Flammarion,
• Abstract要約: 我々はGoldの帰納的推論フレームワークを拡張して、テキスト計算観測とテキスト制約入力源を組み込む。 政策軌道から計算可能な関数を学習することで、入力と出力から学習関数を減らし、有限状態トランスデューサ推論への興味深い接続を明らかにする。
• 参考スコア（独自算出の注目度）: 17.646488317989284
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper studies the problem of learning computable functions in the limit by extending Gold's inductive inference framework to incorporate \textit{computational observations} and \textit{restricted input sources}. Complimentary to the traditional Input-Output Observations, we introduce Time-Bound Observations, and Policy-Trajectory Observations to study the learnability of general recursive functions under more realistic constraints. While input-output observations do not suffice for learning the class of general recursive functions in the limit, we overcome this learning barrier by imposing computational complexity constraints or supplementing with approximate time-bound observations. Further, we build a formal framework around observations of \textit{computational agents} and show that learning computable functions from policy trajectories reduces to learning rational functions from input and output, thereby revealing interesting connections to finite-state transducer inference. On the negative side, we show that computable or polynomial-mass characteristic sets cannot exist for the class of linear-time computable functions even for policy-trajectory observations.
• Abstract（参考訳）: 本稿では,ゴールドの帰納的推論フレームワークを拡張して,計算可能関数を極限で学習する問題について検討する。 従来のインプット・アウトプット・オブザーバの補完として,より現実的な制約下での一般再帰関数の学習可能性を研究するために,タイムバウンド・オブザーバと政策トラジェクトリ・オブザーバを紹介する。 インプット・アウトプット・オブザーバは、その極限における一般再帰関数のクラスを学ぶのに十分ではないが、計算複雑性の制約を課したり、時間的近似的な観測を補うことで、この学習障壁を克服する。 さらに,<textit{computational agent} の観測に関する公式な枠組みを構築し,政策軌跡からの計算可能な関数の学習が,入力と出力から有理関数の学習に還元されることを示し,有限状態トランスデューサ推論への興味深い接続を明らかにする。 負の面から、線形時間計算可能関数のクラスに対して計算可能あるいは多項式質量特性集合は、政策軌道観測においても存在できないことを示す。

関連論文リスト

• Outcome-Based Online Reinforcement Learning: Algorithms and Fundamental Limits [58.63897489864948]
  結果に基づくフィードバックによる強化学習は、根本的な課題に直面します。 適切なアクションにクレジットを割り当てるには? 本稿では,一般関数近似を用いたオンラインRLにおけるこの問題の包括的解析を行う。
  論文  参考訳（メタデータ） (2025-05-26T17:44:08Z)
• Multitask Kernel-based Learning with Logic Constraints [13.70920563542248]
  本稿では,タスク関数の集合間の論理制約をカーネルマシンに組み込む枠組みを提案する。 特徴空間上の複数の一意述語をカーネルマシンで学習するマルチタスク学習方式を検討する。 一般的なアプローチでは、論理節を連続的な実装に変換し、カーネルベースの述語によって計算された出力を処理する。
  論文  参考訳（メタデータ） (2024-02-16T12:11:34Z)
• Learning in POMDPs is Sample-Efficient with Hindsight Observability [36.66596305441365]
  POMDPは、幅広い意思決定問題を捉えているが、難易度の結果は、学習が本質的に部分観測可能であるため、単純な設定でも難易度が高いことを示唆している。 多くの現実的な問題では、より多くの情報が明らかにされるか、学習プロセスのどこかの時点で計算できる。 我々は、学習者が学習中にのみ潜伏状態を明らかにするPOMDPとして設定(setshort)を定式化する。
  論文  参考訳（メタデータ） (2023-01-31T18:54:36Z)
• On Leave-One-Out Conditional Mutual Information For Generalization [122.2734338600665]
  残余条件付き相互情報(loo-CMI)の新しい尺度に基づく教師付き学習アルゴリズムのための情報理論の一般化境界を導出する。 他のCMI境界とは対照的に、我々のloo-CMI境界は容易に計算でき、古典的なout-out-out-cross-validationのような他の概念と関連して解釈できる。 ディープラーニングのシナリオにおいて予測された一般化ギャップを評価することにより,境界の質を実証的に検証する。
  論文  参考訳（メタデータ） (2022-07-01T17:58:29Z)
• Provably Efficient Reinforcement Learning in Partially Observable Dynamical Systems [97.12538243736705]
  関数近似を用いた部分観測可能力学系の強化学習について検討する。 本稿では,POMDP,LQG,予測状態表現 (Predictive State Representations,PSR) などのモデルや,POMDPのHilbert Space Embeddingsや観測可能なPOMDPを遅延低ランク遷移で組み込むことのできる,汎用的な新しいテクスタイト(Partially Observar Bilinear Actor-Critic)フレームワークを提案する。
  論文  参考訳（メタデータ） (2022-06-24T00:27:42Z)
• Reinforcement Learning from Partial Observation: Linear Function Approximation with Provable Sample Efficiency [111.83670279016599]
  部分観察決定過程(POMDP)の無限観測および状態空間を用いた強化学習について検討した。 線形構造をもつPOMDPのクラスに対する部分可観測性と関数近似の最初の試みを行う。
  論文  参考訳（メタデータ） (2022-04-20T21:15:38Z)
• Non-Linear Reinforcement Learning in Large Action Spaces: Structural Conditions and Sample-efficiency of Posterior Sampling [28.371541697552928]
  一般作用空間を線形埋め込み性条件下で保持する非線形関数近似の最初の結果を示す。 最悪の場合,RL問題のランクパラメータでスケールが保証される。
  論文  参考訳（メタデータ） (2022-03-15T20:50:26Z)
• An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
  データから制約をマイニングするための一般的なフレームワークを提案する。 特に、構造化された出力予測の推論を整数線形プログラミング(ILP)問題とみなす。 提案手法は,9×9のスドクパズルの解法を学習し,基礎となるルールを提供することなく,例からツリー問題を最小限に分散させることが可能であることを示す。
  論文  参考訳（メタデータ） (2020-06-18T20:09:53Z)
• Options of Interest: Temporal Abstraction with Interest Functions [58.30081828754683]
  一般関数近似に適した開始集合の一般化を、オプションに関連付けられた興味関数を定義することによって提供する。 我々は、関心関数に対する勾配に基づく学習アルゴリズムを導出し、新たな関心選択批判的アーキテクチャを創出する。
  論文  参考訳（メタデータ） (2020-01-01T21:24:39Z)

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

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