Matrix Sparsity Structured Sparsity

Francis Bach - Guillaume

Description

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 ?

Informations

• Publié par: pefav
• Nombre de lectures: 17
• Poids de l'ouvrage: 11 Mo

Extrait

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)

Givenn X “movies”x∈ Xandn Y “customers”y∈ Y, predict th “rating”z(x,y)∈ Zof customeryfor moviex e Training data: largen X ×n Y incomplete 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 n 1 ` m W in X n (w 1 > x i=1

(i) (i) , . . . ,w K > x,y (i) )

with y (i) ∈ {0,1} K One parameter vectorw k ∈R p per 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 covariatesx∈ p Each model parameterized by:w k ∈R,

R p 1≤k≤K

Sparsity tutorial II, ECML 2010, Barcelona

5/69

Learning on matrices -Multi-task learning

kprediction tasks on same covariatesx∈R p Each model parameterized by:w k ∈R p ,1≤ n Empirical risks:L k (w k ) = n 1 X ` k (w k > x ik ,y ik ) i=1

k≤K

Sparsity tutorial II, ECML 2010, Barcelona

5/69

Learning on matrices -Multi-task learning

kprediction tasks on same covariatesx∈R p Each model parameterized by:w k ∈R p ,1≤k≤K Empirical risks:L k (w k  1 ) = n nX ` k (w k > x ik ,y ik ) i=1 All parameters form a matrix: w 11 . . . W= [w 1 , . . . ,w K ] =    .w jk . w 1 p . .

w 1 K  w . pK 

 

w 1 =   ∈R p×K w . p 

Sparsity tutorial II, ECML 2010, Barcelona

5/69

Learning on matrices -Multi-task learning

kprediction tasks on same covariatesx∈R p Each model parameterized by:w k ∈R p ,1≤k≤K Empirical risk  1 nX ` k (w k > x ik ,y ik ) s:L k (w k ) = n i=1

All parameters form a matrix: W= [w 1 , . . . ,w K ] =    w w . p 1 1 1 . . w . . jk . . w w . 1 K p K    =    w w . 1    ∈R p×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