51
$\begingroup$

Whenever regularization is used, it is often added onto the cost function such as in the following cost function. $$ J(\theta)=\frac 1 2(y-\theta X^T)(y-\theta X^T)^T+\alpha\|\theta\|_2^2 $$ This makes intuitive sense to me since minimize the cost function means minimizing the error (the left term) and minimizing the magnitudes of the coefficients (the right term) at the same time (or at least balancing the two minimizations).

My question is why is this regularization term $\alpha\|\theta\|_2^2$ added onto the original cost function and not multiplied or something else which keeps the spirit of the motivation behind the idea of regularization? Is it because if we simply add the term on it is sufficiently simple and enables us to solve this analytically or is there some deeper reason?

$\endgroup$
  • 1
    $\begingroup$ Another argument is via the representer theorem, $\endgroup$ – jkabrg May 22 '18 at 11:04
  • 2
    $\begingroup$ lagrangian multiplier $\endgroup$ – Haitao Du May 22 '18 at 14:46
  • 9
    $\begingroup$ If you have more independent variables than observations then you may be able get $\frac 1 2(y-\theta X^T)(y-\theta X^T)^T$ to zero several different ways, so multiplying by anything will not help distinguish a useful model $\endgroup$ – Henry May 22 '18 at 14:51
47
$\begingroup$

It has quite a nice intuition in the Bayesian framework. Consider that the regularized cost function $J$ has a similar role as the probability of a parameter configuration $\theta$ given the observations $X, y$. Applying the Bayes theorem, we get:

$$P(\theta|X,y) = \frac{P(X,y|\theta)P(\theta)}{P(X,y)}.$$

Taking the log of the expression gives us:

$$\log P(\theta|X,y) = \log P(X,y|\theta) + \log P(\theta) - \log P(X,y).$$

Now, let's say $J(\theta)$ is the negative1 log-posterior, $-\log P(\theta|X,y)$. Since the last term does not depend on $\theta$, we can omit it without changing the minimum. You are left with two terms: 1) the likelihood term $\log P(X,y|\theta)$ depending on $X$ and $y$, and 2) the prior term $ \log P(\theta)$ depending on $\theta$ only. These two terms correspond exactly to the data term and the regularization term in your formula.

You can go even further and show that the loss function which you posted corresponds exactly to the following model:

$$P(X,y|\theta) = \mathcal{N}(y|\theta X, \sigma_1^2),$$ $$P(\theta) = \mathcal{N}(\theta | 0, \sigma_2^2),$$

where parameters $\theta$ come from a zero-mean Gaussian distribution and the observations $y$ have zero-mean Gaussian noise. For more details see this answer.


1 Negative since you want to maximize the probability but minimize the cost.

$\endgroup$
  • 5
    $\begingroup$ I'm slightly unsatisfied by this answer because it just hand waves the correspondence between the cost function and the log-posterior. If the cost didn't correspond to the log-posterior but rather the posterior itself, we'd conclude the regularization should be multiplied to the non-regularized cost (like the OP asked about). -- To properly justify this answer, you'd need to justify why it's the log-posterior which we're equating to the cost. (You sort of do with the "go even further", but you get a bit hand-wavy at that point.) $\endgroup$ – R.M. May 22 '18 at 15:01
  • 1
    $\begingroup$ @R.M., valid point. There is a reason: it's because standard loss functions used in machine learning correspond to the log-posterior rather than the posterior itself. Why? Because they use empirical risk minimization; $\log P(X_1,\dots,X_n,y_1,\dots,y_n|\theta) = \sum_i \log P(X_i,y_i|\theta)$, and standard loss functions usually take the form $\sum_i f(X_i,y_i,\theta_i)$ where $f$ is a loss function that has a sensible interpretation as a log-posterior probability. (I suspect you know this, but I'm just spelling it out for other visitors.) $\endgroup$ – D.W. May 22 '18 at 20:42
  • $\begingroup$ @R.M. If you have some cost $C$ you could always just redefine your problem in terms of $C = \exp{\ln C}$. In other words, whatever your cost function is, it defines a distribution based on $\exp{\ln C}$ divided by some normalizing constant that you can ignore when using MCMC methods. The fact you can always restate in terms of an exponential is very important for e.g. simulated annealing, MCMC samplers, etc. $\endgroup$ – ely May 23 '18 at 20:40
  • $\begingroup$ @R.M., for example, consider this paper by Jun Liu (and there is a similar comment in Liu's MCMC book), where on page 3 at the bottom it says, "Let $\pi(x) = c\exp{-h(x)}$ be the target probability distribution under investigation (presumably all pdfs can be written in this form)" (emphasis added) . So from the Bayesian point of view where the portion of the posterior defined by the likelihood model would be this loss function, this Bayesian decomposition for this answer would be fully general. $\endgroup$ – ely May 23 '18 at 20:49
  • $\begingroup$ Thanks for the answer! I'm trying to understand the "it" at the beginning of your post: what exactly are you claiming has nice intuition within the bayesian framework? the fundamental reason why adding penalties gives good estimators? or the historical (and nonstatistical) reason why people use these additive estimators? (As I was trying to get my phrasing to suggest, I think your answer addresses the historical reason rather than a statistical reason.) $\endgroup$ – user795305 Jun 4 '18 at 21:27
34
$\begingroup$

Jan and Cagdas give a good Bayesian reason, interpreting the regularizer as a prior. Here are some non-Bayesian ones:

  • If your unregularized objective is convex, and you add a convex regularizer, then your total objective will still be convex. This won't be true if you multiply it, or most other methods of combining. Convex optimization is really, really nice compared to non-convex optimization; if the convex formulation works, it's nicer to do that.

  • Sometimes it leads to a very simple closed form, as wpof mentions is the case for ridge regression.

  • If you think of the problem you "really" want to solve as a problem with a hard constraint $$ \min_{\theta : c(\theta) \le 0} J(\theta) ,$$ then its Lagrange dual is the problem $$ \min_\theta J(\theta) + \lambda c(\theta) .$$ Though you don't have to use Lagrange duality, a lot is understood about it.

  • As ogogmad mentioned, the representer theorem applies to the case of an additive penalty: if you want to optimize $f$ over a whole reproducing kernel Hilbert space of functions $\mathcal H$, then we know that the solution to optimization over the whole space $$ \min_{f \in \mathcal H} J(f) + \lambda \lVert f \rVert_{\mathcal H}^2 $$ lies in a simple finite-dimensional subspace for many losses $J$; I don't know if this would hold for a multiplicative regularizer (though it might). This is the underpinning of kernel SVMs.

  • If you're doing deep learning or something non-convex anyway: additive losses give simple additive gradients. For the simple $L_2$ regularizer you gave, it becomes very simple weight decay. But even for a more complicated regularizer, say the WGAN-GP's loss $$ \sum_{x,y} \underbrace{f_\theta(x) - f_\theta(y)}_\text{the loss} + \lambda \underbrace{\mathbb{\hat E}_{\alpha \sim \mathrm{Uniform}(0, 1)} \left( \lVert \nabla f_\theta(\alpha x + (1 - \alpha) y) \rVert - 1\right)^2}_\text{the regularizer}, $$ it's easier for backpropagation to compute gradients when it only has to consider the sum of the loss and the complicated regularizer (considering things separately), instead of having to do the product rule.

  • Additive losses are also amenable to the popular ADMM optimization algorithm, and other "decomposition"-based algorithms.

None of these are hard-and-fast rules, and indeed sometimes a multiplicative (or some other) regularizer might work better (as ogogmad points out). (In fact, I just the other day submitted a paper about how something you could interpret as a multiplicative regularizer does better than the WGAN-GP additive one above!) But hopefully this helps explain why additive regularizers are "the default."

$\endgroup$
13
$\begingroup$

You want to minimize both terms in the objective function. Therefore, you need to decouple the terms. If you multiply the terms you can have one term large and the other very low. So, you still end up with a low value of the objective function, but with an undesirable result.

You may end up with a model that has most variable close to zero with no predictive power.

enter image description here enter image description here

The objective function, which is the function that is to be minimized, can be constructed as the sum of cost function and regularization terms.

In case both are independent on each other, you get the values illustrated in the first figure for the objective. You see in case of the sum, there is only one minimum at (0, 0). In case of the product you have ambiguity. You have a whole hyper-surface equal to zero at (x=0 or y=0). So, the optimization algorithm can end up anywhere depending on your initialization. And it cannot decide which solution is better.

$\endgroup$
10
$\begingroup$

You can try other binary operations ($\max,\min,\times$) and see how they compare.

The problem with $\min$ and $\times$ is that if the error is $0$, then the regularized penalty will end up being $0$. This allows the model to overfit.

The problem with $\max$ is that you end up minimizing the "harder" of the two penalties (training error or regularization) but not the other.

In contrast, $+$ is simple and it works.

You might ask why not other binary operations? There's no argument that could rule them out, so why not indeed?

$\endgroup$
8
$\begingroup$

I think you have a valid question. To give you a proper answer you will have to understand the probabilistic nature of the problem.

In general the problem we are trying to solve is the following: Given data $D$ what is the distribution of hypotheses that explains this data. When we say hypothesis we mean a PDF (at least in this context). And a distribution of hypotheses is a PDF of PDFs, i.e., $p(H | D)$.

  1. $p(H | D)$ is a distribution over hypotheses given $D$. If we can find this then we can select one among these hypotheses, for example the one with the highest probability, or we may choose to average over all of them. A somewhat easier approach is to attack the problem from a different direction using the Bayes' Theorem.

    $$p(H|D) = \frac{p(D|H)\times p(H)}{p(D)}$$

  2. $p(D|H)$ is one of the hypothesis, it is also called likelihood. $p(H)$ is the distribution of the hypotheses in our universe of hypotheses before observing the data. After we observe the data we update our beliefs.

  3. $p(D)$ is the average of the hypotheses before we updated our beliefs.

Now if we take the $-\log$ of both sides of Bayes' equation we get:

$$-\log [p(H|D)] = -\log [p(D|H)] -\log [p(H)] + \log [p(D)]$$

Usually $p(D)$ is difficult to calculate. The good thing is it doesn't affect the result. It is simply a normalization constant.

Now for example if our set of hypotheses $p(D|H)$ is a bunch of Gaussians with $p(y|X,\theta)\sim N(\theta X,\sigma)$ where we don't know $\theta$, but assume to know $\sigma$ (or at least assume that it is a constant), and moreover hypotheses themselves are distributed as a Gaussian with $p(H) = p(\theta) \sim N(0,\alpha^{-1} I)$ then plugging everything above looks something like:

$$-\log [p(H|D)] = \text{bunch of constants} + \frac{1}{2}(y-\theta X)^2 + \frac{1}{2}\alpha||\theta||^2 + {\rm constant}$$

Now if we minimize this expression we find the hypothesis with the highest probability. Constants don't affect the minimization. This is the expression in your question.

The fact that we used Gaussians doesn't change the fact the regularization term is additional. It must be additive (in log terms or multiplicative in probabilities), there is no other choice. What will change if we use other distributions is the components of the addition. The cost/loss function you have provided is optimal for a specific scenario of Gaussians.

$\endgroup$
  • $\begingroup$ Hey Cagdas, thanks for the explanation. I didn't understand the transformation of last equation on the RHS. Can you point to some resource for me to understand that part more clearly $\endgroup$ – Itachi May 22 '18 at 19:07
7
$\begingroup$

Ridge is a very convenient formulation. In contrast to the probabilistic answers, this answers does not give any interpretation of the estimate but instead explains why ridge is an old and obvious formulation.

In linear regression, the normal equations give $\hat{\theta} = (X^TX)^{-1} X^T y$

But, the matrix $X^TX$ is sometimes not invertible; one way to adjust it is by adding a small element to the diagonal: $X^TX + \alpha I$.

This gives the solution: $\tilde{\theta} = (X^TX + \alpha I)^{-1} X^T y$; then $\tilde{\theta}$ does not solve the original problem but instead the ridge problem.

$\endgroup$
  • 3
    $\begingroup$ Please specify the answers you are referring to. The ordering will move around as votes accumulate so "above" is inherently ambiguous. $\endgroup$ – gung - Reinstate Monica May 22 '18 at 14:47
1
$\begingroup$

I think there is a more intuitive reason as to why we can't multiply by the regularisation term.

Lets take our penalty function to the regular penalty function multiplied by a regularisation term like you suggest.

$$J(θ)=(\frac{1}{2}(y−θX^T)(y−θX^T)^T)α‖θ‖^2_2$$

Here we create a global minimum of the penalty function where $α‖θ‖^2_2=0$. In this case our model can produce high errors between the prediction and the data but it doesn't matter, if the model parameter weights are all zero our penalty function is zero $J(θ=0)=0$.

Since, unless our model is completely perfect, the term $(\frac{1}{2}(y−θX^T)(y−θX^T)^T)$ can never be zero (the probability that there exists a set θ to make our model 'perfect' is negligible for real data), then our model should always tend train towards the solution θ=0.

This is what it will return unless it gets stuck in a local minimum somewhere.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.