論文の概要: Automata Cascades: Expressivity and Sample Complexity

• arxiv url: http://arxiv.org/abs/2211.14028v1
• Date: Fri, 25 Nov 2022 11:02:33 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-28 15:42:35.672246
• Title: Automata Cascades: Expressivity and Sample Complexity
• Title（参考訳）: Automata Cascades: 表現性とサンプル複雑度
• Authors: Alessandro Ronca, Nadezda A. Knorozova, Giuseppe De Giacomo
• Abstract要約: カスケードは、それらのコンポーネントの観点から、オートマトンにおけるサンプルの複雑さを記述することができることを示す。 以上の結果から、無限入力アルファベットと、利用可能なデータ量で指数関数的な多数の状態を持つオートマトンを原理的に学習できることが示唆された。
• 参考スコア（独自算出の注目度）: 90.53326983143644
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Every automaton can be decomposed into a cascade of basic automata. This is the Prime Decomposition Theorem by Krohn and Rhodes. We show that cascades allow for describing the sample complexity of automata in terms of their components. In particular, we show that the sample complexity is linear in the number of components and the maximum complexity of a single component. This opens to the possibility for learning automata representing large dynamic systems consisting of many parts interacting with each other. It is in sharp contrast with the established understanding of the sample complexity of automata, described in terms of the overall number of states and input letters, which in turn implies that it is only possible to learn automata where the number of states and letters is linear in the amount of data available. Instead our results show that one can in principle learn automata with infinite input alphabets and a number of states that is exponential in the amount of data available.
• Abstract（参考訳）: すべてのオートマトンは、基本的なオートマトンのカスケードに分解できる。 これはKrohnとRhodesによるPrime Decomposition Theoremである。 カスケードによって、automattaのサンプル複雑性をコンポーネントの観点から記述できることを示した。 特に,試料の複雑さは,成分数と単一成分の最大複雑性において線形であることを示す。 これは、互いに相互作用する多くの部分からなる大きな動的システムを表現するオートマトンを学習する可能性を開く。 これは、状態と入力文字の総数の観点から記述された、オートマタのサンプル複雑性の確立された理解とは対照的であり、結果として、利用可能なデータ量において状態と文字の数が線形であるようなオートマタを学習することしかできないことを意味する。 その代わり、我々の結果は、無限の入力アルファベットと利用可能なデータ量で指数関数的な多くの状態を持つオートマトンを原則として学習できることを示します。

関連論文リスト

• Counting Reward Automata: Sample Efficient Reinforcement Learning Through the Exploitation of Reward Function Structure [13.231546105751015]
  本稿では,形式言語として表現可能な任意の報酬関数をモデル化可能な有限状態機械変種であるカウント・リワード・オートマトンを提案する。 このような抽象機械を組み込んだエージェントが,現在の手法よりも大きなタスクの集合を解くことができることを実証する。
  論文  参考訳（メタデータ） (2023-12-18T17:20:38Z)
• ASAP: Automated Sequence Planning for Complex Robotic Assembly with Physical Feasibility [27.424678100675163]
  本稿では,一般型アセンブリのシーケンスを自動生成する物理ベースの計画手法であるASAPを提案する。 サーチは、シミュレーションラベルでデータに基づいてトレーニングされた幾何学的またはグラフニューラルネットワークによってガイドすることができる。 数百の複雑な製品集合体からなる大規模データセット上で, 物理的に現実的な組み立て計画を生成する上で, ASAPの優れた性能を示す。
  論文  参考訳（メタデータ） (2023-09-29T00:27:40Z)
• Large Language Models as General Pattern Machines [64.75501424160748]
  我々は,事前訓練された大規模言語モデル (LLM) が,複雑なトークンシーケンスを自動回帰的に完了することを示す。 驚いたことに、語彙からランダムにサンプリングされたトークンを用いてシーケンスが表現された場合でも、パターン完了の習熟度を部分的に保持することができる。 本研究では,ロボット工学における問題に対して,これらのゼロショット機能がどのように適用されるかを検討する。
  論文  参考訳（メタデータ） (2023-07-10T17:32:13Z)
• Transformers Learn Shortcuts to Automata [52.015990420075944]
  低深度変換器は任意の有限状態オートマトンを計算できる。 我々は,$O(log T)$レイヤを持つ変換器が,長さ$T$の入力シーケンス上で,オートマトンを正確に再現可能であることを示す。 さらに、これらの解の脆性について検討し、潜在的な緩和を提案する。
  論文  参考訳（メタデータ） (2022-10-19T17:45:48Z)
• Benchmarking Multimodal AutoML for Tabular Data with Text Fields [83.43249184357053]
  テキストフィールドを含む18個のマルチモーダルデータテーブルを組み立てる。 このベンチマークにより、研究者は、数値的、分類的、テキスト的特徴を用いて教師あり学習を行うための独自の方法を評価することができる。
  論文  参考訳（メタデータ） (2021-11-04T09:29:16Z)
• Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers [50.85524803885483]
  本研究は,統計的学習性を示すために近似ネットワークを必要とする統計有意(SM)近似の形式的定義を提案する。 回路とチューリングマシンの2つの機能クラスに対するSM近似について検討する。
  論文  参考訳（メタデータ） (2021-07-28T04:28:55Z)
• On (co-lex) Ordering Automata [2.800608984818919]
  言語Lを受け入れる正準、最小幅、部分的に順序付けられたオートマトンを提示できることを示す。 Hを用いて、言語を認識する最小限のオートマトンから、言語幅を効果的に計算できることを証明する。
  論文  参考訳（メタデータ） (2021-06-04T07:41:58Z)
• Visualizing computation in large-scale cellular automata [24.62657948019533]
  セルオートマトンのような複雑なシステムの創発的プロセスは、複雑さが増大する計算を実行することができる。 セル状態,クラスタリング,オートエンコーダの周波数解析に基づく粗粒度セルオートマトンの方法を提案する。
  論文  参考訳（メタデータ） (2021-04-01T08:14:15Z)
• A Passive Online Technique for Learning Hybrid Automata from Input/Output Traces [0.0]
  非線形サイバー物理システムの入力出力トレースからハイブリッドオートマトンを合成する新しい手法を提案する。 非線形挙動における類似度検出は、そのようなモデルの抽出の主な課題である。 当社のアプローチは受動的であり、ログされたトレースから自動合成を行う際にシステムとのインタラクションは不要である。
  論文  参考訳（メタデータ） (2021-01-18T13:08:14Z)
• Induction and Exploitation of Subgoal Automata for Reinforcement Learning [75.55324974788475]
  本稿では,Regressed Learning (RL)タスクにおけるサブゴールの学習と活用のためのISAを提案する。 ISAは、タスクのサブゴールによってエッジがラベル付けされたオートマトンであるサブゴールオートマトンを誘導することで強化学習をインターリーブする。 サブゴールオートマトンはまた、タスクの完了を示す状態と、タスクが成功せずに完了したことを示す状態の2つの特別な状態で構成されている。
  論文  参考訳（メタデータ） (2020-09-08T16:42:55Z)

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

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