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

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

Sujets

• Analysis
• Signal processing
• Semi-supervised learning
• Learning

Informations

• Publié par: profil-zyak-2012
• Nombre de lectures: 45
• Langue: English
• Poids de l'ouvrage: 1 Mo

Extrait

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 lineardecompositionofdatausingafewelements ing T i h s is w c e l ll as a s d ic a a p l te d d at t a o - r d e ri c v o e n n str a u p c p ti r o o n ac t h as t k o ss di u c c t h io a n s a r r e y st l o e r a i r n n g - 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,thesesparse s u u s c e h df a o s r c o l t a h s e si r fic p a u t r io p n ose [5 s ], th [ a 7] n , p [11],[ i 1 g 2],[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 s fo e r ns i i n n s g ta , n a c n e, d p i r n op [ o 8] s , ed [9 t ], ol [ e 1 a 0 r ], n dictionariesarelear p n r e e d ss f e or 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]for prov r e a n l to ff b ic e ie m nt uc f h ra m m o e re wo d r if k fic fo u r ltt v o ar o io pt u i s mi t z a e s . k- P d r r e i s v e e n n tin d g ic a - modeling the spatial receptive fields of simple cells in the  gene e mammalianvisualcortex,theideaoflearningthedictionary t E ion n ar t y h l o e u a g rn h i i n t g is pr d o if b f l e e re m n s t i f s ro th m e e m xi a s i t n in t g op m ic ac o h f in th e i l s ea p r a n p i e n r g . from data instead of using off-the-shelf bases has been shown  ve tosignificantlyimprovesignalreconstruction[2]. app F r o o r a i c n h s e t s a , n it ce s , h B a l r e e i s e si t m a i l l . ar [ i 2 t 0 ie ] s h w a i v t e h p m r a o n p y os o e f d th to em l . 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 . E F. va B n a s ch H is all w , it B h er t k h e e le I y N , R C I A A- 9 S 4 ie 7 r 2 r 0 a -3 P 8 ro 6 j 0 e . ct E- T m ea ai m l: , j L u a l b ie or n a @ t s i t r a e t. d b ’ e i r n k f e o l r e m y. a e t d iq u. ue formulation for multitask classification problems where an de l’Ecole Normale S  e´rieu  o orthogonal linear transform of input features is jointly d’Italie,75013Paris, up France r . e E ( - C m N a R il: S/ f E ra N n S ci /I s. N ba R c I h A @i U nr M ia R .fr 8 . 548)23avenue learned with a classifier. Learning compact features has also . J 8 . 5 P 4 o 8) nce an is d w t i h t e h I th N e RI Ec A o - le Wi N ll o o r w ma P le ro S je u c p t- e ´ T ri e e a u m r , e( 2 C 3 N a R v S e / n E ue NS d / ’ I It N al R i I e, A 7 U 50 M 1 R 3 been addressed in the literature of neural networks, with nce@ens. . restricted Boltzmann machines (RBMs) and convolutional Ma P n a u r s i c s r , ip F t ra r n e c c e e . iv E e - d m 2 ai 7 l: S je e a p n t. .p 2 o 010;revi f s r ed4June2011;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 t F p o a r m i i nf @ o c r o m m a p ti u o t n er. o o n rg, ob a t n ai d ni r n ef g er r e e n p c r e in I t E s E o E f C t S his Lo a g rt N ic u le m , b p e l r easesende-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