論文の概要: On the Linguistic Capacity of Real-Time Counter Automata

• arxiv url: http://arxiv.org/abs/2004.06866v2
• Date: Thu, 9 Sep 2021 05:24:50 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-13 03:47:43.194732
• Title: On the Linguistic Capacity of Real-Time Counter Automata
• Title（参考訳）: リアルタイムカウンターオートマトンにおける言語能力について
• Authors: William Merrill
• Abstract要約: リアルタイムカウンターマシンの能力を形式文法として研究する。 対向言語は補数、和、交叉、その他多くの共通集合演算の下で閉じていることを示す。 この研究は、リカレントニューラルネットワークを理解することに興味のある形式言語理論に一般的な貢献をする。
• 参考スコア（独自算出の注目度）: 1.8072051868187933
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Counter machines have achieved a newfound relevance to the field of natural language processing (NLP): recent work suggests some strong-performing recurrent neural networks utilize their memory as counters. Thus, one potential way to understand the success of these networks is to revisit the theory of counter computation. Therefore, we study the abilities of real-time counter machines as formal grammars, focusing on formal properties that are relevant for NLP models. We first show that several variants of the counter machine converge to express the same class of formal languages. We also prove that counter languages are closed under complement, union, intersection, and many other common set operations. Next, we show that counter machines cannot evaluate boolean expressions, even though they can weakly validate their syntax. This has implications for the interpretability and evaluation of neural network systems: successfully matching syntactic patterns does not guarantee that counter memory accurately encodes compositional semantics. Finally, we consider whether counter languages are semilinear. This work makes general contributions to the theory of formal languages that are of potential interest for understanding recurrent neural networks.
• Abstract（参考訳）: カウンターマシンは、自然言語処理(NLP)分野への新たな関連性を実現している。最近の研究は、いくつかの強力な性能のリカレントニューラルネットワークが、そのメモリをカウンタとして利用していることを示唆している。 したがって、これらのネットワークの成功を理解するための潜在的な方法は、カウンター計算の理論を再考することである。 そこで我々は,NLPモデルに関連する形式的特性に着目し,リアルタイムカウンターマシンの形式文法としての能力について検討した。 まず、カウンターマシンのいくつかの変種が収束して、同じ形式言語のクラスを表現することを示す。 また、補数、和、交叉、その他多くの共通集合演算の下でカウンタ言語が閉じていることも証明する。 次に,その構文を弱く検証できるにもかかわらず,カウンタマシンはブール式を評価できないことを示す。 このことは、ニューラルネットワークシステムの解釈可能性と評価に影響を及ぼす。構文パターンをうまくマッチングすることは、カウンタメモリがコンポジションセマンティクスを正確にエンコードすることを保証しない。 最後に、カウンター言語が半線形かどうかを検討する。 この研究は、リカレントニューラルネットワークを理解することに興味のある形式言語理論に一般的な貢献をする。

関連論文リスト

• Training Neural Networks as Recognizers of Formal Languages [87.06906286950438]
  形式言語理論は、特に認識者に関するものである。 代わりに、非公式な意味でのみ類似したプロキシタスクを使用するのが一般的である。 ニューラルネットワークを文字列のバイナリ分類器として直接訓練し評価することで、このミスマッチを補正する。
  論文  参考訳（メタデータ） (2024-11-11T16:33:25Z)
• On the Representational Capacity of Neural Language Models with Chain-of-Thought Reasoning [87.73401758641089]
  CoT推論による現代言語モデル(LM)の性能向上 LMは弦上の分布の族を確率的チューリングマシンと同一に表現できることを示す。
  論文  参考訳（メタデータ） (2024-06-20T10:59:02Z)
• Lower Bounds on the Expressivity of Recurrent Neural Language Models [47.537525313391164]
  ニューラルLMの表現能力の研究は、形式言語を認識できる能力に主に焦点を絞っている。 本稿では, RNN LM の表現能力について, 線形有界精度を持つ RNN LM が任意の正則な LM を表現可能であることを示す。
  論文  参考訳（メタデータ） (2024-05-29T16:02:09Z)
• On the Computational Complexity and Formal Hierarchy of Second Order Recurrent Neural Networks [59.85314067235965]
  2次次リカレントネットワーク(RNN)の理論基盤を拡大する(2次RNN) 有界時間でチューリング完備な RNN のクラスが存在することを証明している。 また、記憶のない2ドルのRNNは、バニラRNNのような現代のモデルよりも優れており、正規文法の認識において繰り返し単位をゲートしていることを示す。
  論文  参考訳（メタデータ） (2023-09-26T06:06:47Z)
• Nondeterministic Stacks in Neural Networks [0.456877715768796]
  我々は、非決定論的プッシュダウンオートマトンを効率的にシミュレートする微分可能なデータ構造を開発する。 これにより、任意の文脈自由言語に対する形式的認識能力が向上することを示す。 また,非決定論的スタックを付加したRNNでは,驚くほど強力な動作が可能であることを示す。
  論文  参考訳（メタデータ） (2023-04-25T16:00:40Z)
• Join-Chain Network: A Logical Reasoning View of the Multi-head Attention in Transformer [59.73454783958702]
  本稿では,多くの結合演算子を連結して出力論理式をモデル化するシンボリック推論アーキテクチャを提案する。 特に,このような結合鎖のアンサンブルが'ツリー構造'の1次論理式であるFOETの広い部分集合を表現できることを実証する。 変圧器における多頭部自己保持モジュールは,確率的述語空間における結合作用素の結合境界を実装する特別なニューラル演算子として理解することができる。
  論文  参考訳（メタデータ） (2022-10-06T07:39:58Z)
• Emergence of Machine Language: Towards Symbolic Intelligence with Neural Networks [73.94290462239061]
  本稿では、ニューラルネットワークを用いてシンボルとコネクショナリズムの原理を組み合わせることで、離散表現を導出することを提案する。 対話型環境とタスクを設計することにより、機械が自発的で柔軟でセマンティックな言語を生成できることを実証した。
  論文  参考訳（メタデータ） (2022-01-14T14:54:58Z)
• SyGNS: A Systematic Generalization Testbed Based on Natural Language Semantics [39.845425535943534]
  自然言語セマンティックス(SyGNS)に基づく体系的一般化テストベッドを提案する。 ニューラルネットワークが、量化子や否定といった論理式の新しい組み合わせを含む文を体系的に解析できるかどうかを検証する。 実験により、Transformer と GRU モデルは、与えられたトレーニングインスタンスの形式に類似しているが、他のモデルには似ていない量化器、否定器、修飾器の組み合わせに一般化できることが示された。
  論文  参考訳（メタデータ） (2021-06-02T11:24:41Z)
• Recognizing Long Grammatical Sequences Using Recurrent Networks Augmented With An External Differentiable Stack [73.48927855855219]
  リカレントニューラルネットワーク(RNN)は、シーケンスモデリング、生成、予測に広く使われているディープアーキテクチャである。 RNNは、非常に長いシーケンスに対してあまり一般化せず、多くの重要な時間的処理や時系列予測問題に適用性を制限する。 これらの欠点に対処する方法の1つは、スタックのような外部の異なるメモリ構造とRNNを結合することである。 本稿では,重要なアーキテクチャと状態更新機構を備えたメモリ拡張RNNを改良する。
  論文  参考訳（メタデータ） (2020-04-04T14:19:15Z)

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

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