Universal Approximation Capability of Cascade Correlation for Structures
Universal Approximation Capability of Cascade Correlation for Structures
复制标题
结构级联相关的万能逼近能力
作者：
B. Hammer;A. Micheli;A. Sperduti
级联相关（CC）是神经网络的一种训练方法，它在训练过程中决定神经网络的权重和结构。已经提出了将CC扩展到结构化数据的各种方法：序列的递归级联关联（RCC），具有有限扇出的树结构的递归级联关联（RecCC），以及具有有限扇入和扇出的根有向位置无环图（DPAGs）的上下文递归级联关联（CRecCC）。我们证明了这些模型在以下意义上具有普遍的近似性质：给定输入集上的概率测度P，从序列到实向量空间的每一个可测量函数都可以用一个s型RCC逼近到任意小概率的输入，达到任何期望的精度程度。从具有有限扇出的树形结构到实向量空间的每个可测量函数都可以通过具有乘法神经元的s型RecCC来近似，其精度可达任意小概率输入的任何期望程度。对于具有乘法神经元的s型CRecCC网络，我们展示了在所有dpag的重要子集上的函数的通用逼近能力，这些dpag具有有限的扇入和扇出，其中特定的线性表示产生唯一的代码。我们给出了后一种性质的一个结构上的充分条件，这个条件很容易检验：入边和出边的枚举必须相容。该属性可以通过重新枚举子节点和父节点实现扇入和扇出两个DPAG，也可以通过扩展扇入和扇出以及重新枚举子节点和父节点实现更大的扇入和扇出。此外，所得结果可推广到结构的输入输出同构转导情况。因此，CRecCC网络构成了第一个证明了涉及相当一般的无环图结构的函数的普遍逼近能力的神经模型。
Cascade correlation (CC) constitutes a training method for neural networks that determines the weights as well as the neural architecture during training. Various extensions of CC to structured data have been proposed: recurrent cascade correlation (RCC) for sequences, recursive cascade correlation (RecCC) for tree structures with limited fan-out, and contextual recursive cascade correlation (CRecCC) for rooted directed positional acyclic graphs (DPAGs) with limited fan-in and fan-out. We show that these models possess the universal approximation property in the following sense: given a probability measure P on the input set, every measurable function from sequences into a real vector space can be approximated by a sigmoidal RCC up to any desired degree of accuracy up to inputs of arbitrary small probability. Every measurable function from tree structures with limited fan-out into a real vector space can be approximated by a sigmoidal RecCC with multiplicative neurons up to any desired degree of accuracy up to inputs of arbitrary small probability. For sigmoidal CRecCC networks with multiplicative neurons, we show the universal approximation capability for functions on an important subset of all DPAGs with limited fan-in and fan-out for which a specific linear representation yields unique codes. We give one sufficient structural condition for the latter property, which can easily be tested: the enumeration of ingoing and outgoing edges should becom patible. This property can be fulfilled for every DPAG with fan-in and fan-out two via reenumeration of children and parents, and for larger fan-in and fan-out via an expansion of the fan-in and fan-out and reenumeration of children and parents. In addition, the result can be generalized to the case of input-output isomorphic transductions of structures. Thus, CRecCC networks consti-tute the first neural models for which the universal approximation ca-pability of functions involving fairly general acyclic graph structures is proved.