Structured Sparsity
in Natural Language Processing:
Models, Algorithms, and Applications

André F. T. Martins1,2,3Mário A. T. Figueiredo1

Noah A. Smith2

1 Instituto de TelecomunicaçõesInstituto Superior Técnico, Lisboa, Portugal
2 Language Technologies Institute, School of Computer Science

Carnegie Mellon University, Pittsburgh, PA, USA
3 Priberam, Lisboa, Portugal

NAACL 2012: Tutorials
Montréal, Québec, June 3, 2012
Slides online at http://tiny.cc/ssnlp
Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

1 / 155

Welcome

This tutorial is about sparsity, a topic of great relevance to NLP.
Sparsity relates to feature selection, model compactness, runtime,
memory footprint, interpretability of our models.
New idea in the last 5 years: structured sparsity. This tutorial tries toanswer:What is structured sparsity?
How do we apply it?
How has it been used so far?

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

2 / 155

Outline
1

Introduction

2

Loss Functions and Sparsity

3

Structured Sparsity

4

Algorithms
Convex Analysis
Batch Algorithms
Online Algorithms

5

Applications

6

Conclusions

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

3 / 155

Notation

Many NLP problems involve mapping from one structured space toanother. Notation:
Input set X
For each x ∈ X, candidate outputs are Y(x) ⊆ Y
Mapping is hw : X → Y

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

4 / 155

Linear Models

Our predictor will take the formhw (x) = arg max w> f(x, y )y ∈Y(x)where:
f is a vector function that encodes all the relevant things about(x, y ); the result of a theory, our knowledge, feature engineering, etc.
w ∈ RD are the weights that parameterize the mapping.
NLP today: D is often in the tens or hundreds of millions.

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

5 / 155

Learning Linear Models
Max ent, perceptron, CRF, SVM, even supervised generative models all fit
the linear modeling framework.
General training setup:
We observe a collection of examples {hxn , yn i}N
n=1 .
Perform statistical analysis to discover w from the data.
Ranges from “count and normalize” to complex optimization routines.
Optimization view:Nb = arg minww

1 X
L(w; xn , yn ) + Ω(w)| {z }
Nn=1|{z} regularizer
empirical loss

This tutorial will focus on the regularizer, Ω.
Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

6 / 155

What is Sparsity?
The word “sparsity” has (at least) four related meanings in NLP!
1

Data sparsity: N is too small to obtain a good estimate for w.
Also known as “curse of dimensionality.”(Usually bad.)2“Probability” sparsity: I have a probability distribution over events(e.g., X × Y), most of which receive zero probability.
(Might be good or bad.)3

Sparsity in the dual: associated with SVMs and other kernel-based
methods; implies that the predictor can be represented via kernel
calculations involving just a few training instances.

4

Model sparsity: Most dimensions of f are not needed for a good hw ;those dimensions of w can be zero, leading to a sparse w (model).

This tutorial is about sense #4: today, (model) sparsity is a good thing!
Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

7 / 155

Why Sparsity is Desirable in NLP

Occam’s razor and interpretability.
The bet on sparsity (Friedman et al., 2004): it’s often correct. When it
isn’t, there’s no good solution anyway!
Models with just a few features areeasy to explain and implement
attractive as linguistic hypotheses
reminiscent of classical symbolic systems

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

8 / 155

A decision list from Yarowsky (1995).
Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

9 / 155

Why Sparsity is Desirable in NLP

Computational savings.
wd = 0 is equivalent to erasing the feature from the model; smaller
effective D implies smaller memory footprint.
This, in turn, implies faster decoding runtime.
Further, sometimes entire kinds of features can be eliminated, giving
asymptotic savings.

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

10 / 155

Why Sparsity is Desirable in NLPGeneralization.
The challenge of learning is to extract from the data only what will
generalize to new examples.
Forcing a learner to use few features is one way to discourage
overfitting.

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

11 / 155

Experimental results from Kazama and Tsujii (2003): F1 on two text
categorization tasks as the number of features varies.

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

12 / 155

(Automatic) Feature Selection

Human NLPers are good at thinking of features.
Can we automate the process of selecting which ones to keep?
Three kinds of methods:
1filters2

wrappers

3

embedded methods (this tutorial)

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

13 / 155

(Automatic) Feature Selection

Human NLPers are good at thinking of features.
Can we automate the process of selecting which ones to keep?
Three kinds of methods:
1filters2

wrappers

3

embedded methods (this tutorial)

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

13 / 155

Filter-based Feature Selection
For each candidate feature fd , apply a heuristic to determine whether toinclude it. (Excluding fd equates to fixing wd = 0.)
Examples:Count threshold: is |{n | fd (xn , yn ) > 0}| > τ ?
(Ignore rare features.)Mutual information or correlation between features and labels
Advantage: speed!
Disadvantages:
Ignores the learning algorithm
Thresholds require tuning

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

14 / 155

Ratnaparkhi (1996), on his POS tagger:
The behavior of a feature that occurs very sparsely in the
training set is often difficult to predict, since its statistics may
not be reliable. Therefore, the model uses the heuristic that any
feature which occurs less than 10 times in the data is unreliable,
and ignores features whose counts are less than 10.1 While there
are many smoothing algorithms which use techniques more
rigorous than a simple count cutoff, they have not yet been
investigated in conjunction with this tagger.

1

Except for features that look only at the current word, i.e., features of the form
wi =<word> and ti = <TAG>. The count of 10 was chosen by inspection of Training andDevelopment data.
Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

15 / 155

(Automatic) Feature Selection

Human NLPers are good at thinking of features.
Can we automate the process of selecting which ones to keep?
Three kinds of methods:
1filters2

wrappers

3

embedded methods (this tutorial)

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

16 / 155

(Automatic) Feature Selection

Human NLPers are good at thinking of features.
Can we automate the process of selecting which ones to keep?
Three kinds of methods:
1filters2

wrappers

3

embedded methods (this tutorial)

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

16 / 155

Wrapper-based Feature Selection

For each subset F ⊆ {1, 2, . . . D}, learn hwF for features {fd | d ∈ F}.
2D − 1 choices; so perform a search over subsets.
Cons:
NP-hard problem (Amaldi and Kann, 1998; Davis et al., 1997)
Must resort to greedy methods
Even those require iterative calls to a black-box learnerDanger of overfitting in choosing F.
(Typically use development data or cross-validate.)

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

17 / 155

Della Pietra et al. (1997) add features one at a time. Step (3) involves
re-estimating parameters:

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

18 / 155

(Automatic) Feature Selection

Human NLPers are good at thinking of features.
Can we automate the process of selecting which ones to keep?
Three kinds of methods:
1filters2

wrappers

3

embedded methods (this tutorial)

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

19 / 155

(Automatic) Feature Selection

Human NLPers are good at thinking of features.
Can we automate the process of selecting which ones to keep?
Three kinds of methods:
1filters2

wrappers

3

embedded methods (this tutorial)

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

19 / 155

Embedded Methods for Feature Selection
Formulate the learning problem as a trade-off between
minimizing loss (fitting the training data, achieving good accuracy on
the training data, etc.)
choosing a desirable model (e.g., one with no more features thanneeded)
N

min
w

1 X
L(w; xn , yn ) + Ω(w)N
n=1

Key advantage: declarative statements of model “desirability” often leadto well-understood, solvable optimization problems.

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

20 / 155

Useful Papers on Feature Selection and Sparsity

Overview of many feature selection methods:
Guyon and Elisseeff (2003)
Greedy wrapper-based method used for max ent models in NLP:
Della Pietra et al. (1997)
Early uses of sparsity in NLP:
Kazama and Tsujii (2003); Goodman (2004)

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

21 / 155

Outline
1

Introduction

2

Loss Functions and Sparsity

3

Structured Sparsity

4

Algorithms
Convex Analysis
Batch Algorithms
Online Algorithms

5

Applications

6

Conclusions

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

22 / 155

Loss functions (I)Regression (y ∈ R) typically uses the squared error loss:
LSE (w; x, y ) =Martins, Figueiredo, Smith (IST, CMU)21y − w> f(x)2Structured Sparsity in NLP

http://tiny.cc/ssnlp

23 / 155

Loss functions (I)Regression (y ∈ R) typically uses the squared error loss:
LSE (w; x, y ) =Total loss:

21
y − w> f(x)
2

N

2 1
1 X
yn − w> f(xn ) = kAw − yk2222
n=1

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

23 / 155

Loss functions (I)Regression (y ∈ R) typically uses the squared error loss:
LSE (w; x, y ) =Total loss:

21
y − w> f(x)
2

N

2 1
1 X
yn − w> f(xn ) = kAw − yk2222
n=1

Design matrix: A = [Aij ]i=1,...,N; j=1,...,D , where Aij = fj (xi ).

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

23 / 155

Loss functions (I)Regression (y ∈ R) typically uses the squared error loss:
LSE (w; x, y ) =Total loss:

21
y − w> f(x)
2

N

2 1
1 X
yn − w> f(xn ) = kAw − yk2222
n=1

Design matrix: A = [Aij ]i=1,...,N; j=1,...,D , where Aij = fj (xi ).
Response vector: y = [y1 , ..., yN ]> .

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

23 / 155

Loss functions (I)Regression (y ∈ R) typically uses the squared error loss:
LSE (w; x, y ) =Total loss:

21
y − w> f(x)
2

N

2 1
1 X
yn − w> f(xn ) = kAw − yk2222
n=1

Design matrix: A = [Aij ]i=1,...,N; j=1,...,D , where Aij = fj (xi ).
Response vector: y = [y1 , ..., yN ]> .
Arguably, the most/best studied loss function (statistics, machinelearning, signal processing).

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

23 / 155

Loss functions (II)Classification and structured prediction using log-linear models(logistic regression, max ent, conditional random fields):
LLR (w; x, y ) = − log P (y |x; w)
exp(w> f (x, y ))= − log P>0y 0 ∈Y(x) exp(w f (x, y ))= − w> f (x, y ) + log Z (w, x)Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

24 / 155

Loss functions (II)Classification and structured prediction using log-linear models(logistic regression, max ent, conditional random fields):
LLR (w; x, y ) = − log P (y |x; w)
exp(w> f (x, y ))= − log P>0y 0 ∈Y(x) exp(w f (x, y ))= − w> f (x, y ) + log Z (w, x)
Partition function:
Z (w, x) =X

exp(w> f (x, y 0 )).

y 0 ∈Y(x)Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

24 / 155

Loss functions (II)Classification and structured prediction using log-linear models(logistic regression, max ent, conditional random fields):
LLR (w; x, y ) = − log P (y |x; w)
exp(w> f (x, y ))= − log P>0y 0 ∈Y(x) exp(w f (x, y ))= − w> f (x, y ) + log Z (w, x)
Partition function:
Z (w, x) =X

exp(w> f (x, y 0 )).

y 0 ∈Y(x)Related loss functions: hinge loss (in SVM) and the perceptron loss.

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

24 / 155

Main Loss Functions: Summary

2y − w> f(x)X−w> f(x, y ) + log
exp(w> f(x, y 0 ))1
2

Squared (linear regression)
Log-linear (MaxEnt, CRF, logistic)y 0 ∈Y

Hinge (SVMs)
Perceptron>−w f(x, y ) + max
w> f(x, y 0 ) + c(y , y 0 )
0
y ∈Y

>

−w f(x, y ) + max
w> f(x, y 0 )0y ∈Y(in the SVM loss, c(y , y 0 ) is a cost function.)

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

25 / 155

Main Loss Functions: Summary

2y − w> f(x)X−w> f(x, y ) + log
exp(w> f(x, y 0 ))1
2

Squared (linear regression)
Log-linear (MaxEnt, CRF, logistic)y 0 ∈Y

Hinge (SVMs)
Perceptron>−w f(x, y ) + max
w> f(x, y 0 ) + c(y , y 0 )
0
y ∈Y

>

−w f(x, y ) + max
w> f(x, y 0 )0y ∈Y(in the SVM loss, c(y , y 0 ) is a cost function.)
All these losses are particular cases of general family (Martins et al., 2010).

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

25 / 155

Regularization
Regularized parameter estimate:b = arg min Ω(w) +
w
w

N
X

|
where Ω(w) ≥ 0 andL(w; xn , yn )

n=1

{z
}
total loss

lim Ω(w) = ∞ (coercive function).

kwk→∞

Why regularize?
Improve generalization by avoiding over-fitting.

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

26 / 155

Regularization
Regularized parameter estimate:b = arg min Ω(w) +
w
w

N
X

|
where Ω(w) ≥ 0 andL(w; xn , yn )

n=1

{z
}
total loss

lim Ω(w) = ∞ (coercive function).

kwk→∞

Why regularize?
Improve generalization by avoiding over-fitting.
The total loss may not be coercive (e.g., logistic loss on separable
data), thus having no minima.

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

26 / 155

Regularization
Regularized parameter estimate:b = arg min Ω(w) +
w
w

N
X

|
where Ω(w) ≥ 0 andL(w; xn , yn )

n=1

{z
}
total loss

lim Ω(w) = ∞ (coercive function).

kwk→∞

Why regularize?
Improve generalization by avoiding over-fitting.
The total loss may not be coercive (e.g., logistic loss on separable
data), thus having no minima.
Express prior knowledge about w.

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

26 / 155

Regularization
Regularized parameter estimate:b = arg min Ω(w) +
w
w

N
X

|
where Ω(w) ≥ 0 andL(w; xn , yn )

n=1

{z
}
total loss

lim Ω(w) = ∞ (coercive function).

kwk→∞

Why regularize?
Improve generalization by avoiding over-fitting.
The total loss may not be coercive (e.g., logistic loss on separable
data), thus having no minima.
Express prior knowledge about w.
Select relevant features (via sparsity-inducing regularization).
Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

26 / 155

Regularization
Regularized parameter estimate:b = arg min Ω(w) +
w
w

N
X

|
where Ω(w) ≥ 0 andL(w; xn , yn )

n=1

{z
}
total loss

lim Ω(w) = ∞ (coercive function).

kwk→∞

Why regularize?
Improve generalization by avoiding over-fitting.
The total loss may not be coercive (e.g., logistic loss on separable
data), thus having no minima.
Express prior knowledge about w.
Select relevant features (via sparsity-inducing regularization).
Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

26 / 155

Regularization Formulations
Tikhonov regularization:

Martins, Figueiredo, Smith (IST, CMU)b = arg min λΩ̄(w) +w
w

Structured Sparsity in NLPNX

L(w; xn , yn )n=1

http://tiny.cc/ssnlp

27 / 155

Regularization Formulations
Tikhonov regularization:b = arg min λΩ̄(w) +
w
w

N
X

L(w; xn , yn )n=1

Ivanov regularizationb = arg min
w
w

N
X

L(w; xn , yn )n=1

subject to Ω(w) ≤ τ

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

27 / 155

Regularization Formulations
Tikhonov regularization:b = arg min λΩ̄(w) +
w
w

N
X

L(w; xn , yn )n=1

Ivanov regularizationb = arg min
w
w

N
X

L(w; xn , yn )n=1

subject to Ω(w) ≤ τMorozov regularizationb = arg min Ω(w)ww

subject toN
X

L(w; xn , yn ) ≤ δ

n=1

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

27 / 155

Regularization Formulations
Tikhonov regularization:b = arg min λΩ̄(w) +
w
w

N
X

L(w; xn , yn )n=1

Ivanov regularizationb = arg min
w
w

N
X

L(w; xn , yn )n=1

subject to Ω(w) ≤ τMorozov regularizationb = arg min Ω(w)ww

subject toN
X

L(w; xn , yn ) ≤ δ

n=1

Equivalent, under mild conditions (namely convexity).
Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

27 / 155

Regularization vs. Bayesian estimation
Regularized parameter estimate:b = arg min Ω(w) +
w
w

N
X

L(w; xn , yn )n=1...interpretable as Bayesian maximum a posteriori (MAP) estimate:NYb = arg max exp (−Ω(w))
w
exp (−L(w; xn , yn )) .
w |
{z
}
n=1
{z
}
|
prior p(w)likelihood (i.i.d. data)

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

28 / 155

Regularization vs. Bayesian estimation
Regularized parameter estimate:b = arg min Ω(w) +
w
w

N
X

L(w; xn , yn )n=1...interpretable as Bayesian maximum a posteriori (MAP) estimate:NYb = arg max exp (−Ω(w))
w
exp (−L(w; xn , yn )) .
w |
{z
}
n=1
{z
}
|
prior p(w)likelihood (i.i.d. data)

This interpretation underlies the logistic regression (LR) loss:
LLR (w; xn , yn ) = − log P (yn |xn ; w).

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

28 / 155

Regularization vs. Bayesian estimation
Regularized parameter estimate:b = arg min Ω(w) +
w
w

N
X

L(w; xn , yn )n=1...interpretable as Bayesian maximum a posteriori (MAP) estimate:NYb = arg max exp (−Ω(w))
w
exp (−L(w; xn , yn )) .
w |
{z
}
n=1
{z
}
|
prior p(w)likelihood (i.i.d. data)

This interpretation underlies the logistic regression (LR) loss:
LLR (w; xn , yn ) = − log P (yn |xn ; w).
Same is true for the squared error (SE) loss:
2
LSE (w; xn , yn ) = 12 y − w> f(x) = − log N(y |w> f(x), 1)
Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

28 / 155

Norms: A Quick Review
Before focusing on regularizers, a quick review about norms.

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

29 / 155

Norms: A Quick Review
Before focusing on regularizers, a quick review about norms.
Some function p : R → R is a norm if if satisfies:p(αw) = |α|p(w), for any w (homogeneity);

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

29 / 155

Norms: A Quick Review
Before focusing on regularizers, a quick review about norms.
Some function p : R → R is a norm if if satisfies:p(αw) = |α|p(w), for any w (homogeneity);p(w + w0 ) ≤ p(w) + p(w0 ), for any w, w0 (triangle inequality);

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

29 / 155

Norms: A Quick Review
Before focusing on regularizers, a quick review about norms.
Some function p : R → R is a norm if if satisfies:p(αw) = |α|p(w), for any w (homogeneity);p(w + w0 ) ≤ p(w) + p(w0 ), for any w, w0 (triangle inequality);p(w) = 0 if and only if w = 0.

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

29 / 155

Norms: A Quick Review
Before focusing on regularizers, a quick review about norms.
Some function p : R → R is a norm if if satisfies:p(αw) = |α|p(w), for any w (homogeneity);p(w + w0 ) ≤ p(w) + p(w0 ), for any w, w0 (triangle inequality);p(w) = 0 if and only if w = 0.
Examples of norms:!1/p
kwkp =X(wi )p(called `p norm, for p ≥ 1).

i

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

29 / 155

Norms: A Quick Review
Before focusing on regularizers, a quick review about norms.
Some function p : R → R is a norm if if satisfies:p(αw) = |α|p(w), for any w (homogeneity);p(w + w0 ) ≤ p(w) + p(w0 ), for any w, w0 (triangle inequality);p(w) = 0 if and only if w = 0.
Examples of norms:!1/p
kwkp =X(wi )p(called `p norm, for p ≥ 1).

i

kwk∞ = lim kwkp = max{|wi |, i = 1, ..., D}p→∞Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

29 / 155

Norms: A Quick Review
Before focusing on regularizers, a quick review about norms.
Some function p : R → R is a norm if if satisfies:p(αw) = |α|p(w), for any w (homogeneity);p(w + w0 ) ≤ p(w) + p(w0 ), for any w, w0 (triangle inequality);p(w) = 0 if and only if w = 0.
Examples of norms:!1/p
kwkp =X(wi )p(called `p norm, for p ≥ 1).

i

kwk∞ = lim kwkp = max{|wi |, i = 1, ..., D}p→∞

Fact: all norms are convex.

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

29 / 155

Norms: A Quick Review
Before focusing on regularizers, a quick review about norms.
Some function p : R → R is a norm if if satisfies:p(αw) = |α|p(w), for any w (homogeneity);p(w + w0 ) ≤ p(w) + p(w0 ), for any w, w0 (triangle inequality);p(w) = 0 if and only if w = 0.
Examples of norms:!1/p
kwkp =X(wi )p(called `p norm, for p ≥ 1).

i

kwk∞ = lim kwkp = max{|wi |, i = 1, ..., D}p→∞

Fact: all norms are convex.
Also important (but not a norm): kwk0 = lim kwkpp = |{i : wi 6= 0}|p→0Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

29 / 155

Classical Regularizers: Ridgeb = arg min
Regularized parameter estimate: ww

NX

L(w; xn , yn ) + Ω(w)

n=1

λ
kwk22
2

Corresponds to zero-mean Gaussian prior p(w) ∝ exp −λkwk22

Arguably, the most classical choice: squared `2 norm: Ω(w) =Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

30 / 155

Classical Regularizers: Ridgeb = arg min
Regularized parameter estimate: ww

NX

L(w; xn , yn ) + Ω(w)

n=1

λ
kwk22
2

Corresponds to zero-mean Gaussian prior p(w) ∝ exp −λkwk22

Arguably, the most classical choice: squared `2 norm: Ω(w) =Ridge regression (SE loss): Hoerl and Kennard (1962 and 1970).

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

30 / 155

Classical Regularizers: Ridgeb = arg min
Regularized parameter estimate: ww

NX

L(w; xn , yn ) + Ω(w)

n=1

λ
kwk22
2

Corresponds to zero-mean Gaussian prior p(w) ∝ exp −λkwk22

Arguably, the most classical choice: squared `2 norm: Ω(w) =Ridge regression (SE loss): Hoerl and Kennard (1962 and 1970).
Ridge logistic regression: Schaefer et al. (1984), Cessie andHouwelingen (1992); in NLP: Chen and Rosenfeld (1999).

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

30 / 155

Classical Regularizers: Ridgeb = arg min
Regularized parameter estimate: ww

NX

L(w; xn , yn ) + Ω(w)

n=1

λ
kwk22
2

Corresponds to zero-mean Gaussian prior p(w) ∝ exp −λkwk22

Arguably, the most classical choice: squared `2 norm: Ω(w) =Ridge regression (SE loss): Hoerl and Kennard (1962 and 1970).
Ridge logistic regression: Schaefer et al. (1984), Cessie andHouwelingen (1992); in NLP: Chen and Rosenfeld (1999).
Closely related to Tikhonov (1943) and Wiener (1949).

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

30 / 155

Classical Regularizers: Ridgeb = arg min
Regularized parameter estimate: ww

NX

L(w; xn , yn ) + Ω(w)

n=1

λ
kwk22
2

Corresponds to zero-mean Gaussian prior p(w) ∝ exp −λkwk22

Arguably, the most classical choice: squared `2 norm: Ω(w) =Ridge regression (SE loss): Hoerl and Kennard (1962 and 1970).
Ridge logistic regression: Schaefer et al. (1984), Cessie andHouwelingen (1992); in NLP: Chen and Rosenfeld (1999).
Closely related to Tikhonov (1943) and Wiener (1949).
Pros: smooth and convex, thus benign for optimization.

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

30 / 155

Classical Regularizers: Ridgeb = arg min
Regularized parameter estimate: ww

NX

L(w; xn , yn ) + Ω(w)

n=1

λ
kwk22
2

Corresponds to zero-mean Gaussian prior p(w) ∝ exp −λkwk22

Arguably, the most classical choice: squared `2 norm: Ω(w) =Ridge regression (SE loss): Hoerl and Kennard (1962 and 1970).
Ridge logistic regression: Schaefer et al. (1984), Cessie andHouwelingen (1992); in NLP: Chen and Rosenfeld (1999).
Closely related to Tikhonov (1943) and Wiener (1949).
Pros: smooth and convex, thus benign for optimization.
Cons: doesn’t promote sparsity (no explicit feature selection).

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

30 / 155

Classical Regularizers: Lassob = arg min
Regularized parameter estimate: ww

NX

L(w; xn , yn ) + Ω(w)n=1

The new classic is the `1 norm: Ω(w) = λkwk1 = λDX|wi |.

i=1

Corresponds to zero-mean Laplacian prior p(wi ) ∝ exp (−λ|wi |)Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

31 / 155

Classical Regularizers: Lassob = arg min
Regularized parameter estimate: ww

NX

L(w; xn , yn ) + Ω(w)n=1

The new classic is the `1 norm: Ω(w) = λkwk1 = λDX|wi |.

i=1

Corresponds to zero-mean Laplacian prior p(wi ) ∝ exp (−λ|wi |)Best known as: least absolute shrinkage and selection operator(Lasso) (Tibshirani, 1996).

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

31 / 155

Classical Regularizers: Lassob = arg min
Regularized parameter estimate: ww

NX

L(w; xn , yn ) + Ω(w)n=1

The new classic is the `1 norm: Ω(w) = λkwk1 = λDX|wi |.

i=1

Corresponds to zero-mean Laplacian prior p(wi ) ∝ exp (−λ|wi |)Best known as: least absolute shrinkage and selection operator(Lasso) (Tibshirani, 1996).
Used earlier in signal processing (Claerbout and Muir, 1973; Taylor
et al., 1979) neural networks (Williams, 1995),...

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

31 / 155

Classical Regularizers: Lassob = arg min
Regularized parameter estimate: ww

NX

L(w; xn , yn ) + Ω(w)n=1

The new classic is the `1 norm: Ω(w) = λkwk1 = λDX|wi |.

i=1

Corresponds to zero-mean Laplacian prior p(wi ) ∝ exp (−λ|wi |)Best known as: least absolute shrinkage and selection operator(Lasso) (Tibshirani, 1996).
Used earlier in signal processing (Claerbout and Muir, 1973; Taylor
et al., 1979) neural networks (Williams, 1995),...

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

31 / 155

Classical Regularizers: Lassob = arg min
Regularized parameter estimate: ww

NX

L(w; xn , yn ) + Ω(w)n=1

The new classic is the `1 norm: Ω(w) = λkwk1 = λDX|wi |.

i=1

Corresponds to zero-mean Laplacian prior p(wi ) ∝ exp (−λ|wi |)Best known as: least absolute shrinkage and selection operator(Lasso) (Tibshirani, 1996).
Used earlier in signal processing (Claerbout and Muir, 1973; Taylor
et al., 1979) neural networks (Williams, 1995),...
In NLP: Kazama and Tsujii (2003); Goodman (2004).

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

31 / 155

Classical Regularizers: Lassob = arg min
Regularized parameter estimate: ww

NX

L(w; xn , yn ) + Ω(w)n=1

The new classic is the `1 norm: Ω(w) = λkwk1 = λDX|wi |.

i=1

Corresponds to zero-mean Laplacian prior p(wi ) ∝ exp (−λ|wi |)Best known as: least absolute shrinkage and selection operator(Lasso) (Tibshirani, 1996).
Used earlier in signal processing (Claerbout and Muir, 1973; Taylor
et al., 1979) neural networks (Williams, 1995),...
In NLP: Kazama and Tsujii (2003); Goodman (2004).
Pros: encourages sparsity: embedded feature selection.

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

31 / 155

Classical Regularizers: Lassob = arg min
Regularized parameter estimate: ww

NX

L(w; xn , yn ) + Ω(w)n=1

The new classic is the `1 norm: Ω(w) = λkwk1 = λDX|wi |.

i=1

Corresponds to zero-mean Laplacian prior p(wi ) ∝ exp (−λ|wi |)Best known as: least absolute shrinkage and selection operator(Lasso) (Tibshirani, 1996).
Used earlier in signal processing (Claerbout and Muir, 1973; Taylor
et al., 1979) neural networks (Williams, 1995),...
In NLP: Kazama and Tsujii (2003); Goodman (2004).
Pros: encourages sparsity: embedded feature selection.
Cons: convex, but non-smooth: challenging optimization.

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

31 / 155

The Lasso and Sparsity
Why does the Lasso yield sparsity?
The simplest case: y −λ ⇐ y >λ12
b = arg min (w − y ) + λ|w | = soft(y , λ) =0
⇐ |y | ≤ λww 2y + λ ⇐ y < −λMartins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

32 / 155

The Lasso and Sparsity
Why does the Lasso yield sparsity?
The simplest case: y −λ ⇐ y >λ12
b = arg min (w − y ) + λ|w | = soft(y , λ) =0
⇐ |y | ≤ λww 2y + λ ⇐ y < −λMartins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

32 / 155

The Lasso and Sparsity
Why does the Lasso yield sparsity?
The simplest case: y −λ ⇐ y >λ12
b = arg min (w − y ) + λ|w | = soft(y , λ) =0
⇐ |y | ≤ λww 2y + λ ⇐ y < −λContrast with the squared `2 (ridge) regularizer (linear scaling):
λ11b = arg min (w − y )2 + w 2 =
w
y
w 2
2
1+λ
Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

32 / 155

The Lasso and Sparsity (II)Why does the Lasso yield sparsity?

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

33 / 155

The Lasso and Sparsity (II)Why does the Lasso yield sparsity?

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

33 / 155

Relationship Between `1 and `0
The `0 “norm” (number of non-zeros): kwk0 = |{i : wi 6= 0}|.
Not convex, but...
√1b = arg min (w − y )2 + λ|w |0 = hard(y , 2λ) =w
w 2Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP√y ⇐ |y | > √2λ
0 ⇐ |y | ≤ 2λ

http://tiny.cc/ssnlp

34 / 155

Relationship Between `1 and `0
The `0 “norm” (number of non-zeros): kwk0 = |{i : wi 6= 0}|.
Not convex, but...
√1b = arg min (w − y )2 + λ|w |0 = hard(y , 2λ) =w
w 2Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP√y ⇐ |y | > √2λ
0 ⇐ |y | ≤ 2λ

http://tiny.cc/ssnlp

34 / 155

Relationship Between `1 and `0
The `0 “norm” (number of non-zeros): kwk0 = |{i : wi 6= 0}|.
Not convex, but...
√1b = arg min (w − y )2 + λ|w |0 = hard(y , 2λ) =
w
w 2



√
y ⇐ |y | > √2λ
0 ⇐ |y | ≤ 2λ

The “ideal” feature selection criterion (best subset):b = arg min
w
w

N
X

L(w; xn , yn )n=1

subject to kwk0 ≤ τMartins, Figueiredo, Smith (IST, CMU)

(limit the number of features)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

34 / 155

Relationship Between `1 and `0 (II)The best subset selection problem

b = arg min
w
w

N
X

L(w; xn , yn )n=1

subject to kwk0 ≤ τ.
Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

35 / 155

Relationship Between `1 and `0 (II)The best subset selection problem is NP-hard Amaldi and Kann
(1998)(Davis et al., 1997).
b = arg min
w
w

N
X

L(w; xn , yn )n=1

subject to kwk0 ≤ τ.
Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

35 / 155

Relationship Between `1 and `0 (II)The best subset selection problem is NP-hard Amaldi and Kann
(1998)(Davis et al., 1997).
b = arg min
w
w

N
X

L(w; xn , yn )n=1

subject to kwk0 ≤ τ
A closely related problem,b = arg min kwk0w
w

subject toN
X

L(w; xn , yn ) ≤ δ

n=1.
Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

35 / 155

Relationship Between `1 and `0 (II)The best subset selection problem is NP-hard Amaldi and Kann
(1998)(Davis et al., 1997).
b = arg min
w
w

N
X

L(w; xn , yn )n=1

subject to kwk0 ≤ τ
A closely related problem, also NP-hard (Muthukrishnan, 2005).
b = arg min kwk0w
w

subject toN
X

L(w; xn , yn ) ≤ δ

n=1.
Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

35 / 155

Relationship Between `1 and `0 (II)The best subset selection problem is NP-hard Amaldi and Kann
(1998)(Davis et al., 1997).
b = arg min
w
w

N
X

L(w; xn , yn )n=1

subject to kwk0 ≤ τ
A closely related problem, also NP-hard (Muthukrishnan, 2005).
b = arg min kwk0w
w

subject toN
X

L(w; xn , yn ) ≤ δ

n=1

In some cases, one may replace `0 with `1 and obtain “similar” results:
central issue in compressive sensing (CS) (Candès et al., 2006a; Donoho,2006).
Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

35 / 155

Compressive Sensing in One Slide

Even in the noiseless case, it seems impossible to recover w from y

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

36 / 155

Compressive Sensing in One Slide

Even in the noiseless case, it seems impossible to recover w from y...unless, w is sparse and A has some properties.

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

36 / 155

Compressive Sensing in One Slide

Even in the noiseless case, it seems impossible to recover w from y...unless, w is sparse and A has some properties.
If w is sparse enough and A has certain properties, then w is stably
recovered via (Haupt and Nowak, 2006)b = arg min kwk0w
w

subject to kAw − yk ≤ δMartins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

NP-hard!
http://tiny.cc/ssnlp

36 / 155

...OK, in Two Slides
Under some conditions on A (e.g., the restricted isometry property (RIP)),`0 can be replaced with `1 (Candès et al., 2006b):b = arg min kwk1w
w

subject to kAw − yk ≤ δMartins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

convex problem

http://tiny.cc/ssnlp

37 / 155

...OK, in Two Slides
Under some conditions on A (e.g., the restricted isometry property (RIP)),`0 can be replaced with `1 (Candès et al., 2006b):b = arg min kwk1w
w

subject to kAw − yk ≤ δconvex problem

Matrix A satisfies the RIP of order k, with constant δk ∈ (0, 1), if
kwk0 ≤ k ⇒ (1 − δk )kwk22 ≤ kAwk ≤ (1 + δk )kwk22...i.e., for k-sparse vectors, A is approximately an isometry.

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

37 / 155

...OK, in Two Slides
Under some conditions on A (e.g., the restricted isometry property (RIP)),`0 can be replaced with `1 (Candès et al., 2006b):b = arg min kwk1w
w

subject to kAw − yk ≤ δconvex problem

Matrix A satisfies the RIP of order k, with constant δk ∈ (0, 1), if
kwk0 ≤ k ⇒ (1 − δk )kwk22 ≤ kAwk ≤ (1 + δk )kwk22...i.e., for k-sparse vectors, A is approximately an isometry.

Other properties (spark and null space property (NSP)) can be used;checking RIP, NSP, spark is NP-hard (Tillmann and Pfetsch, 2012).
Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

37 / 155

Relevant Theory?
Are sparsity-related compressed sensing (CS) results relevant for NLP?

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

38 / 155

Relevant Theory?
Are sparsity-related compressed sensing (CS) results relevant for NLP?
Nearly all CS results assume linear observations y = Aw + noise;
recent exceptions: Blumensath (2012); Plan and Vershynin (2012).

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

38 / 155

Relevant Theory?
Are sparsity-related compressed sensing (CS) results relevant for NLP?
Nearly all CS results assume linear observations y = Aw + noise;
recent exceptions: Blumensath (2012); Plan and Vershynin (2012).
“Good” matrices with RIP or NSP are randomly constructed.

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

38 / 155

Relevant Theory?
Are sparsity-related compressed sensing (CS) results relevant for NLP?
Nearly all CS results assume linear observations y = Aw + noise;
recent exceptions: Blumensath (2012); Plan and Vershynin (2012).
“Good” matrices with RIP or NSP are randomly constructed.
What is missing: results for (multinomial) logistic loss, not based on
RIP or NSP.

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

38 / 155

Relevant Theory?
Are sparsity-related compressed sensing (CS) results relevant for NLP?
Nearly all CS results assume linear observations y = Aw + noise;
recent exceptions: Blumensath (2012); Plan and Vershynin (2012).
“Good” matrices with RIP or NSP are randomly constructed.
What is missing: results for (multinomial) logistic loss, not based on
RIP or NSP.
Other types of results for `1 -regularized logistic regression:

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

38 / 155

Relevant Theory?
Are sparsity-related compressed sensing (CS) results relevant for NLP?
Nearly all CS results assume linear observations y = Aw + noise;
recent exceptions: Blumensath (2012); Plan and Vershynin (2012).
“Good” matrices with RIP or NSP are randomly constructed.
What is missing: results for (multinomial) logistic loss, not based on
RIP or NSP.
Other types of results for `1 -regularized logistic regression:
PAC-Bayesian bounds (generalization improves with sparsity):
Krishnapuram et al. (2005)

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

38 / 155

Relevant Theory?
Are sparsity-related compressed sensing (CS) results relevant for NLP?
Nearly all CS results assume linear observations y = Aw + noise;
recent exceptions: Blumensath (2012); Plan and Vershynin (2012).
“Good” matrices with RIP or NSP are randomly constructed.
What is missing: results for (multinomial) logistic loss, not based on
RIP or NSP.
Other types of results for `1 -regularized logistic regression:
PAC-Bayesian bounds (generalization improves with sparsity):
Krishnapuram et al. (2005)
Oracle (van de Geer, 2008) and consistency (Negahban et al., 2012)
results.

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

38 / 155

Take-Home Messages
Sparsity is desirable for interpretability, computational savings, andgeneralization`1 -regularization gives an embedded method for feature selection
Another view of `1 : a convex surrogate for direct penalization ofcardinality (`0 )Under some conditions, `1 guarantees exact support recovery
However: the currently known sufficient conditions are too strong andnot met in typical NLP problems
Yet: a lot of theory is still missing
There are compelling algorithmic reasons for using convex surrogateslike `1

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

39 / 155

Outline
1

Introduction

2

Loss Functions and Sparsity

3

Structured Sparsity

4

Algorithms
Convex Analysis
Batch Algorithms
Online Algorithms

5

Applications

6

Conclusions

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

40 / 155

Models`1 regularization promotes sparse models
A very simple sparsity pattern: prefer models with small cardinality

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

41 / 155

Models`1 regularization promotes sparse models
A very simple sparsity pattern: prefer models with small cardinality
Our main question: how can we promote less trivial sparsity patterns?

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

41 / 155

Models`1 regularization promotes sparse models
A very simple sparsity pattern: prefer models with small cardinality
Our main question: how can we promote less trivial sparsity patterns?

We’ll talk about structured sparsity and group-Lasso regularization.

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

41 / 155

Structured Sparsity and Groups

Main goal: promote structural patterns, not just penalize cardinality

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

42 / 155

Structured Sparsity and Groups

Main goal: promote structural patterns, not just penalize cardinality
Group sparsity: discard entire groups of features
density inside each group
sparsity with respect to the groups which are selectedchoice of groups: prior knowledge about the intended sparsity patterns

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

42 / 155

Structured Sparsity and Groups

Main goal: promote structural patterns, not just penalize cardinality
Group sparsity: discard entire groups of features
density inside each group
sparsity with respect to the groups which are selectedchoice of groups: prior knowledge about the intended sparsity patterns
Leads to statistical gains if the prior assumptions are correct (Stojnic
et al., 2009)

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

42 / 155

Tons of Usesfeature template selection (Martins et al., 2011b)
multi-task learning (Caruana, 1997; Obozinski et al., 2010)
multiple kernel learning (Lanckriet et al., 2004)
learning the structure of graphical models (Schmidt and Murphy,
2010)

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

43 / 155

“Grid” Sparsity

For feature spaces that can be arranged as a grid (examples next)

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

44 / 155

“Grid” Sparsity

For feature spaces that can be arranged as a grid (examples next)

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

44 / 155

“Grid” Sparsity

For feature spaces that can be arranged as a grid (examples next)

Goal: push entire columns to have zero weights
The groups are the columns of the gridMartins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

44 / 155

Example 1: Sparsity with Multiple Classes
Assume the feature map decomposes as f(x, y ) = f(x) ⊗ ey
In words: we’re conjoining each input feature with each output classlabelsinput features

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

45 / 155

Example 1: Sparsity with Multiple Classes
Assume the feature map decomposes as f(x, y ) = f(x) ⊗ ey
In words: we’re conjoining each input feature with each output classlabelsinput features“Standard” sparsity is wasteful—we still need to hash all the input features
What we want: discard some input features, along with each class they
conjoin with
Solution: one group per input feature
Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

45 / 155

Example 2: Multi-Task Learning(Caruana, 1997; Obozinski et al., 2010)Same thing, except now rows are tasks and columns are features

tasks

shared features

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

46 / 155

Example 2: Multi-Task Learning(Caruana, 1997; Obozinski et al., 2010)Same thing, except now rows are tasks and columns are features

tasks

shared features

What we want: discard features that are irrelevant for all tasks
Solution: one group per feature

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

46 / 155

Example 3: Multiple Kernel Learning(Lanckriet et al., 2004)
Same thing, except now columns are kernel functions {Km }M
m=1

implicit featureskernels

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

47 / 155

Example 3: Multiple Kernel Learning(Lanckriet et al., 2004)
Same thing, except now columns are kernel functions {Km }M
m=1

implicit featureskernels

Goal: a new kernel which is a sparse combination of the given kernels
00

K ((x, y ), (x , y )) =M
X

αm Km ((x, y ), (x 0 , y 0 )),α is sparse

m=1

Solution: make each group be a kernel Kj
Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

47 / 155

Group Sparsity
D features

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

48 / 155

Group Sparsity
D features
M groups G1 , . . . , GM , eachGm ⊆ {1, . . . , D}parameter subvectors w1 , . . . , wM

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

48 / 155

Group Sparsity
D features
M groups G1 , . . . , GM , eachGm ⊆ {1, . . . , D}parameter subvectors w1 , . . . , wM
Group-Lasso (Bakin, 1999; Yuan and Lin, 2006):Ω(w) =

Martins, Figueiredo, Smith (IST, CMU)PM

m=1 kwm k2

Structured Sparsity in NLP

http://tiny.cc/ssnlp

48 / 155

Group Sparsity
D features
M groups G1 , . . . , GM , eachGm ⊆ {1, . . . , D}parameter subvectors w1 , . . . , wM
Group-Lasso (Bakin, 1999; Yuan and Lin, 2006):Ω(w) =

PM

m=1 kwm k2

Intuitively: the `1 norm of the `2 norms
Technically, still a norm (called a mixed norm, denoted `2,1 )Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

48 / 155

Group Sparsity
D features
M groups G1 , . . . , GM , eachGm ⊆ {1, . . . , D}parameter subvectors w1 , . . . , wM
Group-Lasso (Bakin, 1999; Yuan and Lin, 2006):Ω(w) =

PM

m=1 λm kwm k2

Intuitively: the `1 norm of the `2 norms
Technically, still a norm (called a mixed norm, denoted `2,1 )λm : prior weight for group Gm (different groups have different sizes)

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

48 / 155

Regularization Formulations (reminder)
Tikhonov regularization:b = arg min Ω(w) +
w
w

N
X

L(w; xn , yn )n=1

Ivanov regularizationb = arg min
w
w

N
X

L(w; xn , yn )n=1

subject to Ω(w) ≤ τMorozov regularizationb = arg min Ω(w)ww

subject toN
X

L(w; xn , yn ) ≤ δ

n=1

Equivalent, under mild conditions (namely convexity).
Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

49 / 155

Lasso versus group-Lasso

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

50 / 155

Lasso versus group-Lasso

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

50 / 155

Other names, other norms
Statisticians call these composite absolute penalties (Zhao et al., 2009)
In general: the (weighted) `r -norm of the `q -norms (r ≥ 1, q ≥ 1), called
the mixed `q,r normΩ(w) =

Martins, Figueiredo, Smith (IST, CMU)P

Mr
m=1 λm kwm kq

Structured Sparsity in NLP

1/r

http://tiny.cc/ssnlp

51 / 155

Other names, other norms
Statisticians call these composite absolute penalties (Zhao et al., 2009)
In general: the (weighted) `r -norm of the `q -norms (r ≥ 1, q ≥ 1), called
the mixed `q,r normΩ(w) =

PMr
m=1 λm kwm kq

1/rGroup sparsity corresponds to r = 1

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

51 / 155

Other names, other norms
Statisticians call these composite absolute penalties (Zhao et al., 2009)
In general: the (weighted) `r -norm of the `q -norms (r ≥ 1, q ≥ 1), called
the mixed `q,r normΩ(w) =

PMr
m=1 λm kwm kq

1/rGroup sparsity corresponds to r = 1
This talk: q = 2
However q = ∞ is also popular (Quattoni et al., 2009; Graça et al., 2009;
Wright et al., 2009; Eisenstein et al., 2011)

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

51 / 155

Three Scenarios

Non-overlapping Groups
Tree-structured Groups
Graph-structured Groups

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

52 / 155

Three Scenarios

Non-overlapping Groups
Tree-structured Groups
Graph-structured Groups

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

52 / 155

Non-overlapping Groups
Assume G1 , . . . , GM are disjoint⇒ Each feature belongs to exactly one group

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

53 / 155

Non-overlapping Groups
Assume G1 , . . . , GM are disjoint⇒ Each feature belongs to exactly one groupΩ(w) =

PM

m=1 λm kwm k2

Trivial choices of groups recover unstructured regularizers:

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

53 / 155

Non-overlapping Groups
Assume G1 , . . . , GM are disjoint⇒ Each feature belongs to exactly one groupΩ(w) =

PM

m=1 λm kwm k2

Trivial choices of groups recover unstructured regularizers:`2 -regularization: one large group G1 = {1, . . . , D}
`1 -regularization: D singleton groups Gd = {d}Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

53 / 155

Non-overlapping Groups
Assume G1 , . . . , GM are disjoint⇒ Each feature belongs to exactly one groupΩ(w) =

PM

m=1 λm kwm k2

Trivial choices of groups recover unstructured regularizers:`2 -regularization: one large group G1 = {1, . . . , D}
`1 -regularization: D singleton groups Gd = {d}Examples of non-trivial groups:
label-based groups (groups are columns of a matrix)
template-based groups (next)

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

53 / 155

Example: Feature Template Selection

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

54 / 155

Example: Feature Template Selection
Input:
Output:

We
PRP
B-NP

want
VBP
B-VP

Martins, Figueiredo, Smith (IST, CMU)

to
TO
I-VP

exploreVB
I-VP

Structured Sparsity in NLP

the
DT
B-NP

feature
NN
I-NP

space
NN
I-NP

http://tiny.cc/ssnlp

54 / 155

Example: Feature Template Selection
Input:
Output:

We
PRP
B-NP

want
VBP
B-VP

to
TO
I-VP

explore
VB
I-VP

the
DT
B-NP

feature
NN
I-NP

space
NN
I-NP

Goal: Select relevant feature templates

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

54 / 155

Example: Feature Template Selection
Input:
Output:

We
PRP
B-NP

want
VBP
B-VP

to
TO
I-VP

5
explore
VB
I-VP

the
DT
B-NP

feature
NN
I-NP

space
NN
I-NP

Goal: Select relevant feature templates

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

54 / 155

Example: Feature Template Selection
Input:
Output:

We
PRP
B-NP

want
VBP
B-VP

to
TO
I-VP

5
explore
VB
I-VP

the
DT
B-NP

feature
NN
I-NP

space
NN
I-NP

Goal: Select relevant feature templates

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

54 / 155

Example: Feature Template Selection
Input:
Output:

We
PRP
B-NP

want
VBP
B-VP

to
TO
I-VP

explore
VB
I-VP

5
the
DT
B-NP

feature
NN
I-NP

space
NN
I-NP

Goal: Select relevant feature templates"explore the""the feature"

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

54 / 155

Example: Feature Template Selection
Input:
Output:

We
PRP
B-NP

want
VBP
B-VP

to
TO
I-VP

explore
VB
I-VP

the
DT
B-NP

feature
NN
I-NP

space
NN
I-NP

Goal: Select relevant feature templates"explore the""the feature"

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

54 / 155

Example: Feature Template Selection
Input:
Output:

We
PRP
B-NP

want
VBP
B-VP

to
TO
I-VP

5
explore
VB
I-VP

the
DT
B-NP

feature
NN
I-NP

space
NN
I-NP

Goal: Select relevant feature templates"explore the""the feature"

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

54 / 155

Example: Feature Template Selection
Input:
Output:

We
PRP
B-NP

want
VBP
B-VP

to
TO
I-VP

explore
VB
I-VP

5
the
DT
B-NP

feature
NN
I-NP

space
NN
I-NP

Goal: Select relevant feature templates"explore the""the feature""DT NN NN""VB DT NN"

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

54 / 155

Example: Feature Template Selection
Input:
Output:

We
PRP
B-NP

want
VBP
B-VP

to
TO
I-VP

explore
VB
I-VP

the
DT
B-NP

feature
NN
I-NP

space
NN
I-NP

Goal: Select relevant feature templates⇒ Make each group correspond to a feature template"explore the""the feature""DT NN NN""VB DT NN"

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

54 / 155

Example: Feature Template Selection
Input:
Output:

We
PRP
B-NP

want
VBP
B-VP

to
TO
I-VP

explore
VB
I-VP

the
DT
B-NP

feature
NN
I-NP

space
NN
I-NP

Goal: Select relevant feature templates⇒ Make each group correspond to a feature template"DT NN NN""VB DT NN"

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

54 / 155

Example: Feature Template Selection
Input:
Output:

We
PRP
B-NP

want
VBP
B-VP

to
TO
I-VP

explore
VB
I-VP

the
DT
B-NP

feature
NN
I-NP

space
NN
I-NP

Goal: Select relevant feature templates⇒ Make each group correspond to a feature template

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

54 / 155

Example: Feature Template Selection
Input:
Output:

We
PRP
B-NP

want
VBP
B-VP

to
TO
I-VP

explore
VB
I-VP

the
DT
B-NP

feature
NN
I-NP

space
NN
I-NP

Goal: Select relevant feature templates⇒ Make each group correspond to a feature template

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

54 / 155

Example: Feature Template Selection
Input:
Output:

We
PRP
B-NP

want
VBP
B-VP

to
TO
I-VP

explore
VB
I-VP

the
DT
B-NP

feature
NN
I-NP

space
NN
I-NP

Goal: Select relevant feature templates⇒ Make each group correspond to a feature template

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

54 / 155

Three Scenarios

Non-overlapping Groups
Tree-structured Groups
Graph-structured Groups

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

55 / 155

Three Scenarios

Non-overlapping Groups
Tree-structured Groups
Graph-structured Groups

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

55 / 155

Tree-Structured Groups
Assumption: if two groups overlap, one is contained in the other⇒ hierarchical structure (Kim and Xing, 2010; Mairal et al., 2010)

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

56 / 155

Tree-Structured Groups
Assumption: if two groups overlap, one is contained in the other⇒ hierarchical structure (Kim and Xing, 2010; Mairal et al., 2010)

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

56 / 155

Tree-Structured Groups
Assumption: if two groups overlap, one is contained in the other⇒ hierarchical structure (Kim and Xing, 2010; Mairal et al., 2010)

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

56 / 155

Tree-Structured Groups
Assumption: if two groups overlap, one is contained in the other⇒ hierarchical structure (Kim and Xing, 2010; Mairal et al., 2010)

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

56 / 155

Tree-Structured Groups
Assumption: if two groups overlap, one is contained in the other⇒ hierarchical structure (Kim and Xing, 2010; Mairal et al., 2010)

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

56 / 155

Tree-Structured Groups
Assumption: if two groups overlap, one is contained in the other⇒ hierarchical structure (Kim and Xing, 2010; Mairal et al., 2010)

What is the sparsity pattern?

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

56 / 155

Tree-Structured Groups
Assumption: if two groups overlap, one is contained in the other⇒ hierarchical structure (Kim and Xing, 2010; Mairal et al., 2010)

What is the sparsity pattern?
If a group is discarded, all its descendants are also discarded

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

56 / 155

Plate Notation

Typically used for graphical models, but also works here for representing
the Hasse diagram of tree-structured groups

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

57 / 155

Three Scenarios

Non-overlapping Groups
Tree-structured Groups
Graph-structured Groups

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

58 / 155

Three Scenarios

Non-overlapping Groups
Tree-structured Groups
Graph-structured Groups

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

58 / 155

Graph-Structured Groups
In general: groups can be represented as a directed acyclic graphset inclusion induces a partial order on groups (Jenatton et al., 2009)
feature space becomes a poset
sparsity patterns: given by this poset

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

59 / 155

Example: coarse-to-fine regularization
1

Define a partial order between basic feature templates (e.g., p0  w0 )2

Extend this partial order to all templates by lexicographic closure:p0  p0 p1  w0 w1

Goal: only include finer features if coarser ones are also in the modelMartins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

60 / 155

Things to Keep in Mind

Structured sparsity cares about the structure of the feature spaceGroup-Lasso regularization generalizes `1 and it’s still convex

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

61 / 155

Things to Keep in Mind

Structured sparsity cares about the structure of the feature spaceGroup-Lasso regularization generalizes `1 and it’s still convex
Choice of groups: problem dependent, opportunity to use priorknowledge to favour certain structural patterns

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

61 / 155

Things to Keep in Mind

Structured sparsity cares about the structure of the feature spaceGroup-Lasso regularization generalizes `1 and it’s still convex
Choice of groups: problem dependent, opportunity to use priorknowledge to favour certain structural patterns
Next: algorithms
We’ll see that optimization is easier with non-overlapping ortree-structured groups than with arbitrary overlaps

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

61 / 155

Outline
1

Introduction

2

Loss Functions and Sparsity

3

Structured Sparsity

4

Algorithms
Convex Analysis
Batch Algorithms
Online Algorithms

5

Applications

6

Conclusions

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

62 / 155

Learning the Model
Recall that learning involves solvingN

1 X
min Ω(w) +L(w, xi , yi ),w| {z }
Ni=1
regularizer |{z}total loss

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

63 / 155

Learning the Model
Recall that learning involves solvingN

1 X
min Ω(w) +L(w, xi , yi ),w| {z }
Ni=1
regularizer |{z}total loss

We’ll address two kinds of optimization algorithms:
batch algorithms (attacks the complete problem);
online algorithms (uses the training examples one by one)

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

63 / 155

Learning the Model
Recall that learning involves solvingN

1 X
min Ω(w) +L(w, xi , yi ),w| {z }
Ni=1
regularizer |{z}total loss

We’ll address two kinds of optimization algorithms:
batch algorithms (attacks the complete problem);
online algorithms (uses the training examples one by one)
Before that: we’ll review some key concepts of convex analysis

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

63 / 155

Outline
1

Introduction

2

Loss Functions and Sparsity

3

Structured Sparsity

4

Algorithms
Convex Analysis
Batch Algorithms
Online Algorithms

5

Applications

6

Conclusions

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

64 / 155

Key Concepts in Convex Analysis: Convex Sets

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

65 / 155

Key Concepts in Convex Analysis: Convex Functions

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

66 / 155

Key Concepts in Convex Analysis: Minimizers

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

67 / 155

Key Concepts in Convex Analysis: Subgradients
Convexity ⇒ continuity; convexity 6⇒ differentiability (e.g., f (w) = kw k1 ).
Subgradients generalize gradients for (maybe non-diff.) convex functions:

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

68 / 155

Key Concepts in Convex Analysis: Subgradients
Convexity ⇒ continuity; convexity 6⇒ differentiability (e.g., f (w) = kw k1 ).
Subgradients generalize gradients for (maybe non-diff.) convex functions:v is a subgradient of f at x if f (x0 ) ≥ f (x) + v> (x0 − x)
Subdifferential: ∂f (x) = {v : v is a subgradient of f at x}

linear lower boundMartins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

68 / 155

Key Concepts in Convex Analysis: Subgradients
Convexity ⇒ continuity; convexity 6⇒ differentiability (e.g., f (w) = kw k1 ).
Subgradients generalize gradients for (maybe non-diff.) convex functions:v is a subgradient of f at x if f (x0 ) ≥ f (x) + v> (x0 − x)
Subdifferential: ∂f (x) = {v : v is a subgradient of f at x}
If f is differentiable, ∂f (x) = {∇f (x)}linear lower boundMartins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

68 / 155

Key Concepts in Convex Analysis: Subgradients
Convexity ⇒ continuity; convexity 6⇒ differentiability (e.g., f (w) = kw k1 ).
Subgradients generalize gradients for (maybe non-diff.) convex functions:v is a subgradient of f at x if f (x0 ) ≥ f (x) + v> (x0 − x)
Subdifferential: ∂f (x) = {v : v is a subgradient of f at x}
If f is differentiable, ∂f (x) = {∇f (x)}linear lower boundMartins, Figueiredo, Smith (IST, CMU)

non-differentiable case

Structured Sparsity in NLP

http://tiny.cc/ssnlp

68 / 155

Key Concepts in Convex Analysis: Subgradients
Convexity ⇒ continuity; convexity 6⇒ differentiability (e.g., f (w) = kw k1 ).
Subgradients generalize gradients for (maybe non-diff.) convex functions:v is a subgradient of f at x if f (x0 ) ≥ f (x) + v> (x0 − x)
Subdifferential: ∂f (x) = {v : v is a subgradient of f at x}
If f is differentiable, ∂f (x) = {∇f (x)}linear lower boundnon-differentiable case˜ (x) is a subgradient of f at x
Notation: ∇fMartins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

68 / 155

Key Concepts in Convex Analysis: Strong Convexity
Recall the definition of convex function: ∀λ ∈ [0, 1],f (λx + (1 − λ)x 0 ) ≤ λf (x) + (1 − λ)f (x 0 )convexity

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

69 / 155

Key Concepts in Convex Analysis: Strong Convexity
Recall the definition of convex function: ∀λ ∈ [0, 1],f (λx + (1 − λ)x 0 ) ≤ λf (x) + (1 − λ)f (x 0 )A β−strongly convex function satisfies a stronger condition: ∀λ ∈ [0, 1]
f (λx + (1 − λ)x 0 ) ≤ λf (x) + (1 − λ)f (x 0 ) −convexity

Martins, Figueiredo, Smith (IST, CMU)βλ(1 − λ)kx − x 0 k22
2strong convexity

Structured Sparsity in NLP

http://tiny.cc/ssnlp

69 / 155

Key Concepts in Convex Analysis: Strong Convexity
Recall the definition of convex function: ∀λ ∈ [0, 1],f (λx + (1 − λ)x 0 ) ≤ λf (x) + (1 − λ)f (x 0 )A β−strongly convex function satisfies a stronger condition: ∀λ ∈ [0, 1]
f (λx + (1 − λ)x 0 ) ≤ λf (x) + (1 − λ)f (x 0 ) −convexity

strong convexity

Strong convexity
Martins, Figueiredo, Smith (IST, CMU)βλ(1 − λ)kx − x 0 k22
2⇒strict convexity.
6⇐

Structured Sparsity in NLP

http://tiny.cc/ssnlp

69 / 155

Proximity Operators
Let Ω : RD → R̄ be a convex function.

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

70 / 155

Proximity Operators
Let Ω : RD → R̄ be a convex function.
The Ω-proximity operator is the following RD → RD map:1
w 7→ proxΩ (w) = arg min ku − wk22 + Ω(u)u 2...always well defined, because ku − wk22 is strictly convex.

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

70 / 155

Proximity Operators
Let Ω : RD → R̄ be a convex function.
The Ω-proximity operator is the following RD → RD map:1
w 7→ proxΩ (w) = arg min ku − wk22 + Ω(u)u 2...always well defined, because ku − wk22 is strictly convex.
Classical examples:
Squared `2 regularization, Ω(w) = λ2 kwk22 : scaling operation
proxΩ (w) =Martins, Figueiredo, Smith (IST, CMU)

1
w
1+λ

Structured Sparsity in NLP

http://tiny.cc/ssnlp

70 / 155

Proximity Operators
Let Ω : RD → R̄ be a convex function.
The Ω-proximity operator is the following RD → RD map:1
w 7→ proxΩ (w) = arg min ku − wk22 + Ω(u)u 2...always well defined, because ku − wk22 is strictly convex.
Classical examples:
Squared `2 regularization, Ω(w) = λ2 kwk22 : scaling operation
proxΩ (w) =

1
w
1+λ

`1 regularization, Ω(w) = λkwk1 : soft-thresholding;proxΩ (w) = soft(w, λ)Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

70 / 155

Proximity Operators (II)1prox Ω (w) = arg min ku − wk22 + Ω(u)u 2Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

71 / 155

Proximity Operators (II)1prox Ω (w) = arg min ku − wk22 + Ω(u)u 2`2 regularization, Ω(w) = λkwk2 : vector soft thresholding0⇐ kwk ≤ λproxΩ (w) =w
kwk (kwk − λ) ⇐ kwk > λMartins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

71 / 155

Proximity Operators (II)1prox Ω (w) = arg min ku − wk22 + Ω(u)u 2`2 regularization, Ω(w) = λkwk2 : vector soft thresholding0⇐ kwk ≤ λproxΩ (w) =w
kwk (kwk − λ) ⇐ kwk > λ

0
⇐ w∈S
indicator function, Ω(w) = ιS (w) =+∞ ⇐ w 6∈ SproxΩ (w) = PS (w)Euclidean projection
Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

71 / 155

Proximity Operators (III)Group regularizers: Ω(w) =MXΩj (wGm )m=1

Groups: Gm ⊂ {1, 2, ..., D}.

Martins, Figueiredo, Smith (IST, CMU)

wGm is a sub-vector of w.

Structured Sparsity in NLP

http://tiny.cc/ssnlp

72 / 155

Proximity Operators (III)Group regularizers: Ω(w) =MXΩj (wGm )m=1

Groups: Gm ⊂ {1, 2, ..., D}.

wGm is a sub-vector of w.

Non-overlapping groups (Gm ∩ Gn = ∅, for m 6= n): separable prox
operator[proxΩ (w)]Gm = proxΩm (wGm )Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

72 / 155

Proximity Operators (III)Group regularizers: Ω(w) =MXΩj (wGm )m=1

Groups: Gm ⊂ {1, 2, ..., D}.

wGm is a sub-vector of w.

Non-overlapping groups (Gm ∩ Gn = ∅, for m 6= n): separable prox
operator[proxΩ (w)]Gm = proxΩm (wGm )Tree-structured groups: (two groups are either non-overlapping or
one contais the other) proxΩ can be computed recursively (Jenatton
et al., 2011).

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

72 / 155

Proximity Operators (III)Group regularizers: Ω(w) =MXΩj (wGm )m=1

Groups: Gm ⊂ {1, 2, ..., D}.

wGm is a sub-vector of w.

Non-overlapping groups (Gm ∩ Gn = ∅, for m 6= n): separable prox
operator[proxΩ (w)]Gm = proxΩm (wGm )Tree-structured groups: (two groups are either non-overlapping or
one contais the other) proxΩ can be computed recursively (Jenatton
et al., 2011).
Arbitrary groups:
For Ωj (wGm ) = kwGm k2 : solved via convex smooth optimization (Yuanet al., 2011).
Sequential proximity steps (Martins et al., 2011a) (more later).

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

72 / 155

Outline
1

Introduction

2

Loss Functions and Sparsity

3

Structured Sparsity

4

Algorithms
Convex Analysis
Batch Algorithms
Online Algorithms

5

Applications

6

Conclusions

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

73 / 155

Subgradient Methods
minw Ω(w) + Λ(w), where Λ(w) = N1

Martins, Figueiredo, Smith (IST, CMU)

PN

Structured Sparsity in NLP

i=1 L(w, xi , yi ) (loss)

http://tiny.cc/ssnlp

74 / 155

Subgradient Methods
minw Ω(w) + Λ(w), where Λ(w) = N1PN

i=1 L(w, xi , yi ) (loss)

Subgradient methods were invented by Shor in the 1970’s (Shor, 1985):
input: stepsize sequence (ηt )T
t=1
initialize w
for t = 1, 2, . . . do˜˜
(sub-)gradient step: w ← w − ηt ∇Ω(w)+ ∇Λ(w)end forMartins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

74 / 155

Subgradient Methods
minw Ω(w) + Λ(w), where Λ(w) = N1PN

i=1 L(w, xi , yi ) (loss)

Subgradient methods were invented by Shor in the 1970’s (Shor, 1985):
input: stepsize sequence (ηt )T
t=1
initialize w
for t = 1, 2, . . . do˜˜
(sub-)gradient step: w ← w − ηt ∇Ω(w)+ ∇Λ(w)end forKey disadvantages:
The step size ηt needs to be annealed for convergence: very slow!
Doesn’t explicitly capture the sparsity promoted by `1 regularizers.

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

74 / 155

(Block-)Coordinate Descentminw Ω(w) + Λ(w), where Λ(w) = N1

Martins, Figueiredo, Smith (IST, CMU)

PN

Structured Sparsity in NLP

i=1 L(w, xi , yi ) (loss)

http://tiny.cc/ssnlp

75 / 155

(Block-)Coordinate Descentminw Ω(w) + Λ(w), where Λ(w) = N1PN

i=1 L(w, xi , yi ) (loss)

Update one (block of) component(s) of w at a time:
winew ← arg min Ω([w1 , ..., wi , ...wD ]) + Λ([w1 , ..., wi , ...wD ])wi(Genkin et al., 2007; Krishnapuram et al., 2005; Liu et al., 2009; Shevade andKeerthi, 2003; Tseng and Yun, 2009; Yun and Toh, 2011)

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

75 / 155

(Block-)Coordinate Descentminw Ω(w) + Λ(w), where Λ(w) = N1PN

i=1 L(w, xi , yi ) (loss)

Update one (block of) component(s) of w at a time:
winew ← arg min Ω([w1 , ..., wi , ...wD ]) + Λ([w1 , ..., wi , ...wD ])wi(Genkin et al., 2007; Krishnapuram et al., 2005; Liu et al., 2009; Shevade andKeerthi, 2003; Tseng and Yun, 2009; Yun and Toh, 2011)

Squared error loss: closed-form solution. Other losses (e.g., logistic):solve numerically, e.g., Newton steps (Shevade and Keerthi, 2003).
use local quadratic approximation/bound (Krishnapuram et al., 2005;
Tseng and Yun, 2009; Yun and Toh, 2011).

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

75 / 155

(Block-)Coordinate Descentminw Ω(w) + Λ(w), where Λ(w) = N1PN

i=1 L(w, xi , yi ) (loss)

Update one (block of) component(s) of w at a time:
winew ← arg min Ω([w1 , ..., wi , ...wD ]) + Λ([w1 , ..., wi , ...wD ])wi(Genkin et al., 2007; Krishnapuram et al., 2005; Liu et al., 2009; Shevade andKeerthi, 2003; Tseng and Yun, 2009; Yun and Toh, 2011)

Squared error loss: closed-form solution. Other losses (e.g., logistic):solve numerically, e.g., Newton steps (Shevade and Keerthi, 2003).
use local quadratic approximation/bound (Krishnapuram et al., 2005;
Tseng and Yun, 2009; Yun and Toh, 2011).
Shown to converge; competitive with state-of-the-art (Yun and Toh, 2011).
Has been used in NLP: Sokolovska et al. (2010); Lavergne et al. (2010).
Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

75 / 155

Projected GradientInstead of min Ω(w) + Λ(w) , tackle min Λ(w) subject to Ω(w) ≤ τ .
w

Martins, Figueiredo, Smith (IST, CMU)w

Structured Sparsity in NLP

http://tiny.cc/ssnlp

76 / 155

Projected GradientInstead of min Ω(w) + Λ(w) , tackle min Λ(w) subject to Ω(w) ≤ τ .
w

w

Building blocks:
˜
loss gradient ∇Λ(w)
Euclidean projection PS (w), where S = {w : Ω(w) ≤ τ }Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

76 / 155

Projected GradientInstead of min Ω(w) + Λ(w) , tackle min Λ(w) subject to Ω(w) ≤ τ .
w

w

Building blocks:
˜
loss gradient ∇Λ(w)
Euclidean projection PS (w), where S = {w : Ω(w) ≤ τ }˜w ← PS (w − η ∇Λ(w))...maybe using line search to adjust the step length.

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

76 / 155

Projected GradientInstead of min Ω(w) + Λ(w) , tackle min Λ(w) subject to Ω(w) ≤ τ .
w

w

Building blocks:
˜
loss gradient ∇Λ(w)
Euclidean projection PS (w), where S = {w : Ω(w) ≤ τ }˜w ← PS (w − η ∇Λ(w))...maybe using line search to adjust the step length.
Example: for S = {w : kwk1 ≤ τ }, projection PS (w) has O(D log D) cost
(Duchi et al., 2008).
Viable and competitive alternative, which has been used in machinelearning and NLP (Duchi et al., 2008; Quattoni et al., 2009).

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

76 / 155

Projected GradientInstead of min Ω(w) + Λ(w) , tackle min Λ(w) subject to Ω(w) ≤ τ .
w

w

Building blocks:
˜
loss gradient ∇Λ(w)
Euclidean projection PS (w), where S = {w : Ω(w) ≤ τ }˜w ← PS (w − η ∇Λ(w))...maybe using line search to adjust the step length.
Example: for S = {w : kwk1 ≤ τ }, projection PS (w) has O(D log D) cost
(Duchi et al., 2008).
Viable and competitive alternative, which has been used in machinelearning and NLP (Duchi et al., 2008; Quattoni et al., 2009).
Shown later: projected gradient is a particular instance of the moregeneral proximal gradient methods.
Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

76 / 155

From Gradient to Hessian: Newton’s Method
Assume F (w) = Ω(w) + Λ(w) is twice-differentiable.
Second order (quadratic) Taylor expansion around w0 :1>F (w) ≈ F (w0 ) + ∇F (w0 ) (w − w0 ) + (w − w0 )> H(w0 ) (w − w0 )| {z }| {z }
2
Gradient

Martins, Figueiredo, Smith (IST, CMU)

Hessian:

Structured Sparsity in NLP

http://tiny.cc/ssnlp

77 / 155

From Gradient to Hessian: Newton’s Method
Assume F (w) = Ω(w) + Λ(w) is twice-differentiable.
Second order (quadratic) Taylor expansion around w0 :1>F (w) ≈ F (w0 ) + ∇F (w0 ) (w − w0 ) + (w − w0 )> H(w0 ) (w − w0 )| {z }| {z }
2
Gradient

Hessian:

Use the direction that minimizes this quadratic approximation:w ← w − α(H(w))−1 ∇F (w)with stepsize α usually determined by line search.

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

77 / 155

From Gradient to Hessian: Newton’s Method
Assume F (w) = Ω(w) + Λ(w) is twice-differentiable.
Second order (quadratic) Taylor expansion around w0 :1>F (w) ≈ F (w0 ) + ∇F (w0 ) (w − w0 ) + (w − w0 )> H(w0 ) (w − w0 )| {z }| {z }
2
Gradient

Hessian:

Use the direction that minimizes this quadratic approximation:w ← w − α(H(w))−1 ∇F (w)with stepsize α usually determined by line search.
Drawback: may be costly (or impossible) to compute and invert the
Hessian! O(D 3 ) for a naı̈ve approach.

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

77 / 155

From Gradient to Hessian: Newton’s Method
Assume F (w) = Ω(w) + Λ(w) is twice-differentiable.
Second order (quadratic) Taylor expansion around w0 :1>F (w) ≈ F (w0 ) + ∇F (w0 ) (w − w0 ) + (w − w0 )> H(w0 ) (w − w0 )| {z }| {z }
2
Gradient

Hessian:

Use the direction that minimizes this quadratic approximation:w ← w − α(H(w))−1 ∇F (w)with stepsize α usually determined by line search.
Drawback: may be costly (or impossible) to compute and invert the
Hessian! O(D 3 ) for a naı̈ve approach.
Quasi-Newton methods, namely L-BFGS, approximate the inverse
Hessian directly from past gradient information.
Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

77 / 155

Orthant-Wise Limited-memory Quasi Newton
OWL-QN: clever adaptation of L-BFGS to `1 -regularization (Andrew andGao, 2007; Gao et al., 2007)

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

78 / 155

Orthant-Wise Limited-memory Quasi Newton
OWL-QN: clever adaptation of L-BFGS to `1 -regularization (Andrew andGao, 2007; Gao et al., 2007)
input: stepsize sequence (ηt )T
t=1
initialize w = 0
for t = 1, 2, . . . do˜˜compute a particular subgradient gt := ∇Ω(w)+ ∇Λ(w)
compute inverse Hessian approximation St “a la L-BFGS”
compute descent direction dt = −(St ) gt
do line search for α, and update w ← w + αdt
clip w if necessary to stay in the same orthantend forMartins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

78 / 155

Orthant-Wise Limited-memory Quasi Newton
OWL-QN: clever adaptation of L-BFGS to `1 -regularization (Andrew andGao, 2007; Gao et al., 2007)
input: stepsize sequence (ηt )T
t=1
initialize w = 0
for t = 1, 2, . . . do˜˜compute a particular subgradient gt := ∇Ω(w)+ ∇Λ(w)
compute inverse Hessian approximation St “a la L-BFGS”
compute descent direction dt = −(St ) gt
do line search for α, and update w ← w + αdt
clip w if necessary to stay in the same orthantend for

Pros: provably convergent; updates are sparse due to the clipping.
Cons: not applicable to group-regularizers.
Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

78 / 155

Proximal Gradient
Recall the problem: min Ω(w) + Λ(w)w

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

79 / 155

Proximal Gradient
Recall the problem: min Ω(w) + Λ(w)w

Key assumptions: ∇Λ(w) and proxΩ “easy”.

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

79 / 155

Proximal Gradient
Recall the problem: min Ω(w) + Λ(w)w

Key assumptions: ∇Λ(w) and proxΩ “easy”.
wt+1 ← proxηt Ω (wt − ηt ∇Λ(wt ))Key feature: each steps decouples the loss and the regularizer.

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

79 / 155

Proximal Gradient
Recall the problem: min Ω(w) + Λ(w)w

Key assumptions: ∇Λ(w) and proxΩ “easy”.
wt+1 ← proxηt Ω (wt − ηt ∇Λ(wt ))Key feature: each steps decouples the loss and the regularizer.

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

79 / 155

Proximal Gradient
Recall the problem: min Ω(w) + Λ(w)w

Key assumptions: ∇Λ(w) and proxΩ “easy”.
wt+1 ← proxηt Ω (wt − ηt ∇Λ(wt ))Key feature: each steps decouples the loss and the regularizer.
Projected gradient is a particular case, for proxΩ = PS .

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

79 / 155

Proximal Gradient
Recall the problem: min Ω(w) + Λ(w)w

Key assumptions: ∇Λ(w) and proxΩ “easy”.
wt+1 ← proxηt Ω (wt − ηt ∇Λ(wt ))Key feature: each steps decouples the loss and the regularizer.
Projected gradient is a particular case, for proxΩ = PS .
Can be derived with different tools:
expectation-maximization (EM) (Figueiredo and Nowak, 2003);
majorization-minimization (Daubechies et al., 2004);
forward-backward splitting (Combettes and Wajs, 2006);
separable approximation (Wright et al., 2009).
Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

79 / 155

Majorization-Minimization Derivation
Assume Λ(w) has L-Lipschitz gradient: k∇Λ(w) − ∇Λ(w0 )k ≤ Lkw − w0 k.
Separable 2nd order approximation of Λ(w) around wt
Λ(w0 ) + (w − wt )> ∇Λ(w0 ) +Martins, Figueiredo, Smith (IST, CMU)

1kw − w0 k2 = Q(w, wt )2ηtStructured Sparsity in NLP

http://tiny.cc/ssnlp

80 / 155

Majorization-Minimization Derivation
Assume Λ(w) has L-Lipschitz gradient: k∇Λ(w) − ∇Λ(w0 )k ≤ Lkw − w0 k.
Separable 2nd order approximation of Λ(w) around wt
Λ(w0 ) + (w − wt )> ∇Λ(w0 ) +1
kw − w0 k2 = Q(w, wt ) ≥ Λ(w)2ηt

if ηt ≤ 1/L, with equality for w = wt .

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

80 / 155

Majorization-Minimization Derivation
Assume Λ(w) has L-Lipschitz gradient: k∇Λ(w) − ∇Λ(w0 )k ≤ Lkw − w0 k.
Separable 2nd order approximation of Λ(w) around wt
Λ(w0 ) + (w − wt )> ∇Λ(w0 ) +1
kw − w0 k2 = Q(w, wt ) ≥ Λ(w)2ηt

if ηt ≤ 1/L, with equality for w = wt .
Consequently, if wt+1 = arg minw Q(w, wt ) + Ω(w),Λ(wt+1 ) + Ω(wt+1 ) ≤ Q(wt+1 , wt ) + Ω(wt+1 )≤ Q(wt , wt ) + Ω(w1 ) = Λ(wt ) + Ω(wt )Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

80 / 155

Majorization-Minimization Derivation
Assume Λ(w) has L-Lipschitz gradient: k∇Λ(w) − ∇Λ(w0 )k ≤ Lkw − w0 k.
Separable 2nd order approximation of Λ(w) around wt
Λ(w0 ) + (w − wt )> ∇Λ(w0 ) +1
kw − w0 k2 = Q(w, wt ) ≥ Λ(w)2ηt

if ηt ≤ 1/L, with equality for w = wt .
Consequently, if wt+1 = arg minw Q(w, wt ) + Ω(w),Λ(wt+1 ) + Ω(wt+1 ) ≤ Q(wt+1 , wt ) + Ω(wt+1 )≤ Q(wt , wt ) + Ω(w1 ) = Λ(wt ) + Ω(wt )Easy to show that
wt+1 = arg min Q(w, wt ) + Ω(w) = proxηt Ω (wt − ηt ∇Λ(wt )) .
w

Thus, with ηt ≤ 1/L: objective monotonically decreases.
Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

80 / 155

Monotonicity and Convergence
Proximal gradient, a.k.a., iterative shrinkage thresholding (IST):
wt+1 ← proxηt Ω (wt − ηt ∇Λ(wt )) .
Monotonicity: if ηt ≤ 1/L, then Λ(wt+1 ) + Ω(wt+1 ) ≤ Λ(wt ) + Ω(wt ).

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

81 / 155

Monotonicity and Convergence
Proximal gradient, a.k.a., iterative shrinkage thresholding (IST):
wt+1 ← proxηt Ω (wt − ηt ∇Λ(wt )) .
Monotonicity: if ηt ≤ 1/L, then Λ(wt+1 ) + Ω(wt+1 ) ≤ Λ(wt ) + Ω(wt ).
Convergence of objective value (Beck and Teboulle, 2009)
 


1
∗
∗
Λ(wt ) + Ω(wt ) − Λ(w ) + Ω(w ) = O
tMartins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

81 / 155

Monotonicity and Convergence
Proximal gradient, a.k.a., iterative shrinkage thresholding (IST):
wt+1 ← proxηt Ω (wt − ηt ∇Λ(wt )) .
Monotonicity: if ηt ≤ 1/L, then Λ(wt+1 ) + Ω(wt+1 ) ≤ Λ(wt ) + Ω(wt ).
Convergence of objective value (Beck and Teboulle, 2009)
 


1
∗
∗
Λ(wt ) + Ω(wt ) − Λ(w ) + Ω(w ) = O
t
Important: monotonicity doesn’t imply convergence of w1 , w2 , ..., wt , ....
Convergence (even with inexact steps) proved for ηt ≤ 2/L (Combettes
and Wajs, 2006).

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

81 / 155

Accelerating IST: SpaRSA
The step sizes ηt ≤ 2/L (guarantees convergence) and ηt ≤ 1/L(monotonicity) are too conservative.

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

82 / 155

Accelerating IST: SpaRSA
The step sizes ηt ≤ 2/L (guarantees convergence) and ηt ≤ 1/L(monotonicity) are too conservative.
A bolder choice: let ηt mimic a Newton step (Barzilai and Borwein, 1988),
1
I ∼ H(wt ) (Hessian)ηtMartins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

82 / 155

Accelerating IST: SpaRSA
The step sizes ηt ≤ 2/L (guarantees convergence) and ηt ≤ 1/L(monotonicity) are too conservative.
A bolder choice: let ηt mimic a Newton step (Barzilai and Borwein, 1988),
1
I ∼ H(wt ) (Hessian)ηtApproximation in the mean squared sense over the previous step:
1= arg min kα(wt − wt−1 ) − (∇Λ(wt ) − ∇Λ(wt−1 ))k2αηtMartins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

82 / 155

Accelerating IST: SpaRSA
The step sizes ηt ≤ 2/L (guarantees convergence) and ηt ≤ 1/L(monotonicity) are too conservative.
A bolder choice: let ηt mimic a Newton step (Barzilai and Borwein, 1988),
1
I ∼ H(wt ) (Hessian)ηtApproximation in the mean squared sense over the previous step:
1= arg min kα(wt − wt−1 ) − (∇Λ(wt ) − ∇Λ(wt−1 ))k2αηtResulting algorithm: SpaRSA (sparse reconstruction by separable
approximation); shown to converge (with a safeguard) and to be fast
Wright et al. (2009).
Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

82 / 155

Accelerating IST: FISTA
Idea: compute wt+1 based, not only on wt , but also on wt−1 .

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

83 / 155

Accelerating IST: FISTA
Idea: compute wt+1 based, not only on wt , but also on wt−1 .
Fast IST algorithm (FISTA) (Beck and Teboulle, 2009):√
1+ 1+4 bt2
bt+1 =
2−1z= wt + bbtt+1(wt − wt−1 )wt+1 = proxηΩ (z − η∇Λ(z))

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

83 / 155

Accelerating IST: FISTA
Idea: compute wt+1 based, not only on wt , but also on wt−1 .
Fast IST algorithm (FISTA) (Beck and Teboulle, 2009):√
1+ 1+4 bt2
bt+1 =
2−1z= wt + bbtt+1(wt − wt−1 )wt+1 = proxηΩ (z − η∇Λ(z))
Convergence of objective value (Beck and Teboulle, 2009)
 


1
∗
∗
Λ(wt ) + Ω(wt ) − Λ(w ) + Ω(w ) = O(vs O(1/t) for IST)t2
Convergence of iterates has not been shown.

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

83 / 155

Accelerating IST: FISTA
Idea: compute wt+1 based, not only on wt , but also on wt−1 .
Fast IST algorithm (FISTA) (Beck and Teboulle, 2009):√
1+ 1+4 bt2
bt+1 =
2−1z= wt + bbtt+1(wt − wt−1 )wt+1 = proxηΩ (z − η∇Λ(z))
Convergence of objective value (Beck and Teboulle, 2009)
 


1
∗
∗
Λ(wt ) + Ω(wt ) − Λ(w ) + Ω(w ) = O(vs O(1/t) for IST)t2
Convergence of iterates has not been shown.
Another two-step method: TwIST (two-step IST) (Bioucas-Dias andFigueiredo, 2007).
Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

83 / 155

Least Angle Regression (LARS)LARS only applies to ŵ(λ) = arg min λkwk1 + kAw − yk2wMartins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

84 / 155

Least Angle Regression (LARS)LARS only applies to ŵ(λ) = arg min λkwk1 + kAw − yk2w

Key ideas (Efron et al., 2004; Osborne et al., 2000)“regularization path” ŵ(λ) is piecewise linear (Markowitz, 1952);
the cusps can be identified in closed form;
simply jump from one cusp to the next.

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

84 / 155

Least Angle Regression (LARS)LARS only applies to ŵ(λ) = arg min λkwk1 + kAw − yk2w

Key ideas (Efron et al., 2004; Osborne et al., 2000)“regularization path” ŵ(λ) is piecewise linear (Markowitz, 1952);
the cusps can be identified in closed form;
simply jump from one cusp to the next.

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

84 / 155

Least Angle Regression (LARS)LARS only applies to ŵ(λ) = arg min λkwk1 + kAw − yk2w

Key ideas (Efron et al., 2004; Osborne et al., 2000)“regularization path” ŵ(λ) is piecewise linear (Markowitz, 1952);
the cusps can be identified in closed form;
simply jump from one cusp to the next.

Cons: doesn’t apply to group regularizers; exponential worst casecomplexity (Mairal and Yu, 2012).
Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

84 / 155

Homotopy/Continuation Methods
LARS is related to a more general family: homotopy/continuation
methods.
Consider ŵ(λ) = arg min λΩ̄(w) + Λ(w)w

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

85 / 155

Homotopy/Continuation Methods
LARS is related to a more general family: homotopy/continuation
methods.
Consider ŵ(λ) = arg min λΩ̄(w) + Λ(w)w

Key ideas
start with high value of λ, such that ŵ(λ) is easy (e.g., zero);slowly decrease λ while “tracking” the solution;“tracking” means: use the previous ŵ(λ) to “warm start” the solver
for the next problem.

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

85 / 155

Homotopy/Continuation Methods
LARS is related to a more general family: homotopy/continuation
methods.
Consider ŵ(λ) = arg min λΩ̄(w) + Λ(w)w

Key ideas
start with high value of λ, such that ŵ(λ) is easy (e.g., zero);slowly decrease λ while “tracking” the solution;“tracking” means: use the previous ŵ(λ) to “warm start” the solver
for the next problem.
It’s a meta-algorithm of general applicability when using “warm startable”
solvers (Figueiredo et al., 2007; Hale et al., 2008; Osborne et al., 2000).

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

85 / 155

Some Stuff We Didn’t Talk About

shooting method (Fu, 1998);
grafting (Perkins et al., 2003) and grafting-light (Zhu et al., 2010);
forward stagewise regression (Hastie et al., 2007);
alternating direction method of multipliers (ADMM) (Figueiredo andBioucas-Dias, 2011).

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

86 / 155

Some Stuff We Didn’t Talk About

shooting method (Fu, 1998);
grafting (Perkins et al., 2003) and grafting-light (Zhu et al., 2010);
forward stagewise regression (Hastie et al., 2007);
alternating direction method of multipliers (ADMM) (Figueiredo andBioucas-Dias, 2011).
Next: We’ll talk about online algorithms.

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

86 / 155

Outline
1

Introduction

2

Loss Functions and Sparsity

3

Structured Sparsity

4

Algorithms
Convex Analysis
Batch Algorithms
Online Algorithms

5

Applications

6

Conclusions

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

87 / 155

Why Online?

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

88 / 155

Why Online?

1

Suitable for large datasets

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

88 / 155

Why Online?

1

Suitable for large datasets

2

Suitable for structured prediction

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

88 / 155

Why Online?

1

Suitable for large datasets

2

Suitable for structured prediction

3

Faster to approach a near-optimal region

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

88 / 155

Why Online?

1

Suitable for large datasets

2

Suitable for structured prediction

Faster to approach a near-optimal region
4 Slower convergence, but this is fine in machine learning3

cf. “the tradeoffs of large scale learning” (Bottou and Bousquet, 2007)

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

88 / 155

Why Online?

1

Suitable for large datasets

2

Suitable for structured prediction

Faster to approach a near-optimal region
4 Slower convergence, but this is fine in machine learning3

cf. “the tradeoffs of large scale learning” (Bottou and Bousquet, 2007)

What we will say can be straighforwardly extended to the mini-batch case.
Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

88 / 155

Plain Stochastic (Sub-)Gradient Descent
N

min
w

1 X
Ω(w) +L(w, xi , yi ),| {z }
Ni=1
regularizer |{z}empirical loss

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

89 / 155

Plain Stochastic (Sub-)Gradient Descent
N

min
w

1 X
Ω(w) +L(w, xi , yi ),| {z }
Ni=1
regularizer |{z}empirical loss

input: stepsize sequence (ηt )T
t=1
initialize w = 0
for t = 1, 2, . . . dotake training pair (xt , yt )˜˜(sub-)gradient step: w ← w − ηt ∇Ω(w)+ ∇L(w;
xt , yt )end forMartins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

89 / 155

What’s the Problem with SGD?
˜˜+ ∇L(w;
xt , yt )(Sub-)gradient step: w ← w − ηt ∇Ω(w)Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

90 / 155

What’s the Problem with SGD?
˜˜+ ∇L(w;
xt , yt )(Sub-)gradient step: w ← w − ηt ∇Ω(w)˜`2 -regularization Ω(w) = λ2 kwk22 =⇒ ∇Ω(w)= λw
˜w ← (1 − ηt λ)w − ηt ∇L(w;xt , yt )| {z }
scaling

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

90 / 155

What’s the Problem with SGD?
˜˜+ ∇L(w;
xt , yt )(Sub-)gradient step: w ← w − ηt ∇Ω(w)˜`2 -regularization Ω(w) = λ2 kwk22 =⇒ ∇Ω(w)= λw
˜w ← (1 − ηt λ)w − ηt ∇L(w;xt , yt )| {z }
scaling˜`1 -regularization Ω(w) = λkwk1 =⇒ ∇Ω(w)= λsign(w)˜w ← w − ηt λsign(w) − ηt ∇L(w;xt , yt )|{z}
constant penalty

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

90 / 155

What’s the Problem with SGD?
˜˜+ ∇L(w;
xt , yt )(Sub-)gradient step: w ← w − ηt ∇Ω(w)˜`2 -regularization Ω(w) = λ2 kwk22 =⇒ ∇Ω(w)= λw
˜w ← (1 − ηt λ)w − ηt ∇L(w;xt , yt )| {z }
scaling˜`1 -regularization Ω(w) = λkwk1 =⇒ ∇Ω(w)= λsign(w)˜w ← w − ηt λsign(w) − ηt ∇L(w;xt , yt )|{z}
constant penalty

Problem: iterates are never sparse!

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

90 / 155

Plain SGD with `2 -regularization

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

91 / 155

Plain SGD with `2 -regularization

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

91 / 155

Plain SGD with `2 -regularization

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

91 / 155

Plain SGD with `2 -regularization

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

91 / 155

Plain SGD with `2 -regularization

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

91 / 155

Plain SGD with `2 -regularization

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

91 / 155

Plain SGD with `2 -regularization

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

91 / 155

Plain SGD with `2 -regularization

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

91 / 155

Plain SGD with `2 -regularization

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

91 / 155

Plain SGD with `2 -regularization

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

91 / 155

Plain SGD with `1 -regularization

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

92 / 155

Plain SGD with `1 -regularization

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

92 / 155

Plain SGD with `1 -regularization

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

92 / 155

Plain SGD with `1 -regularization

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

92 / 155

Plain SGD with `1 -regularization

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

92 / 155

Plain SGD with `1 -regularization

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

92 / 155

Plain SGD with `1 -regularization

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

92 / 155

Plain SGD with `1 -regularization

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

92 / 155

Plain SGD with `1 -regularization

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

92 / 155

Plain SGD with `1 -regularization

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

92 / 155

“Sparse” Online Algorithms

SGD with Cumulative Penalty (Tsuruoka et al., 2009)
Truncated Gradient (Langford et al., 2009)
Online Forward-Backward Splitting (Duchi and Singer, 2009)
Regularized Dual Averaging (Xiao, 2010)
Online Proximal Gradient (Martins et al., 2011a)

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

93 / 155

“Sparse” Online Algorithms

SGD with Cumulative Penalty (Tsuruoka et al., 2009)
Truncated Gradient (Langford et al., 2009)
Online Forward-Backward Splitting (Duchi and Singer, 2009)
Regularized Dual Averaging (Xiao, 2010)
Online Proximal Gradient (Martins et al., 2011a)

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

93 / 155

Cumulative Penalties (Tsuruoka et al., 2009)an attempt to reconcile SGD and `1 regularizarion, maintaining
algorithmic efficiency
computational trick: accumulates the penalties, and applies them
all at once when a feature fires (due to Carpenter (2008))
clipping: if the total penalty is greater than the magnitude of thefeature weight wj , clip wj to zerobut store the amount of clipping for future use.

leads to very sparse models
however: no proof of convergence

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

94 / 155

Cumulative Penalties (Tsuruoka et al., 2009)

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

95 / 155

Cumulative Penalties (Tsuruoka et al., 2009)

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

95 / 155

Cumulative Penalties (Tsuruoka et al., 2009)

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

95 / 155

Cumulative Penalties (Tsuruoka et al., 2009)

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

95 / 155

Cumulative Penalties (Tsuruoka et al., 2009)

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

95 / 155

Cumulative Penalties (Tsuruoka et al., 2009)

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

95 / 155

Cumulative Penalties (Tsuruoka et al., 2009)

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

95 / 155

Cumulative Penalties (Tsuruoka et al., 2009)

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

95 / 155

Cumulative Penalties (Tsuruoka et al., 2009)

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

95 / 155

Cumulative Penalties (Tsuruoka et al., 2009)

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

95 / 155

“Sparse” Online Algorithms

SGD with Cumulative Penalty (Tsuruoka et al., 2009)
Truncated Gradient (Langford et al., 2009)
Online Forward-Backward Splitting (Duchi and Singer, 2009)
Regularized Dual Averaging (Xiao, 2010)
Online Proximal Gradient (Martins et al., 2011a)

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

96 / 155

Truncated Gradient (Langford et al., 2009)
input: laziness coefficient K , stepsize sequence (ηt )T
t=1
initialize w = 0
for t = 1, 2, . . . dotake training pair (xt , yt )˜(sub-)gradient step: w ← w − ηt ∇L(θ;xt , yt )if t/K is integer thentruncation step: w ← w − sign(w) (|w| − ηt K τ ){z}|soft-thresholding

end ifend fortake gradients only with respect to the loss
every K rounds: a “lazy” soft-thresholding stepLangford et al. (2009) also suggest other forms of truncation
converges to -accurate objective after O(1/2 ) iterations
Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

97 / 155

Truncated Gradient (Langford et al., 2009)

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

98 / 155

Truncated Gradient (Langford et al., 2009)

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

98 / 155

Truncated Gradient (Langford et al., 2009)

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

98 / 155

Truncated Gradient (Langford et al., 2009)

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

98 / 155

Truncated Gradient (Langford et al., 2009)

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

98 / 155

Truncated Gradient (Langford et al., 2009)

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

98 / 155

Truncated Gradient (Langford et al., 2009)

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

98 / 155

Truncated Gradient (Langford et al., 2009)

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

98 / 155

Truncated Gradient (Langford et al., 2009)

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

98 / 155

Truncated Gradient (Langford et al., 2009)

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

98 / 155

“Sparse” Online Algorithms

SGD with Cumulative Penalty (Tsuruoka et al., 2009)
Truncated Gradient (Langford et al., 2009)
Online Forward-Backward Splitting (Duchi and Singer, 2009)
Regularized Dual Averaging (Xiao, 2010)
Online Proximal Gradient (Martins et al., 2011a)

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

99 / 155

Online Forward-Backward Splitting (Duchi andSinger, 2009)T
input: stepsize sequences (ηt )T
t=1 , (ρt )t=1
initialize w = 0
for t = 1, 2, . . . dotake training pair (xt , yt )gradient step: w ← w − ηt ∇L(w; xt , yt )proximal step: w ← proxρt Ω (w)end forgeneralizes truncated gradient to arbitrary regularizers Ω
can tackle non-overlapping or hierarchical group-Lasso, but arbitraryoverlaps are difficult to handle (more later)practical drawback: without a laziness parameter, iterates areusually not very sparseconverges to -accurate objective after O(1/2 ) iterations
Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

100 / 155

“Sparse” Online Algorithms

SGD with Cumulative Penalty (Tsuruoka et al., 2009)
Truncated Gradient (Langford et al., 2009)
Online Forward-Backward Splitting (Duchi and Singer, 2009)
Regularized Dual Averaging (Xiao, 2010)
Online Proximal Gradient (Martins et al., 2011a)

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

101 / 155

Regularized Dual Averaging (Xiao, 2010)
input: coefficient η0
initialize w = 0
for t = 1, 2, . . . dotake training pair (xt , yt )gradient step: s ← s +√∇L(w; xt , yt )proximal step: w ← η0 t × proxΩ (−s/t)
end forbased on the dual averaging technique (Nesterov, 2009)
in practice: quite effective at getting sparse iterates (the proximal
steps are not vanishing)√O(C1 /2 + C2 / ) convergence, where C1 is a Lipschitz constant,and C2 is the variance of the stochastic gradients
drawback: requires storing two vectors (w and s), and s is not sparse
Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

102 / 155

What About Group Sparsity?
Both online forward-backward splitting (Duchi and Singer, 2009) andregularized dual averaging (Xiao, 2010) can handle groups
All that is necessary is to compute proxΩ (w)easy for non-overlapping and tree-structured groups
But what about general overlapping groups?
Martins et al. (2011a): a prox-grad algorithm that can handle arbitraryoverlapping groupsP
decompose Ω(w) = Jj=1 Ωj (w) where each Ωj is non-overlapping
then apply proxΩj sequentiallystill convergent (Martins et al., 2011a)

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

103 / 155

“Sparse” Online Algorithms

SGD with Cumulative Penalty (Tsuruoka et al., 2009)
Truncated Gradient (Langford et al., 2009)
Online Forward-Backward Splitting (Duchi and Singer, 2009)
Regularized Dual Averaging (Xiao, 2010)
Online Proximal Gradient (Martins et al., 2011a)

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

104 / 155

Online Proximal Gradient (Martins et al., 2011a)T
input: gravity sequence (σt )T
t=1 , stepsize sequence (ηt )t=1
initialize w = 0
for t = 1, 2, . . . dotake training pair (xt , yt )gradient step: w ← w − ηt ∇L(θ; xt , yt )sequential proximal steps:
for j = 1, 2, . . . dow ← proxηt σt Ωj (w)end forend forMartins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

105 / 155

Online Proximal Gradient (Martins et al., 2011a)T
input: gravity sequence (σt )T
t=1 , stepsize sequence (ηt )t=1
initialize w = 0
for t = 1, 2, . . . dotake training pair (xt , yt )gradient step: w ← w − ηt ∇L(θ; xt , yt )sequential proximal steps:
for j = 1, 2, . . . dow ← proxηt σt Ωj (w)end forend for

PAC Convergence. -accurate solution after T ≤ O(1/2 ) rounds
Computational efficiency. Each gradient step is linear in thenumber of features that fire.
Each proximal step is linear in the number of groups M.
Both are independent of D.
Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

105 / 155

Implementation Tricks (Martins et al., 2011b)
Budget driven shrinkage. Instead of a regularization constant,specify a budget on the number of selected groups. Each proximal
step sets σt to meet this target.
Sparseptron. Let L(w) = w> (f(x, ŷ ) − f(x, y )) be the perceptron
loss. The algorithm becomes perceptron with shrinkage.
Debiasing. Run a few iterations of sparseptron to identify therelevant groups. Then run a unregularized learner at a second stage.

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

106 / 155

Implementation Tricks (Martins et al., 2011b)
Budget driven shrinkage. Instead of a regularization constant,specify a budget on the number of selected groups. Each proximal
step sets σt to meet this target.
Sparseptron. Let L(w) = w> (f(x, ŷ ) − f(x, y )) be the perceptron
loss. The algorithm becomes perceptron with shrinkage.
Debiasing. Run a few iterations of sparseptron to identify therelevant groups. Then run a unregularized learner at a second stage.

Martins, Figueiredo, Smith (IST, CMU)

6

6
# Features

Memory efficiency. Only asmall active set of features need
to be maintained. Entire groups
can be deleted after eachproximal step.
Many irrelevant features arenever instantiated.

x 10

4
MIRA
Sparceptron + MIRA (B=30)200Structured Sparsity in NLP

5

10

15

# Epochs

http://tiny.cc/ssnlp

106 / 155

Summary of Algorithms

Coordinate descent
Prox-grad (IST)OWL-QN
SpaRSAFISTA
ADMM (C-SALSA)
Online subgradient
Cumulative penalty
Truncated gradient
FOBOS
RDA
Online prox-grad

Converges?
X
X
X
X
X
X
X
?
X
X
X
X

Martins, Figueiredo, Smith (IST, CMU)

Rate?
?
O(1/)?
O(1/)√
O(1/ )?
O(1/2 )?
O(1/2 )O(1/2 )O(1/2 )O(1/2 )Sparse?
X
Yes/NoYes/NoYes/NoYes/NoNo
No
X
X
Sort of
X
X

Structured Sparsity in NLPGroups?
Maybe
X
No
X
X
X
X
No
No
X
X
X

Overlaps?
No
Not easyNo
Not easy
Not easy
X
No
NoNo
Not easy
Not easyX

http://tiny.cc/ssnlp

107 / 155

Outline
1

Introduction

2

Loss Functions and Sparsity

3

Structured Sparsity

4

Algorithms
Convex Analysis
Batch Algorithms
Online Algorithms

5

Applications

6

Conclusions

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

108 / 155

Applications of Structured Sparsity in NLP

Relatively few to date (but this list may not be exhaustive).
1

Martins et al. (2011b):
Phrase chunking
Named entity recognition
Dependency parsing

2

Semisupervised lexicon expansion (Das and Smith, 2012)3

Unsupervised tagging (Graça et al., 2009)4

Sociolinguistic association discovery (Eisenstein et al., 2011)

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

109 / 155

Applications of Structured Sparsity in NLP

Relatively few to date (but this list may not be exhaustive).
1

Martins et al. (2011b):
Phrase chunking
Named entity recognition
Dependency parsing

2

Semisupervised lexicon expansion (Das and Smith, 2012)3

Unsupervised tagging (Graça et al., 2009)4

Sociolinguistic association discovery (Eisenstein et al., 2011)

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

109 / 155

Martins et al. (2011b): Group by Template
Feature templates provide a straightforward way to define non-overlappinggroups.
To achieve group sparsity, we optimize:N

1 X
L(w; xn , yn ) + Ω(w)w N
| {z }| n=1 {z} regularizerminempirical loss

where we use the `2,1 norm:Ω(w) = λMX

dm kwm k2

m=1

for M groups/templates.
Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

110 / 155

Chunking

CoNLL 2000 shared task (Sang and Buchholz, 2000)
Unigram features: 96 feature templates using POS tags, words, andword shapes, with various context sizes
Bigram features: 1 template indicating the label bigram
Baseline: L2 -regularized MIRA, 15 epochs, all features,cross-validation to choose regularization strength
Template-based group lasso: 5 epochs of sparseptron + 10 of
MIRA

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

111 / 155

Chunking Experiments# templates
model size
F1 (%)

Baseline
96
5,300,396
93.10

Martins, Figueiredo, Smith (IST, CMU)

Template-based group lasso
10
20
30
40
71,075 158,844 389,065 662,018
92.99
93.28
93.59
93.42

Structured Sparsity in NLP

http://tiny.cc/ssnlp

112 / 155

# Features

6

x 10

6

4
MIRA
Sparceptron + MIRA (B=30)

2
0
0

5

# Epochs

10

15

Memory requirement of sparseptron is < 7.5% of that of the baseline.
(Oscillations are due to proximal steps after every 1,000 instances.)

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

113 / 155

Applications of Structured Sparsity in NLP

Relatively few to date (but this list may not be exhaustive).
1

Martins et al. (2011b):
Phrase chunking
Named entity recognition
Dependency parsing

2

Semisupervised lexicon expansion (Das and Smith, 2012)3

Unsupervised tagging (Graça et al., 2009)4

Sociolinguistic association discovery (Eisenstein et al., 2011)

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

114 / 155

Named Entity Recognition
CoNLL 2002/2003 shared tasks (Sang, 2002; Sang and De Meulder,2003): Spanish, Dutch, and English
Unigram features: 452 feature templates using POS tags, words, word
shapes, prefixes, suffixes, and other string features, all with various
context sizes
Bigram features: 1 template indicating the label bigram
Baselines:
L2 -regularized MIRA, 15 epochs, all features, cross-validation to choose
regularization strength
sparseptron with lasso, different values of C

Template-based group lasso: 5 epochs of sparseptron + 10 of
MIRA

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

115 / 155

10000000
9000000
8000000
7000000

MIRA
Lasso (0.1)

6000000

Lasso (0.5)

5000000

Lasso (1)4000000

Group Lasso (100)3000000

Group Lasso (200)Group Lasso (300)2000000
1000000
0
SpanishDutch

EnglishNamed entity models: number of features. (Lasso C = 1/λN.)
Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

116 / 155

85
80

MIRA
Lasso (0.1)

75

Lasso (0.5)
Lasso (1)70Group Lasso (100)65Group Lasso (200)Group Lasso (300)60
SpanishDutch

EnglishNamed entity models: F1 accuracy on the test set. (Lasso C = 1/λN.)

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

117 / 155

Applications of Structured Sparsity in NLP

Relatively few to date (but this list may not be exhaustive).
1

Martins et al. (2011b):
Phrase chunking
Named entity recognition
Dependency parsing

2

Semisupervised lexicon expansion (Das and Smith, 2012)3

Unsupervised tagging (Graça et al., 2009)4

Sociolinguistic association discovery (Eisenstein et al., 2011)

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

118 / 155

Non-projective Dependency Parsing
CoNLL-X shared task (Buchholz and Marsi, 2006): Arabic, Danish,
Dutch, Japanese, Slovene, and Spanish
Arc-factored models (McDonald et al., 2005)
684 feature templates by conjoining words, shapes, lemmas, and POSof the head and the modifier, contextual POS, distance andattachment direction
Baselines:
MIRA with all features
filter-based template selection (information gain)
standard lasso

Our methods: template-based group lasso; coarse-to-fine
regularization
Budget sizes: 200, 300, and 400

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

119 / 155

Non-projective Dependency Parsing (c’ed)
DanishArabic

93.5

89.8

78
UAS (%)

Japanese

90

78.5

93

89.6
77.5

76.5
2

89.4

Group−Lasso
Group−Lasso (C2F)
Lasso
Filter−based (IG)

77

4

6
8
10
Number of Features

92.5

89.2
12

89
0

5

10

15

6

92
0

2

4

x 10

Slovene8x 10

Spanish

84

6

6

x 10

6

Turkish

84

76

83.5

75.5

83

75

82.5

74.5

83

82

81
0

2

4

6

8

10
6

x 10

82
0

0.5

1

1.5

2
7

x 10

74
0

5

10

15
x 10

6

Template-based group lasso is better at selecting feature templates thanthe IG criterion, and slightly better than coarse-to-fine.
Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

120 / 155

Which features get selected?
Qualitative analysis of selected templates:
Bilexical
Lex. → POS
POS → Lex.
POS → POS
Middle POS
Shape
Direction
Distance

Arabic
++
+
++
++
++
++

Danish
+
+
++
++
+
+

Japanese

Slovene

+
+
++
++
++
+
+

+
++
++
+
+

Spanish+Turkish

+

+

++

++

+
+

+
+

(Empty: none or very few templates selected; +: some templates
selected; ++: most or all templates selected.)
Morphologically-rich languages with small datasets (Turkish andSlovene) avoid lexical features.
In Japanese, contextual POS appear to be especially relevant.

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

121 / 155

Which features get selected?
Qualitative analysis of selected templates:
Bilexical
Lex. → POS
POS → Lex.
POS → POS
Middle POS
Shape
Direction
Distance

Arabic
++
+
++
++
++
++

Danish
+
+
++
++
+
+

Japanese

Slovene

+
+
++
++
++
+
+

+
++
++
+
+

Spanish+Turkish

+

+

++

++

+
+

+
+

(Empty: none or very few templates selected; +: some templates
selected; ++: most or all templates selected.)
Morphologically-rich languages with small datasets (Turkish andSlovene) avoid lexical features.
In Japanese, contextual POS appear to be especially relevant.
Take this with a grain of salt: some patterns may be properties ofthe datasets, not the languages!
Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

121 / 155

Applications of Structured Sparsity in NLP

Relatively few to date (but this list may not be exhaustive).
1

Martins et al. (2011b):
Phrase chunking
Named entity recognition
Dependency parsing

2

Semisupervised lexicon expansion (Das and Smith, 2012)3

Unsupervised tagging (Graça et al., 2009)4

Sociolinguistic association discovery (Eisenstein et al., 2011)

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

122 / 155

Lexicon Expansion (Das and Smith, 2012)

Desired: mapping from words (types) to categories (e.g., POS or
semantic predicates)
Allow ambiguity, but not too much!
Given some words’ mappings and a large corpus

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

123 / 155

Lexicon Expansion (Das and Smith, 2012)
Approach:1

Calculate distributional vectors for words

2

Construct a graph with words as vertices; edges from a word to the
k-most similar distributional vectors

3“Link” known words to empirical distributions

4“Propagate” label distributions throughout the graph (Corduneanu
and Jaakkola, 2003; Zhu et al., 2003; Subramanya and Bilmes, 2008,2009; Talukdar and Crammer, 2009)

Known as graph-based semisupervised learning.
See Noah’s talk about this work on Wednesday!

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

124 / 155

Example (Das and Smith, 2011)
 























 





 



Green words are observed in FrameNet data, each with a single frame(category); other words come from a larger, unlabeled corpus.

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

125 / 155

Graph-Based SSL

Here we reason about types, not tokens (instances).
Regularized empirical risk minimization doesn’t quite describe thissetting.
Instead, think of maximum a posteriori inference in a factor graph
G = (V, F, E):p({v }v ∈V ) =1 Y
φf ({v }v ∈V:(v ,f )∈E )Z
f ∈F

where V are random variables, F are factors, and E are edges.

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

126 / 155

Factor Graph Representation of Graph-Based SSL
X1

X2

X4

X3

Shaded variables X̂1 and X̂4 take the values of empirical distributions over
categories for words 1 and 4. Shaded factors encourage inferred
distributions X1 and X4 to be similar to them. Solid white factors
encourage smoothness across the graph, and dashed unary factors can beused to encourage sparsity.
Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

127 / 155

Unary Factors
Here, qn (y ) is an unnormalized distribution over categories given the word
associated with the nth vertex.
Three unary factor conditions:
Uniform squared `2 : −λ

XX
n

y

1
qn (y ) −|Y|

2

Used in past work (Subramanya et al., 2010); with quadratic pairwise
penalties and normalized q, generalizes Zhu et al. (2003)

Lasso (`1 ) for global sparsity: −λXXn|qn (y )|yElitist lasso (squared `1,2 ; Kowalski and Torrésani, 2009) for
per-vertex sparsity):
!2
−λ

X X
n

Martins, Figueiredo, Smith (IST, CMU)

|qn (y )|yStructured Sparsity in NLP

http://tiny.cc/ssnlp

128 / 155

Experimental Results: Expanding the FrameNet
LexiconVertices: lemmatized, coarse POS-tagged word types
Each qn (·) is a(n unnormalized) distribution over 877 semantic frames
9,263 vertices with labels, 55,217 unlabeled
Accuracy is for unknown predicates, partial match score (SemEval
2007)

supervised
Das and Smith (2011)(normalized qn , squared `2 -uniform)
squared `2 -uniform`1
squared `1,2
Martins, Figueiredo, Smith (IST, CMU)

accuracy
46.62

lexicon size
–

62.35
62.81
62.43
65.28

128,960
128,232
128,771
45,554Structured Sparsity in NLP

http://tiny.cc/ssnlp

129 / 155

Applications of Structured Sparsity in NLP

Relatively few to date (but this list may not be exhaustive).
1

Martins et al. (2011b):
Phrase chunking
Named entity recognition
Dependency parsing

2

Semisupervised lexicon expansion (Das and Smith, 2012)3

Unsupervised tagging (Graça et al., 2009)4

Sociolinguistic association discovery (Eisenstein et al., 2011)

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

130 / 155

Unsupervised Tagging (Graça et al., 2009)

Posterior regularization (Ganchev et al., 2010): penalize
probabilistic models based on properties of their posterior
distributions.
One such property: for each token, the number of labels with nonzero
probability.
Related idea: Ravi and Knight (2009) directly minimized the numberof tag bigram types allowed by the model (using ILP).

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

131 / 155

Understanding Posterior Regularization

Begin with a generative model pw (X , Y ). We are unsupervised here,
so Y is always hidden.
This leads to log P
marginal likelihood as loss:
L(w; xn ) = − log y ∈Y pw (xn , y ).
For a given x, define a set of distributions
Qx,ξ = {q(Y | x) | Eq [f(x, Y )] − b ≤ ξ}.
For a model distribution pw (X , Y ), define a regularizer:Ω(w, ξ) = σkξkβ +

N
X
n=1

Martins, Figueiredo, Smith (IST, CMU)

min KL(q(·)kpw (· | xn ))q∈Qxn ,ξStructured Sparsity in NLP

http://tiny.cc/ssnlp

132 / 155

Optimization for Posterior Regularization
An iterative EM-like algorithm can be used to locally optimize theregularized loss:
E-step: calculate posteriors pw (Y | xn ), ∀n. (Hinges on local
factorization of pw .)Project onto Qxn : for each n:∗>∀y , q(y | xn ) ∝ pw (y | xn )e −λn f(xn ,y )where λ∗ are the solution to the dual of the optimization problem
inside Ω. (Hinges on local factorization of f.)
M-step: solve quasi-supervised problem using q to fill in the
distribution over Y :
min

N X
X

w

Martins, Figueiredo, Smith (IST, CMU)

−q(y | xn ) log pw (xn , y ))n=1 yStructured Sparsity in NLP

http://tiny.cc/ssnlp

133 / 155

Posterior Sparsity (Graça et al., 2009)
Define indicator features: 1 if xn contains the ith occurrence of w at position j
and y [j] = tfi,w ,t (xn , y ) =
0 otherwisebi,w ,t = 0
Regularize with the `∞,1 norm (ξ is solved for and substituted):Ω(w) = σN
Xmin KL(q(·)kpw (· | xn ))max Epw [fi,w ,t ] +iw ,t |{z} n=1 q∈Qxn

X

`

|

{z ∞
`1

}

The dual form of the optimization problem is solvable with projectedgradient descent.
Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

134 / 155

From Ganchev et al. (2010), figure 11. (Left) initial tag distributions for
20 instances of a word. (Middle) Optimal dual variables λ; each row sums
to σ = 20. (Right) q concentrates posteriors for all instances on the NN
tag, reducing the `∞,1 norm from ≈ 4 to ≈ 1.

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

135 / 155

Unsupervised Tagging Results (Graça et al., 2009)

Average accuracy (standard deviation in parentheses) over 10 different
runs (random seeds identical across models) for 200 iterations. Sparse PR
constraint strength is give in parentheses.

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

136 / 155

Applications of Structured Sparsity in NLP

Relatively few to date (but this list may not be exhaustive).
1

Martins et al. (2011b):
Phrase chunking
Named entity recognition
Dependency parsing

2

Semisupervised lexicon expansion (Das and Smith, 2012)3

Unsupervised tagging (Graça et al., 2009)4

Sociolinguistic association discovery (Eisenstein et al., 2011)

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

137 / 155

Sociolinguistic Association Discovery

Dataset:geotagged tweets from 9,250 authors
mapping of locations to the U.S. Census’ ZIP code tabulation areas(ZCTAs)a ten-dimensional vector of statistics on demographic attributes

Can we learn a compact set of terms used on Twitter that associatewith demographics?

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

138 / 155

Sociolinguistic Association Discovery (Eisenstein
et al., 2011)
Setup: multi-output regression.
xn is a P-dimensional vector of independent variables; matrix is
X ∈ RN×P
yn is a T -dimensional vector of dependent variables; matrix is
Y ∈ RN×T
wp,t is the regression coefficient for the pth variable in the tth task;
matrix is W ∈ RP×T
Regularized objective with squared error loss typical for regression:min Ω(W) + kY − XWk2F
W

Regressions are run in both directions.

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

139 / 155

Structured Sparsity with `∞,1
Drive entire rows of W to zero (Turlach et al., 2005): “somepredictors are useless for any task”
PΩ(W) = λ T
t=1 maxp wp,tOptimization with blockwise coordinate ascent (Liu et al., 2009) andsome tricks to maintain sparsity:
Scale X to achieve variance 1 for each predictor
Precompute C = X> Y − Nx̄> ȳ, where x̄ and ȳ are mean row vectors
for X, Y, respectively
Precompute D = X> X − Nx̄> x̄More regression tricks in Eisenstein et al. (2011)

Related work: Duh et al. (2010) used multitask regression and `2,1 toselect features useful for reranking across many instances (applicationin machine translation).

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

140 / 155

Predicting Demographics from Text (Eisenstein
et al., 2011)
Predict 10-dimensional ZCTA characterization from words tweeted inthat region (vocabulary is P = 5, 418)
Measure Pearson’s correlation between prediction and correct value(average over tasks, cross-validated test sets)
Compare with truncated SVD, greatest variance across authors, mostfrequent words
0.28

average correlation

0.26
0.24
0.22
0.2

multi−output lasso
SVD
highest variancemost frequent

0.18
0.16

2

10

Martins, Figueiredo, Smith (IST, CMU)

3

10number of features

Structured Sparsity in NLP

http://tiny.cc/ssnlp

141 / 155

Predictive Words (Eisenstein et al., 2011)

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

142 / 155

Predicting Text from Demographics (Eisenstein
et al., 2011)

Embed the model in a feature induction outer loop: “screen andclean” (Wu et al., 2010)
Compare language model perplexity of models with no demographic
features, raw demographic features (10), and 37 discovered
conjunctive features.
Significant reduction compared to both baselines.

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

143 / 155

Predictive Demographic Features (Eisenstein et al.,2011)

Selected demographic features and words with high and low log-odds
associated with each.
Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

144 / 155

Outline
1

Introduction

2

Loss Functions and Sparsity

3

Structured Sparsity

4

Algorithms
Convex Analysis
Batch Algorithms
Online Algorithms

5

Applications

6

Conclusions

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

145 / 155

Summary
Sparsity is desirable in NLP: feature selection, runtime, memory
footprint, interpretability
Beyond plain sparsity: structured sparsity can be promoted throughgroup-Lasso regularization
Choice of groups reflects prior knowledge about the desired sparsity
patterns.
We have seen examples for feature template selection, grid sparsity,and elite discovery, but many more are possible!
Small/medium scale: many batch algorithms available, with fast
convergence (IST, FISTA, SpaRSA, ...)
Large scale: online proximal-gradient algorithms suitable to explore
large feature spaces

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

146 / 155

Thank you!

Questions?

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

147 / 155

Acknowledgments
National Science Foundation (USA), CAREER grant IIS-1054319
Fundação para a Ciência e Tecnologia (Portugal), grantPEst-OE/EEI/LA0008/2011.
Fundação para a Ciência e Tecnologia and Information andCommunication Technologies Institute (Portugal/USA), through the
CMU-Portugal Program.
Priberam: QREN/POR Lisboa (Portugal), EU/FEDER programme,
Discooperio project, contract 2011/18501.

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

148 / 155

References I
Amaldi, E. and Kann, V. (1998). On the approximation of minimizing non zero variables or unsatisfied relations in linear
systems. Theoretical Computer Science, 209:237–260.
Andrew, G. and Gao, J. (2007). Scalable training of L1-regularized log-linear models. In Proc. of ICML. ACM.
Bakin, S. (1999). Adaptive regression and model selection in data mining problems. PhD thesis, Australian National University.
Barzilai, J. and Borwein, J. (1988). Two point step size gradient methods. IMA Journal of Numerical Analysis, 8:141–148.
Beck, A. and Teboulle, M. (2009). A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM Journal
on Imaging Sciences, 2(1):183–202.
Bioucas-Dias, J. and Figueiredo, M. (2007). A new twist: two-step iterativeshrinkage/thresholding algorithms for image
restoration. IEEE Transactions on Image Processing, 16:2992–3004.
Blumensath, T. (2012). Compressed sensing with nonlinear observations and related nonlinear optimisation problems. Technicalreport, arXiv/1205.1650.
Bottou, L. and Bousquet, O. (2007). The tradeoffs of large scale learning. NIPS, 20.
Buchholz, S. and Marsi, E. (2006). CoNLL-X shared task on multilingual dependency parsing. In Proc. of CoNLL.
Candès, E., Romberg, J., and Tao, T. (2006a). Robust uncertainty principles: Exact signal reconstruction from highly
incomplete frequency information. IEEE Transactions on Information Theory, 52:489–509.
Candès, E., Romberg, J., and Tao, T. (2006b). Stable signal recovery from incomplete and inaccurate measurements.
Communications in Pure and Applied Mathematics, 59:1207–1223.
Carpenter, B. (2008). Lazy sparse stochastic gradient descent for regularized multinomial logistic regression. Technical report,
Technical report, Alias-i.
Caruana, R. (1997). Multitask learning. Machine Learning, 28(1):41–75.
Cessie, S. L. and Houwelingen, J. C. V. (1992). Ridge estimators in logistic regression. Journal of the Royal Statistical Society;
Series C, 41:191–201.
Chen, S. and Rosenfeld, R. (1999). A Gaussian prior for smoothing maximum entropy models. Technical report,
CMU-CS-99-108.
Claerbout, J. and Muir, F. (1973). Robust modelling of erratic data. Geophysics, 38:826–844.
Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

149 / 155

References II
Combettes, P. and Wajs, V. (2006). Signal recovery by proximal forward-backward splitting. Multiscale Modeling and
Simulation, 4:1168–1200.
Corduneanu, A. and Jaakkola, T. (2003). On information regularization. In Proc. of UAI.
Das, D. and Smith, N. A. (2011). Semi-supervised frame-semantic parsing for unknown predicates. In Proc. of ACL.
Das, D. and Smith, N. A. (2012). Graph-based lexicon expansion with sparsity-inducing penalties. In Proceedings of NAACL.
Daubechies, I., Defrise, M., and De Mol, C. (2004). An iterative thresholding algorithm for linear inverse problems with asparsity constraint. Communications on Pure and Applied Mathematics, 11:1413–1457.
Davis, G., Mallat, S., and Avellaneda, M. (1997). Greedy adaptive approximation. Journal of Constructive Approximation,
13:57–98.
Della Pietra, S., Della Pietra, V., and Lafferty, J. (1997). Inducing features of random fields. IEEE Transactions on PatternAnalysis and Machine Intelligence, 19:380–393.
Donoho, D. (2006). Compressed sensing. IEEE Transactions on Information Theory, 52:1289–1306.
Duchi, J., Shalev-Shwartz, S., Singer, Y., and Chandra, T. (2008). Efficient projections onto the L1-ball for learning in highdimensions. In ICML.
Duchi, J. and Singer, Y. (2009). Efficient online and batch learning using forward backward splitting. JMLR, 10:2873–2908.
Duh, K., Sudoh, K., Tsukada, H., Isozaki, H., and Nagata, M. (2010). n-best reranking by multitask learning. In Proceedings of
the Joint Fifth Workshop on Statistical Machine Translation and Metrics.
Efron, B., Hastie, T., Johnstone, I., and Tibshirani, R. (2004). Least angle regression. Annals of Statistics, 32:407–499.
Eisenstein, J., Smith, N. A., and Xing, E. P. (2011). Discovering sociolinguistic associations with structured sparsity. In Proc. of
ACL.
Figueiredo, M. and Bioucas-Dias, J. (2011). An alternating direction algorithm for (overlapping) group regularization. In Signal
processing with adaptive sparse structured representations–SPARS11. Edinburgh, UK.
Figueiredo, M. and Nowak, R. (2003). An EM algorithm for wavelet-based image restoration. IEEE Transactions on Image
Processing, 12:986–916.
Figueiredo, M., Nowak, R., and Wright, S. (2007). Gradient projection for sparse reconstruction: application to compressedsensing and other inverse problems. IEEE Journal of Selected Topics in Signal Processing: Special Issue on Convex
Optimization Methods for Signal Processing, 1:586–598.
Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

150 / 155

References III
Friedman, J., Hastie, T., Rosset, S., Tibshirani, R., and Zhu, J. (2004). Discussion of three boosting papers. Annals of
Statistics, 32(1):102–107.
Fu, W. (1998). Penalized regressions: the bridge versus the lasso. Journal of computational and graphical statistics, pages
397–416.
Ganchev, K., Graça, J., Gillenwater, J., and Taskar, B. (2010). Posterior regularization for structured latent variable models.
JMLR, 11:2001–2049.
Gao, J., Andrew, G., Johnson, M., and Toutanova, K. (2007). A comparative study of parameter estimation methods forstatistical natural language processing. In Proc. of ACL.
Genkin, A., Lewis, D., and Madigan, D. (2007). Large-scale Bayesian logistic regression for text categorization. Technometrics,
49:291–304.
Goodman, J. (2004). Exponential priors for maximum entropy models. In Proc. of NAACL.
Graça, J., Ganchev, K., Taskar, B., and Pereira, F. (2009). Posterior vs. parameter sparsity in latent variable models. Advancesin Neural Information Processing Systems.
Guyon, I. and Elisseeff, A. (2003). An introduction to variable and feature selection. Journal of Machine Learning Research,
3:1157–1182.
Hale, E., Yin, W., and Zhang, Y. (2008). Fixed-point continuation for l1-minimization: Methodology and convergence. SIAM
Journal on Optimization, 19:1107–1130.
Hastie, T., Taylor, J., Tibshirani, R., and Walther, G. (2007). Forward stagewise regression and the monotone lasso. Electronic
Journal of Statistics, 1:1–29.
Haupt, J. and Nowak, R. (2006). Signal reconstruction from noisy random projections. IEEE Transactions on Information
Theory, 52:4036–4048.
Jenatton, R., Audibert, J.-Y., and Bach, F. (2009). Structured variable selection with sparsity-inducing norms. Technical report,
arXiv:0904.3523.
Jenatton, R., Mairal, J., Obozinski, G., and Bach, F. (2011). Proximal methods for hierarchical sparse coding. Journal of
Machine Learning Research, 12:2297–2334.
Kazama, J. and Tsujii, J. (2003). Evaluation and extension of maximum entropy models with inequality constraints. In Proc. of
EMNLP.
Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

151 / 155

References IV
Kim, S. and Xing, E. (2010). Tree-guided group lasso for multi-task regression with structured sparsity. In Proc. of ICML.
Kowalski, M. and Torrésani, B. (2009). Sparsity and persistence: mixed norms provide simple signal models with dependent
coefficients. Signal, Image and Video Processing, 3(3):251–264.
Krishnapuram, B., Carin, L., Figueiredo, M., and Hartemink, A. (2005). Sparse multinomial logistic regression: Fast algorithms
and generalization bounds. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 27:957–968.
Lanckriet, G. R. G., Cristianini, N., Bartlett, P., Ghaoui, L. E., and Jordan, M. I. (2004). Learning the kernel matrix withsemidefinite programming. JMLR, 5:27–72.
Langford, J., Li, L., and Zhang, T. (2009). Sparse online learning via truncated gradient. JMLR, 10:777–801.
Lavergne, T., Cappé, O., and Yvon, F. (2010). Practical very large scale CRFs. In Proc. of ACL.
Liu, H., Palatucci, M., and Zhang, J. (2009). Blockwise coordinate descent procedures for the multi-task lasso, with applications
to neural semantic basis discovery. In Proceedings of the 26th Annual International Conference on Machine Learning, pages
649–656. ACM.
Mairal, J., Jenatton, R., Obozinski, G., and Bach, F. (2010). Network flow algorithms for structured sparsity. In Advances in
Neural Information Processing Systems.
Mairal, J. and Yu, B. (2012). Complexity analysis of the lasso regularization path. Technical report, arXiv:1205.0079.
Markowitz, H. (1952). Portfolio selection. Journal of Finance, 7:77–91.
Martins, A. F. T., Figueiredo, M. A. T., Aguiar, P. M. Q., Smith, N. A., and Xing, E. P. (2011a). Online learning of structured
predictors with multiple kernels. In Proc. of AISTATS.
Martins, A. F. T., Smith, N. A., Aguiar, P. M. Q., and Figueiredo, M. A. T. (2011b). Structured Sparsity in Structured
Prediction. In Proc. of Empirical Methods for Natural Language Processing.
Martins, A. F. T., Smith, N. A., Xing, E. P., Aguiar, P. M. Q., and Figueiredo, M. A. T. (2010). Turbo parsers: Dependency
parsing by approximate variational inference. In Proc. of EMNLP.
McDonald, R. T., Pereira, F., Ribarov, K., and Hajic, J. (2005). Non-projective dependency parsing using spanning tree
algorithms. In Proc. of HLT-EMNLP.
Muthukrishnan, S. (2005). Data Streams: Algorithms and Applications. Now Publishers, Boston, MA.
Negahban, S., Ravikumar, P., Wainwright, M., and Yu, B. (2012). A unified framework for high-dimensional analysis of
m-estimators with decomposable regularizers. Technical report, Department of EECS, UC Berkeley.
Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

152 / 155

References V
Nesterov, Y. (2009). Primal-dual subgradient methods for convex problems. Mathematical programming, 120(1):221–259.
Obozinski, G., Taskar, B., and Jordan, M. (2010). Joint covariate selection and joint subspace selection for multiple
classification problems. Statistics and Computing, 20(2):231–252.
Osborne, M., Presnell, B., and Turlach, B. (2000). A new approach to variable selection in least squares problems. IMA Journalof Numerical Analysis, 20:389–403.
Perkins, S., Lacker, K., and Theiler, J. (2003). Grafting: Fast, incremental feature selection by gradient descent in function
space. Journal of Machine Learning Research, 3:1333–1356.
Plan, Y. and Vershynin, R. (2012). Robust 1-bit compressed sensing and sparse logistic regression: A convex programming
approach. Technical report, arXiv/1202.1212.
Quattoni, A., Carreras, X., Collins, M., and Darrell, T. (2009). An efficient projection for l1,∞ regularization. In Proc. of ICML.
Ratnaparkhi, A. (1996). A maximum entropy model for part-of-speech tagging. In Proc. of EMNLP.
Ravi, S. and Knight, K. (2009). Minimized models for unsupervised part-of-speech tagging. In Proc. of ACL.
Sang, E. (2002). Introduction to the CoNLL-2002 shared task: Language-independent named entity recognition. In Proc. of
CoNLL.
Sang, E. and Buchholz, S. (2000). Introduction to the CoNLL-2000 shared task: Chunking. In Proceedings of CoNLL-2000 and
LLL-2000.
Sang, E. and De Meulder, F. (2003). Introduction to the CoNLL-2003 shared task: Language-independent named entity
recognition. In Proc. of CoNLL.
Schaefer, R., Roi, L., and Wolfe, R. (1984). A ridge logistic estimator. Communications in Statistical Theory and Methods,
13:99–113.
Schmidt, M. and Murphy, K. (2010). Convex structure learning in log-linear models: Beyond pairwise potentials. In Proc. of
AISTATS.
Shevade, S. and Keerthi, S. (2003). A simple and efficient algorithm for gene selection using sparse logistic regression.
Bioinformatics, 19:2246–2253.
Shor, N. (1985). Minimization Methods for Non-differentiable Functions. Springer.
Sokolovska, N., Lavergne, T., Cappé, O., and Yvon, F. (2010). Efficient learning of sparse conditional random fields forsupervised sequence labelling. IEEE Journal of Selected Topics in Signal Processing, 4(6):953–964.
Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

153 / 155

References VI
Stojnic, M., Parvaresh, F., and Hassibi, B. (2009). On the reconstruction of block-sparse signals with an optimal number ofmeasurements. Signal Processing, IEEE Transactions on, 57(8):3075–3085.
Subramanya, A. and Bilmes, J. (2008). Soft-supervised learning for text classification. In Proc. of EMNLP.
Subramanya, A. and Bilmes, J. (2009). Entropic graph regularization in non-parametric semi-supervised classification. In Proc.
of NIPS.
Subramanya, A., Petrov, S., and Pereira, F. (2010). Efficient graph-based semi-supervised learning of structured tagging models.
In Proc. of EMNLP.
Talukdar, P. P. and Crammer, K. (2009). New regularized algorithms for transductive learning. In Proc. of the ECML-PKDD.
Taylor, H., Bank, S., and McCoy, J. (1979). Deconvolution with the `1 norm. Geophysics, 44:39–52.
Tibshirani, R. (1996). Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society B., pages
267–288.
Tikhonov, A. (1943). On the stability of inverse problems. In Dokl. Akad. Nauk SSSR, volume 39, pages 195–198.
Tillmann, A. and Pfetsch, M. (2012). The computational complexity of RIP, NSP, and related concepts in compressed sensing.
Technical report, arXiv/1205.2081.
Tseng, P. and Yun, S. (2009). A coordinate gradient descent method nonsmooth seperable approximation. Mathematical
Programmin (series B), 117:387–423.
Tsuruoka, Y., Tsujii, J., and Ananiadou, S. (2009). Stochastic gradient descent training for l1-regularized log-linear models withcumulative penalty. In Proc. of ACL.
Turlach, B. A., Venables, W. N., and Wright, S. J. (2005). Simultaneous variable selection. Technometrics, 47(3):349–363.
van de Geer, S. (2008). High-dimensional generalized linear models and the lasso. The Annals of Statistics, 36:614–645.
Wiener, N. (1949). Extrapolation, Interpolation, and Smoothing of Stationary Time Series. Wiley, New York.
Williams, P. (1995). Bayesian regularization and pruning using a Laplace prior. Neural Computation, 7:117–143.
Wright, S., Nowak, R., and Figueiredo, M. (2009). Sparse reconstruction by separable approximation. IEEE Transactions on
Signal Processing, 57:2479–2493.
Wu, J., Devlin, B., Ringquist, S., Trucco, M., and Roeder, K. (2010). Screen and clean: A tool for identifying interactions ingenome-wide association studies. Genetic Epidemiology, 34(3):275–285.
Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

154 / 155

References VII

Xiao, L. (2010). Dual averaging methods for regularized stochastic learning and online optimization. Journal of Machine
Learning Research, 11:2543–2596.
Yarowsky, D. (1995). Unsupervised word sense disambiguation rivaling supervised methods. In Proc. of ACL.
Yuan, L., Liu, J., and Ye, J. (2011). Efficient methods for overlapping group lasso. In Advances in Neural Information
Processing Systems 24, pages 352–360.
Yuan, M. and Lin, Y. (2006). Model selection and estimation in regression with grouped variables. Journal of the Royal
Statistical Society (B), 68(1):49.
Yun, S. and Toh, K.-C. (2011). A coordinate gradient descent method for L1-regularized convex minimization. Computational
Optimization and Applications, 48:273–307.
Zhao, P., Rocha, G., and Yu, B. (2009). Grouped and hierarchical model selection through composite absolute penalties. Annalsof Statistics, 37(6A):3468–3497.
Zhu, J., Lao, N., and Xing, E. (2010). Grafting-light: fast, incremental feature selection and structure learning of markov
random fields. In Proc. of International Conference on Knowledge Discovery and Data Mining, pages 303–312.
Zhu, X., Ghahramani, Z., and Lafferty, J. D. (2003). Semi-supervised learning using Gaussian fields and harmonic functions. In
Proc. of ICML.

Martins, Figueiredo, Smith (IST, CMU)

Structured Sparsity in NLP

http://tiny.cc/ssnlp

155 / 155