Nov, 2017
递归神经网络作为加权语言识别器
Recurrent Neural Networks as Weighted Language Recognizers
TL;DR本文研究了作为识别加权语言的形式模型的简单循环神经网络（RNN）的各种问题的计算复杂性，其中我们专注于单层、ReLU-激活、有理权重的 RNN，其使用广泛应用于自然语言处理应用程序。本文表明，这种 RNN 的大多数问题都是不可判定的，包括一致性、等价性、最小化和确定最高加权字符串。但对于一致性 RNN，最后一个问题变成可判定的，但其解决方案的长度可能超过所有可计算的界限。如果该字符串长度也被限制在多项式长度，那么该问题就变成了 NP-完全的并且是 APX-难的，因此本文表明了在这些 RNN 的实际应用程序中，逼近算法是必要的。