Cet ouvrage et des milliers d'autres font partie de la bibliothèque YouScribe
Obtenez un accès la bibliothèque pour les lire en ligne
En savoir plus

Partagez cette publication

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