Matrix Sparsity Structured Sparsity

De
Publié par

Matrix Sparsity - Structured Sparsity Francis Bach - Guillaume Obozinski Willow group - INRIA - ENS - Paris ECML 2010, Barcelona, September 20th Sparsity tutorial II, ECML 2010, Barcelona 1/69

  • multivariate problems

  • sparse structured

  • sparsity tutorial

  • variate output design

  • structured sparsity

  • given nx

  • matrix noise

  • vector wk ?


Publié le : mardi 19 juin 2012
Lecture(s) : 17
Source : di.ens.fr
Nombre de pages : 90
Voir plus Voir moins
Matrix
Sparsity
-
Structured
Sparsity
Francis Bach - Guillaume Obozinski
Willow group - INRIA - ENS - Paris
ECML 2010, Barcelona, September 20th
Sparsity tutorial II, ECML 2010, Barcelona
1/69
Outline
1
2
3
Matrix Sparsity Learning on matrices Forms of sparsity for matrices Multivariate learning and row sparsity Sparse spectrum Sparse Principal Component Analysis Dictionary learning, image denoising and inpainting
Structured sparsity Overview Sparsity patterns stable by union Sparse Structured PCA Hierarchical Dictionary Learning
Conclusion
Sparsity tutorial II, ECML 2010, Barcelona
2/69
Learning on matrices -Collaborative Filtering (CF)
GivennX“movies”x∈ XandnY“customers”y∈ Y, predict th “rating”z(x,y)∈ Zof customeryfor moviex e Training data: largenX×nYincomplete matrixZthat describes the known ratings of some customers for some movies Goal: complete the matrix.
Sparsity tutorial II, ECML 2010, Barcelona
3/69
Learning on matrices -Multivariate problems
Multivariate linear regression
Sparsity tutorial II, ECML 2010, Barcelona
4/69
Learning on matrices -Multivariate problems
Multivariate linear regression
Multiclass classification n1` mWinXn(w1>x i=1
(i) (i) , . . . ,wK>x,y(i))
with y(i)∈ {0,1}K One parameter vectorwkRpper class ` multiclass logistic lossis e.g. the
Sparsity tutorial II, ECML 2010, Barcelona
4/69
Learning on matrices -Multi-task learning
kprediction tasks on same covariatesxp Each model parameterized by:wkR,
Rp 1kK
Sparsity tutorial II, ECML 2010, Barcelona
5/69
Learning on matrices -Multi-task learning
kprediction tasks on same covariatesxRp Each model parameterized by:wkRp,1n Empirical risks:Lk(wk) =n1X`k(wk>xik,yik) i=1
kK
Sparsity tutorial II, ECML 2010, Barcelona
5/69
Learning on matrices -Multi-task learning
kprediction tasks on same covariatesxRp Each model parameterized by:wkRp,1kK Empirical risks:Lk(wk 1) =nnX`k(wk>xik,yik) i=1 All parameters form a matrix: w11. . . W= [w1, . . . ,wK] =.wjk. w1 p. .
w1Kw.pK
 
w1 =Rp×K w.p
Sparsity tutorial II, ECML 2010, Barcelona
5/69
Learning on matrices -Multi-task learning
kprediction tasks on same covariatesxRp Each model parameterized by:wkRp,1kK Empirical risk 1nX`k(wk>xik,yik) s:Lk(wk) =n i=1
All parameters form a matrix: W= [w1, . . . ,wK] =ww.p111..w..jk..ww.1KpK=ww.1Rp×K p Many applications Multi-category classification (one task per class) (Amit et al., 2007) Share parameters between various tasks similar to fixed effect/random effect models (Raudenbush and Bryk, 2002)
Sparsity tutorial II, ECML 2010, Barcelona
5/69
Learning on matrices -Image denoising
Simultaneously denoise all patches of a given image Example from Mairal et al. (2009b)
Sparsity tutorial II, ECML 2010, Barcelona
6/69
Outline
1
2
3
Matrix Sparsity Learning on matrices Forms of sparsity for matrices Multivariate learning and row sparsity Sparse spectrum Sparse Principal Component Analysis Dictionary learning, image denoising and inpainting
Structured sparsity Overview Sparsity patterns stable by union Sparse Structured PCA Hierarchical Dictionary Learning
Conclusion
Sparsity tutorial II, ECML 2010, Barcelona
7/69
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.