論文の概要: 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から構築する還元アルゴリズムを提案する。 最後に,提案手法の有効性を示す実験を行い,提案の有効性を検証する。

関連論文リスト

• Fast Exact NPN Classification with Influence-aided Canonical Form [4.210634768624388]
  ブール関数解析の基本的な概念であるNPN分類にブール効果を導入する。 インフルエンサーは入力ネゲーション非依存であり、入力パーミューテーション依存であり、以前のシグネチャとは別の構造情報を持っていることを示す。 ABCで実装された最先端のアルゴリズムと比較すると,NPN分類の精度は5.5倍に向上する。
  論文  参考訳（メタデータ） (2023-08-23T01:50:09Z)
• Nonparametric Masked Language Modeling [113.71921977520864]
  既存の言語モデル(LM)は、有限語彙上のソフトマックスでトークンを予測する。 NPMは,このソフトマックスを参照コーパス内の各フレーズの非パラメトリック分布に置き換える最初の非パラメトリックマスク付き言語モデルである。 NPMは、コントラスト目的と全コーパス検索に対するバッチ内近似で効率的に訓練することができる。
  論文  参考訳（メタデータ） (2022-12-02T18:10:42Z)
• 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)
• 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)
• Approximation and Non-parametric Estimation of ResNet-type Convolutional Neural Networks [52.972605601174955]
  本稿では,ResNet型CNNが重要な関数クラスにおいて最小誤差率を達成可能であることを示す。 Barron と H'older のクラスに対する前述のタイプの CNN の近似と推定誤差率を導出する。
  論文  参考訳（メタデータ） (2019-03-24T19:42:39Z)

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

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