論文の概要: Learning Deterministic Finite Automata from Confidence Oracles
- arxiv url: http://arxiv.org/abs/2311.10963v1
- Date: Sat, 18 Nov 2023 04:21:05 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-22 13:06:57.729576
- Title: Learning Deterministic Finite Automata from Confidence Oracles
- Title（参考訳）: 信頼オラクルから決定論的有限オートマトンを学ぶ
- Authors: Wilson Wu
- Abstract要約: 私たちは、あるターゲット言語について不完全な知識を持つオラクル$Q$へのアクセスをアルファベット$Sigma$で与えられます。
オラクルは、文字列 $xinSigma*$ を、文字列が言語内にあるという自信を示す区間 $[-1,1]$ のスコアにマッピングする。
我々のゴールは、自信のある情報を保存する託宣のDFA表現を学習することである。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We discuss the problem of learning a deterministic finite automaton (DFA)
from a confidence oracle. That is, we are given access to an oracle $Q$ with
incomplete knowledge of some target language $L$ over an alphabet $\Sigma$; the
oracle maps a string $x\in\Sigma^*$ to a score in the interval $[-1,1]$
indicating its confidence that the string is in the language. The
interpretation is that the sign of the score signifies whether $x\in L$, while
the magnitude $|Q(x)|$ represents the oracle's confidence. Our goal is to learn
a DFA representation of the oracle that preserves the information that it is
confident in. The learned DFA should closely match the oracle wherever it is
highly confident, but it need not do this when the oracle is less sure of
itself.
- Abstract（参考訳）: 本稿では,決定論的有限オートマトン(DFA)を信頼性オラクルから学習する問題について論じる。
すなわち、あるターゲット言語の不完全な知識を持つオラクル$Q$へのアクセスが与えられ、そのオラクルは文字列$x\in\Sigma^*$を、文字列が言語内にあるという自信を示す間隔$[-1,1]$のスコアにマッピングする。
この解釈では、スコアの符号は$x\in l$ のかどうかを示し、$|q(x)|$ はオラクルの信頼を表す。
私たちの目標は、oracleが自信を持っている情報を保存しているdfa表現を学ぶことです。
学んだdfaは、oracleが自信を持っているところならどこでも密に一致すべきだが、oracleが自身を確信していない場合、そうする必要はない。
関連論文リスト
- Computational Lower Bounds for Regret Minimization in Normal-Form Games [68.66209476382213]
乗算重み更新などの既存の学習アルゴリズムが最適に近いことを示す。
結果はKothari と Mehta が提案したアルゴリズムの枠組みで得られた。
論文 参考訳（メタデータ） (2024-11-04T00:39:52Z) - Simple online learning with consistent oracle [55.43220407902113]
オンライン学習は、学習アルゴリズムが、どの時点でも、今まで見てきたすべての例に一致する関数をクラスから与えることができる、という、一貫性のあるオラクルを通じてのみクラスにアクセスすることができるモデルであると考えている。
論文 参考訳（メタデータ） (2023-08-15T21:50:40Z) - Quantum Algorithms for Identifying Hidden Strings with Applications to
Matroid Problems [8.347058637480506]
我々は、ペアの$s, s'$を特定するために、最大内部積のオラクルに$O(1)$クエリを消費する量子アルゴリズムを提案する。
また、サブセットのオラクルに$fracn2+O(sqrtn)$クエリを消費する量子アルゴリズムを提案し、任意の古典的アルゴリズムが少なくとも$n+Omega(1)$クエリを必要とすることを証明した。
論文 参考訳（メタデータ） (2022-11-19T11:14:19Z) - Oracle-Efficient Online Learning for Beyond Worst-Case Adversaries [29.598518028635716]
オンライン学習の最悪のケース分析を超越した,オラクル効率のアルゴリズムについて検討する。
このスムーズな分析設定のために,本研究は,スムーズな相手を持つオンライン学習のための最初のオラクル効率のアルゴリズムを提供する。
論文 参考訳（メタデータ） (2022-02-17T09:49:40Z) - Learning Graph Partitions [2.3224617218247126]
グラフの連結成分への分割が与えられたとき、会員オラクルはグラフの任意の2つの頂点が同じ成分に含まれるか否かを主張する。
我々は$nge kge 2$の場合、$k$コンポーネントで$n$-vertex隠れグラフのコンポーネントを学ぶには、少なくとも$frac12(n-k)(k-1)$メンバシップクエリが必要であることを証明している。
論文 参考訳（メタデータ） (2021-12-15T05:28:45Z) - The Hardness Analysis of Thompson Sampling for Combinatorial
Semi-bandits with Greedy Oracle [16.50998008977657]
トンプソンサンプリング(TS)は、バンディット地域に多くの関心を集めている。
1930年代に導入されたが、理論上は近年まで証明されていない。
論文 参考訳（メタデータ） (2021-11-08T06:40:03Z) - Simplified Quantum Algorithm for the Oracle Identification Problem [0.0]
oracleは未知の文字列のビットに$x$ of length$n$をアクセスし、既知のセットである$Csubseteq0,1n$に属することを約束する。
目標は、できるだけ少数のオラクルへのクエリを使って$x$を識別することだ。
この問題に対して,クエリ複雑性を$Oleft(sqrtfracnlog M log(n/log M)+1right)$,$M$は$C$である。
論文 参考訳（メタデータ） (2021-09-08T19:48:27Z) - Agnostic learning with unknown utilities [70.14742836006042]
現実世界の多くの問題において、決定の効用は基礎となる文脈である$x$ と decision $y$ に依存する。
我々はこれを未知のユーティリティによる不可知学習として研究する。
サンプルされた点のみのユーティリティを推定することで、よく一般化した決定関数を学習できることを示す。
論文 参考訳（メタデータ） (2021-04-17T08:22:04Z) - On Avoiding the Union Bound When Answering Multiple Differentially
Private Queries [49.453751858361265]
このタスクのアルゴリズムは、$o(frac1epsilonsqrtk log frac1delta)$の期待値$ell_infty$エラーバウンドを達成する。
一方、DaganとKurkのアルゴリズムは、$O(frac1epsilonsqrtk log frac1delta)$の$ell_infty$エラー境界が期待だけでなく常に保持するという驚くべき利点を持っています。
論文 参考訳（メタデータ） (2020-12-16T17:58:45Z) - RNNs can generate bounded hierarchical languages with optimal memory [113.73133308478612]
RNNは、自然言語構文の足場を反映した境界階層言語を効率的に生成できることを示す。
Dyck-($k$,$m$)は、よくネストされた括弧($k$型)と$m$バウンドされたネスト深さの言語である。
明示的な構成により,$O(m log k)$ hidden units の RNN がメモリの指数的削減に十分であることを示す。
論文 参考訳（メタデータ） (2020-10-15T04:42:29Z) - Safe Learning under Uncertain Objectives and Constraints [66.05180398174286]
我々は、テキスト不明で安全クリティカルな制約の下で、非テクスト無知かつ安全クリティカルな最適化問題を考察する。
このような問題は、ロボティクス、製造、医療などの様々な領域で自然に発生する。
我々の分析の重要な要素は、安全な最適化の文脈で収縮と呼ばれる手法を導入し、適用することである。
論文 参考訳（メタデータ） (2020-06-23T20:51:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。