Dev

Download

dev@dynare.org

June 2009

5 participants
21 discussions

Re: [DynareDev] Kalman Filter
by Michel Juillard 01 Jun '09

01 Jun '09

This is indeed disapointing. Could you profile the code for your experiments 3) and 4) in order to try to understand where is the C++ filter at a disadvantage. You probably need to write a main program in C++ setting up the matrices in order to profile the C++ code. If we can't write a C++ filter than runs faster than Matlab, there is no point in trying to write a C++ estimation DLL. All the best, Michel G. Perendia wrote: > Dear Michel > > Results of run lapse time using etime(clock,t) are rather surprising and > very disappointing (I had to repeat some in a sheer disbelief) - far the > best is Matlab Dynare kalman_filter.m (even after applying some refactoring > of the kalman.cpp's deep inner loop, not applied to all DLL tests yet)!!!. > > Timing tests on Pentium 2.4 GHz > > 1)calling Kalman_filters.m in the 10000 loop, itself calling the optimised > version of DLL with preparation of H and Z matrices in each loop: > total_dll_time = 202.7320 > > 2)calling core optimised version of Kalman_filter_dll in the 10000 loop > after (i.e., loop without) preparation of H&Z matrices in kalman_filters.m: > core_dll_time= = 1st run: 172.5890 2nd run: 195.0500 at ~93% of CPU time > > 3)calling the Kalman_filter_loop.dll with its own inner 10000 loop from > kalman_filters.m (including the one-off call time) > innrloop_dll_time = 1st run 197.8640 2nd run: 192.5970 > 3rd run (after some refactoring of the kalman.cpp filter deep inner loop > not yet used in other DLL tests): 184.9760 > > 4)calling Dynare SVN kalman_filter.m in 10000 loop > matlabKF_time = 1st run: 48.9600 2nd run: 48.4600 > > 5) for a comparison and sanity check: calling Kalman_filters running the > debug version of DLL in the 10000 loop > dbug total_dll_time=etime(clock, t) = 642.4140 running at ~93% of CPU time > > It is possible that using proper, optimised lapack and BLAS may give a > better performance for C++. (NOTE: the DLLs used Matlab lapack and blas > libraries.) > > Shall I nevertheless continue with the C++ version of DsgeLikelihood as > planned or try to revise the performance tests first? > > Best regards > > George > artilogica(a)btconnect.com > > ----- Original Message ----- > From: "Michel Juillard" <michel.juillard(a)ens.fr> > To: "G. Perendia" <george(a)perendia.orangehome.co.uk> > Sent: Monday, June 01, 2009 10:32 AM > Subject: Re: [DynareDev] Kalman Filter > > > >> Thanks George, now it is clear. I'm also interested by a timing >> comparison. Could you time >> a) 10'000 calls to the Matlab filter routine >> b) 10'000 calls to the C++ filter routine >> c) add the 10'000 loop inside the DLL and time one call to this modified >> function. >> >> I guess after that we should pass to the coding in C++ of DsgeLikelihood.m >> >> All the best, >> >> Michel >> >> >> G. Perendia wrote: >> >>> Dear Michel >>> >>> No, I do not think there is additional problem (other than with Diffuse >>> Likelihood*.m files when if used) or that correction was not sufficient. >>> >>> Over the weekend I was just trying full 1st stage estimation with a >>> > model we > >>> use for Part Info, with and without the corrections, which just shows >>> > the > >>> scale of the effect of the log likelihood calculation error (now >>> > properly > >>> corrected for the SVN likelihood files) . As you can see in the .rtf >>> > file, > >>> in the few of the tests with SVN version (using >>> > /likelihood/kalman.filter.m) > >>> I used your new code too, but for comparing results in older versions of >>> Dynare- v4.0.2 and 4.0.3 - (using Diffuse Likelihood1.m), I used my >>> > quick > >>> fix applied to the 4.02 DiffuseLikelihod*.m that I also enclosed. >>> >>> Also, some additional tests I did over the weekend show that, after the >>> correction, Dynare now reports estimates more comparable to the new Part >>> Info method than before the correction, also proving that the correction >>> works ! >>> >>> As you suggested, I run a test of your new correction that can be >>> > compared > >>> to C++ and, for the test model I used, F converges at t=3 (start is 41), >>> > and > >>> your new kalman_filter.m code gives total >>> LIK=1640935.5855619563 >>> which is virtually the same as C++ and the quick fix for Diffuse >>> > Likelihood > >>> I tested last week (requoted from below): >>> >>> >>> >>>>>>> the reported likelihood for presample=40 from (quick >>>>>>> >>>>>>> >>> fix) Matlab KF >>> >>> >>>>>>> 1640935.5855267849 >>>>>>> which is nearly the same as that from C++ KF below: >>>>>>> 1640935.5854489324 >>>>>>> >>>>>>> >>> Let me know if you want me to run more tests or work on correcting any >>> > other > >>> Dynare Matlab code! >>> >>> Best regards >>> >>> George >>> >>> ----- Original Message ----- >>> From: "Michel Juillard" <michel.juillard(a)ens.fr> >>> To: "G. Perendia" <george(a)perendia.orangehome.co.uk> >>> Sent: Monday, June 01, 2009 9:08 AM >>> Subject: Re: [DynareDev] Kalman Filter >>> >>> >>> >>> >>>> Dear George, >>>> >>>> I'm a bit confused. We agreed that all the versions of Kalman >>>> likelihood, both in ./matlab and in ./matlab/kalman/likelihood were >>>> wrong when presample was larger than the period where the filter >>>> > reaches > >>>> its stationary state. So I don't see the point in still using this code >>>> for testing. >>>> >>>> the code in matlab/kalman/likelihood was corrected last Wednesday on >>>> > SVN > >>>> r2007 >>>> >>>> Do you have reasons to believe that the correction wasn't sufficient? >>>> > Or > >>>> is there another source of discrepancy between the Matlab code and the >>>> C++ code? >>>> Before comparing results of entire estimation procedures, we have to >>>> make sure that all the outputs from the Matlab and C++ functions with >>>> the same inputs are close enough. >>>> >>>> Note that we still have to correct DsgeLikelihood_hh.m that calls the >>>> obsolete DiffuseLikelihood*.m routines instead of the ones in >>>> kalman/likelihood >>>> >>>> Then we should just remove the DiffuseLikelihood*.m functions >>>> >>>> >>>> Best >>>> >>>> Michel >>>> >>>> >>>> G. Perendia wrote: >>>> >>>> >>>>> Dear Michel >>>>> >>>>> Problem and discrepancies with log likelihood calculation with >>>>> >>>>> >>> presampling >>> >>> >>>>> (start>1) is something I have been encountering for some time (i.e. >>>>> > few > >>>>> weeks) already , whilst doing some tests for the new partial >>>>> > information > >>>>> kalman estimation, but, expecting that the problem is in the new >>>>> > Partial > >>>>> info code, I did not get to the bottom of the cause until I >>>>> > encountered > >>>>> discrepancy between the C++ KF (modified to handle presampling >>>>> > properly) > >>> and >>> >>> >>>>> the Dynare KF too. It was that second discrepancy that led me to >>>>> > analyse > >>>>> Dynare KF handling of presampling and to find the problem there. >>>>> >>>>> I did some more preliminary tests yesterday with the older and the >>>>> >>>>> >>> latest >>> >>> >>>>> SVN versions of Dynare, without and with the correction (including >>>>> correction using the fix based around the min() function I initially >>>>> suggested and now applied as a quick fix to the older >>>>> >>>>> >>> DiffuseLikelihood1.m) >>> >>> >>>>> and the estimation results with and without correction are >>>>> > significantly > >>>>> different as can be seen from the enclosed rtf document which uses two >>>>> >>>>> >>> very >>> >>> >>>>> similar models, (i.e. one with gamma>0 the other with gamma=0), to >>>>> >>>>> >>> compare >>> >>> >>>>> the results (also very similar to the one I sent to Stephane). >>>>> >>>>> Although the initial calculations of log-likelihood ("Initial value of >>>>> >>>>> >>> the >>> >>> >>>>> log posterior (or likelihood): ") are same, (i.e. when reste is 0 or >>>>> >>>>> >>> very >>> >>> >>>>> small), it appears that the differences builds up during the >>>>> > estimation > >>> as >>> >>> >>>>> the kalman filter cov matrix start to converges earlier and earlier, >>>>> eventually before the given presample start is reached, as the later >>>>> > in > >>> the >>> >>> >>>>> ML and estimation error minimisation we are (and probably throughout >>>>> > the > >>>>> MCMC estimation process), when the parameters get close to the mode >>>>> (especially if the parameter priors were taken from previously >>>>> > estimated > >>>>> posteriors as is the case with the test models I used). >>>>> >>>>> (I did not yet run MCMC due to estimation failing with the chol() >>>>> non-positive definite error so I would need to change starting >>>>> > values.) > >>>>> Let me know if you would like me to develop and perform more >>>>> > structured > >>>>> tests on a large range of models. >>>>> >>>>> >>>>> Best regards >>>>> >>>>> George >>>>> >>>>> ----- Original Message ----- >>>>> From: "Michel Juillard" <michel.juillard(a)ens.fr> >>>>> To: "List for Dynare developers" <dev(a)dynare.org> >>>>> Cc: "G. Perendia" <george(a)perendia.orangehome.co.uk> >>>>> Sent: Wednesday, May 27, 2009 12:16 PM >>>>> Subject: Re: [DynareDev] Kalman Filter >>>>> >>>>> >>>>> >>>>> >>>>> >>>>>> In fact the discrepancy found by George occurs only for start ~= 1 >>>>>> So it is clearly related to the handling of the constants. >>>>>> >>>>>> Best >>>>>> >>>>>> Michel >>>>>> >>>>>> >>>>>> Stéphane Adjemian wrote: >>>>>> >>>>>> >>>>>> >>>>>>> George, Can you share your example. In my experience (with medium >>>>>>> scaled models) it takes much more iterations to get to the steady >>>>>>> state kalman filter... >>>>>>> >>>>>>> I didn't look at the cc codes, but one possible source of >>>>>>> > discrepancy > >>>>>>> between matlab and cc may be the steady state KF criterion. I test >>>>>>> > for > >>>>>>> the stationarity of KF considering the changes in the biggest >>>>>>> > elements > >>>>>>> of the Kalman Gain matrix, not the changes in the determinant of the >>>>>>> forecast errors covariance matrix... >>>>>>> >>>>>>> Best, >>>>>>> Stéphane. >>>>>>> >>>>>>> >>>>>>> 2009/5/27 G. Perendia <george(a)perendia.orangehome.co.uk >>>>>>> <mailto:george@perendia.orangehome.co.uk>> >>>>>>> >>>>>>> >>>>>>> 1. In my experience, the filter cov. determinants dF becomes >>>>>>> stationary after several steps (5-10), e.g. 7 >>>>>>> and number of periods the filter is stationary is >>>>>>> reste=smpl-7 >>>>>>> whilst, if start =41 (presample=40) than reste is then larger >>>>>>> > than > >>>>>>> smpl -start+1=smpl-40. >>>>>>> >>>>>>> 2. it is not problematic to add all the determinants at once in >>>>>>> the last period of the stationary filter >>>>>>> as long as we subtract from the total sum >>>>>>> >>>>>>> start-1-(smpl-reste) = 41 -1 -(smpl-smpl+7)=33 >>>>>>> determinants, or, add only >>>>>>> min(reste,(smpl-start+1)) >>>>>>> Best regards >>>>>>> >>>>>>> George >>>>>>> >>>>>>> ----- Original Message ----- >>>>>>> *From:* Stéphane Adjemian >>>>>>> > <mailto:stephane.adjemian@gmail.com> > >>>>>>> *To:* List for Dynare developers <mailto:dev@dynare.org> >>>>>>> *Cc:* G. Perendia <mailto:george@perendia.orangehome.co.uk> >>>>>>> *Sent:* Wednesday, May 27, 2009 11:04 AM >>>>>>> *Subject:* Re: [DynareDev] Kalman Filter >>>>>>> >>>>>>> Hi all, >>>>>>> >>>>>>> I agree, the matlab code is very unclear (even if I had fun >>>>>>> writting it this way ;-) and prone to errors if one uses the >>>>>>> vector lik (Marco is using it). I would rather prefer to add >>>>>>> the constants outside of the loop with a (sub)vector >>>>>>> operation, this should be more efficient. I will do it today >>>>>>> or tomorrow. >>>>>>> >>>>>>> Best, >>>>>>> Stéphane. >>>>>>> >>>>>>> 2009/5/27 Michel Juillard <michel.juillard(a)ens.fr >>>>>>> <mailto:michel.juillard@ens.fr>> >>>>>>> >>>>>>> On closer inspection, I don't think that the expression >>>>>>> pointed by George in kalman_filter.m is wrong: >>>>>>> >>>>>>> 1. reste = smpl-t or the number of periods during which >>>>>>> the filter is stationary. This shouldn't be larger than >>>>>>> T-start+1 >>>>>>> >>>>>>> 2. it is problematic (see below) but not wrong to add >>>>>>> > all > >>>>>>> the determinants at once in the last period of the >>>>>>> stationary filter >>>>>>> >>>>>>> 3. I don't think this explains the difference with the >>>>>>> > C++ > >>>>>>> version of the filter and we still have to look for it. >>>>>>> >>>>>>> 4. it remains that the current code is very unclear and >>>>>>> that if LIK is correct the vector lik doesn't have the >>>>>>> correct constants on each elements. >>>>>>> >>>>>>> 5. I would like to simplify the code and add the correct >>>>>>> constant to each element of the lik vector. It would be >>>>>>> > a > >>>>>>> little bit less efficient in Matlab than the current >>>>>>> > code, > >>>>>>> but I doubt it would be noticeable. >>>>>>> Stephane, what do you think? >>>>>>> >>>>>>> >>>>>>> Best >>>>>>> >>>>>>> Michel >>>>>>> >>>>>>> G. Perendia wrote: >>>>>>> >>>>>>> Dear Michel >>>>>>> >>>>>>> I think I found an error in Dynare Matlab >>>>>>> kalman_filter. suite of utilities >>>>>>> which affects the likelihood LIK results with >>>>>>> > start>1 > >>>>>>> (i.e. presampling>0): >>>>>>> >>>>>>> the calculation speed-up construct which relies on >>>>>>> converged covariance >>>>>>> matrix >>>>>>> >>>>>>> lik(t) = lik(t) + reste*log(dF); >>>>>>> >>>>>>> adds reste * log(dF) to the last-1 (i.e. the smpl) >>>>>>> member of lik >>>>>>> (the last, the lik(smpl+1) one contains >>>>>>> >>>>>>> >>>>>>> >>>>> smpl*pp*log(2*pi)) >>>>> >>>>> >>>>> >>>>>>> but reste is usually larger than T-start+1 so that >>>>>>> >>>>>>> LIK = >>>>>>> >>>>>>> >>>>>>> >>>>> .5*(sum(lik(start:end))-(start-1)*lik(smpl+1)/smpl) >>>>> >>>>> >>>>> >>>>>>> has much more log(dF)s added than required since >>>>>>> > they > >>>>>>> are all concentrated >>>>>>> in the last-1 (the T) member >>>>>>> >>>>>>> For example, if I change the above construct to >>>>>>> lik(t) = lik(t) + min(reste,(smpl-start+1))*log(dF); >>>>>>> >>>>>>> the reported likelihood for presample=40 from Matlab >>>>>>> >>>>>>> >>> KF >>> >>> >>>>> is >>>>> >>>>> >>>>> >>>>>>> 1640935.5855267849 >>>>>>> which is nearly the same as that from C++ KF below: >>>>>>> 1640935.5854489324 >>>>>>> >>>>>>> Shall I make changes to kalman/likelihood/ KFs and >>>>>>> upload the .m files? >>>>>>> This problem affects also the older versions of >>>>>>> DiffuseLikelihood**.m too. >>>>>>> >>>>>>> Best regards >>>>>>> >>>>>>> George >>>>>>> artilogica(a)btconnect.com >>>>>>> >>>>>>> >>>>>>> >>>>> <mailto:artilogica@btconnect.com> >>>>> >>>>> >>>>> >>>>>>> ----- Original Message ----- From: "Michel Juillard" >>>>>>> <michel.juillard(a)ens.fr >>>>>>> >>>>>>> >>> <mailto:michel.juillard@ens.fr>> >>> >>> >>>>>>> To: "G. Perendia" <george(a)perendia.orangehome.co.uk >>>>>>> <mailto:george@perendia.orangehome.co.uk>> >>>>>>> Sent: Tuesday, May 26, 2009 10:32 AM >>>>>>> Subject: Re: Kalman Filter+PS >>>>>>> >>>>>>> >>>>>>> >>>>>>> >>>>>>> Hi George, >>>>>>> >>>>>>> >>>>>>> >>>>>>> >>>>>>> Re 1) below: >>>>>>> I modified C++ KF so that it reports >>>>>>> log-likelihood for given >>>>>>> start/preampling in same/similar manner as >>>>>>> > the > >>>>>>> Matlab KFs do and I am >>>>>>> getting approximately close results, e.g. >>>>>>> >>>>>>> ll= -1640935.5854489324 for C++ and >>>>>>> (-) 1640482.4179242959 for Matlab KF (for >>>>>>> start=41, i.e. >>>>>>> >>>>>>> >>>>>>> presample=40). >>>>>>> >>>>>>> >>>>>>> whilst they appear same for presample=0 >>>>>>> (e.g.2.5906e+006), i.e. >>>>>>> -2590556.989730841 vs >>>>>>> 2590556.989778722 >>>>>>> >>>>>>> Are those results acceptably close or should >>>>>>> > I > >>>>>>> investigate further where >>>>>>> >>>>>>> >>>>>>> the >>>>>>> >>>>>>> >>>>>>> above difference may come form? >>>>>>> >>>>>>> >>>>>>> >>>>>>> >>>>>>> This indicates a problem . The difference should >>>>>>> be the same with and >>>>>>> without presample. It may come from the >>>>>>> computation of the likelihood >>>>>>> constant. This is done in a very obscure manner >>>>>>> > in > >>>>>>> Dynare Matlab. >>>>>>> >>>>>>> >>>>>>> >>>>>>> >>>>>>> >>>>>>> >>>>>>> >>>>>>> >>>>>>> >>>>>>> _______________________________________________ >>>>>>> Dev mailing list >>>>>>> Dev(a)dynare.org <mailto:Dev@dynare.org> >>>>>>> http://www.dynare.org/cgi-bin/mailman/listinfo/dev >>>>>>> >>>>>>> >>>>>>> >>>>>>> >>>>>>> -- >>>>>>> Stéphane Adjemian >>>>>>> CEPREMAP & Université du Maine >>>>>>> >>>>>>> Tel: (33)1-43-13-62-39 >>>>>>> >>>>>>> >>>>>>> >>>>>>> > ------------------------------------------------------------------------ > >>>>>>> _______________________________________________ >>>>>>> Dev mailing list >>>>>>> Dev(a)dynare.org <mailto:Dev@dynare.org> >>>>>>> http://www.dynare.org/cgi-bin/mailman/listinfo/dev >>>>>>> >>>>>>> >>>>>>> _______________________________________________ >>>>>>> Dev mailing list >>>>>>> Dev(a)dynare.org <mailto:Dev@dynare.org> >>>>>>> http://www.dynare.org/cgi-bin/mailman/listinfo/dev >>>>>>> >>>>>>> >>>>>>> >>>>>>> >>>>>>> -- >>>>>>> Stéphane Adjemian >>>>>>> CEPREMAP & Université du Maine >>>>>>> >>>>>>> Tel: (33)1-43-13-62-39 >>>>>>> >>>>>>> >>>>> ----------------------------------------------------------------------- >>>>> > - > >>>>>>> _______________________________________________ >>>>>>> Dev mailing list >>>>>>> Dev(a)dynare.org >>>>>>> http://www.dynare.org/cgi-bin/mailman/listinfo/dev >>>>>>> >>>>>>> >>>>>>> >>>>>>> >>>>>> _______________________________________________ >>>>>> Dev mailing list >>>>>> Dev(a)dynare.org >>>>>> http://www.dynare.org/cgi-bin/mailman/listinfo/dev >>>>>> >>>>>> >>>>>> >>>>>> >>> >>> >>> >> > > > >

1 0