Skip to content

bug in L-BFGS-B? (PR#8099)

12 messages · Berwin A Turlach, Peter Dalgaard, Brian Ripley

#
--WWm7B+u2U4
Content-Type: text/plain; charset=us-ascii
Content-Description: message body text
Content-Transfer-Encoding: 7bit

G'day all,

I believe that this is related to PR#1717 (filed under
not-reproducible) which was reported for a version of R that is a
quite a bit older than the ones used in for this report.  But I
noticed this behaviour under R 2.1.1 and R 2.2.0 on my linux box and
under R 2.0.1 and R 2.1.1 on my Windows box.

I recently ran the examples for fitdistr in the MASS library and on my
linux machine I get the following results:
shape         rate   
  6.45947303   0.13593172 
 (0.89052006) (0.01948648)
shape         rate    
  2.156761461   0.010000000 
 (0.277607887) (0.001433778)

I find the second result quite extraordinary.  O.k., the likelihood
that is maximised is quite flat along a certain direction, but I don't
think that it is so flat that it should fool the underlying
optimisation routine into believing that it has converged.

Moreover:
shape         rate   
  6.48686551   0.13651012 
 (0.89438949) (0.01956818)

As far as I can tell, the problem is with L-BFGS-B hitting the lower
bound and stopping, the same problem as reported in #1717.

I tried the same comments on my Windows box and the result is as
attached below (together with the system information that bug.report
produces on that machine).  Looking at the output given on the Windows
machine, I am actually amazed that my Linux box didn't give me any of
those warning messages --- the R input/output given above is cut and
paste.  I am not aware of any fiddling with ptions regarding warning
messages by any configurations files anywhere on my linux system; and I
ran the same commands using `R --vanilla' on the linux box and did not
get any warning messages.

Cheers,

        Berwin


--WWm7B+u2U4
Content-Type: text/plain
Content-Description: Manifestation of bug on a Windows machine
Content-Disposition: inline;
	filename="Bug.txt"
Content-Transfer-Encoding: 7bit
shape         rate   
  6.48592894   0.13649147 
 (0.89425721) (0.01956555)
Warning messages:
1: NaNs produced in: dgamma(x, shape, scale, log) 
2: NaNs produced in: dgamma(x, shape, scale, log) 
3: NaNs produced in: dgamma(x, shape, scale, log)
shape         rate    
  2.156761461   0.010000000 
 (0.277607888) (0.001433778)
Warning message:
bounds can only be used with method L-BFGS-B in: optim(start, mylogfn, x = x, hessian = TRUE, ...)
shape         rate   
  6.48686551   0.13651012 
 (0.89438949) (0.01956818)
Warning message:
bounds can only be used with method L-BFGS-B in: optim(start, mylogfn, x = x, hessian = TRUE, ...) 

--please do not edit the information below--

Version:
 platform = i386-pc-mingw32
 arch = i386
 os = mingw32
 system = i386, mingw32
 status = 
 major = 2
 minor = 1.1
 year = 2005
 month = 06
 day = 20
 language = R

Windows XP Professional (build 2600) Service Pack 2.0

Locale:
LC_COLLATE=English_Australia.1252;LC_CTYPE=English_Australia.1252;LC_MONETARY=English_Australia.1252;LC_NUMERIC=C;LC_TIME=English_Australia.1252

Search Path:
 .GlobalEnv, package:MASS, package:methods, package:stats, package:graphics, package:grDevices, package:utils, package:datasets, Autoloads, package:base

--WWm7B+u2U4
Content-Type: text/plain; charset=us-ascii
Content-Description: message body text
Content-Transfer-Encoding: 7bit


--please do not edit the information below--

Version:
 platform = i686-pc-linux-gnu
 arch = i686
 os = linux-gnu
 system = i686, linux-gnu
 status = Under development (unstable)
 major = 2
 minor = 2.0
 year = 2005
 month = 08
 day = 26
 svn rev = 35424
 language = R

Locale:
C

Search Path:
 .GlobalEnv, package:methods, package:stats, package:graphics, package:grDevices, package:utils, package:datasets, Autoloads, package:base

--WWm7B+u2U4--
#
Check your versions of MASS.  The Windows one appears to be an outdated 
version, and does different things.

As for the problem, yes it probably is a bug in L-BFGS-B.  Fancy debugging 
the code?
On Sat, 27 Aug 2005 berwin at maths.uwa.edu.au wrote:

            

  
    
#
Prof Brian Ripley <ripley at stats.ox.ac.uk> writes:
Forgetting to run tools/rsync-recommended during build will do that
sort of thing to you, but it would seem that Berwin used a binary
download. But of course he might be picking up an older version of the
package from a private library.
B. might just be capable of it, but this is certainly some of the more
impenetrable code in R. While he (or anyone else) is in there, there
seems to be another problem in that the Hessian calculations refuse to
stay within the bounds (which is pretty annoying when the objective
function is undefined outside of them). Try for instance

f <- function(p) sum(ifelse(p>=-1e-4,p,Inf)^2)
optim(f, lower=c(0,0), par=c(5,5), method="L-BFGS-B")
optim(f, lower=c(0,0), par=c(5,5), method="L-BFGS-B", hess=T)
#
On Sat, 27 Aug 2005, Peter Dalgaard wrote:

            
I think it is a case of the version released with 2.1.0 vs an update 
(possibly one post 2.1.1).
I think you will find that is as documented: see the return value stated.
Could be fixed though.
#
G'day Brian,

I am splitting my reply to your e-mail into two since there are two
separate spinoffs.
BDR> Check your versions of MASS.  The Windows one appears to be
    BDR> an outdated version, and does different things.
Thanks, yes, this is the problem.  On my linux box, I compile things
from source and had the latest version of MASS (7.2-19) installed
under R 2.1.1 and R 2.2.0.

Since I hardly ever work under Windows, I rely for my Windows box on
the precompiled versions provided from CRAN and do not compile R or
packages from source.  (Though I have it set up so that I can compile
my own packages.)  Actually, I only installed R 2.1.1 on that machine
(which has an AMD processor) yesterday and it was using MASS version
7.2-16.  Running `update.packages' today, updated MASS to version
7.2-18.  And, lo and behold, there are no more warning messages, even
more, running the example in `fitdistr' now returns:
shape         rate   
  6.45947303   0.13593172 
 (0.89052006) (0.01948648)
shape         rate   
  6.48714685   0.13651706 
 (0.89442924) (0.01956916)

So it was perhaps lucky that I did not run update.packages yesterday,
since I would have expected that (like PR#1717) my bug report would be
filed under not-reproducible. :-)

But this made me curious, and I fired my laptop (which has an Intel
chip) up under Windows (usually it runs under Linux) and installed R
2.1.1 on it.  On that Windows machine, I get the same answers as those
reported yesterday under both MASS 7.2-16 and 7.2-18.  Thus, I am a
bit baffled.  Well, I just went back to the AMD box and re-run the
code, now it gives me again the "nonsense" answer in the second case.
There is definitely something wrong in the L-BFGS-B routine, which
will be hard to find.

Regarding the changed subject line:

After installing R 2.1.1 on my laptop, I executed an R source file
which, essentially, only contains an install.packages command with the
list of contributed packages that I like to have installed.  One of
this packages is DAAG and it seems that overnight the file
DAAG_0.58.zip disappeared from
        http://mirror.aarnet.edu.au/pub/CRAN/bin/windows/contrib/2.1/
so the install.packages command terminated with an error message that
the source file could not be downloaded.

Would it be possible to robustify the install.packages command such
that it continues with installing all the other packages requested
instead of terminating?

After redirecting R 2.1.1 on my laptop to use 
        http://cran.au.r-project.org/
for the CRAN repository, the install.packages() command ran without
problems.  I issued the command `library(MASS)' and tried out the
example from fitdistr on that machine (same strange result for second
command and warning messages were issued).  So I said
update.packages()  and that command failed when it wanted to update
the MASS package.  So I detach()'ed MASS and re-ran update.packages()
and again it failed.  So I exited R 2.1.1 and restarted it again
(probably I should have unloaded the namespace of MASS??) and then the
update.packages command worked.

However, update.packages() wanted to update quite a few packages
besides MASS (the other packages in the VR bundle, nlme, lattice &c).
Once it failed on MASS, it terminated with an error and did not update
any of the other packages.  Would it be possible to robustify
update.packages behaviour such that it would continue in such
situations with updating the remaining packages?

Cheers,

        Berwin
#
G'day Brian,
BDR> As for the problem, yes it probably is a bug in L-BFGS-B.
    BDR> Fancy debugging the code?
I was afraid that somebody would ask this. ;-)

I looked a bit at the code and it seems to be non-trivial.  Moreover,
it seems to be code translated from FORTRAN to C via f2c and I am not
a fan of such kind of code.  I know that "Writing R Extensions" lists
in Appendix B ("R coding standards") f2c as a tool that `can "safely
be assumed" for R extensions'.  However, f2c, despite its `-A' option,
does not produce ANSI C compliant code but rather C code that provokes
undefined behaviour.

The problem is, that the code produced by f2c is decrementing pointers
to simulate 1-based vectors and the C FAQ is pretty unambigious about
the fact that this provokes undefined behaviour, see
        http://www.eskimo.com/~scs/C-faq/q6.17.html

As far as I understand, this translated code mostly stems from the
time when some platforms did not have ready access to a fortran
compiler and, hence, f2c was used (extensively?).  But now, with g77
this does not seem to be an issue anymore.  So I wonder whether there
are any plans of returning to the original fortran code?  Or are there
plans to clean up these f2c'd code snippet to make them ANSI C
compliant?  

I noticed such f2c'd code already in the splines.c file when I studied
how splinefun was implemented (which lead to bug report #8030).  In
that case, I am fairly familiar with the algorithms used in splines.c
since I programmed them myself on other occassions and I probably
could rewrite the algorithms in proper ANSI C (it would still take
some time).  But it would be nice to know what the official stance of
the R Core Team is.

When I spoke with one member of the R Core Team about this on a
conference in 2004, the answer was, IIRC, "yes, we know that this code
invokes undefined behaviour, but there are bigger problems to fix
first and this pointer manipulation seems to work on all platforms
these days."  Another member of the R Core Team whom I recently asked:

      I guess all platforms on which R is running at the moment do not
      have a problem with this trick, but are there any plans to
      change such kind of code to "valid" C?  Would patches that do
      that be accepted?

answered:

      Hmm, I think we'd tend to disagree here. But in any case that
      would be a wide issue.  Can you address this question to R-core,
      please?  (or I forward?)

Cheers,

        Berwin
#
Berwin A Turlach <berwin at maths.uwa.edu.au> writes:
There's more to it than that. F2c has also been used in places to make
Fortran code reentrant, which it is generally not. I forget whether we
were ever bitten by nested calls to optim(), but we certainly was by
integrate().

There is of course no argument against the fact that the
pointer-decrement trick goes against the C specs, but I do wonder
whether it is *actually* biting anyone these days. The remarks in the
C FAQ seem to mainly refer to segmented architectures like the
original IBM PC. With modern flat address spaces, it would seem quite
unlikely to run into trouble.
#
We've never encountered this lying mirror problem.  Perhaps you (or 
another user of the unreliable mirror) could contribute suitable fixes.
On Sun, 28 Aug 2005, Berwin A Turlach wrote:

            
Yes, and that *is* in the rw-FAQ.
Not a good idea. Better to follow the FAQ.  At that point the dependencies 
have been worked out and will not be re-computed if a package installation 
fails.
#
On Sun, 28 Aug 2005, Prof Brian Ripley wrote:

            
I checked, and I am unable to reproduce this.  I get
trying URL 
'http://cran.at.r-project.org/bin/windows/contrib/2.2/tree_1.0-19.zip'
Content type 'application/zip' length 144676 bytes
opened URL
downloaded 141Kb

package 'tree' successfully unpacked and MD5 sums checked

The downloaded packages are in
         C:\Documents and Settings\ripley\Local 
Settings\Temp\Rtmp13777\downloaded_packages
updating HTML package descriptions
Warning message:
package MASS is in use and will not be installed

which seems perfectly reasonable.
#
G'day Brian,
BDR> We've never encountered this lying mirror problem.
Indeed, that mirror is a worry, I guess that is the reason why it is
not on the official mirror list.

We had the problem with install.packages/update.packages under linux
too: source packages that supposedly should have been on the mirror
were not and the commands just terminated with an error message instead
of installing all those packages that could be found.  

Unfortunately, the way we are charged for internet traffic, it is much
cheaper for us to use mirror.aarnet.edu.au than any other mirror.  I
remember that last year around this time (give or take a some months)
when a new R version was released (2.0.0?) it took actually quite some
time before the sources appeared on the mirror, the directory
structure was mirrored, but not the files.  That was when I decided to
(temporarily) change mirrors.

    BDR> Perhaps you (or another user of the unreliable mirror) could
    BDR> contribute suitable fixes.
I will look into this when I find some time.

Cheers,

        Berwin
#
G'day Brian,
>>> However, update.packages() wanted to update quite a few
    >>> packages besides MASS (the other packages in the VR bundle,
    >>> nlme, lattice &c).  Once it failed on MASS, it terminated with
    >>> an error and did not update any of the other packages.  Would
    >>> it be possible to robustify update.packages behaviour such
    >>> that it would continue in such situations with updating the
    >>> remaining packages?
    >>  Not a good idea. Better to follow the FAQ.  At that point the
    >> dependencies have been worked out and will not be re-computed
    >> if a package installation fails.

    BDR> I checked, and I am unable to reproduce this.  I get
O.k., I tried to reproduce the behaviour.  So I installed the binary
distribution of R 2.1.1 in another directory on my laptop once more
(and then deleted the copy that I actually wanted to keep; shouldn't
do such things at this time of the day).

So below I attach what is, I believe a faithful reproduction of what I
tried to do yesterday.  Except that I did not run the file that
installs all the contributed packages that I like to have installed.

But it seems that now VR_7.2-17.zip has vanished from
mirror.aarnet.edu.au and you can see how on the first occassion the
download stops with an error.  I believe that in this case it could
have continued to download the other files.

Once I changed the mirror, the other behaviour that I mentioned
becomes apparent.  But I take your point that because of package
dependencies it might actually be not wise to continue with updating
further packages once the update of a package has failed.  But then,
shouldn't in that case (by the same argument) all the updates that
have been done already be undone again?

Cheers,

        Berwin

++++++++++++++++++ Transcript of R session ++++++++++++++++++++++++++++

R : Copyright 2005, The R Foundation for Statistical Computing
Version 2.1.1  (2005-06-20), ISBN 3-900051-07-0

R is free software and comes with ABSOLUTELY NO WARRANTY.
You are welcome to redistribute it under certain conditions.
Type 'license()' or 'licence()' for distribution details.

  Natural language support but running in an English locale

R is a collaborative project with many contributors.
Type 'contributors()' for more information and
'citation()' on how to cite R or R packages in publications.

Type 'demo()' for some demos, 'help()' for on-line help, or
'help.start()' for a HTML browser interface to help.
Type 'q()' to quit R.
boot :
 Version 1.2-22 installed in C:/PROGRA~1/R/rw2011/library 
 Version 1.2-23 available at http://mirror.aarnet.edu.au/pub/CRAN
Update (y/N/c)?  y
VR :
 Version 7.2-16 installed in C:/PROGRA~1/R/rw2011/library 
 Version 7.2-17 available at http://mirror.aarnet.edu.au/pub/CRAN
Update (y/N/c)?  y
cluster :
 Version 1.10.0 installed in C:/PROGRA~1/R/rw2011/library 
 Version 1.10.1 available at http://mirror.aarnet.edu.au/pub/CRAN
Update (y/N/c)?  y
foreign :
 Version 0.8-8 installed in C:/PROGRA~1/R/rw2011/library 
 Version 0.8-9 available at http://mirror.aarnet.edu.au/pub/CRAN
Update (y/N/c)?  y
lattice :
 Version 0.11-8 installed in C:/PROGRA~1/R/rw2011/library 
 Version 0.12-3 available at http://mirror.aarnet.edu.au/pub/CRAN
Update (y/N/c)?  y
mgcv :
 Version 1.3-1 installed in C:/PROGRA~1/R/rw2011/library 
 Version 1.3-4 available at http://mirror.aarnet.edu.au/pub/CRAN
Update (y/N/c)?  y
nlme :
 Version 3.1-60 installed in C:/PROGRA~1/R/rw2011/library 
 Version 3.1-62 available at http://mirror.aarnet.edu.au/pub/CRAN
Update (y/N/c)?  y
trying URL 'http://mirror.aarnet.edu.au/pub/CRAN/bin/windows/contrib/2.1/boot_1.2-23.zip'
Content type 'application/zip' length 767814 bytes
opened URL
downloaded 749Kb

trying URL 'http://mirror.aarnet.edu.au/pub/CRAN/bin/windows/contrib/2.1/VR_7.2-17.zip'
Error in download.file(url, destfile, method, mode = "wb") : 
        cannot open URL 'http://mirror.aarnet.edu.au/pub/CRAN/bin/windows/contrib/2.1/VR_7.2-17.zip'
In addition: Warning message:
cannot open: HTTP status was '404 Not Found'
CRAN 
"http://cran.au.r-project.org/"
boot :
 Version 1.2-22 installed in C:/PROGRA~1/R/rw2011/library 
 Version 1.2-23 available at http://cran.au.r-project.org
Update (y/N/c)?  y
VR :
 Version 7.2-16 installed in C:/PROGRA~1/R/rw2011/library 
 Version 7.2-19 available at http://cran.au.r-project.org
Update (y/N/c)?  y
cluster :
 Version 1.10.0 installed in C:/PROGRA~1/R/rw2011/library 
 Version 1.10.1 available at http://cran.au.r-project.org
Update (y/N/c)?  y
foreign :
 Version 0.8-8 installed in C:/PROGRA~1/R/rw2011/library 
 Version 0.8-10 available at http://cran.au.r-project.org
Update (y/N/c)?  y
lattice :
 Version 0.11-8 installed in C:/PROGRA~1/R/rw2011/library 
 Version 0.12-5 available at http://cran.au.r-project.org
Update (y/N/c)?  y
mgcv :
 Version 1.3-1 installed in C:/PROGRA~1/R/rw2011/library 
 Version 1.3-6 available at http://cran.au.r-project.org
Update (y/N/c)?  y
nlme :
 Version 3.1-60 installed in C:/PROGRA~1/R/rw2011/library 
 Version 3.1-64 available at http://cran.au.r-project.org
Update (y/N/c)?  y
trying URL 'http://cran.au.r-project.org/bin/windows/contrib/2.1/boot_1.2-23.zip'
Content type 'application/zip' length 767814 bytes
opened URL
downloaded 749Kb

trying URL 'http://cran.au.r-project.org/bin/windows/contrib/2.1/VR_7.2-19.zip'
Content type 'application/zip' length 1575000 bytes
opened URL
downloaded 1538Kb

trying URL 'http://cran.au.r-project.org/bin/windows/contrib/2.1/cluster_1.10.1.zip'
Content type 'application/zip' length 480389 bytes
opened URL
downloaded 469Kb

trying URL 'http://cran.au.r-project.org/bin/windows/contrib/2.1/foreign_0.8-10.zip'
Content type 'application/zip' length 176663 bytes
opened URL
downloaded 172Kb

trying URL 'http://cran.au.r-project.org/bin/windows/contrib/2.1/lattice_0.12-5.zip'
Content type 'application/zip' length 713040 bytes
opened URL
downloaded 696Kb

trying URL 'http://cran.au.r-project.org/bin/windows/contrib/2.1/mgcv_1.3-6.zip'
Content type 'application/zip' length 795159 bytes
opened URL
downloaded 776Kb

trying URL 'http://cran.au.r-project.org/bin/windows/contrib/2.1/nlme_3.1-64.zip'
Content type 'application/zip' length 2142405 bytes
opened URL
downloaded 2092Kb

package 'boot' successfully unpacked and MD5 sums checked
bundle 'VR' successfully unpacked and MD5 sums checked
Error: cannot remove prior installation of package 'MASS'
[1] ".GlobalEnv"        "package:MASS"      "package:methods"  
 [4] "package:stats"     "package:graphics"  "package:grDevices"
 [7] "package:utils"     "package:datasets"  "Autoloads"        
[10] "package:base"
VR :
 Version 7.2-16 installed in C:/PROGRA~1/R/rw2011/library 
 Version 7.2-19 available at http://cran.au.r-project.org
Update (y/N/c)?  y
cluster :
 Version 1.10.0 installed in C:/PROGRA~1/R/rw2011/library 
 Version 1.10.1 available at http://cran.au.r-project.org
Update (y/N/c)?  y
foreign :
 Version 0.8-8 installed in C:/PROGRA~1/R/rw2011/library 
 Version 0.8-10 available at http://cran.au.r-project.org
Update (y/N/c)?  y
lattice :
 Version 0.11-8 installed in C:/PROGRA~1/R/rw2011/library 
 Version 0.12-5 available at http://cran.au.r-project.org
Update (y/N/c)?  y
mgcv :
 Version 1.3-1 installed in C:/PROGRA~1/R/rw2011/library 
 Version 1.3-6 available at http://cran.au.r-project.org
Update (y/N/c)?  y
nlme :
 Version 3.1-60 installed in C:/PROGRA~1/R/rw2011/library 
 Version 3.1-64 available at http://cran.au.r-project.org
Update (y/N/c)?  y
trying URL 'http://cran.au.r-project.org/bin/windows/contrib/2.1/VR_7.2-19.zip'
Content type 'application/zip' length 1575000 bytes
opened URL
downloaded 1538Kb

trying URL 'http://cran.au.r-project.org/bin/windows/contrib/2.1/cluster_1.10.1.zip'
Content type 'application/zip' length 480389 bytes
opened URL
downloaded 469Kb

trying URL 'http://cran.au.r-project.org/bin/windows/contrib/2.1/foreign_0.8-10.zip'
Content type 'application/zip' length 176663 bytes
opened URL
downloaded 172Kb

trying URL 'http://cran.au.r-project.org/bin/windows/contrib/2.1/lattice_0.12-5.zip'
Content type 'application/zip' length 713040 bytes
opened URL
downloaded 696Kb

trying URL 'http://cran.au.r-project.org/bin/windows/contrib/2.1/mgcv_1.3-6.zip'
Content type 'application/zip' length 795159 bytes
opened URL
downloaded 776Kb

trying URL 'http://cran.au.r-project.org/bin/windows/contrib/2.1/nlme_3.1-64.zip'
Content type 'application/zip' length 2142405 bytes
opened URL
downloaded 2092Kb

bundle 'VR' successfully unpacked and MD5 sums checked
Error: cannot remove prior installation of package 'MASS'
[1] ".GlobalEnv"        "package:methods"   "package:stats"    
[4] "package:graphics"  "package:grDevices" "package:utils"    
[7] "package:datasets"  "Autoloads"         "package:base"
1 day later
#
On Mon, 29 Aug 2005, Prof Brian Ripley wrote:

            
The difference here was that it is install.packages("VR") which 
update.packages() uses, not install.packages("MASS"), and of course "VR" 
is not a package.

I've altered the code to check if any package in a bundle is in use.  We 
can only do that if installing from a repository (not a local zip file), 
but at least we can cover than base.

I've also changed the code to use warning() and not stop() if moving fails 
(although that is likely to be quite a serious problem).