Supervised Dictionary Learning Julien Mairal INRIA-Willow project julien.mairal@inria.fr Jean Ponce ´ Ecole Normale Superieure jean.ponce@ens.fr Francis Bach INRIA-Willow project francis.bach@inria.fr Andrew Zisserman University of Oxford az@robots.ox.ac.uk Guillermo Sapiro University of Minnesota guille@ece.umn.edu Abstract It is now well established that sparse signal models are well suited to restoration tasks and can effectively be learned from audio, image, and video data. Recent research has been aimed at learning discriminative sparse models instead of purely reconstructive ones. This paper proposes a new step in that direction, with a novel sparse representation for signals belonging to different classes in terms of a shared dictionary and multiple discriminative class models. The linear variant of the proposed model admits a simple probabilistic interpretation, while its most general variant admits an interpretation in terms of kernels. An optimization framework for learning all the components of the proposed model is presented, along with experimental results on standard handwritten digit and texture classification tasks. 1 Introduction Sparse and overcomplete image models were first introduced in [1] for modeling the spatial receptive fields of simple cells in the human visual system. The linear decomposition of a signal using a few atoms of a learned dictionary, instead of predefined ones­such as wavelets­has recently led to state-of-the-art results for numerous low-level image processing tasks such as denoising [2], showing that sparse models are well adapted to natural images. Unlike principal component analysis decompositions, these models are most ofen overcomplete, with a number of basis elements greater than the dimension of the data. Recent research has shown that sparsity helps to capture higherorder correlation in data: In [3, 4], sparse decompositions are used with predefined dictionaries for face and signal recognition. In [5], dictionaries are learned for a reconstruction task, and the sparse decompositions are then used a posteriori within a classifier. In [6], a discriminative method is introduced for various classification tasks, learning one dictionary per class; the classification process itself is based on the corresponding reconstruction error, and does not exploit the actual decomposition coefficients. In [7], a generative model for document representation is learned at the same time as the parameters of a deep network structure. The framework we present in this paper extends these approaches by learning simultaneously a single shared dictionary as well as multiple models for different signal classes in a mixed generative and discriminative formulation (see also [8], where a different discrimination term is added to the classical reconstructive one for supervised dictionary learning). Similar joint generative/discriminative frameworks have started to appear in probabilistic approaches to learning, e.g., [9, 10, 11, 12, 13, 14], but not, to the best of our knowledge, in the sparse dictionary learning framework. Section 2 presents the formulation and Section 3 its interpretation in term of probability and kernel frameworks. The optimization procedure is detailed in Section 4, and experimental results are presented in Section 5. 2 Supervised dictionary learning We present in this section the core of the proposed model. We start by describing how to perform sparse coding in a supervised fashion, then show how to simultaneously learn a discriminative/reconstructive dictionary and a classifier. 1 2.1 Supervised Sparse Coding In classical sparse coding tasks, one considers a signal x in Rn and a fixed dictionary D = [d1 , . . . , dk ] in Rn×k (allowing k > n, making the dictionary overcomplete). In this setting, sparse coding with an 1 regularization1 amounts to computing R (x, D) = min ||x - D||2 + 1 ||||1 . (1) 2 Rk It is well known in the statistics, optimization, and compressed sensing communities that the 1 penalty yields a sparse solution, very few non-zero coefficients in , [15], although there is no explicit analytic link between the value of 1 and the effective sparsity that this model yields. Other sparsity penalties using the 0 regularization2 can be used as well. Since it uses a proper norm, the 1 formulation of sparse coding is a convex problem, which makes the optimization tractable with algorithms such as those introduced in [16, 17], and has proven in our proposed framework to be more stable than its 0 counterpart, in the sense that the resulting decompositions are less sensitive to small perturbations of the input signal x. Note that sparse coding with an 0 penalty is an NP-hard problem and is often approximated using greedy algorithms. In this paper, we consider a different setting, where the signal may belong to any of p different classes. We model the signal x using a single shared dictionary D and a set of p decision functions gi (x, , ) (i = 1, . . . , p) acting on x and its sparse code over D. The function gi should be positive for any signal in class i and negative otherwise. The vector parametrizes the model and will be jointly learned with D. In the following, we will consider two kinds of models: T (i) linear in : gi (x, , ) = wi + bi , where = {wi Rk , bi R}p=1 , and the vectors wi i (i = 1, . . . , p) can be thought of as p linear models for the coefficients , with the scalars bi acting as biases; (ii) bilinear in x and : gi (x, , ) = xT Wi + bi , where = {Wi Rn×k , bi R}p=1 . Note i that the number of parameters in (ii) is greater than in (i), which allows for richer models. One can interpret Wi as a filter encoding the input signal x into a model for the coefficients , which has a role similar to the encoder in [18] but for a discriminative task. Let us define softmax discriminative cost functions as Ci (x1 , ..., xp ) = log( jp exj -xi ), =1 for i = 1, . . . , p. These are multiclass versions of the logistic function, enjoying properties similar to that of the hinge loss from the SVM literature, while being differentiable. Given some input signal x and fixed (for now) dictionary D and parameters , the supervised sparse coding problem for the class p can be defined as computing Si (x, D, ) = min Si (, x, D, ), (2) where Si (, x, D, ) = Ci ({gj (x, , )}p=1 ) + 0 ||x - D||2 + 1 ||||1 . (3) 2 j Note the explicit incorporation of the classification and discriminative component into sparse coding, in addition to the classical reconstructive term (see [8] for a different classification component). In turn, any solution to this problem provides a straightforward classification procedure, namely: i (x, D, ) = arg min Si (x, D, ). i=1,...,p (4) Compared with earlier work using one dictionary per class [6], this model has the advantage of letting multiple classes share some features, and uses the coefficients of the sparse representations as part of the classification procedure, thereby following the works from [3, 4, 5], but with learned representations optimized for the classification task similar to [8, 9]. As shown in Section 3, this formulation has a straightforward probabilistic interpretation, but let us first see how to learn the dictionary D and the parameters from training data. 2.2 SDL: Supervised Dictionary Learning Let us assume that we are given p sets of training data Ti , i = 1, . . . , p, such that all samples in Ti belong to class i. The most direct method for learning D and is to minimize with respect to these 1 2 P The 1 norm of a vector x of size n is defined as ||x||1 = n 1 |x[i]|. i= The 0 pseudo-norm of a vector x is the number of nonzeros coefficients of x. Note that it is not a norm. 2 j = 1, . . . , m D xj j yj W Figure 1: Graphical model for the proposed generative/discriminative learning framework. variables the mean value of Si , with an 2 regularization term to prevent overfitting: + ip j Si (xj , D, ) 2 || ||2 , s.t. i = 1, . . . , k , ||di ||2 1. min 2 D, = 1 Ti (5) 2 Since the reconstruction errors ||x - D||2 are invariant to scaling simultaneously D by a scalar and by its inverse, constraining the 2 norm of columns of D prevents any transfer of energy between these two variables, which would have the effect of overcoming the sparsity penalty. Such a constraint is classical in sparse coding [2]. We will refer later to this model as SDL-G (supervised dictionary learning, generative). Nevertheless, since the classification procedure from Eq. (4) will compare the different residuals Si of a given signal for i = 1, . . . , p, a more discriminative approach is to not only make the Si small for signals with label i, as in (5), but also make the value of Sj greater than Si for j different than i, which is the purpose of the softmax function Ci . This leads to: + ip j min Ci ({Sl (xj , D, )}p=1 ) 2 || ||2 s.t. i = 1, . . . , k , ||di ||2 1. (6) 2 l D, =1 Ti As detailed below, this problem is more difficult to solve than Eq. (5), and therefore we adopt instead a mixed formulation between the minimization of the generative Eq. (5) and its discriminative version (6), [12]--that is, + ip j µCi ({Sl (xj , D, )}p=1 ) + (1 - µ)Si (xj , D, ) 2 || ||2 s.t. i, ||di ||2 1, min 2 l D, =1 Ti (7) where µ controls the trade-off between reconstruction from Eq. (5) and discrimination from Eq. (6). This is the proposed generative/discriminative model for sparse signal representation and classification from learned dictionary D and model . We will refer to this mixed model as SDL-D, (supervised dictionary learning, discriminative). Before presenting the proposed optimization procedure, we provide below two interpretations of the linear and bilinear versions of our formulation in terms of a probabilistic graphical model and a kernel. 3 3.1 Interpreting the model A probabilistic interpretation of the linear model Let us first construct a graphical model which gives a probabilistic interpretation to the training and classification criteria given above when using a linear model with zero bias (no constant term) on T the coefficients--that is, gi (x, , ) = wi . This model consists of the following components (Figure 1): · The matrices D and W are parameters of the problem, with a Gaussian prior on W, p(W) k 2 2 e-2 ||W||2 , and on the columns of D, p(D) l=1 e-l ||dl ||2 , where the l 's are the Gaussian parameters. All the dl 's are considered independent of each other. · The coefficients j are latent variables with a Laplace prior, p(j ) e-1 ||j ||1 . · The signals xj are generated according to a Gaussian probability distribution conditioned on D 2 and j , p(xj |j , D) e-0 ||xj -Dj ||2 . All the xj 's are considered independent from each other. · The labels yj are generated according to a probability distribution conditioned on W and j , p T T and given by p(yj = i|j , W) = e-Wi j / l=1 e-Wl j . Given D and W, all the triplets (j , xj , yj ) are independent. 3 What is commonly called "generative training" in the literature (e.g., [11, 12]), amounts to finding the maximum likelihood for D and W according to the joint distribution p({xj , yj }m 1 , D, W), j= where the xj 's and the yj 's are respectively the training signals and their labels. It can easily be shown (details omitted due to space limitations) that there is an equivalence between this generative training and our formulation in Eq. (5) under MAP approximations.3 Although joint generative modeling of x and y through a shared representation, e.g., [9], has shown great promise, we show in this paper that a more discriminative approach is desirable. "Discriminative training" is slightly m different and amounts to maximizing p({yj }m 1 , D, W|{xj }j =1 ) with respect to D and W: Given j= some input data, one finds the best parameters that will predict the labels of the data. The same kind of MAP approximation relates this discriminative training formulation to the discriminative model of Eq. (6) (again, details omitted due to space limitations). The mixed approach from Eq. (7) is a classical trade-off between generative and discriminative (e.g., [11, 12]), where generative components are often added to discriminative frameworks to add robustness, e.g., to noise and occlusions (see examples of this for the model in [8]). 3.2 A kernel interpretation of the bilinear model Our bilinear model with gi (x, , ) = xT Wi + bi does not admit a straightforward probabilistic interpretation. On the other hand, it can easily be interpreted in terms of kernels: Given two signals x1 and x2 , with coefficients 1 and 2 , using the kernel K (x1 , x2 ) = T 2 xT x2 in a logistic 1 1 regression classifier amounts to finding a decision function of the same form as (ii). It is a product of two linear kernels, one on the 's and one on the input signals x. Interestingly, Raina et al. [5] learn a dictionary adapted to reconstruction on a training set, then train an SVM a posteriori on the decomposition coefficients . They derive and use a Fisher kernel, which can be written as K (x1 , x2 ) = T 2 rT r2 in this setting, where the r's are the residuals of the decompositions. 1 1 Experimentally, we have observed that the kernel K , where the signals x replace the residuals r, generally yields a level of performance similar to K , and often actually does better when the number of training samples is small or the data are noisy. 4 Optimization procedure which is not jointly convex in (D, ), but convex with respect to each unknown when the other one is fixed. This is why block coordinate descent on D and performs reasonably well [1, 5, 19], although not necessarily providing the global optimum. Training when µ = 0 (generative case), i.e., from Eq. (5), enjoys similar properties and can be addressed with the same optimization procedure. Equation (5) can be rewritten as: + ip j Si (xj , j , D, ) 2 || ||2 , s.t. i = 1, . . . , k , ||di ||2 1. (9) min 2 D, , =1 Ti Block coordinate descent consists therefore of iterating between supervised sparse coding, where D and are fixed and one optimizes with respect to the 's and supervised dictionary update, where the coefficients j 's are fixed, but D and are updated. Details on how to solve these two problems are given in Section 4.1 and 4.2. The discriminative version of SDL from Eq. (6) is more problematic. The minimization of the term Ci ({Sl (j l , xj , D, )}p=1 ) with respect to D and when the j l 's are fixed, is not convex in l general, and does not necessarily decrease the first term of Eq. (6), i.e., Ci ({Sl (xj , D, )}p=1 ). To l reach a local minimum for this difficult problem, we have chosen a continuation method, starting from the generative case and ending with the discriminative one as in [6]. The algorithm is presented on Figure 2, and details on the hyperparameters' settings are given in Section 5. 4.1 Supervised sparse coding The supervised sparse coding problem from Eq. (10) (D and are fixed in this step), amounts to minimizing a convex function under an 1 penalty. The fixed-point continuation method (FPC) from 3 We are also investigating how to properly estimate D by marginalizing over instead of maximizing with respect to that parameter. Classical dictionary learning techniques (e.g., [1, 5, 19]), address the problem of learning a reconstructive dictionary D in Rn×k well adapted to a training set T as j min ||xj - Dj ||2 + 1 ||j ||1 , (8) 2 D, T 4 Input: p (number of classes); n (signal dimensions); {Ti }p=1 (training signals); k (size of the i dictionary); 0 , 1 , 2 (parameters); 0 µ1 µ2 . . . µm 1 (increasing sequence); Output: D Rn×k (dictionary); (parameters). Initialization: Set D to a random Gaussian matrix. Set to zero. Loop: For µ = µ1 , . . . , µm , Loop: Repeat until convergence (or a fixed number of iterations), · Supervised sparse coding: Compute, for all i = 1, . . . , p, all j in Ti , and all l = 1, . . . , p, l = arg min Sl (, xj , D, ). (10) j Rk · Dictionary update: Solve, under the constraint ||dl || 1 for all l = 1, . . . , k + ip j 2 2 || ||2 . (11) µCi ({Sl (j l , xj , D, )}p=1 ) + (1 - µ)Si (i , xj , D, ) min j l D, =1 Ti Figure 2: SDL: Supervised dictionary learning algorithm. [17] achieves good results in terms of convergence speed for this class of problems. For our specific problem, denoting by f the convex function to minimize, this method only requires f and a bound on the spectral norm of its Hessian Hf . Since the we have chosen models gi in Eq. (10) which are linear in , there exists, for each signal x to be sparsely represented, a matrix A in Rk×p and a vector b in Rp such that f () = Ci (AT + b) + 0 ||x - D||2 , 2 f () = ACi (AT + b) - 20 DT (x - D), and it can be shown that, if ||U||2 denotes the spectral norm of a matrix U (which is the magnitude 1 of its largest eigenvalue), then ||Hf ||2 (1 - p )||AT A||2 + 20 ||DT D||2 . In the case where p = 2 2 T T (only two classes), we can obtain a tighter bound, ||H ()|| e-C1 (A )-C2 (A ) ||a - a ||2 + f 2 2 20 ||DT D||2 , where a1 and a2 are the first and second columns of A. 4.2 Dictionary update 12 (13) j l = µCi ({Sm (m , xj , D, )}p =1 )[l] + (1 - µ)1l=i . j m T Partial derivatives when using our model with the bilinear models gi (x, , ) = x Wi + bi are not given in this paper because of space limitations. where The problem of updating D and in Eq. (11) is not convex in general (except when µ is close to 0), but a local minimum can be obtained using projected gradient descent (as in the general literature on dictionary learning, this local minimum has experimentally been found to be good enough for our formulation). Denoting E (D, ) the function we want to minimize in Eq. (11), we just need the partial derivatives of E with respect to D and the parameters . Details when using the linear model T for the 's, gi (x, , ) = wi + bi , and = {W Rk×p , b Rp }, are lp ip j , E T = -20 j l (xj - Dl )j l j D = 1 Ti = 1 E lp ip j = j l l ClT (WT l + b), (12) j j W = 1 Ti = 1 E lp ip j = j l Cl (WT l + b), b j =1 Ti =1 5 Experimental validation We compare in this section a reconstructive approach, dubbed REC, which consists of learning a reconstructive dictionary D as in [5] and then learning the parameters a posteriori; SDL with generative training (dubbed SDL-G); and SDL with discriminative learning (dubbed SDL-D). We also compare the performance of the linear (L) and bilinear (BL) models. 5 MNIST USPS REC L 4.33 6.83 SDL-G L 3.56 6.67 SDL-D L 1.05 3.54 REC BL 3.41 4.38 k-NN, 2 5.0 5.2 SVM-Gauss 1.4 4.2 Table 1: Error rates on MNIST and USPS datasets in percents from the REC, SDL-G L and SDL-D L approaches, compared with k-nearest neighbor and SVM with a Gaussian kernel [20]. Before presenting experimental results, let us briefly discuss the choice of the five model parameters 0 , 1 , 2 , µ and k (size of the dictionary). Tuning all of them using cross-validation is cumbersome and unnecessary since some simple choices can be made, some of which can be done sequentially. 1 We define first the sparsity parameter = 0 , which dictates how sparse the decompositions are. When the input data points have unit 2 norm, choosing = 0.15 was empirically found to be a good choice. For reconstructive tasks, a typical value often used in the literature (e.g., [19]) is k = 256 Nevertheless, for discriminative tasks, increasing the number of parameters is likely to allow overfitting, and smaller values like k = 64 or k = 32 are preferred. The scalar 2 is a regularization parameter for preventing the model to overfit the input data. As in logistic regression or support vector machines, this parameter is crucial when the number of training samples is small. Performing cross validation with the fast method REC quickly provides a reasonable value for this parameter, which can be used afterward for SDL-G or SDL-D. Once , k and 2 are chosen, let us see how to find 0 . 0 plays the important role of controlling the trade-off between reconstruction and discrimination in Eq. (3). First, we perform cross-validation for a few iterations with µ = 0 to find a good value for SDL-G. Then, a scale factor making the m o Si 's discriminative for µ > 0 can be chosen during the optip izatij n process: Given a set of Si 's, Ci ({ Sl (xj , D, W)}). We one can compute a scale factor such that = arg min i=1 Ti therefore propose the following strategy, which has proven to be efficient during our experiments: Starting from small values for 0 and a fixed , we apply the algorithm in Figure 2, and after a supervised sparse coding step, we compute the best scale factor , and replace 0 and 1 by 0 and 1 . Typically, applying this procedure during the first 10 iterations has proven to lead to reasonable values for these parameters. Since we are following a continuation path starting from µ = 0 to µ = 1, the optimal value of µ is found along the path by measuring the classification performance of the model on a validation set during the optimization. 5.1 Digits recognition In this section, we present experiments on the popular MNIST [20] and USPS handwritten digit datasets. MNIST is composed of 70 000 images of 28 × 28 pixels, 60 000 for training, 10 000 for testing, each of them containing a handwritten digit. USPS is composed of 7291 training images and 2007 test images. As it is often done in classification, we have chosen to learn pairwise binary classifiers, one for each pair of digits. Although we have presented a multiclass framework, pairwise binary classifiers have proven to offer a slightly better performance in practice. Five-fold cross validation has been performed to find the best pair (k , ). The tested values for k are {24, 32, 48, 64, 96}, and for , {0.13, 0.14, 0.15, 0.16, 0.17}. Then, we have kept the three best pairs of parameters and used them to train three sets of pairwise classifiers. For a given patch x, the test procedure consists of selecting the class which receives the most votes from the pairwise classifiers. All the other parameters are obtained using the procedure explained above. Classification results are presented on Table 1 when using the linear model. We see that for the linear model L, SDL-D L performs the best. REC BL offers a larger feature space and performs better than REC L. Nevertheless, we have observed no gain by using SDL-G BL or SDL-D BL instead of REC BL. Since the linear model is already performing very well, one side effect of using BL instead of L is to increase the number of free parameters and thus to cause overfitting. Note that the best error rates published on these datasets (without any modification of the training set) are 0.60% [18] for MNIST and 2.4% [21] for USPS, using methods tailored to these tasks, whereas ours is generic and has not been tuned to the handwritten digit classification domain. The purpose of our second experiment is not to measure the raw performance of our algorithm, but to answer the question "are the obtained dictionaries D discriminative per se or is the pair (D, ) discriminative?". To do so, we have trained on the USPS dataset 10 binary classifiers, one per digit in a one vs all fashion on the training set. For a given value of µ, we obtain 10 dictionaries D and 10 sets of parameters , learned by the SDL-D L model. 6 M 300 1500 3000 6000 15000 30000 REC L 48.84 46.8 45.17 45.71 47.54 47.28 SDL-G L 47.34 46.3 45.1 43.68 46.15 45.1 SDL-D L 44.84 42 40.6 39.77 38.99 38.3 REC BL 26.34 22.7 21.99 19.77 18.2 18.99 SDL-G BL 26.34 22.3 21.22 18.75 17.26 16.84 SDL-D BL 26.34 22.3 21.22 18.61 15.48 14.26 Gain 0% 2% 4% 6% 15% 25% Table 2: Error rates for the texture classification task using various frameworks and sizes M of training set. The last column indicates the gain between the error rate of REC BL and SDL-D BL. 2.5 2.0 1.5 1.0 0.5 (a) REC, MNIST (b) SDL-D, MNIST 0 0 0.2 0.4 0.6 0.8 1.0 Figure 3: On the left, a reconstructive and a discriminative dictionary. On the right, average error rate in percents obtained by our dictionaries learned in a discriminative framework (SDL-D L) for various values of µ, when used in used at test time in a reconstructive framework (REC-L). To evaluate the discriminative power of the dictionaries D, we discard the learned parameters and use the dictionaries as if they had been learned in a reconstructive REC model: For each dictionary, we decompose each image from the training set by solving the simple sparse reconstruction problem from Eq. (1) instead of using supervised sparse coding. This provides us with some coefficients , which we use as features in a linear SVM. Repeating the sparse decomposition procedure on the test set permits us to evaluate the performance of these learned linear SVM. We plot the average error rate of these classifiers on Figure 3 for each value of µ. We see that using the dictionaries obtained with discrimative learning (µ > 0, SDL-D L) dramatically improves the performance of the basic linear classifier learned a posteriori on the 's, showing that our learned dictionaries are discriminative per se. Figure 3 shows a dictionary adapted to the reconstruction of the MNIST dataset and a discriminative one, adapted to "9 vs all". 5.2 Texture classification In the digit recognition task, our BL bilinear framework did not perform better than L and we believe that one of the main reasons is due to the simplicity of the task, where a linear model is rich enough. The purpose of our next experiment is to answer the question "When is BL worth using?". We have chosen to consider two texture images from the Brodatz dataset, presented in Figure 4, and to build two classes, composed of 12 × 12 patches taken from these two textures. We have compared the classification performance of all our methods, including BL, for a dictionary of size k = 64 and = 0.15. The training set was composed of patches from the left half of each texture and the test sets of patches from the right half, so that there is no overlap between them in the training and test set. Error rates are reported for varying sizes of the training set. This experiment shows that in some cases, the linear model completely fails and BL is necessary. Discrimination helps especially when the size of the training set is particularly valuable for large training sets. Note that we did not perform any cross-validation to optimize the parameters k and for this experiment. Dictionaries obtained with REC and SDL-D BL are presented in Figure 4. Note that though they are visually quite similar, they lead to very different performance. 6 Conclusion We have introduced in this paper a discriminative approach to supervised dictionary learning that effectively exploits the corresponding sparse signal decompositions in image classification tasks, and affords an effective method for learning a shared dictionary and multiple (linear or bilinear) models. Future work will be devoted to adapting the proposed framework to shift-invariant models that are standard in image processing tasks, but not readily generalized to the sparse dictionary learning setting. We are also investigating extensions to unsupervised and semi-supervised learning and applications into natural image classification. 7 (a) Texture 1 (b) Texture 2 (c) REC (d) SDL-D BL Figure 4: Left: test textures. Right: reconstructive and discriminative dictionaries Acknowledgments This paper was supported in part by ANR under grant MGA. Guillermo Sapiro would like to thank Fernando Rodriguez for insights into the learning of discriminatory sparsity patterns. His work is partially supported by NSF, NGA, ONR, ARO, and DARPA. References [1] B. A. Olshausen and D. J. Field. Sparse coding with an overcomplete basis set: A strategy employed by v1? Vision Research, 37, 1997. [2] M. Elad and M. Aharon. Image denoising via sparse and redundant representations over learned dictionaries. IEEE Trans. IP, 54(12), 2006. [3] K. Huang and S. Aviyente. Sparse representation for signal classification. In NIPS, 2006. [4] J. Wright, A. Y. Yang, A. Ganesh, S. Sastry, and Y. Ma. Robust face recognition via sparse representation. In PAMI, 2008. to appear. [5] R. Raina, A. Battle, H. Lee, B. Packer, and A. Y. Ng. Self-taught learning: transfer learning from unlabeled data. In ICML, 2007. [6] J. Mairal, F. Bach, J. Ponce, G. Sapiro, and A. Zisserman. Learning discriminative dictionaries for local image analysis. In CVPR, 2008. [7] M. Ranzato and M. Szummer. Semi-supervised learning of compact document representations with deep networks. In ICML, 2008. [8] F. Rodriguez and G. Sapiro. Sparse representations for image classification: Learning discriminative and reconstructive non-parametric dictionaries. IMA Preprint 2213, 2007. [9] D. Blei and J. McAuliffe. Supervised topic models. In NIPS, 2007. [10] A. Holub and P. Perona. A discriminative framework for modeling object classes. In CVPR, 2005. [11] J.A. Lasserre, C.M. Bishop, and T.P. Minka. Principled hybrids of generative and discriminative models. In CVPR, 2006. [12] R. Raina, Y. Shen, A. Y. Ng, and A. McCallum. Classification with hybrid generative/discriminative models. In NIPS, 2004. [13] R. R. Salakhutdinov and G. E. Hinton. Learning a non-linear embedding by preserving class neighbourhood structure. In AI and Statistics, 2007. [14] J. Winn, A. Criminisi, and T. Minka. Object categorization by learned universal visual dictionary. In ICCV, 2005. [15] D. L. Donoho. Compressive sampling. IEEE Trans. IT, 52(4), 2006. [16] B. Efron, T. Hastie, I. Johnstone, and R. Tibshirani. Least angle regression. Ann. Stat., 32(2), 2004. [17] E. T. Hale, W. Yin, and Y. Zhang. A fixed-point continuation method for l1-regularized minimization with applications to compressed sensing. CAAM Tech Report TR07-07, 2007. [18] M. Ranzato, C. Poultney, S. Chopra, and Y. LeCun. Efficient learning of sparse representations with an energy-based model. In NIPS, 2006. [19] M. Aharon, M. Elad, and A. M. Bruckstein. The K-SVD: An algorithm for designing of overcomplete dictionaries for sparse representations. IEEE Trans. SP, 54(11), 2006. [20] Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition. Proc. of the IEEE, 86(11), 1998. [21] B. Haasdonk and D. Keysers. Tangent distant kernels for support vector machines. In ICPR, 2002. 8