Sparse Modeling

Theory, Algorithms and Applications

Irina Rish Genady Grabarnik

Computational Biology Center (CBC) Department of Math and CS
IBM T.J. Watson Research Center, NY CUNY, NY
Outline

„ Introduction

„ Sparse Linear Regression: Lasso

„ Sparse Signal Recovery and Lasso: Some Theory

„ Sparse Modeling: Beyond Lasso

„ Consistency-improving extensions

„ Beyond l1-regularization (l1/lq, Elastic Net, fused Lasso)

„ Beyond linear model (GLMs, MRFs)

„ Sparse Matrix Factorizations

„ Beyond variable-selection: variable construction

„ Summary and Open Issues

Schedule

„ 9:00-9:40
Introduction
Lasso

„ 9:40-10:20
Sparse signal recovery and Lasso: Some Theory

„ 10:20-10:30
Coffee Break

„ 10:30-11:45
Sparse Modeling Beyond Lasso
A Common Problem

Unknown
state of world X1 X2 X2
X3 X4 X5 Decoding:
Inference, learning
(Noisy) encoding
Y=f(X) x* = arg max P (x | y )
x

Observations Y1 Y2

Can we recover a high-dimensional X from a low-dimensional Y?

Yes, if:
X is structured; e.g., sparse (few Xi =/ 0 ) or compressible (few large Xi)
encoding preserves information about X

Examples:
Sparse signal recovery (compressed sensing, rare-event diagnosis)
Sparse model learning
Example 1: Diagnosis in Computer Networks

Probe (Beygelzimer, Kephart and Rish 2007)

4216 2

6 1 4 9

N links (possible bottlenecks)

3

X1 X2 X3 X4 X5 X6 vector X of
(unknown)
vector Y of
Y XY XZ X] Y[ Z[ [` link delays
end-to-end
probe delays Y1 [YX] 1 0 1 1 0 0
M probes

Y2 [ZX] 0 1 1 0 1 0
Y3 ZXY 1 1 0 0 0 0 Routing
Y4 XY[` 1 0 0 1 0 1 matrix A

„ Model: y = Ax + noise

„ Problem structure: X is nearly sparse - small number of large delays

„ Task: find bottlenecks (extremely slow links) using probes (M << N)

Recover sparse state (`signal’) X from noisy linear observations

Example 2: Sparse Model Learning from fMRI Data

„ Data: high-dimensional, small-sample

10,000 - 100,000 variables (voxels)
100s of samples (time points, or TRs)

„ Task: given fMRI, predict mental states

emotional: angry, happy, anxious, etc.
cognitive: reading a sentence vs viewing an image
mental disorders (schizophrenia, autism, etc.)

„ Issues:
Overfitting: can we learn a predictive model that generalizes well?
Interpretability: can we identify brain areas predictive of mental states?
fMRI image courtesy of fMRI Research Center @ Columbia University
Sparse Statistical Models: Prediction + Interpretability

Data Predictive Model

x - fMRI voxels,
y = f(x)
y - mental state
+ +
Small number + happy

of Predictive + - -
- - -
Variables ? sad

„ Sparsity variable selection model interpretability

„ Sparsity regularization less overfitting / better prediction

Sparse Linear Regression

y = Ax + noise

Measurements: fMRI data (“encoding’) Unknown

mental states, behavior, rows – samples (~500) parameters
tasks or stimuli Columns – voxels (~30,000) (‘signal’)

Find small number of most relevant voxels (brain areas)

fMRI activation image and time-course courtesy of Steve Smith, FMRIB

Sparse Recovery in a Nutshell

noiseless design
observations (measurement) sparse input
matrix

Can we recover a sparse input efficiently

from a small number of measurements?
Sparse Recovery in a Nutshell

M
N dimensions

K nonzeros

``Compressed Sensing Surprise’’:

Given random A (i.i.d. Gaussian entries), can be reconstructed
exactly (with high probability):

„ from just measurements

„ efficiently - by solving convex problem

(Ù linear program)
Sparse Recovery in a Nutshell

M
N dimensions

K nonzeros

In general, if A is ``good’’ (e.g., satisfies Restricted Isometry Property

with a proper constant), sparse can be reconstructed with M <<N
measurements by solving (linear program):
Sparse Recovery in a Nutshell

noise
observations noiseless design
observations (measurement)
matrix
sparse input

And what if there is noise in observations?

Sparse Recovery in a Nutshell

Still, can reconstruct the input accurately (in l2-sense), for A

satisfying RIP; just solve a noisy version of our l1-optimization:

(Basis Pursuit, aka Lasso)

Sparse Linear Regression vs Sparse Signal Recovery

„ Both solve the same optimization problem

„ Both share efficient algorithms and theoretical results

„ However, sparse learning setting is more challenging:

„ We do not design the “design” matrix, but rather deal with
the given data

„ Thus, nice matrix properties may not be satisfied

(and they are hard to test on a given matrix, anyway)

„ We don’t really know the ground truth (``signal”) – but

rather assume it is sparse (to interpret and to regularize)

„ Sparse learning includes a wide range of problems beyond

sparse linear regression (part 2 of this tutorial)
Outline

„ Introduction

„ Sparse Linear Regression: Lasso

„ Sparse Signal Recovery and Lasso: Some Theory

„ Sparse Modeling: Beyond Lasso

„ Consistency-improving extensions

„ Beyond l1-regularization (l1/lq, Elastic Net, fused Lasso)

„ Beyond linear model (GLMs, MRFs)

„ Sparse Matrix Factorizations

„ Beyond variable-selection: variable construction

„ Summary and Open Issues

Motivation: Variable Selection
Model Selection as Regularized Optimization
Bayesian Interpretation: MAP Estimation
Log-likelihood Losses: Examples
What is special about l1-norm? Sparsity + Computational Efficiency

lq-norm constraints for different values of q

Image courtesy of [Hastie, Friedman and Tibshirani, 2009]

 1

0.9
lambda = 2
0.8
lambda=1
lambda=0.5
0.7

0.6

0.5

0.4

0.3

0.2

0.1

0
−10 −8 −6 −4 −2 0 2 4 6 8 10
.
Lasso vs Ridge and Best-Subset in Case of Orthonormal Designs

hard thresholding shrinkage soft thresholding

Image courtesy of [Hastie, Friedman and Tibshirani, 2009]
Geometric View of LARS

Image courtesy of [Hastie, 2007]

 Piecewise Linear Solution Path: LARS vs LASSO
LARS vs LASSO for pain perception prediction from fMRI data [Rish, Cecchi, Baliki, Apkarian, 2010]:
for illustration purposes, we use just n=9 (out of 120) samples, but p=4000 variables; LARS selects n-1=8 variables

Least Angle regression (LARS) LARS with LASSO modification

0.04

0.03 0.03

0.02 0.02

0.01 0.01

0 0

Coefficients
Coefficients

−0.01
Crossing −0.01

−0.02 zero −0.02

Variable
deleted
−0.03 −0.03

−0.04
−0.04

−0.05
−0.05

−0.06
−0.06

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
Outline

„ Introduction

„ Sparse Linear Regression: Lasso

„ Sparse Signal Recovery and Lasso: Some Theory

„ Sparse Modeling: Beyond Lasso

„ Consistency-improving extensions

„ Beyond l1-regularization (l1/lq, Elastic Net, fused Lasso)

„ Beyond linear model (GLMs, MRFs)

„ Sparse Matrix Factorizations

„ Beyond variable-selection: variable construction

„ Summary and Open Issues

Outline

• Introduction

• Sparse Linear Regression: Lasso

• Sparse Signal Recovery and Lasso: Some Theory

• Sparse Modeling: Beyond Lasso

• Consistency-improving extensions

• Beyond l1-regularization (l1/lq, Elastic Net, fused Lasso)

• Beyond linear model (GLMs, MRFs)

• Sparse Matrix Factorizations

• Beyond variable-selection: variable construction

• Summary and Open Issues

Outline

„ Introduction

„ Sparse Linear Regression: Lasso

„ Sparse Signal Recovery and Lasso: Some Theory

„ Sparse Modeling: Beyond Lasso

„ Consistency-improving extensions

„ Beyond l1-regularization (l1/lq, Elastic Net, fused Lasso)

„ Beyond linear model (GLMs, MRFs)

„ Sparse Matrix Factorizations

„ Beyond variable-selection: variable construction

„ Summary and Open Issues

Beyond LASSO

Other likelihoods Adding structure

(loss functions) beyond sparsity

„ Generalized Linear Models „ Elastic Net

(exponential family noise) „ Fused Lasso
„ Block l1-lq norms:
„ Multivariate Gaussians group Lasso
(Gaussian MRFs) simultaneous Lasso
 Truth LASSO
relevant
cluster of
correlated
predictors
 lasso penalty
λ1 > 0, λ2= 0

ridge penalty Elastic Net

λ1 = 0, λ2> 0 penalty
Example: Application to fMRI Analysis

Pittsburgh Brain Activity Interpretation Competition (PBAIC-07):

„ subjects playing a videogame in a scanner

„ 24 continuous response variables, e.g.

• Annoyance
• Sadness
• Anxiety
• Dog
• Faces
• Instructions
• Correct hits

Goal: predict responses from fMRI data

17 minutes
Grouping Effect on PBAIC data (Carroll, Cecchi, Rish, Garg, Rao 2009)

Predicting ‘Instructions’ (auditory stimulus)

Small grouping effect: λ2 = 0.1 Larger grouping effect: λ2 = 2.0

Higher λ2→ selection of more voxels from correlated clusters →
larger, more spatially coherent clusters
Grouping Tends to Improve Model Stability (Carroll, Cecchi, Rish, Garg, Rao 2009)

Stability is measured here by average % overlap between models for 2 runs by same subject

1
OLS
Ridge
0.8 LASSO
EN 0.1
Test Correl.

0.6 EN 2.0

0.4

0.2

0
Instructions VRFixation Velocity
Regression Method

Among almost equally predictive models,

increasing λ2 can significantly improve model stability
Another Application: Sparse Models of Pain Perception from fMRI

Predicting pain ratings from fMRI in presence of thermal pain stimulus

(Rish, Cecchi, Baliki, Apkarian, BI-2010)

Pain Prediction
0.8

Best prediction
for higher λ2 response)
(corr w/ response) 0.75
Predictive accuracy

0.7
withaccuracy

0.65
predictive
(corr.

OLS
0.6 lambda2=0.1
lambda2=1
lambda2=5
lambda2=10
0.55
0 500 1000 1500
number of voxels (sparsity)

number of voxels

Including more correlated voxels (increasing λ2)

often improves the prediction accuracy as well
Image courtesy of [Tibshirani et al, 2005]
Group Lasso: Examples
More on Group Lasso
Outline

„ Introduction

„ Sparse Linear Regression: Lasso

„ Sparse Signal Recovery and Lasso: Some Theory

„ Sparse Modeling: Beyond Lasso

„ Consistency-improving extensions

„ Beyond l1-regularization (l1/lq, Elastic Net, fused Lasso)

„ Beyond linear model (GLMs, MRFs)

„ Sparse Matrix Factorizations

„ Beyond variable-selection: variable construction

„ Summary and Open Issues

Beyond Lasso: General Log-likelihood Losses

1. Gaussian Ù Lasso

2. Bernoulli Ù logistic regression

3. Exponential-family Ù Generalized Linear Models

(includes 1 and 2)

4. Multivariate Gaussian Ù Gaussian MRFs

l1-regularized M-estimators
Beyond LASSO

Other likelihoods Adding structure

(loss functions) beyond sparsity

„ Generalized Linear Models „ Elastic Net

(exponential family noise) „ Fused Lasso
„ Block l1-lq norms:
„ Multivariate Gaussians group Lasso
(Gaussian MRFs) simultaneous Lasso
Sparse Signal Recovery with M-estimators

„ Can l1-regularization accurately

. recover sparse signals given
general log P(y|x) losses?

„ Yes!
(under proper conditions)

„ risk consistency of generalized linear models (Van de Geer, 2008)

„ model-selection consistency of Gaussian MRFs (Ravikumar et al, 2008a)
„ generalized linear models: recovery in l2-norm (non-asymptotic regime) for
exponential-family noise and standard RIP conditions on the design matrix
(Rish and Grabarnik, 2009)
„ Asymptotic consistency of general losses satisfying restricted strong convexity,
with decomposable regularizers (Negahban et al., 2009)
Exponential Family Distributions

natural base
parameter measure

log-partition function

Examples: Gaussian, exponential, Bernoulli, multinomial,

gamma, chi-square, beta, Weibull, Dirichlet, Poisson, etc.
Generalized Linear Models (GLMs)
Summary: Exponential Family, GLMs, and Bregman Divergences

Exponential-Family Distributions

Legendre duality:

Generalized Linear Models Bregman Divergences

Bijection Theorem (Banerjee et al, 2005):

Fitting GLM Ù maximizing exp-family likelihood Ù

Ù minimizing Bregman divergence
Sparse Signal Recovery with Exponential-Family Noise

noise
observations natural design matrix
parameters

sparse signal

Can we recover a sparse signal

from a small number of noisy observations?
Sufficient Conditions

1 2 3
Noise is small: Restricted Isometry s-sparse
Property (RIP)

4
*
bounded

*otherwise, different proofs for some specific cases (e.g., Bernoulli, exponential, etc. )
Beyond LASSO

Other likelihoods Adding structure

(loss functions) beyond sparsity

„ Generalized Linear Models „ Elastic Net

(exponential family noise) „ Fused Lasso
„ Block l1-lq norms:
„ Multivariate Gaussians group Lasso
(Gaussian MRFs) simultaneous Lasso
Markov Networks (Markov Random Fields)
Sparse Markov Networks in Practical Applications

„ Social Networks
US senate voting data (Banerjee et al, 2008):
democrats (blue) and republicans (red)

„ Genetic Networks
Rosetta Inpharmatics Compendium of gene expression
profiles (Banerjee et al, 2008)

„ Brain Networks from fMRI

Monetary reward task (Honorio et al., 2009)
Drug addicts more connections in cerebellum
(yellow) vs control subjects (more connections
in prefrontal cortex – green)

(a) Drug addicts (b) controls

Sparse MRFs Can Predict Well

Classifying Schizophrenia Mental state prediction

(sentence vs picture)*:
(Cecchi et al., 2009)
(Scheinberg and Rish, submitted)
86% accuracy 90% accuracy
Sentence vs. Picture: Subject 04820
0.5
sparse MRF (1.0)
0.45 error

0.4

0.35

classification error
0.3

0.25

0.2

0.15

0.1

0.05

0
0 50 100 150 200 250 300 350 400
K top voxels (ttest)

MRF classifiers can often exploit informative interactions among

variables and often outperform state-of-art linear classifiers (e.g., SVM)
*Data @ [Link]/afs/[Link]/project/theo-81/www/ from T. Mitchell et al., Learning to Decode Cognitive States from Brain Images,
Machine Learning, 2004.
Network Properties as BioMarkers (Predictive Features)

Discriminative Network Models of Schizophrenia (Cecchi et al., 2009)

- Voxel degrees in functional networks (thresholded covariance matrices)

are statistically significantly different in schizophrenic patients that appear to
lack “hubs” in auditory/language areas

FDR-corrected Degree Maps

2-sample t-test performed for each voxel in

degree maps, followed by FDR correction

Red/yellow: Normal subjects have higher

values than Schizophrenics

Also, abnormal MRF connectivity observed in Alzheimer’s patients (Huang 2009),

in drug addicts (Honorio 2009), etc.
Sparse Inverse Covariance Selection Problem
Maximum Likelihood Estimation
Block-Coordinate Descent on the Dual Problem
Projected Gradient on the Dual Problem
Alternatives: Solving Primal Problem Directly

1.

2.
Additional Related Work
Selecting the Proper Regularization Parameter

“…the general issue of selecting a proper amount of regularization for getting a

right-sized structure or model has largely remained a problem with unsatisfactory
solutions“ (Meinshausen and Buehlmann , 2008)

“asymptotic considerations give little advice on how to choose a specific penalty

parameter for a given problem'‘ (Meinshausen and Buehlmann , 2006)

„ Bayesian Approach ([Link] Asadi, K. Scheinberg and I. Rish, 2009)

Assume a Bayesian prior on the regularization parameter
Find maximum a posteriory probability (MAP) solution

„ Result:
more ``balanced’’ solution (False Positive vs False Negative error) than
„ cross-validation - too dense, and
„ theoretical (Meinshausen & Buehlmann 2006, Banerjee et al 2008) - too sparse

Does not require solving multiple optimization problems over data subsets as
compared to the stability selection approach (Meinshausen and Buehlmann 2008)
Existing Approaches
Results on Random Networks

False Negatives: Missed Links False Positives: ‘Noisy’ Links

Random Networks, P=100, density=4% Random Networks, P=100, density=4%
1 1

0.9 0.9
Flat Prior (Reg. Likelihood)
0.8 0.8 Exp. Prior
False Negative Error

False Positive Error

Flat Prior (Reg. Likelihood) Theoretical
0.7 Exp. Prior 0.7 CV
Theoretical
0.6 0.6
CV

0.5 0.5

0.4 0.4

0.3 0.3

0.2 0.2

0.1 0.1

0 0
0 200 400 600 800 1000 0 200 400 600 800 1000
N N

- Cross-validation (green) overfits drastically, producing almost complete C matrix

- Theoretical (black) is too conservative: misses too many edges (near-diagonal C)

- Prior-based approaches (red and blue) are much more ‘balanced’: low FP and FN
Outline

„ Introduction

„ Sparse Linear Regression: Lasso

„ Sparse Signal Recovery and Lasso: Some Theory

„ Sparse Modeling: Beyond Lasso

„ Consistency-improving extensions

„ Beyond l1-regularization (l1/lq, Elastic Net, fused Lasso)

„ Beyond linear model (GLMs, MRFs)

„ Sparse Matrix Factorizations

„ Beyond variable-selection: variable construction

„ Summary and Open Issues

Sparse Matrix Factorization

T
X U V
n samples

m basis vectors
(dictionary)
~
p variables sparse representation
Outline

„ Introduction

„ Sparse Linear Regression: Lasso

„ Sparse Signal Recovery and Lasso: Some Theory

„ Sparse Modeling: Beyond Lasso

„ Consistency-improving extensions

„ Beyond l1-regularization (l1/lq, Elastic Net, fused Lasso)

„ Beyond linear model (GLMs, MRFs)

„ Sparse Matrix Factorizations

„ Beyond variable-selection: variable construction

„ Summary and Open Issues

From Variable Selection to Variable Construction

Supervised Dimensionality Reduction (SDR):

Y1 … YK Assume there is an inherent low-dimensional

structure in the data that is predictive about
the target Y

U1 … UL Learn a predictor (mapping from U to Y)

simultaneously with dimensionality reduction

X1 … XD
Idea: dimensionality reduction (DR) guided by
the class label may result into better predictive
features than the unsupervised DR
Particular Mappings X U and U Y

1. F. Pereira and G. Gordon. The Support Vector Decomposition Machine, ICML-06.

Real-valued X, discrete Y (linear map from X to U, SVM for Y(U) )

2. E. Xing, A. Ng, M. Jordan, and S. Russell. Distance metric learning with application to clustering with
side information, NIPS-02.
3. K. Weinberger, J. Blitzer and L. Saul. Distance Metric Learning for Large Margin Nearest Neighbor
Classification, NIPS-05.
Real-valued X, discrete Y (linear map from X to U, nearest-neighbor Y(U))

4. K. Weinberger and G. Tesauro. Metric Learning for Kernel Regression, AISTATS-07.

Real-valued X, real-valued Y (linear map from X to U, kernel regression Y(U))

5. Sajama and A. Orlitsky. Supervised Dimensionality Reduction using Mixture Models, ICML-05.
Multi-type X ([Link]), discrete Y (modeled as mixture of exp-family distributions)

6. M. Collins, S. Dasgupta and R. Schapire. A generalization of PCA to the exponential family, NIPS-01.
7. A. Schein, L. Saul and L. Ungar. A generalized linear model for PCA of binary data, AISTATS-03
Unsupervised dimensionality reduction beyond Gaussian data (nonlinear GLM mappings)

8. I. Rish, G. Grabarnik, G. Cecchi, F. Pereira and G. Gordon. Closed-form Supervised Dimensionality

Reduction with Generalized Linear Models, ICML-08
Example: SDR with Generalized Linear Models (Rish et al., 2008)

U
V1 Wk
VD W1
X1 … XD Y1 … YK

E.g., in linear case, we have:

X~ UV and Y~ UV
Supervised DR Outperforms Unsupervised DR on Simulated Data

„ Generate a separable 2-D

dataset U

„ Blow-up in D dimensional data

X by adding exponential-family
noise (e.g., Bernoulli)

„ Compare SDR w/ different

noise models (Gaussian,
Bernoulli) vs. unsupervised DR
(UDR) followed by SVM or
logistic regression

„ SDR outperforms unsupervised DR by 20-45%

„ Using proper data model (e.g., Bernoulli-SDR for binary data) matters

„ SDR ``gets’’ the structure (0% error), SVM does not (20% error)
…and on Real-Life Data from fMRI Experiments

Real-valued data, Classification Task

Predict the type of word (tools or buildings) the subject is seeing
84 samples (words presented to a subject), 14043 dimensions (voxels)

Latent dimensionality L = 5, 10, 15, 20, 25

„ Gaussian-SDR achieves overall best performance

„ SDR matches SVM’s performance using only 5 dimensions, while SVDM needs 15

„ SDR greatly outperforms unsupervised DR followed by learning a classifier

Outline

„ Introduction

„ Sparse Linear Regression: Lasso

„ Sparse Signal Recovery and Lasso: Some Theory

„ Sparse Modeling: Beyond Lasso

„ Consistency-improving extensions

„ Beyond l1-regularization (l1/lq, Elastic Net, fused Lasso)

„ Beyond linear model (GLMs, MRFs)

„ Sparse Matrix Factorizations

„ Beyond variable-selection: variable construction

„ Summary and Open Issues

Summary and Open Issues

„ Common problem: small-sample, high-dimensional inference

„ Feasible if the input is structured – e.g. sparse in some basis

„ Efficient recovery of sparse input via l1- relaxation

„ Sparse modeling with l1-regularization: interpretability + prediction

„ Beyond l1-regularization: adding more structure

„ Beyond Lasso: M-estimators, dictionary learning, variable construction

„ Open issues, still:

choice of regularization parameter?

choice of proper dictionary?

Is interpretability Ù sparsity? (NO!)

Interpretability: Much More than Sparsity?

Data Predictive Model

x - fMRI voxels,
y = f(x)
y - mental state
+ +
Interpretable + happy

Predictive + - -
- - -
Patterns sad
References
References
References
References
References
References
References
References
Appendix A
Why Exponential Family Loss?
Hub
„ Network Management – Problem Diagnosis:
R outer
binary failures - Bernoulli
non-negative delays – exponential
DB W eb
S erver Server

„ Collaborative prediction: Probing station

discrete rankings - multinomial

„ DNA microarray data analysis:

Real-valued expression level – Gaussian

„ fMRI data analysis

Real-valued voxel intensities, binary, nominal and continuous responses

Variety of data types: real-valued, binary, nominal, non-negative, etc.

Noise model: exponential-family

 Legendre duality:

Exponential-family Bregman
distribution divergence
Image courtesy of Arindam Banerjee
Appendix A
Appendix B
*

*
Appendix B
Beyond LASSO

„ Elastic Net penalty „ Generalized Linear Models

(exponential family noise)
„ Fused Lasso penalty
„ Block l1-lq norms:
group & multi-task penalties „ Multivariate Gaussians
(Gaussian MRFs)

Other penalties Other losses

(structured (other data likelihoods)
sparsity) LASSO

Improving consistency and stability

w.r.t. the sparsity parameter choice

„ Adaptive Lasso
„ Relaxed Lasso
„ Bootstrap Lasso
„ Randomized Lasso w/
Stability selection