論文の概要: Taking advantage of a very simple property to efficiently infer NFAs

• arxiv url: http://arxiv.org/abs/2303.09311v1
• Date: Thu, 16 Mar 2023 13:36:55 GMT
• ステータス: 処理完了
• システム内更新日: 2023-03-17 15:21:19.081442
• Title: Taking advantage of a very simple property to efficiently infer NFAs
• Title（参考訳）: NFAを効率的に推論するための非常に単純な性質の活用
• Authors: Tomasz Jastrzab, 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 finite state machine or as a set of rewrite rules. In this paper, we are concerned with inferring Nondeterministic Finite Automata (NFA) that must accept some words, and reject some other words from a given sample. This problem can naturally be modeled in SAT. The standard model being enormous, some models based on prefixes, suffixes, and hybrids were designed to generate smaller SAT instances. There is a very simple and obvious property that says: if there is an NFA of size k for a given sample, there is also an NFA of size k+1. We first strengthen this property by adding some characteristics to the NFA of size k+1. Hence, we can use this property to tighten the bounds of the size of the minimal NFA for a given sample. We then propose simplified and refined models for NFA of size k+1 that are smaller than the initial models for NFA of size k. We also propose a reduction algorithm to build an NFA of size k from a specific NFA of size k+1. Finally, we validate our proposition with some experimentation that shows the efficiency of our approach.
• Abstract（参考訳）: 文法推論は、形式文法を有限状態機械または書き直し規則の集合として学習することで構成される。 本稿では,ある単語を受理しなければならない非決定論的有限オートマタ(NFA)を推定し,与えられたサンプルから他の単語を拒絶することに関心がある。 この問題は自然にsatでモデル化できる。 標準モデルは巨大であり、プレフィックス、接尾辞、ハイブリッドに基づくいくつかのモデルはより小さなsatインスタンスを生成するように設計された。 あるサンプルに対してサイズ k の NFA が存在するなら、サイズ k+1 の NFA が存在する。 我々はまず、この性質を k+1 の NFA にいくつかの特性を加えて強化する。 したがって、この性質を用いて、与えられたサンプルに対して最小の NFA の大きさの境界を締め付けることができる。 次に、k の NFA の初期モデルよりも小さいサイズ k+1 の NFA に対する単純化された洗練されたモデルを提案する。 また,サイズkのnfaを,サイズk+1の特定のnfaから構築する還元アルゴリズムを提案する。 最後に,提案手法の有効性を示す実験を行い,提案の有効性を検証する。

関連論文リスト

• Sample-Then-Optimize Batch Neural Thompson Sampling [50.800944138278474]
  我々はトンプソンサンプリング(TS)ポリシーに基づくブラックボックス最適化のための2つのアルゴリズムを提案する。 入力クエリを選択するには、NNをトレーニングし、トレーニングされたNNを最大化してクエリを選択するだけです。 我々のアルゴリズムは、大きなパラメータ行列を逆転する必要性を助長するが、TSポリシーの妥当性は保たれている。
  論文  参考訳（メタデータ） (2022-10-13T09:01:58Z)
• Thutmose Tagger: Single-pass neural model for Inverse Text Normalization [76.87664008338317]
  逆テキスト正規化(ITN)は自動音声認識において重要な後処理ステップである。 本稿では,ITN例の粒度アライメントに基づくデータセット作成手法を提案する。 タグと入力語との1対1対応により、モデルの予測の解釈性が向上する。
  論文  参考訳（メタデータ） (2022-07-29T20:39:02Z)
• Nearest Neighbor Zero-Shot Inference [68.56747574377215]
  kNN-Promptは、言語モデル(LM)を用いたゼロショット推論のためのk-nearest neighbor (kNN)検索拡張手法である。 ファジィ動詞化器は、各分類ラベルを自然言語トークンのセットに自動的に関連付けることで、下流タスクのスパースkNN分布を利用する。 実験により,kNN-Promptはドメイン適応に有効であり,さらに,kNN検索に使用するモデルのサイズに応じて,検索のメリットが増加することが示された。
  論文  参考訳（メタデータ） (2022-05-27T07:00:59Z)
• Minimax Optimal Quantization of Linear Models: Information-Theoretic Limits and Efficient Algorithms [59.724977092582535]
  測定から学習した線形モデルの定量化の問題を考える。 この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。 本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
  論文  参考訳（メタデータ） (2022-02-23T02:39:04Z)
• Geometric Path Enumeration for Equivalence Verification of Neural Networks [2.007262412327553]
  2つのNNが等価な振る舞いを示すことを示すことを目的としたNN等価性の形式的検証問題に焦点をあてる。 理論的には、epsilon-equivalence問題はcoNP完全であることを示す。 第3のステップでは、等価性検証のための拡張アルゴリズムを実装し、その実用化に必要な最適化を評価する。
  論文  参考訳（メタデータ） (2021-12-13T11:56:08Z)
• Improved SAT models for NFA learning [0.0]
  文法推論は、単語からオートマトンと文法を学ぶアルゴリズムの研究に関係している。 単語のサンプルからサイズkの非決定論的有限オートマトンを学習することに集中する。
  論文  参考訳（メタデータ） (2021-07-13T06:54:07Z)
• GA and ILS for optimizing the size of NFA models [0.0]
  文法的推論は、形式文法(書き直し規則の集合または有限状態機械のような)を学ぶことから成る 非決定論的有限オートマタ(NFA)を正と負の単語のサンプルから学習することに関心がある。 接尾辞に基づく新しいモデルと接尾辞と接尾辞に基づくハイブリッドモデルを提案する。
  論文  参考訳（メタデータ） (2021-07-13T06:52:41Z)
• Efficient Explanations With Relevant Sets [30.296628060841645]
  本稿では,$delta$-relevant 集合の実用的限界に対処するための解について検討する。 $delta$-relevant 集合の部分集合の計算は NP であり、NP のオラクルへの多くの呼び出しで解ける。
  論文  参考訳（メタデータ） (2021-06-01T14:57:58Z)
• Adaptive Nearest Neighbor Machine Translation [60.97183408140499]
  kNN-MTは、事前訓練されたニューラルネットワーク翻訳とトークンレベルのk-nearest-neighbor検索を組み合わせる。 従来のkNNアルゴリズムは、ターゲットトークンごとに同じ数の近傍を検索する。 ターゲットトークン毎のk個数を動的に決定する適応的kNN-MTを提案する。
  論文  参考訳（メタデータ） (2021-05-27T09:27:42Z)
• PCFGs Can Do Better: Inducing Probabilistic Context-Free Grammars with Many Symbols [22.728124473130876]
  テンソル分解に基づくPCFGの新しいパラメータ化形式を提案する。 ニューラルパラメタライゼーションを新しい形式に応用し,教師なし解析性能を向上させる。 10言語のモデルを評価し、より多くのシンボルの使用の有効性を実証しています。
  論文  参考訳（メタデータ） (2021-04-28T12:25:27Z)
• Anchor & Transform: Learning Sparse Embeddings for Large Vocabularies [60.285091454321055]
  我々は,アンカー埋め込みとスパース変換行列の小さな組を学習する,単純で効率的な埋め込みアルゴリズムを設計する。 テキスト分類、言語モデリング、映画レコメンデーションのベンチマークでは、ANTは大きな語彙サイズに特に適していることが示されている。
  論文  参考訳（メタデータ） (2020-03-18T13:07:51Z)

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

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