Tell me more ×
Cross Validated is a question and answer site for statisticians, data analysts, data miners and data visualization experts. It's 100% free, no registration required.
up vote 2 down vote favorite

I'm trying to simulate this scenario: 10 different algorithms are solving a number of problems. All 10 are run on each problem instance, which means if a particular problem instance is hard, I expect all algorithms to perform quite bad and vice versa.

Now, to simulate this, I created 10 different normal distributions from which I draw random numbers. These numbers represent the algorithms performance for some problem instance; however, since the distributions are independent, I'm not capturing the effect of the problem instance on the drawn numbers. Any idea how I can do this (i.e. correlated the random numbers that are drawn)?

Regards,

share|improve this question
Could this relate to Copula? It is uncorrelated distributions, but with dependent structures. I am not sure whether the question is correct, because statistically independent means uncorrelated, but uncorrelation doesn't mean independent. The question maybe another way around. – Fred Feb 6 '12 at 1:10
I don't think I quite follow you – Jawad Feb 6 '12 at 11:26

3 Answers

up vote 3 down vote

This sounds like a multi-level or mixed model would be useful. You have two sources of uncertainty: the alorithm and the problem. You can write this as

$$t_{ij}=a_{i}+p_{j}+e_{ij}$$

Where a is algorithm p is problem and e is error or interaction between problem and algorithm and t is you target for the $ij$ problem-algorithm pair. So you generate a problem effect, and a algorithm effect from their distributions (which is assigned by you), and an interaction effect. I would recommend the interaction effect if you have "tailored" algorithm designed for specific problems (eg exploit sparsity).

share|improve this answer
Thanks, the model you suggested exactly fits what I'm looking at. While creating the algorithm effect and problem effect can be easily done by drawing random numbers from the corresponding dists., the interaction effect isn't. Would you suggest a way to do it? – Jawad Feb 6 '12 at 11:13
You would also draw it from a distribution. The purpose of the interaction is to allow the algorithm effect depend on the problem, rather than be constant for all problems. If you're not sure what to use, perhaps using an empirical distribution from a few test runs would be useful. – probabilityislogic Feb 6 '12 at 12:28
I might use an empirical dist. Thanks. – Jawad Feb 6 '12 at 13:35
1  
+1. This appears to be the same as another solution proposed slightly earlier. The two replies together give a good answer. I am upvoting this one because it uses a universal language--mathematical notation--developed for communicating such ideas to people rather than a narrow specialized language (R) intended for instructing computers. The R version is one solution out of many possible (and therefore makes a nice illustration) whereas the mathematical version given here is a general solution which is readily translated to any computing platform. – whuber♦ Feb 6 '12 at 15:41
@whuber, all of that is true. – gung Feb 6 '12 at 23:13
up vote 2 down vote

I'm not sure what's "best" here, but a couple of approaches are thinkable. One is to draw a random number representing problem difficulty. (If you wanted, you could have additional values, for example, that index the quality of the algorithm.) Then you sum these values. For instance, in R:

nProbs           = 1000     # the number of problems
nAlgs            =   10     # the number of algorithms
sigma_easiness   =    5     # the SD of the distribution of how easy the problems are

     # algorithms differ in quality:
algorithms        = seq(from=-2, to=2, length.out=nAlgs)        

prob_easiness     = rnorm(nProbs, mean=0, sd=sigma_difficulty)
values            = rep(prob_difficulty, each=nAlgs) + algorithms 
resid_variability = rnorm(nProbs*nAlgs)
performance       = matrix(data=(values+resid_variability), ncol=10, byrow=T)

> mean(abs(cor(performance)))
[1] 0.9636438

More complex versions can also be done (say, with the variability of the algorithms differing, or some algorithms performing better or worse depending on problem difficulty, etc.).

Sidestepping all this, if you just want to generate correlated data from a multivariate normal distribution, the function mvrnorm from the MASS library in R will do that for you.

share|improve this answer
Thanks for the reply, but I'm not quite sure I follow the R algorithm, I'm not familiar with R's syntax... yet. If I understood correctly, you suggest adding a random number to the numbers drawn from the distributions? For example, adding a 5 to the randomly drawn numbers? Best means a lower value since I'm minimizing. – Jawad Feb 5 '12 at 20:05
Not knowing R is unfortunate, since my answer is R intensive, & R is ideal for these kinds of simulations. Several things: minimizing vs. maximizing doesn't matter here; note, I changed the code, e.g., I switched problem_difficulty w/ problem_easiness so that the directionality is the same as algorithms. Here's the gist of my approach: think of a matrix w/ rows=problems & algs=columns, add a different rand # to the elements of each row--each row gets a different #, but every element in a given row gets the same #, that makes rows tend to rise & fall together. – gung Feb 5 '12 at 21:09
For one, you are right, I should learn R fast. Second, thanks for the clarification, it is as I expected it to be. But, I did try that out before, but I think this approach won't work, here's why: To simulate the problem difficulty effect, the numbers should be drawn from the appropriate parts of the distributions, for example, a hard problem means that numbers should be drawn from parts near the upper tail of the distributions (e.g. for an algorithm who's mean performance is 10 and std. dev. is 1, a number like 14 would indicate a bad performance for that algorithm, assuming minimization). – Jawad Feb 5 '12 at 22:23
The opposite holds for easy problems. If a value, like 5, is added to a number, like 7, drawn from the lower tail of the just mentioned distribution, the final result will be 12 which indicates that the problem is of above average difficulty; however, if a number, like 15, is drawn from the lower tail of another dist. (i.e. another algorithm's performance dist.) with mean 30 and std. dev. of 5, and the same 5 is added to it, the result will be 20 which represents a below average difficulty. – Jawad Feb 5 '12 at 22:25
Clearly, the first dist. represents a better algorithm, but in this case we got the opposite outcome. That's why I think that adding a random number will not simulate the proper difficulty. – Jawad Feb 5 '12 at 22:25
show 4 more comments
up vote 0 down vote

Perhaps Multivar will do what you want: http://mypage.iu.edu/~haguinis/mmr/

share|improve this answer
Thanks, I'll look at it :) – Jawad Feb 5 '12 at 20:06

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.