A semi-supervised learning framework using the feedforward-designed convolutional neural networks (FF-CNNs) is proposed for image classification in this work. One unique property of FF-CNNs is that no backpropagation is used in model parameters determination. Since unlabeled data may not always enhance semi-supervised learning, we define an effective quality score and use it to select a subset of unlabeled data in the training process. We conduct experiments on the MNIST, SVHN, and CIFAR-10 datasets, and show that the proposed semi-supervised FF-CNN solution outperforms the CNN trained by backpropagation (BP-CNN) when the amount of labeled data is reduced. Furthermore, we develop an ensemble system that combines the output decision vectors of different semi-supervised FF-CNNs to boost classification accuracy. The ensemble systems can achieve further performance gains on all three benchmarking datasets.
The construction of FC layers is achieved by the cascade of multiple rectified linear least-squared regressors (LSRs) @cite_19 . Let the input and output dimensions of a FC layer be @math and @math (with @math ), respectively. To construct an FC layer, we cluster input samples of dimension @math into @math clusters, and assign pseudo-labels based on clustering results. Next, all samples are transformed into a vector space of dimension @math via LSR, where the index of the output space dimension defines a pseudo-label. In this way, we obtain a supervised LSR building module to serve as one FC layer. It accommodates intra-class variability while enhancing discriminability gradually.
@cite_19
2949474319
The model parameters of convolutional neural networks (CNNs) are determined by backpropagation (BP). In this work, we propose an interpretable feedforward (FF) design without any BP as a reference. The FF design adopts a data-centric approach. It derives network parameters of the current layer based on data statistics from the output of the previous layer in a one-pass manner. To construct convolutional layers, we develop a new signal transform, called the Saab (Subspace Approximation with Adjusted Bias) transform. It is a variant of the principal component analysis (PCA) with an added bias vector to annihilate activation's nonlinearity. Multiple Saab transforms in cascade yield multiple convolutional layers. As to fully-connected (FC) layers, we construct them using a cascade of multi-stage linear least squared regressors (LSRs). The classification and robustness (against adversarial attacks) performances of BP- and FF-designed CNNs applied to the MNIST and the CIFAR-10 datasets are compared. Finally, we comment on the relationship between BP and FF designs. We establish @math and @math error bounds for functions of many variables that are approximated by linear combinations of ReLU (rectified linear unit) and squared ReLU ridge functions with @math and @math controls on their inner and outer parameters. With the squared ReLU ridge function, we show that the @math approximation error is inversely proportional to the inner layer @math sparsity and it need only be sublinear in the outer layer @math sparsity. Our constructions are obtained using a variant of the Jones-Barron probabilistic method, which can be interpreted as either stratified sampling with proportionate allocation or two-stage cluster sampling. We also provide companion error lower bounds that reveal near optimality of our constructions. Despite the sparsity assumptions, we showcase the richness and flexibility of these ridge combinations by defining a large family of functions, in terms of certain spectral conditions, that are particularly well approximated by them. In this paper, we consider regression problems with one-hidden-layer neural networks (1NNs). We distill some properties of activation functions that lead to @math in the neighborhood of the ground-truth parameters for the 1NN squared-loss objective. Most popular nonlinear activation functions satisfy the distilled properties, including rectified linear units (ReLUs), leaky ReLUs, squared ReLUs and sigmoids. For activation functions that are also smooth, we show @math guarantees of gradient descent under a resampling rule. For homogeneous activations, we show tensor methods are able to initialize the parameters to fall into the local strong convexity region. As a result, tensor initialization followed by gradient descent is guaranteed to recover the ground truth with sample complexity @math and computational complexity @math for smooth homogeneous activations with high probability, where @math is the dimension of the input, @math ( @math ) is the number of hidden nodes, @math is a conditioning property of the ground-truth parameter matrix between the input layer and the hidden layer, @math is the targeted precision and @math is the number of samples. To the best of our knowledge, this is the first work that provides recovery guarantees for 1NNs with both sample complexity and computational complexity @math in the input dimension and @math in the precision. We present new approximation algorithms for the @math -median and @math -means clustering problems. To this end, we obtain small coresets for @math -median and @math -means clustering in general metric spaces and in Euclidean spaces. In @math , these coresets are of size with polynomial dependency on the dimension @math . This leads to @math -approximation algorithms to the optimal @math -median and @math -means clustering in @math , with running time @math , where @math is the number of points. This improves over previous results. We use those coresets to maintain a @math -approximate @math -median and @math -means clustering of a stream of points in @math , using @math space. These are the first streaming algorithms, for those problems, that have space complexity with polynomial dependency on the dimension. We study the improper learning of multi-layer neural networks. Suppose that the neural network to be learned has @math hidden layers and that the @math -norm of the incoming weights of any neuron is bounded by @math . We present a kernel-based method, such that with probability at least @math , it learns a predictor whose generalization error is at most @math worse than that of the neural network. The sample complexity and the time complexity of the presented method are polynomial in the input dimension and in @math , where @math is a function depending on @math and on the activation function, independent of the number of neurons. The algorithm applies to both sigmoid-like activation functions and ReLU-like activation functions. It implies that any sufficiently sparse neural network is learnable in polynomial time. In this preliminary work, we study the problem of distributed authentication in wireless networks. Specifically, we consider a system where multiple Bob (sensor) nodes listen to a channel and report their correlated measurements to a Fusion Center (FC) which makes the ultimate authentication decision. For the feature- based authentication at the FC, channel impulse response has been utilized as the device fingerprint. Additionally, the correlated measurements by the Bob nodes allow us to invoke Compressed sensing to significantly reduce the reporting overhead to the FC. Numerical results show that: i) the detection performance of the FC is superior to that of a single Bob-node, ii) compressed sensing leads to at least @math overhead reduction on the reporting channel at the expense of a small ( @math dB) SNR margin to achieve the same detection performance. We study the optimal design problems where the goal is to choose a set of linear measurements to obtain the most accurate estimate of an unknown vector in @math dimensions. We study the @math -optimal design variant where the objective is to minimize the average variance of the error in the maximum likelihood estimate of the vector being measured. The problem also finds applications in sensor placement in wireless networks, sparse least squares regression, feature selection for @math -means clustering, and matrix approximation. In this paper, we introduce proportional volume sampling to obtain improved approximation algorithms for @math -optimal design. Our main result is to obtain improved approximation algorithms for the @math -optimal design problem by introducing the proportional volume sampling algorithm. Our results nearly optimal bounds in the asymptotic regime when the number of measurements done, @math , is significantly more than the dimension @math . We also give first approximation algorithms when @math is small including when @math . The proportional volume-sampling algorithm also gives approximation algorithms for other optimal design objectives such as @math -optimal design and generalized ratio objective matching or improving previous best known results. Interestingly, we show that a similar guarantee cannot be obtained for the @math -optimal design problem. We also show that the @math -optimal design problem is NP-hard to approximate within a fixed constant when @math . This paper explores the complexity of deep feedforward networks with linear pre-synaptic couplings and rectified linear activations. This is a contribution to the growing body of work contrasting the representational power of deep and shallow network architectures. In particular, we offer a framework for comparing deep and shallow models that belong to the family of piecewise linear functions based on computational geometry. We look at a deep rectifier multi-layer perceptron (MLP) with linear outputs units and compare it with a single layer version of the model. In the asymptotic regime, when the number of inputs stays constant, if the shallow model has @math hidden units and @math inputs, then the number of linear regions is @math . For a @math layer model with @math hidden units on each layer it is @math . The number @math grows faster than @math when @math tends to infinity or when @math tends to infinity and @math . Additionally, even when @math is small, if we restrict @math to be @math , we can show that a deep model has considerably more linear regions that a shallow one. We consider this as a first step towards understanding the complexity of these models and specifically towards providing suitable mathematical tools for future analysis. For input @math , let @math denote the set of outputs that are the "legal" answers for a computational problem @math . Suppose @math and members of @math are so large that there is not time to read them in their entirety. We propose a model of local computation algorithms which for a given input @math , support queries by a user to values of specified locations @math in a legal output @math . When more than one legal output @math exists for a given @math , the local computation algorithm should output in a way that is consistent with at least one such @math . Local computation algorithms are intended to distill the common features of several concepts that have appeared in various algorithmic subfields, including local distributed computation, local algorithms, locally decodable codes, and local reconstruction. We develop a technique, based on known constructions of small sample spaces of @math -wise independent random variables and Beck's analysis in his algorithmic approach to the Lov ' a sz Local Lemma, which under certain conditions can be applied to construct local computation algorithms that run in polylogarithmic time and space. We apply this technique to maximal independent set computations, scheduling radio network broadcasts, hypergraph coloring and satisfying @math -SAT formulas. This paper proposes a reinforcement ant optimized fuzzy controller (FC) design method, called RAOFC, and applies it to wheeled-mobile-robot wall-following control under reinforcement learning environments. The inputs to the designed FC are range-finding sonar sensors, and the controller output is a robot steering angle. The antecedent part in each fuzzy rule uses interval type-2 fuzzy sets in order to increase FC robustness. No a priori assignment of fuzzy rules is necessary in RAOFC. An online aligned interval type-2 fuzzy clustering (AIT2FC) method is proposed to generate rules automatically. The AIT2FC not only flexibly partitions the input space but also reduces the number of fuzzy sets in each input dimension, which improves controller interpretability. The consequent part of each fuzzy rule is designed using Q-value aided ant colony optimization (QACO). The QACO approach selects the consequent part from a set of candidate actions according to ant pheromone trails and Q-values, both of whose values are updated using reinforcement signals. Simulations and experiments on mobile-robot wall-following control show the effectiveness and efficiency of the proposed RAOFC. Universal circuits UCs can be programmed to evaluate any circuit of a given size k. They provide elegant solutions in various application scenarios, e.g. for private function evaluationi¾?PFE and for improving the flexibility of attribute-based encryptioni¾?ABE schemes. The optimal size of a universal circuit is proven to be @math Ωklogk. Valianti¾?STOC'76 proposed a size-optimized UC construction, which has not been put in practice ever since. The only implementation of universal circuits was provided by Kolesnikov and Schneider FC'08, with sizei¾? @math Oklog2k. In this paper, we refine the size of Valiant's UC and further improve the construction by at least 2k. We show that due to recent optimizations and our improvements, it is the best solution to apply in the case for circuits with a constant number of inputs and outputs. When the number of inputs or outputs is linear in the number of gates, we propose a more efficient hybrid solution based on the two existing constructions. We validate the practicality of Valiant's UC, by giving an example implementation for PFE using these size-optimized UCs. Convolutional neural networks (CNNs) have recently achieved remarkable successes in various image classification and understanding tasks. The deep features obtained at the top fully connected layer of the CNN (FC-features) exhibit rich global semantic information and are extremely effective in image classification. On the other hand, the convolutional features in the middle layers of the CNN also contain meaningful local information, but are not fully explored for image representation. In this paper, we propose a novel locally supervised deep hybrid model (LS-DHM) that effectively enhances and explores the convolutional features for scene recognition. First, we notice that the convolutional features capture local objects and fine structures of scene images, which yield important cues for discriminating ambiguous scenes, whereas these features are significantly eliminated in the highly compressed FC representation. Second, we propose a new local convolutional supervision layer to enhance the local structure of the image by directly propagating the label information to the convolutional layers. Third, we propose an efficient Fisher convolutional vector (FCV) that successfully rescues the orderless mid-level semantic information (e.g., objects and textures) of scene image. The FCV encodes the large-sized convolutional maps into a fixed-length mid-level representation, and is demonstrated to be strongly complementary to the high-level FC-features. Finally, both the FCV and FC-features are collaboratively employed in the LS-DHM representation, which achieves outstanding performance in our experiments. It obtains 83.75 and 67.56 accuracies, respectively, on the heavily benchmarked MIT Indoor67 and SUN397 data sets, advancing the state-of-the-art substantially. We give the first dimension-efficient algorithms for learning Rectified Linear Units (ReLUs), which are functions of the form @math with @math . Our algorithm works in the challenging Reliable Agnostic learning model of Kalai, Kanade, and Mansour (2009) where the learner is given access to a distribution @math on labeled examples but the labeling may be arbitrary. We construct a hypothesis that simultaneously minimizes the false-positive rate and the loss on inputs given positive labels by @math , for any convex, bounded, and Lipschitz loss function. The algorithm runs in polynomial-time (in @math ) with respect to any distribution on @math (the unit sphere in @math dimensions) and for any error parameter @math (this yields a PTAS for a question raised by F. Bach on the complexity of maximizing ReLUs). These results are in contrast to known efficient algorithms for reliably learning linear threshold functions, where @math must be @math and strong assumptions are required on the marginal distribution. We can compose our results to obtain the first set of efficient algorithms for learning constant-depth networks of ReLUs. Our techniques combine kernel methods and polynomial approximations with a "dual-loss" approach to convex programming. As a byproduct we obtain a number of applications including the first set of efficient algorithms for "convex piecewise-linear fitting" and the first efficient algorithms for noisy polynomial reconstruction of low-weight polynomials on the unit sphere. Conventional convolutional neural networks use either a linear or a nonlinear filter to extract features from an image patch (region) of spatial size @math (typically, @math is small and is equal to @math , e.g., @math is 5 or 7). Generally, the size of the filter is equal to the size @math of the input patch. We argue that the representational ability of equal-size strategy is not strong enough. To overcome the drawback, we propose to use subpatch filter whose spatial size @math is smaller than @math . The proposed subpatch filter consists of two subsequent filters. The first one is a linear filter of spatial size @math and is aimed at extracting features from spatial domain. The second one is of spatial size @math and is used for strengthening the connection between different input feature channels and for reducing the number of parameters. The subpatch filter convolves with the input patch and the resulting network is called a subpatch network. Taking the output of one subpatch network as input, we further repeat constructing subpatch networks until the output contains only one neuron in spatial domain. These subpatch networks form a new network called the cascaded subpatch network (CSNet). The feature layer generated by CSNet is called the csconv layer. For the whole input image, we construct a deep neural network by stacking a sequence of csconv layers. Experimental results on five benchmark data sets demonstrate the effectiveness and compactness of the proposed CSNet. For example, our CSNet reaches a test error of 5.68 on the CIFAR10 data set without model averaging. To the best of our knowledge, this is the best result ever obtained on the CIFAR10 data set. Interpolators---estimators that achieve zero training error---have attracted growing attention in machine learning, mainly because state-of-the art neural networks appear to be models of this type. In this paper, we study minimum @math norm ( ridgeless') interpolation in high-dimensional least squares regression. We consider two different models for the feature distribution: a linear model, where the feature vectors @math are obtained by applying a linear transform to a vector of i.i.d. entries, @math (with @math ); and a nonlinear model, where the feature vectors are obtained by passing the input through a random one-layer neural network, @math (with @math , @math a matrix of i.i.d. entries, and @math an activation function acting componentwise on @math ). We recover---in a precise quantitative way---several phenomena that have been observed in large-scale neural networks and kernel machines, including the double descent' behavior of the prediction risk, and the potential benefits of overparametrization. We consider the problem of learning an unknown function @math on the @math -dimensional sphere with respect to the square loss, given i.i.d. samples @math where @math is a feature vector uniformly distributed on the sphere and @math . We study two popular classes of models that can be regarded as linearizations of two-layers neural networks around a random initialization: (RF) The random feature model of Rahimi-Recht; (NT) The neural tangent kernel model of Jacot-Gabriel-Hongler. Both these approaches can also be regarded as randomized approximations of kernel ridge regression (with respect to different kernels), and hence enjoy universal approximation properties when the number of neurons @math diverges, for a fixed dimension @math . We prove that, if both @math and @math are large, the behavior of these models is instead remarkably simpler. If @math , then RF performs no better than linear regression with respect to the raw features @math , and NT performs no better than linear regression with respect to degree-one and two monomials in the @math . More generally, if @math then RF fits at most a degree- @math polynomial in the raw features, and NT fits at most a degree- @math polynomial. We show how to approximate a data matrix @math with a much smaller sketch @math that can be used to solve a general class of constrained k-rank approximation problems to within @math error. Importantly, this class of problems includes @math -means clustering and unconstrained low rank approximation (i.e. principal component analysis). By reducing data points to just @math dimensions, our methods generically accelerate any exact, approximate, or heuristic algorithm for these ubiquitous problems. For @math -means dimensionality reduction, we provide @math relative error results for many common sketching techniques, including random row projection, column selection, and approximate SVD. For approximate principal component analysis, we give a simple alternative to known algorithms that has applications in the streaming setting. Additionally, we extend recent work on column-based matrix reconstruction, giving column subsets that not only cover' a good subspace for @math , but can be used directly to compute this subspace. Finally, for @math -means clustering, we show how to achieve a @math approximation by Johnson-Lindenstrauss projecting data points to just @math dimensions. This gives the first result that leverages the specific structure of @math -means to achieve dimension independent of input size and sublinear in @math . An ensemble method that fuses the output decision vectors of multiple feedforward-designed convolutional neural networks (FF-CNNs) to solve the image classification problem is proposed in this work. To enhance the performance of the ensemble system, it is critical to increasing the diversity of FF-CNN models. To achieve this objective, we introduce diversities by adopting three strategies: 1) different parameter settings in convolutional layers, 2) flexible feature subsets fed into the Fully-connected (FC) layers, and 3) multiple image embeddings of the same input source. Furthermore, we partition input samples into easy and hard ones based on their decision confidence scores. As a result, we can develop a new ensemble system tailored to hard samples to further boost classification accuracy. Experiments are conducted on the MNIST and CIFAR-10 datasets to demonstrate the effectiveness of the ensemble method. We study a generalization of the setting of regenerating codes, motivated by applications to storage systems consisting of clusters of storage nodes. There are @math clusters in total, with @math nodes per cluster. A data file is coded and stored across the @math nodes, with each node storing @math symbols. For availability of data, we require that the file be retrievable by downloading the entire content from any subset of @math clusters. Nodes represent entities that can fail. We distinguish between intra-cluster and inter-cluster bandwidth (BW) costs during node repair. Node-repair in a cluster is accomplished by downloading @math symbols each from any set of @math other clusters, dubbed remote helper clusters, and also up to @math symbols each from any set of @math surviving nodes, dubbed local helper nodes, in the host cluster. We first identify the optimal trade-off between storage-overhead and inter-cluster repair-bandwidth under functional repair, and also present optimal exact-repair code constructions for a class of parameters. The new trade-off is strictly better than what is achievable via space-sharing existing coding solutions, whenever @math . We then obtain sharp lower bounds on the necessary intra-cluster repair BW to achieve optimal trade-off. Under functional repair, random linear network codes (RLNCs) simultaneously optimize usage of both inter- and intra-cluster repair BW; simulation results based on RLNCs suggest optimality of the bounds on intra-cluster repair-bandwidth. Our bounds reveal the interesting fact that, while it is beneficial to increase the number of local helper nodes @math in order to improve the storage-vs-inter-cluster-repair-BW trade-off, increasing @math not only increases intra-cluster BW in the host-cluster, but also increases the intra-cluster BW in the remote helper clusters. We also analyze resilience of the clustered storage system against passive eavesdropping by providing file-size bounds and optimal code constructions. We develop an extension of recently developed methods for obtaining time-space tradeoff lower bounds for problems of learning from random test samples to handle the situation where the space of tests is signficantly smaller than the space of inputs, a class of learning problems that is not handled by prior work. This extension is based on a measure of how matrices amplify the 2-norms of probability distributions that is more refined than the 2-norms of these matrices. As applications that follow from our new technique, we show that any algorithm that learns @math -variate homogeneous polynomial functions of degree at most @math over @math from evaluations on randomly chosen inputs either requires space @math or @math time where @math is the dimension of the space of such functions. These bounds are asymptotically optimal since they match the tradeoffs achieved by natural learning algorithms for the problems.