Heavy bug in "exponential fit"??

[Herbert]

sorry,

my implemented version did not have any weights. To test the new modifications I put different weights (0.5 was last) and compared alpha and beta to the standard function.

Just throw that out and the weights are in.

About speed testing:

I did it similar to the test below measuring the speed of the dot-product function. This function is used at several places to calculate chisquare, instead of using the simple square- and add-functions.

Herbert

[Herbert]

Found out that the above test was "optimized" by the compiler:

Doing the same test working on a 2d-array, the dot product was 30% faster than the two basic functions.

Herbert

[altenbach]

---

@Herbert wrote:
I agree, with the two nested for-loops it does not look as elegant as the NI-solution but - in my case - is 10 fold faster.

---

OK, did some testing and for many typical scenarios yours is significantly more efficient than the stock algorithm and gives the same result. Kudos!

It IS slower for some scenarios. For example with 1000 data points and 200 parameters, yours is about 2x slower than stock. My modification is still 2x faster. 😉

There are still a few tweaks and simplifications possible and I got it about 3x faster than yours (note that you can parallelize the outer FOR loop, for example and the replace array subset is resizeable.... ;))

[Herbert]

---

@altenbach wrote:

---

@Herbert wrote:
I agree, with the two nested for-loops it does not look as elegant as the NI-solution but - in my case - is 10 fold faster.

---

OK, did some testing and for many typical scenarios yours is significantly more efficient than the stock algorithm and gives the same result. Kudos!

It IS slower for some scenarios. For example with 1000 data points and 200 parameters, yours is about 2x slower than stock. My modification is still 2x faster. 😉

There are still a few tweaks and simplifications possible and I got it about 3x faster than yours (note that you can parallelize the outer FOR loop, for example and the replace array subset is resizeable.... ;))

---

Thanks for your Kudos!

I consciously worded the beginning of my response to your first comment and I still keep up to my opening sentence!

As I am trying to improve fitting speed within a university-sponsored project, I would enjoy to get some details about how you are beating me by a factor of 3 - but only if I am allowed to use it under the condition of proper citing of the author.

In between I'll look at my solution and will try to find out, how you miracled the factor 3. Parallelization is most probably one of the keywords, but - I am still waiting for free time to dig into the details of that topic.

Herbert

[altenbach]

---

@Herbert wrote:
As I am trying to improve fitting speed within a university-sponsored project, I would enjoy to get some details about how you are beating me by a factor of 3 - but only if I am allowed to use it under the condition of proper citing of the author.

---

 Well, it is basically your code. Here's my quick benchmark comparing:

1. CA (a slightly cleaned up version of the stock code in (3). Less clutter :D) Speed is about the same as stock.
2. Herbert (the code you have attached above) Faster than stock if the number of parameters is much smaller than the number of data points.
3. Stock (Basically copied from Ni ABX code
4. Rewrite (basically Herbert, but added parallelization). Always fastest on a 4 core machine, haven't tried on others. If I disable parallelism, its similar to (2) so I expect no real gains on a single core machine.

I do get slightly different results in LabVIEW 2012 (e.g. parallelization gains slightly more), but it does not change the overall picture.

Please let me know if you see any mistakes. All four code fragments produce the same output.

For the defaults of 10000 points and 100 parameters, you are actually slowest. 😉

[Herbert]

Thanks for the details.

By the way, I found a solution to the exponential curve fit on the Matlab home page

http://www.mathworks.com/matlabcentral/fileexchange/21959-exponential-fit-without-start-guess

I translated it into LV and it works well, finds the good minimum for my data.

Herbert

[Topper_Harley]

Hi Herbert,

thank you for reporting your concern with the exponential fit function. Did any NI employee get in touch with you regarding this?

Regards, Topper

[Herbert]

---

@Topper_Harley wrote:

Hi Herbert,

thank you for reporting your concern with the exponential fit function. Did any NI employee get in touch with you regarding this?

Regards, Topper

---

Hi Topper,

thanks for asking, the answer is no. As I do not regularly check the forum, may I ask - in case - to directly contact me by Email?

Regards Herbert

[DSPGuy]

Herbert,

Thanks for looking so closely at the curve fitting functions.  You have raised some important points, so I'd like to reply to them one at a time.
1.  I'm not sure why you are having a problem with the exponential fit VI, but clearly we are not performaing as we should.  There is something about your data that is causing a failure or poor performance.  I realize that you have a solution that is working for you now, but it would be helpful to us if you could post your dataset so that we can track down our problem.  Is this possible?
2.  The implementation of the Levenberg-Marquardt (LM) algorithm was formulated after looking over many sources, including Numerical recipes.  Because of its success there has been a lot of research into all aspects of the original LM algorithm, and there are many variants available.  Testing these variants can be challenging, and so we make use of all the NIST nonlinear regression datasets (http://www.itl.nist.gov/div898/strd/nls/nls_main.shtml).  We choose the hardest starting values for each problem, and require correct solutions to all problems, without using analytic gradients.  Running this set of problems with the shipping algorithm yields a total number of fcn evals = 152720, with all problems passing.   If the damping strategy is chosen as Numerical Recipes, and the initial lambda value is .001, with update as lambda*10 and downdate as lambda/10, then the total number of function evals is 149335, with one test failing the precision requirements (misses this problem completely). 
If lambda is initially 10, with the numerical recipes update and downdate, then the total number of function evals is 92998, but with 3 failures.  Changing the update and downdate factors changes which tests may fail, but the end result is still a failed test.  
If we keep the shipping damping strategy, but use an initial lambda = 0.001, then total function evals=165492, and 2 tests fail.  We have investigated a number of combinations of update and downdate factors for lambda, both through experimentation and surveys of the literature, and have not found a clearly better combination for all problems tested.  The bottom line is that we have implemented and tuned the LM algorithm to perform well on this test suite.

As you know, the lambda parameter and its iterative adaptation, allows the LM algorithm to move between two different update directions: the steepest descent and newton directions.  A larger lambda value favors the steepest descent direction, while a small value favors the newton direction.  If the problem is smooth, and the starting value is good, then a small lambda is justified and will allow the LM algorithm to move rapidly toward the optimum.  If lambda is 0 then the LM algorithm becomes the Gauss-Newton algorithm.  LM is not guaranteed to be a global optimum.  The least squares function typically has many local minima, and where the LM terminates is dependent on the starting point and the steps taken.  A small initial lambda may allow LM to take a large step out of one basin of attraction and into another with a less optimal minimum.  We have sometimes recommended that the initial lambda be modified for problems where performance was a premium, and the starting guess was good.  We debated placing the initial lambda value on the connector pane of 'nonlinear curve fit.vi' as a parameter, but decided against it because of the difficulty in setting it for a given problem.  Unfortunately changing the initial lambda also means changing shipping VIs.  Perhaps we should revisit this?  It may be possible to have an advanced VI that exposes more parameters (initial lambda, upddate/downdate factors, etc.).  

3.  Your point about the vectorization of the code in abx.vi is well taken.  We could do better there, as the work by yourself and Christian demonstrates.  You show a significant improvement in the performance of this VI, but the portion of time of curve-fit that is spent in the abx.vi is some fraction of the total, so the overall speedup of the curve fit is more modest.  As an experiment I replaced the stock abx code with Christian's best case, and reran the test suite using tick count VIs to measure performance.  Stock time was 2696ms, while the new abx code clocked in at 2467ms.  8.5% reduction in execution time.  This is definitely worth pursuing, and so we will look more carefully at this implementation, and adjust accordingly.

-Jim

[Herbert]

Thanks DSPGuy,

for responding to my message, demonstrating that NI takes such issues serious!

---

DSPGuy wrote:

Herbert,

Thanks for looking so closely at the curve fitting functions.  You have raised some important points, so I'd like to reply to them one at a time.
1.  I'm not sure why you are having a problem with the exponential fit VI, but clearly we are not performing as we should.  There is something about your data that is causing a failure or poor performance.  I realize that you have a solution that is working for you now, but it would be helpful to us if you could post your dataset so that we can track down our problem.  Is this possible?

---

I prepared a - hopefully nice - VI and attached it to the first posting of mine. In this VI the data and all the rest is available (check my P.S. )

In addition, I would like to mention that the exponential fit runs fine, if the data are distributed in the interval x = 0..1 instead of x = 0.78 .. 1. This dependence of the fit result on the x-range really stroke me - I could not get any reason for it and thus had to question the suitability of the exponential fit for completely automatic fitting, as planned.

Yes - I found a temporary solution to my problem - but one, for which there is no theoretical derivation available nor any test results about its robustness. So - if you - means the "LV Scientific Computing Group" - finds a way to correct the fitting procedure, I would prefer to resort back to a tested and documented algorithm.

---

2.  The implementation of the Levenberg-Marquardt (LM) algorithm was formulated after looking over many sources,

including Numerical recipes.  ...............

---

In this case I would like to ask NI to give us users some hints, when you deviate from well known literature. This would help me a lot (and I think other advanced LV-users), when trying to optimize code for a specific task. The documentation of Igor for example cites the literature, on which they base their code and its tweaks.

Concerning an advanced LM-VI with more options:

In LV I really like the "politics" of NI, to not password protect very many of the functions. This allowed me for example to modify the LM-function such that my customer can select what parameters of the model should be fitted and which ones of them should be treated as constants (a common feature in regression functions not yet present in NI's version). This is why I am quite happy with the current solution: As long as I am able to modify and complement the existing code, I can do it - although it is quite laborious, as the libraries are password protected.

If I thus may issue a wish, I would prefer you putting that effort into the documentation, giving us some more details about the implementation and the reasons for it.

With best regards

Herbert