14 Pages
English

Task Driven Dictionary Learning Julien Mairal Francis Bach and Jean Ponce Fellow IEEE

Gain access to the library to view online
Learn more

Description

Niveau: Supérieur, Doctorat, Bac+8
Task-Driven Dictionary Learning Julien Mairal, Francis Bach, and Jean Ponce, Fellow, IEEE Abstract—Modeling data with linear combinations of a few elements from a learned dictionary has been the focus of much recent research in machine learning, neuroscience, and signal processing. For signals such as natural images that admit such sparse representations, it is now well established that these models are well suited to restoration tasks. In this context, learning the dictionary amounts to solving a large-scale matrix factorization problem, which can be done efficiently with classical optimization tools. The same approach has also been used for learning features from data for other purposes, e.g., image classification, but tuning the dictionary in a supervised way for these tasks has proven to be more difficult. In this paper, we present a general formulation for supervised dictionary learning adapted to a wide variety of tasks, and present an efficient algorithm for solving the corresponding optimization problem. Experiments on handwritten digit classification, digital art identification, nonlinear inverse image problems, and compressed sensing demonstrate that our approach is effective in large-scale settings, and is well suited to supervised and semi-supervised classification, as well as regression tasks for data that admit sparse representations. Index Terms—Basis pursuit, Lasso, dictionary learning, matrix factorization, semi-supervised learning, compressed sensing. Ç 1 INTRODUCTION THE linear decomposition of data using a few elementsfrom a learned dictionary instead of a predefined one— based on wavelets [1] for example—has recently led to state-of-the-art results in numerous low-

  • signal processing

  • semi-supervised learning

  • also been used

  • learning has

  • can easily

  • unlike classical

  • classification tasks

  • learning

  • task-driven dictionary

  • driven dictionary


Subjects

Informations

Published by
Reads 45
Language English
Document size 1 MB
IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 34, NO. 4, APRIL 2012
Task-Driven Dictionary Learning Julien Mairal, Francis Bach, and Jean Ponce, Fellow , IEEE
Abstract —Modeling data with linear combinations of a few elements from a learned dictionary has been the focus of much recent research in machine learning, neuroscience, and signal processing. For signals such as natural images that admit such sparse representations, it is now well established that these models are well suited to restoration tasks. In this context, learning the dictionary amounts to solving a large-scale matrix factorization problem, which can be done efficiently with classical optimization tools. The same approach has also been used for learning features from data for other purposes, e.g., image classification, but tuning the dictionary in a supervised way for these tasks has proven to be more difficult. In this paper, we present a general formulation for supervised dictionary learning adapted to a wide variety of tasks, and present an efficient algorithm for solving the corresponding optimization problem. Experiments on handwritten digit classification, digital art identification, nonlinear inverse image problems, and compressed sensing demonstrate that our approach is effective in large-scale settings, and is well suited to supervised and semi-supervised classification, as well as regression tasks for data that admit sparse representations.
Index Terms —Basis pursuit, Lasso, dictionary learning, matrix factorization, semi-supervised learning, compressed sensing. Ç
791
1 I NTRODUCTION T HE lineardecompositionofdatausingafewelementsingTihsiswcelllasasdicaaplteddattao-rdericvoennstraupcptiroonacthastkossdiuccthioansarreystloerairnng-from a learned dictionary instead of a predefined one— based on wavelets [1] for example—has recently led to a noisy signal. These dictionaries, which are good at state-of-the-art results in numerous low-level signal proces- reconstructing clean signals but bad at reconstructing noise, sing tasks such as image denoising [2], [3], [4], audio have indeed led to state-of-the-art denoising algorithms [2], processing [5], [6], as well as classification tasks [7], [8], [9], [3], [4]. Unsupervised dictionary learning has also been [10], [11], [12]. Unlike decompositions based on principal ure s nal reconstruction, componentanalysis(PCA)anditsvariants,thesesparsesuuscehdfaosrcoltahsesirficpautriopnose[5s],th[a7]n,p[11],[i1g2],[15],butrecent models do not impose that the dictionary elements be works have shown that better results can be obtained when orthogonal, allowing more flexibility to adapt the repre- the dictionary is tuned to the specific task (and not just data) sentation to the data. it is intended for. Duarte-Carvajalino and Sapiro [16] have, Consider a vector x in IR m . We say that it admits a sparse dictionaries for com d approximation over a dictionary D ¼ ½ d 1 ; . . . ; d p in IR m p sfoernsiinnsgta,nacne,dpirnop[o8]s,ed[9t],ol[e1a0r],ndictionariesarelearpnreedssfeor when one can find a linear combination of a “few” columns signal classification. In this paper, we will refer to this type from D that is “close” to the vector x . Experiments have of approach as task-driven dictionary learning. shown that modeling signals with such sparse decomposi- Whereas purely data-driven dictionary learning has been tions ( sparse coding ) is very effective in many signal processing shown to be equivalent to a large-scale matrix factorization applications [13]. For natural images, predefined dictionaries problem that can be effectively addressed with several based on various types of wavelets [1] have been used for this methods [14], [17], [18], [19], its task-driven counterpart has task.InitiallyintroducedbyOlshausenandField[14]forprovreanltoffbiceiemntucfhrammoerewodrifkficfourlttvoaroioptuismitzaes.k-Pdrreisveenntindgica-modeling the spatial receptive fields of simple cells in the gene e mammalianvisualcortex,theideaoflearningthedictionarytEionnartyhloeuagrnhiintgisprdoifbfleeremnstifsrothmeemxiasitnintgopmicacohfintheilseapranpienrg. from data instead of using off-the-shelf bases has been shown ve tosignificantlyimprovesignalreconstruction[2].appFrooraicnhsetsa,nitces,hBalreeisesitmaill.ar[i2t0ie]shwaivtehpmraonpyosoefdthtoeml.earna latent topic model intended for document classification. In a . J. Mairal is with the Department of Statistics, University of California, 301 different context, Argyriou et al. [21] introduced a convex . EF.vaBnaschHisallw,itBhertkheeleIyN,RCIAA-9S4ie7r2r0a-3P8ro6j0e.ctE-Tmeaaiml:,jLualbieorna@tsitraet.dbeirnkfeolremy.aetdiqu.ue formulation for multitask classification problems where an de l’Ecole Normale S e´rieu o orthogonal linear transform of input features is jointly dItalie,75013Paris,upFrancer.eE(-CmNaRil:S/fEraNnSci/Is.NbaRcIhA@iUnrMiaR.fr8.548)23avenue learned with a classifier. Learning compact features has also . J8.5P4o8)nceanisdwtihtehIthNeRIEcAo-leWiNlloorwmaPleroSjeucpt-e´Trieeaumr,e(2C3NaRvSe/nEueNSd/IItNalRiIe,A7U50M1R3 been addressed in the literature of neural networks, with nce@ens. . restricted Boltzmann machines (RBMs) and convolutional MaPnaursicsr,ipFtrarneccee.ivEe-dm2ai7l:Sjeeapnt..p2o010;revifsred4June2011;accepted13July neural networks, for example (see [22], [23], [24], [25], [26] 2011; published online 28 July 2011. and references therein). Interestingly, the question of Recommended for acceptance by J. Winn. learning the data representation in an unsupervised or tFpoarmiinf@ocrommaptiuotner.oonrg,obatnaidnirnefgerreenpcreinItEsEoEfCtShisLoagrtNiculem,bpelreasesende-mailto: supervised way has also been investigated for these TPAMI-2010-09-0740. approaches. For instance, a supervised topic model is Digital Object Identifier no. 10.1109/TPAMI.2011.156. proposed in [27] and tuning latent data representations 0162-8828/12/$31.00 2012 IEEE Published by the IEEE Computer Society