論文の概要: (PAC-)Learning state machines from data streams: A generic strategy and an improved heuristic (Extended version)

• arxiv url: http://arxiv.org/abs/2604.02244v1
• Date: Thu, 02 Apr 2026 16:35:07 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-03 14:21:10.921099
• Title: (PAC-)Learning state machines from data streams: A generic strategy and an improved heuristic (Extended version)
• Title（参考訳）: (PAC-)データストリームから状態マシンを学習する:汎用戦略と改良されたヒューリスティック(拡張版)
• Authors: Robert Baumgartner, Sicco Verwer,
• Abstract要約: これは、データストリームからの学習状態マシンの拡張版です。 PACバウンドに関する公式な証明によって拡張され、同様のアプローチの議論と分析が付録から全節に移動された。
• 参考スコア（独自算出の注目度）: 4.569217855609235
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This is an extended version of our publication Learning state machines from data streams: A generic strategy and an improved heuristic, International Conference on Grammatical Inference (ICGI) 2023, Rabat, Morocco. It has been extended with a formal proof on PAC-bounds, and the discussion and analysis of a similar approach has been moved from the appendix and is now a full Section. State machines models are models that simulate the behavior of discrete event systems, capable of representing systems such as software systems, network interactions, and control systems, and have been researched extensively. The nature of most learning algorithms however is the assumption that all data be available at the beginning of the algorithm, and little research has been done in learning state machines from streaming data. In this paper, we want to close this gap further by presenting a generic method for learning state machines from data streams, as well as a merge heuristic that uses sketches to account for incomplete prefix trees. We implement our approach in an open-source state merging library and compare it with existing methods. We show the effectiveness of our approach with respect to run-time, memory consumption, and quality of results on a well known open dataset. Additionally, we provide a formal analysis of our algorithm, showing that it is capable of learning within the PAC framework, and show a theoretical improvement to increase run-time, without sacrificing correctness of the algorithm in larger sample sizes.
• Abstract（参考訳）: 汎用戦略と改良されたヒューリスティック、国際文法推論会議(ICGI)2023, Rabat, Morocco。 PACバウンドに関する公式な証明によって拡張され、同様のアプローチに関する議論と分析が付録から移動され、現在は完全なセクションになっている。 状態マシンモデルは、離散イベントシステムの振る舞いをシミュレートするモデルであり、ソフトウェアシステム、ネットワークインタラクション、制御システムなどのシステムを表現することができ、広範囲に研究されている。 しかし、ほとんどの学習アルゴリズムの性質は、全てのデータがアルゴリズムの開始時に利用できるという仮定であり、ストリーミングデータから状態マシンを学ぶ際にはほとんど研究が行われていない。 本稿では、データストリームから状態マシンを学習する汎用的な方法と、スケッチを用いて不完全な接頭辞木を記述したマージヒューリスティックを提示することにより、このギャップをさらに埋めたい。 我々は、オープンソースステートマージライブラリにアプローチを実装し、既存のメソッドと比較する。 我々は、よく知られたオープンデータセット上で、実行時間、メモリ消費、結果の品質に関して、我々のアプローチの有効性を示す。 さらに,本アルゴリズムはPACフレームワーク内で学習可能であり,より大規模なサンプルサイズでアルゴリズムの正しさを犠牲にすることなく,実行時間を改善する理論的改善を示す。

関連論文リスト

• Efficient Machine Unlearning via Influence Approximation [75.31015485113993]
  インフルエンサーベースのアンラーニングは、個別のトレーニングサンプルがモデルパラメータに与える影響を再トレーニングせずに推定する顕著なアプローチとして現れてきた。 本稿では,暗記(増分学習)と忘れ(未学習)の理論的関連性を確立する。 本稿では、インフルエンス近似アンラーニングアルゴリズムを導入し、インクリメンタルな視点から効率的なマシンアンラーニングを行う。
  論文  参考訳（メタデータ） (2025-07-31T05:34:27Z)
• Continual Learning with Deep Streaming Regularized Discriminant Analysis [0.0]
  本稿では,この課題に対する解決法として,正規化判別分析のストリーミング版を提案する。 アルゴリズムを畳み込みニューラルネットワークと組み合わせて、バッチ学習と既存のストリーミング学習アルゴリズムよりも優れていることを実証します。
  論文  参考訳（メタデータ） (2023-09-15T12:25:42Z)
• Explainable Lifelong Stream Learning Based on "Glocal" Pairwise Fusion [17.11983414681928]
  リアルタイムデバイス上での連続学習アプリケーションは、携帯電話、消費者向けロボット、スマートアプライアンスで使用されている。 本研究では,いくつかの重要な特徴を取り入れたExplainable Lifelong Learning(ExLL)モデルを提案する。 ExLLはテストシナリオの大部分において、正確性のためにすべてのアルゴリズムを上回ります。
  論文  参考訳（メタデータ） (2023-06-23T09:54:48Z)
• Provably Efficient Representation Learning with Tractable Planning in Low-Rank POMDP [81.00800920928621]
  部分的に観測可能なマルコフ決定過程(POMDP)における表現学習の研究 まず,不確実性(OFU)に直面した最大推定(MLE)と楽観性を組み合わせた復調性POMDPのアルゴリズムを提案する。 次に、このアルゴリズムをより広範な$gamma$-observable POMDPのクラスで機能させる方法を示す。
  論文  参考訳（メタデータ） (2023-06-21T16:04:03Z)
• Learning state machines via efficient hashing of future traces [10.57164270098353]
  ステートマシンは、ソフトウェアシステムのような離散的なシステムをモデル化し、視覚化し、正規文法を表現するために一般的なモデルである。 データから状態マシンを受動的に学習するほとんどのアルゴリズムは、すべてのデータが最初から利用可能であると仮定し、そのデータをメモリにロードする。 本研究では,メモリ要求量を削減するため,データストリームから状態マシンを学習する手法を提案する。
  論文  参考訳（メタデータ） (2022-07-04T15:24:21Z)
• Value-Consistent Representation Learning for Data-Efficient Reinforcement Learning [105.70602423944148]
  本稿では,意思決定に直接関連のある表現を学習するための,VCR(Value-Consistent Expression Learning)という新しい手法を提案する。 この想像された状態と環境によって返される実状態とを一致させる代わりに、VCRは両方の状態に$Q$-valueヘッドを適用し、2つのアクション値の分布を得る。 検索不要なRLアルゴリズムに対して,提案手法が新たな最先端性能を実現することが実証された。
  論文  参考訳（メタデータ） (2022-06-25T03:02:25Z)
• SOLIS -- The MLOps journey from data acquisition to actionable insights [62.997667081978825]
  本稿では,基本的なクロスプラットフォームテンソルフレームワークとスクリプト言語エンジンを使用しながら,すべての要件をサポートする統合デプロイメントパイプラインとフリー・ツー・オペレートアプローチを提案する。 しかし、このアプローチは、実際のプロダクショングレードシステムに機械学習機能を実際にデプロイするために必要な手順やパイプラインを提供していない。
  論文  参考訳（メタデータ） (2021-12-22T14:45:37Z)
• GRAD-MATCH: A Gradient Matching Based Data Subset Selection for Efficient Learning [23.75284126177203]
  我々は、トレーニングや検証セットの勾配と密接に一致する部分集合を見つける汎用フレームワークgrad-matchを提案する。 GRAD-MATCHは、最近のデータ選択アルゴリズムよりも大きく、一貫して優れていることを示す。
  論文  参考訳（メタデータ） (2021-02-27T04:09:32Z)
• A Survey on Large-scale Machine Learning [67.6997613600942]
  機械学習はデータに対する深い洞察を与え、マシンが高品質な予測を行うことを可能にする。 ほとんどの高度な機械学習アプローチは、大規模なデータを扱う場合の膨大な時間コストに悩まされる。 大規模機械学習は、ビッグデータからパターンを、同等のパフォーマンスで効率的に学習することを目的としている。
  論文  参考訳（メタデータ） (2020-08-10T06:07:52Z)
• FedPD: A Federated Learning Framework with Optimal Rates and Adaptivity to Non-IID Data [59.50904660420082]
  フェデレートラーニング(FL)は、分散データから学ぶための一般的なパラダイムになっています。 クラウドに移行することなく、さまざまなデバイスのデータを効果的に活用するために、Federated Averaging(FedAvg)などのアルゴリズムでは、"Computation then aggregate"(CTA)モデルを採用している。
  論文  参考訳（メタデータ） (2020-05-22T23:07:42Z)
• Reasoning About Generalization via Conditional Mutual Information [26.011933885798506]
  我々は、Mutual Information (CMI) を用いて、入力がどの程度の精度で認識できるかを定量化する。 CMIのバウンダリは,VC次元,圧縮スキーム,差分プライバシー,その他の手法から得られることを示す。 次に、有界な CMI は様々な種類の一般化を意味することを示す。
  論文  参考訳（メタデータ） (2020-01-24T18:13:04Z)

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

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