Enumeration of linear threshold functions from the lattice of hyperplane intersections

Convex Dual Theory Analysis of Two-Layer Convolutional Neural Networks With Soft-Thresholding

Soft-thresholding has been widely used in neural networks. Its basic network structure is a two-layer convolution neural network with soft-thresholding. Due to the network's nature of nonlinear and nonconvex, the training process heavily depends on an appropriate initialization of network parameters, resulting in the difficulty of obtaining a globally optimal solution. To address this issue, a convex dual network is designed here. We theoretically analyze the network convexity and prove that the strong duality holds. Extensive results on both simulation and real-world datasets show that strong duality holds, the dual network does not depend on initialization and optimizer, and enables faster convergence than the state-of-the-art two-layer network. This work provides a new way to convexify soft-thresholding neural networks. Furthermore, the convex dual network model of a deep soft-thresholding network with a parallel structure is deduced.

Refinements of Approximation Results of Conditional Restricted Boltzmann Machines

Conditional restricted Boltzmann machines (CRBMs) are the conditional variant of restricted Boltzmann machines (RBMs), which are used to simulate conditional probability distributions. While promising for practical applications, there is a lack of theoretical studies on the approximation ability of CRBMs. In this article, by contributing analysis tools, especially designed for the conditional models, we improve the results of the representational power of CRBMs based on existing work on RBMs. We first study the properties of CRBMs to approximate conditional Markov random fields. On this basis, a universal approximation result is obtained by deriving upper bounds on the minimal number of hidden units, which improves the previous result. Furthermore, the result about maximal approximation errors of CRBMs is also improved by reducing the number of hidden units that can guarantee approximations within a given error tolerance. Furthermore, the representational efficiency of CRBMs in computing deterministic conditional distributions is investigated. Specifically, we show that there are exponentially many deterministic conditional distributions that cannot be computed by CRBMs whose size does not exponentially grow with the number of input units. Some specific examples of these hard-to-present deterministic conditional distributions are provided. Finally, some numerical experiments are carried out to verify the theoretical results of the properties of CRBMs to approximate conditional Markov random fields and the universal approximation of CRBMs.

Characterization of Linearly Separable Boolean Functions: A Graph-Theoretic Perspective

In this paper, we present a novel approach for studying Boolean function in a graph-theoretic perspective. In particular, we first transform a Boolean function f of n variables into an induced subgraph H_f of the n -dimensional hypercube, and then, we show the properties of linearly separable Boolean functions on the basis of the analysis of the structure of H_f . We define a new class of graphs, called hyperstar, and prove that the induced subgraph H_f of any linearly separable Boolean function f is a hyperstar. The proposal of hyperstar helps us uncover a number of fundamental properties of linearly separable Boolean functions in this paper.

Separating points by parallel hyperplanes--characterization problem

This paper deals with partitions of a discrete set S of points in a d-dimensional space, by h parallel hyperplanes. Such partitions are in a direct correspondence with multilinear threshold functions which appear in the theory of neural networks and multivalued logic. The characterization (encoding) problem is studied. We show that a unique characterization (encoding) of such multilinear partitions of S = {0, 1,..., m-1}d is possible within theta(h x d2 x log m) bit rate per encoded partition. The proposed characterization (code) consists of (d + 1) x (h + 1) discrete moments having the order no bigger than 1. The obtained bit rate is evaluated depending on the mutual relations between h, d, and m. The optimality is reached in some cases.

On encoding and enumerating threshold functions

In this paper, we deal with encoding and enumerating threshold functions defined on n-dimensional binary inputs. The paper specifies situations in which the unique characterization of functions from a given class is preserved by usage of an appropriate set of discrete moments. Moreover, sometimes such a characterization (coding) is optimal with respect to the number of necessary bit rate per coded function. By estimating the number of possible values of the discrete moments used, several upper bounds (for different classes of threshold functions) are derived, some of which are better than those previously known.

Bounds on the number of hidden neurons in three-layer binary neural networks

This paper investigates an important problem concerning the complexity of three-layer binary neural networks (BNNs) with one hidden layer. The neuron in the studied BNNs employs a hard limiter activation function with only integer weights and an integer threshold. The studies are focused on implementations of arbitrary Boolean functions which map from [0, 1]n into [0, 1]. A deterministic algorithm called set covering algorithm (SCA) is proposed for the construction of a three-layer BNN to implement an arbitrary Boolean function. The SCA is based on a unit sphere covering (USC) of the Hamming space (HS) which is chosen in advance. It is proved that for the implementation of an arbitrary Boolean function of n-variables (n > or = 3) by using SCA, [3L/2] hidden neurons are necessary and sufficient, where L is the number of unit spheres contained in the chosen USC of the n-dimensional HS. It is shown that by using SCA, the number of hidden neurons required is much less than that by using a two-parallel hyperplane method. In order to indicate the potential ability of three-layer BNNs, a lower bound on the required number of hidden neurons which is derived by using the method of estimating the Vapnik-Chervonenkis (VC) dimension is also given.