論文の概要: Distance and Equivalence between Finite State Machines and Recurrent
Neural Networks: Computational results
- arxiv url: http://arxiv.org/abs/2004.00478v1
- Date: Wed, 1 Apr 2020 14:48:59 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-17 18:11:19.235259
- Title: Distance and Equivalence between Finite State Machines and Recurrent
Neural Networks: Computational results
- Title（参考訳）: 有限状態機械とリカレントニューラルネットワーク間の距離と等価性:計算結果
- Authors: Reda Marzouk and Colin de la Higuera
- Abstract要約: 訓練されたRNN言語モデルから有限状態マシンベースモデルを抽出する問題に関するいくつかの結果を示す。
我々の3-SATによる削減技術は、後者の事実を他のRNNアーキテクチャに容易に一般化できるようにする。
- 参考スコア（独自算出の注目度）: 0.348097307252416
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The need of interpreting Deep Learning (DL) models has led, during the past
years, to a proliferation of works concerned by this issue. Among strategies
which aim at shedding some light on how information is represented internally
in DL models, one consists in extracting symbolic rule-based machines from
connectionist models that are supposed to approximate well their behaviour. In
order to better understand how reasonable these approximation strategies are,
we need to know the computational complexity of measuring the quality of
approximation. In this article, we will prove some computational results
related to the problem of extracting Finite State Machine (FSM) based models
from trained RNN Language models. More precisely, we'll show the following: (a)
For general weighted RNN-LMs with a single hidden layer and a ReLu activation:
- The equivalence problem of a PDFA/PFA/WFA and a weighted first-order RNN-LM
is undecidable; - As a corollary, the distance problem between languages
generated by PDFA/PFA/WFA and that of a weighted RNN-LM is not recursive; -The
intersection between a DFA and the cut language of a weighted RNN-LM is
undecidable; - The equivalence of a PDFA/PFA/WFA and weighted RNN-LM in a
finite support is EXP-Hard; (b) For consistent weight RNN-LMs with any
computable activation function: - The Tcheybechev distance approximation is
decidable; - The Tcheybechev distance approximation in a finite support is
NP-Hard. Moreover, our reduction technique from 3-SAT makes this latter fact
easily generalizable to other RNN architectures (e.g. LSTMs/RNNs), and RNNs
with finite precision.
- Abstract（参考訳）: ディープラーニング(DL)モデルを解釈する必要性は、過去数年間、この問題に関連する作業の急増につながっている。
DLモデルにおいて、情報がどのように内部的に表現されるかを示すことを目的とした戦略の中で、その振舞いをうまく近似するコネクショナリストモデルからシンボリックルールベースのマシンを抽出する。
これらの近似戦略がどの程度妥当かをよりよく理解するためには、近似の質を測る計算の複雑さを知る必要がある。
本稿では、訓練されたRNN言語モデルから有限状態マシン(FSM)ベースのモデルを抽出する問題に関連する計算結果について述べる。
より正確には、下記のとおりです。
a) 単一の隠蔽層とReLuアクティベーションを持つ一般的なRNN-LMの場合: - PDFA/PFA/WFAと重み付き一階RNN-LMの等価性問題は決定不能; - 概要として、PDFA/PFA/WFAと重み付きRNN-LMの言語間の距離問題は再帰的; - DFAと重み付きRNN-LMのカット言語との交点は決定不能; - PDFA/PFA/WFAと重み付きRNN-LMの有限サポートにおける等価性はEXP-Hard;
(b) 計算可能な活性化関数を持つ一貫したウェイト RNN-LM に対して、 - チェベチェフ距離近似は決定可能である; - 有限支持におけるチェベチェフ距離近似は NP-Hard である。
さらに,本手法は, LSTM/RNN などの他の RNN アーキテクチャや, 有限精度の RNN にも適用可能である。
関連論文リスト
- Learning Useful Representations of Recurrent Neural Network Weight Matrices [30.583752432727326]
リカレントニューラルネットワーク(Recurrent Neural Networks、RNN)は、汎用並列シーケンスコンピュータである。
下流タスクと同様に、RNN分析を容易にするRNN重みの有用な表現をどうやって学習するか?
我々は、RNN重みに対するいくつかの力学的アプローチを検討し、RNNに対して置換同変のDeep Weight Space層を適用する。
我々の2つの新しい機能主義者は、入力を探索することでRNNの重みから情報を'インターロゲート'することで抽出する。
論文 参考訳（メタデータ） (2024-03-18T17:32:23Z) - On the Representational Capacity of Recurrent Neural Language Models [56.19166912044362]
計算時間を持つ有理重み付きRLMは、有理重み付き遷移を持つ決定論的確率的チューリングマシン(PTM)をシミュレートできることを示す。
また, 実時間計算の制約下では, 決定論的実時間有理PTMをシミュレートできることを示した。
論文 参考訳（メタデータ） (2023-10-19T17:39:47Z) - Recurrent Neural Language Models as Probabilistic Finite-state Automata [66.23172872811594]
RNN LMが表現できる確率分布のクラスについて検討する。
単純なRNNは確率的有限状態オートマトンの部分クラスと同値であることを示す。
これらの結果は、RNN LMが表現できる分布のクラスを特徴付けるための第一歩を示す。
論文 参考訳（メタデータ） (2023-10-08T13:36:05Z) - 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) - Bayesian Neural Network Language Modeling for Speech Recognition [59.681758762712754]
長期記憶リカレントニューラルネットワーク(LSTM-RNN)とトランスフォーマーで表される最先端のニューラルネットワーク言語モデル(NNLM)は非常に複雑になりつつある。
本稿では,LSTM-RNN と Transformer LM の基盤となる不確実性を考慮するために,ベイズ学習フレームワークの全体構造を提案する。
論文 参考訳（メタデータ） (2022-08-28T17:50:19Z) - Comparative Analysis of Interval Reachability for Robust Implicit and
Feedforward Neural Networks [64.23331120621118]
我々は、暗黙的ニューラルネットワーク(INN)の堅牢性を保証するために、区間到達可能性分析を用いる。
INNは暗黙の方程式をレイヤとして使用する暗黙の学習モデルのクラスである。
提案手法は, INNに最先端の区間境界伝搬法を適用するよりも, 少なくとも, 一般的には, 有効であることを示す。
論文 参考訳（メタデータ） (2022-04-01T03:31:27Z) - Multilevel Bayesian Deep Neural Networks [0.5892638927736115]
我々は、ディープニューラルネットワーク(DNN)、特にトレースクラスニューラルネットワーク(TNN)に関連付けられた推論について検討する。
TNN事前は無限個の隠れ単位を持つ関数上で定義され、有限個の隠れ単位を持つ強い収束近似を持つ。
本稿では,TNNの強い収束を利用して,これらのモデルにマルチレベルモンテカルロ(MLMC)を適用する。
論文 参考訳（メタデータ） (2022-03-24T09:49:27Z) - Adaptive Discounting of Implicit Language Models in RNN-Transducers [33.63456351411599]
RNN-Tアーキテクチャでは,軽量適応型LMディスカウント技術が利用できることを示す。
WERとレアワードPERの最大4%と14%の相対的削減を,会話型,コード混在型のHindi- English ASRタスクで達成した。
論文 参考訳（メタデータ） (2022-02-21T08:44:56Z) - Explainable Natural Language Processing with Matrix Product States [2.3243389656894595]
我々は,映画レビューの感情分析である,ユビキタスNLPタスクにおいて,RNNの行動の体系的分析を行う。
単層RACは最大情報伝達能力を有することを示す。
我々の研究は、RACにおける学習の現象学と、より一般的にはNLPにおけるRNNの説明可能性に光を当てている。
論文 参考訳（メタデータ） (2021-12-16T05:10:32Z) - Connecting Weighted Automata, Tensor Networks and Recurrent Neural
Networks through Spectral Learning [58.14930566993063]
我々は、形式言語と言語学からの重み付き有限オートマトン(WFA)、機械学習で使用されるリカレントニューラルネットワーク、テンソルネットワークの3つのモデル間の接続を提示する。
本稿では,連続ベクトル入力の列上に定義された線形2-RNNに対する最初の証明可能な学習アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-10-19T15:28:00Z) - On Computability, Learnability and Extractability of Finite State
Machines from Recurrent Neural Networks [0.0]
この研究は、有限状態マシン(FSM)とリカレントニューラルネットワーク(RNN)の間の接続に光を当てることを目的としている。
このマスターの論文では、リカレントニューラルネットワークからの有限状態マシンの抽出可能性、学習可能性の側面、計算リンクの3倍のコネクションが検討されている。
論文 参考訳（メタデータ） (2020-09-10T15:55:30Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。