Covering Cubes by Random Half Cubes, with Applications to Binary Neural Networks
✍ Scribed by Jeong Han Kim; James R. Roche
- Publisher
- Elsevier Science
- Year
- 1998
- Tongue
- English
- Weight
- 650 KB
- Volume
- 56
- Category
- Article
- ISSN
- 0022-0000
No coin nor oath required. For personal study only.
✦ Synopsis
Let Q n be the (hyper)cube [&1, 1] n . This paper is concerned with the following question: How many vectors must be chosen uniformly and independently at random from Q n before every vector in Q n itself has negative inner product with at least one of the random vectors? For any fixed =>0, a simple expectation argument shows that for all sufficiently large n, (1+=) n random vectors suffice with high probability. In this paper we prove that there are =, >0 such that (1&=) n random vectors are also enough and such that at least \n random vectors are necessary.
This problem is partially motivated by neural network problems. Neural networks are being used to solve a growing number of difficult problems such as speech recognition, handwriting recognition, and protein structure prediction. Recently, for both theoretical and practical reasons, neural networks with binary weights (binary neural networks) have attracted much attention. In spite of considerable analysis based on statistical mechanics, the following two basic questions about binary neural networks have remained unanswered.
Q1. Is there a positive constant \ such that for all sufficiently large n there is a binary neural network of n neurons which can separate \n (unbiased) random patterns with probability close to 1? Q2. Is it possible for a binary neural network of n neurons to separate (1&o(1)) n random patterns with probability greater than some positive constant? (Here o(1) goes to 0 as n goes to infinity.) This question is raised because no binary neural network of n neurons can separate more than n random patterns with probability close to 1.
Our results yield the answers YES'' to Q1 and NO'' to Q2. ] 1998 Academic Press P b, b (n, (1+=) n) Ä 0 as n Ä .
(Of course, (1+=) n actually means w(1+=) nx. For the sake of simplicity, floor or ceiling signs will be omitted.) A previously unresolved question is whether there exists =>0 so that the probability P b, b (n, (1&=) n) still goes to 0. Another heretofore open question is whether there is a
Article No. SS971560 223