论文标题
有限状态机与经常性神经网络之间的距离和等效性：计算结果
Distance and Equivalence between Finite State Machines and Recurrent Neural Networks: Computational results
论文作者
论文摘要
在过去的几年中，需要解释深度学习（DL）模型的需求导致了这个问题所关心的作品的扩散。旨在阐明在DL模型内部表示信息的策略中，其中一种是从连接派模型中提取基于符号规则的机器，这些机器本来可以近似其行为。为了更好地了解这些近似策略的合理性，我们需要了解测量近似质量的计算复杂性。在本文中，我们将证明与从训练有素的RNN语言模型中提取有限状态机（FSM）模型的问题有关的一些计算结果。更确切地说，我们将显示以下内容：（a）对于具有单个隐藏层的一般加权RNN-LMS和一个relu激活： - PDFA/PFA/WFA的等价问题和加权的一阶RNN-LM是不可否认的； - 作为推论，PDFA/PFA/WFA产生的语言之间的距离问题与加权RNN-LM的距离不是递归的； - DFA与加权RNN-LM的剪切语言之间的相交是不可确定的； - 在有限支撑中，PDFA/PFA/WFA和加权RNN-LM的等效性； （b）对于具有任何可计算激活函数的一致重量RNN -LMS： - Tcheybechev距离近似是可决定的； - 有限支撑中的Tcheybechev距离近似是NP固定。此外，我们从3-SAT进行的还原技术使后一个事实很容易概括为其他RNN架构（例如LSTMS/RNNS）和具有有限精度的RNN。
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.
