Sparse methods for machine learning

Francis Bach

Description

Sparse methods for machine learning Francis Bach Willow project, INRIA - Ecole Normale Superieure CVPR Tutorial - June 2010 Special thanks to R. Jenatton, G. Obozinski

• norms


• supervised learning


• multi-task learning


• sparsity- inducing norms


• structured sparse


• ?1 -norm ?w?1


• sparse methods


• norm

Sujets

• Supervised learning
• Multi-task learning

Informations

• Publié par: pefav
• Nombre de lectures: 23
• Langue: English

Extrait

Sparse methods for machine learning

Francis Bach

Willowproject,INRIA-EcoleNormaleSup´erieure

CVPR Tutorial - June 2010 Special thanks to R. Jenatton, G. Obozinski

Sparse methods for machine learning Outline

•Sparse linear estimation with theℓ 1 -norm

–Lasso –Important theoretical results

•Structured sparse methods on vectors

–Groups of features / Multiple kernel learning

•Sparse methods on matrices

–Multi-task learning –Matrix factorization (low-rank, sparse PCA, dictionary learning)

Supervised learning and regularization

•Data:x i ∈ X,y i ∈ Y,i= 1     n

•Minimize with respect to functionf:X → Y:

n X ℓ(y i  f(x i )) i=1 Error on data

Loss & function space ?

•Two theoretical/algorithmic issues:

1. Loss 2.Function space / norm

+ +

λ 2 kfk 2 Regularization

Norm ?

Regularizations

• overfitting avoidMain goal:

•Two main lines of work:

1.

EuclideanandHilbertiannorms (i.e.,ℓ 2 -norms) –Possibility of non linear predictors –Non parametric supervised learning and kernel methods –Well developped theory and algorithms (see, e.g., Wahba, 1990; Sch¨olkopfandSmola,2001;Shawe-TaylorandCristianini,2004)

Regularizations

•Main goal: avoid overfitting

•Two main lines of work:

1.

EuclideanandHilbertiannorms (i.e.,ℓ 2 -norms) –Possibility of non linear predictors –Non parametric supervised learning and kernel methods –Well developped theory and algorithms (see, e.g., Wahba, 1990; Scho¨lkopfandSmola,2001;Shawe-TaylorandCristianini,2004) 2.ngciti-yniudSapsrnorms –restricted to linear predictors on vectorsUsually f(x) =w ⊤ x –Main example:ℓ 1 -normkwk 1 = P p i=1 |w i | –Perform model selection as well as regularization –Theory and algorithms “in the making”