Combining results from (GBM or any other) model based on samples from a very large database

Question

How would you combine results of model performed on random samples of a very large dataset?

I need to model a very large database in R (~75 million rows) that can not be loaded directly into memory. I am still at the planning phase.

My first idea was to divide the dataset in smaller datasets using random sampling without replacement. Then I could run the random forest model on the datasets by batch, and then combine the results. I think this approach would give reasonable results.

I was wondering if it would be possible to do the same approach with the GBM model? I read the documentation and each iteration depends on the previous one (unlike random forest) and thus I don't know how the results could be combined in the end.

Do you know the statistical principles used to merge model results in such a parallel implementation? I am interested in general methods, not only specific to GBM.

Answer 1

This paper follows an approach very similar to the one you suggest, but they stratify the samples. In their case, each model sees a particular part of the geographic space, which lets the different submodels specialize. Figures 6 and 8 show that this partitioning can lead to better results than trying to fit the whole country with a single model.

I haven't read the paper in detail yet, but when I spoke with the first author about it last week, he seemed to indicate that no fancy procedure was needed to combine the results--he just took the average prediction from all the relevant models.

Answer 2

Not quite the answer you are looking for but...

Do you really need to use that much data? How many predictors do you have? If the number of predictors is small, how much of the data is redundant and just filling in the predictor space? Is it all relevant? Are there data points that are not really in the application domain of the model (i.e. 20 year old cases)? Just because you have it doesn't mean you must use it.

I would sample the data based on similarity - come up with a subset of points that are most dissimilar from the other points n the training set.

Finally, why use a tree ensemble method? I love RF but it is perhaps the model that will give you the largest possible footprint (i.e. thousands of very large unpruned trees). Try 100 bagged trees if you want to use a tree ensemble. Heck, boosted C5 trees probably need a much smaller number of iterations that CART-like boosting methods (from what I've seen so far)

You may have no idea going into this process which model will be best or even good enough. Again, this depends on $p$, but start with some high bias models (LDA, logistic regression, naive Bayes) and see what you can get out of them before bringing out the big, complex, computational expensive (or infeasible) tools. Try logistic regression with cubic smoothing splines to approximate any non-linearities.

Answer 3

In the spirit of using summaries to avoid using all that data. May be going in quite a different from your original request. Just a very naive way to get started - this could probably be done on a very large Postgres instance. This is an initial exploration step so it uses crude sums and counts to get some rough insights. you get some power from very efficient sum/count capabilities of a DBMS and use it to do some rough analysis. I am from a database and massively parallel data analysis background so take this as a somewhat of a stat newbies approach, (I do have an MS in Appl Math not used actively till very recently)

So with all those caveats here goes

a) consider naively, the attributes (date, itemsold, price, zipcode) as columns of your table. I am sure you have more but let's focus on these.

b) create a secondary table in the database by adding up all the $ amts for a day's sales by zipcode now you get (date, dailysales, zipcode). Some simple SQL ( select date, zipcode, sum(price) as dailysales from table group by .... ) gets you this table.

A much smaller table with 365 rows per zip code X # of zipcodes in your data.
Use this table for initial explorations and also when you sample you can use this as a reality check.

Depending on how much CPU and memory you give it this step could take minutes or hours. Suggest not trying it on a laptop (I blew my motherboard after a few 100 runs of similar sized problem on a circa 2005 laptop back then :-) )

c) for each zipcode separately do "your favorite regression", (dailysales dependent variable, date independent variable). See the MADlib project http://MADlib.net if you want to do this in-place (MADlib does in-database analytics by embedding C++ math, array and stats libs in Postgres)

d) one plot per zip code, 365 data points (if you have daily data) - look for increasing, decreasing or inconclusive. or just get the correlation coefficients and partition into three buckets +, - and "dontknow".

This now allows you to separate out, via Pareto thinking, the top 20 (or 10 or ..) zip codes with the most increase in sales by % and by $amt. Similar for most decrease ...

You can now separately strategize how to drill down for the increasing, inconclusive and decreasing buckets of zipcodes, in a divide and conquer fashion.

MADlib also allows you to run in-database R routines via PL/R but for Linear/Logistic Regression and SVM the embedded C++ is some 100 times faster. C4.5 is also available.

If your data size gets too big for Postgres (dont think so, but just in case) then there's the Greenplum MPP database. For 75 million rows you should be able to do this on a X-Large EC2 instance or similar with Postgres.

If you don't want to do this in a dbms there are ways to write some Python code and iterate over the disk file or database table pulling a few thousand or hundred thousand rows at a time into memory. If you do put it into Postgres there's ways to get small random samples of the rows.

Hope this makes some sense or at least is not complete nonsense in your context :-)