論文の概要: GA and ILS for optimizing the size of NFA models

• arxiv url: http://arxiv.org/abs/2107.05877v1
• Date: Tue, 13 Jul 2021 06:52:41 GMT
• ステータス: 処理完了
• システム内更新日: 2021-07-14 14:45:26.639295
• Title: GA and ILS for optimizing the size of NFA models
• Title（参考訳）: NFAモデルのサイズ最適化のためのGAとILS
• Authors: Fr\'ed\'eric Lardeux (LERIA), Eric Monfroy (LERIA)
• Abstract要約: 文法的推論は、形式文法(書き直し規則の集合または有限状態機械のような)を学ぶことから成る 非決定論的有限オートマタ(NFA)を正と負の単語のサンプルから学習することに関心がある。 接尾辞に基づく新しいモデルと接尾辞と接尾辞に基づくハイブリッドモデルを提案する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Grammatical inference consists in learning a formal grammar (as a set of rewrite rules or a finite state machine). We are concerned with learning Nondeterministic Finite Automata (NFA) of a given size from samples of positive and negative words. NFA can naturally be modeled in SAT. The standard model [1] being enormous, we also try a model based on prefixes [2] which generates smaller instances. We also propose a new model based on suffixes and a hybrid model based on prefixes and suffixes. We then focus on optimizing the size of generated SAT instances issued from the hybrid models. We present two techniques to optimize this combination, one based on Iterated Local Search (ILS), the second one based on Genetic Algorithm (GA). Optimizing the combination significantly reduces the SAT instances and their solving time, but at the cost of longer generation time. We, therefore, study the balance between generation time and solving time thanks to some experimental comparisons, and we analyze our various model improvements.
• Abstract（参考訳）: 文法的推論は形式文法(書き換え規則または有限状態機械のセットとして)を学ぶことから始まる。 非決定論的有限オートマタ(NFA)を正と負の単語のサンプルから学習することに関心がある。 NFAはSATでモデル化できる。 標準モデル[1]は巨大であり、より小さなインスタンスを生成するプレフィックス[2]に基づくモデルも試します。 また,接尾辞に基づく新しいモデルと接尾辞と接尾辞に基づくハイブリッドモデルを提案する。 次に、ハイブリッドモデルから発行されるSATインスタンスのサイズを最適化することに集中する。 この組み合わせを最適化する2つの手法を提案する。1つは反復局所探索(ils)、もう1つは遺伝的アルゴリズム(ga)に基づく。 組み合わせの最適化は、satインスタンスとその解決時間を大幅に削減するが、長い生成時間のコストがかかる。 そこで,実験による比較により,生成時間と解解時間とのバランスについて検討し,モデルの改良について検討した。

関連論文リスト

• Random Models for Fuzzy Clustering Similarity Measures [0.0]
  Adjusted Rand Index (ARI) は、ハードクラスタリングを比較するために広く使われている手法である。 本稿では,ハードクラスタリングとファジィクラスタリングの両方に対して直感的で説明可能な3つのランダムモデルを用いて,ARIを計算するための単一のフレームワークを提案する。
  論文  参考訳（メタデータ） (2023-12-16T00:07:04Z)
• Improving generalization in large language models by learning prefix subspaces [5.911540700785975]
  本稿では、希少なデータ構造における大規模言語モデル(LLM)の微調整に焦点を当てる("few-shot"学習環境としても知られる)。 ニューラルネットワーク部分空間に基づくLLMの一般化能力を向上させる手法を提案する。
  論文  参考訳（メタデータ） (2023-10-24T12:44:09Z)
• A Stable, Fast, and Fully Automatic Learning Algorithm for Predictive Coding Networks [65.34977803841007]
  予測符号化ネットワークは、ベイズ統計学と神経科学の両方にルーツを持つ神経科学にインスパイアされたモデルである。 シナプス重みに対する更新規則の時間的スケジュールを変更するだけで、元の規則よりもずっと効率的で安定したアルゴリズムが得られることを示す。
  論文  参考訳（メタデータ） (2022-11-16T00:11:04Z)
• Hierarchical Phrase-based Sequence-to-Sequence Learning [94.10257313923478]
  本稿では、学習中の帰納バイアスの源として階層的フレーズを取り入れ、推論中の明示的な制約として、標準的なシーケンス・ツー・シーケンス(seq2seq)モデルの柔軟性を維持するニューラルトランスデューサについて述べる。 本手法では,木が原文と対象句を階層的に整列するブラケット文法に基づく識別的導出法と,整列した句を1対1で翻訳するニューラルネットワークセク2セックモデルという2つのモデルを訓練する。
  論文  参考訳（メタデータ） (2022-11-15T05:22:40Z)
• Optimizing Binary Decision Diagrams with MaxSAT for classification [3.2894524838755608]
  説明可能な人工知能への関心の高まりは、解釈可能な機械学習(ML)モデルの必要性を動機付けている。 近年、従来の手法の弱点を克服するために、そのようなモデルを計算するためのいくつかの正確な方法が提案されている。 本稿ではまず,最適なバイナリ決定図(BDD)を学習するためのSATモデルを提案する。 次に、符号化をMaxSATモデルに上げ、限られた深さで最適なBDDを学習します。 最後に、MaxSATモデルを介して見つけたBDDの互換性のあるサブツリーをマージする手法を導入することにより、フラグメンテーションの問題に取り組む。
  論文  参考訳（メタデータ） (2022-03-21T23:17:37Z)
• Transformer-based Machine Learning for Fast SAT Solvers and Logic Synthesis [63.53283025435107]
  CNFベースのSATとMaxSATは論理合成と検証システムの中心である。 そこで本研究では,Transformerアーキテクチャから派生したワンショットモデルを用いて,MaxSAT問題の解法を提案する。
  論文  参考訳（メタデータ） (2021-07-15T04:47:35Z)
• Improved SAT models for NFA learning [0.0]
  文法推論は、単語からオートマトンと文法を学ぶアルゴリズムの研究に関係している。 単語のサンプルからサイズkの非決定論的有限オートマトンを学習することに集中する。
  論文  参考訳（メタデータ） (2021-07-13T06:54:07Z)
• Structured Reordering for Modeling Latent Alignments in Sequence Transduction [86.94309120789396]
  本稿では,分離可能な置換の辺りを正確に推定する効率的な動的プログラミングアルゴリズムを提案する。 結果のSeq2seqモデルは、合成問題やNLPタスクの標準モデルよりも体系的な一般化が優れている。
  論文  参考訳（メタデータ） (2021-06-06T21:53:54Z)
• Fantastically Ordered Prompts and Where to Find Them: Overcoming Few-Shot Prompt Order Sensitivity [16.893758238773263]
  少数のトレーニングサンプルしか持たなかった場合、GPT-3のような非常に大きな事前訓練された言語モデルは、競争力のある結果を示した。 サンプルが提供される順序は、ほぼ最先端の予測性能とランダムな推測性能の差であることを示す。 言語モデルの生成特性を利用して人工的な開発セットを構築し、このセットから候補置換のエントロピー統計に基づいて、実行者プロンプトを同定する。
  論文  参考訳（メタデータ） (2021-04-18T09:29:16Z)
• Finding Geometric Models by Clustering in the Consensus Space [61.65661010039768]
  本稿では,未知数の幾何学的モデル,例えばホモグラフィーを求めるアルゴリズムを提案する。 複数の幾何モデルを用いることで精度が向上するアプリケーションをいくつか提示する。 これには、複数の一般化されたホモグラフからのポーズ推定、高速移動物体の軌道推定が含まれる。
  論文  参考訳（メタデータ） (2021-03-25T14:35:07Z)
• Learning Gaussian Graphical Models via Multiplicative Weights [54.252053139374205]
  乗算重み更新法に基づいて,Klivans と Meka のアルゴリズムを適用した。 アルゴリズムは、文献の他のものと質的に類似したサンプル複雑性境界を楽しみます。 ランタイムが低い$O(mp2)$で、$m$サンプルと$p$ノードの場合には、簡単にオンライン形式で実装できる。
  論文  参考訳（メタデータ） (2020-02-20T10:50:58Z)

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

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