29

In computer science field is common to produce papers that present algorithms that estimate something with a certain accuracy and a certain speed.

Many algorithms can clearly be tuned to have high performances, compromising a bit accuracy, or high accuracy, compromising in this case performances.

When an author proposes a new algorithm he should present empirical results about performances AND empirical results about accuracy.

Is it honest to present result about performances obtained with the algorithm tuned to be fast (and less accurate), and results about accuracy with the algorithm tuned to be precise (and slow)?

  • 16
    See also Volkswagen who are embroiled in a serious scandal for doing almost exactly what you describe. Namely, they programmed their deisel cars to have a certain engine tuning in some situations and a different engine tuning in others. That's not necessarily a big deal on its own, it became a big deal because they did not disclose that their engines used different turnings, and they programmed them that way for the exact purpose of deceiving everyone regarding the measured engine characteristics. – Todd Wilcox Apr 21 '16 at 9:34
  • 15
    Unfortunately this happens a lot in CS, specially in machine learning and so. Please, disencourage this behavior. This is what makes people skeptic about CS, the fact that is so easy to do. Do not contribute to the degradation of the field, but the opposite, try to clean it! – Ander Biguri Apr 21 '16 at 11:22
  • 37
    I would in fact expect a graph plotting accuracy versus runtime. – MSalters Apr 21 '16 at 12:10
  • 8
    My general rule of thumb: If you are completely upfront and clear about the results, there is no ethical problem. – Bitwise Apr 21 '16 at 12:14
  • 1
    When an author proposes a new algorithm he should present empirical results — ...unless it's a theory paper. (cough) – JeffE Apr 21 '16 at 22:41
63

It would be dishonest to do this without mentioning that the algorithm was tuned differently. You ought to specify what the tuning changed and how this affects the results of the algorithm.

You should also list accuracy results for the fast algorithm and speed results for the accurate algorithm. (Your probably also want some numbers for middle of the road tuning too). Not listing the "bad" results isn't dishonest, but it's bad science. If you didn't include these numbers, I'd expect your reviewers to bring it up and ask for them.

  • It's the 'without mentioning' part that makes this answer the best. Why do you think so many TV ads have fine print? – candied_orange Apr 24 '16 at 3:45
53

To paraphrase your question, "Is it honest to suggest that my algorithm is both fast and accurate when, in fact, it can only be fast and not-so-accurate or accurate and not-so-fast?"

NO!!!

Of course it isn't. Seriously, why do you even need to ask?

16

I am just a Master student, so I do not know much of the dynamics of “the game”. Therefore I can only give some spectator opinion.

One of my supervisors likes to have brutally honest plots in his papers. His work focuses on the scaling of parallel algorithms. For starters, he chooses strong scaling instead of weak scaling. The former is taking a fixed problem size and using more processors $P$ to run. Ideally, one would obtain a $1/P$ drop in time. Taking a double-log-plot of time versus process count and also plotting the $1/P$ perfect curve, you see quickly when it goes bad.

Weak scaling is scaling of the problem size with the resources. Then the time needed should stay constant. For problems which become hard to parallelize at some fine level, you will never see anything interesting in weak scaling. With strong scaling you can go into the extremes like “one pixel per core” or “one atom per thread”.

He said that the interesting parts (in science) are those that do not work yet. He surely can make up a plot that makes the algorithm look great. But that is not what he is interested in. He wants to know how far it can be pushed.

I really admire this brutal honesty. If one has results which are only so-so, then this method will clearly show that they are not that great. On the other hand, if you take away all the attack surface yourself, nobody can rip you apart later for hiding anything.

Therefore I would make plots which show how bad the accuracy gets when you optimize for speed. I'd include a honest accuracy vs. speed (or vice versa) plot. Then one can either see whether there is a sweet spot in the middle and how well that actually is.

If your algorithm goes to the very extremes but has a nice middle ground, it is worth mentioning, I guess. And if the extremes are only a few percent slower or less accurate, that also is a result.

6

Compare apples with apples

Algorithm performance is rarely evaluated in isolation: usually, different algorithms are compared to one another or to some reference algorithm. When doing such a comparison, you should determine conditions in which reference algorithms were evaluated, and evaluate your own algorithm in the same conditions:

  • if reference algorithms have comparable accuracy, tune your algorithm to have the same accuracy and compare the performance
  • if reference algorithms have similar performance, tune your own to the same performance and compare the accuracy

On the contrary, if you have comparison data in different conditions, it is OK to select the conditions which are most favorable to your algorithm. This is not cheating, but a legitimate analysis of conditions in which your algorithm is the most practical.

1

Until now, I have refrained from joining this site as I did not feel qualified to comment. I left the world of academia two days before I was supposed to have graduated with a BS. (I'll leave my sordid story as a comment). I finally joined this site just because of this question. The answer is NO. "Tuned" algorithms from academic researchers bedevil practitioners.

A specific example: I spent two absolutely wonderful years determining how to detect thruster failures on a space vehicle. A previously developed "tuned" algorithm suggested that one could do without the very expensive and failure-prone sensors traditionally used to detect thruster failures by instead using accelerometer and gyro readings. That "tuned" work implicitly assumed perfectly-aligned and perfectly-located thrusters with lots and lots of oomph. I, on the other hand, had to deal with the equivalent of a Mack truck on ice with misaligned VW engines and no breaks. I didn't have a simple signal to noise problem to contend with. I had to contend with a noise to signal problem.

I used a Bayesian approach. Hardly anyone understood my mathematics. Another (very expensive) group was consulted to ensure that what I did was sound. They saw the same noise-to-signal problem, but they used a frequentist approach to solve the problem. (Hardly anyone understood their mathematics, either.) While they were frequentists and I was a Bayesianist, they concurred that my approach was valid. In the end, it cost two years of my time and a year of that other group's time. Compare that to $200K for sensors plus a few months of the time needed by a low-level programmer, whose code could easily be understood by all. While I had massive geek fun, investing in me and that other group was stupid from both an economic and maintainability point of view.

I have seen this time and time again over the course of my career.

  • My sordid story: I had been accepted to a PhD physics program, thanks much to recommendations by my undergrad research advisor, only to be told by my academic advisor that I was not graduating. He did this two days before graduation, on a Saturday, when I was 150 miles from my school, where I was the best man at my best friend's wedding. I was told after the fact that I appeared more nervous than either the bride or the groom. – David Hammen Apr 24 '16 at 11:04
  • I eventually did get that damned degree. My advisor found a clause that said I needed to take four liberal arts courses as a freshman and sophomore, and four more as a junior and senior. I instead took five and three. I later took a class at a different school on Shakespeare, restricted to senior English majors. The instructor reluctantly accepted me, but said it would be my fault if I couldn't produce quality results. I got an A-. My advisor said "you aren't graduating, ever, over my dead body." I got smart enough to go over his head. I donated money to competing Ivy League schools for years. – David Hammen Apr 24 '16 at 11:11
0

In the context of developing algorithms for academic purposes the real 'wall-clock' running time of the program is not important. What is important is the time complexity (see the Big-Oh notation). Usually a few performance tweaks or optimizations to an algorithm do not change the actual time complexity and are thus of little interest.

If an algorithms does change the time complexity, but also changes the accuracy the algorithm has solved a different problem and is not comparable. Still comparing these is a case of serious neglect at least.

Unfortunately, in the real world, only 'trivial' problems, such as sorting a list are so well defined that everybody makes an algorithm that has exactly the same pre- and post-conditions. A good paper comparing algorithms should recognize these difference and investigate their impact.

  • 2
    the real 'wall-clock' running time of the program is not important. [citation needed]. When algorithms are benchmarked on realistic datasets, running time is important, because the big o is usually fixed. Take, for example, any paper on neural networks: they are O(n), but using one non linearity function or another can have huge impacts in accuracy and / or performance. – Davidmh Apr 22 '16 at 8:17
  • 1
    The difference between a computer from 1986 and one from 2016 is a constant factor, therefore of little interest :-) The difference between a 19200 bit modem and gigabit ethernet is a constant factor, therefore of little interest. – gnasher729 Apr 23 '16 at 17:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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