Representation Learning: A Review and New Perspectives <s> Learning to Represent Nonlinear Manifolds <s> Several unsupervised learning algorithms based on an eigendecomposition provide either an embedding or a clustering only for given training points, with no straightforward extension for out-of-sample examples short of recomputing eigenvectors. This paper provides a unified framework for extending Local Linear Embedding (LLE), Isomap, Laplacian Eigenmaps, Multi-Dimensional Scaling (for dimensionality reduction) as well as for Spectral Clustering. This framework is based on seeing these algorithms as learning eigenfunctions of a data-dependent kernel. Numerical experiments show that the generalizations performed have a level of error comparable to the variability of the embedding algorithms due to the choice of training data. <s> BIB001 </s> Representation Learning: A Review and New Perspectives <s> Learning to Represent Nonlinear Manifolds <s> This paper introduces a new method for semi-supervised learning on high dimensional nonlinear manifolds, which includes a phase of unsupervised basis learning and a phase of supervised function learning. The learned bases provide a set of anchor points to form a local coordinate system, such that each data point x on the manifold can be locally approximated by a linear combination of its nearby anchor points, and the linear weights become its local coordinate coding. We show that a high dimensional nonlinear function can be approximated by a global linear function with respect to this coding scheme, and the approximation quality is ensured by the locality of such coding. The method turns a difficult nonlinear learning problem into a simple global linear learning problem, which overcomes some drawbacks of traditional local learning methods. <s> BIB002 </s> Representation Learning: A Review and New Perspectives <s> Learning to Represent Nonlinear Manifolds <s> Humans and animals learn much better when the examples are not randomly presented but organized in a meaningful order which illustrates gradually more concepts, and gradually more complex ones. Here, we formalize such training strategies in the context of machine learning, and call them "curriculum learning". In the context of recent research studying the difficulty of training in the presence of non-convex training criteria (for deep deterministic and stochastic neural networks), we explore curriculum learning in various set-ups. The experiments show that significant improvements in generalization can be achieved. We hypothesize that curriculum learning has both an effect on the speed of convergence of the training process to a minimum and, in the case of non-convex criteria, on the quality of the local minima obtained: curriculum learning can be seen as a particular form of continuation method (a general strategy for global optimization of non-convex functions). <s> BIB003 </s> Representation Learning: A Review and New Perspectives <s> Learning to Represent Nonlinear Manifolds <s> Local Coordinate Coding (LCC), introduced in (Yu et al., 2009), is a high dimensional nonlinear learning method that explicitly takes advantage of the geometric structure of the data. Its successful use in the winning system of last year's Pascal image classification Challenge (Everingham, 2009) shows that the ability to integrate geometric information is critical for some real world machine learning applications. This paper further develops the idea of integrating geometry in machine learning by extending the original LCC method to include local tangent directions. These new correction terms lead to better approximation of high dimensional nonlinear functions when the underlying data manifold is locally relatively flat. The method significantly reduces the number of anchor points needed in LCC, which not only reduces computational cost, but also improves prediction performance. Experiments are included to demonstrate that this method is more effective than the original LCC method on some image classification tasks. <s> BIB004 </s> Representation Learning: A Review and New Perspectives <s> Learning to Represent Nonlinear Manifolds <s> This paper proposes a principled extension of the traditional single-layer flat sparse coding scheme, where a two-layer coding scheme is derived based on theoretical analysis of nonlinear functional approximation that extends recent results for local coordinate coding. The two-layer approach can be easily generalized to deeper structures in a hierarchical multiple-layer manner. Empirically, it is shown that the deep coding approach yields improved performance in benchmark datasets. <s> BIB005 </s> Representation Learning: A Review and New Perspectives <s> Learning to Represent Nonlinear Manifolds <s> We present in this paper a novel approach for training deterministic auto-encoders. We show that by adding a well chosen penalty term to the classical reconstruction cost function, we can achieve results that equal or surpass those attained by other regularized auto-encoders as well as denoising auto-encoders on a range of datasets. This penalty term corresponds to the Frobenius norm of the Jacobian matrix of the encoder activations with respect to the input. We show that this penalty term results in a localized space contraction which in turn yields robust features on the activation layer. Furthermore, we show how this penalty term is related to both regularized auto-encoders and denoising auto-encoders and how it can be seen as a link between deterministic and non-deterministic auto-encoders. We find empirically that this penalty helps to carve a representation that better captures the local directions of variation dictated by the data, corresponding to a lower-dimensional non-linear manifold, while being more invariant to the vast majority of directions orthogonal to the manifold. Finally, we show that by using the learned features to initialize a MLP, we achieve state of the art classification error on a range of datasets, surpassing other methods of pretraining. <s> BIB006 </s> Representation Learning: A Review and New Perspectives <s> Learning to Represent Nonlinear Manifolds <s> It has been hypothesized, and supported with experimental evidence, that deeper representations, when well trained, tend to do a better job at disentangling the underlying factors of variation. We study the following related conjecture: better representations, in the sense of better disentangling, can be exploited to produce Markov chains that mix faster between modes. Consequently, mixing between modes would be more efficient at higher levels of representation. To better understand this, we propose a secondary conjecture: the higher-level samples fill more uniformly the space they occupy and the high-density manifolds tend to unfold when represented at higher levels. The paper discusses these hypotheses and tests them experimentally through visualization and measurements of mixing between modes and interpolating between samples. <s> BIB007
Can we learn a manifold without requiring nearest neighbor searches? Yes, for example, with regularized autoencoders or PCA. In PCA, the sensitivity of the extracted components (the code) to input changes is the same regardless of position x. The tangent space is the same everywhere along the linear manifold. By contrast, for a nonlinear manifold, the tangent of the manifold changes as we move on the manifold, as illustrated in Fig. 6 . In nonlinear representation-learning algorithms, it is convenient to think about the local variations in the representation as the input x is varied on the manifold, i.e., as we move among high-probability configurations. As we discuss below, the first derivative of the encoder therefore specifies the shape of the manifold (its tangent plane) around an example x lying on it. If the density was really concentrated on the manifold and the encoder had captured that, we would find the encoder derivatives to be nonzero only in the directions spanned by the tangent plane. Let us consider sparse coding in this light: Parameter matrix W may be interpreted as a dictionary of input directions from which a different subset will be picked to model the local tangent space at an x on the manifold. That subset corresponds to the active, i.e., nonzero, features for input x. Nonzero component h i will be sensitive to small changes of the input in the direction of the associated weight vector W :;i , whereas inactive features are more likely to be stuck at 0 until a significant displacement has taken place in input space. The local coordinate coding (LCC) algorithm BIB002 is very similar to sparse coding, but is explicitly derived from a manifold perspective. Using the same notation as that of sparse coding in (2), LCC replaces regularization term kh ðtÞ k 1 ¼ P j jh ðtÞ j j yielding objective This is identical to sparse coding when p ¼ À1, but with larger p it encourages the active anchor points for x ðtÞ (i.e., the codebook vectors W :;j with nonnegligible jh ðtÞ j j that are combined to reconstruct x ðtÞ ) to be not too far from x ðtÞ ; hence the local aspect of the algorithm. An important theoretical contribution of Yu et al. BIB002 is to show that that any Lipschitz-smooth function : M ! IR defined on a smooth nonlinear manifold M embedded in IR dx can be well approximated by a globally linear function with respect to the resulting coding scheme (i.e., linear in h), where the accuracy of the approximation and required number d h of anchor points depend on d M rather than d x . This result has been further extended with the use of local tangent directions BIB004 , as well as to multiple layers BIB005 . Let us now consider the efficient noniterative "feedforward" encoders f , used by PSD and the autoencoders reviewed in Section 7.2, which are in the form of BIB001 or BIB007 . The computed representation for x will only be significantly sensitive to input space directions associated with nonsaturated hidden units (see, e.g., BIB003 for the Jacobian of a sigmoid layer). These directions to which the representation is significantly sensitive, like in the case of PCA or sparse coding, may be viewed as spanning the tangent space of the manifold at point x. Rifai et al. BIB006 empirically analyze in this light the singular value spectrum of the Jacobian (derivatives of representation vector with respect to input vector) of a trained CAE. Here, the SVD provides an ordered orthonormal basis of most sensitive directions. The spectrum is sharply decreasing, indicating a relatively small number of significantly sensitive directions. This is taken as empirical evidence that the CAE indeed modeled the tangent space of a low-dimensional manifold. The leading singular vectors form a basis for the tangent plane of the estimated manifold, as illustrated in Fig. 4 . The CAE criterion is believed to achieve this thanks to its two opposing terms: The isotropic contractive penalty that encourages the representation to be equally insensitive to changes in any input directions, and the reconstruction term that pushes different training points (in particular neighbors) to have a different representation (so they may be reconstructed accurately), thus counteracting the isotropic contractive pressure only in directions tangent to the manifold. Analyzing learned representations through the lens of the spectrum of the Jacobian and relating it to the notion of tangent space of a manifold is feasible whenever the mapping is differentiable and regardless of how it was learned, whether as direct encoding (as in autoencoder variants) or derived from latent variable inference (as in sparse coding or RBMs). Exact low-dimensional manifold models (like PCA) would yield nonzero singular values associated to directions along the manifold, and exact zeros for directions orthogonal to the manifold. But in smooth models like the CAE or the RBM, we will instead have large versus relatively small singular values (as opposed to nonzero versus exactly zero).