I'm new to the CS field and I have noticed that in many of the papers that I read, there are no empirical results (no code, just lemmas and proofs). Why is that? Considering that Computer Science is a science, shouldn't it follow the scientific method?
$\begingroup$
$\endgroup$
13
-
26$\begingroup$ The short answer is that "computer science" is many things. Some parts like (some) AI actually are science. Other parts are engineering, and the theoretical side is (applied) math. Parts of HCI are more like art. Computer science is a broad tent. $\endgroup$– Aaron RothCommented Feb 22, 2011 at 18:49
-
7$\begingroup$ If you have proofs, why do you even need empirical results? $\endgroup$– AryabhataCommented Feb 22, 2011 at 19:07
-
2$\begingroup$ @Moron: How do you prove that an algorithm is implementable without implementing it? $\endgroup$– Jukka SuomelaCommented Feb 22, 2011 at 19:34
-
10$\begingroup$ Theoretical CS seems to be akin to Mathematical Physics which also avoids empirical results. If you want something like Experimental Physics, you could look at research in Software Engineering, Program Verification, Database Systems etc $\endgroup$– Yaroslav BulatovCommented Feb 22, 2011 at 23:15
-
4$\begingroup$ nitpicking: "the scientific method"? $\endgroup$– KavehCommented Feb 23, 2011 at 7:07
|
Show 8 more comments
6 Answers
$\begingroup$
$\endgroup$
4
Mathematics is a science also, and you would have to search for a long time to find published empirical results in this field (although I guess there must be some). There are other scientific domains where "lemmas and proofs" are valued over experience, such as quantum physics. That said, most sciences mix theory and practice (with various ratios), and Computer Science is no exception.
Computer Science has its roots in Mathematics (see Turing's biography for instance http://en.wikipedia.org/wiki/Alan_Turing), and as such many results (generally dubbed as in the field of "theoretical computer science") consist in proofs that computers in some computational model can solve some problem in a given amount of operations (e.g. conferences such as FOCS, STOC, SODA, SoCG, etc..). Nevertheless, many other results of computer science are concerned with the applicability of those theories to practical life, through the analysis of experimental results (e.g. conferences such as WADS, ALENEX, etc...).
It is often suggested that the ideal is a good balance between theory and practice, as in "Natural Science", where the observation of experiments prompts the generation of new theories, which in turn suggest new experiments to confirm or infirm those: as such many conferences attempts to accept both experimental and theoretic results (e.g. ESA, ICALP, LATIN, CPM, ISAAC, etc...). The subfield of "Algorithms and Data Structures" in computer science might suffer of an imbalance in the sense that "Theoretical" conferences are generally more highly ranked than experimental ones. I believe that this is not true in other subfields of computer science, such as HCI or AI.
Hope it helps?
-
1$\begingroup$ Thanks, it helps a lot indeed. I have been interested in graph theory lately and in the papers I was reading, almost none of them had code or experimental results. This is why I asked. When you do pure maths, you cannot produce experimental results hence proofs are everything. But in Graph Theory it's not THAT hard to code your algorithm and produce useful experimental results! Let's take the MST problem. Current industry implementations are Prim/Kruskal and Boruvska and yet, more powerful algorithms are described in papers but they are not used since no one has ever coded them. $\endgroup$– totoCommented Feb 22, 2011 at 21:37
-
1$\begingroup$ Yes, you could implement algorithms from graph theory. But for many of the interesting problems in graph theory, that is at least $NP$-hard, that would be useless as only very small inputs would be (acceptably) computable due to the exponential-time complexity of the algorithms. $\endgroup$ Commented Feb 22, 2011 at 22:19
-
1$\begingroup$ @ toto Certainly what you are saying applies to some problems, but for the MST problem, you can see the results (maybe somewhat outdated) of implementing some of the powerful algorithms in books.google.com/… $\endgroup$ Commented Feb 22, 2011 at 23:01
-
1$\begingroup$ @toto. This is not the only reason older algorithms are used. For the TCS perspective $O ( n )$ is always better than $O( n \log n)$. But big-oh can hide a large constant that makes the algorithm impractical in practice. Such a work aims at TCS people and coding the algorithm would provide no gain or even confuse the reader. $\endgroup$– chazisopCommented Feb 23, 2011 at 2:05
$\begingroup$
$\endgroup$
6
Implementing algorithms well is a skill which takes a different set of tools than just proving theorems. Many algorithms which were discovered by the theory community have indeed been implemented in practice (although I would like to see the theory community take a bigger role in this process). Physics doesn't ask the same researchers to do theory and experiment, although it is expected that the two groups communicate. Why shouldn't you expect to see the same divide in computer science?
ADDED IN EDIT:
Expanding on my comment in answer to Suresh's about what I meant by "role" above, at Bell Labs and AT&T Labs, researchers in algorithms were encouraged to talk to people in development. I didn't do as much of this as I probably should have, but I did get at least one paper out of it, and I think it would be good for the field if there were more communication between people in theory at universities and practitioners. This doesn't mean that I think everybody who comes up with an algorithm should code it (even if it's practical).
On the other hand, coding algorithms (or having a student code them) that you think might be practical can be useful in getting them adapted by practitioners. Consider one example. Lempel and Ziv wrote two technical papers in 1977 and 1978 on new data compression algorithms. Everybody ignored them. In 1984, Welch wrote a much less technical paper giving a slight twist on LZ78 that improved its performance somewhat, and gave the results of a small study comparing its performance with other data compression methods. It was published in a journal read by a number of programmers, and the algorithm was given by a few lines of pseudocode. The method was quickly adapted in a number of places, eventually resulting in an infamous intellectual property dispute.
Of course, one of the best ways for algorithms researchers to communicate with practice is to produce grad students who go off and work at Google, IBM, or other companies, and we're already doing that. Another way might be to answer practitioner's questions in this forum. Hopefully, we're doing a reasonable job of that as well.
answered Feb 23, 2011 at 21:35
-
4$\begingroup$ So you're saying that even though in physics there's no expectation of the same person doing both, in theoryCS we should do both ? is it because models of computation are much more of an approximation to reality than physics models ? $\endgroup$ Commented Feb 23, 2011 at 21:51
-
11$\begingroup$ I'm saying that the theorists should talk more to the practitioners. If you look at the history of physics, bad things start happening when theorists stop talking to experimentalists. I actually think we have a reasonable amount of communication between the two groups right now, but that it wouldn't hurt to have some more. $\endgroup$ Commented Feb 23, 2011 at 22:02
-
3$\begingroup$ I won't generalize but I think that many researchers simply cannot code/don't like to and they would rather let the practical work be done by one of their students. That's the case with me and my mentor. $\endgroup$– totoCommented Feb 23, 2011 at 22:27
-
1$\begingroup$ Nice. btw in retrospect my comment made it sound like I was arguing with you, whereas my intent was only clarification. I also know well the beneficial aspects at AT&T of talking to researchers outside algorithms :) $\endgroup$ Commented Feb 24, 2011 at 16:57
-
3$\begingroup$ The history of Lempel-Ziv, and looking at posts on StackOverflow, have just led me to formulate a very simple precept which might help get algorithms theorists come up with implemented vy practitioners: If you think your algorithm might be practical, put pseudocode in your paper. $\endgroup$ Commented Feb 26, 2011 at 14:53
$\begingroup$
$\endgroup$
5
One research area that uses empirical methods and methods of Theoretical Computer Science is the field called "Experimental Algorithmics" or "Algorithm Engineering". Like Chris mentioned, high performance computing relies heavily on this as modern systems have complex cache and latency issues that we have a hard time modeling.
Gerth Brodal and Peter Sanders are good examples of researchers who maintain a foot in both the "proof" and "empirical" realms.
--Update 1/20/2013-- I would also mention a great presentation by Robert Sedgewick.
-
4$\begingroup$ Both ALENEX and ESA encourage applied algorithms work, and there's also a conference (SAE) on this topic. $\endgroup$ Commented Feb 22, 2011 at 23:53
-
$\begingroup$ What is SAE? That TLA is ungoogleable. Do you have a URL for it? $\endgroup$ Commented Feb 23, 2011 at 4:31
-
6$\begingroup$ SAE is a typo for SEA, the Symposium on Experimental Algorithms. $\endgroup$ Commented Feb 23, 2011 at 7:23
-
1$\begingroup$ You can also do Algorithm Engineering in a more rigorous way, i.e. refine theoritcal models so they fit reality but stil do precise analyses. It's hard, though. $\endgroup$– RaphaelCommented Feb 24, 2011 at 17:24
-
$\begingroup$ @Raphael You would have to model a sphere around each VonNeuman compute node and explicitly put and get memory objects with a latency cost proportional to the distance; random access is $O(CubeRoot(n))$, the diameter of the memory sphere, speed of light is your best case latency. $\endgroup$ Commented Nov 20, 2014 at 18:14
$\begingroup$
$\endgroup$
This depends on the discipline you are in; as Jeremy states, there is a spectrum of theory vs. practice.
Topics like complexity tend to be weighted towards the theory side, as often the goal is to find a boundary for the space or runtime. Implementing an algorithm in C++ and then running it a bunch of times isn't going to prove that a problem is NP-complete.
As a polar opposite, high-performance computing (with conferences like Supercomputing) are all empirical; no one would ever submit a proof to an HPC publication as there is too much variability with regard to memory hierarchy and kernel overhead.
So what seems like the same question (How long does something take to run?) will be approached two completely different ways depending on the goals, techniques, community, etc. See Poul-Henning Kamp's You're Doing It Wrong for an example of the dissonance.
$\begingroup$
$\endgroup$
In programming languages research many ideas for new programming language constructs or new type checking mechanisms stem from theory (perhaps informed by experience in practice, perhaps not). Often a paper is written about such mechanisms from a formal/theoretical/conceptual perspective. That's relatively easy to do. Next comes the first hurdle: implementing the new constructs in the context of an existing compiler and experimenting with it, in terms of efficiency or flexibility. This too is relatively easy.
But can we then say that the programming construct constitutes an advance to the science of programming? Can we say that it makes writing programs easier? Can we say that it makes the programming language better?
The answer is no. A proper empirical evaluation involving scores of experienced programmers over large periods of time would be needed to answer those kinds of questions. This research is hardly ever done. The only judge of the value of a programming language (and its constructs) is the popularity of the language. And for programming language purists, this goes against what our hypotheses tell us.
answered Feb 23, 2011 at 7:20
$\begingroup$
$\endgroup$
Perhaps I'm missing the motivation for your question but there are many examples of empirical results motivating research, algorithms and other results.
MP3 use psychoacoustic to optimize the algorithm for human encoding.
Plouffe gives an account of discovering the BBP spigot algorithm for the digits of $\pi$ where he recounts the use of whatever Integer Relation Algorithm Mathematica was using to discover the formula.
Along the same line, Bailey and Borwein are big proponents of experimental mathematics. See "The Computer as Crucible: An Introduction to Experimental Mathematics", "Computational Excursions in Number Theory" amongst others. One might argue that this is more experimental Mathematics but I would argue that at this level the discussion the distinction is semantic.
Phase transitions of NP-Complete problems are another area where empirical results are heavily used. See Monasson, Zecchina, Kirkpatrick, Selman and Troyansky and Gent and Walsh for starters, though there are many, many more (see here for a brief survey).
Though not quite on the level of Theoretical Computer Science or Mathematics, there is a discussion here about how the unix utility grep's average case runtime beats optimized worst case algorithms because it relies on the fact that it's searching human readable text (grep does as bad or worst on files with random characters in them).
Even Gauss used experimental evidence to give his hypothesis of the Prime Number Theorem.
Data mining (Bellkor's solution to the Netflix Prize to make a better recommendation system) might be argued to be a theory completely based on empirical evidence. Artificial Intelligence (genetic algorithms, neural networks, etc.) relies heavily on experimentation. Cryptography is in a constant push and pull between code makers and code breakers. I've really only named a few and if you relax your definition of empirical, then you could cast an even wider net.
My apologies for being so scattered in answering your question but I hope I've given at least a few examples that are helpful.
