Scientific debugging

2010-10-28 20:09
Quite some years ago I ready Why programs fail - a systematic guide to debugging - a book written on the art of debugging programs written by Andreas Zeller (Prof. at University Saarbrücken, researcher working on Mining Software Archives, Automated Debugging, Mutation Testing and Mining Models and one of the authors of famous Data Display Debugger).

One aspect that I found particularly intriguing about the book was up to then known to me only from the book Zen and the Art of Motorcycle Maintenance: Scientific debugging as a way to find bugs in a piece of software in a structured way with methods usually known from the scientific method.

When working together with software developers one theme that often occured to me as very strange is other developers - especially Junior level developers' - ways of debugging programs: When faced with a problem they would usually come up with some hypothesis as to what the problem could be. Without verifying the correctness of that hypothesis they would jump directly to implementing a fix for the perceived problem. Not too seldom this led to either half baked solutions somewhat similar to the Tweaking the Code behaviour on "The daily WTF", or - even worse - to no solution at all after days of implementation time were gone.

For the rest of this posting I'll make a distinction between the terms

  • defect for a programming error that might cause unintended behaviour.
  • failure for an observed mis-behaviour of a program. Failures are caused by specific defects.

For all but trivial bugs (for your favourite changing and vague definition of "trivial") I try to apply a more structured approach to identifying causes for failures.

  1. Identify a failure. Reproduce the failure locally whenever possible. To get most out of the process write some automated test that reproduces the failure.
  2. Form a hypothesis. Usually this is done sub-consciously by most developers. This time around we explicitly write down what we think what the underlying defect is.
  3. Devise an experiment. The goal here is to show experimentally that your hunch about the defect was correct. This may involve debug statements, more extensive logging, using your favourite debugger with a break point set exactly at the position where you think the defect lies. However the experiment could also involve using wireshark or tcpdump if you are debugging even simple distributed systems. On the other hand for extremely trivial defects the experiment could just be to fix the defect and see the test run through successfully.
  4. Observe results.
  5. Reach a conclusion. Interpret the result of your experiment. If they reject your hypothesis move on to your next potential cause for the failure. If they don't you can go on to either devise more experiments in support of your hypothesis if the last one didn't convince you (or your boss) or fix the defect just found. In any case you should tidy up any remains of your experiment before moving on in most cases.

When taking a closer look at the steps involved it's actually pretty straight forward. This makes this method so easy to use while still being most effective. When combined with automated testing it even helps when squashing bugs in code that is not written by the person fixing it. One way to make the strategy even stronger is to support the process by manually writing down a protocol of the debugging session with pen and paper. Not only does this help avoid checking the same hypothesis over and over again. It's also a way to quickly note down all hypothesis': In the process of debugging the person doing the analysis might be faster thinking of new possible causes than he can actually check. Noting them down helps keeping one's mind free and open as well as remembering all possible options.

Machine Learning Gossip Meeting Berlin

2010-10-25 18:51
This evening the first Machine Learning Gossip meeting is scheduled to take place at 9p.m. at Victoriabar: Professionals working in research advancing machine learning algorithms and industry projects putting machine learning algorithms to practical use meet for some drinks, food and hopefully lots of interesting discussions.

If successful the meeting is supposed to take place on a regular schedule. Ask Michael Brückner for the date and location of the next meetup.

NoSQL summer Berlin - this evening

2010-08-11 06:38
This evening at Volkspark Friedrichshain, Café Schoenbrunn the next NoSQL summer Berlin (organised by Tim Lossen) is meeting to discuss the paper on Amazon's Dynamo "Dynamo: Amazon's Highly Available Key-value Store". The group is planning to meet at 19:30 for some beer and discussions on the publication.

Seminar on scaling learning at DIMA TU Berlin

2010-03-17 21:10
Last Thursday the seminar on scaling learning problems took place at DIMA at TU Berlin. We had five students give talks.

The talks started with an introduction to map reduce. Oleg Mayevskiy first explained the basic concept, than gave an overview of the parallelization architecture and finally showed how jobs can be formulated as map reduce jobs.

His paper as well as his slides are available online.

Second was Daniel Georg - he was working on the rather broad topic of NoSQL databases. Being too fuzzy to be covered in one 20min talk, Daniel focussed on distributed solutions - namely Bigtable/HBase and Yahoo! PNUTS.

Daniel's paper as well as the slides are available online as well.

Third was Dirk Dieter Flamming on duplicate detection. He concentrated on algorithms for near duplicate detection needed when building information retrieval systems that work with real world documents: The web is full of copies, mirrors, near duplicates and documents made of partial copies. The important task is to identify near duplicates to not only reduce the data store but to potentially be able to track original authorship over time.

Again, paper and slides are available online.

After a short break, Qiuyan Xu presented ways to learn ranking functions from explicit as well as implicit user feedback. Any interaction with search engines provides valuable feedback about the quality of the current ranking function. Watching users - and learning from their clicks - can help to improve future ranking functions.

A very detailedpaper as well as slides are available for download.

Last talk was be Robert Kubiak on topic detection and tracking. The talk presented methods for identifying and tracking upcoming topics e.g. in news streams or blog postings. Given the amount of new information published digitally each day, these systems can help following interesting news topics or by sending notifications on new, upcoming topics.

Paper and slides are available online.

If you are a student in Berlin interested in scalable machine learning: The next course IMPRO2 has been setup. As last year the goal is to not only improve your skills in writing code but also to interact with the community and if appropriate to contribute back the work created during the course.

Learning to Rank Challenge

2010-03-09 19:49
In one of his recent blog posts, Jeff Dalton published an article on currently running machine learning challenges. Especially interesting for those working on search engines and interested in learning new rankings from data should be the Yahoo! Learning to Rank Challenge to be held in conjunction with this year's ICML 2010 in Haifa, Israel. The goal is to show that your algorithm does not only scale on real-world data provided by Yahoo!. Tasks are split in two. The first one focusses on traditional learning to rank procedures, the second one on transfer learning. Tracks are open to participants from industry and research.

A second challenge was published by the machine learning theory blog. The challenge is hosted by Yahoo! as well and deals with Key scientific challenges in statistics and machine learning.

Both programs look pretty interesting - would be great to lots of people from the community participating and comparing their systems.

MLOSS workshop at ICML accepted

2010-02-15 19:31
The workshop on machine learning open source software has been accpted. Find further details on the workshop homepage.

Submissions are open until April 10th, Samoa time.