論文の概要: Analyzing Robustness of Angluin's L* Algorithm in Presence of Noise

• arxiv url: http://arxiv.org/abs/2209.10315v1
• Date: Wed, 21 Sep 2022 12:44:45 GMT
• ステータス: 処理完了
• システム内更新日: 2022-09-22 16:52:06.289072
• Title: Analyzing Robustness of Angluin's L* Algorithm in Presence of Noise
• Title（参考訳）: 雑音下におけるアングルインL*アルゴリズムのロバスト性の解析
• Authors: Igor Khmelnitsky (Universit\'e Paris-Saclay, CNRS, ENS Paris-Saclay, INRIA, LMF, France), Serge Haddad (Universit\'e Paris-Saclay, CNRS, ENS Paris-Saclay, INRIA, LMF, France), Lina Ye (Universit\'e Paris-Saclay, CNRS, ENS Paris-Saclay, CentraleSup\'elec, LMF, France), Beno\^it Barbot (Universit\'e Paris-Est Cr\'eteil, France), Benedikt Bollig (Universit\'e Paris-Saclay, CNRS, ENS Paris-Saclay, LMF, France), Martin Leucker (Institute for Software Engineering and Programming Languages, Universit\"at zu L\"ubeck, Germany), Daniel Neider (Carl von Ossietzky University of Oldenburg, Germany), Rajarshi Roy (Max Planck Institute for Software Systems, Germany)
• Abstract要約: アングルインのL*アルゴリズムは、正規言語の最小(完全)決定論的有限オートマトン(DFA)をメンバシップと等価クエリを用いて学習する。 ここでは、ノイズを導入してDFAから得られるデバイスに対して、AngluinのPAC学習アルゴリズムがどのように振る舞うかに興味がある。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Angluin's L* algorithm learns the minimal (complete) deterministic finite automaton (DFA) of a regular language using membership and equivalence queries. Its probabilistic approximatively correct (PAC) version substitutes an equivalence query by a large enough set of random membership queries to get a high level confidence to the answer. Thus it can be applied to any kind of (also non-regular) device and may be viewed as an algorithm for synthesizing an automaton abstracting the behavior of the device based on observations. Here we are interested on how Angluin's PAC learning algorithm behaves for devices which are obtained from a DFA by introducing some noise. More precisely we study whether Angluin's algorithm reduces the noise and produces a DFA closer to the original one than the noisy device. We propose several ways to introduce the noise: (1) the noisy device inverts the classification of words w.r.t. the DFA with a small probability, (2) the noisy device modifies with a small probability the letters of the word before asking its classification w.r.t. the DFA, and (3) the noisy device combines the classification of a word w.r.t. the DFA and its classification w.r.t. a counter automaton. Our experiments were performed on several hundred DFAs. Our main contributions, bluntly stated, consist in showing that: (1) Angluin's algorithm behaves well whenever the noisy device is produced by a random process, (2) but poorly with a structured noise, and, that (3) almost surely randomness yields systems with non-recursively enumerable languages.
• Abstract（参考訳）: アングルインのL*アルゴリズムは、正規言語の最小(完全)決定論的有限オートマトン(DFA)をメンバシップと等価クエリを用いて学習する。 その確率的近似的正解(PAC)バージョンは、その答えに高い信頼を得るのに十分な数のランダムなメンバシップクエリによって等価クエリを代用する。 したがって、任意の種類の(あるいは非正規な)デバイスに適用することができ、観察に基づいてデバイスの動作を抽象化するオートマトンを合成するアルゴリズムと見なすことができる。 ここでは、ノイズを導入してDFAから得られるデバイスに対して、AngluinのPAC学習アルゴリズムがどのように振る舞うかに興味がある。 より正確には、Angluinのアルゴリズムがノイズを低減し、ノイズの多いデバイスよりも元のものに近いDFAを生成するかどうかを研究する。 本稿では,(1)DFA の単語 w.r.t の分類を小さな確率で反転させるノイズ装置,(2) DFA の分類を問う前に単語の文字を小さい確率で修正するノイズ装置,(3) DFA の単語 w.r.t の分類と、その分類をカウンターオートマトンとするノイズ装置を提案する。 数百のDFAで実験を行った。 angluinのアルゴリズムは、無作為なプロセスによってノイズのあるデバイスが生成されるたびにうまく振る舞うが、構造化されたノイズでは不十分であり、(3)ほぼ確実にランダム性は、非帰納的可算言語を持つシステムをもたらす。

関連論文リスト

• Pivotal Auto-Encoder via Self-Normalizing ReLU [20.76999663290342]
  トランスフォーメーション学習問題として,単一の隠蔽層スパースオートエンコーダを定式化する。 本稿では,テスト時の騒音レベルに不変な予測モデルを実現する最適化問題を提案する。 実験結果から, 各種ノイズに対する安定性が向上することが示唆された。
  論文  参考訳（メタデータ） (2024-06-23T09:06:52Z)
• Multiclass Learning from Noisy Labels for Non-decomposable Performance Measures [15.358504449550013]
  非分解性性能尺度の2つのクラスに対して雑音ラベルから学習するアルゴリズムを設計する。 どちらの場合も、広範に研究されているクラス条件雑音モデルの下で、アルゴリズムのノイズ補正バージョンを開発する。 実験では,ラベルノイズ処理におけるアルゴリズムの有効性を実証した。
  論文  参考訳（メタデータ） (2024-02-01T23:03:53Z)
• Variational quantum algorithms on cat qubits [0.0]
  現在のハードウェアは、制御不能なノイズに悩まされ、1つの計算の期待結果を変更できる。 我々は、本質的にビットフリップに耐性を持つ技術である猫クビットについて検討する。 VQAで定式化できる2種類の問題をシミュレーションする。
  論文  参考訳（メタデータ） (2023-05-23T15:09:00Z)
• Larger Offspring Populations Help the $(1 + (\lambda, \lambda))$ Genetic Algorithm to Overcome the Noise [76.24156145566425]
  進化的アルゴリズムは、適合性の評価においてノイズに対して堅牢であることが知られている。 我々は$(lambda,lambda)$の遺伝的アルゴリズムがどんなにノイズに強いかを解析する。
  論文  参考訳（メタデータ） (2023-05-08T08:49:01Z)
• Unified Functional Hashing in Automatic Machine Learning [58.77232199682271]
  高速に統一された関数型ハッシュを用いることで,大きな効率向上が得られることを示す。 私たちのハッシュは"機能的"であり、表現やコードが異なる場合でも同等の候補を識別します。 ニューラルアーキテクチャ検索やアルゴリズム発見など、複数のAutoMLドメインで劇的な改善がなされている。
  論文  参考訳（メタデータ） (2023-02-10T18:50:37Z)
• Open-Set Automatic Target Recognition [52.27048031302509]
  オートマチックターゲット認識(Automatic Target Recognition、ATR)は、異なるセンサーから取得したデータに基づいてターゲットを認識しようとするコンピュータビジョンアルゴリズムのカテゴリである。 既存のATRアルゴリズムは、トレーニングとテストが同じクラス分布を持つ従来のクローズドセット手法向けに開発されている。 ATRアルゴリズムのオープンセット認識機能を実現するためのオープンセット自動ターゲット認識フレームワークを提案する。
  論文  参考訳（メタデータ） (2022-11-10T21:28:24Z)
• Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
  オンラインアルゴリズム選択(OAS)では、アルゴリズム問題クラスのインスタンスがエージェントに次々に提示され、エージェントは、固定された候補アルゴリズムセットから、おそらく最高のアルゴリズムを迅速に選択する必要がある。 SAT(Satisfiability)のような決定問題に対して、品質は一般的にアルゴリズムのランタイムを指す。 本研究では,OASのマルチアームバンディットアルゴリズムを再検討し,この問題に対処する能力について議論する。 ランタイム指向の損失に適応し、時間的地平線に依存しない空間的・時間的複雑さを維持しながら、部分的に検閲されたデータを可能にする。
  論文  参考訳（メタデータ） (2021-09-13T18:10:52Z)
• Improved, Deterministic Smoothing for L1 Certified Robustness [119.86676998327864]
  分割雑音を伴う非加法的決定論的平滑化法(dssn)を提案する。 一様加法平滑化とは対照的に、ssn認証は無作為なノイズコンポーネントを独立に必要としない。 これは、規範ベースの敵対的脅威モデルに対して決定論的「ランダム化平滑化」を提供する最初の仕事である。
  論文  参考訳（メタデータ） (2021-03-17T21:49:53Z)
• Learning based signal detection for MIMO systems with unknown noise statistics [84.02122699723536]
  本論文では,未知のノイズ統計による信号を堅牢に検出する一般化最大確率(ML)推定器を考案する。 実際には、システムノイズに関する統計的な知識はほとんどなく、場合によっては非ガウス的であり、衝動的であり、分析不可能である。 我々のフレームワークは、ノイズサンプルのみを必要とする教師なしの学習アプローチによって駆動される。
  論文  参考訳（メタデータ） (2021-01-21T04:48:15Z)
• Multi-class Gaussian Process Classification with Noisy Inputs [2.362412515574206]
  いくつかの状況では、騒音の量は事前に知ることができる。 提案手法を,合成データと実データを含むいくつかの実験により評価した。
  論文  参考訳（メタデータ） (2020-01-28T18:55:13Z)

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

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