Distance and Equivalence between Finite State Machines and Recurrent
  Neural Networks: Computational results
  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.
