Search

PAC learning theory is the foundation of computational learning theory. VC-dimension, Rademacher complexity, and empirical risk-minimization principle are three concepts for deriving a generalization error bound for a trained machine. The fundamental theorem of learning theory relates PAC learnability, VC-dimension, and empirical risk-minimization principle. Another basic theorem in computational learning theory is no-free-lunch theorem. These topics are addressed in this chapter.

Sparse coding is a matrix factorization technique. It models a target signal as a sparse linear combination of atoms (elementary signals) drawn from a dictionary (a fixed collection). Sparse coding has become a popular paradigm in signal processing, statistics, and machine learning. This chapter introduces compressed sensing, sparse representation/sparse coding, tensor compressed sensing, and sparse PCA.

SVM [12, 201] is one of the most popular nonparametric classification algorithms. It is optimal and is based on computational learning theory [200, 202]. The goal of SVM is to minimize the VC dimension by finding the optimal hyperplane between classes, with the maximal margin, where the margin is defined as the distance of the closest point in each class to the separating hyperplane. It has a general-purpose linear learning algorithm and a problem-specific kernel that computes the inner product of input data points in a feature space. The key idea of SVM is to project the training set in a high-dimensional space into a lower-dimensional feature space by means of a set of nonlinear kernel functions, where the projections of the training examples are always linearly separable in the feature space. The hippocampus, a brain region critical for learning and memory processes, has been reported to possess pattern separation function similar to SVM [6].

Hardware and parallel implementations can substantially speed up machine learning algorithms to extend their widespread applications. In this chapter, we first introduce various circuit realizations for popular neural network learning methods. We then introduce their parallel implementations on graphic processing units (GPUs), systolic arrays of processors, and parallel computers.

Biometrics are the personal or physical characteristics of a person. These biometric identities are usually used for identification or verification. Biometric recognition systems are increasingly being deployed as a more natural, more secure, and more efficient means than the conventional password-based method for the recognition of people. Many biometric verification systems have been developed for global security.

The brain is a strongly recurrent structure. This massive recurrence suggests a major role of self-feeding dynamics in the processes of perceiving, acting and learning, and in maintaining the organism alive

Imagine that you are attending a cocktail party, the surrounding is full of chatting and noise, and somebody is talking about you. In this case, your ears are particularly sensitive to this speaker. This is the cocktail-party problem, which can be solved by blind source separation (BSS).

The human brain stores the information in synapses or in reverberating loops of electrical activity. Most of existing associative memory models store information in synapses.

The kernel method was originally invented in Aizerman et al. (Autom. Remote Control, 25, 821–837, 1964). The key idea is to project the training set in a lower-dimensional space into a high-dimensional kernel (feature) space by means of a set of nonlinear kernel functions.

Matrix factorization or factor analysis is an important task that is helpful in the analysis of high-dimensional real-world data. SVD is a classical method for matrix factorization, which gives the optimal low-rank approximation to a real-valued matrix in terms of the squared error. Many application areas, including information retrieval, pattern recognition, and data mining, require processing of binary rather than real data.

Learning is a fundamental capability of neural networks. Learning rules are algorithms for finding suitable weights W and/or other network parameters.

Clustering is a fundamental tool for data analysis. It finds wide applications in many engineering and scientific fields including pattern recognition, feature extraction, vector quantization, image segmentation, bioinformatics, and data mining. Clustering is a classical method for the prototype selection of kernel-based neural networks such as the RBF network, and is most useful for neurofuzzy systems.

The Bayesian network model was introduced by Pearl in 1985 [147]. It is the best known family of graphical models in artificial intelligence (AI). Bayesian networks are a powerful tool of common knowledge representation and reasoning for partial beliefs under uncertainty. They are probabilistic models that combine probability theory and graph theory.

MLPs are feedforward networks with one or more layers of units between the input and output layers. The output units represent a hyperplane in the space of the input patterns. The architecture of MLP is illustrated in Fig. 4.1.

Conventional competitive learning-based clustering algorithms like \(C\)-means and LVQ are plagued by a severe initialization problem [57, 106]. If the initial values of the prototypes are not in the convex hull formed by the input data, clustering may not produce meaningful results.

Different learning algorithms have different accuracies. The no free lunch theorem asserts that no single learning algorithm always achieves the best performance in any domain. They can be combined to attain higher accuracy. Data fusion is the process of fusing multiple records representing the same real-world object into a single, consistent, and clean representation. Fusion of data for improving prediction accuracy and reliability is an important problem in machine learning.

The Hopfield model [27, 28] is the most popular dynamic model. It is biologically plausible since it functions like the human retina [36].

Hardware technologies for implementing neural networks can be either analog or digital. Analog hardware is a good choice. The design of analog chips requires good theoretical knowledge of transistor physics as well as experience. Weights in a neural network can be coded by one single analog element (e.g., a resistor). Very simple rules such as Kirchoff’s laws can be used to carry out addition of input signals. As an example, Boltzmann machines can be easily implemented by amplifying the natural noise present in analog devices.

Most signal-processing problems can be reduced to some form of eigenvalue or singular-value problems.

Learning is an approximation problem, which is closely related to the conventional approximation techniques, such as generalized splines and regularization techniques. The RBF network has its origin in performing exact interpolation of a set of data points in a multidimensional space [81]. The RBF network is a universal approximator, and it is a popular alternative to the MLP, since it has a simpler structure and a much faster training process. Both models are widely used for classification and function approximation.