9 ms·
How to implement an algorithm from a scientific paper
- smiddereens 14y agoPray for an appendix with source code.
- dmlorenzetti 14y agoIt's kind of funny that the article lists "authors citing their own work" as an identifying feature of groundbreaking research. I don't know about CS, but in most scientific fields, this may be a bad sign. It can mean they're just trying to pump up their own reference counts, or it can mean they don't really know what other people are doing. The only way to be sure that neither of these is the case is to know, a priori, that they're truly doing groundbreaking work.
- arethuza 14y agoI think the warning sign should really be if an author only cites their own work, from what I recall having a small number of references to your own previous work that you are building on is pretty standard and desirable as most research is incremental.
- sophacles 14y agoThis is true. A lot of times the process goes: 1. Here is a paper about some interesting things we've been looking at, here is what we know, here are some ideas we are building on. These tend to be presented at conferences, as a "what do you guys think?" sort of introduction for the larger community. It is nice, because other researchers can then tell you if this is actually new, or just a repeat of an idea (that was hard to find because it used different terms and went nowhere), or something worth looking into, or the old "hey, here's some pitfalls I see from my expertise". 2. A couple more conference papers with results building on the ideas in the seminal paper in 1. These are just to keep awareness of your work to others in the field, get feedback, and to play the game right - you get much less credit if you don't have a history of showing you've been working on this for a while when someone comes along and "scoops" you. 3. Actually interesting/important work. This is the type of paper that the OP calls "groundbreaking". After all that work (see documentation over the years), here is something pretty awesome! Another facet of this process: When doing research, you have no idea what you are doing. I mean, you have expertise and goals and hypothesis/theory, but you don't know how it will pan out. You don't know if you suddenly find a spot where a left turn is required. So publishing about these new things is a good idea. Other people in the field can benefit from just that. Further, in my experience, each small result tends to spawn more questions/investigatory tracks, etc than it closes. So a lot of papers with honest "future work" sections are great places for grad students and others new to the field to dive in and get their feet wet. They can follow some of the tracks the original researchers just had no time for, and help fill in gaps. Finally, the self reference is a good sign, because it establishes you aren't just some person coming out of left field with $BIG_IDEA (which looks a bit crack-pot-esque...)
- lake99 14y agoNot funny at all. Referencing your own work, by itself, is not a bad sign. In many cases, the groundbreaking work take several years to accomplish. The years of work generate several new ideas on their own, resulting in several related papers.
- mturmon 14y agoYes. The OP agrees; here is the full context of the quote: "Groundbreaking papers...out of research teams in smaller universities that have been tackling the problem for about six to ten years. The later is easy to spot: they reference their own publications in the papers, showing that they have been on the problem for some time now, and that they base their new work on a proven record of publications."
- shardling 14y agoYou completely misread that bit -- citing your own work is noted as a sign of incremental research done over several years. It was in the discussion of different types of groundbreaking research.
- jmilloy 14y agoIt's pretty clear when they are trying to pump references; the papers they reference may be tangentially on not even related, or have no new content.
- _delirium 14y ago> just trying to pump up their own reference counts Don't most bibliometrics exclude self-citations?
- bendmorris 14y agoIn my field (ecology and evolutionary biology) there's a small but concerted push to get people to publish "executable papers" where all code and data is available via GitHub, on an iPython notebook, etc. so that all figures and test cases can easily be reproduced by reviewers and researchers. If you're publishing research, it shouldn't be the reader's job to parse your paper and reimplement the research you describe; it should be on you to make your results replicable, and I think this is a standard we need to insist upon. I can't count how many papers I've read lately that were missing either crucial methods or underlying data so that replication was impossible. edit: Here's an example: https://github.com/weecology/white-etal-2012-ecology https://github.com/weecology/white-etal-2012-ecology Run portions of the analysis pipeline: Empirical analyses: python mete_sads.py ./data/ empir Simulation analyses: python mete_sads.py ./data/ sims Figures: python mete_sads.py ./data/ figs
- mej10 14y agoThis should be the default for all code and data produced by publicly funded research.
- 46Bit 14y agoYes, although I don't think this is just a question of open access. It's a question of research verification - and expected of all published research.
- vidarh 14y agoThat's great... When I did my MSc (my thesis was on reducing error rates in OCR), of the dozens of computer science papers I surveyed, there were perhaps 2-3 where I didn't have to do extensive "reverse engineering" of the results of the papers to figure out a whole lot of unstated assumptions when I wanted to test their algorithms. It was a tremendous waste of time... Especially when pretty much all of these papers described results that meant the authors had already implemented their algorithms in executable form. But almost none of them made the code available in any form whatsoever.
- 14y ago
- bjoernbu 14y agoWhile peer review is flawed in so many ways and neither all papers accepted at top conferences are good, nor all good papers get accepted, it has still some meaning. When deciding which paper to read, it can be a great hit where it was published. The link merely claims groundbreaking work was published in the best "journals". Especially in computer science, conferece papers are where recent, groundbreaking work is published and good conference are the ones that are hard to get into. However, I agree that groundbreaking work ofter gets a longer follow-up journal aritcle. But those usually appear years later and for those algorithms it is likely that there are existing implementations available by that time.
- omaranto 14y ago6.3 and 6.4 read funny one after the other: put references to the paper in the comments, but change all the notation from the paper.
- 1wheel 14y agoProbably the worse piece of advice in the article : > 6.4 – Avoid mathematical notations in your variable names Let’s say that some quantity in the algorithm is a matrix denoted A. Later, the algorithm requires the gradient of the matrix over the two dimensions, denoted dA = (dA/dx, dA/dy). Then the name of the the variables should not be “dA_dx” and “dA_dy”, but “gradient_x” and “gradient_y”. Similarly, if an equation system requires a convergence test, then the variables should not be “prev_dA_dx” and “dA_dx”, but “error_previous” and “error_current”. Always name things for what physical quantity they represent, not whatever letter notation the authors of the paper used (e.g. “gradient_x” and not “dA_dx”), and always express the more specific to the less specific from left to right (e.g. “gradient_x” and not “x_gradient”). Especially when you're just starting out, creating your own naming scheme just creates more opportunities to do something wrong.
- scrumper 14y agoHave to disagree. Those derivatives are a bad example of a good point. Most mathematical symbols aren't representable in code, at least until we're able to use unicode identifiers and sub/superscripts in every language. When you're forced to write 'theta' instead of θ then you might as well just say 'angle' so your future maintenance programmer will have an easier time of it. An equation and an algorithm might achieve the same result but the ways they get there are so different that using different notation styles makes perfect sense. For example, a simple finite summation is a compact block in mathematical notation but it's a multi-line for loop in C. Trying to force the constraints of the 'source' notation on the implementation makes no sense. Remember, dA/dx means 'gradient'. You're not creating your own naming scheme, you're translating the concept of 'gradient' to the appropriate notation for the medium you're working in.
- mistercow 14y ago
- mistercow 14y ago>If you are in the U.S., beware of software patents. Some papers are patented and you could get into trouble for using them in commercial applications. Is it only commercial applications that you have to worry about? I was under the impression that even a free implementation would be infringing the patent and make you liable for damages.
- brainid 14y agoFree implementations are liable. See Madey v. Duke University. It severely restricted the research exemption (http://en.wikipedia.org/wiki/Research_exemption http://en.wikipedia.org/wiki/Research_exemption) I have had University Council tell me I cannot open source code I have written implementing patented algorithms. It is unfortunately more common than most people think, and often not acknowledged in publications.
- Gravityloss 14y agoIt's interesting to note how Matlab is still so fast to prototype stuff in. I've done it myself countless times. Data generation, input, manipulation, output and result checking are all very good. Maybe things like Go can change that, or then some optionally typed language. There is no fundamental reason not to get massive improvements.
- carterschonwald 14y agoIndeed. These plenty of room for improvement in the tools for implementing such algorithms. I'm actually spending a bit of time on the algorithm engineering and data provenance bits
- carterschonwald 14y agoIndeed. These plenty of room for improvement in the tools for implementing such algorithms. I'm actually spending a bit of time on the algorithm engineering and data provenance bits
- nullc 14y agoThe site is down now, so I haven't seen the article— but I hope it just says "(1) give up and beg the author for their implementation, which undoubtedly contains 2 megabytes of opaque unmentioned magic constants."
- binarymax 14y agoI got into a situation a couple years ago, where I wanted to understand how relational databases worked. I mean how they really worked. Down to the algorithms and processes that implemented query parsing and ACID - purely so I could try and toy around with implementing some OLAP stuff on my own, without all the 'overhead' of the rest of the database (at the time I didn't really care about transactions or query optimization). I ended up getting into a pile of papers so deep I thought I would never escape, and eventually gave up. I even ordered a thick book that was a collection of papers, tying it all together. Some of the papers on the subject - the groundbreaking ones by folks like Goetz Graefe - were brilliant and very interesting reads, but at the same time were so involved I felt like I would need to dedicate years before even scratching the surface. Walking away, I did learn to see the difference between good papers and bad, and learned a heck of a lot on DB internals (good through the end of the 90's at least). But I think I'll stick with books from now on :)
- Cyranix 14y agoI bumped into #1.4 (patented research) not too long ago -- I wanted to try out Bi-Normal Separation for feature space reduction in a machine learning classifier, but BNS comes out of HP Labs and would need to be licensed. I think the wording on this point needs to be changed; why would it only apply to those in the US?
- Gmo 14y agoBecause, officially at least, software patents in the EU are not allowed.
- ChristianMarks 14y agoI recently refereed a paper in computational geosciences and recommended substantial revision because the authors did not make their source code available for evaluation. The paper was ultimately rejected.
- wheaties 14y agoWhen my other half was going through her PhD, she was attempting to implement a signal processing approach to construct grids for FEM. Eventually adding some constraints led to an acceptable result. As she presented her findings at a conference the author of the paper eagerly questioned her about her approach. Why? He had never gotten it to work and failed to mention that next to the glowing praise heaped upon the technique.
- jmilloy 14y agoGood thing he published then! It may have been a long time before someone thought of the approach and ironed out all of the implementation details. This sounds like exactly how science progresses... incrementally building on the work of others.
- joe_the_user 14y agoIt seems like one should say "that's how scholarly research progresses". To be science as such it seems like one has to do some verification as well as some speculation.
- dmpk2k 14y agoAlternatively, such a paper could lead many a reader to implement a dead end. Each assumes they did it wrong, and after much wrangling, silently move on. Later, the next intellectual victim comes along.
- jamieb 14y agoWith regard to section 3.5 "Know the definition of all terms", I found that in a given field these terms change over time. I wasn't really aware of it, and then I went back to a paper after reading about Domain Maps in Eric Evan's Domain Driven Design. Lightbulb! I quickly made a list of the terms used in each paper, and then drew lines between the identical or related terms. I have for some time been attempting to learn everything I can about automated theorem proving. A key paper is Robinson's 1965 paper "A Machine-Oriented Logic Based on the Resolution Principle". It uses quite different notations compared to, say, Kowalski's "Logic for Problem Solving". Robinson made an important contribution, but his work is like the assembly language of logic. Modern papers are much higher level. Kowalski's book is 1979, so its like C. My new domain map made these works much more comprehensible, especially as I switched between them. The other good point is patents. That's why I'm reading papers from 1965 and books from 1979.
- denzil_correa 14y agoHarsh Truth - Sometimes the algorithm is on purpose obfuscated to make the authors gain a competitive edge. PS - Speaking from CS perspective.
- marshray 14y agoHow about this one: Figure out if the pseudocode notation in the paper is using 0- or 1-based array indexing. If the paper doesn't match your implementation language, consider doing the initial implementation using an array adapter class. The adapters can be removed later if they reduce performance, but they will likely have save you a number of maddening errors in the meantime.
- willcodeforfoo 14y agoI'm a little ignorant on the topic, what legal rights do I have to use a (self)implemented academic paper?
- Xcelerate 14y agoThis is very interesting and something I've been thinking about lately. My research is in molecular dynamics. I've only been a grad student for one semester, but I've written a lot of code. The code I am currently working on takes a force-field description, combines it with a listing of atom coordinates, and completely automates the production of an input file to a simulation program. (This is less trivial than it sounds. All stretching, bending, torsional, and improper atom connections must be generated. Bond-orders must be determined, solely from the structure. And then this is combined with equations from the paper describing the force-field to give an energetic potential for each connection type). I would think this code could have a lot of value to other researchers. Though I doubt anyone in non-CS departments have even heard of Github.
- jongraehl 14y ago"create your own type to encapsulate the underlying type (float or double, 32-bit or 64-bit), and use this type in your code. This can be done with a define is C/C++ or a class in Java." No. A Java class would certainly have worse performance than just float or double, since each instance would be individually heap allocated, have the usual per-Object overhead. Better use text preprocessing (or just "double") than that. (otherwise, this is all fine advice)
- jwr 14y agoThere is one increasingly common kind of paper out there, the 'obfuscapaper'. It's a paper which pretends to outline all the steps, but really doesn't -- key information is either missing or obfuscated. You often see that with papers published by people working at companies, or by people who are about to leave academia to work at a company. Problem is, this kind of obfuscation is really difficult to spot unless you actually understand the paper and see all the steps necessary to implement the algorithm.