4
$\begingroup$

Suppose I have a 1000-length vector of zeros and ones and I am modelling each of its components as an i.i.d. Bernoulli. Then the probability of that vector is

$$p(x | \theta) =\prod_{d=1}^{1000}\theta_d^{x_d}(1-\theta_d)^{1-x_d} $$

I want to maximize the log-likelihood through gradient descent.

$$\nabla_\theta logp(x|\theta) = \frac{1}{p(x|\theta)} \nabla_\theta\prod_{d=1}^{1000}\theta_d^{x_d}(1-\theta_d^{1-x_d}) $$

So for $\frac{\partial{logp(x|\theta)}}{\theta_i} $

$$\frac{\partial{logp(x|\theta)}}{\theta_i} = \frac{1}{p(x|\theta)} \prod_{d = 1, d\ne i}^{1000}\theta_d^{x_d}(1-\theta_d^{1-x_d})(x_i\theta_i^{x_i-1}(1-\theta_i)^{1-x_i}-(1-x_i)(1-\theta_i)^{-x_i})$$

where the last part is just the derivative (product rule) of a Bernoulli. Because the $x$'s are either 0 or 1 the last part,

$$ (x_i\theta_i^{x_i-1}(1-\theta_i)^{1-x_i}-(1-x_i)(1-\theta_i)^{-x_i})$$

works out to either 1 or -1. So the gradient with respect to $\theta$ can be negative.

What is stopping it from making $\theta_i$ less than zero? I am trying to implement this and I am running into this problem. Because the probabilities are so small I have to sum the logs but sometimes $\theta$ ends up negative.

$\endgroup$
  • 1
    $\begingroup$ you are forgetting to take logs on the products (logxy = logx + logy). $\endgroup$ – jpmuc Mar 12 '17 at 7:26
7
$\begingroup$

There are a couple issues with the expressions. I'll address these, then answer the question down below.

In your expression, $p(x \mid \theta)$ will always be 0 if $x=1$. It should be $\theta^{x_d} (1 - \theta)^{1-x_d}$ rather than $\theta^{x_d} (1 - \theta^{1-x_d})$. No need to subscript the thetas; the data are i.i.d. so $\theta$ is a single, scalar value that's shared for all data points. If performing gradient descent you'd work with the negative log likelihood (otherwise you'd be minimizing the likelihood rather than maximizing it). Use the log likelihood if using gradient ascent.

The negative log likelihood should be:

$$L(\theta) = -\log \prod_{d=1}^{n} \theta^{x_d} (1 - \theta)^{1-x_d}$$

The log of a product is a sum of logs so:

$$L(\theta) = -\sum_{d=1}^{n} \log \left ( \theta^{x_d} (1 - \theta)^{1-x_d} \right )$$

Differentiating w.r.t. $\theta$, we have:

$$\frac{d}{d\theta} L(\theta) = -\sum_{d=1}^{n} \left ( \frac{x_d}{\theta} + \frac{x_d-1}{1 - \theta} \right )$$

Can gradient descent ever set $\theta$ to be less than 0 or greater than 1? One thing that will tend to prevent this is that, when the data set contains a mix of zeros and ones, the negative log likelihood approaches infinity as $\theta$ approaches 0 or 1. This discourages gradient descent from approaching or exceeding these values; the gradient will pull $\theta$ back into a more reasonable range.

For example, here's the negative log likelihood and gradient for some points sampled i.i.d. from a Bernoulli distribution with true $\theta=0.7$:

enter image description here

But, say we set the step size too large. For example, say the current $\theta$ is 0.5 (so gradient descent will step in the positive direction), and the step size is some large value. We can overshoot the optimum ($\theta=0.7$), and even exceed the valid parameter range; $\theta$ could end up greater than 1. If this happens, the expression for the negative log likelihood will return a complex value because we'd be taking the log of a negative number. This breaks the optimization.

The case is different when the data set contains all zeros or all ones. For example, here's the negative log likelihood and gradient for 100 values that are all one:

enter image description here

The true value of $\theta$ is 1, which has a negative log likelihood of 0. But, looking at the expressions above, the gradient is -100. This means gradient descent will keep stepping in the positive direction. And, in this case, the expression for the negative log likelihood will produce increasingly negative values. So, gradient descent will continue to increase $\theta$ without bound.

The issue is that gradient descent is an unconstrained optimization algorithm, but this problem requires that $\theta \in [0, 1]$. Solving the problem correctly requires imposing this constraint. Of course, this particular problem can be solved by simply calculating the frequency of ones in the data (no need for iterative optimization). But, for the sake of illustration, there are a couple approaches that can work. One way is to reparameterize the problem. For example, we could let $\theta = \exp(\alpha)$, so $\alpha$ can take any real value and $\theta$ will always be positive. We can then use an unconstrained optimization algorithm to minimize the negative log likelihood w.r.t. $\alpha$. Another approach is to use an optimization algorithm that lets us impose bound constraints, which will force $\theta$ to lie in the correct range. There are dedicated solvers that can implement many kinds of constraints, and the best choice will depend on the particular problem. A simple example in this case would be to modify gradient descent to clip theta to the allowed range after each step: $\theta = \min(\max(\theta, 0), 1)$. This is an example of a 'gradient projection method'. There are other methods with faster convergence.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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