論文の概要: On the Statistical Query Complexity of Learning Semiautomata: a Random Walk Approach

• arxiv url: http://arxiv.org/abs/2510.04115v1
• Date: Sun, 05 Oct 2025 09:35:35 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-07 16:52:59.46405
• Title: On the Statistical Query Complexity of Learning Semiautomata: a Random Walk Approach
• Title（参考訳）: セミオートマタ学習における統計的クエリ複雑性について:ランダムウォークアプローチ
• Authors: George Giapitzakis, Kimon Fountoulakis, Eshaan Nichani, Jason D. Lee,
• Abstract要約: 我々は,アルファベットサイズと入力長の両方が状態数である場合に,統計的クエリの硬さを確立することができることを示す。 この結果は、半オートマタの内部状態遷移構造からのみ導かれる。
• 参考スコア（独自算出の注目度）: 59.589793281734636
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Semiautomata form a rich class of sequence-processing algorithms with applications in natural language processing, robotics, computational biology, and data mining. We establish the first Statistical Query hardness result for semiautomata under the uniform distribution over input words and initial states. We show that Statistical Query hardness can be established when both the alphabet size and input length are polynomial in the number of states. Unlike the case of deterministic finite automata, where hardness typically arises through the hardness of the language they recognize (e.g., parity), our result is derived solely from the internal state-transition structure of semiautomata. Our analysis reduces the task of distinguishing the final states of two semiautomata to studying the behavior of a random walk on the group $S_{N} \times S_{N}$. By applying tools from Fourier analysis and the representation theory of the symmetric group, we obtain tight spectral gap bounds, demonstrating that after a polynomial number of steps in the number of states, distinct semiautomata become nearly uncorrelated, yielding the desired hardness result.
• Abstract（参考訳）: セミオートマタは、自然言語処理、ロボット工学、計算生物学、データマイニングに応用された、シーケンス処理アルゴリズムの豊富なクラスを形成する。 我々は,入力語と初期状態の均一分布の下で,半オートマタに対する最初の統計的問合せ硬度結果を確立する。 我々は,アルファベットサイズと入力長の両方が状態数における多項式である場合に,統計的クエリの硬さを確立することができることを示す。 決定論的有限オートマトンの場合とは異なり、ハードネスは通常、認識する言語の硬さ(例えばパリティ)によって生じるが、その結果は半オートマトンの内部状態遷移構造からのみ導かれる。 本分析により,群$S_{N} \times S_{N}$におけるランダムウォークの挙動を研究するために,2つの半オートマタの最終状態を識別する作業が削減される。 フーリエ解析と対称群の表現理論のツールを適用して、厳密なスペクトルギャップ境界を求め、状態数における多項式のステップ数の後、区別された半オートマタはほぼ無相関となり、所望の硬度結果が得られることを示した。

関連論文リスト

• Bisimulation Learning [55.859538562698496]
  我々は、大きな、潜在的に無限の状態空間を持つ状態遷移系の有限バイシミュレートを計算する。 提案手法は,実際に行われている他の最先端ツールよりも高速な検証結果が得られる。
  論文  参考訳（メタデータ） (2024-05-24T17:11:27Z)
• An Analysis of On-the-fly Determinization of Finite-state Automata [65.268245109828]
  有限状態オートマトンをオンザフライで決定する手法の抽象化を確立し, オートマトンにどのように適用できるかを実証する。 我々の発見の特別な例は、多くの非決定論的遷移を持つオートマトンが、ほとんど常に複雑性の決定性を持っていることである。
  論文  参考訳（メタデータ） (2023-08-27T11:51:27Z)
• Automata Cascades: Expressivity and Sample Complexity [90.53326983143644]
  カスケードは、それらのコンポーネントの観点から、オートマトンにおけるサンプルの複雑さを記述することができることを示す。 以上の結果から、無限入力アルファベットと、利用可能なデータ量で指数関数的な多数の状態を持つオートマトンを原理的に学習できることが示唆された。
  論文  参考訳（メタデータ） (2022-11-25T11:02:33Z)
• Computing the quantum guesswork: a quadratic assignment problem [6.445605125467573]
  従来の計算手法は、半定値の標準的なプログラミング技術に基づいていた。 確率分布が均一な量子ビットアンサンブルの量子推定処理を計算すれば、よりクワッドラティックなスピードアップがもたらされることを示す。 例として、正則および準正則なクォービット状態集合の推理を計算する。
  論文  参考訳（メタデータ） (2021-12-03T01:24:57Z)
• Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers [50.85524803885483]
  本研究は,統計的学習性を示すために近似ネットワークを必要とする統計有意(SM)近似の形式的定義を提案する。 回路とチューリングマシンの2つの機能クラスに対するSM近似について検討する。
  論文  参考訳（メタデータ） (2021-07-28T04:28:55Z)

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

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