In most machine learning tasks where you can formulate some probability $p$ which should be maximised, we would actually optimize the log probability $\log p$ instead of the probability for some parameters $\theta$. E.g. in maximum likelihood training, it's usually the log-likelihood. When doing this with some gradient method, this involves a factor:

$$ \frac{\partial \log p}{\partial \theta} = \frac{1}{p} \cdot \frac{\partial p}{\partial \theta} $$

See here or here for some examples.

Of course, the optimization is equivalent, but the gradient will be different, so any gradient-based method will behave different (esp. stochastic gradient methods). Is there any justification that the $\log p$ gradient works better than the $p$ gradient?

  • 3
    you need to notice that we usually maximize likelihood using derivatives. On the other hand in many cases the independence condition is applied meaning that the Likelihood is the product of some iid probability density functions. Moreover product of many small values (in [0,1] interval) results in a very tiny value. This result in a computation difficulty. – TPArrow Sep 28 '15 at 9:20
  • @AlejandroRodriguez check out my answer here for more detail. – Paul Oct 12 '15 at 17:34
up vote 47 down vote accepted
+50

Gradient methods generally work better optimizing $\log p(x)$ than $p(x)$ because the gradient of $\log p(x)$ is generally more well-scaled. That is, it has a size that consistently and helpfully reflects the objective function's geometry, making it easier to select an appropriate step size and get to the optimum in fewer steps.

To see what I mean, compare the gradient optimization process for $p(x) = \exp(-x^2)$ and $f(x) = \log p(x) = -x^2$. At any point $x$, the gradient of $f(x)$ is $$f'(x) = -2x.$$ If we multiply that by $1/2$, we get the exact step size needed to get to the global optimum at the origin, no matter what $x$ is. This means that we don't have to work too hard to get a good step size (or "learning rate" in ML jargon). No matter where our initial point is, we just set our step to half the gradient and we'll be at the origin in one step. And if we don't know the exact factor that is needed, we can just pick a step size around 1, do a bit of line search, and we'll find a great step size very quickly, one that works well no matter where $x$ is. This property is robust to translation and scaling of $f(x)$. While scaling $f(x)$ will cause the optimal step scaling to differ from 1/2, at least the step scaling will be the same no matter what $x$ is, so we only have to find one parameter to get an efficient gradient-based optimization scheme.

In contrast, the gradient of $p(x)$ has very poor global properties for optimization. We have $$p'(x) = f'(x) p(x)= -2x \exp(-x^2).$$ This multiplies the perfectly nice, well-behaved gradient $-2x$ with a factor $\exp(-x^2)$ which decays (faster than) exponentially as $x$ increases. At $x = 5$, we already have $\exp(-x^2) = 1.4 \cdot 10^{-11}$, so a step along the gradient vector is about $10^{-11}$ times too small. To get a reasonable step size toward the optimum, we'd have to scale the gradient by the reciprocal of that, an enormous constant $\sim 10^{11}$. Such a badly-scaled gradient is worse than useless for optimization purposes - we'd be better off just attempting a unit step in the uphill direction than setting our step by scaling against $p'(x)$! (In many variables $p'(x)$ becomes a bit more useful since we at least get directional information from the gradient, but the scaling issue remains.)

In general there is no guarantee that $\log p(x)$ will have such great gradient scaling properties as this toy example, especially when we have more than one variable. However, for pretty much any nontrivial problem, $\log p(x)$ is going to be way, way better than $p(x)$. This is because the likelihood is a big product with a bunch of terms, and the log turns that product into a sum, as noted in several other answers. Provided the terms in the likelihood are well-behaved from an optimization standpoint, their log is generally well-behaved, and the sum of well-behaved functions is well-behaved. By well-behaved I mean $f''(x)$ doesn't change too much or too rapidly, leading to a nearly quadratic function that is easy to optimize by gradient methods. The sum of a derivative is the derivative of the sum, no matter what the derivative's order, which helps to ensure that that big pile of sum terms has a very reasonable second derivative!

  • 3
    +1 This answer brings up and emphasizes points that get to the heart of the matter. – whuber Oct 12 '15 at 16:26

Underflow

The computer uses a limited digit floating point representation of fractions, multiplying so many probabilities is guaranteed to be very very close to zero.

With $log$, we don't have this issue.

  • 3
    +1 for numerical stability - this and the Yuril's answer should be one! – Alec Teal Sep 29 '15 at 0:02
  • 1
    You can calculate the product in log-space, thus it becomes a sum, and then transfer it back. Or you calculate $\frac{\partial \log p}{\partial \theta} \cdot p$ which is equal to $\frac{\partial p}{\partial \theta}$. So, numerical stability is not the question. – Albert Sep 29 '15 at 6:58
  • 1
    Keep in mind that the $p$ you mentioned, is the multiplication of the probabilities of the all of the events in the sample, and $p$ is the element subject to underflow. – Uri Goren Sep 29 '15 at 7:21
  • 5
    @Filip The terminology in this thread is somewhat ill-advised. We're discussing probability densities, not probabilities. Densities are arbitrary: they depend on the units of measurement. Moreover, for sufficient sample sizes the probability density of any simple sample from a parametric model will eventually be less than $2^{-127}$. In large problems (with millions of data), probability densities routinely are $2^{-1000000}$ or smaller. Even a sample of size $80$ from the standard Normal distribution is almost certain to have a probability density less than $2^{-127}$. – whuber Sep 29 '15 at 20:53
  • 4
    @FilipHaglund : whuber is correct, however, the fact that it's densities isn't the crucial observation here. We could just as well be discussing a discrete process and talking about actual probabilities (and in fact, the OP did not say anything that excludes this case). But we're talking about probabilities for very specific outcomes (e.g., a million observations going some particular way). A single specific outcome is unlikely, but in Bayesian inference ratios of probabilities are important, so we need to know how much bigger is one tiny probability from another. – Meni Rosenfeld Oct 10 '15 at 20:31
  1. The logarithm of the probability of multiple joint probabilities simplifies to the sum of the logarithms of the individual probabilities (and the sum rule is easier than the product rule for differentiation)

    $\log \left(\prod_i P(x_i)\right) = \sum_i \log \left( P(x_i)\right)$

  2. The logarithm of a member of the family of exponential probability distributions (which includes the ubiquitous normal) is polynomial in the parameters (i.e. max-likelihood reduces to least-squares for normal distributions)

    $\log\left(\exp\left(-\frac{1}{2}x^2\right)\right) = -\frac{1}{2}x^2$

  3. The latter form is both more numerically stable and symbolically easier to differentiate than the former.

  4. Last but not least, the logarithm is a monotonic transformation that preserves the locations of the extrema (in particular, the estimated parameters in max-likelihood are identical for the original and the log-transformed formulation)

  • 4
    Reason 2 cannot be stressed enough. To maximize the log-likelihood for a linear model with Gaussian noise, you just have to solve a least-squares problem, which amounts to solving a linear system of equations. – Paul Sep 28 '15 at 16:41
  • Reason 1 and 3 just describe how to calculate it. You can calculate it that way and then convert it back (multiply by $p$) to get $\frac{\partial p}{\partial \theta}$. It's actually quite common to calculate in log-space for numerical stability. But that does not explain why you use that gradient. Reason 4 also is not a reason why the $\log p$ gradient is better. You can do that with many other transformations, too. Reason 2 is interesting but I'm still not exactly sure why the gradient of a polynomial is better than the gradient of another function. – Albert Sep 29 '15 at 7:04
  • @Albert the derivative of a polynomial is a polynomial of one degree lower (in particular, quadratic goes to linear), whereas exponentials don't simply under differentiation – TemplateRex Sep 29 '15 at 7:18
  • @TemplateRex: Yes, that's clear. But I'm asking about the convergence properties in a stochastic gradient method. – Albert Sep 29 '15 at 13:16

It is much easier to take a derivative of sum of logarithms than to take a derivative of product, that contains, say, 100 multipliers.

  • 10
    Plus you reduce potential numerical problems when terms become very small or large. – Björn Sep 28 '15 at 9:17
  • 8
    On the contrary, the OP implicitly provides an excellent way to compute the derivative of any product of nonnegative functions: multiply the sum of the derivatives of the logs by the product itself. (This multiplication is best carried out in terms of logarithms, which eliminates the numerical problems referred to in @Björn's comment, too.) Thus, "ease" offers no real explanatory power, nor does it address the more meaningful question about comparing the gradients. – whuber Sep 28 '15 at 16:53

As a general rule, the most basic and easy optimization problem is to optimize a quadratic function. You can easily find the optimum of such a function no matter where you start. How this manifests depends on the specific method but the closer your function to a quadratic, the better.

As noted by TemplateRex, in a wide variety of problems, the probabilities that go into calculating the likelihood function come from the normal distribution, or are approximated by it. So if you work on the log, you get a nice quadratic function. Whereas if you work on the probabilities, you have a function that

  1. Is not convex (the bane of optimization algorithms everywhere)
  2. Crosses multiple scales rapidly, and therefore has a very narrow range where the function values are indicative of where to direct your search.

Which function would you rather optimize, this, or this?

(This was actually an easy one; in practical applications your search can start so far off the optimum that the function values and gradients, even if you were able to compute them numerically, will be indistinguishable from 0 and useless for the purposes of the optimization algorithm. But transforming to a quadratic function makes this a piece of cake.)

Note that this is completely consistent with the numerical stability issues already mentioned. The reason log scale is required to work with this function, is exactly the same reason that the log probability is much better behaved (for optimization and other purposes) than the original.

You could also approach this another way. Even if there was no advantage to the log (which there is) - we're gonna use the log scale anyway for derivations and calculation, so what reason is there to apply the exp transformation just for computing the gradient? We may as well remain consistent with the log.

  • @TemplateRex: The log of a (downward) convex positive function is convex, but the converse isn't true. The probabilities aren't convex so they have nothing to preserve, but the log is convex. Look at the graphs I linked - exp(-10x^2) is obviously non-convex, but -10x^2 is. – Meni Rosenfeld Sep 29 '15 at 20:36

By using the $\ln p$ we increase the dynamic range of the optimization algorithm. The $p$ in applications is usually a product of functions. For instance, in maximum likelihood estimation it's the product of the form $L(x|\theta)=\Pi_{i=1}^n f(x_i|\theta)$, where $f(.)$ is the density function, which can be greater or less than 1, btw.

So, when $n$ is very large, i.e. large sample, your likelihood function $L(.)$ is usually far away from 1: it's either very small or very large, because it's a power function $L\sim f(.)^n$.

By taking a log we simply improve the dynamic range of any optimization algorithm, allowing it to work with extremely large or small values in the same way.

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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