Constructive higher-order network that is polynomial time

Redding, Nicholas J., Kowalczyk, Adam and Downs, Tom (1993) Constructive higher-order network that is polynomial time. Neural Networks, 6 7: 997-1010. doi:10.1016/S0893-6080(09)80009-9

Author Redding, Nicholas J.
Kowalczyk, Adam
Downs, Tom
Title Constructive higher-order network that is polynomial time
Journal name Neural Networks   Check publisher's open access policy
ISSN 0893-6080
Publication date 1993-01-01
Sub-type Article (original research)
DOI 10.1016/S0893-6080(09)80009-9
Open Access Status Not yet assessed
Volume 6
Issue 7
Start page 997
End page 1010
Total pages 14
Language eng
Subject 2805 Cognitive Neuroscience
1702 Artificial Intelligence
Abstract Constructive learning algorithms are important because they address two practical difficulties of learning in artificial neural networks. First, it is not always possible to determine the minimal network consistent with a particular problem. Second, algorithms like backpropagation can require networks that are larger than the minimal architecture for satisfactory convergence. Further, constructive algorithms have the advantage that polynomial-time learning is possible if network size is chosen by the learning algorithm so that the learning of the problem under consideration is simplified. This article considers the representational ability of feedforward networks (FFNs) in terms of the fan-in required by the hidden units of a network. We define network order to be the maximum fan-in of the hidden units of a network. We prove, in terms of the problems they may represent, that a higher-order network (HON) is at least as powerful as any other FFN architecture when the order of the networks are the same. Next, we present a detailed theoretical development of a constructive, polynomial-time algorithm that will determine an exact HON realization with minimal order for an arbitrary binary or bipolar mapping problem. This algorithm does not have any parameters that need tuning for good performance. We show how an FFN with sigmoidal hidden units can be determined from the HON realization in polynomial time. Last, simulation results of the constructive HON algorithm are presented for the two-or-more clumps problem, demonstrating that the algorithm performs well when compared with the Tiling and Upstart algorithms.
Keyword Constructive networks
Feedforward networks
Higher-order networks
Network order
Polynomial time
Two-or-more clumps problem
Q-Index Code C1
Q-Index Status Provisional Code
Institutional Status UQ

Document type: Journal Article
Sub-type: Article (original research)
Collection: Scopus Import - Archived
Version Filter Type
Citation counts: Scopus Citation Count Cited 65 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Fri, 05 Jan 2018, 03:59:27 EST