論文の概要: Learning Weighted Finite Automata over the Max-Plus Semiring and its Termination
- arxiv url: http://arxiv.org/abs/2407.09775v1
- Date: Sat, 13 Jul 2024 05:08:06 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-16 20:58:50.126062
- Title: Learning Weighted Finite Automata over the Max-Plus Semiring and its Termination
- Title(参考訳): マックスプラスセミナーにおける重み付き有限オートマタの学習とその終了
- Authors: Takamasa Okudono, Masaki Waga, Taro Sekiyama, Ichiro Hasuo,
- Abstract要約: 最大余剰半環上での重み付きオートマトンに対するL*型学習アルゴリズムについて検討した。
表の整合性の維持に失敗する可能性を示し、従って、明らかに間違った仮説オートマトン上で等価なクエリを作成できることを示す。
- 参考スコア(独自算出の注目度): 2.024925013349319
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Active learning of finite automata has been vigorously pursued for the purposes of analysis and explanation of black-box systems. In this paper, we study an L*-style learning algorithm for weighted automata over the max-plus semiring. The max-plus setting exposes a "consistency" issue in the previously studied semiring-generic extension of L*: we show that it can fail to maintain consistency of tables, and can thus make equivalence queries on obviously wrong hypothesis automata. We present a theoretical fix by a mathematically clean notion of column-closedness. We also present a nontrivial and reasonably broad class of weighted languages over the max-plus semiring in which our algorithm terminates.
- Abstract(参考訳): 有限オートマトンの能動的学習はブラックボックスシステムの解析と説明のために活発に追求されてきた。
本稿では,最大余剰半環上の重み付きオートマトンに対するL*型学習アルゴリズムについて検討する。
最大余剰設定は、L* の半順序拡張において「整合性」の問題を明らかにする: 表の整合性の維持に失敗し、従って明らかに間違った仮説オートマトン上で等価なクエリを作成できることを示す。
列閉性という数学的にクリーンな概念による理論的修正を提案する。
また、アルゴリズムが終了する最大余剰半環上で、非自明で合理的に広い重み付き言語のクラスを示す。
関連論文リスト
- When can you trust feature selection? -- I: A condition-based analysis
of LASSO and generalised hardness of approximation [49.1574468325115]
近似入力を読み取る際に、LASSOのミニミサの正しいサポートセットを(確率$>1/2$で)決定できないことを示す。
不適切な入力の場合、アルゴリズムは永遠に動作するので、間違った答えを出すことはない。
無限条件数を持つ点を含む開集合上で定義される任意のアルゴリズムに対して、アルゴリズムが永久に実行されるか、間違った解を生成するような入力が存在する。
論文 参考訳(メタデータ) (2023-12-18T18:29:01Z) - Generalized Convergence Analysis of Tsetlin Machines: A Probabilistic
Approach to Concept Learning [20.519261060300302]
本稿では,Tsetlinオートマトンに基づく機械学習アルゴリズムの総合収束解析について述べる。
本稿では,確率論的概念学習(PCL, Probabilistic Concept Learning)と呼ばれる新しいフレームワークを提案する。
我々は、任意の節$C_k$に対して、PCLが0.5p_k1$のときにリテラルの結合に収束することを確認する理論的証明を確立する。
論文 参考訳(メタデータ) (2023-10-03T12:21:41Z) - SatLM: Satisfiability-Aided Language Models Using Declarative Prompting [68.40726892904286]
本研究では,大規模言語モデル (LLM) の推論能力を向上させるために,新しい満足度支援言語モデリング (SatLM) 手法を提案する。
我々はLLMを用いて命令型プログラムではなく宣言型タスク仕様を生成し、既製の自動定理証明器を利用して最終解を導出する。
我々はSATLMを8つの異なるデータセット上で評価し、命令パラダイムにおいてプログラム支援されたLMよりも一貫して優れていることを示す。
論文 参考訳(メタデータ) (2023-05-16T17:55:51Z) - Differentially-Private Hierarchical Clustering with Provable
Approximation Guarantees [79.59010418610625]
階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。
例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。
本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-01-31T19:14:30Z) - Quantum Finite Automata and Quiver Algebras [0.0]
近接リングの概念を用いて、多重時間測定により量子有限オートマトンを再構成する。
これにより、量子コンピューティングとディープラーニングに対する統一的な理解が得られます。
論文 参考訳(メタデータ) (2022-03-15T02:12:13Z) - Learning Union of Integer Hypercubes with Queries (Technical Report) [0.0]
本稿では,d次元整数格子上での整数ハイパーキューブの有限和を求める問題について検討する。
非固定次元において、問題はDNF式を学習する問題を仮定する。
我々の問題には、量化子なし整数線型算術公式のモナディック分解問題への自然な応用がある。
論文 参考訳(メタデータ) (2021-05-27T11:39:10Z) - Induction and Exploitation of Subgoal Automata for Reinforcement
Learning [75.55324974788475]
本稿では,Regressed Learning (RL)タスクにおけるサブゴールの学習と活用のためのISAを提案する。
ISAは、タスクのサブゴールによってエッジがラベル付けされたオートマトンであるサブゴールオートマトンを誘導することで強化学習をインターリーブする。
サブゴールオートマトンはまた、タスクの完了を示す状態と、タスクが成功せずに完了したことを示す状態の2つの特別な状態で構成されている。
論文 参考訳(メタデータ) (2020-09-08T16:42:55Z) - Efficient Optimistic Exploration in Linear-Quadratic Regulators via
Lagrangian Relaxation [107.06364966905821]
線形2次レギュレータ(LQR)設定における探索・探索ジレンマについて検討した。
有限 MDP に対する楽観的アルゴリズムで用いられる拡張値反復アルゴリズムに着想を得て,Oulq の楽観的最適化を緩和することを提案する。
我々は、少なくとも$Obig(log (1/epsilon)big)$ Riccati方程式を解くことで、$epsilon$-OptimisticControllerを効率的に計算できることを示した。
論文 参考訳(メタデータ) (2020-07-13T16:30:47Z) - Preventing Value Function Collapse in Ensemble {Q}-Learning by
Maximizing Representation Diversity [0.0]
MaxminとEnsemble Q-learningアルゴリズムは、過大評価バイアスを減らすために、学習者のアンサンブルが提供する異なる推定値を使用している。
残念ながら、これらの学習者はパラメトリックまたは表現空間において同じ点に収束し、古典的な単一ニューラルネットワークDQNに戻ることができる。
経済理論とコンセンサス最適化から着想を得た5つの正規化関数を提案し,比較する。
論文 参考訳(メタデータ) (2020-06-24T15:53:20Z) - Competitive Mirror Descent [67.31015611281225]
制約のある競合最適化には、制約の対象となる競合する目的を最小化しようとする複数のエージェントが含まれる。
本稿では, 競合ミラー降下法(CMD)を提案する。
特別の場合として、正の円錐上の問題に対する新しい競合乗法重みアルゴリズムを得る。
論文 参考訳(メタデータ) (2020-06-17T22:11:35Z) - Submodular Maximization in Clean Linear Time [42.51873363778082]
我々は,濃度(サイズ)制約下での部分モジュライメーションの厳密な1-1/e$近似を保証する,最初の決定論的アルゴリズムを提供する。
解に対して許容される濃度が一定であるとき、関数評価のサブ線形数を作るアルゴリズムは、任意の定数比を保証できないことを示す。
我々は,映画推薦,位置情報要約,twitterテキスト要約,ビデオ要約など,複数のリアルタイム機械学習アプリケーションにおいて,我々のアルゴリズムを広範囲に評価する。
論文 参考訳(メタデータ) (2020-06-16T17:06:45Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。