Learning Nonoverlapping Perceptron Networks from Examples and Membership Queries

作者:Thomas R. Hancock, Mostefa Golea, Mario Marchand

摘要

We investigate, within the PAC learning model, the problem of learning nonoverlapping perceptron networks (also known as read-once formulas over a weighted threshold basis). These are loop-free neural nets in which each node has only one outgoing weight. We give a polynomial time algorithm that PAC learns any nonoverlapping perceptron network using examples and membership queries. The algorithm is able to identify both the architecture and the weight values necessary to represent the function to be learned. Our results shed some light on the effect of the overlap on the complexity of learning in neural networks.

论文关键词:Neural networks, PAC learning, nonoverlapping, read-once formula, learning with queries

论文评审过程:

论文官网地址:https://doi.org/10.1023/A:1022637108202