# Dealing with -Inf in a maximisation problem.

12 messages
Open this post in threaded view
|

## Dealing with -Inf in a maximisation problem.

 I am trying to deal with a maximisation problem in which it is possible for the objective function to (quite legitimately) return the value -Inf, which causes the numerical optimisers that I have tried to fall over. The -Inf values arise from expressions of the form "a * log(b)", with b = 0.  Under the *starting* values of the parameters, a must equal equal 0 whenever b = 0, so we can legitimately say that a * log(b) = 0 in these circumstances.  However as the maximisation algorithm searches over parameters it is possible for b to take the value 0 for values of a that are strictly positive.  (The values of "a" do not change during this search, although they *do* change between "successive searches".) Clearly if one is *maximising* the objective then -Inf is not a value of particular interest, and we should be able to "move away".  But the optimising function just stops. It is also clear that "moving away" is not a simple task; you can't estimate a gradient or Hessian at a point where the function value is -Inf. Can anyone suggest a way out of this dilemma, perhaps an optimiser that is equipped to cope with -Inf values in some sneaky way? Various ad hoc kludges spring to mind, but they all seem to be fraught with peril. I have tried changing the value returned by the objective function from "v" to exp(v) --- which maps -Inf to 0, which is nice and finite. However this seemed to flatten out the objective surface too much, and the search stalled at the 0 value, which is the antithesis of optimal. The problem arises in a context of applying the EM algorithm where the M-step cannot be carried out explicitly, whence numerical optimisation. I can give more detail if anyone thinks that it could be relevant. I would appreciate advice from younger and wiser heads! :-) cheers, Rolf Turner -- Technical Editor ANZJS Department of Statistics University of Auckland Phone: +64-9-373-7599 ext. 88276 ______________________________________________ [hidden email] mailing list -- To UNSUBSCRIBE and more, see https://stat.ethz.ch/mailman/listinfo/r-helpPLEASE do read the posting guide http://www.R-project.org/posting-guide.htmland provide commented, minimal, self-contained, reproducible code.
Open this post in threaded view
|

## Re: Dealing with -Inf in a maximisation problem.

 Have you tried reparameterizing, using logb (=log(b)) instead of b? Bill Dunlap TIBCO Software wdunlap tibco.com On Sun, Nov 6, 2016 at 1:17 PM, Rolf Turner <[hidden email]> wrote: > > I am trying to deal with a maximisation problem in which it is possible > for the objective function to (quite legitimately) return the value -Inf, > which causes the numerical optimisers that I have tried to fall over. > > The -Inf values arise from expressions of the form "a * log(b)", with b = > 0.  Under the *starting* values of the parameters, a must equal equal 0 > whenever b = 0, so we can legitimately say that a * log(b) = 0 in these > circumstances.  However as the maximisation algorithm searches over > parameters it is possible for b to take the value 0 for values of > a that are strictly positive.  (The values of "a" do not change during > this search, although they *do* change between "successive searches".) > > Clearly if one is *maximising* the objective then -Inf is not a value of > particular interest, and we should be able to "move away".  But the > optimising function just stops. > > It is also clear that "moving away" is not a simple task; you can't > estimate a gradient or Hessian at a point where the function value is -Inf. > > Can anyone suggest a way out of this dilemma, perhaps an optimiser that is > equipped to cope with -Inf values in some sneaky way? > > Various ad hoc kludges spring to mind, but they all seem to be fraught > with peril. > > I have tried changing the value returned by the objective function from > "v" to exp(v) --- which maps -Inf to 0, which is nice and finite. However > this seemed to flatten out the objective surface too much, and the search > stalled at the 0 value, which is the antithesis of optimal. > > The problem arises in a context of applying the EM algorithm where the > M-step cannot be carried out explicitly, whence numerical optimisation. > I can give more detail if anyone thinks that it could be relevant. > > I would appreciate advice from younger and wiser heads! :-) > > cheers, > > Rolf Turner > > -- > Technical Editor ANZJS > Department of Statistics > University of Auckland > Phone: +64-9-373-7599 ext. 88276 > > ______________________________________________ > [hidden email] mailing list -- To UNSUBSCRIBE and more, see > https://stat.ethz.ch/mailman/listinfo/r-help> PLEASE do read the posting guide http://www.R-project.org/posti> ng-guide.html > and provide commented, minimal, self-contained, reproducible code. >         [[alternative HTML version deleted]] ______________________________________________ [hidden email] mailing list -- To UNSUBSCRIBE and more, see https://stat.ethz.ch/mailman/listinfo/r-helpPLEASE do read the posting guide http://www.R-project.org/posting-guide.htmland provide commented, minimal, self-contained, reproducible code.
Open this post in threaded view
|

## Re: Dealing with -Inf in a maximisation problem.

Open this post in threaded view
|

## Re: Dealing with -Inf in a maximisation problem.

Open this post in threaded view
|

## Re: Dealing with -Inf in a maximisation problem.

Open this post in threaded view
|

## Re: Dealing with -Inf in a maximisation problem.

 In reply to this post by Rolf Turner On Mon, 7 Nov 2016, Rolf Turner wrote: > On 07/11/16 13:07, William Dunlap wrote: >> Have you tried reparameterizing, using logb (=log(b)) instead of b? > > Uh, no.  I don't think that that makes any sense in my context. > > The "b" values are probabilities and must satisfy a "sum-to-1" constraint. > To accommodate this constraint I re-parametrise via a "logistic" style > parametrisation --- basically > >   b_i = exp(z_i)/[sum_j exp(z_j)], j = 1, ... n > > with the parameters that the optimiser works with being z_1, ..., z_{n-1} > (and with z_n == 0 for identifiability).  The objective function is of the > form sum_i(a_i * log(b_i)), This is sum_i(a_i * z_i) - sum(a_i)*log(sum_j(exp(z_j)), isn't it? So you don't need to evaluate b_i here, do you? Large values of z_j will lead to exp(z_j) == Inf, but using   sum_i(a_i * (z_i-max.z)) - sum(a_i)*log(sum_j(exp(z_j-max.z)) will handle that. HTH, Chuck p.s. Regarding "advice from younger and wiser heads", I probably cannot claim to be either. ______________________________________________ [hidden email] mailing list -- To UNSUBSCRIBE and more, see https://stat.ethz.ch/mailman/listinfo/r-helpPLEASE do read the posting guide http://www.R-project.org/posting-guide.htmland provide commented, minimal, self-contained, reproducible code.
Open this post in threaded view
|

## Re: Dealing with -Inf in a maximisation problem.

 On 07/11/16 15:46, Charles C. Berry wrote: > On Mon, 7 Nov 2016, Rolf Turner wrote: > >> On 07/11/16 13:07, William Dunlap wrote: >>> Have you tried reparameterizing, using logb (=log(b)) instead of b? >> >> Uh, no.  I don't think that that makes any sense in my context. >> >> The "b" values are probabilities and must satisfy a "sum-to-1" >> constraint. To accommodate this constraint I re-parametrise via a >> "logistic" style parametrisation --- basically >> >>   b_i = exp(z_i)/[sum_j exp(z_j)], j = 1, ... n >> >> with the parameters that the optimiser works with being z_1, ..., >> z_{n-1} (and with z_n == 0 for identifiability).  The objective >> function is of the form sum_i(a_i * log(b_i)), > > > This is sum_i(a_i * z_i) - sum(a_i)*log(sum_j(exp(z_j)), isn't it? > > So you don't need to evaluate b_i here, do you? > > Large values of z_j will lead to exp(z_j) == Inf, but using > >     sum_i(a_i * (z_i-max.z)) - sum(a_i)*log(sum_j(exp(z_j-max.z)) > > will handle that. Wow!!!  That looks like it will work!!!  I won't completely believe it until I've programmed it up and tried it --- but for the first time in days I'm feeling hopeful. > > HTH, > > Chuck > > p.s. Regarding "advice from younger and wiser heads", I probably cannot > claim to be either. On present evidence you certainly appear to be one hell of a lot wiser!!! Thanks. cheers, Rolf -- Technical Editor ANZJS Department of Statistics University of Auckland Phone: +64-9-373-7599 ext. 88276 ______________________________________________ [hidden email] mailing list -- To UNSUBSCRIBE and more, see https://stat.ethz.ch/mailman/listinfo/r-helpPLEASE do read the posting guide http://www.R-project.org/posting-guide.htmland provide commented, minimal, self-contained, reproducible code.
Open this post in threaded view
|

## Re: Dealing with -Inf in a maximisation problem.

Open this post in threaded view
|

## Re: Dealing with -Inf in a maximisation problem.

Open this post in threaded view
|

## Re: Dealing with -Inf in a maximisation problem.

 In reply to this post by Rolf Turner > > I am trying to deal with a maximisation problem in which it is possible > for the objective function to (quite legitimately) return the value > -Inf, (Just to add to the pedantic part of the discuss by those of us that do not qualify as younger and wiser:) Setting log(0) to -Inf is often convenient but really I think the log function is undefined at zero, so I would not refer to this as "legitimate". >which causes the numerical optimisers that I have tried to fall over. In theory as well as practice. You need to have a function that is defined on the whole domain. > > The -Inf values arise from expressions of the form "a * log(b)", with b > = 0.  Under the *starting* values of the parameters, a must equal equal > 0 whenever b = 0, so we can legitimately say that a * log(b) = 0 in This also is undefined and not "legitimate". I think there is no reason it should be equal zero. We tend to want to set it to the value we think of as the "limit": for a=0 the limit as b goes to zero would be zero, but the limit of a*(-inf) is -inf as a goes to zero. So, you really do need to avoid zero because your function is not defined there, or find a redefinition that works properly at zero. I think you have a solution from another post. Paul > these circumstances.  However as the maximisation algorithm searches > over parameters it is possible for b to take the value 0 for values of > a that are strictly positive.  (The values of "a" do not change during > this search, although they *do* change between "successive searches".) > > Clearly if one is *maximising* the objective then -Inf is not a value of > particular interest, and we should be able to "move away".  But the > optimising function just stops. > > It is also clear that "moving away" is not a simple task; you can't > estimate a gradient or Hessian at a point where the function value is -Inf. > > Can anyone suggest a way out of this dilemma, perhaps an optimiser that > is equipped to cope with -Inf values in some sneaky way? > > Various ad hoc kludges spring to mind, but they all seem to be fraught > with peril. > > I have tried changing the value returned by the objective function from > "v" to exp(v) --- which maps -Inf to 0, which is nice and finite. > However this seemed to flatten out the objective surface too much, and > the search stalled at the 0 value, which is the antithesis of optimal. > > The problem arises in a context of applying the EM algorithm where the > M-step cannot be carried out explicitly, whence numerical optimisation. > I can give more detail if anyone thinks that it could be relevant. > > I would appreciate advice from younger and wiser heads! :-) > > cheers, > > Rolf Turner > > -- Technical Editor ANZJS Department of Statistics University of > Auckland Phone: +64-9-373-7599 ext. 88276 ______________________________________________ [hidden email] mailing list -- To UNSUBSCRIBE and more, see https://stat.ethz.ch/mailman/listinfo/r-helpPLEASE do read the posting guide http://www.R-project.org/posting-guide.htmland provide commented, minimal, self-contained, reproducible code.