Covering cubes by random half cubes, with applications to binary neural networks
type: Item
instance of: scholarly article
title: Covering cubes by random half cubes, with applications to binary neural networks
zbMATH Open document ID: 0948.68163
author: Jeong Han Kim
author: James R. Roche
published in: Journal of Computer and System Sciences
publication date: 1998-11-10T00:00:00Z
review text: The problem of covering the unit sphere \(S_n\) by \(k\) random vectors lie on the same hemisphere \(S_n\) was considered in the late 1950 and early 1960. Some researchers solved this problem by determining the value of \(k\), with the probability measures on \(S_n\) and consequently it was clear that at least \((2-\varepsilon)n\) random vectors are necessary and \((2+ \varepsilon)n\) vectors are sufficient for this purpose. Subsequently, Furedi proved that the number of binary vectors (vectors from \(Q_n\)) needed to cover \(S_n\) is almost equal to the number of random vectors (not necessarily binary vectors) that are required to cover \(S_n\). The relationships they have established are \[ P_{bs}(n, k)= P_{ss}(n, k)+ O(1/\sqrt n). \] The authors have invoked the question ``How many vectors must be chosen uniformly and independently at random from the hyper-cube \(Q_n\), so that every vector in the same hyper-cube \(Q\), has negative inner product with at least one of the random vectors?'' Subsequently, the authors analyzed it in the theoretical stand point of neural network.
Mathematics Subject Classification ID: 68T05
Mathematics Subject Classification ID: 68T99
Mathematics Subject Classification ID: 60D05
Mathematics Subject Classification ID: 60K35
zbMATH DE Number: 1220915
zbMATH Keywords: covering cubes
zbMATH Keywords: random half cubes
zbMATH Keywords: binary neural networks
reviewed by: Laxminarayan Das
MaRDI profile type: Publication
full work available at URL: jcss.1997.1560
OpenAlex ID: W2050173734
cites work: Q4004078
cites work: Q3682518
cites work: Q5563135
cites work: Enumeration of Seven-Argument Threshold Functions
cites work: The capacity of majority rule
cites work: Learning binary perceptrons perfectly efficiently.
cites work: Random polytopes in the d-dimensional cube
cites work: The space of interactions in neural network models
cites work: Neural networks and physical systems with emergent collective computational abilities.
cites work: Self-organization and associative memory
cites work: Q5532610
cites work: The existence of persistent states in the brain
cites work: Analytic study of the memory storage capacity of a neural network
cites work: Generalization properties of multilayered neural networks
cites work: A logical calculus of the ideas immanent in nervous activity
cites work: Q5556830
cites work: A Problem in Geometric Probability.
DOI: 10.1006/JCSS.1997.1560
description: scientific article; zbMATH DE number 1220915