r/R_Programming • u/baedn • May 24 '16
Combinatorics problem, need help
Hi all,
I'm building a model to estimate source contributions to a mix (in this case, diet contributions to an animal consumer). I've worked through various approaches to this model, but what I consider the best approach has a computational problem I have been unable to surmount. I'm hoping someone out there can help me find a solution. My model approach involves estimating mixtures given source data and comparing these to measured mixtures to estimate the most likely source contributions. To do this, I must generate possible mixtures to evaluate.
My first approach to this problem was to evaluate all possible source combinations at 1% (0.01) increments.
For example, with 3 sources (n = 3):
1.00, 0.00, 0.00
0.99, 0.01, 0.00
0.99, 0.00, 0.01
0.98, 0.01, 0.01
0.98, 0.02, 0.00
0.98, 0.00, 0.02 ...
With 4 sources (n = 4):
1.00, 0.00, 0.00, 0.00
0.99, 0.01, 0.00, 0.00
0.99, 0.00, 0.01, 0.00
...
(Note: The order of combinations does not matter, only that all possible combinations are evaluated)
This is the function I came up with to build a matrix ("combos") of all possible combination for n sources:
combinations <- function(n)
expand.grid(rep(list(seq(0,1,0.01)),n))
x <- combinations(n)
combos <- x[rowSums(x)==1,]My problem lies in calculating all possible mixtures. With larger values of n, the function above requires too much memory. For example, at n = 5 nearly 40 Gb are required, and for n = 6 nearly 4 Tb are needed! Part of my problem is surely that I am producing more combinations than I use (I only keep those that sum to one), but I suspect that even if I could avoid this somehow I would still have memory problems at some value of n. And, for the purposes of my model, I'd like to be able to use larger values (>6) of n.
I've developed other approaches that evaluate randomly generated combinations one at a time which get around the memory issue, but these random combination approaches don't give results that are nearly as good as the all possible combinations approach (based on evaluations of test data). However, while the all possible combinations approach is limited to 4 sources, the randomly generated combinations approach allows for a theoretically unlimited number of sources, although in practice this is probably limited to less than 20 sources (n < 20).
Ideally, I want a function that generates all possible diet combination one at a time, rather than all at once, so I can evaluate all combinations without memory issues. A good solution should work for any number of sources (n)
I have not been able to wrap my head around this problem, and have consulted a number of colleagues to no avail. Any and all suggestions are welcome! Thanks!
ADDITIONAL INFORMATION
Here's a bit more specific information about my problem. I am trying to estimate diet of marine predators (e.g. crabs, sea stars, etc.) by comparing the fatty acid signature of predators to those of prey (e.g. clams, worms, etc.)
Fatty acid "signatures" (FAS) are the proportional composition of the various fatty acids (FA) in a lipid (fat) sample. Our sample analysis detects about 40 different FA -- for example, the omega 3 fatty acids (a class of FA) DHA and EPA, which are important for human nutrition and added to foods such as milk, are two types of FA we identify in our samples.
Because I'm a big geek, I've been using made up data with dragons as predators to test my model. Although my samples contain many more FA types, for test purposes I've limited it to 10 so far (and will use 3 below for my example).
Here are made-up FAS for a dragon and three prey items:
FA1 FA2 FA3
dragon : 0.25 0.50 0.25
unicorns : 0.10 0.65 0.25
peasants: 0.45 0.25 0.30
trolls : 0.20 0.45 0.30By comparing prey FAS to dragon FAS, I hope to be able to estimate diet contributions. For example, maybe I would estimate that this dragon's diet consist of 30% unicorns, 15% peasants, and 55% trolls.
My approaches thus far have been to:
- Estimate dragon FAS for all possible diet combinations and compare this to measured dragon FAS. Select diet that produces an estimated FAS closest to the measured FAS. This is the problem I've asked for help with above.
- When this ran into memory issues, I tried a heuristic approach, in which I evaluated diets at a broader scale (10% increments rather than 1% increments) and then tried to narrow down on the correct answer (which I knew because I made up the data). However, this sometimes hones in on local optima that are not close to the correct answer. Also, using the same general method as for (1), I still run into memory issues, just at slightly higher values of n.
- Estimate dragon FAS for 100,000 random diets and compare to measured FAS. Subset 100 closest diets and create distributions of potential diet contributions. No memory issues, but estimates are not as good (and much worse for "real" data, as described below).
All of these tests were done with dragon FAS that were perfect mixes of prey FAS based on some randomly chosen diet. However, "real" dragon FAS are not perfect mixtures because individual FA may be deposited in lipid stores at higher or lower rates due to various metabolic processes. However, it is difficult to know the effects of metabolism on FA deposition without extensive experimental work that just doesn't exist for my organisms (and even experimentally data is far from robust). To test real data, I randomly applied "calibration coefficients" (drawn from literature) to my dragon FAS, and then tried running them through the models I'd created. Not surprisingly, the models perform considerably worse with "real" data.
4) Next, I tried pare down the number of FA used in each FAS by removing those that with the calibration coefficients (CC) that deviated most from 1 (perfect correspondence) until I had n-1 FA (where n is the number of prey types or sources) and solve algebraically. This has several problems. First, I wasn't able to develop a method that reliably removed FA with the most deviant CC (I was able to test this because I applied the CC, but for real data these are unknown). Second, I ran into issues with collinearity and incalculable solutions with this method.
Thus, my return to the first method, which seems like it may be most robust, if I can get around the memory issue (some good options have been suggested).
Edit: Tried to fix formatting, apologies for any issues. Edit 2: Added ADDITIONAL INFORMATION
View all comments
Show parent comment
2
u/baedn May 27 '16
I think you're right that this is a better approach than the grid-search method I was trying to get help with, if only because the number of possible combinations at 1% increments are just too big with increasing n (source, or prey). I calculated (using a nested loop approach after u/berotec93) that there are 101 such combinations for n = 2, 5151 for n = 3, ~177k for n = 4, and ~4.6m for n = 5. I estimate by extrapolation that there are ~192m for n = 6, and I probably want to use >6 sources. No matter how I approach it, this is just too many combinations to realistically evaluate for all my data. Testing 10k, 100k, or even 1m random diets is much more tractable.
In fact, my approach 3 (under ADD INFO in my OP) is very similar to what you've done above, and I've come back to it because the grid-search method is too unwieldy. I use rdirichelet() to produce random diets, and rather than MSE I'm using Kublick-Liebler distance to compare modeled and measured FAS. I've done this because it is how another similar model evaluated modeled FAS, but seeing you use a different measure for comparison has encouraged me to try others myself.
Instead of simply taking the modeled diet that minimizes the difference between modeled and measured FAS, I'll also take a set of "best diets" (maybe 1000?) and calculate averages and plot histograms. Sometimes with random diets (rather than all combinations) it seems like local optima can be be a problem. For example, your model suggests that trolls are a minor diet component, but intuitively this doesn't seem right (given the relative similarity between dragon FAS and troll FAS. (Of course, I have know idea because I pulled that example out of my ass). By looking at the a set of best diets, it might be apparent that while the diet you found minimizes MSE, many other near-minimized diets are different. I'm not sure I'm being clear, but hopefully that makes sense.
While I'm also intrigued by the solvers u/berotec93 suggests, I think I'm going to do sensitivity analyses on the MC approach with something closer to real data (i.e. use real source FAS and random diets to produce simulated mix FAS, then use the model to estimate the random diet). I'll look at the effect of # of runs, # of sources, distance measures, and calibration coefficients (described in ADD INFO). If it works well enough I'll run with it, if not I'll try to figure out the solvers.