Linear decision lists and partitioning algorithms for the construction of neural networks
Linear decision lists and partitioning algorithms for the construction of neural networks
复制标题
用于构建神经网络的线性决策表和分区算法
DOI：
--
复制
发表时间：
1997
期刊：
影响因子：
--
通讯作者：
F. Vatan
中科院分区：
文献类型：
--
作者：
György Turán;F. Vatan
我们考虑由分区算法构建的神经网络的计算能力。这些神经网络也可以被视为带有评估线性函数的测试的决策列表。证明了该模型中显式布尔函数的复杂性的指数下界。下界扩展到有界等级的决策树。我们还讨论了这些模型与阈值电路复杂性类别的层次结构之间的关系。
We consider the computational power of neural networks constructed by partitioning algorithms. These neural networks can also be viewed as decision lists with tests evaluating linear functions. An exponential lower bound is proved for the complexity of an explicit Boolean function in this model. The lower bound is extended to decision trees of bounded rank. We also discuss the relationship between these models and the hierarchy of threshold circuit complexity classes.