Sparse Representations · Bagging and Other Ensemble Methods

§7.10 Sparse representations

Weight decay penalizes the parameters. A different idea is to penalize the activations — pushing the hidden units toward zero. That is a sparse representation , and it is a distinct thing from a sparse parametrization. An L¹ penalty on the weights zeroes entries of the weight matrix; an L¹ penalty on the representation zeroes entries of the code $\boldsymbol{h}$ . Both describe the same linear system $\boldsymbol{y}=\boldsymbol{A}\boldsymbol{x}$ , but the zeros live in different places:

Representational sparsity is achieved with the same machinery — just aimed at $\boldsymbol{h}$ :

Term by term

\tilde{J}(\boldsymbol{\theta}; \boldsymbol{X}, \boldsymbol{y}) = J(\boldsymbol{\theta}; \boldsymbol{X}, \boldsymbol{y}) + \alpha\,\Omega(\boldsymbol{h})

$\Omega(\boldsymbol{h}) = \lVert\boldsymbol{h}\rVert_1$	an L¹ penalty on the REPRESENTATION (not the weights) drives its elements to zero — representational sparsity	norm penalty on h
$\text{other choices}$	a Student-t prior, or a KL-divergence penalty pushing the average activation (1/m)Σhᵢ toward a small target like 0.01 (handy when h ∈ [0,1])	alternatives
$\text{OMP-}k$	or a HARD constraint: orthogonal matching pursuit solves argmin‖x−Wh‖² with at most k non-zeros (‖h‖₀ < k), efficient when W is orthogonal	hard version

Essentially any model with hidden units can be made sparse this way — OMP-1 is even an effective standalone feature extractor for deep architectures.

§7.11 Bagging and other ensemble methods

Bagging reduces generalization error by training several models separately and having them vote — an instance of model averaging . It works because different models rarely make all the same errors. Make that precise: suppose $k$ regressors each have per-example error variance $v$ and pairwise covariance $c$ . The averaged prediction’s expected squared error is:

Term by term

\mathbb{E}\!\left[\Big(\tfrac{1}{k}\textstyle\sum_i \epsilon_i\Big)^2\right] = \tfrac{1}{k}v + \tfrac{k-1}{k}c

$\tfrac{1}{k}v$	the variance term — shrinks like 1/k as the ensemble grows	shrinks with k
$\tfrac{k-1}{k}c$	the covariance term — governed by how CORRELATED the members errors are; it tends to c as k grows	the ceiling
$c=0 \Rightarrow \tfrac{1}{k}v$	independent errors → error falls linearly in k. Perfectly correlated (c=v) → stays v, no benefit at all	the two limits

Drag $k$ and the error correlation $c$ to see the two regimes:

Ensemble MSE = v/k + (k−1)/k·c: independent errors (c=0, green) fall as v/k; identical errors (c=v, red) give no improvement

k = 6c = 0.20

MSE = v/k + (k−1)/k · c

= 0.167 + 0.167

= 0.333

(v = 1)

If the models make identical errors (c = v), the green and red curves meet and averaging does nothing. As the errors become independent (c → 0), the ensemble error falls like v/k — that is the whole point of bagging.

Concretely, bagging builds $k$ datasets by sampling the original with replacement (each ends up missing some examples and duplicating others — about ⅔ of the originals appear in each), trains one model per dataset, and averages. The differing datasets make the models differ:

Ensembles for free — and the boosting exception

Neural nets reach so many different solutions that they benefit from model averaging even trained on the same dataset — differences in random initialization, minibatch order, and hyperparameters make their errors partly independent. Model averaging is powerful enough that it is discouraged in benchmark papers (any method gains from it, at a compute cost) yet routinely wins competitions. One caveat: not every ensemble is a regularizer. Boosting incrementally adds members to build an ensemble with higher capacity than any individual — the opposite intent to bagging’s variance reduction.

Next: dropout — which makes bagging practical for exponentially many neural networks at once — dropout, part 1.

Check yourself — sparse representations and bagging

1.What is the difference between a sparse parametrization and a sparse representation?

2.How do you induce representational sparsity, and what is OMP-k?

3.For k models with error variance v and covariance c, the ensemble MSE is (1/k)v + ((k−1)/k)c. What do the two extremes of c give?

4.In BaggingLab, set c = 0 and slide k from 1 to 20. What happens to the ensemble MSE, and why does bagging use resampling with replacement?

5.Why is boosting NOT a variance-reducing regularizer like bagging?

5 questions