English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The need of interpreting Deep Learning (DL) models has led, during the pastyears, to a proliferation of works concerned by this issue. Among strategieswhich aim at shedding some light on how information is represented internallyin DL models, one consists in extracting symbolic rule-based machines fromconnectionist models that are supposed to approximate well their behaviour. Inorder to better understand how reasonable these approximation strategies are,we need to know the computational complexity of measuring the quality ofapproximation. In this article, we will prove some computational resultsrelated to the problem of extracting Finite State Machine (FSM) based modelsfrom 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-LMis undecidable; - As a corollary, the distance problem between languagesgenerated by PDFA/PFA/WFA and that of a weighted RNN-LM is not recursive; -Theintersection between a DFA and the cut language of a weighted RNN-LM isundecidable; - The equivalence of a PDFA/PFA/WFA and weighted RNN-LM in afinite support is EXP-Hard; (b) For consistent weight RNN-LMs with anycomputable activation function: - The Tcheybechev distance approximation isdecidable; - The Tcheybechev distance approximation in a finite support isNP-Hard. Moreover, our reduction technique from 3-SAT makes this latter facteasily generalizable to other RNN architectures (e.g. LSTMs/RNNs), and RNNswith finite precision.

Distance and Equivalence between Finite State Machines and Recurrent Neural Networks: Computational results