-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathon-regularization.html
140 lines (111 loc) · 12 KB
/
on-regularization.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
<!doctype html>
<html lang="">
<head>
<meta charset="utf-8"/>
<title>Introductory notes on regularization - On Statistics and Machine Learning</title>
<meta name="author" content="Alex Companioni">
<meta name="description" content="A couple of different channels converged on discussions of regularization recently: Julia Evans recently wrote about the bias-variance trade-off -- go read her post, it's great! -- and asked some questions about regularization in it; one of my coworkers -- and I'm paraphrasing here, Ravi -- called LASSO one of the most important statistical …">
<link rel="stylesheet" href="/theme/css/main.css" type="text/css" />
</head>
<body>
<div class="container">
<header role="banner">
<div class="feeds">
</div>
<a href="" class="title">On Statistics and Machine Learning</a>
</header>
<div class="wrapper">
<div role="main" class="content">
<article class="full">
<h1>Introductory notes on regularization</h1>
<div class="metadata">
<time datetime="2016-01-23T21:07:00-05:00" pubdate>Sat 23 January 2016</time>
<address class="vcard author">
by <a class="url fn" href="/author/alejandro-companioni.html">Alejandro Companioni</a>
</address>
in <a href="/category/misc.html">misc</a>
</div>
<p>A couple of different channels converged on discussions of regularization recently:</p>
<ul>
<li>
<p>Julia Evans recently wrote about <a href="http://jvns.ca/blog/2016/01/02/winning-the-bias-variance-tradeoff/">the bias-variance trade-off</a> -- go read her post, it's great! -- and asked some questions about regularization in it;</p>
</li>
<li>
<p>one of my coworkers -- and I'm paraphrasing here, Ravi -- called LASSO one of the most important statistical innovations in recent decades;</p>
</li>
<li>
<p>and I also learned about the ElasticNet algorithm recently, a great tool for improving the predictive accuracy of your models (more on that later).</p>
</li>
</ul>
<p>Now that this blog is alive and kicking again, I figured I'd post some notes I took while refreshing my memory on regularization. I'll define what it is and how it works, then roll into some comments on applying regularization and debugging your regularized models.</p>
<h2>First though, some shout-outs</h2>
<p>This post is really a tl;dr of some excellent resources on regularization. If you'd like more detail, check out the paper introducing <a href="http://statweb.stanford.edu/~tibs/lasso/lasso.pdf">the LASSO</a> or <a href="http://math.arizona.edu/~hzhang/math574m/Read/Ridge.pdf">ridge regression</a>.</p>
<p>The eponymous <a href="http://statweb.stanford.edu/~tibs/ElemStatLearn/">Elements of Statistical Learning</a> also has a nice review of regularization. I would recommend reading the sections on model selection (Chapter 2.9), model complexity (Chapter 7.2), and subset selection (Chapter 3.4) back-to-back-to-back; this will contextualize regularization nicely with the related modeling concerns.</p>
<p>Finally, there's a new (free!) book on the LASSO from <a href="http://web.stanford.edu/~hastie/StatLearnSparsity/">Hastie, Tibshirani, and Wainwright</a>. It has an interesting outline, and the first part includes a great overview of the LASSO.</p>
<h2>On the regular(ization of models)</h2>
<p>Assume we have a multivariate dataset $X = x_1, x_2, … x_i, …, x_n$, with each observation consisting of $f$ features. We would then like to fit a linear model of the form</p>
<p>$$\hat{y} = \mathbf{w}^T\mathbf{x}$$</p>
<p>using this dataset. Regularization is a process for fitting a statistical model against a modified objective function of the form:</p>
<p>$$L(\mathbf{w}) = \sum_{i=1}^{N}(y_i - \mathbf{w}^{T}x_i)^{2} + \lambda R(\mathbf{w})$$</p>
<p>We use the sum of squares error for simplicity, since we will instead focus on the new term $R(\mathbf{w})$. Common values for this function include the 1-norm $R(\mathbf{w}) = \sum_{i=1}^{M}|\mathbf{w}<em i="1">i|$ and the 2-norm $R(\mathbf{w}) = \sum</em>^{M}\mathbf{w}_{i}^{2}$. We’ll come back to these later, but note that both regularizers increase monotonically: as $\mathbf{w}$ grows in size, so does the increase in $L(\mathbf{w})$ due to $R(\mathbf{w})$. This has the effect of discouraging larger values of our estimated parameterization $\hat{\mathbf{w}}$, so that its size is pushed downward in proportion to the chosen $\lambda$.</p>
<h2>Why regularize?</h2>
<p>This downward nudge to $\mathbf{w}$ reduces the complexity of our model. Practically speaking, a lower $\mathbf{w}_f$ decreases the amount contributed by each feature $\mathbf{x}_f$ to our estimate $\hat{y}$. In the extreme, $\mathbf{w}_f = 0$ and the feature $f$ contributes nothing to the estimate $\hat{y}$.</p>
<p>As Julia <a href="http://jvns.ca/blog/2016/01/02/winning-the-bias-variance-tradeoff/">suggested in her post</a>, limiting model complexity exchanges some of the error resulting from variance for some error resulting from bias. If you’re reading this post you’ve likely seen this plot a million times before — seriously, check out <a href="https://www.google.com/search?q=model+complexity+prediction+error&espv=2&biw=1243&bih=669&source=lnms&tbm=isch&sa=X&ved=0ahUKEwiqxcqYocHKAhUGcz4KHRj5BEcQ_AUIBigB">these Google Image results</a>, it’s everywhere — but it’s useful for understanding how your model’s complexity influences it’s generalizability:</p>
<p><img alt="Here’s a novel plot you’ve never seen before!!11" src="/images/reg-pred-error.png"></p>
<p><strong>This is the first benefit of regularization: it will likely improve your model’s prediction accuracy on previously unseen data.</strong> I use the word “likely” here because you <em>could</em> be operating in the left region of that curve. If that’s the case, you might need to start engineering some features!</p>
<p>What’s the second benefit of regularizing? I previously mentioned that regularization could actually zero our weights for some of your features. This is a nice side effective of regularization—the data helps us with model selection by zeroing out some features! <strong>That’s actually the second benefit of regularization: it helps us with model selection by only keeping those features with the strongest effects on our labels.</strong> At iHeartRadio we talk about “throwing the kitchen sink” at a modeling problem, knowing that aggressive regularization can limit the effects of spurious predictors. Simpler natural language techniques also take this path, using bag-of-word features, the LASSO, and high values of $\lambda$ to drop all but the most important features.</p>
<h2>Ok, let’s regularize</h2>
<p>With these benefits in mind, it’s easy to add a regularization term to your objective function. You face two decisions:</p>
<ol>
<li>Your choice of function $R(\mathbf{w})$, and</li>
<li>Your choice of regularizing parameter $\lambda$</li>
</ol>
<p>When addressing the first question, you’ll probably choose between the 1-norm (known as the LASSO, or L1-regularization) and the 2-norm (known as ridge regularization or L2-regularization). These regularizers induce different behaviors in your learned weights. While ridge regularization nudges learned weights downward, the LASSO strongly encourages sparsity in the learned model by favoring $\mathbf{w}_f = 0$ for any feature $f$.</p>
<p>Here’s a brief explanation as to why that’s the case. The objective function $L(w, x)$ above can be restated as a constrained optimization problem of the form:</p>
<p>$$L(\mathbf{w}) = \sum_{i=1}^{N}(y_i - \mathbf{w}^{T}x_i)^{2}$$</p>
<p>subject to the constraint $R(\mathbf{w}) \le \lambda$. Assume that $\mathbf{w}$ and $x_i$ are both in $\mathbb{R}^2$. Since we’ve stuck with the sum of squares error, we can visualize this optimization problem as follows:</p>
<p><img alt="I know this plot says \beta, but just ignore that. :)" src="/images/reg-opt-plots.png"></p>
<p>These plots show the space of possible assignments to the parameter estimate $\mathbf{w}$ (let’s assume the component of $\beta$ along each axis is instead a component of $\mathbf{w}$). The blue region in each plot is the constrained space of solutions, while the red contours represent potential values of $\hat{\mathbf{w}}$. We want to find the point inside the constrained space that sits on the contour closest to the solution; for the LASSO region on the left, that point is far more likely to sit along an axis, which would thus yield a sparser solution for $\hat{\mathbf{w}}$.</p>
<p>Returning to the second question, it is common to treat $\lambda$ as a parameter selected via grid search (just make sure to use cross-validation). You could also instead roll with the <a href="http://scikit-learn.org/stable/modules/generated/sklearn.linear_model.ElasticNet.html">ElasticNet algorithm</a>, which regularizes your objective function using $R(\mathbf{w}) = \alpha<em>\sum_{i=1}^{M}|\mathbf{w}_i| + (1-\alpha)</em>\sum_{i=1}^{M}\mathbf{w}_{i}^{2}$ while adaptively choosing the best $\alpha$.</p>
<h2>Final comments</h2>
<p>Some notes on regularizing:</p>
<ul>
<li>You should standardize your input dataset so that it is distributed according to $\mathcal{N}(0, 1)$, since solutions to the regularized objective function depend on the scale of your features.</li>
<li>Both scikit-learn and R have great regularization packages. Check out the <a href="http://scikit-learn.org/stable/modules/linear_model.html">scikit-learn docs on GLMs</a> or <a href="http://web.stanford.edu/~hastie/glmnet/glmnet_alpha.html">R’s glmnet</a>.</li>
</ul>
<p>Julia asked about how one can debug regularization. It is not guaranteed that a regularized model generalizes better than an unregularized model, but I have observed the following in the past:</p>
<ul>
<li>If introducing LASSO to your model forces your coefficients to zero, your model is not that great. You might need to reconsider your features.</li>
<li>Try estimating $\mathbf{w}$ using vanilla regression, then check the 1-norm and 2-norm of $\hat{\mathbf{w}}$. Intuitively-speaking, this unregularized estimate should have a higher norm than its regularized counterpart.</li>
</ul>
<p>Finally, I aimed for a very straightforward discussion of regularization here. Some interesting follow-up resources:</p>
<ul>
<li>EoSL introduces a Bayesian interpretation of regularization — ridge regularization is equivalent to imposing a Gaussian prior on the model parameters — and comments on the relationship to the singular value decomposition (as a feature's singular value under the SVD of $\mathbf{X}$ decreases, its corresponding weight is also downweighted by regularization). Interesting stuff.</li>
<li>This post used the sum of squares for simplicity, although regularization extends to all sorts of model classes. Section 5.5 of <a href="http://research.microsoft.com/en-us/um/people/cmbishop/PRML/">Pattern Recognition and Machine Learning</a> explains how regularization can also mitigate over-fitting when training neural networks, for example.</li>
</ul>
<h2>References</h2>
<p>What I actually referenced while writing this post:</p>
<ol>
<li>Hastie, T. et. al. (2009). The Elements of Statistical Learning: Data Mining, Inference, and Prediction. Springer-Verlag.</li>
<li>Hastie, T. et. al. (2015). Statistical Learning with Sparsity: The Lasso and Generalizations. Chapman and Hall.</li>
<li>Some Wikipedia on various things to refresh my memory.</li>
</ol>
</article>
<p>
<a href="https://twitter.com/share" class="twitter-share-button" data-via="" data-lang="en" data-size="large" data-related="">Tweet</a>
<script>!function(d,s,id){var js,fjs=d.getElementsByTagName(s)[0];if(!d.getElementById(id)){js=d.createElement(s);js.id=id;js.src="//platform.twitter.com/widgets.js";fjs.parentNode.insertBefore(js,fjs);}}(document,"script","twitter-wjs");</script>
</p>
</div>
<div class="sidebar">
<div class="sidebar-container" >
</div>
</div>
</div>
<footer>
<p role="contentinfo">
Alex Companioni - Proudly powered by <a href="http://alexis.notmyidea.org/pelican/">pelican</a>. Theme <a href="https://github.com/fle/pelican-sober">pelican-sober</a>.
</p>
</footer>
</div>
</body>
</html>