SERVING THE QUANTITATIVE FINANCE COMMUNITY

 
User avatar
quartz
Topic Author
Posts: 424
Joined: June 28th, 2005, 12:33 pm

(incremental/parallel) statistics

February 1st, 2012, 9:29 pm

Dear QFCLers, I open a whole new thread for discussing statistics, as there's enough to decide here already.[edit: sorry I didn't notice the other one in time, can we merge them and delete this thread altogether?]We have different challenges:- providing numerically good estimators- get them running incrementally? (please especially comment on this; a few algorithms require two passes, while in some cases plain processing of the whole sample set is already fine)- perform estimates in a parallel setting- get everything fast- new algos should ideally also provide a weighted form- [integrate with boost accumulators]- [stay SIMD & GPU friendly]- [beware of QMC]- do we want to also add algos for trading? e.g. moving averages (in boost) & other windowed statistics, EWMA and so on... (I once saw of a OS lib for this but was taken offline). I think it would be great to expand the scope beyond just pricing&risk... but it might complicate the design. What accumulators would you like to see?Outrun has nice ones, and I got a few ideas for others.Parallel accumulators; here there are many different approaches leading to different designs:- ex post merging of n independent estimates (low accuracy, might also lead to bias) - easiest to implement- ex post merging of accumulator working data, and final estimate on such - inherently parallel algorithms (such as enhanced GK)- collection of all samples from different workers, and subsequent application of standard quantile algorithms (possibly with parallel implementation)Clearly approaches with most potential (for speed and accuracy) are also the more involved.I find it difficult to choose a priori an approach (and thus corresponding design) before having done a through comparison.Ideally then it would be great to devise a framework flexible enough to cover all options.Is any of you familiar with the accumulator framework in Boost? I wonder wether we should extend it or write independent code.Documentation is not so clear about numerical accuracy, I shall write some tests, e.g. for the rolling sum...For the case of quantile and conditional expectations, boost offers:- global ICDF approximation via P^2 algorithm- tail quantile (what's the complexity?)- tail conditional expectation- peak over threshold (from extreme value theory)- peak over threshold conditional expectation(what are tail_variate & c?)There are weighted versions already, but parallelization might not be immediate.Also the quality could be improved, and some accuracy tests would be nice.Most importantly, the benchmark case of (accurate) methods working on the whole set are missing.
Last edited by quartz on January 31st, 2012, 11:00 pm, edited 1 time in total.
 
User avatar
quartz
Topic Author
Posts: 424
Joined: June 28th, 2005, 12:33 pm

(incremental/parallel) statistics

February 8th, 2012, 12:24 pm

Hey Outrun,good, so for a first start I would suggest:- "parallel" reduction of two min/max/mean etc accumulator states into one- "parallel" reduction of two P^2 quantile accumulator states - "parallel" reduction of two tail accumulator states - global framework for using the above accumulator pair reductions to reduce more (either in a sequential or tree-like fashion)- include a collector of all samples from all threads into a single sample set, for offline and serial statistics, as a benchmark for quality and unit testing (or the other way round: generate sample sequentially, split them for many threads, accumulate in parallel, reduce and compare to sequential statistics of the whole original sample; what approach do you prefer?)- performance testing- add other quantile algos, e.g. those from the papers you posted, and maybe the extended GK algorithm too- CUDA versions of what exactly? and in what context? what is the framework? some reductions are implemented in thrust, but is that the right level for orchestrating it all? how to handle multiGPU or even just multicore+GPU? - and what about OpenCL? why prefer something proprietary and less stable other than for performance and simil-C++?Once this basic stuff is ready we can think of more complicated algorithms.Who volunteers where? I'd like the quantile stuff...For algo trading remember that there's now the circular_buffer<T, Alloc> container available. But here maybe someone from the field should comment and maybe post a wishlist :-) We do have some nice algorithms, but still unsure about the extent to which opensource'm.As for your accumulators, are they easy to parallelize? Both usage options seem interesting, but I'll write you more about this topic.
ABOUT WILMOTT

PW by JB

Wilmott.com has been "Serving the Quantitative Finance Community" since 2001. Continued...


Twitter LinkedIn Instagram

JOBS BOARD

JOBS BOARD

Looking for a quant job, risk, algo trading,...? Browse jobs here...


GZIP: On