5 ms·

I don't know how else to put it, but the technique suggested in this paper is irreparably incorrect in the setting that it recommends. Attempting to fix a linea

I don't know how else to put it, but the technique suggested in this paper is irreparably incorrect in the setting that it recommends. Attempting to fix a linear least squares fit by removing points with high residuals does not work. Please don't do that: they won't necessarily be the outliers in the dataset and your model will converge to the wrong thing. Statistics is hard. Like, really really hard. Stuff goes wrong all the time. Please leave it to the experts. If you're going to do this, please look up the methods behind (for example) robust least squares, outlier detection, L_1 regression, etc. The right way to do this is to start with a small dataset that is with very high probability free of outliers, and slowly grow it by never adding points which have large residuals. (If you've done 3D scan registration and image alignment, this is what RANSAC does.) The principle is, intuitively, that once an out-of-distribution point gets into your linear model, the model is poisoned forever. You can't trust the model to tell you that the bad points are the outliers. The way this paper does is is irreparably broken, sorry :/

reubenmorais 7y ago
For the specific problem of benchmarking small code snippets, how do you create the initial small dataset?
- cscheid 7y ago
  Thank you for pointing out some bad phrasing on my part. When I said "small dataset", I should have said "small subset of all collected points that are initially fed to the model". The issue isn't that you have to collect the data little by little. The issue is that, once you've given a linear model an input that is outside the distribution which you're hoping to model, nothing about the model can be trusted. So you collect all the data points, but you don't give them all to the model at once. (I'm describing the RANSAC method here now) You start with a large number of "candidate models" that are all fit with a small number of input points, and then test which of the candidate models predict well the points you have not yet given the model. Then you feed the best of these candidate models only the points which it predicts well, and create a more refined, still outlier-free model. This can be proven to work in the presence of a small number of out-of-distribution points.
  - derefr 7y ago
    Very interesting. It sounds to me like this approach exists outside any kind of Bayesian learning framework; i.e. an individual Bayesian agent couldn’t be expected to converge to a correct model here. Is that true? I would hazard that the RANSAC method sounds a lot like what you’d get out of a larger hybrid model, where e.g. many Bayesian agents with different priors are bred under a genetic algorithm after being ranked by their predictive power. (Like humans surviving to reproduce and pass down models to their children!)
    - cscheid 7y ago
      As far as i understand it the RANSAC arguments are very much not Bayesian (they're all about "if you repeat this an infinite number of times under an infinite number of new samples, then...", which is almost caricaturely frequentist). Still, you just gave me reason to mention one of my favorite "no, that won't work either" paper :) on how Bayes will not save you in the presence of model misspecification. Instead of butchering it any further, I'll just point you to this piece explaining the work, written by the author of the paper himself: http://bactra.org/weblog/601.html http://bactra.org/weblog/601.html
colmmacc 7y ago
There's another reason too; there are strong reasons why the timing of successive code executions should not be linear. Typically the first call to a function will incur the cost of fetching data into a cache. At minimum the basic blocks for the function will be loaded through the l1/l2/l3 pipelines. 2, 3, 4 function calls in a row will benefit from that caching, but also help train the speculative execution engine. At some point that speculation may radically alter performance. Later, with a sufficient number of runs, the timing will also suffer from preemption, context-switches, or other interruptions that can invalidate both the cache and the speculative execution engine. The idea that there is a fixed performance time for a function is naive on modern hardware.
- cscheid 7y ago
  You make a good point I hadn't considered. In that case, not even robust least squares will save you, because the samples are not independent of one another. You'd have to start looking into explicit time-dependent methods and yikes, I have no idea of what the literature says about time dependence and outliers. I wouldn't be surprised if it's "here be dragons" territory.
  - colmmacc 7y ago
    Speculative execution optimizations, e.g. branch prediction, are even data dependent. It's a very complex measurement space!
  - gdxhyrd 7y ago
    You are speaking as a stats person. :) While there are dozens of things that can go south in benchmarking, how to solve them is not about applying advanced stats, but about understanding and eliminating the sources of noise. Most benchmarks in CS can be done quite easily as long as one understands all the technology stack.
    - cscheid 7y ago
      I'm not a stats person! But I have been burned in real projects by doing the wrong thing. I just have learned --- the hard way --- to honestly appreciate it.
gdxhyrd 7y ago
> Please don't do that: they won't necessarily be the outliers in the dataset and your model will converge to the wrong thing. They are the outliers. These experiments are typically measuring something that is effectively constant with almost zero noise, rather than some complex physical phenomena. If you don't get an almost perfect fit, there is something going on that invalidates what you are doing (e.g. cache effects, clock effects, etc.). In fact, if there are any outliers, I would not trust the benchmark at all. So removing them seems like trying to fix a bad benchmark with statistics. > Statistics is hard. Like, really really hard. Stuff goes wrong all the time. Please leave it to the experts. That is unnecessary gatekeeping. Benchmarking in CS is hard not because the maths/stats that are needed are hard, but because setting up the right experiment is hard and most people don't know all the pitfalls. Therefore, if anything, you should leave benchmarks to CS/SE experts, rather than a statistician!

reubenmorais 7y ago

For the specific problem of benchmarking small code snippets, how do you create the initial small dataset?

cscheid 7y ago
Thank you for pointing out some bad phrasing on my part. When I said "small dataset", I should have said "small subset of all collected points that are initially fed to the model". The issue isn't that you have to collect the data little by little. The issue is that, once you've given a linear model an input that is outside the distribution which you're hoping to model, nothing about the model can be trusted. So you collect all the data points, but you don't give them all to the model at once. (I'm describing the RANSAC method here now) You start with a large number of "candidate models" that are all fit with a small number of input points, and then test which of the candidate models predict well the points you have not yet given the model. Then you feed the best of these candidate models only the points which it predicts well, and create a more refined, still outlier-free model. This can be proven to work in the presence of a small number of out-of-distribution points.
- derefr 7y ago
  Very interesting. It sounds to me like this approach exists outside any kind of Bayesian learning framework; i.e. an individual Bayesian agent couldn’t be expected to converge to a correct model here. Is that true? I would hazard that the RANSAC method sounds a lot like what you’d get out of a larger hybrid model, where e.g. many Bayesian agents with different priors are bred under a genetic algorithm after being ranked by their predictive power. (Like humans surviving to reproduce and pass down models to their children!)
  - cscheid 7y ago
    As far as i understand it the RANSAC arguments are very much not Bayesian (they're all about "if you repeat this an infinite number of times under an infinite number of new samples, then...", which is almost caricaturely frequentist). Still, you just gave me reason to mention one of my favorite "no, that won't work either" paper :) on how Bayes will not save you in the presence of model misspecification. Instead of butchering it any further, I'll just point you to this piece explaining the work, written by the author of the paper himself: http://bactra.org/weblog/601.html http://bactra.org/weblog/601.html

colmmacc 7y ago

There's another reason too; there are strong reasons why the timing of successive code executions should not be linear. Typically the first call to a function will incur the cost of fetching data into a cache. At minimum the basic blocks for the function will be loaded through the l1/l2/l3 pipelines. 2, 3, 4 function calls in a row will benefit from that caching, but also help train the speculative execution engine. At some point that speculation may radically alter performance. Later, with a sufficient number of runs, the timing will also suffer from preemption, context-switches, or other interruptions that can invalidate both the cache and the speculative execution engine. The idea that there is a fixed performance time for a function is naive on modern hardware.

cscheid 7y ago
You make a good point I hadn't considered. In that case, not even robust least squares will save you, because the samples are not independent of one another. You'd have to start looking into explicit time-dependent methods and yikes, I have no idea of what the literature says about time dependence and outliers. I wouldn't be surprised if it's "here be dragons" territory.
- colmmacc 7y ago
  Speculative execution optimizations, e.g. branch prediction, are even data dependent. It's a very complex measurement space!
- gdxhyrd 7y ago
  You are speaking as a stats person. :) While there are dozens of things that can go south in benchmarking, how to solve them is not about applying advanced stats, but about understanding and eliminating the sources of noise. Most benchmarks in CS can be done quite easily as long as one understands all the technology stack.
  - cscheid 7y ago
    I'm not a stats person! But I have been burned in real projects by doing the wrong thing. I just have learned --- the hard way --- to honestly appreciate it.

gdxhyrd 7y ago

> Please don't do that: they won't necessarily be the outliers in the dataset and your model will converge to the wrong thing. They are the outliers. These experiments are typically measuring something that is effectively constant with almost zero noise, rather than some complex physical phenomena. If you don't get an almost perfect fit, there is something going on that invalidates what you are doing (e.g. cache effects, clock effects, etc.). In fact, if there are any outliers, I would not trust the benchmark at all. So removing them seems like trying to fix a bad benchmark with statistics. > Statistics is hard. Like, really really hard. Stuff goes wrong all the time. Please leave it to the experts. That is unnecessary gatekeeping. Benchmarking in CS is hard not because the maths/stats that are needed are hard, but because setting up the right experiment is hard and most people don't know all the pitfalls. Therefore, if anything, you should leave benchmarks to CS/SE experts, rather than a statistician!