Fugu-MT 論文翻訳(概要): Learning Weighted Finite Automata over the Max-Plus Semiring and its Termination

論文の概要: 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* の半順序拡張において「整合性」の問題を明らかにする: 表の整合性の維持に失敗し、従って明らかに間違った仮説オートマトン上で等価なクエリを作成できることを示す。列閉性という数学的にクリーンな概念による理論的修正を提案する。また、アルゴリズムが終了する最大余剰半環上で、非自明で合理的に広い重み付き言語のクラスを示す。

関連論文リスト

Learning Quantitative Automata Modulo Theories [17.33092604696224]
本稿では,学習者が帰納的推論によって有効なオートマトンを推論する,能動的学習アルゴリズムQUINTICを提案する。本評価では, 累積, 減算, 積, 量的オートマトンを学習するために, 有理理論を利用する。
論文参考訳（メタデータ） (2024-11-15T21:51:14Z)
An $\mathbf{L^*}$ Algorithm for Deterministic Weighted Regular Languages [41.871773940580105]
我々は、FSAを学習するためのAngluin (1987) $mathbfL*$アルゴリズムの重み付き変種を示す。我々は、$mathbfL*$がターゲット言語に対して最小限のオートマトンを直接学習する方法を示す。
論文参考訳（メタデータ） (2024-11-09T16:17:14Z)
LLMs as Probabilistic Minimally Adequate Teachers for DFA Learning [11.037017229299607]
大規模言語モデル(LLM)におけるインテリジェンス(インテリジェンス)の出現は、オートマチックラーニングへの統合に関する調査にインスピレーションを与えている。本稿では,pMAT (probabilistic Minimally Adequate Teacher) の定式化について紹介する。我々は,解答精度を向上し,学習したオートマタの正確性を確保する技術を開発した。
論文参考訳（メタデータ） (2024-08-06T07:12:09Z)
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)
Automata Learning from Preference and Equivalence Queries [17.33092604696224]
本稿では,能動オートマトン学習問題の新たな変種として,嗜好クエリを用いて有限オートマトンを積極的に学習する手法を提案する。 ReMAPは、クエリの複雑さの最小限の複雑さを、正確な等価クエリの下で正確に推測することが保証されている。実験により,REMAPを大規模オートマトンにスケールすることは,一貫した教師から正しいオートマトンを学習するのに有効であることが示唆された。
論文参考訳（メタデータ） (2023-08-18T04:49:45Z)
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)
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)
Competitive Mirror Descent [67.31015611281225]
制約のある競合最適化には、制約の対象となる競合する目的を最小化しようとする複数のエージェントが含まれる。本稿では, 競合ミラー降下法(CMD)を提案する。特別の場合として、正の円錐上の問題に対する新しい競合乗法重みアルゴリズムを得る。
論文参考訳（メタデータ） (2020-06-17T22:11:35Z)

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