論文の概要: DFAMiner: Mining minimal separating DFAs from labelled samples

• arxiv url: http://arxiv.org/abs/2405.18871v1
• Date: Wed, 29 May 2024 08:31:34 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-30 18:09:15.331733
• Title: DFAMiner: Mining minimal separating DFAs from labelled samples
• Title（参考訳）: DFAMiner:ラベル付きサンプルから最小限のDFAを分離する
• Authors: Daniele Dell'Erba, Yong Li, Sven Schewe,
• Abstract要約: DFAMinerは、ラベル付きサンプルから最小限の決定論的有限オートマトン(DFA)を分離するパッシブ学習ツールである。 まず,ラベル付きサンプルの集合から3値のDFAを漸進的に構築する,単純で線形時間アルゴリズムを提案する。 そこで我々は,SAT問題を最小化して構築したオートマトンを最小化することにより,ラベル付きサンプルの最小分離DFAをマイニングするツールを開発した。
• 参考スコア（独自算出の注目度）: 8.196522686887713
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We propose DFAMiner, a passive learning tool for learning minimal separating deterministic finite automata (DFA) from a set of labelled samples. Separating automata are an interesting class of automata that occurs generally in regular model checking and has raised interest in foundational questions of parity game solving. We first propose a simple and linear-time algorithm that incrementally constructs a three-valued DFA (3DFA) from a set of labelled samples given in the usual lexicographical order. This 3DFA has accepting and rejecting states as well as don't-care states, so that it can exactly recognise the labelled examples. We then apply our tool to mining a minimal separating DFA for the labelled samples by minimising the constructed automata via a reduction to solving SAT problems. Empirical evaluation shows that our tool outperforms current state-of-the-art tools significantly on standard benchmarks for learning minimal separating DFAs from samples. Progress in the efficient construction of separating DFAs can also lead to finding the lower bound of parity game solving, where we show that DFAMiner can create optimal separating automata for simple languages with up to 7 colours. Future improvements might offer inroads to better data structures.
• Abstract（参考訳）: ラベル付きサンプルから最小限の決定論的有限オートマトン(DFA)を分離する受動的学習ツールであるDFAMinerを提案する。 分離オートマトンは、通常モデルチェックで一般的に発生する興味深いオートマトンクラスであり、パリティゲーム解決の基本的な問題に関心を寄せている。 まず,3値のDFA(3DFA)を,通常の語彙順に付与されたラベル付きサンプルの集合からインクリメンタルに構築する,単純で線形な時間的アルゴリズムを提案する。 この3DFAは、ラベル付き例を正確に認識できるように、状態を受け入れ、拒否すると同時に、不注意な状態も受け入れている。 そこで我々は,SAT問題を最小化して構築したオートマトンを最小化することにより,ラベル付きサンプルの最小分離DFAをマイニングするツールを開発した。 実験的な評価の結果,本ツールはサンプルから最小限のDFAを学習するための標準ベンチマークにおいて,最先端のツールよりも優れていた。 DFAを分離する効率的な構築の進歩は、DFAMinerが最大7色までの単純な言語に対して最適な分離オートマトンを作成できることを示すために、パリティゲーム解決の低い境界を見つけることにも繋がる。 将来的には、データ構造の改善が期待できるだろう。

関連論文リスト

• Instruction Tuning with Retrieval-based Examples Ranking for Aspect-based Sentiment Analysis [7.458853474864602]
  アスペクトベースの感情分析(ABSA)は、特定の側面に関連する感情情報を識別し、企業や組織に対してより深い市場洞察を提供する。 近年の研究では、ABSAを生成タスクとして再構成する命令チューニングの固定例が提案されている。 本研究では,ABSAタスクの検索に基づくサンプルランキングを用いた指導学習手法を提案する。
  論文  参考訳（メタデータ） (2024-05-28T10:39:10Z)
• Prompt Optimization with EASE? Efficient Ordering-aware Automated Selection of Exemplars [66.823588073584]
  大規模言語モデル(LLM)は、現実世界のアプリケーションで印象的な機能を示している。 これらの卓越した作品の品質は、パフォーマンスに大きな影響を与えます。 既存の方法は、先行注文がパフォーマンスに与える影響を適切に説明できない。
  論文  参考訳（メタデータ） (2024-05-25T08:23:05Z)
• Direct Large Language Model Alignment Through Self-Rewarding Contrastive Prompt Distillation [47.16091219929373]
  コントラッシブ・プロンプト・ペア下での応答対の出力確率を用いて応答選好を評価する手法を提案する。 そこで本研究では,DLMA(Direct Large Model Alignment)の自動アライメント手法を提案する。 実験段階において,本手法は人手による好みデータに頼ることなく,textttRLHF法を超えることができる。
  論文  参考訳（メタデータ） (2024-02-19T07:46:40Z)
• Optimization meets Machine Learning: An Exact Algorithm for Semi-Supervised Support Vector Machines [1.104960878651584]
  サポートベクトルマシン(SVM)は、バイナリ分類のための教師付き学習モデルである。 半定値プログラミング(SDP)緩和を用いたS3VMの新しい分岐手法を提案する。 SDP緩和は文献で利用できるものよりもはるかに強い境界を提供する。
  論文  参考訳（メタデータ） (2023-12-15T13:44:54Z)
• Self-Supervised Dataset Distillation for Transfer Learning [77.4714995131992]
  ラベルなしデータセットを、効率的な自己教師付き学習(SSL)のための小さな合成サンプル群に蒸留する新しい問題を提案する。 両レベル最適化におけるSSL目標に対する合成サンプルの勾配は、データ拡張やマスキングから生じるランダム性から、テキストバイアスを受けていることを最初に証明する。 転送学習を含む様々な応用における本手法の有効性を実証的に検証する。
  論文  参考訳（メタデータ） (2023-10-10T10:48:52Z)
• Towards Automated Imbalanced Learning with Deep Hierarchical Reinforcement Learning [57.163525407022966]
  不均衡学習はデータマイニングにおいて基本的な課題であり、各クラスにトレーニングサンプルの不均等な比率が存在する。 オーバーサンプリングは、少数民族のための合成サンプルを生成することによって、不均衡な学習に取り組む効果的な手法である。 我々は,異なるレベルの意思決定を共同で最適化できる自動オーバーサンプリングアルゴリズムであるAutoSMOTEを提案する。
  論文  参考訳（メタデータ） (2022-08-26T04:28:01Z)
• Sparse Conditional Hidden Markov Model for Weakly Supervised Named Entity Recognition [68.68300358332156]
  雑音ラベリング機能を評価するために,スパース条件付き隠れマルコフモデル(Sparse-CHMM)を提案する。 Sparse-CHMMは、3段階のトレーニングパイプラインで教師なし学習によって最適化される。 5つの包括的なデータセットで平均F1スコアが3.01向上する。
  論文  参考訳（メタデータ） (2022-05-27T20:47:30Z)
• Fast Variational AutoEncoder with Inverted Multi-Index for Collaborative Filtering [59.349057602266]
  変分オートエンコーダ (VAE) は, 協調フィルタリングの非線形手法として拡張されている。 内積に基づくソフトマックス確率を逆多重インデックスに基づいて分解する。 FastVAEはサンプリング品質と効率の両面で最先端のベースラインを上回っます。
  論文  参考訳（メタデータ） (2021-09-13T08:31:59Z)
• Examining and Combating Spurious Features under Distribution Shift [94.31956965507085]
  我々は、最小限の統計量という情報理論の概念を用いて、ロバストで刺激的な表現を定義し、分析する。 入力分布のバイアスしか持たない場合でも、モデルはトレーニングデータから急激な特徴を拾い上げることができることを証明しています。 分析から着想を得た結果,グループDROは,グループ同士の相関関係を直接考慮しない場合に失敗する可能性が示唆された。
  論文  参考訳（メタデータ） (2021-06-14T05:39:09Z)
• Finding Influential Instances for Distantly Supervised Relation Extraction [42.94953922808431]
  本研究は、影響関数(IF)による距離監視(DS)のための新しいモデル非依存型インスタンスサンプリング法を提案する。 提案手法は、IFに基づいてバッグ内の好ましくない/好ましくないインスタンスを特定し、次に動的インスタンスサンプリングを行う。 実験の結果、REIFは複雑なアーキテクチャを持つ一連のベースラインに勝てることがわかった。
  論文  参考訳（メタデータ） (2020-09-17T02:02:07Z)
• AFP-SRC: Identification of Antifreeze Proteins Using Sparse Representation Classifier [5.285065659030821]
  極寒地に住む種は、解凍タンパク質(AFP)を用いた厳しい環境と戦う スパース再構成を用いたサンプル固有分類法を用いて,AFPの予測のための計算フレームワークを提案する。 提案手法は, 平衡精度とユーデン指数の点で優れていた。
  論文  参考訳（メタデータ） (2020-09-11T08:24:50Z)

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

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